计算机图形学 第3章

《计算机图形学 第3章》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3章基本图形生成算法3.1生成直线的常用算法均假定所画直线的斜率k∈[0，1]。3.1.1DDA画线算法DDA（DigitalDifferentialAnalyzer）画线算法也称数值微分法，是一种增量算法。它的算法实质是用数值方法解微分方程，通过同时对x和y各增加一个小增量，计算下一步的x、y值。已知一条直线段L（P0,P1）,其端点坐标为：P0(x0,y0),P1(x1,y1)。可计算出直线的斜率k为：假定端点坐标均为整数，取直线起点P0(x0,y0)作为初始坐标。画线过程从x的左端点x0开始，向x右端点步进，每步x递增1，y递增k（即直线斜率）；取像素

2、点（x，round（y））作为当前点的坐标。3.1.2中点画线算法假设x坐标为xp的各像素点中，与直线最近者已确定，为P（xp,yp），那么，下一个与直线最近的像素只能是正右方的P1(xp+1,yp)，或右上方的P2（xp+1,yp+1）两者之一。令M为P1和P2的中点，易知M的坐标为（xp+1,yp+0.5）。设Q是理想直线与垂直线x=xp+1的交点。显然，若M在Q的下方，则P2离直线近，应取为下一个像素；否则应取P1。令a=y0-y1，b=x1-x0，c=x0y1-x1y0。构造判别式：d=a(xp+1)+b(yp+0.5)+cd的初始值d0=a+0.5b在

3、d≥0的情况下，取正右方像素P1，d1=a(xp+2)+b(yp+0.5)+c=d+a在d<0的情况下，取右上方像素P2，d2=a(xp+2)+b(yp+1.5)=d+a+b由于我们使用的只是d的符号，而且d的增量都是整数，只是其初始值包含小数。因此，我们可以用2d代替d，来摆脱小数。如果进一步把算法中2*a改为a+a等等，那么这个算法不仅只包含整数变量，而且不包含乘除法，适合硬件实现。3.1.3Bresenham画线算法过各行各列像素中心构造一组虚拟网格线，按直线从起点到终点的顺序计算直线与各垂直网格线的交点，然后确定该列像素中与此交点最近的像素。由图3-5不

4、难看出：若s

5、性，如下图所示。本节讨论的圆的生成算法均只计算从x=0到x=y分段内（1b区域）的像素点，其余的像素位置利用八对称性即可得出。3.2.2中点画圆算法假设x坐标为xp的各像素点中，与该圆弧最近者已确定，为P（xp,yp），那么，下一个与圆弧最近的像素只能是正右方的P1(xp+1,yp)，或右下方的P2（xp+1,yp-1）两者之一。令M为P1和P2的中点，易知M的坐标为（xp+1,yp-0.5）。显然，若M在圆内，则P1离圆弧近，应取为下一个像素；否则应取P2。判别式d：d的初始值为：在d≥0的情况下，取右下方像素P2，在d<0的情况下，取正右方像素P1，3.2.

6、3Bresenham画圆算法假设生成圆心在坐标原点，半径为r，从x=0到x=y的1/8圆弧。xi+1=xi+1相应的y则在两种可能中选择：y=yi，或者y=yi-1选择的原则是考察理想的y值是靠近yi还是靠近yi-1。判别式：di+1=2(xi+1)2+yi2+(yi-1)2-2r2判断式d的初始值为：d0=3-2r。如果di+1>=0，则y=yi-1，di+2=di+1+4(xi-yi)+10如果di+1<0，则y=yi，di+2=di+1+4xi+63.3区域填充3.3.1区域的表示和类型顶点表示：也称为几何表示，是用区域的顶点序列来表示区域。点阵表示：也称

7、为像素表示，是用位于多边形内的像素集合来刻画多边形。内点表示：区域内的所有像素着同一颜色，而区域外的所有像素具有另一种颜色；边界表示：区域边界上的所有像素点具有特定的颜色（可以是填充色），在区域内的所有像素均不能具有这一特定色，而且边界外的像素不能具有与边界相同的颜色。区域填充算法要求区域是连通的，因为只有在连通区域中，才可能将种子点的颜色扩展到区域内的其它点。区域按连通情况又可分为四连通区域和八连通区域。四连通区域指的是从区域上一点出发，可通过四个方向，即上、下、左、右移动的组合，在不越出区域的前提下，到达区域内的任意像素。八连通区域指的是从区域内每一像素出发

8、，可通过八个方向，即上、