光栅化渲染器（三）光栅化2D三角形
发表于2018-07-04
这篇主要讲扫描转换方法光栅化2d三角形。之前我们已经完成了线段的绘制，而三角形其实3条线段的首尾相连，所以我们只要给出三个不在同一直线的顶点就能绘制三角形。
一、完善画线算法
Bresenham算法是种相对高效的算法，但目前我项目中的这一算法在顶点x坐标或y坐标相同时还无法完成绘制。所以这一情况下，我选择DDA算法取代。
如下
void DrawLine(point_t v1, point_t v2, color_t c) ｛ if (v1.x == v2.x || v1.y == v2.y) ｛ DrawLineDDA2d(v1, v2, c); ｝ else ｛ DrawLineBre(v1, v2, c); ｝ ｝
这样一来就完成了相对高效且完全通用的画线算法
二、用画线算法绘制三角形
算法很简单，就是绘制三条首尾相连的三角形
void DrawTriangle(point_t v1, point_t v2, point_t v3,color_t c) ｛ if (v1.x == v2.x&&v1.x == v3.x) return; if (v1.y == v2.y&&v1.y == v3.y) return; DrawLine(v1, v2,c); DrawLine(v2, v3,c); DrawLine(v3, v1,c); ｝
接下来在重绘函数里测试代码
// 重绘函数 void myDisplay(void) ｛ glClear(GL_COLOR_BUFFER_BIT); // 清屏幕 glBegin(GL_POINTS); point_t v1｛ 10,15 ｝; point_t v2｛ 400,405 ｝; point_t v3｛ 100,405 ｝; color_t c｛ 1.0,1.0,0,1.0 ｝;//黄色 DrawTriangle(v1, v2, v3, c); glEnd(); glFlush(); // 将所有输出到显示屏上 ｝
奇怪这个三角形怎么只有线段，好吧，我们需要填充三角形
三、扫描转换算法
int Sgn(float d)//符号判断 ｛ if (d<0) return -1; else if (d == 0) return 0; else return 1; ｝ // 计算插值：t 为 [0, 1] 之间的数值 float interp(float x1, float x2, float t) ｛ return x1 + (x2 - x1) * t; ｝
我们需要用一个个线段填充三角形的内部
这是一个平底三角形，我们可以通过从最上方顶点开始从上而下绘制线段
//扫描转换填充三角形 void DrawTriangle_ScanConversion(point_t v1, point_t v2, point_t v3, color_t c) ｛ float dy =abs(v2.y-v1.y); int x = v1.x; int y = v1.y; int x2 = v2.x; int y2 = v2.y; int x3 = v3.x; int y3 = v3.y; int s = Sgn(y - y3); point_t newV1=v1; point_t newV2=v1; for (int i = 1; i<dy; i++) ｛ float f = i / dy; newV1.x = interp(x, x2, f)+0.5; newV1.y -= s; newV2.x = interp(x, x3, f)+0.5; newV2.y -= s; DrawLine(newV1, newV2, c); ｝ ｝
四、填充三角形
之前的算法只适合平底三角形，接下来我们把之前算法拓展到任何一种三角形。
我们可以发现任何一个三角形都是由2个平底三角形组成，只要让他的顶点根据y坐标排序，挑选出y坐标大小排序在中间的点，做平行x轴的直线，就可以将任何一个非平底或平顶三角形分割成2个平底或平顶三角形。
算法实现如下：
void DrawTriangle(point_t v1, point_t v2, point_t v3,color_t c) ｛ if (v1.x == v2.x&&v1.x == v3.x) return; if (v1.y == v2.y&&v1.y == v3.y) return; //DrawLine(v1, v2,c); //DrawLine(v2, v3,c); //DrawLine(v3, v1,c); vector<float> PointY｛ v1.y,v2.y,v3.y ｝; sort(PointY.begin(), PointY.end()); float midY = PointY[1]; float minY = PointY[0]; float maxY = PointY[2]; point_t MaxYPoint; point_t MidYPoint; point_t MinYPoint; if (midY != minY && midY != maxY) ｛ if (midY == v1.y) ｛ MidYPoint = v1; if (maxY == v2.y) ｛ MaxYPoint = v2; MinYPoint = v3; ｝ if (maxY == v3.y) ｛ MaxYPoint = v3; MinYPoint = v2; ｝ ｝ else if (midY == v2.y) ｛ MidYPoint = v2; if (maxY == v1.y) ｛ MaxYPoint = v1; MinYPoint = v3; ｝ if (maxY == v3.y) ｛ MaxYPoint = v3; MinYPoint = v1; ｝ ｝ else if (midY == v3.y) ｛ MidYPoint = v3; if (maxY == v1.y) ｛ MaxYPoint = v1; MinYPoint = v2; ｝ if (maxY == v2.y) ｛ MaxYPoint = v2; MinYPoint = v1; ｝ ｝ point_t newV; float t = (midY - maxY) / (minY - maxY); newV.x = interp(MaxYPoint.x, MinYPoint.x, t); newV.y = midY; DrawTriangle_ScanConversion(MaxYPoint, MidYPoint, newV, c); DrawTriangle_ScanConversion(MinYPoint, MidYPoint, newV, c); ｝ else ｛ if(v1.y==v2.y) DrawTriangle_ScanConversion(v3, v1,v2, c); if (v1.y == v3.y) DrawTriangle_ScanConversion(v2, v1, v3, c); if (v3.y == v2.y) DrawTriangle_ScanConversion(v1, v3, v2, c); ｝ ｝
我写的顶点排序算法有些复杂，我又心急接下来光栅渲染器的实现，就先不在这里纠结了，如果大家有更好的算法，希望告知
最终完成了，一个简陋，实现算法糟糕的2d三角形。