关于光栅化的问题：随机采样、Pineda 边函数和不动点数
Questions about Rasterization: Stochastic Sampling, Pineda Edge Function and Fixed Point Numbers
我正在尝试 study/understand 光栅化算法，并且已经发布了一些与此相关的帖子，不幸的是没有得到很多答案：
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.
所以没关系，我明白为什么会这样，但是在一般情况下，我们进行超级采样甚至随机采样（将像素分成抖动的 4x4 样本）这种方法仍然有用吗？
2) 我还是不知道边缘函数如何通过插值计算s/t/z？有人可以帮我解决这个问题，或者告诉我一些对此进行解释的页面吗？
3) 现在正在研究其他的三角形光栅化方法，比如Bresenham算法，但是好像到处都在说它只适用于定点坐标？我很困惑。投影后三角形顶点为浮点数。你怎么能从浮点坐标到定点坐标？
光栅化
首先，典型的光栅化算法不会像您尝试的那样遍历投影三角形的整个边界框，因为那样太慢了。
想法是：
- 将顶点投影到图像 space、
- 水平或垂直排列 2D 顶点（最好使用较小边界框维度的方向）
- 将三角形一分为二：
- 从第一个顶点到垂直或水平通过第二个顶点，
- 从vertical/horizontal经过第二个顶点到第三个顶点，
- 光栅化每一半
你会得到这样的东西：
* v2
/|\
/ | \
/ | \
/ T1|T2 \
v1 *----+----* v3
现在，为了栅格化三角形 T1，您可以让 X 从 v1.x 迭代到 v2.x 并使用边的斜率来计算 Y 应该在 X 处迭代三角形切片的范围.
此 Y 范围的边界对于每个垂直切片都有恒定的增量，因此您可以将这些增量表示为小数（定点或浮点数）或使用 Bresenham 算法。
三角形T2的想法是一样的。
多重采样
当对抖动样本进行多重采样时，您将决定每个单独的样本是否位于三角形内，基本上按照您的尝试进行，但是 这仅对边缘像素是必需的三角形。
然而，纹理查找只需要为每个像素发生一次（覆盖多个样本）。
如果你想计算每个样本的深度，每个像素的深度增量基本上必须乘以样本相对于像素质心的分数抖动。
内插纹理坐标
现在如果我们考虑光栅化算法，可以认为 X 或 Y 中的每个增量都转化为 S、T 和 Z 中的增量。这基本上工作正常但会导致失真，因为 S、T 的线性插值, Z不考虑深度划分。
与其尝试将图像-space 坐标转换回 3D 场景坐标，不如从简单计算的坐标计算校正后的 S、T、Z 是可能的（而且成本更低）。
您可以查看此 PDF 以找到校正因子的公式：
http://web.cs.ucdavis.edu/~amenta/s12/perspectiveCorrect.pdf
我正在尝试 study/understand 光栅化算法，并且已经发布了一些与此相关的帖子，不幸的是没有得到很多答案：
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.
所以没关系，我明白为什么会这样，但是在一般情况下，我们进行超级采样甚至随机采样（将像素分成抖动的 4x4 样本）这种方法仍然有用吗？
2) 我还是不知道边缘函数如何通过插值计算s/t/z？有人可以帮我解决这个问题，或者告诉我一些对此进行解释的页面吗？
3) 现在正在研究其他的三角形光栅化方法，比如Bresenham算法，但是好像到处都在说它只适用于定点坐标？我很困惑。投影后三角形顶点为浮点数。你怎么能从浮点坐标到定点坐标？
光栅化
首先，典型的光栅化算法不会像您尝试的那样遍历投影三角形的整个边界框，因为那样太慢了。 想法是：
- 将顶点投影到图像 space、
- 水平或垂直排列 2D 顶点（最好使用较小边界框维度的方向）
- 将三角形一分为二：
- 从第一个顶点到垂直或水平通过第二个顶点，
- 从vertical/horizontal经过第二个顶点到第三个顶点，
- 光栅化每一半
你会得到这样的东西：
* v2
/|\
/ | \
/ | \
/ T1|T2 \
v1 *----+----* v3
现在，为了栅格化三角形 T1，您可以让 X 从 v1.x 迭代到 v2.x 并使用边的斜率来计算 Y 应该在 X 处迭代三角形切片的范围.
此 Y 范围的边界对于每个垂直切片都有恒定的增量，因此您可以将这些增量表示为小数（定点或浮点数）或使用 Bresenham 算法。
三角形T2的想法是一样的。
多重采样
当对抖动样本进行多重采样时，您将决定每个单独的样本是否位于三角形内，基本上按照您的尝试进行，但是 这仅对边缘像素是必需的三角形。
然而，纹理查找只需要为每个像素发生一次（覆盖多个样本）。
如果你想计算每个样本的深度，每个像素的深度增量基本上必须乘以样本相对于像素质心的分数抖动。
内插纹理坐标
现在如果我们考虑光栅化算法，可以认为 X 或 Y 中的每个增量都转化为 S、T 和 Z 中的增量。这基本上工作正常但会导致失真，因为 S、T 的线性插值, Z不考虑深度划分。
与其尝试将图像-space 坐标转换回 3D 场景坐标，不如从简单计算的坐标计算校正后的 S、T、Z 是可能的（而且成本更低）。
您可以查看此 PDF 以找到校正因子的公式： http://web.cs.ucdavis.edu/~amenta/s12/perspectiveCorrect.pdf