华科_图形学笔记_0401_图形思维的起点

本文主要是介绍华科_图形学笔记_0401_图形思维的起点_朴素的软光栅(一)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

计算机图形学_华中科技大学_中国大学MOOC(慕课)

4.1.1_初次尝试-点和直线(上):DDA算法

光栅扫描式图形显示器实际上可以看做是一个点积单元发生器

在这样一个设备上生成图形的过程,其实就是光栅化的过程,其可以分为两个过程

1.根据图形的定义在点阵单元上确定最佳逼近与图形的像素集,这个逼近的过程本质可以认为是 连续量向离散量的转换

2.给像素指定合适的颜色值,这里可以通过光照,纹理等的计算,来得到对应像素的颜色值

这个过程就叫做图形的光栅化,也叫做图形的扫描转换

根据之前对管线的了解,在现代管线中,经常通过应用程序,得到三角网格的顶点表示,而光栅化的工作则交给CPU光栅化阶段来完成

但是,其实我们也可以自己来完成从图元到像素点的转换,这种不借助硬件提供的API,直接由应用程序来进行计算的过程就叫做软光栅

扫描转换的概念

课程约定

1.左下角为(0,0),水平方向是X轴,向右方向X增大,垂直是Y轴,向上方向Y增大,很显然每个像素点的XYZ坐标都必须是整型的数值

2.为了简化问题,我们先考虑二维图形的生成

首先来看一个点,它的输入是一个点的坐标,输出是最佳逼近该点的像素点

怎么找到一个最佳逼近的点呢?如果点的坐标有小数,就需要进行一下四舍五入,这样就直接可以最佳逼近它的像素点了

以点为基础,我们再来看看直线,直线扫描转换的输入是P0和P1,也就是它的两个端点的坐标,输出则是最佳逼近这条直线的像素点阵,除此以外,还要特别考虑直线生成的质量

什么样的直线才算是高质量的?

第一点,直线要直,一方面所选的像素点应该尽量的靠近理想的直线,另一方面,由于扫描转换总会产生一些锯齿的效应,这就是走样现象,因为需要根据需要采用 反走样技术

第二点,直线的端点,要准确,也就是没有定向性和断裂的情况

无定向性:就是从A点到B点画一条直线和B点到A点画一条直线,这两条直线应该是重合的,而在直线和由直线组成的图形绘制中,由算法的累计误差和设备的精度所致产生的断裂和不连接的情况也是不允许的

第三点,直线的亮度和色泽要均匀,如果绘出的像素点密度不均匀,就从视觉上给人一种一段亮,一段暗的感觉,当显示的直线宽度及转角不同的时候,点的密度也应该保持不变,否则也会造成直线亮度的不均

第四点,画线的速度要快,最后还要可能要求直线具有不用的色泽,亮度,线型等

在光栅图形学的研究中,有很多成熟的直线绘制算法

数值微分法_DDA

DDA算法原理

由于直线的一阶导数是连续的,而且对于δX和δY是成比例的,因此可以通过当前的位置(Xi,Yi)上,分别加一个小的增量, ξ δX和 ξ δY,这里的 ξ (埃普西隆)是一个无穷小的正数,来求出下一个点,Xi+1和Yi+1的X,Y坐标

下一个点的坐标可以这样来计算

Xi+1 = Xi + ξ* δX

Yi+1 = Yi + ξ* δY

很显然,这个方法在精度无限高的情况下,可以绘制出没有误差的直线

但是,设备的精度总是有限的,因此通常要选择一个什么样的值?

选择一个 ξ等于 δX和 δY中的最大值的导数,这个时候, ξ δX或者是 ξ δY中就会有一个变成单位步长,这样以来可以使得算法在 最大位移方向 上,每次总是走一步,这就可以分成两种情况进行考虑了

一种是最大位移方向是X方向,也是就说斜率的绝对值小于1的情况,这个时候 ξ是 δX绝对值的导数

那么在X方向上,每次走一步,也就是X增加1或者减少1,那么Y对应的增量是+-K,这里的K是斜率

另一种情况,最大位移方向是Y方向,也是就说斜率的绝对值大于1的情况,这个时候 ξ当然就取得了 δY绝对值的导数,每次在Y的方向上,每次走一步,也就是Y增加1或者减少1,那么X对应的增量是+-K分之1

最大位移方向

如果不管最大位移方向,每次就按习惯让X走一步,来计算Y会如何呢?

当斜率大于1或者很大的时候,X每次走一步,可是Y的变化就很大了,这样画出来的点与点的距离很大,直线看起来就是一系列离散的点,根本没法连在一起,形成一条连续的直线,所以在DDA算法实现的过程中,要注意最大位移方向的变化

两种情况下,直线的生成

需要注意的是,由于在光栅化的过程中,不可能绘制半个像素点,因此,对求出的Xi+1和Y i+1的值,需要进行四舍五入,当然也可以通过+0.5再取整的方法来实现,从某种程度上来讲,后面的方法效率更高

这样一来,就可以得到DDA算法的过程

for循环就是用来输出最佳逼近的像素点

