如何在軟件中正確執行z順序

Question

我在2D畫布上渲染3D對象，方法是在軟件中進行所有必要的計算。我沒有使用圖形加速。

最初所有的對象都是相同大小的立方體，所以我可以根據它們在距離攝像機Z中的距離對它們進行排序，並且可以正確地對它們進行排序。但是現在我試圖畫出不同尺寸的立方體。這使得我的簡單Z排序算法在透視投影中失敗。

我看了一下計算機圖形學書籍，發現了使用的技術，他們最終推薦使用基於像素的兩個多邊形比較來確定哪一個超前於其他。這可能就是他們在顯卡上所做的。但是在軟件中這樣做似乎過於困難，而且即使我可以做到這一點，我估計它在實際應用中也會很慢。

有沒有一個簡單的竅門在軟件中做到這一點？ 3D圖形早期的任何示例，當圖形卡不可用時？

雖然這是通用的3D圖形問題，但如果它有幫助，我可以在HTML5 Canvas 2D API上執行此操作。

Answer 1

由於@ybungalobill已經提到，z-buffer是最容易實現的算法。填充組成立方體的三角形/多邊形時，插入它們之間的Z座標並將其存儲爲每像素。如果稍後填充另一個在同一X，Y座標上呈現的多邊形，請檢查其Z是否小於已存儲在緩衝區中的Z.重繪之前不要忘記將Z緩衝區清除爲無窮大。僞代碼：

foreach (scanline in polygon) { 
    int length = scanline.right.x - scanline.left.x; 
    foreach (pixel in scanline) { 
    float t = (float)pixel.x/length; 
    float z = (1 - t) * scanline.left.z + t * scanline.right.z; // Interpolate the Z coordinate 
    if (z < zbuffer[scanline.y][pixel.x]) 
     drawPixel(pixel.x, scanline.y, polygon.color); // The pixel is closer, paint it 
    } 
} 

，通過不拉絲，將被覆蓋的像素上執行CPU更好的Z緩存的修訂方法被稱爲段緩衝：http://www.gamedev.net/reference/articles/article668.asp

另一種方法是沃諾克的算法。它使用遞歸，這使得很難在GPU上使用，但如果使用自己的堆棧來避免堆棧溢出，CPU應該會很好。這個想法在於將場景劃分爲4部分並檢查是否只有一個覆蓋整個部分的多邊形。如果不再分割，直到滿足條件（在最壞的情況下它將在像素級別被滿足）。僞代碼：

void warnock(Rectangle rect) 
{ 
    float minZ = infinity; 
    foreach (polygon in polygons) { 
    if (rect is inside polygon) { 
     float z = interpolateZ(polygon, rect.x + rect.width/2, rect.y + rect.height/2); // Get Z coordinate at the centre of the rectangle 
     if (z < minZ) { // If there are more polygons in this rectangle, make sure the topmost one gets drawn last 
     fillRect(polygon.color); 
     minZ = z; 
     } 
    } else { 
     // Divide to 4 subrectangles 
     warnock(Rectangle(rect.x, rect.y, rect.width/2, rect.height/2)); // Top left 
     warnock(Rectangle(rect.x, rect.y + rect.height/2, rect.width/2, rect.height/2)); // Bottom left 
     warnock(Rectangle(rect.x + rect.width/2, rect.y, rect.width/2, rect.height/2)); // Bottom right 
     warnock(Rectangle(rect.x + rect.width/2, rect.y + rect.height/2, rect.width/2, rect.height/2)); // Top right 
    } 
    } 
} 

的畫家算法是您與您的多維數據集做了什麼，唯一的區別是，它排序的多邊形，而不是整個對象。即使這樣，很難解決各種多邊形交集，我個人不會將它用於非平凡的場景。

您可能使用的另一種算法是背面剔除算法。這僅適用於不重疊的凸對象。該算法計算每個多邊形的法線，並且如果它指向相機的方向，則會將其移除。

Raycasting是另一種確定每像素可見性的方法。但是，它的CPU密集程度相當高。基本思想是檢查屏幕的每個像素，哪個多邊形與它相交（哪個多邊形被當前像素投射的光線擊中）。光線的起源是眼睛的位置。僞代碼：

