我是靠谱客的博主 可靠世界,最近开发中收集的这篇文章主要介绍用C++编写一个简单的光栅化渲染器:2D篇,觉得挺不错的,现在分享给大家,希望可以做个参考。

概述

本篇文章将会介绍2D的几何图元光栅化算法,此外还会涉及几何裁剪算法。

1.2D坐标系

本文在光栅化过程中所采用的2D坐标系(Screen space)如下:

红色框为Viewport,Viewport左上角为坐标系原点,y轴向下

此2D坐标系以Viewport左上角为原点,处于Viewport中的点的坐标范围为:

2.画点

绘制2D点直接将点的颜色设置到对应坐标即可:

void DrawPoint(const Vec2<float> &v, const Vec4<float> &color, Image<Vec4<uint8_t>> &image)
{
	image.SetPixel(Vec4<uint8_t>(color.r, color.g, color.b, 1), round(v.x), round(v.y));
}

2D图像由离散的像素点组成,所以设置像素时要将点坐标四舍五入为最近整数值。

2.线段光栅化

这里只介绍一下DDA算法,相似的画线算法还有Bresenham算法。

已知线段两端点坐标v0(x0, y0),v1(x1, y1)的情况下,直线可以表示为:

x坐标每增加1则y坐标增量为:

同理,y坐标每增加1则x坐标增量为:

DDA算法的思路为,首先判断组成线段的像素在那个坐标轴方向上更为密集,若dx>dy则像素在y轴方向上更为密集,此时选择x轴作为步进方向,从端点(x0, y0)开始每次沿x轴步进1,则y轴递增dy/dx,可以得出对应点的坐标为 (n为步进次数),然后设置对应点的像素属性即可。若dy>dx,则选择y轴作为步进方向,从端点(x0, y0)开始每次沿y轴步进1,则x轴递增dy/dx,对应点坐标为

DDA算法实现如下:

void DDALine(const Vec2I &v0, const Vec2I &v1, const Vec4<float> &color0, const Vec4<float> &color1, Image<Vec4<uint8_t>> &image)
{
	float dx = v1.x - v0.x;
	float dy = v1.y - v0.y;

	//选择步进方向
	int step;
	if (abs(dx) > abs(dy))
	{
		step = abs(dx);
	}
	else
	{
		step = abs(dy);
	}

	dx /= step;
	dy /= step;

	float x = v0.x;
	float y = v0.y;

	float length = (Vec2f(v1.x, v1.y) - Vec2f(v0.x, v0.y)).length();

	Vec4<float> curr_color(color0.r, color0.g, color0.b, color0.a);

	for (int i = 0; i <= step; i++)
	{
		image.SetPixel(Vec4<uint8_t>(curr_color.r, curr_color.g, curr_color.b, 1), round(x), round(y));
		x += dx;
		y += dy;

		//属性插值
		Vec2f diff_vector = Vec2f(x,y) - Vec2f(v0.x, v0.y);
		float t = diff_vector.length() / length;
		curr_color = color0 * (1 - t) + color1 * t;
	}
}

已知线段两端点v0和v1以及线段上一点p:

可以通过点p的重心坐标(Barycentric Coordinates)对其属性进行插值。位于线段v0v1上的点p可由重心坐标表示为:

3.三角形光栅化

Ⅰ. Scan-Line光栅化算法

Scan-Line算法的核心思想和DDA算法相似。

已知三角形三个顶点v0,v1,v2的坐标,可以求得边v0v1和边v0v2的斜率分别为k0和,k1,从三角形顶点v0开始沿着y轴方向步进,通过两条边的斜率和v0点的坐标可以得到p0和p1的坐标为

,得到P0,P1的坐标后可以直接通过之前介绍的DDA算法填充P0与P1构成的线段。

当P0移动到V2时,三角形边的斜率会发生改变,为了方便绘制,可以将三角形拆分为平顶三角形和平底三角形,如下图所示:

将三角形拆分为平顶三角形和平底三角形

