如何在软件中正确执行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进行光栅化。据我所知，他们得到了某种巫术编程，尽管我可能会用手指来了解它们是如何做到的。