基本图形生成

《基本图形生成》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章基本光栅图形基础*****物体的形状和颜色可用象素矩阵或直线线段和多边形填充区域等基本几何结构来描述。点和直线段是最简单的几何成分，其它可供构造图形的输出图元有圆及其它圆锥曲线、二次曲面、样条曲线和曲面、多边形填充区域以及字符串等。而二维图形的生成是三维图形生成的基础，研究计算机生成图形需先从二维图形的生成开始。下面将讨论一些基本二维图元生成技术和算法，以光栅图形系统的扫描转换方法为基础。7/31/20211计算机图形学演示稿本章内容？直线段的扫描转换算法DDA算法Bresenham画线算法？区域填充扫描线填充种

2、子填充边填充7/31/20212计算机图形学演示稿直线段的扫描转换算法直线的扫描转换:确定最佳逼近于该直线的一组象素，并且按扫描线顺序，对这些象素进行写操作。常用算法：数值微分法（DDA）Bresenham算法。7/31/20213计算机图形学演示稿直线是点的集合，在几何学中直线被定义为两个点之间的最短距离。也就是说一条直线是指所有在它上面的点的集合。直线是一维的，即它们具有长度但没有面积。直线可以向一个方向及其相反的方向无限伸长，这不是计算机图形学中所需要的，在图形学中研究的对象是直线段。已知线段的起点坐标（x1,y

3、1），终点坐标（x2,y2)，这两点就确定了一条线段。一般来讲，任何图形输出设备都能准确地画出水平线X和垂直线Y,或对角线，但要画出一条准确斜线不是件容易的事。在光栅系统中，线段通过象素绘制，水平和垂直方向的台阶大小受象素的间隔限制。这就是说，必须在离散位置上对线段取样，并且在每个取样位置上决定距线段最近的象素，画一条直线实际上就计算出来一系列与该线靠近的象素。7/31/20214计算机图形学演示稿AB光栅化的直线ABCD7/31/20215计算机图形学演示稿数值微分法（ＤＤＡ）假定直线的起点、终点分别为：（x0,y0

4、),(x1,y1)，且都为整数。7/31/20216计算机图形学演示稿数值微分(DDA)法基本思想已知过端点P0(x0,y0),P1(x1,y1)的直线段Ly=kx+b直线斜率为这种方法直观，但效率太低，因为每一步需要一次浮点乘法和一次舍入运算。7/31/20217计算机图形学演示稿数值微分(DDA)法计算yi+1=kxi+1+b=kxi+b+kx=yi+kx当x=1;yi+1=yi+k即：当x每递增1，y递增k(即直线斜率)；注意上述分析的算法仅适用于k≤1的情形。在这种情况下，x每增加1,y最多增加1。当

5、k1时，必须把x，y地位互换7/31/20218计算机图形学演示稿(Xi+1,Yi+k)(Xi,Round(Yi))(Xi,Yi)栅格交点表示象素点位置7/31/20219计算机图形学演示稿数值微分(DDA)法增量算法：在一个迭代算法中，如果每一步的x、y值是用前一步的值加上一个增量来获得，则称为增量算法。DDA算法就是一个增量算法。7/31/202110计算机图形学演示稿数值微分(DDA)法voidDDALine(intx0,inty0,intx1,inty1,intcolor)intx；floatdx,dy

6、,y,k;dx=x1-x0;dy=y1-y0;k=dy/dx;y=y0;for(x=x0;xx1,x++)drawpixel(x,int(y+0.5),color);y=y+k;7/31/202111计算机图形学演示稿数值微分(DDA)法例：画直线段P0(0,0)--P1(5,2)xint(y+0.5)y+0.5000+0.5100.4+0.5210.8+0.5311.2+0.5421.6+0.5522.0+0.57/31/202112计算机图形学演示稿数值微分(DDA)法缺点：在此算法中，y、k必须是floa

7、t，且每一步都必须对y进行舍入取整，不利于硬件实现。7/31/202113计算机图形学演示稿Bresenham画线算法在直线生成的算法中Bresenham算法是最有效的算法之一。令k=Δy/Δx，就0≤k≤1的情况来说明Bresenham算法。由DDA算法可知：yi+1=yi+k(1)由于k不一定是整数，由此式求出的yi也不一定是整数，因此要用坐标为（xi,yir）的象素来表示直线上的点，其中yir表示最靠近yi的整数。7/31/202114计算机图形学演示稿Bresenham画线算法设图中xi列上已用（xi,yir）

8、作为表示直线的点，又设B点是直线上的点，其坐标为（xi+1,yi+1），显然下一个表示直线的点（xi+1,yi+1,r）只能从图中的C或者D点中去选。设A为CD边的中点。若B在A点上面则应取D点作为（xi+1,yi+1,r），否则应取C点。xiXi+1Yi,rYi+1,rCDBAε(x)的几何意义为能确定B在A点上面或下面，令ε(