平顶三角形可以从y坐标最小的顶点开始朝下绘制,平顶三角形可以从y坐标最大的点开始朝上绘制。点v3的y坐标与v2相同,且处在线段v0v1上,可以求得v3的坐标为 :, 求出点v3的坐标即可对三角形进行拆分。

Scan-Line算法实现如下:

void Sort(Vec2I &v0, Vec2I &v1, Vec2I &v2)
{
	if (v1.y > v0.y)
	{
		Swap(v0, v1);
	}

	if (v2.y > v0.y)
	{
		Swap(v0, v2);
	}

	if (v2.y > v1.y)
	{
		Swap(v1, v2);
	}
}

//绘制平顶三角形
void DrawTopFlatTriangle(const Vec2I &v0, const Vec2I &v1, const Vec2I &v2, const Vec4<uint8_t> &color, Image<Vec4<uint8_t>> &image)
{
	int ybegin = v2.y;
	int yend = v1.y;

	float x0 = v2.x;
	float x1 = v2.x;

	float slopeInv0 = (v0.x - v2.x) / static_cast<float>(v0.y - v2.y);
	float slopeInv1 = (v1.x - v2.x) / static_cast<float>(v1.y - v2.y);

	for (int y = ybegin; y <= yend; y++)
	{
		DDALineBase(Vec2I(x0, y), Vec2I(x1, y), color, image);
		x0 += slopeInv0;
		x1 += slopeInv1;
	}
}

//绘制平底三角形
void DrawBottomFlatTriangle(const Vec2I &v0, const Vec2I &v1, const Vec2I &v2, const Vec4<uint8_t> &color, Image<Vec4<uint8_t>> &image)
{
	int ybegin = v0.y;
	int yend = v1.y;

	float x0 = v0.x;
	float x1 = v0.x;

	float slopeInv0 = (v0.x - v1.x) / static_cast<float>(v0.y - v1.y);
	float slopeInv1 = (v0.x - v2.x) / static_cast<float>(v0.y - v2.y);

	for (int y = ybegin; y > yend; y--)
	{
		DDALineBase(Vec2I(x0, y), Vec2I(x1, y), color, image);
		x0 -= slopeInv0;
		x1 -= slopeInv1;
	}
}

void ScanlineTriangle(const Vec2I &v0, const Vec2I &v1, const Vec2I &v2,const Vec4<uint8_t> &color, Image<Vec4<uint8_t>> &image)
{
	Vec2I sv0(std::round(v0.x), std::round(v0.y));
	Vec2I sv1(std::round(v1.x), std::round(v1.y));
	Vec2I sv2(std::round(v2.x), std::round(v2.y));
	//为了区分三角形类型,需要对顶点按y坐标进行排序
	Sort(sv0, sv1, sv2);

	if (sv0.y == sv1.y)	//平顶三角形
	{
		DrawTopFlatTriangle(sv0, sv1, sv2, color, image);
	}
	else if (sv1.y == sv2.y)	//平底三角形
	{
		DrawBottomFlatTriangle(sv0, sv1, sv2, color, image);
	}
	else
	{
		//拆分三角形
		float x = static_cast<float>(sv0.x) + (sv1.y - sv0.y)*(sv0.x - sv2.x) / static_cast<float>(sv0.y - sv2.y);
		Vec2I newVertex(x, sv1.y);
		DrawBottomFlatTriangle(sv0, sv1, newVertex, color, image);
		DrawTopFlatTriangle(newVertex, sv1, sv2, color, image);
	}
}

Ⅱ. Half-Space光栅化算法

一条直线可以将空间划分为两个half-space(“左-”边和“右+”边)。

向量a将空间一份为二

通过计算向量之间的叉乘可以判断一点v2在由v0和v1构成的向量a的哪一侧。二维向量叉乘(Perp Dot product or Edge Function)定义如下:

根据叉乘结果可以得到点与向量在空间中的相对关系:

Half-space算法通过计算三角形三条边Half-Space的交集判断点是否在三角形内,即 均大于等于0。

在实际计算中并不需要遍历Viewport内的所有像素点判断其是否在三角形内,只需要遍历位于三角形包围盒内部的像素即可。

Half-Space算法的简单实现如下:

