西安交通大学计算机图形学第三章

计算机图形学1第3章输出图元杨新宇计算机图形学2主要内容1.点和线2.画线算法3.帧缓冲的装载4.画线函数5.圆生成算法6.椭圆生成算法7.其他曲线8.并行曲线算法9.曲线函数10.像素编址和物体的集合表示11.填充区域图元12.区域填充函数13.单元阵列14.字符生成计算机图形学33-1点和线通过将应用程序提供的单个坐标位置转换成输出设备的相应操作，可以进行点的绘制。通过计算沿路径上两指定端点间的中间位置，可以绘制一条线段。计算机图形学43-1点和线数字设备通过绘制两端点之间的离散点来显示线段。两个函数：setpixel(x,y)和getpixel(x,y)计算机图形学53-2画线算法直线的笛卡儿斜率截距方程为：

y=m*x+b

(3-1)给定线段的两个端点(x1,y1)和(x2,y2)，如图3-3，我们可以计算斜率m和截距y：

m=(y2-y1)/(x2-x1)(3-2)b=y1-m*x1(3-3)计算机图形学63-2画线算法对任意给定x增量∆x：∆

y=m*∆x(3-4)∆x=∆y/

m(3-5)计算机图形学7DDA算法数字微分分析仪(DDA)是一种线段扫描转换算法，基于等式（3.4）或（3.5）计算的∆

x或∆

y。

∆

y=m*∆x(3-4)∆x=∆y/

m(3-5)在一个坐标轴上以单位间隔对线段采样，从而确定另一个坐标轴上最靠近路径的对应整数值。计算机图形学8DDA算法如果斜率小于等于1，则以单位x（∆

x=1）间隔采样，并逐步计算每个y值。m是斜率k取整数值，从第一个开始递增至最后端点。由于m是0到1之间的任意实数，所以计算出的y必须取整。计算机图形学9DDA算法对于具有大于1的正斜率线段，则交换x和y的位置

m是斜率假设线段从左端点到右端点计算机图形学10DDA算法假如这个过程中的处理方向相反，即起始点在右侧。那么∆

x=-1或者（当斜率大于1，起始点在右侧时），则Δy=-1并且计算机图形学11DDA算法方程3-6至3-9也可以用来计算具有负斜率的线段的像素位置。假如斜率绝对值小于1，并且起始端在左侧，设置Δx=1并用方程3-6计算y的值。起始点在右侧(斜率绝对值小于1)，设Δx=-1得到y的位置从方程3-8。斜率绝对值大于1，设置Δy=-1和方程3-9。或设置Δy=1和方程3-7。计算机图形学12DDA算法输入两端点的像素位置(xa,ya)、(xb,yb)：端点水平间垂直间距离分别赋值为dx，dy。绝对值大的参数决定参数的steps值。从像素位置(xa,ya)开始，确定沿线段生成的下一个像素位置的每一步的偏移量。（运用方程3-6~方程3-9）循环上述过程steps次。计算机图形学13DDA算法DDA算法计算像素位置要比直接使用方程3-1要快。它利用光栅特性消除了方程3-1中的乘法，而在x和y方向使用适当的增量，从而沿路径逐步得到每个像素的位置。DDA算法缺点在浮点增量的连续叠加中，取整运算的累积误差使得计算像素的位置偏离实际线段。程序lineDDA中的取整操作和浮点运算仍然十分耗时。DDA练习直线的两个端点是（-10，5）与（13，20）直线的两个端点是（-10，10）与（-20，40）直线的两个端点是（10，20）与（30，10）直线的两个端点是（10，20）与（30，30）直线的两个端点是（13，20）与（-10，5）直线的两个端点是（-10，5）与（13，20）

格式：-------------------------------------------------

序号

