c++ - 关于光栅化: Stochastic Sampling, Pineda边函数和定点数的问题

Question

我正在尝试研究/理解光栅化算法并且已经发布了一些与此相关的帖子但不幸的是没有得到很多答案:

Rasterisation Algorithm: finding the "ST" coordinates of point in 2D quad and Inverse Projection

在第一个问题中，我想光栅化一个四边形，但现在我将自己限制在一个三角形上，无论如何这是标准渲染基元。

所以我的问题是要准确知道使用哪种技术来查找给定像素是否在三角形中。我一直在使用边缘函数方法，这没问题。假设我需要遍历 2D Triange 周围的 bbox 的所有像素。

float dX0 = (v1.x - v0.x);
float dY0 = (v1.y - v0.y);
float dX1 = (v2.x - v1.x);
float dY1 = (v2.y - v1.y);
float dX2 = (v0.x - v2.x);
float dY2 = (v0.y - v2.y);
for (int y = ymin; y <= ymax; ++y) {
    for (int x = xmin; x <= xmax; ++x) {
        float xctr = x + 0.5;
        float yctr = y + 0.5;
        float s0 = (xctr - v0.x) * dX0 - (yctr - v0.y) * dY0;
        float s1 = (xctr - v1.x) * dX1 - (yctr - v1.y) * dY1;
        float s2 = (xctr - v2.x) * dX2 - (yctr - v2.y) * dY2;

        if (s0 >= 0 && s1 >= 0 && s2 >= 0) {
             // point is in triangle
        }
    }
}

我也尝试过重心方法。为三角形中的点计算 s 和 t，如果 (s + t) <= 1 那么我知道该点在三角形中。

因此我有几个问题:

1) 在论文中 Pineda [88]虽然据说如果你沿着 x 或 y 移动，你可以简单地通过简单的加法更新边缘函数的结果。我引用:

The edge functions may then be computed incrementally for a unit step in the X or Y direction:
Ei(x+l,y)=Ei(x,y)+dYi,
Ei(x-1,y)=Ei(x,y)-dYi,
Ei(x,y+l)=Ei(x,y)-dXi,
Ei(x,y-l)=Ei(x,y)+dXi.

所以没关系，我明白为什么会这样，但在一般情况下，我们进行 super 采样甚至随机采样(将像素分成抖动的 4x4 样本)这种方法仍然有用吗？

2) 我仍然不知道如何使用边缘函数通过插值计算 s/t/z？有人可以帮我解决这个问题，或者告诉我一些对此进行解释的页面吗？

3) 现在我正在研究其他光栅化三角形的方法，例如 Bresenham 算法，但似乎到处都说它只适用于固定点坐标？我很困惑。投影后三角形顶点为 float 。如何从浮点坐标转到定点坐标？

Answer 1

栅格化

首先，典型的光栅化算法不会像您尝试的那样遍历投影三角形的整个边界框，因为那样太慢了。想法是:

• 将顶点投影到图像空间，
• 水平或垂直排列 2D 顶点(最好使用较小边界框维度的方向)
• 将三角形一分为二:
  • 从第一个顶点到垂直或水平通过第二个顶点，
  • 从垂直/水平通过第二个顶点到第三个顶点，
• 光栅化每一半

你会得到这样的东西:

           * v2
          /|\
         / | \
        /  |  \
       / T1|T2 \
   v1 *----+----* v3

现在，对于光栅化三角形 T1，您可以让 X 从 v1.x 迭代到 v2.x，并使用边的斜率来计算 Y 应该迭代 X 处的三角形切片的范围。

此 Y 范围的边界对于每个垂直切片都有恒定的增量，因此您可以将这些增量表示为小数(定点或 float )或使用 Bresenham 算法。

三角形T2的想法是一样的。

多重采样

当对抖动样本进行多重采样时，您将决定每个单独的样本是否位于三角形内，基本上按照您的尝试进行，但是这仅对三角形边缘的像素是必需的。 p>

然而，纹理查找只需要为每个像素发生一次(覆盖多个样本)。

如果您想计算每个样本的深度，则每个像素的深度增量基本上必须乘以样本相对于像素质心的小数抖动。

内插纹理坐标

现在如果我们考虑光栅化算法，可以认为 X 或 Y 中的每个增量都转化为 S、T 和 Z 中的增量。这基本上可以正常工作，但会导致失真，因为 S、T、Z 的线性插值不考虑深度划分。

与其尝试将图像空间坐标转换回 3D 场景坐标，不如从简单计算的坐标计算校正后的 S、T、Z 是可能的(而且成本更低)。

您可以查看此 PDF 以找到校正因子的公式: http://web.cs.ucdavis.edu/~amenta/s12/perspectiveCorrect.pdf