void HalfSpaceTriangleBase(const Vec2I &v0, const Vec2I &v1, const Vec2I &v2, const Vec4<uint8_t> &color, Image<Vec4<uint8_t>> &image)
{
	auto PerpDot = [](const Vec2I &p0, const Vec2I &p1, const Vec2I &p) {
		return ((p1.x - p0.x) * (p.y - p0.y) - (p1.y - p0.y) * (p.x - p0.x));
	};

	//计算三角形的包围盒
	Vec2I min, max;
	min.x = max(min(min(v0.x, v1.x), v2.x), 0);
	min.y = max(min(min(v0.y, v1.y), v2.y), 0);

	max.x = min(max(max(v0.x, v1.x), v2.x), image.GetWidth() - 1);
	max.y = min(max(max(v0.y, v1.y), v2.y), image.GetHeight() - 1);

	if (min.x >= max.x || min.y >= max.y)
	{
		return;
	}

	//遍历包围盒内的像素
	for (int y = min.y; y <= max.y; y++)
	{
		for (int x = min.x; x <= max.x; x++)
		{
			Vec2I currPoint(x, y);

			int e0 = PerpDot(v1, v2, currPoint);
			int e1 = PerpDot(v2, v0, currPoint);
			int e2 = PerpDot(v0, v1, currPoint);

			//若点p与三条边的PerpDot均大于等于0则点p在三角形内
			if (e0 >= 0 && e1 >= 0 && e2 >= 0)
			{
				image.SetPixel(color, x, y);
			}
		}
	}
}

注:由于叉乘不满足交换律,所以顶点必须按照顺时针方向声明,若顶点按逆时针方向声明则计算结果会完全相反。

Ⅲ. 三角形重心坐标属性插值

位于三角形v0v1v2内的点p可由重心坐标表示如下:

                            点p在三角形内的重心坐标与点p和三角形顶点组成的三角形面积相关

在一维的图形(线段)中,点的重心坐标与距离相关,而在二维图形中点的中心坐标与面积相关。点p的重心坐标与面积的关系如下:

二维向量叉乘可以得到对应四边形面积

之前提到的二维向量叉乘可由用来判断点与向量的相对关系,同时也可以用来计算四边形面积:

void HalfSpaceTriangle(const Vec2I &v0, const Vec2I &v1, const Vec2I &v2, //顶点位置
	const Vec4<uint8_t> &color0, const Vec4<uint8_t> &color1, const Vec4<uint8_t> &color2, //顶点颜色
	Image<Vec4<uint8_t>> &image)
{
	auto PerpDot = [](const Vec2I &p0, const Vec2I &p1, const Vec2I &p) {
		return ((p1.x - p0.x) * (p.y - p0.y) - (p1.y - p0.y) * (p.x - p0.x));
	};

	float area = PerpDot(v0, v1, v2);

	//若三角形v0v1v2面积为0则为退化三角形
	if (area == 0)
	{
		return;
	}

	Vec2I min, max;
	min.x = max(min(min(v0.x, v1.x), v2.x), 0);
	min.y = max(min(min(v0.y, v1.y), v2.y), 0);

	max.x = min(max(max(v0.x, v1.x), v2.x), image.GetWidth() - 1);
	max.y = min(max(max(v0.y, v1.y), v2.y), image.GetHeight() - 1);

	if (min.x >= max.x || min.y >= max.y)
	{
		return;
	}

	for (int y = min.y; y <= max.y; y ++)
	{
		for (int x = min.x; x <= max.x; x ++)
		{
			Vec2I currPoint(x, y);

			float e0 = PerpDot(v1, v2, currPoint)/ area;
			float e1 = PerpDot(v2, v0, currPoint)/ area;
			float e2 = PerpDot(v0, v1, currPoint)/ area;

			if (e0 >= 0 && e1 >= 0 && e2 >= 0)
			{
				//插值顶点颜色
				float r = color0.r * e0 + color1.r * e1 + color2.r * e2;
				float g = color0.g * e0 + color1.g * e1 + color2.g * e2;
				float b = color0.b * e0 + color1.b * e1 + color2.b * e2;
				//或:float r = color0.r * e0 + color1.r * e1 + color2.r * (1 - e1 - e2);
				image.SetPixel(Vec4<uint8_t>(r,g,b,1), x, y);
			}
		}
	}
}

