實現畫家算法時，排列多邊形的正確方法是什麼？

我正在寫一個HTML5畫布，所以使用z緩衝區看起來非常昂貴。例如，如果它是一個500x500的畫布，並且不得不循環10個多邊形，那麼在CPU中完成每幀2,500,000次迭代。我不知道這是一個很大的數字，但它似乎是錯誤的方式來做這個應用程序。

畫家算法似乎更合適。基本步驟是：

1. Sort polygons based on their "z". 
2. Paint all polygons, but paint the ones farthest away first.

但我很困惑如何找到他們的z。假設我們從下列多邊形中俯瞰：

如果我只是找到最大z（離屏幕最遠），紅色將被視爲更遠。所以它會先塗成紅色，然後用橙色塗上紅色，即使紅色在橙色前面。

排序這些多邊形的正確方法是什麼？或者更一般地說，當實現畫家算法時，您如何確定多邊形的順序？

編輯：this就是爲什麼我怕我自己的滾動Z緩存的（經過的每個像素，並隨機分配它在這五年的老酷睿i7顏色〜10FPS）。

的複雜性是相同的。您可以對10個（修剪過的）三角形進行排序，並使用2.5M 2D像素操作盲目地繪製它們，或者使用z緩衝區爲每個像素只添加一個z操作。只有在CG算法確定某些三角形完全被其他三角形遮擋的情況下才會帶來好處。 –

三個三角形可以循環地相互覆蓋，這意味着不存在通用的排序算法。相反，通常通過沿重疊邊緣切割重疊的三角形形成新的三角形/多邊形來解決問題，該三角形/多邊形完全位於彼此的任一側。

所討論的兩個多邊形可以通過頂點與另一個多邊形的平面方程的有符號距離進行OTOH排序。

2017-07-21 18:37:31

所有的多邊形都放在一個大的列表中，然後運行排序算法，或者您應該嘗試根據它們是否在x和y中重疊來對多邊形進行分組？ – user1873073

通過邊界框（對齊xyz或非對齊）或球體進行分組通常用於加快排序。 –

Z排序通常比較慢然後Z緩衝。你有更好的多邊形是使用Z緩衝區。你對迭代的假設是錯誤的。 Z緩衝不是基於每個多邊形進行迭代，而是基於每個像素進行迭代。

所以無論你得到多少多邊形。重要的是以像素呈現的區域（重疊區域每個多邊形佔據多次一次）。所以你不能指望500x500屏幕和10多邊形將得到10*500*500迭代。

我不HTML5畫布代碼，但除非你有直接像素訪問和影后緩衝器和柵格化的多邊形你自己（或有接取它像GLSL片段着色器），你會得到時間難以實現z緩衝即使它只是單個簡單的條件。我認爲它可以用模板或alpha蒙版來完成，但從來沒有這樣做過。

Z分級通常用在這些情況下：

但隨着對方的回答涵蓋了它，如果你的多邊形的距離相交的相機，你需要將它們切割成多。這種操作通常非常昂貴，以至於消耗的時間會抵消z-sorting的任何益處。這就是爲什麼即使是＃3是使用Z緩衝和排序是由面部剔除像這樣僞造：

或者光線追蹤的使用形式：

在某些情況下，組合使用Z排序（排序網格渲染順序）和Z緩衝（每個多邊形順序）。這裏的一個示例：

2017-07-22 06:11:33 Spektre

回答