如何正确地在软件中进行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

另一种方法是Warnock 算法。它使用递归，这使得它很难在 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
    }
  }
}

该画家算法是你们用自己的多维数据集做了什么，唯一的区别是，它排序的多边形，而不是整个对象。即便如此，解决各种多边形交叉点也很困难，我个人不会将它用于非平凡的场景。

您可能会使用的另一种算法是背面剔除算法。这仅适用于不重叠的凸对象。该算法计算每个多边形的法线，如果它指向相机的方向，则将其删除。

光线投射是另一种确定每像素可见性的方法。但是，它非常占用 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;
      }
    }
  }
}