绘制效果如下:

 

4. 裁剪

Ⅰ. 点的裁剪

直接判断点是否在由Viewport组成的矩形内即可。

Ⅱ. 线段裁剪

线段与裁剪窗口之间的关系

线段与Viewport构成的裁剪窗口(Clip Window)之间存在三种关系:

  • 线段在Clip Window内(线段v0v1)
  • 线段在Clip Window外(线段v2v3)
  • 线段与Clip Window相交(线段v4v5)

构成Clip Window的四条直线left,right,top,bottom各自将2D平面分为2个区域,这些区域可以用4位二进制编码(Clip Code)表示:

  • 位于left左侧区域第一位编码为1,位于left右侧区域第一位编码为0
  • 位于right右侧区域第二位编码为1,位于left左侧区域第e二位编码为0
  • 位于bottom下侧区域第三位编码为1,位于bottom上侧区域第三位编码为0
  • 位于top上侧区域第四位编码为1,位于top下侧区域第四位编码为0

可以根据线段两个端点的Clip Code(code0,code1)判断线段与Clip Window之间的关系:

  • 若线段的两个端点都位于Clip Window内(code0 | code1=0000),则线段位于Clip Window内不需要裁剪。
  • 若线段的两个端点都位于平面内的同一区域中(code0 & code1 != 0000),则线段一定位于Clip Window外,可以直接抛弃。
  • 若线段的两个端点位于不同区域中(code0 ^ code1 != 0000),则需要进行裁剪。此时可以利用Clip Code判断线段与那条构成Clip Window的直线相交(如:code0 ^ code1 = 0001则与left相交)。

当线段与Clip Window相交时就需要求出线段与Clip Window的left,right,top,bottom的交点。

如上图,线段v0v1与线段v2v3相交与点p,已知点v0(x0, y0),v1(x1, y1),v2(x2, y2),v3(x3, y3)的坐标,求点p的坐标(x, y)。

//计算交点
bool LineIntersect(const Vec2I &v0, const Vec2I &v1, const Vec2I &v2, const Vec2I &v3, Vec2I &p)
{
	int a = v0.x * v1.y - v0.y * v1.x;
	int b = v2.x * v3.y - v2.y* v3.x;
	int denom = (v0.x - v1.x) * (v2.y - v3.y) - (v0.y - v1.y) * (v2.x - v3.x);

	int numx = a * (v2.x - v3.x) - (v0.x - v1.x) * b;
	int numy = a * (v2.y - v3.y) - (v0.y - v1.y) * b;

	//分母为0则线段不相交
	if (denom == 0 )
	{
		p = Vec2I(0,0);
		return false;
	}

	p = Vec2I(numx / denom, numy / denom);
	return true;
}

static unsigned int INSIDE = 0;
static unsigned int LEFT = 1 << 0;
static unsigned int RIGHT = 1 << 1;
static unsigned int BOTTOM = 1 << 2;
static unsigned int TOP = 1 << 3;

//计算ClipCode
unsigned int ComputeClipCode(Vec2I &v, const Vec2I &winMin, const Vec2I &winMax)
{
	unsigned int code = INSIDE;
	if (v.x < winMin.x)
	{
		code |= LEFT;
	}

	if (v.x > winMax.x)
	{
		code |= RIGHT;
	}

	if (v.y < winMin.y)
	{
		code |= BOTTOM;
	}

	if (v.y > winMax.y)
	{
		code |= TOP;
	}

	return code;
}

