Koch雪花渲染時間（以及如何使用龜繪製雪花）

我目前正在通過MIT 6.006課程的在線課程材料獲得樂趣。我在問題集＃2（找到了here），並對koch雪花問題（問題＃1）漸近渲染時間的計算有疑問。Koch雪花渲染時間（以及如何使用龜繪製雪花）

根據這些解決方案，當CPU負責渲染和座標計算時，漸進渲染時間比CPU和GPU之間的分離過程更快。數學對我來說是有道理的，但是有沒有人對此有直覺？

在我看來，CPU仍然需要計算渲染雪花（Theta（4^n）時間）的座標，然後必須渲染圖像。在我看來，這些應該是加法的，而不是乘法的。因爲每個三角形/線段較短（對於問題1中的最後兩個子問題），所以運行時間減少爲Theta（（4/3）^ n）或Theta （1）！

我不是計算機科學家 - 這個東西對我來說只是一個有趣的愛好。我真的很感謝你的一個回答你的天才之一:)

另外，我玩了一些python烏龜模塊的樂趣。下面有一些非常不完美的代碼來繪製一個Koch雪花在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)

來源

2015-12-30 lstbl

我把你的代碼和相當多的修改與我的一些補充，我可以發佈CodeReview問題與我的版本？（我會給你歸屬） – Caridorc

當然可以！我不在乎 – lstbl

你可以看到我的這段代碼的版本（起初是基於你的） - > http://codereview.stackexchange.com/questions/115453/koch-snowflake-in-python-with-turtle it結果需要相當多的代碼來製作動畫，就像我想要的那樣。 – Caridorc

正如對問題集的小五的評論指出，由CPU和GPU所採用的方法是不同的。

僅限CPU（無硬件加速）appproach首先計算需要繪製的內容，然後將其發送到GPU進行繪製。由於我們假定光柵化的成本大於收集線段的成本，因此繪製圖像的時間將由GPU控制，其成本將與其實際需要的像素數成比例畫。

GPU-CPU（帶硬件加速）方法計算所有三角形，大小，然後將它們發送到GPU繪製大三角形，刪除中間像素，繪製較小的三角形，刪除不需要的像素，等等。由於繪圖需要很長時間，因此GPU必須花費繪圖和擦除的時間將佔用花費的總時間;因爲大多數（漸近地，100％）被繪製的像素將最終被擦除，所花費的總時間將遠遠大於實際上必須繪製的像素的數量。換句話說，硬件加速場景將大部分工作轉移到GPU上，這比CPU要慢得多。如果CPU在GPU正在處理時還有其他事情需要處理，這是可以的;然而，這裏並不是這樣;所以，CPU正在浪費週期，而GPU正在進行繪製。

來源

2015-12-30 19:50:42 Alex

這對我來說現在是有意義的：問題表明，當CPU向GPU發送信息時，每個三角形的渲染時間是等效的。但是，當CPU自行處理計算時，渲染時間與三角形的大小成比例地減小。因此，整個計算在時間上大量減少，因爲它將常數因子改變爲指數減少的因子。非常感謝Alex！ – lstbl

Koch雪花渲染時間（以及如何使用龜繪製雪花）

回答

相關問題