概述
本篇文章将会介绍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篇所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
发表评论 取消回复