点位置-------------------------------------------------0(-10,5)1(-9,6)计算机图形学14计算机图形学15Bresenham画线算法该算法是由Bresenham提出的一种精确而有效的光栅线段生成算法。可用于圆和其它曲线显示的整数增量运算。以单位x间距取样，需确定每个取样步长时哪个像素位置更接近于线段路径。计算机图形学16Bresenham画线算法首先考虑斜率小于1的直线的扫描转换过程，沿路径的像素位置以单位x间隔取样。从给定线段的左端点（x0，y0）开始，逐步处理后继列，并在离扫描线y值最近线段的像素上绘出一点。图3-7显示了这个过程中的第k步，假设已经决定要显示的像素在（xk，yk），那么下一步要确定在列xk+1上绘制那个像素，是在位置（xk+1，yk），还是（xk+1，yk+1）。计算机图形学17Bresenham画线算法两个点之间的差距为在取样位置xk+1，我们使用dl

和d2

来标示两个像素在数学路径上的垂直偏移(Fig.3-8)。在像素列位置xk+1处的直线上的y坐标可计算为：则计算机图形学18Bresenham画线算法假如yk处的像素更接近于线段，那么参数pk是负的，此时绘制较低像素。反之，绘制较高像素。Pk为画线算法中的第k步的决策参数。Pk的符号和d1-d2的符号相同。计算机图形学19Bresenham画线算法每一个单位步长都会引起直线x和y方向的坐标变化。因此可以利用递增函数运算得到后续的决策参数值。在k+1步，决策参数可从方程3-12中得到。减去方程3-12，得到但是xk+1=xk+1,所以其中yk+1-yk

取0或1，取决于参数pk的符号（pk为负，yk+1-yk

取0

）。计算机图形学20Bresenham画线算法在每个整数x位置，从线段的坐标端点开始，反复进行决策参数的这种递归运算。起始像素位置（x0，y0）的第一个参数p0用m=Δy/Δx和方程3-12计算得出。常量2Δy和2Δy-2Δx对每条进行扫描转换的直线只计算一次，因此系统仅进行着两个常量间的整数加减法。计算机图形学21Bresenham|m|<1时的画线算法计算机图形学22例子3-1Bresenham画线算法端点:(20,10)和(30,18)斜率:0.8Δx=10,Δy=8P0=2Δy-Δx=62Δy=16,2Δy-2Δx=-4初始点(x0,y0)=(20,10)计算机图形学23例子3-1Bresenham画线算法计算机图形学24并行画线算法利用并行计算机，可通过将计算分割到可用的多个处理器中来得到线段的像素位置。一种解决方法是将现有的顺序算法放到多个处理器上。可以寻找其他处理方法，从而使像素位置能以并行方式有效地计算。在算法中，一个很重要的思想是平衡各处理器间的处理负载。计算机图形学25并行画线算法

给定np个处理器，可以通过把线段分割成np个子线段，在每个子线段中同时生成线段并建立起并行Bresenham画线算法。对于斜率为0<m<1，且左端点坐标位置为（x0，y0）的线段，我们沿正x方向对线段进行分割。相邻分段的起始x位置间的距离可计算为：计算机图形学26并行画线算法建立光栅系统并行算法的另一种方法是为每个处理器分配一组屏幕像素。只要具有足够数目的处理器，就可以将每个处理器分配给某个屏幕区域内的一个像素。这种方法可以通过为一个处理器分配线段的坐标范围之内的一个像素，并计算像素距离线段之间的距离而移植成线段显示方法。在线段的边界框中的像素数目为Δx*Δy。在图3.10中，从线段到坐标（x，y）处像素的垂直距离d，可利用下列算式得到：计算机图形学27并行画线算法如果d小于指定线段的粗细参数，就绘制一个像素。计算机图形学28并行画线算法除了把屏幕分割成单个像素，也可以按线段的斜率为每个处理器分配一条扫描线或一列像素。然后，每个处理器计算线段与分配给该处理器的水平行或垂直列的交点。对于斜率|m|<1的线段，每个处理器将简单地按给定的x值从直线方程中求解y。对于斜率值大于1的线段，处理器则根据给定的扫描线y值，从直线方程中求解x。尽管这种直接方法在顺序算法机器中的计算速度很慢，但使用多处理器能十分有效地完成这一算法。

