科赫雪花渲染时间（以及如何使用乌龟绘制雪花）

Question

我目前正在学习麻省理工学院 6.006 在线课程 material 的乐趣。我在处理问题集 #2（找到 here）并且对 koch 雪花问题（问题 #1）的渐近渲染时间的计算有疑问。

根据解决方案，当CPU负责渲染和坐标计算时，渐近渲染时间比进程在CPU和GPU之间拆分要快.数学对我来说很有意义，但是有谁知道为什么这是真的吗？

在我看来，CPU还是要计算坐标渲染雪花（Theta(4^n)次），然后渲染图像。在我看来，这些应该是相加的，而不是相乘的。

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

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

此外，我在玩 python turtle 模块时获得了一些乐趣。这是在 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-only（没有硬件加速）的方法是先计算需要绘制的内容，然后将其发送给GPU进行绘制。由于我们假设光栅化的成本大于收集线段的成本，因此绘制图像的时间量将由 GPU 控制，其成本将与实际需要绘制的像素数成正比画.

GPU-CPU（有硬件加速）方法计算所有的三角形，无论大小，然后将它们发送到GPU绘制大三角形，删除中间像素，绘制小三角形，删除不需要的像素，等等。由于绘图需要很长时间，那么 GPU 用于绘图和擦除的时间将占总耗时的大部分；由于大多数（渐近地，100%）绘制的像素最终将被擦除，因此所花费的总时间将大大超过实际必须绘制的像素数。

换句话说：hardware-acceleration 场景将大部分工作转储到 GPU 上，这比 CPU 慢得多。如果 CPU 在 GPU 进行处理时还有其他事情要做，这没关系；但是，这里不是这种情况；因此，CPU 只是在 GPU 进行绘图时浪费周期。

科赫雪花渲染时间（以及如何使用乌龟绘制雪花）

Koch snowflake rendering time (and how to draw a snowflake using turtle)

python

big-o

asymptotic-complexity