python - Koch雪花渲染时间(以及如何使用turtle绘制雪花)

Question

我目前正在研究 MIT 6.006 类(class)的在线类(class) Material ，以获取乐趣。我正在处理问题集#2(找到 here )，并对科赫雪花问题(问题#1)的渐近渲染时间的计算有疑问。

根据解决方案，当CPU负责渲染和坐标计算时，渐近渲染时间比CPU和GPU之间分割进程的情况要快。数学对我来说很有意义，但是有人对为什么这是真的有直觉吗？

在我看来，CPU 仍然需要计算渲染雪花的坐标(Theta(4^n) 时间)，然后渲染图像。在我看来，这些应该是加法，而不是乘法。

然而，解决方案表明这些是乘法的，因此由于每个三角形/线段都较短(对于问题 1 中的最后两个子问题)，运行时间减少到 Theta((4/3)^n) 或 Theta( 1)!

我不是计算机科学家——这对我来说只是一个有趣的爱好。我真的很感谢你们其中一位天才的回答:)

此外，我在使用 python 海龟模块时也得到了一些乐趣。下面是一些在 python 中绘制科赫雪花的非常不完美的代码:

import turtle

def snowflake(n,size=200):
    try: turtle.clear()
    except: pass
    turtle.tracer(0,0)
    snowflake_edge(n,size)
    turtle.right(120)
    snowflake_edge(n,size)
    turtle.right(120)
    snowflake_edge(n,size)
    turtle.update()
    turtle.hideturtle()

def snowflake_edge(n,size=200):
    if n==0:
        turtle.forward(size)
    else:
        snowflake_edge(n-1,size/3.0)
        turtle.left(60)
        snowflake_edge(n-1,size/3.0)
        turtle.right(120)
        snowflake_edge(n-1,size/3.0)
        turtle.left(60)
        snowflake_edge(n-1,size/3.0)

Answer 1

正如问题集P.5的注释所示，CPU和GPU采取的方法是不同的。

仅CPU(无硬件加速)的方法是首先计算需要绘制的内容，然后将其发送到GPU进行绘制。由于我们假设光栅化的成本大于收集线段的成本，因此绘制图像的时间将由 GPU 主导，其成本将与它实际需要的像素数量成正比。画画。

GPU-CPU(具有硬件加速)方法计算所有大小的三角形，然后将它们发送到 GPU 绘制大三角形，删除中间像素，绘制较小的三角形，删除不需要的像素，等等。由于绘制需要很长时间，那么GPU用于绘制和删除的时间将主导所花费的总时间；由于大多数(渐近，100%)绘制的像素最终都会被删除，因此所花费的总时间将大大超过实际需要绘制的像素数量。

换句话说:硬件加速场景将大部分工作转储到 GPU，而 GPU 比 CPU 慢得多。如果 GPU 正在处理时 CPU 有其他事情要做，那么这是可以的；然而，这里的情况并非如此；因此，当 GPU 进行绘图时，CPU 只是在浪费周期。