记录：tinyrenderer

Bresenham’s line drawing（布雷森汉姆算法）

进行games101的光栅化作业时，对其渲染原理仍不甚了解，找到tinyrenderer软光栅项目。在此记录下试错的过程。
作者在最初为我们做好了framebuffer,读者入手的方向实际是从渲染的过程开始。对于如何渲染出像素显示在画面上，应该需要从其他博主那进行学习，或者从作者实现的文件中分析，这里就不做多余的解释。
友情提示:这里记录个人对tinyrenderer原理的理解，若需源代码请从原作者的github处下载。（作者的博客内蓝色高光处包含了不同阶段源代码的地址）

github地址在这里：https://ssloy.github.io/tinyrenderer
作者第一节从线的绘制开始，一个三角面有三个顶点，即绘制三条直线。
Bresenham’s line drawing（布雷森汉姆算法）
给出两个顶点a(ax,ay),b(bx,by),渲染出两点间的直线。
按照作者的说法，直接抛出算法会很难以理解，采取渐进的形式，逐渐演化算法的执行。
假设参数t \(\in\)[0,1],定义二维点(x(t),y(t))如下：

1. x(t) = a_x + t * (b_x - a_x)<br>
2. y(t) = a_y + t * (b_y - b_y)

复制代码

对于该公式的推导可以想象直线上两点，在两点间再取一点(x(t),y(t))，(这里设为（x,y）或许更好一些，但是图画好了懒得改了)
很容易可以想到它们间存在的相似三角形，

1. (y(t) - a_y) / (b_y - a_y) = t

复制代码

t为0时，y(t) = ay，t为1时，y(t) = by。
之后，简单推导即可得到参数方程，x(t)同理可得。

代码实现

1. void line(int ax,int ay,int bx,int by, TGAImage &framebuffer,TGAColor color){
2.     for(float t = 0; t < 1; t += 0.02){
3.         int x = ax + std::round(t * (bx - ax));
4.         int y = ay + std::round(t * (by - ay));
5.         framebuffer.set(x,y,color);
6.     }
7. }

复制代码

可以注意到红线部分存在四个缺口,仔细观察一下可以发现

t的取值为0-1，每0.02取值进行运算，可取51次

cx - ax = 62 - 7 = 55 次

其gap = 55 - 1 = 4

t的取值不足导致了gap的出现：
一个直接的解决方法是：

1. 可以将 t += .02改为 t += .01，这样确实可以解决当前的gap问题，但当cx - ax的差值更大时，t的取值仍然会不足；

复制代码

作者给出的方法则是使用t的定义式，而不是直接赋值：

1. t = (x(t) - a_x) / (b_x - a_x)
2. 或者
3. t = (y(t) - a_y) / (b_y - a_y)
4. <details><summary>对于t定义式可行的个人见解</summary>
5. 每一个(x(t),y(t))坐标表示一个像素点位置，两点间横坐标差值即缺少的横向像素点的数量，纵坐标同理，这样即可遍历每一个单位像素点的横坐标，得到对应的t值，从而求得相应的纵坐标。<br>
6. </details>

复制代码

函数实现

1. void line(int ax,int ay,int bx,int by, TGAImage &framebuffer,TGAColor color){
2.     for(int x = ax; x <= bx; x ++){
3.         //t需要float型，故须使用static_cast<float>来使计算返回浮点值
4.         float t = (x - ax) / static_cast <float> (bx - ax);
5.         int y = ay + std::round(t * (by - ay));
6.         framebuffer.set(x,y,color);
7.     }
8. }

复制代码

不难猜出，这次引入float error会花费更多的性能,为进行接下来的消除浮点运算。

我在这里进行进一步的演算，以便可以更清晰的消除浮点运算（error由float转为int）：

1. if(bx < ax){
2.     std::swap(ax,bx);
3.     std::swap(ay,by);
4. }

复制代码

至此，我们成功消除了浮点运算，实现布雷森汉姆算法。代码实现

1. bool steep = std::abs(bx - ax) < std::abs(by - ay);
2. if(steep){
3.     std::swap(ax,ay);
4.     std::swap(bx,by);
5. }
7. //在绘制直线时，须判断steep，换回x,y位置
8. if(steep)
9.     framebuffer.set(y,x,color)
10. else
11.     framebuffer.set(x,y,color);

复制代码

从作者的测试结果来看，布雷森汉姆算法的实际速度要慢于第一次的优化，原因则是现在的整数运算并不总是比浮点运算更高效。
至于无分支结构的优化，可以在作者的博客中进行了解，我实际进行的测试中，作者的无分支形式实际要花费更多的性能，可能是现在的CPU的对分支版本的优化更加高效，不充分的无分支形式无法在其中获得优势

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！