计算机图形学293-5圆生成算法圆的特性中点圆算法计算机图形学30圆的特点圆定义为所有到中心位置(xc,yc)距离为给定值r的点集。圆的方程为计算机图形学31圆的特性圆的极坐标方程为：已知x值，则y值为：为何会稀疏？计算机图形学32圆的特性考虑圆的对称性后可简化圆的计算。计算机图形学33中点圆算法如同光栅画线算法，以单位间隔取样并在每个步长中确定离指定圆最近的像素位置。对于给定半径r和圆心（xc，yc），可以先使用算法计算圆心在坐标原点（0，0）的圆的像素位置，然后通过将xc加到x和yc加到y，从而把计算出的每个位置（x，y）移动到其适当的屏幕位置。在第一象限中，圆弧段从x=0到x=y，曲线的斜率从0变化到-1。因此，可以在该八分圆上的正x方向取单位步长，并使用决策参数来确定每一步两个可能的y位置中，哪一个更接近于圆的位置。然后，其他七个八分圆中的位置可由对称性得到。计算机图形学34中点圆算法圆的方程如下：任何点（x，y）的相对位置可由对圆函数的检测来实现。计算机图形学35中点圆算法假定圆上一点(xk，yk)，下一像素可能是(xk+1，yk)或(xk+1，yk-1)。决策参数是：如果pk<0，中心点位于圆内。扫描线yk

更接近于圆周边界。否则，中心点位于圆外或圆上。扫描线yk-1更接近于圆周边界。计算机图形学36中点圆算法后续的决策参数为：yk+1

是yk

或yk-1，取决于pk的符号。计算机图形学37中点圆算法得到pk+1

的增量为：

2xk+1+1(如果pk<0)或2xk+1+1-2yk+12xk+1和2yk+1

的求值为：

2xk+1=2xk+22yk+1=2yk–2在起始位置(0,r)，这两个项的值分别为0和2r。所以：2x1=2x0+2=2和2y1=2y0-2=2r-2。计算机图形学38中点圆算法对于第一个点(x0,y0)=(0,r)，初始决策参数是：假如r指定为整数：计算机图形学39中点圆算法计算机图形学40例3-2中点圆算法计算机图形学41例3-2中点圆算法圆心坐标(0，0),半径为：8计算机图形学42计算机图形学43圆心坐标(0，0),半径为：8初始点(0,8)，初始点的对称点(0,8),(0,-8),(0,-8),(8,0),(-8,0),(8,0),(-8,0)-------------------------------------------------------------------------kPk(Xk+1,Yk+1)2Xk+12Yk+1对称点-------------------------------------------------------------------------0-7(1,8)216(-1,8),(1,-8),(-1,-8),(8,1),(-8,1),(8,-1),(-8,-1)1-4(2,8)416(-2,8),(2,-8),(-2,-8),(8,2),(-8,2),(8,-2),(-8,-2)21(3,7)614(-3,7),(3,-7),(-3,-7),(7,3),(-7,3),(7,-3),(-7,-3)3-6(4,7)814(-4,7),(4,-7),(-4,-7),(7,4),(-7,4),(7,-4),(-7,-4)43(5,6)1012(-5,6),(5,-6),(-5,-6),(6,5),(-6,5),(6,-5),(-6,-5)52(6,5)1210(-6,5),(6,-5),(-6,-5),(5,6),(-5,6),(5,-6),(-5,-6)圆心坐标(100，100),半径为：20计算机图形学44圆心坐标(100，100),半径为：20初始点(100,120)，初始点的对称点(100,120),(100,80),(100,80),(120,100),(80,100),(120,100),(80,100)-------------------------------------------------------------------------kPk(Xk+1,Yk+1)2Xk+12Yk+1对称点-------------------------------------------------------------------------0-19(101,120)240(99,120),(101,80),(99,80),(120,101),(80,101),(120,99),(80,99)1-16(102,120)440(98,120),(102,80),(98,80),(120,102),(80,102),(120,98),(80,98)2-11(103,120)640(97,120),(103,80),(97,80),(120,103),(80,103),(120,97),(80,97)3-4(104,120)840(96,120),(104,80),(96,80),(120,104),(80,104),(120,96),(80,96)45(105,119)1038(95,119),(105,81),(95,81),(119,105),(81,105),(119,95),(81,95)5-22(106,119)1238(94,119),(106,81),(94,81),(119,106),(81,106),(119,94),(81,94)6-9(107,119)1438(93,119),(107,81),(93,81),(119,107),(81,107),(119,93),(81,93)76(108,118)1636(92,118),(108,82),(92,82),(118,108),(82,108),(118,92),(82,92)8-13(109,118)1836(91,118),(109,82),(91,82),(118,109),(82,109),(118,91),(82,91)96(110,117)2034(90,117),(110,83),(90,83),(117,110),(83,110),(117,90),(83,90)10-7(111,117)2234(89,117),(111,83),(89,83),(117,111),(83,111),(117,89),(83,89)1116(112,116)2432(88,116),(112,84),(88,84),(116,112),(84,112),(116,88),(84,88)129(113,115)2630(87,115),(113,85),(87,85),(115,113),(85,113),(115,87),(85,87)136(114,114)2828(86,114),(114,86),(86,86),(114,114),(86,114),(114,86),(86,86)计算机图形学45计算机图形学463-6椭圆生成算法椭圆特征中点椭圆算法计算机图形学47椭圆的特征椭圆定义为到两个定点（焦点）的距离之和等于常数的点的集合（图3.17）。计算机图形学48椭圆的特征假如椭圆上的任意点P=(x,y)到两个焦点的距离为d1和d2，那么椭圆的通用方程可以表示为：用焦点坐标F1=(x1,y1)和F2=(x2,y2)来表示d1和d2,得到：计算机图形学49椭圆的特征椭圆方程的一般形式如下：其中，系数A、B、C、D、E、F依据焦点坐标和长轴及短轴的尺寸而求值得到。长轴是从椭圆的一侧通过焦点延伸到另一侧的线段。短轴是横跨椭圆的较短尺寸，它在两个焦点之间中点位置（椭圆中心）将长轴二等分。

