光栅化渲染器(三)光栅化2D三角形

发表于2018-07-04
评论0 3.8k浏览
这篇主要讲扫描转换方法光栅化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三角形。

如社区发表内容存在侵权行为,您可以点击这里查看侵权投诉指引