foreach (pixel in screen) { 
    float minZ = infinity; // Can be zfar from the perspective projection 
    Color pixelColor = backgroundColor; 
    foreach (polygon in projectedPolygons) { 
    if (polygon contains Point(pixel.x, pixel.y)) { 
     float z = interpolateZ(polygon, pixel.x, pixel.y); // Get the current Z for (x, y) and this polygon using bilinear interpolation 
     if (z < minZ) { 
     minZ = z; 
     pixelColor = polygon.color; 
     } 
    } 
    } 
} 

Answer 2

對，今天你在GPU上使用Z緩衝來進行每像素深度比較。你也可以用軟件來做到這一點。

排序技術通常不起作用，請參見wikipedia。儘管將立方體分解成單獨的面並將它們排序而不是立方體，但可以改進它。

在很多早期遊戲（例如Doom）中使用的更一般的技術是BSP trees。他們不會使用動態場景，因爲創建它們非常昂貴。但是他們總體上解決了排序問題。

Answer 3

我發現的適合我的是與Warnock結合的固定網格。分區屏幕包含在視錐模型（一個或多個）的區域爲單元：

爲此，您可以只使用你插入原語的邊框。這個結構可以非常快速地更新，因爲你所要做的就是操縱整數從一個單元格移動到另一個單元格。爲了避免不斷地分配和重新分配數據，使用一個免費的列表方法：

現在呈現每個網格單元，如果它是「足夠簡單」（沃爾諾克標準）。如果不是，則應用Warnock。

如果單元格的矩形完全包含在您爲該單元格渲染的三角形內，則網格單元格「足夠簡單」，例如，並且給定三角形內矩形的所有4個交點都在其他所有矩形的前面（具有最小深度值）...或者如果單元格是空的或者只有一個基元。

也就是說，我並沒有真正做到實時顯示的目的。在複雜的網格上實時執行此操作可能相當困難。

我主要是做一些事情，如選取框和套索，在非常密集的網格上選擇三維軟件中的頂點/邊/多邊形，我們不想錯過未固定的基元，通過近似固定的像素分辨率。在這種情況下，用戶可以放大遠離網格，我們不希望我們的套索和選取框選擇錯過一大堆亞像素基元，因此在這裏使用與分辨率無關的Warnock的吸引力是可以遞歸地直到你得到足夠簡單的結果，這個結果可以是一個比像素小得多的矩形。對於具有合理高效的子採樣的抗鋸齒也可能是有用的（因爲如果像素具有全覆蓋範圍，則不會進行子採樣，例如）。我從來沒有真正將它用於光柵化上下文。

光線追蹤也很有趣，因爲它可以打開間接照明，焦散，自由度等所有選項，儘管它的計算量非常大，正如Karel指出的那樣。也就是說，我發現如果我只是做大部分的直接照明，我可以用一個好的BVH發現，如今我可以在相當高的水平上進行實時光線追蹤。

這裏有一個小例子，我在幾年前掀起的CPU上實時追蹤了一百萬個三角形網格。這是我的i3和1600x1200像素。只花了一天時間來編碼。該GIF真的降級的質量和幀速率（原是超過〜120 FPS），但希望你的想法：

主要缺點我與CPU的實時光線跟蹤（以及GPU）是實際上不是光柵化部分。雖然我可以用i3很容易地實時渲染基礎材料和照明（這甚至不是優化的代碼，只是C中的一些基本的SIMD和並行循環），但如果每百萬個三角形網格每變形一次，將會困難得多幀。然後，我必須能夠以超過100 FPS的速度更新存儲超過一百萬個三角形的BVH，我不知道如何做得足夠快。

也就是說，這裏有一個軟件實際上是實時光柵化數百萬個多邊形值的變形數據。它被稱爲ZBrush：

我不知道他們如何管理它。他們可能會使用LOD或者在用戶使用畫筆或其他東西使其變形的同時超快速地對網格進行體素化。對我來說，它並不重要，因爲它們可以讓您控制每個頂點級別，每個多邊形級別的事物，讓您看到線框，並讓您在加載和保存時輸入和輸出多邊形網格物體。無論哪種方式，它都具有處理數百萬個多邊形值的數據的效果（它甚至可以在17年前柵格化和變形網格，覆蓋超過2000萬個多邊形，這是無與倫比的; 17年後，人們甚至無法匹配），並允許用戶以某種方式雕刻結果並在每個頂點級別控制事物，同時保持交互式幀速率，而無需使用GPU進行光柵化。據我所知，他們得到了某種巫術編程，儘管我可能會用手指來了解它們是如何做到的。