计算机图形学50椭圆的特征图3.18中的椭圆方程，可以借助于椭圆中心坐标和参数rx和ry，改写成：利用极坐标，也可以按照参数方程的形式来描述标准位置的椭圆：

计算机图形学51椭圆的特性考虑椭圆的对称性可以减少计算量。计算机图形学52中点椭圆算法中点椭圆算法将分成两部分应用于第一象限。图3.20中示例了依据椭圆斜率（rx<ry

）对第一象限进行划分：斜率绝对值小于1的区域内在x方向取单位步长（区域1）；斜率绝对值大于等于1的区域内在y方向取单位步长（区域2）。计算机图形学53中点椭圆算法从方程3-35且(xc,yc)=(0,0)，定义椭圆方程：该函数特征如下:

因此，椭圆函数fellipse(x,y)作为中点算法的决策参数。在每个取样位置，根据椭圆函数沿椭圆轨迹对两个候选像素间中点求值的符号，来选择下一个像素。

计算机图形学54中点椭圆算法从（0,ry）开始，在x方向取单位步长，从而移动到区域1和区域2之间的边界（图3.20）；然后转换成y方向的单位步长，再通过第一象限中剩余的曲线段。在每一步中，需要检测曲线的斜率值。

椭圆的斜率可从方程（3.37）中计算得出：

计算机图形学55中点椭圆算法在区域1和区域2的交界上

,dy/dx=-1而且因此，移出区域1的条件是：

计算机图形学56中点椭圆算法图3.21示例了区域1内取样位置xk

＋1处两个候选像素间的中点。假如在前一步中选择了位置(xk,yk)

，便可通过该中点对决策参数（即椭圆函数（3.37））求值来确定沿椭圆轨迹的下一个位置：

假如p1k<0，那么中点位于椭圆内，扫描线yk上的像素更接近于椭圆边界。否则，中点在椭圆之外或在椭圆边界上，所选的像素应在扫描线yk-1

