光栅化渲染器(三)光栅化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三角形。