4.1.2_初次尝试-点和直线(中):中点的Bresenham算法

在之前的DDA算法中，我们已经明白了最大位移方向的重要性。同时，我们也发现了一个规律，那就是从当前点到下一个点，每次都需要在最大位移方向上走一步, 其实取决于直线真实位置更靠近哪里，我们可以认为这里有一个误差项，可以根据误差项的不同来确定另一个方向是否走步。

首先，我们来看看终点的算法。

同样给定直线的两个端点P0和P1，可以得到直线的斜截式表示Y=KX+B，我们还可以写出它的隐式方程F(x,y)=Y-KX-B, 其中的K，仍然是斜率这个概念。很显然，一条直线将平面分为了三个区域，直线的上方，直线以及直线的下方。有了这样的隐式方程，我们会发现，对于直线上的点 F(x,y) =0。对于直线上方的点 F(x,y) >0,而对于直线下方的点 F(x,y)<0。

中点Bresenham算法基本原理

我们把我们的直线假定在斜率是从零到一的范围内,由于X是最大位移方向，因此每次在X方向上加一，

假定当前的点是Pi(Xi,Yi)，那么下一个点一定是Pu，或者是Pd,Pu就是P_up上面的点，所以它的坐标是(Xi+1，Yi+1)。而Pd，也就是P_down下面的点。那么它的坐标是(Xi+1,Yi)。

如果我们用M表示Pu和Pd的中点，也就是现在M的坐标是这样的了，M他的坐标是(Xi+1,Yi+0.5)。而这里的Q是理想直线与垂直线X=Xi+1的交点。如果中点M在Q的下方，证明这条直线，更接近Pu这个点，所以我们就把 Pu 选为下一个像素。

否则，就表明，它更接近于下面的这个点，我们就应该取P_down。

这个时候，刚才的隐式方程就派上用场了。

直线的隐式方程F(x,y )=Y-KX-B，只需要判断M是在直线的上方，下方还是直线上就可以了。所以我们把M带入到这个隐式方程 F(x,y ) 中，并且判断它的符号。就可以知道Q和M的位置关系，所以我们可以构造一个判别式，大家看这个公式d。当这个D<0的时候，M在直线的下方，所以就应该取Pu，当d>0的时候，就应该取正右方的Pd。而d=0的时候,Pu和Pd都可以，可以随便取一个，那这里，我们可以约定曲Pd。

也就是说，当d<0的时候，Y需要增加1,而d>=0的时候，Y保持不变。

想要得到一个简化的算法，还要对误差项进行递推。当然这也分为两种情况，一个是d<0的情况，这时取右上方的像素Pu。

既然当前点为Pu了，候选点就是这样的两个点，那么候选点的中点坐标显然Xi+2，Yi+1.5。有了中点的坐标，这时的误差项就很容易计算了。此时地的增量，是1-K。

另一种情况，也就是d>=零的时候，这时候取证右方的像素Pd。

既然当前点为P的候选点,就是这样的两个, 那么候选点的中点坐标显然就是X加二和Y加0.5,这时可以算出d的增量是-K。

对于误差项来说，我们已经知道是如何递推的了，那么接下来我们就必须找到它的初值。显然，直线的第一个像素点P0(X0,Y0)是在直线上是准确的，那么这时候两个候选点就在这儿。中点当然就在这儿，显然它的坐标是X0+1，Y0+0.5。因此，我们可以算出D的初值。

是多少？0.5减K。这样一来，有了D的初值，也有了d的递推方法。也知道如何根据d来取点，这个算法就完备了。而且这里的d 也采用了增量计算来处理了，可是我们发现到这里，这个算法还是没有超越的DDA，因为这其中仍然有小数，比如dk。其实我们只用到了d的符号，我们如果把它放大一个正整数倍，把它变成整数。

那么K是小数，K的计算是δY/ δ X得到的，所以我们需要放大德塔X倍才能把它整数化。另外一个是0.5，显然比较简单，只需要放大两倍。因此我们可以用两倍的 δX倍的d来代替原来的d来摆脱小数。请注意，这时候d的初值增量都发生了变化，他们都变成了整数。所以我们终于得到了一个只有整数运算的算法。

这个斜率在零到一之间的情况下，Bresenham算法的过程。首先输入直线的两个端点P0和P1。第二步，计算初始的值， δ X， δ Y。那么接下来就是XY。第三步是绘制这个点XY。首先要判断D的符号，当d<0的时候，那么(x,y)它的更新就是X+1，Y+1。这个d的更新，就是为d加上两倍的 δ X减去两倍的 δY 。否则，XY就更新为(X+1,Y)，也就是说，y不往上走了。而这时候d的增量是负的两倍的 δy。

第四步，当直线没有画完的时候，重复这个步骤三，否则，就结束了。下面我们可以看一个具体的例子了，对于一条连接着两个点(0,0)和(8,5)的直线段，我们可以看一看终点Bresenham算法扫描转换的全过程。由于这里的X0,Y0是零，而X1,Y1是八五。所以直线的斜率是5/8,满足在零到一之间，所以刚才的算法是适用的。