。计算机图形学57中点椭圆算法在下一个取样位置(xk+1+1=xk+2)（区域1）的决策参数可求值为：yk+1

是yk

或yk-1，取决于p1k的符号。

计算机图形学58中点椭圆算法决策参数以下列增量递增:

如同画圆算法，决策参数的增量计算仅需使用加减运算，因2ry2x和2rx2y的值也可以通过递增得到。计算机图形学59中点椭圆算法在起始位置(0,ry)，这两项值可计算为当x和y递增时，通过将等式（3.43）加上2ry2以及将等式（3.44）减去2rx2对每一步的更新值进行比较，当满足条件（3.40）时，就从区域1移向区域2。计算机图形学60中点椭圆算法在区域1中，决策参数的初始值可以通过椭圆函数在起始点（x0，y0）=（0，ry）求值而得：

计算机图形学61中点椭圆算法在区域2中，在负y方向以单位步长取样。对于该区域，决策参数将求值为：如果p2k>0，中心点位于椭圆之外，选择的像素位置在xk处。如果p2k<=0，中心点位于椭圆的内或边界上，我们选择像素xk+1。计算机图形学62中点椭圆算法为了确定区域2中后续决策参数间的关系，我们在下一取样步骤yk+1-1=yk-2对椭圆函数求值:

其中xk+1

是xk

或xk+1，取决于p2k的符号。计算机图形学63中点椭圆算法为了简化p20的计算,以逆时针方向从(rx,0)开始选择像素位置。然后以正y方向取单位步长，直到区域1中选择的最后位置。当进入区域2时，起初始点(x0,y0)就是区域1中选择的最后位置，那么区域2的初始决策参数为：计算机图形学64中点椭圆算法计算机图形学65中点椭圆算法计算机图形学66中点椭圆算法给定输入椭圆参数rx=8和ry=6

，我们将给出中点椭圆算法的步骤，从而确定第一像限内椭圆轨迹上的光栅像素位置。决策参数的初始值和增量计算为：

计算机图形学67中点椭圆算法对于区域1：椭圆心在原点的椭圆的初始点为（x0,y0）=（0,6），决策参数的初始值为：

使用中点算法计算后续的决策参数值和椭圆轨迹位置：

计算机图形学68中点椭圆算法对于区域2：初始点为(x0,y0)=(7,3)，决策参数为（错误的）：第一象限中椭圆轨迹的其余位置计算为(错误的)：

计算机图形学69中点椭圆算法对于区域2：初始点为(x0,y0)=(7,3)---------------------------------区域2-------------------------------------------kP2k(Xk+1,Yk+1)

2Ry*Ry*Xk+1

2Rx*Rx*Yk+1

对称点------------------------------------------------------------------------------------0-23(8,2)576256(-8,2),(8,-2),(-8,-2)1361(8,1)576128(-8,1),(8,-1),(-8,-1)2297(8,0)5760(-8,0),(8,0),(-8,0)计算机图形学70中点椭圆算法第一象限内沿椭圆边界所选择的位置请参见图3.23。