bool ClipLine(Vec2I &v0, Vec2I &v1, //进行相交测试的线段
	const Vec2I &winMin, const Vec2I &winMax) //Clip Window包围盒的最大和最小点坐标
{
	unsigned int code0 = ComputeClipCode(v0, winMin, winMax);
	unsigned int code1 = ComputeClipCode(v1, winMin, winMax);

	unsigned int code_and = code0 & code1;
	unsigned int code_or = code0 | code1;
	unsigned int code_xor = code0 ^ code1;

	//线段在Clip Window外
	if (code_and)
	{
		return false;
	}

	//线段在Clip Window内
	if (!code_or)
	{
		return true;
	}

	//若线段与left相交
	if (code_xor & LEFT)
	{
		Vec2I intersect_point;
		unsigned int point_code;
		if (LineIntersect(v0, v1, Vec2I(winMin.x, winMin.y), Vec2I(winMin.x, winMax.y), intersect_point))
		{
			point_code = ComputeClipCode(intersect_point, winMin, winMax);
			if (!code0)
			{
				v1 = intersect_point;
				code1 = point_code;
			}
			else
			{
				v0 = intersect_point;
				code0 = point_code;
			}
		}
	}

	//若线段与right相交
	if (code_xor & RIGHT)
	{
		Vec2I intersect_point;
		unsigned int point_code;

		if (LineIntersect(v0, v1, Vec2I(winMax.x, winMin.y), Vec2I(winMax.x, winMax.y), intersect_point))
		{
			point_code = ComputeClipCode(intersect_point, winMin, winMax);
			if (!code0)
			{
				v1 = intersect_point;
				code1 = point_code;
			}
			else
			{
				v0 = intersect_point;
				code0 = point_code;
			}
		}
	}

	//若线段与bottom相交
	if (code_xor & BOTTOM)
	{
		Vec2I intersect_point;
		unsigned int point_code;

		if (LineIntersect(v0, v1, Vec2I(winMin.x, winMax.y), Vec2I(winMax.x, winMax.y), intersect_point))
		{
			point_code = ComputeClipCode(intersect_point, winMin, winMax);
			if (!code0)
			{
				v1 = intersect_point;
				code1 = point_code;
			}
			else
			{
				v0 = intersect_point;
				code0 = point_code;
			}
		}
	}

	//若线段与top相交
	if (code_xor & TOP)
	{
		Vec2I intersect_point;
		unsigned int point_code;

		if (LineIntersect(v0, v1, Vec2I(winMin.x, winMin.y), Vec2I(winMax.x, winMin.y), intersect_point))
		{
			point_code = ComputeClipCode(intersect_point, winMin, winMax);
			if (!code0)
			{
				v1 = intersect_point;
				code1 = point_code;
			}
			else
			{
				v0 = intersect_point;
				code0 = point_code;
			}
		}
	}

	//判断裁剪后的线段是否在Clip Window内
	code_or = code0 | code1;
	if (!code_or)
	{
		return true;
	}

	return false;
}

裁剪效果如下:

无裁剪和有裁剪对比,黑色框为Clip Window

Ⅲ. 三角形裁剪

三角形裁剪可以采用Sutherland–Hodgman几何裁剪算法,首先选取Clip Window的一条边(Clip Edge, 这里选取left),然后依次遍历三角形的每条边,并维持一个输出顶点列表,根据三角形边与Clip Edge的关系更新输出顶点列表:

  • 若三角形边的两个端点都在线段Clip Edge内侧(根据PrepDotP判断顶点与Clip Edge的关系),则将第二个顶点加入到输出列表中。
  • 若三角形边的第一个端点在线段Clip Edge内侧而第二个端点在Clip Edge外侧,则将边与Clip Edge的交点加入到输出列表中。
  • 若三角形边的第一个端点在线段Clip Edge外侧而第二个端点在Clip Edge内侧,则将边与Clip Edge的交点以及第二个顶点依次加入到输出列表中。
  • 若三角形边的两个端点都在线段Clip Edge外侧,则什么都不做。

最后将输出的顶点三角化,即得到了被选定Clip Edge裁剪后的三角形,对每条Clip Edge重复以上过程即得到了裁剪后的三角形。裁剪过程用Gif展示如下:

Sutherland–Hodgman动态展示

Sutherland–Hodgman算法实现如下(裁剪后的顶点的属性插值可以参考DDA算法中所写的插值方法):

