dda算法画直线_计算机图形学三：直线光栅化的数值微分算法,中点Brensenham算法和三角形的光栅化...
直线与三角形的光栅化算法
在进入具体的直线光栅化以及三角形光栅化算法之前，我们首先需要知道光栅化是一个什么样的过程。简单来说光栅化的目的就是将想要展现的物体给真正现实到屏幕上的过程，因为我们的物体其实都是一个个顶点数据来表示的，如何表这些蕴含几何信息的数据转化为屏幕上的像素就是光栅化所考虑的东西。比如说一条直线，究竟该用哪些像素点去逼近它，一个三角形，又用哪些像素集合表示它，这都是光栅化的过程。本节主要讨论介绍两个直线光栅化和一个三角形光栅化算法。
1 屏幕像素的表示
屏幕中的每一个像素点我们都用整数坐标进行表示，最大最小值与分辨率相对应，考虑到每个像素都有一定的面积，我们定义(x+0.5,y+0.5)为该(x,y)像素的中心，如图中黑圈所示。
2 直线光栅化算法
2.1 DDA数值微分算法
DDA算法是一个非常简单直观的算法。 首先当任何一条直线知道任意两点时都可以用
我们分别就图上两种情况进行考虑(假设起点与终点给定(确定了直线方程)，就像图中一样)
1 当
2 当
图中的两种情况的光栅化结果也已给出供参考。
2.2 中点Bresenham算法
我们首先规定想要光栅化的线段的起点
中点Bresenham算法的思想其实也比较简单，我们在这里只给出
我们已经成功画出了前三个蓝色方格之后，所要考虑的便是第三个蓝色方格右边或者右上的橙色方格，此时我们取这两个橙色方格的中点，如图中圆圈符号所对应的那个点，倘若这个点在直线方程的下面，那么很明显我们应该选择右上的方格。
第二种情况：
此时中点位于直线方程的上方，此时选择右边的橙色方格。
至此，如何判断两种方格选择的条件已很明显，就是确定中点与直线的位置关系，这里就可以使用到一开始定义的
显然，当f(x+1,y+0.5) > 0的时候中点在直线上方，当f(x+1,y+0.5) < 0的时候中点在直线下方 （其中x+1，y+0.5是为了表示两个橙色方格的中点，此时x，y为前一个确定的像素坐标）
伪代码如下：
其中的，some condition也就很明显的是
目前为止，算法整体便已完成，但有一个问题是，我们每次都要进行一次F（x，y）的计算，倘若直线方程比较复杂，这是很消耗资源的(因为在底层可能是几百万次的重复调用)。因此一种改进方法便是利用增量算法。不难具体算出f(x,y)方程具体如下：
观察可以得出
那么算法只需要算出第一次的 f(x+1,y+0.5) ，之后的每次只需根据上述式子进行相应增量计算即可，如下：
如果还有不解，不妨具体的取两个点推一边算法便可加深理解。 当然中点bresenham算法其实还在这之上进一步做了一步优化，因为第一个d其中存在浮点数0.5,所以将有关d的等式两边都乘以2，消除了该0.5的浮点，增加了计算效率。
3 三角形光栅化算法
有读者可能会疑问，为什么不讲四边形五边形的光栅化算法，偏偏要谈三角形呢，因为三角形是最基本的多边形，大部分的模型都是用一个个三角形面表示，且任意的其它多边形其实都可以转化成多个三角形的形式，因此三角形的光栅化可以说是图形学中最基础的部分了。那么该怎么去做呢？
其实有一个非常直观的做法，我们对屏幕中的每一个像素进行采样，如果这个像素点在三角形之中那么这个像素点就应该被采用！对，这其实就是该算法的做法。那么该如何去判断一个点在不在三角形内部呢，那么其中一种办法就是利用叉乘的性质了
如图所示，我们事先知道想要光栅化的三角形的三个顶点P0，P1，P2，以及检测点Q。 只要分别计算
因此自然的，只需要遍历每一个点就可以得出三角形的光栅化结果了！当然我们还可以进一步的进行优化，因为显然并没有必要去测试屏幕中的每一个点，一个三角形面可能只占屏幕很小的部分，可以利用一个bouding box 包围住想要测试的三角形，只对该bounding box内的点进行采样测试，如下图：
这样就可以得到很大的效率提升了！
(强烈推荐闫令琪大佬的计算机图形学，讲的很棒B站有，本系列笔记可算作为该课程的对应笔记，并且会额外加上虎书以及其它计算机图形学课程的一些补充内容)
Reference
[1] Fundamentals of Computer Graphics 4th
[2] GAMES101-现代计算机图形学入门-闫令琪
[3] 华中科技大学-计算机图形学-万琳教授