中心坐标(0，0),横半轴：20，纵半轴：10中心坐标(0，0),横半轴：20，纵半轴：10初始点(0,10),初始点的对称点(0,10)(0,-10)(0,-10)------------------------------区域1-------------------------------------------------kP1k(Xk+1,Yk+1)2Ry*Ry*Xk+12Rx*Rx*Yk+1对称点------------------------------------------------------------------------------------0-3800(1,10)2008000(-1,10),(1,-10),(-1,-10)1-3500(2,10)4008000(-2,10),(2,-10),(-2,-10)2-3000(3,10)6008000(-3,10),(3,-10),(-3,-10)3-2300(4,10)8008000(-4,10),(4,-10),(-4,-10)4-1400(5,10)10008000(-5,10),(5,-10),(-5,-10)5-300(6,10)12008000(-6,10),(6,-10),(-6,-10)61000(7,9)14007200(-7,9),(7,-9),(-7,-9)7-4700(8,9)16007200(-8,9),(8,-9),(-8,-9)8-3000(9,9)18007200(-9,9),(9,-9),(-9,-9)9-1100(10,9)20007200(-10,9),(10,-9),(-10,-9)101000(11,8)22006400(-11,8),(11,-8),(-11,-8)11-3100(12,8)24006400(-12,8),(12,-8),(-12,-8)12-600(13,8)26006400(-13,8),(13,-8),(-13,-8)132100(14,7)28005600(-14,7),(14,-7),(-14,-7)14-600(15,7)30005600(-15,7),(15,-7),(-15,-7)152500(16,6)32004800(-16,6),(16,-6),(-16,-6)161000(17,5)34004000(-17,5),(17,-5),(-17,-5)17500(18,4)36003200(-18,4),(18,-4),(-18,-4)中心坐标(0，0),横半轴：20，纵半轴：10初始点(0,10),初始点的对称点(0,10)(0,-10)(0,-10)------------------------------区域2-------------------------------------------------kP2k(Xk+1,Yk+1)2Ry*Ry*Xk+12Rx*Rx*Yk+1对称点------------------------------------------------------------------------------------0-2175(19,3)38002400(-19,3),(19,-3),(-19,-3)1-375(20,2)40001600(-20,2),(20,-2),(-20,-2)22425(20,1)4000800(-20,1),(20,-1),(-20,-1)32025(20,0)40000(-20,0),(20,0),(-20,0)中心坐标(-100，150),横半轴：16，纵半轴：10中心坐标(-100，150),横半轴：16，纵半轴：10初始点(-100,160),初始点的对称点(-100,160)(-100,140)(-100,140)------------------------------区域1-------------------------------------------------kP1k(Xk+1,Yk+1)2Ry*Ry*Xk+12Rx*Rx*Yk+1对称点------------------------------------------------------------------------------------0-2396(-99,160)2005120(-101,160),(-99,140),(-101,140)1-2096(-98,160)4005120(-102,160),(-98,140),(-102,140)2-1596(-97,160)6005120(-103,160),(-97,140),(-103,140)3-896(-96,160)8005120(-104,160),(-96,140),(-104,140)44(-95,159)10004608(-105,159),(-95,141),(-105,141)5-3504(-94,159)12004608(-106,159),(-94,141),(-106,141)6-2204(-93,159)14004608(-107,159),(-93,141),(-107,141)7-704(-92,159)16004608(-108,159),(-92,141),(-108,141)8996(-91,158)18004096(-109,158),(-91,142),(-109,142)9-1200(-90,158)20004096(-110,158),(-90,142),(-110,142)10900(-89,157)22003584(-111,157),(-89,143),(-111,143)11-384(-88,157)24003584(-112,157),(-88,143),(-112,143)122116(-87,156)26003072(-113,156),(-87,144),(-113,144)131744(-86,155)28002560(-114,155),(-86,145),(-114,145)中心坐标(-100，150),横半轴：16，纵半轴：10初始点(-100,160),初始点的对称点(-100,160)(-100,140)(-100,140)

------------------------------区域2-------------------------------------------------kP2k(Xk+1,Yk+1)2Ry*Ry*Xk+12Rx*Rx*Yk+1对称点------------------------------------------------------------------------------------0-479(-85,154)30002048(-115,154),(-85,146),(-115,146)1729(-85,153)30001536(-115,153),(-85,147),(-115,147)2-551(-84,152)32001024(-116,152),(-84,148),(-116,148)31881(-84,151)3200512(-116,151),(-84,149),(-116,149)41625(-84,150)32000(-116,150),(-84,150),(-116,150)计算机图形学773-7其他曲线圆锥曲线多项式和样条曲线计算机图形学78圆锥曲线通常，我们可以使用二次方程来描述圆锥曲线：