//使用选定Clip Edge对三角形进行裁剪
template<typename T>
void Clip(std::vector<Triangle> &ts, const Vec2I &clipP0, const Vec2I &clipP1, T fun)
{
	std::vector<Triangle> clipedTriangle;
	for (int j = 0; j < ts.size(); j++)
	{
		Triangle currT = ts[j];
		if (fun(currT))
		{
			clipedTriangle.push_back(currT);
		}
		else
		{
			std::vector<Vec2I> clipedPoint;

			auto PerpDot = [clipP0, clipP1](const Vec2I &p) { return (clipP1.x - clipP0.x) * (p.y - clipP0.y) - (clipP1.y - clipP0.y) * (p.x - clipP0.x); };
			int tPrepDot[3] = { PerpDot(currT.v[0]), PerpDot(currT.v[1]),  PerpDot(currT.v[2]) };

			for (int i = 0; i < 3; i++)
			{
				int k = (i + 1) % 3;
				Vec2I p0 = currT.v[i];
				Vec2I p1 = currT.v[k];

				int iPrepDot = tPrepDot[i];
				int kPrepDot = tPrepDot[k];

				if (iPrepDot <= 0 && kPrepDot <= 0)
				{
					clipedPoint.push_back(p1);
				}
				else if (iPrepDot > 0 && kPrepDot <= 0)
				{
					Vec2I newPoint = LineIntersectBase(clipP0, clipP1, p0, p1);
					clipedPoint.push_back(newPoint);
					clipedPoint.push_back(p1);
				}
				else if (iPrepDot <= 0 && kPrepDot > 0)
				{
					Vec2I newPoint = LineIntersectBase(clipP0, clipP1, p0, p1);
					clipedPoint.push_back(newPoint);
				}
				else
				{
				}
			}

			for (int i = 0; i < clipedPoint.size() - 2; i++)
			{

				int k = (i + 1) % clipedPoint.size();
				int m = (i + 2) % clipedPoint.size();
				Triangle tri(clipedPoint[0], clipedPoint[k], clipedPoint[m]);

				clipedTriangle.push_back(tri);
			}
		}
	}

	ts = clipedTriangle;
}

void SHClip(std::vector<Triangle> &ts, const int &left, const int &right, const int &bottom, const int &top)
{
	Vec2I lb(left, bottom);
	Vec2I rb(right, bottom);
	Vec2I lt(left, top);
	Vec2I rt(right, top);

	//对Left进行裁剪
	auto filterLeft = [left](const Triangle &tri) { return tri.tmin.x >= left; }; // 若三角形包围盒满足条件则可以不裁剪
	Clip(ts, lb, lt, filterLeft);

	//对Top进行裁剪
	auto filterTop = [top](const Triangle &tri) { return tri.tmax.y <= top; };
	Clip(ts, lt, rt, filterTop);

	//对Right进行裁剪
	auto filterRight = [right](const Triangle &tri) { return tri.tmax.x <= right; };
	Clip(ts, rt, rb, filterRight);

	//对Bottom进行裁剪
	auto filterBottom = [bottom](const Triangle &tri) { return tri.tmin.y >= bottom; };
	Clip(ts, rb, lb, filterBottom);
}

裁剪效果如下:

三角形裁剪效果,黑色框为裁剪窗口

 

5. 2D遮挡

之前所介绍的算法只解决了如何绘制几何图元的问题,但光栅化还涉及到图元遮挡问题,对于2D遮挡的最简单算法为:画家算法。用一句话来说就是:先绘制的图元会被后绘制的图元遮挡。

 

由于篇幅所限本篇文章还没有介绍其他的half-space改进算法如Block Based Half-space,Zig-Zag等..,这些改进算法可以参考文献:

https://www.researchgate.net/publication/286441992_Accelerated_Half-Space_Triangle_Rasterization

 

 

 

 

 

 

 

 

 

 

 

 

 

最后

以上就是可靠世界为你收集整理的用C++编写一个简单的光栅化渲染器:2D篇的全部内容,希望文章能够帮你解决用C++编写一个简单的光栅化渲染器:2D篇所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(37)

评论列表共有 0 条评论

立即
投稿
返回
顶部