1. 主页
  2. 文档
  3. 从零开始的计算机图形_程序员的3D渲染介绍教程
  4. 从零开始的计算机图形_程序员的3D渲染介绍 填充三角形
  5. 绘制填充三角形

绘制填充三角形

我们想画一个三角形,用我们选择的颜色填充。就像计算机图形学中经常出现的情况一样,有不止一种方法来处理这个问题。我们在画填充三角形时,可以把它们看作是一组水平线段的集合,这些线段画在一起时看起来像一个三角形。图7-2显示了一个这样的三角形,如果我们能看到各个线段的话,会是什么样子。

图7-2:用水平线段画一个填充的三角形

以下是我们想做的非常粗略的第一种近似的做法。

for each horizontal line y between the triangle's top and bottom
compute x_left and x_right for this y
DrawLine(x_left, y, x_right, y) 

让我们从 “三角形的顶部和底部之间 “开始。一个三角形由其三个顶点P0、P1和P2定义。如果我们将这些点按y的增加值排序,使y0≤y1≤y2,那么三角形所占的y值范围是[y0,y2]。

if y1 < y0 { swap(P1, P0) }
if y2 < y0 { swap(P2, P0) }
if y2 < y1 { swap(P2, P1) }

这样对顶点进行排序使事情变得更容易:这样做之后,我们总是可以假设P0是三角形的最低点,P2是最高点,所以我们不必处理每一种可能的排序。

接下来我们必须计算x_left和x_right数组。这稍微有点麻烦,因为三角形有三条边,而不是两条。然而,只考虑y的值,我们总是有一条从P0到P2的 “高 “边,以及从P0到P1和P1到P2的两条 “短 “边。

有一种特殊情况,当y0=y1或y1=y2时,即当三角形的一条边是水平的。当这种情况发生时,另外两条边有相同的高度,所以任何一条都可以被认为是 “高 “边。我们应该选择右边还是左边?幸运的是,这并不重要;算法将支持从左到右和从右到左的水平线,所以我们可以坚持我们的定义,即 “高 “边是指从P0到P2的那一条。

x_right的值要么来自高边,要么来自连接短边;x_left的值将来自另一组。我们将从计算三条边的x值开始。由于我们要画水平线,我们希望每个y的值都有一个x的值;这意味着我们可以用Interpolate来计算这些值,以y为自变量,x为因变量。

x01 = Interpolate(y0, x0, y1, x1)
x12 = Interpolate(y1, x1, y2, x2)
x02 = Interpolate(y0, x0, y2, x2)

其中一条边的x值在x02中;另一条边的值来自x01和x12的连接。注意,在x01和x12中有一个重复的值:y1的x值既是x01的最后一个值,也是x12的第一个值。我们只需要去掉其中一个(我们任意选择x01的最后一个值),然后将数组连接起来。

remove_last(x01)
x012 = x01 + x12

我们最后有x02和x012,我们需要确定哪个是x_left,哪个是x_right。要做到这一点,我们可以选择任何一条水平线(例如中间那条),然后比较它在x02和x012中的x值:如果x02中的x值小于x012中的x值,那么我们知道x02一定是x_left;否则,它一定是x_right。

m = floor(x02.length / 2)
if x02[m] < x012[m] {
x_left = x02
x_right = x012
} else {
x_left = x012
x_right = x02
}

现在我们有了绘制水平线段所需的所有数据。我们可以使用DrawLine来做这件事。然而,DrawLine是一个非常通用的函数,在这种情况下,我们总是在绘制从左到右的水平线,所以使用一个简单的for循环会更有效率。这也让我们对所画的每个像素有了更多的 “控制”,这在后面的章节中会特别有用。

清单7-1有完成的DrawFilledTriangle。

DrawFilledTriangle (P0, P1, P2, color) {
❶ // Sort the points so that y0 <= y1 <= y2
if y1 < y0 { swap(P1, P0) }
if y2 < y0 { swap(P2, P0) }
if y2 < y1 { swap(P2, P1) }
❷ // Compute the x coordinates of the triangle edges
x01 = Interpolate(y0, x0, y1, x1)
x12 = Interpolate(y1, x1, y2, x2)
x02 = Interpolate(y0, x0, y2, x2)
❸ // Concatenate the short sides
remove_last(x01)
x012 = x01 + x12
❹ // Determine which is left and which is right
m = floor(x012.length / 2)
if x02[m] < x012[m] {
x_left = x02
x_right = x012
} else {
x_left = x012
x_right = x02
}
❺ // Draw the horizontal segments
for y = y0 to y2 {
for x = x_left[y - y0] to x_right[y - y0] {
canvas.PutPixel(x, y, color)
}
}
} 

清单7-1:一个绘制填充三角形的函数

让我们看看这里发生了什么。这个函数接收三角形的三个顶点作为参数,以任何顺序。我们的算法需要它们从下到上的顺序,所以我们以这种方式排序 ❶。接下来,我们计算三条边的每个y值的x值 ❷,并将两条 “短 “边的数组连接起来 ❸。然后我们找出哪个是x_left,哪个是x_right ❹。最后,对于三角形顶部和底部之间的每个水平段,我们得到它的左和右的x坐标,并逐个像素地画出这个段❺。

图7-3显示了结果;为了验证,我们先调用DrawFilledTriangle,然后再调用DrawWireframeTriangle,坐标相同但颜色不同。尽可能地验证你的结果–这是一个非常有效的发现代码中的错误的方法

图7-3:填充三角形,用线框边缘进行验证

您可以在https://gabrielgambetta.com/cgfs/triangle-demo上找到该算法的现场实现。

你可能会注意到三角形的黑色轮廓与绿色内部区域并不完全匹配;这在三角形的右下边缘尤为明显。这是因为DrawLine计算的是这条边的y = f(x),而DrawTriangle计算的是x = f(y),由于四舍五入的关系,结果可能会略有不同。这是一种近似误差,我们愿意接受,以使我们的渲染算法快速。

这篇文章对您有用吗?