第三章绘制基本图元.pptVIP

例，使用中点画圆算法画圆给定圆半径r=10，确定在第一象限从x=0到x=y沿八分圆的各像素点位置。决策参数的初始值为:p0=1-r=-9对于中心在原点的圆，初始点(x0,y0)=(0,10)，决策参数的初始增量值：2x0=0,2y0=20使用中点画圆法计算的后续决策参数值及像素位置如下：kpkxk+1,yk+12xk+1,2yk+10-6(1,10)2201-6(2,10)4202-1(3,10)62036(4,9)8184-3(5,9)101858(6,8)121665(7,7)1414第29页，共65页，星期日，2025年，2月5日用中点画圆法得到的像素位置(空心圆为第一象限的对称位置)第30页，共65页，星期日，2025年，2月5日使用折线来逼近曲线常见的曲线除圆以外，还有椭圆、圆锥曲线、三角和指数函数、样条曲线等。生成圆和椭圆等基本曲线的函数并未作为图元包含在OpenGL的核心库中，但核心库中包含了Bezier样条曲线，该曲线是由一组离散点定义的多项式。显示曲线的简单方法是使用直线段来逼近曲线，仅需确定一组曲线上的点并将它们连接成一组直线段。折线中的线段越多，曲线越平滑。第31页，共65页，星期日，2025年，2月5日3.5填充区图元图形学中常常需要用一种颜色或某种图案来填充一个区域，尽管有可能使用各种形状，但图形库一般不支持任意的填充形状，多数库函数要求填充区为多边形。多边形是由三个或更多的顶点连接而成的封闭图形，由于多边形的边界为直线段，因而比其他形状更容易处理。可将曲线转换为由分段折线构成的多边形，曲面也可以用一系列多边形面片来逼近。如果一个多边形的所有内角均小于180°，则该多边形为凸(convex)多边形。等价定义：它的内部完全在它的任一边及其延长线的一侧。如果任意两点位于凸多边形的内部，则其连线上的任一点也在凸多边形的内部。不是凸多边形的多边形称为凹(concave)多边形。退化多边形是指有共线或重合顶点的多边形，共线的顶点生成一条线段，重叠的顶点可以生成多余线段、重叠边或长度为0的边。为了软件的鲁棒性，图形软件可以拒绝退化或非平面的多边形。凹多边形也会产生一些问题，对凹多边形的填充及其它处理比较复杂，常常将凹多边形分割成一组凸多边形以提高效率。第32页，共65页，星期日，2025年，2月5日可以为多边形的每一条边建立一个向量，用相邻边的叉积来测试凸凹性，凸多边形的所有向量叉积均同号，如果某些叉积为正而另一些为负，则为凹多边形。识别凹多边形的另一个方法是观察多边形顶点位置与每条边延长线的关系。如果有些顶点在某一延长线的一侧而有些顶点在另一侧，则为凹多边形。多边形的填充算法分为扫描线填充算法和种子填充算法。扫描线的含义来源于光栅显示器，对屏幕上的每个像素点，按从上到下，从左到右的顺序进行显示，水平方向从左到右每扫描一行，就是一条y方向的扫描线，同理，从上到下也能形成x方向的扫描线。扫描线填充算法的原理是：待填充区域按y方向(或x方向)扫描线的顺序，计算扫描线与多边形的相交区间，再用指定的颜色填充这些区间的像素，区间的端点可以通过计算扫描线与多边形边界的交点求得。第33页，共65页，星期日，2025年，2月5日通用多边形的扫描线填充算法下图给出了多边形区域实心填充的扫描线过程。对每一条与多边形相交的扫描线，与边的交点从左到右排序，且将每一对交点之间的像素位置包括这对像素在内，设定为指定颜色，本例中与边界的四个交点定义了两段内部像素：从x=10到14的5个像素，以及从x=18到x=24的7个像素。如果是用图案填充多边形，则沿一条扫描线的每一个像素颜色由与图案重叠的位置确定。穿过多边形区域的扫描线上的内部像素第34页，共65页，星期日，2025年，2月5日有时情况比较复杂，当一条扫描线经过多边形的一个顶点时，扫描线在该顶点处与多边形的两条边相交，这种情况可能导致在这条扫描线上的交点要增加两个点。下图给出了在顶点处与多边形相交的两条扫描线。扫描线y’与偶数条边相交，必须将该顶点处的交点作为2个交点，才能正确标识该扫描线上的两对交点之间为内部像素段。扫描线y与多边形的5条边相交，必须将该顶点除的交点作为1个交点，才能正确标识该扫描线上的两对交点之间为内部像素段。通过观察相交边相对于扫描线的位置，可以发现扫描线y和扫描线y’间的拓扑差异。对于扫描线y，共享一个顶点的两条相交边位于扫描线的两侧，对于扫描线y’，两条相交边位于扫描线的同一侧。扫描线与多边形顶点相交，y’生成奇数个交点，y’生成偶数个交点第35页，共65页，星期日，2025