计算机图形学79圆锥曲线其中，参数A、B、C、D、E和F的值决定所要显示的曲线类型。判别式B*B-4AC求值来确定要生成的特殊圆锥曲线：计算机图形学80圆锥曲线椭圆、双曲线和抛物线在某些动画应用中有独特的用处。这些曲线可以描述受到地球引力、电磁场和原子力作用的物体的运行轨道和其他运动。例如：太阳系的平面轨迹是椭圆，进入均匀地球引力场的物体沿抛物线轨迹运动。对于负y方向作用的引力场，图3.24示例了标准位置上的抛物线轨迹。显示物体的抛物线轨迹方程可以写为：（常数a和b由物体的初始速度和均匀引力引起的加速度g决定。）计算机图形学81圆锥曲线也可利用以秒计量的时间参数，根据初始发射点的参数方程来描述这种抛物线轨迹：计算机图形学82圆锥曲线双曲线运动（图3.25）发生在有关带电粒子碰撞的问题以及某些引力问题中。例如，彗星或陨星绕太阳的运动是沿双曲线轨迹，并且向外层空间逃逸而从不返回。描述物体运动的特定分支（图3.25中的左边或右边曲线）取决于问题中涉及的力。可以将图3.25中双曲线（中心位于原点）的标准方程写为：计算机图形学83圆锥曲线抛物线和双曲线具有对称性。公式3-53中的抛物线的对称轴为：计算机图形学84多项式和样条曲线x的n次多项式函数可以定义为：其中，n为非负整数，ak是常数且an‡0，当n=2时得到二次曲线，n=3时为三次曲线，n=4时为四次曲线，等等；当n=1时得到直线。多项式用于许多图形应用中，包括物体形状设计、动画轨迹的确定以及在离散数据点集合中数据趋势的图形化等。计算机图形学85多项式和样条曲线样条曲线是有一系列连续的曲线（多项式曲线段）组成的。每个曲线段描述为:计算机图形学86多项式和样条曲线其中，参数u在0和1之间变化。参数方程中u的系数值根据曲线段的边界条件确定。边界条件之一是两个相邻曲线段具有公共端点，另一个条件是在边界上匹配两条曲线的斜率，以便得到连续的平滑曲线（图3.26）。利用多项式曲线段形成的这种连续曲线称为样条曲线，简称样条。计算机图形学873-8并行曲线算法既可采用顺序算法按曲线分段分配处理器，也可以提出其他方法将处理器分配给屏幕的不同区域。可以简单地使用扫描线分段方法。计算机图形学883-9曲线函数在许多图形软件包中一般都包括圆、样条和其他常用曲线的生成程序，PHIGS标准中不提供这些曲线的显式函数，但其包含下列通用曲线函数。generalizedDrawingPrimitive(n,wcPoints,id,datalist)其中，wcPoints是n个坐标位置的列表，而datalist包含非坐标数据值，参数id用来选择所希望的功能。在某些设置中，id=1表示引用圆，id＝2则表示引用椭圆，等等。

计算机图形学893-9曲线函数生成圆和椭圆的函数可以通过指定端点的参数来绘制曲线段。扩充的参数表允许指定圆弧的起始角度和终止角度，如图3.27所示。设计圆弧或椭圆弧的另一种方法是输入弧的起始和终止坐标位置。计算机图形学903-10像素编址和物体集合表示屏幕网格坐标保留显示的物体的几何特性计算机图形学91屏幕网格坐标根据像素中心定址显示位置的一种替换方法是参考屏幕网格坐标（图3.28），坐标中的网格由相距为单位长的水平和垂直像素边界线组成。

计算机图形学92屏幕网格坐标假如坐标原点位于屏幕左下方，那么每个像素区域就可由左下角的整数网格坐标来指定。

计算机图形学93保留显示的物体的几何特性假如使用像素的中心位置编址，那么可以通过去除端点中的一个来调整线段显示的长度。假如把屏幕坐标差作为编址的像素边界，那么仅用线路径内部的像素，即通过线段两端点间的像素来绘制直线。计算机图形学94保留显示的物体的几何特性对于封闭区域，只要仅显示在物体边界内的像素就能保持输入的几何特性。计算机图形学95保留显示的物体的几何特性这种沿物体边界的有限像素宽度的补偿能应用于其他多边形和曲线图形，从而使光栅显示保持输入物体的要求。

