图形学初步

上一篇讲完了直线最简单的生成算法，这篇我们讲圆的生成算法，这些都是比较basic&easy的思路和code，并且一定能实现，因为博主我也在学习中~

除了直线的光栅化研究，还有很多曲线光栅化研究，比如说：圆、椭圆、抛物线、双曲线等圆锥曲线的光栅化。其中，Bresenham算法是一种最简单最有效的方法。我们先看下图：

怎么画圆呢？如果是一个像素一个像素的去算，是不是太不符合工科生的思维了。我们要的是，用尽量小的脑力劳动去完成一个比较大的工作量~只要算法写得好，放心交给计算机跑。

首先，我们只需要画出一个八分圆(逆时针0°-45°)，也就是①的那段圆弧；然后②这段圆弧就可以通过y=x对称变换得到，这时候我们把①②合并起来就得到了一个四分圆(逆时针0°-90°)；四分圆对x=0对称变换，得到了③④，把①②③④合并起来通过y=0对称变换，就得到了下半部分的半圆，上半圆和下边圆合并起来就是整个圆啦！

那三个 二阶对称变换矩阵怎么理解，这里需要读者有线性代数的基础。比如说我们有点A(2,1)在圆上，那么通过y=x这个直线得到的对称点是：

不知道哪位小主有更好的数学描述工具啊，一眼看上去就很拙劣的图都是鄙人用mspaint画出来的，委屈·····

好了，下面我们开始推导Bresenham算法啦，这里我们让坐标原点是圆心，那么第一个四分圆应该是顺时针画还是逆时针画呢，我们看到，如果起始点是(0,R),然后顺时针画圆的话，y是x的递减函数；如果起始点是(R,0)，然后逆时针画圆的话，x是y的递减函数。顺时针比较符合人的理解方式，所以我们选择顺时针方向画圆~

那么从起点开始，下一个像素该选择哪个像素呢？我们有三个方向的像素可以选择-----右方像素、右下角像素、下方像素，分别记为mH，mD，mV。如下图所示：

我们要在这三个像素中，选择一个像素点。选择的依据就是这个点应该是最逼近真正的圆的。我们用差值来表达逼近的程度，也就是---这个点离圆心的距离平方-圆半径平方：

圆这条线呢，肯定不会乖乖的经过这三个点，它可能会在点与点之间裸奔。于是我们用人脑穷举，发现圆与点(xi,yi)附近光栅网格的相交关系只有5种可能，也就是上面的那幅图。下面我们开始思考这5种情况了：

如果∆i < 0 ，说明右下角像素点(xi + 1,yi - 1) 在圆内，对应情形①②，这时候取像素(xi + 1,yi),也就是mH；或者取像素(xi + 1,yi - 1)，也就是mD，因为这时候只有mH或者mD最逼近圆弧了，反正看情况二选一。

        情形①，到底圆弧离mH近还是mD近，用这个方程来衡量：

               下面我们来简化这个判断语句，对于情形①来讲，mH肯定是在圆外，mD肯定是在圆内，也就是说

               因此     

               去括号以后，得到

        情形②，只能选择mH，这时候mH和mD都位于圆内，因此

               这时候，

               我们就可以把情形②跟情形 ①中的其中一个分支合并啦，合并结果就是：

如果∆i > 0, 也就是右下角(xi + 1,yi -1)位于圆外，对应图中的情形③④，显然只能取mD，或者mV，下面就分情况讨论。

        情形③，判断mV和mD哪个点更逼近真正的圆

       同理，我们把公式简化

        情形④，只能取下方像素mV

        因此，我们可以把情形④和情形③中的一个分支合并啦，合并结果就是：

如果∆i=0，

        情形⑤，圆恰巧乖乖的经过了mD，这时候，我们要看是否可以归并到上述的两大情况的其中一种：

         也就是：

          随便归类到哪一个都行。

最后，判别准则就简化如下：

也可以这么写：

因此我们的Bresenham的伪代码就出来了：

最后的画图结果应该是这样的：

好了，一个四分圆搞定了，那么我们怎么通过整个四分圆得到整个圆呢?

思路就是在循环中，每次都把选中的像素散播在其他象限对应的位置。

于是我的c++代码是这样的：

因为计算机的原点是从屏幕左上角开始的，往右是x轴正向，往下是y轴正向~

其实这个算法并不难，就是要计算的公式太多。。。。。没有耐心和数学功底的人是干不下去的。。。

若有理解不到之处，还请大佬指正~