计算机图形学96保留显示的物体的几何特性计算机图形学973-11填充区域图元在光栅系统中有两种基本的区域填充方法：一种是通过确定横跨区域的扫描线的覆盖间隔进行填充（应用于多边形、圆等）；另一种是从给定的位置开始涂描直到指定的边界条件为止（应用于具有复杂形状边界的以及交互式涂描系统中）。

计算机图形学983-11填充区域图元扫描线多边形填充算法内外测试曲线边界区域的扫描线填充边界填充算法泛滥填充算法计算机图形学99扫描线多边形填充算法图3.35示例了多边形区域的实心填充的扫描线步骤：对于每条横跨多边形的扫描线，区域填充算法确定扫描线与多边形的交点位置。将这些点自左至右存储，并给每对交点间对应的帧缓冲器位置设置指定的填充颜色。计算机图形学100扫描线多边形填充算法特殊处理有些在多边形顶点处的扫描线交点需要特殊处理。在这些位置上，扫描线通过一个顶点与多边形的两条边相交，因此在这条扫描线的交点列表上要增加两个点。计算机图形学101扫描线多边形填充算法解决将顶点计为一个或两个交点的问题的一种方法是，将多边形的某些边缩短，从而分离那些应计为一个交点的顶点。计算机图形学102扫描线多边形填充算法在扫描转换及其他图形算法中完成的计算，经常利用待显示的场景的各种连贯特性。这里所指的连贯性，可以简单地看做是场景中的一部分的特性以某种方式与场景中的其他部分相关，这种关系可用来减少处理。连贯方法经常包括沿一条扫描线或在连续的扫描线间应用的增量计算。计算机图形学103扫描线多边形填充算法图3.38示例了与多边形右面一条边相交的两条连续扫描线，这个多边形边界线的斜率可以用扫描线交点坐标来表示：计算机图形学104扫描线多边形填充算法两条连续扫描线间y的变化：上面扫描线的x交点值xk+1可以从前一条扫描线上的x交点值xk来决定，每个后续的交点x值都可这样得出：计算机图形学105扫描线多边形填充算法为了有效地完成多边形填充，可以首先将多边形边界存储在有序边表（sortededgetable)中，其中包含有效处理扫描线所需的全部信息。无论是以顺时针或逆时针沿边处理时，可以使用桶排序存储各条边，按每条边的最小y值排序，存储在相应的扫描线位置。有序边表中仅存储非水平线。在处理边时，可以缩短某些边以解决顶点相交问题。对于某条特定的扫描线，表中的每个入口包含该边的最大y值、边的x交点值（在较低顶点处）和边斜率的倒数。对于每条扫描线，以从左到右的顺序对边进行排序。图3.39示例了一个多边形及其相应的有序边表。计算机图形学106扫描线多边形填充算法计算机图形学107内外测试区域填充算法和其他图形处理通常需要鉴别对象的内部区域。在基本的几何形体中，通常定义多边形为不自交的。标准多边形的例子有三角形、四边形、八角形和十角形。这些对象的组成边仅在顶点处连接，而在平面内没有其他公共点。鉴别标准多边形的内部区域通常是一个直观过程，但在大多数图形应用中，我们可以指定填充区域顶点的任何顺序，包括产生相交边的顺序，如图3.40所示。对于这样的形状，xy平面上哪个区域是“内部”以及哪个区域是对象的“外部”并非总是一目了然的。通常采用奇偶规则或非零环绕数规则来鉴别物体的内部区域。计算机图形学108内外测试计算机图形学109内外测试奇偶规则

从任何位置点P到对象坐标范围以外的远点画一条射线，统计沿该射线与各边的交点数目。如果交点数为奇数，P是内部点。如果交点数为偶数，P是外部点。计算机图形学110内外测试非零环绕数规则

该方法统计多边形边以逆时针方向环绕某一特定点的次数，这个数称为环绕数。将二维物体的内部点定义为具有非零值的环绕数。计算机图形学11