计算机图形学

1、计算机图形学,武汉大学电子信息学院 王泉德 ,第五章 图形生成和计算,一、 区域填充,一个区域是指一组相邻而又相连的象素，且具有同样的属性。区域的建立和定义通常可采用两种方式： 内定义区域（Interior-Defined）：区域内部所有象素具有同一种颜色或亮度值，而区域外的所有象素具有其他颜色或亮度值。 边界定义区域（Boundary-Defined）：区域边界上所有象素均具有特定的颜色或亮度值，而在区域内、外的象素则具有不同于边界值的颜色或亮度值。,给出一个区域的边界，要求对边界范围内的所有象素单元赋予指定的颜色代码称为区域填充。区域填充算法可分为两大类： 种子填充算法：假定封闭轮廓线内某

2、点是已知的，然后算法开始搜索与种子点相邻且位于轮廓线内的点。种子填充算法只适用于光栅扫描设备。 扫描转换填充算法：按扫描线的顺序确定某一点是否位于多边形或轮廓线范围之内。算法一般从轮廓线的顶部开始进行到它的底部。 区域填充的边界可以是直线也可以是曲线。,1：多边形区域的扫描转换 2：多边形区域的种子填充 3：光栅图形的反走样算法,1.多边形的扫描转换,1.1 扫描转换 计算机生成的物体常常可以用若干多边形来描述，有些非多边形的物体，也可以用多边形来逼近。在计算机图形学中，多边形有两种重要的表示方法：顶点表示和点阵表示。 顶点表示是用多边形的顶点序列来刻划多边形。这种方式直观，几何意义强，占用内

3、存少，但不能直接用于面着色。 点阵表示是用位于多边形内的象素的集合来刻划多边形。这种方法虽然失去了很多重要的几何信息，但便于运用帧缓冲器表示图形，是面着色所需要的图形表示形式。,顶点表示的多边形,P4,P0,P3,P2,P1,点阵表示的多边形,光栅图形的一个基本问题就是把多边形的顶点表示转换成为点阵表示，也就是从多边形的给定边界出发，求出位于其内部的各个象素，并给帧缓冲器内部的各个对应元素设置相应的灰度和颜色，通常这种转换称为“多边形的扫描转换”。 多边形的扫描转换过程，实际上就是给多边形包围的区域着色的过程，因此是一种面着色的方法。,扫描转换的常用算法,逐点判断算法 扫描线算法 边缘填充算法

4、 边界标志算法,1.2 逐点判断算法,思想：逐个象素判别，确定它们是否在多边形内部，从而给出位于多边形内的点（象素）的集合。 难点：如何确定一个点是否在多边形内部？,点是否在多边形内部的检验,为了对多边形内部的象素点赋值，首先要解决如何判断一个点是否在多边形内部。 判断的方法：先在多边形外部找一个点，然后用线段连接待判决点和待判决点，计算出此线段与多边形边界相交的次数，如果交点的数目为奇数，则待判决点在多边形内部；如果为偶数，待判决点在多边形外部。,1,1,3,2,2,3,P,4,图例,（1）怎样才能“在多边形外部找一个点”？ 确定多边形的包围矩形：即xmin,ymin,xmax,ymax，在

5、包围矩形外的点肯定是多边形的外部点； （2）交点计数的特殊情况处理,线段和多边形相交在顶点（奇点的处理）： 当线段与多边形P的交点是P的顶点Pi 时，则称该交点为奇点; 为了保证线段和多边形P边界的交点个数为偶数，现将奇点分为极值点和非极值点两类：如果相交的两条边位于线段同侧，则顶点Pi 为极值点，否则为非极值点; 当奇点是P的极值点时，该点按照两个交点计算；否则按照一个交点计算。,线段和多边形边共线：线段与多边形相交二次；,算法实现,现设P=P0P1PnP0为一给定的多边形。Framebuffer(x,y)是与点(x,y)相对应的帧缓冲器中的元素。则逐点判断的算法可以表示成为如下的程序： f

6、or y:= ymin to ymax do for x:= xmin to xmax do if inside(p, x, y) then setpixel(framebuffer, x, y, polygon-color) else setpixel(framebuffer, x, y, back-color);,逐点判断的算法虽然程序简单，但是不可取。原因是速度太慢，该算法割断了各个象素之间的联系，孤立的考察各个象素和多边形P的内外关系，使得几十万甚至几百万个象素都要一一判别，每次判别都要多次求交点，需要做大量的乘除运算，花费大量的时间。,1.3 扫描线算法,扫描线算法是多边形扫描转换的

7、常用方法。相比起逐点判断算法，扫描线算法充分利用了象素之间的连贯性，避免的对象素的逐点判断和反复求交的过程。 扫描线算法综合利用了区域的连贯性，扫描线连贯性和边的连贯性等三种形式的连贯性。,区域的连贯性,yk+1,yk,扫描线yk和yk+1将多边形P分割成若干的梯形，它们具有如下的性质：,梯形的两底边分别在y=yk和y=yk+1两条扫描线上，腰在多边形P的边上和显示屏幕的边界上； 这些梯形可以分为两类，一类在多边形P的内部，一类在多边形P的外部； 两类梯形在长方形区域yk , yk+1内相间的排列，即相邻的两个梯形必有一个在多边形P内，另一个在P外； 根据这些性质，实际上只要知道该长方形区域z

8、中任一梯形内一点关于多边形P的内外关系后，整个梯形内关于多边形P的内外关系就可以确定了。,扫描线的连贯性,扫描线yk和多边形P相交，交点为X1,X2,.XL，它们具有如下的性质：,L是偶数； 该扫描线上，区段(Xk, Xk+1),k=1,3,5位于多边形P内部，其余区段都在多边形P外。两类区段沿扫描线相间排列。,边的连贯性,设d为一整数，d=e-1。若多边形P的边Pr-1Pr与扫描线y=d和y=e都相交，和两交点的横坐标xe和xd满足下面的关系(mr为斜率)：,因此，可利用多边形与当前扫描线交点的位置及递推关系，求得多边形与下一条扫描线的交点的位置。以上性质称为边的连贯性，它是区域的连贯性在两

9、条相邻扫描线上的体现。,扫描线和多边形相交在顶点（奇点的处理）： 当扫描线与多边形P的交点是P的顶点Pi 时，则称该交点为奇点; 为了保证扫描线和多边形P边界的交点个数为偶数，现将奇点分为极值点和非极值点两类：如果相交的两条边位于扫描线同侧，即： (yi+1-yi)*(yi-1-yi)0 则顶点Pi 为极值点，否则为非极值点; 当奇点是P的极值点时，该点按照两个交点计算；否则按照一个交点计算。,扫描线和多边形边共线：线段与多边形相交二次；,扫描线算法的实现,算法的基本思想： 利用多边形的边的连贯性和扫描线的连贯性，对于一个给定的多边形，用一组水平(垂直)的扫描线进行扫描 对每一条扫描线均可求出

10、与多边形边的交点 交点将扫描线分割成落在多边形内部的线段和落在多边形外部的线段，并且二者相间排列 将落在多边形内部的线段上的所有象素点赋以给定的色彩值。,扫描线算法的实现原理,根据多边形内部点的连续性知：一条扫描线与多边形的交点中，入点和出点之间所有点都是多边形的内部点。所以，对所有的扫描线填充入点到出点之间所有的点就可填充多边形。 判断扫描线上的点是否在多边形之内根据多边形区域连续性，分为3个步骤： 求出扫描线与多边形所有边的交点； 把这些交点的x坐标值以升序排列； 从奇数交点出发到偶数交点的扫描 线段位于多边形内部。 如右图，排序x坐标得到的交点序列是 (2,4,9,13)，然后对交点2与

11、4之间、9与13之间的所有象素点进行填充。,扫描线算法的实现原理奇点的处理,p1,p3,p4,p5属于局部极值点，要把他们两次存入交点表中。 如扫描线y=7上的交点中，有交点(2,7,13)，按常规方法填充不正确，而要把顶点(7,7)两次存入交点表中(2,7,7,13)。p2，p6为非极值点，则不用如上处理。,p1,p2,p3,p4,p5,p6,p1,p2,p3,p4,p5,p6,扫描线算法的实现步骤,对于一条扫描线填充过程可以分为四个步骤： 求交 排序 配对 填色,扫描线算法的数据结构,边的活化链表(AET)：把与当前扫描线相交的边称为活性边，并把它们按与扫描线交点x坐标递增的顺序存放在一个

12、链表中，结点内容 x：当前扫描线与边的交点坐标 x：从当前扫描线到下一条扫描线间x的增量(边斜率的倒数) ymax：该边所交的最高扫描线号ymax,边的分类表(ET)：存放在该扫描线第一次出现的边。若某边的较低端点为ymin，则该边就放在扫描线ymin的新边表中。,x：边的下端点的x坐标； x：从当前扫描线到下一条扫描线间x的增量 ymax：该边所交的最高扫描线号ymax,扫描线算法描述,建立ET表，置y为ET表中非空的最小y坐标值 置AEL表为空，且按照y值将ET表的边加入AEL表中 while AEL表非空并且ET表中非空 dobegin 对AEL表中的xmin值按升序排列 按照AEL表中

13、交点前后次序，在每对奇偶交点间的x段予以填充 if 扫描线 y=ymaxthen 从AEL表中删除这些边 对在AEL表中的其他边，计算与下一条扫描线的交点：x=x+1/m 计算下一条扫描线：y=y+1 按照扫描线y值把ET表中相应的边加入AEL表中end end of algorithm,扫描线算法性能分析,扫描线算法的数据结构和程序结构都远比逐点判断算法复杂，对各种表的维护和排序的耗费很大； 但是由于它充分利用的多边形的区域、扫描线和边的三种形式的连贯性，从而避免了反复求交点的大量运算，因此速度比逐点判断法快的多。,1.4 边缘填充算法,基本思想： 在光栅图形中，如果某区域已经着上了为M的某

14、种颜色，则对M做偶数次求补运算后，该区域的颜色不变；而做奇数次求补运算后，该区域则变为 的颜色。因此，边缘填充算法对于每一条扫描线与多边形边的交点(x,y)，依次将交点右方的所有象素取补，从而实现对多边形的填充。,算法实现,步骤1：将位于扫描线y=e上的所有象素都着上值为M的颜色； for x:= xmin to xmax do setpixel(framebuffer, x, e, M); 步骤2：对每一个交点xi,依次向右求补； for i:= 1 to m do for x:= xi to xmax do complement(framebuffer, x, e) 当完成上述两个步骤后，

15、扫描线y=e上位于多边形内部的象素进行了奇数次求补运算，并着上了 的颜色。,改进：,对于复杂的图形，一些象素可能被访问多次，一种改进的办法是引入栅栏。通过多边形设一栅栏，每次只对交点与栅栏之间的象素点取补，可使访问象素的次数减少。下图示出了这一算法的原理。,边缘填充算法性能分析,边缘填充算法的数据结构和程序结构都比扫描线算法简单的多。因为边缘填充算法用求补代替了排序，因此在算法执行时需要对帧缓冲器中的大批元素反复的赋值，因此速度不比扫描线算法快。,1.5 边界标志算法,算法思想： 先用一种特殊的颜色将多边形的边界勾画出来，然后在采用和扫描线算法相类似的方法将位于多边形内的各个区段着上所需要的颜

16、色。,边界标志算法实现步骤,步骤1：以值为boundary-color的特殊颜色勾画多边形P的边界。可采用相应的直线生成算法； 步骤2：逐条扫描线对多边形着色。先将扫描线上值为boundary-color的特殊象素点依x坐标递增顺序两两配对，再将中间的象素着上相应的颜色；,边界标志算法类语言描述,For y:= ymin to ymax do Begin interior-point := false; for x:= xmin to xmax do begin if getpixel(framebuffer,x,y) = boundary-color then interior-point

17、= not interior-point; if interior-point then setpixel(framebuffer,x,y,polygon-color) else setpixel(framebuffer,x,y,background-color); end end,边界标志算法性能分析,和边界填充算法相比，本算法避免了对帧缓冲器中的大量元素的多次赋值，但是需要逐条扫描线的对帧缓冲器中的元素进行搜索和比较。当用软件实现本算法时，速度与扫描线算法相当。本算法适合于硬件实现，硬件实现时的速度则有很大的提高。,2. 多边形的种子填充,种子填充是指先将区域内的一点(称为种子点)赋予给定

18、的颜色，然后将这种颜色扩展到整个区域内的过程。 这里所指的区域是已经表示成为点阵形式的象素集合。,2.1 4连通区域和8连通区域,取区域内任意两点，若从其中一点出发通过上、下、左、右四中运动，只经过该区域内的点可到达另一点时，则称该区域为4连通区域； 若将运动方式增加为水平方向、垂直方向和对角线方向的八种运动，仍满足上述的要求，则该区域为8连通区域；,2.2种子填充的递归算法,4连通区域种子填充的递归实现：,procedure flood-fill-4(x,y) begin if getpixel(framebuffer,x,y) = old-color then begin setpixel

19、(framebuffer,x,y,new-color); flood-fill-4(x,y+1); flood-fill-4(x,y-1); flood-fill-4(x-1,y); flood-fill-4(x+1,y); end end of algorithm;,4连通种子填充的递归过程：,递归种子填充算法的性能分析,区域填充的递归算法程序简单，表达清楚。但由于多层递归，系统堆栈反复进出，费时费内存。,上述填充算法是一种深度优先搜索算法，采用堆栈实现。也可以改为广度优先搜索，采用队列实现。,2.3扫描线种子填充算法,基本思想： 首先填充当前扫描线上的位于给定区域内的一段区段，然后确定与这

20、一区段相邻的上下两条扫描线上位于区域内的区段，并依次将它们保存起来。反复进行这个过程，直到所保存的各区段都填充完毕为止。,28,21,12,27,26,20,19,11,25,18,24,23,17,16,8,3,35,7,2,34,37,39,36,38,41,43,45,40,42,44,22,15,14,10,5,13,9,6,30,29,1,33,32,4,31,扫描线种子填充算法举例,保存上下扫描线区段最右侧象素为种子象素,区域填充的扫描线算法描述,将种子象素点压入堆栈 while 堆栈非空 do begin 从堆栈中弹出一个种子象素 沿着扫描线对种子象素的左右象素进行填充，直至遇到

21、边界 象素为止 标志区间内最左和最右象素为xleft 和xright if在xleftxxright中检查与当前扫描线相邻的上下两条扫描线全为边界象素或全为已填充过的象素 then goto 2 在xleftxxright中标记每一个既不包含边界象素又不包含已填充过的象素的区间 将每一区间的最右象素作为种子象素压入堆栈end end of algorithm,2.4 扫描转换和区域填充的比较,多边形的扫描转换和区域填充是两类典型的面着色问题，在一定条件下两者可以相互转换。但二者的基本思想是不同的。 多边形的扫描转换是指将多边形的顶点表示转换成点阵表示，在扫描转换过程中利用了多边形各种形式的连贯

22、性； 区域填充只改变区域的颜色，不改变区域的表示方法。在填充过程中应用了区域的连通性。,3. 光栅图形的反走样算法,光栅图形的走样现象 光栅图形的走样(aliasing)是由于采用离散的量来表示连续的量而引起的。线段，多边形的边界都是连续量，而光栅图形的象素是离散量。因此，用离散的象素表示连续的线段时导致光栅图形走样，即光滑的线段变成了阶梯的形状。用于减少或消除这种效果的技术称为反走样(antialiasing)。,3.1 反走样线段和反走样多边形,基本思想： 现实中的线段是有宽度的，应把线段看作是狭长的矩形； 当线段通过某象素时，可求出两者相交的面积； 最后根据相交的面积大小决定该象素的颜色

23、或灰度值；,3.2 提高分辨率的反走样方法,采用高分辨率的光栅图形显示器； 用软件的方法提高分辨率，采用高分辨率计算，低分辨率显示的技术： 高分辨率计算指将低分辨的图形显示象素划分为许多子象素，如2*2划分，3*3划分等，然后按照通常的算法计算出各个子象素的颜色或灰度值； 低分辨率显示指将一个象素所对应的各个子象素的颜色值的加权平均值(或算术平均值)作为该象素的颜色值进行显示；,提高分辨率的反走样方法,把显示器分辨率提高一倍， 直线经过两倍的象素，锯齿也增加一倍， 但同时每个阶梯的宽度也减小了一倍， 所以显示出的直线段看起来就平直光滑了一些。 增加分辨率虽然简单，但是是不经济的方法，有物理上的

24、困难，而且它也只能减轻而不能消除锯齿问题,区域采样,每个象素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与象素有交时，求出两者相交区域的面积，然后根据相交区域面积的大小确定该象素的亮度值。,有宽度的线条轮廓,象素相交的五种情况及用于计算面积的量,情况（5)阴影面积为：D2/2m； 情况（4)阴影面积为：D - m/2； 情况阴影面积为：1 - D2/m,对圆等二次曲线的区域采样可以采取适当的近似，并建立查找表来减小计算复杂度,二、字符的生成,计算机图形学中，字符可以用不同的方式表达和生成。常用的方法有点阵式、矢量式和编码式。 1、点阵式字符 点阵式字符将字符表示为一

25、个矩形点阵，由点阵中点的不同值表达字符的形状。常用的点阵大小有57、7 9、88、1616等等。下图所示的字母“P”的点阵式表示例子。在这种88网格中的字形比较粗糙，但当点阵变大时，字型可以做得非常漂亮。,使用点阵式字符时，需将字库中的矩形点阵拷贝到buffer中指定的单元中去。在拷贝过程中，可以施加变换，以获得简单的变化。 图（b）变成粗体字：当字符原型中每个象素被写入帧缓存寄存器的指定位置xi, yi时，同时被写入xi+1, yi。 图（c）旋转90度 ：把字符原型中每个象素的x, y坐标彼此交换，并使y值改变符号后，再写入帧缓存寄存器的指定位置。 图（d）斜体字：从底到顶逐行拷贝字符，每

26、隔n行，左移一单元。,由于光栅扫描显示器的普遍使用，点阵式字符表示已经成为一种字符表示的主要形式。从字库中读出原字型，经过变换拷贝到buffer中去的操作，经常制成专门的硬件来完成。这就大大加快了字符生成的速度。,2、矢量式字符 矢量式字符将字符表达为一个点坐标的序列，相邻两点表示一条矢量，字符的形状便由矢量序列刻划。图2.4.2示出用矢量式表示的字符“B”。“B”是由顶点序列a, b, c, d, e, f, e, g, h, I, j, k ,a, l的坐标表达。 调用矢量式字符的过程相当于输出一个polyline。由于矢量式字符具有和图形相一致的数据结构，因而可以接受任何对于图形的操作，

27、如放大、旋转，甚至透视。而且，矢量式字符不仅可用于显示，也可用于绘图机输出。,3、方向编码式字符 方向编码式字符用有限的若干种方向编码来表达一个字符，常用8方向编码。 8个方向的编码分别为07，其中编码为偶数和0的固定长度为1，编码为奇数的固定长度为 。 一个字符就可以表示为一连串方向码。下图为字母“B”的方向矢量构成。 “B”可用8方向编码：000012344400012344440666666来表示。,优点： 方向编码式字符很容易被填入帧缓存寄存器中予以显示； 方向编码所占的空间比较小； 能接受一些特定的变换操作，如按比例在x和y两个方向放大或缩小以及以45度角为单位的旋转，但难以进行任意

28、角度的旋转。,4、轮廓字型技术 当对输出字符的要求较高时（如排版印刷），需要使用高质量的点阵字符。 对于6763个基本汉字，假设每个汉字是72X72点阵，那么一个字库就需要72X72X6763/8=4.4兆字节存储空间； 在实际使用时，还需要多种字体（如基本体、宋体、仿宋体、黑体、楷体等），每种字体又需要多种字号。可见，直接使用点阵字符方法将耗费巨大的存储空间。,因此把每种字体、字号的字符都存储一个对应的点阵，在一般情况是不可行的。,解决方法： 对字型数据压缩后再存储，使用时，将压缩的数据还原为字符位图点阵。 压缩方法有多种 黑白段压缩法：简单，还原快，不失真，但压缩较差，使用起来也不方便，一

29、般用于低级的文字处理系统中； 部件压缩法：压缩比大，缺点是字型质量不能保证； 三是轮廓字型法：压缩比大，且能保证字符质量，是当今国际上最流行的一种方法，基本上也被认为是符合工业标准化的方法。,轮廓字型： 轮廓字型法采用直线、或者二、三次Bezier曲线的集合来描述一个字符的轮廓线； 轮廓线构成一个或若干个封闭的平面区域； 轮廓线定义加上一些指示横宽、竖宽、基点、基线等的控制信息，构成了字符的压缩数据。控制信息用于保证字符变倍时引起的字符笔划原来的横宽/竖宽变大变小时，其宽度在任何点阵情况下永远一致 采用适当的区域填充算法，可以从字符的轮廓线定义产生字符的位图点阵，区域填充算法可以用硬件实现，也

30、可以用软件实现。,由美国Apple和Microsoft公司联合开发的TrueType字型技术就是一种轮廓字型技术，已被用于为Windows中文版生成汉字字库； 当前占领主要的电子印刷市场的我国北大方正和华光电子印刷系统，用的字型技术是汉字字型轮廓矢量法。这种方法能够准确地把字符的信息描述下来，保证了还原的字符质量，又对字型数据进行了大量的压缩。调用字符时，可以任意地放大、缩小或进行花样变化，基本上能满足电子印刷中字型质量的要求； 轮廓字型技术有着广泛的应用。到目前为止在印刷行业中使用最多，随着Ms-Windows的大量使用，在CAD、图形学等领域也将变得越来越重要。,三、图形求交,在计算机图形

31、学中常常会遇到求交计算： 在进行扫描线区域填充时要求线段的交点 许多消隐算法需要进行直线和平面多边形的求交 求交运算往往比较复杂，为了减小计算量，在进行真正的求交计算之前，往往先用凸包等辅助结构进行粗略的比较，排除那些显然不相交的情形。 求交计算是CAD系统的重要部分。它的准确性与效率直接影响CAD系统的可靠性与实用性。,容差： 在数学上两个浮点数可以严格相等 计算机表示的浮点数有误差，所以当两个浮点数的差的绝对值充分小时（例如，小于某个正数 ），就认为它们相等 求交运算中引进容差。当两个点的坐标值充分接近时，即其距离充分近时，就被认为是重合的点 点可看作半径为 的球，线可看作半径为 的圆管，

32、面可看作厚度为2 的薄板 一般取 =10-6或更小的数。 求交问题可以分为求交点和求交线两类。,1、求交点算法,（1）直线段与直线段的交点 方法一： 假设二条直线的端点分别为P1，P2，Q1，Q2，则它们可以用向量形式表示为： P(t)=A+Bt (0 t 1) Q(s)=C+Ds (0 s 1) 其中，A=P1，B=P2-P1，C=Q1，D=Q2-Q1。 构造方程 A+Bt=C+Ds 对三维空间中的直线段来说，上述方程实际上是一个二元一次方程组，由三个方程式组成。可以从其中两个解出s, t，再用第三个验证解的有效性：若第三个方程成立则说明找到了解，否则说明两条直线不相交。当所得的解（ti,

33、si）是有效解时，可用二个线段方程之一计算交点坐标，例如P(ti)=A+Bti。,方法二： 根据向量的基本性质，直接计算s与t 。对方程A+Bt=C+Ds两边构造点积得： (C D) (A+Bt)=(C D) (C+Ds) 由于C D同时垂直于C和D，等式右边为零。故有： 类似地有： 此外还应判断无解与无穷多解（共线）的情形，以及考虑数值计算误差造成的影响。,（2）直线段与二次曲线的交点 不失一般性，考虑平面上一条直线与同平面的一条二次曲线的交。 设曲线方程为： f(x, y)=0, 直线段方程为： (x, y)=(x1+t(x2-x1), y1+t(y2-y1), 则在交点处有 f(x1+t

34、(x2-x1), y1+t(y2-y1)=0 当曲线为二次曲线时，上述方程可写为 at2+bt+c=0 用二次方程求根公式即可解出t值。,（3）圆锥曲线与圆锥曲线的交点 其中一条圆锥曲线用代数/几何法表示为隐函数形式 另一条表示为参数形式（如二次NURBS曲线） 将参数形式代入隐函数形式可得关于参数的四次方程，可以使用四次方程的求根公式解出交点参数 验证交点是否在有效的圆锥曲线段上。,（4）直线段与平面的交点 平面上的点表示为P(u, w)=A+uB+wC，直线段上的点表示为Q(t)=D+tE，二者的交点记为R。假设线段不平行于平面，则它们交于R=P(u, w)=Q(t)，即 A+uB+wC=

35、D+tE 等式两边点乘（B C），得 （B C）（A+uB+wC）=（B C）（D+tE）,由于B C既垂直于B，又垂直于C，故有 （B C）A=（B C）（D+tE） 可解出 类似求得 如果是直线与平面区域求交点，则要进一步判断点是否在平面上的有效区域中,（5）圆锥曲线与平面的交点 圆锥曲线与平面求交时，可以把圆锥曲线表示为参数形式，并把圆锥曲线的参数形式代入平面方程，即可得到参数的二次方程进行求解。 （6）圆锥曲线与二次曲面的交点 圆锥曲线与二次曲面求交时，可把圆锥曲线的参数形式代入二次曲面的隐式方程，得到参数的四次方程，用求根公式求解。,2、求交线算法,（1）平面与平面的交线 求平面上两

36、有界区域的交线 两个平面区域分别由P(u, w), Q(s, t), u, w, s, t0, 1定义。如果它们不共面而且不分离，则必交于一直线段。这条直线必落在P(u, w)-Q(s, t)=0所定义的无限直线上。 得到含有四个未知数，三个方程式的方程组，只要分别与八条边界线方程：u=0, u=1, w=0, w=1, s=0, s=1, t=0, t=1联立，即可求出线段的两个端点的参数。 只要找到两组解，就可以不再对剩余其它方程组求解。找到的两组解就是所求的交线段端点参数。,求平面上两多边形的交线： 两个多边形（可能是凸的，也可能是凹的，甚至可能带有内孔）相交时，可能有多段交线。 两个多

37、边形分别记为A和B，用如下的方法求出它们的交线： （1）把A的所有边与B求交，求出所有有效交点； （2）把B的所有边与A求交，求出所有有效交点； （3）把所有交点先按y，再按x的大小进行排序； （4）把每对交点的中点与A和B进行包含性检测，若该中点即在A中又在B中，则该对交点定义了一条交线段。,（2）平面与二次曲面的交线 1）代数法 把二次曲面表示为代数形式， Ax2+By2+Cz2+2Dxy+2Eyz+2Fxz+2Gx+2Hy+2Iz+J=0 通过平移与旋转坐标变换把平面变为XOY平面，对二次曲面进行同样的坐标变换 在新坐标系下平面的方程为z=0，所以新坐标系下二次曲面方程中，把含z项都去掉

38、即为平面与二次曲面的交线方程。对交线方程进行一次逆坐标变换即可获得在原坐标系下的交线方程。,交线表示法： 代数表示：用二元二次方程系数表示交线，辅之以局部坐标系到用户坐标系的变换矩阵。 缺点：每当需要使用这些交线时，都要进行坐标变换。例如，判断一个空间点是否在交线上，必须先对它进行坐标变换，变到z=0平面上，再进行检测。需要绘制该交线时，也要先在局部坐标系下求出点坐标，再变换到用户坐标系下的坐标 几何表示：几何表示存储曲线的类型（椭圆、抛物线或双曲线），以及定义参数（中心点、对称轴、半径等大小尺寸）的数值信息，使用局部坐标系到用户坐标系的变换，把局部坐标系下的定义参数变换到用户坐标系直接使用。

39、 特点：使用较少的变换，但需要用计算来判断曲线的种类，及计算曲线的定义参数。由于浮点运算的不精确性，容易发生判错类型以及定义参数误差过大的问题。,2）几何法 当平面与二次曲面的交线需要精确表示时，往往采用几何法求交。,特点： 准确性大大优于用代数法计算分类的方法 不需要对面进行变换，所以只要通过很少的计算就可以得到交线的精确描述 存储的信息是具有几何意义的，所以判断相等性、相对性等问题时，可以确定有几何意义的容差。,二次曲面采用几何表示 根据平面与二次曲面的相对位置与角度直接判断交线类型,例子：平面与球求交 平面用一个记录p表示，p的两子域p.b, p.w分别代表平面上一点与平面法向量。球面用

40、记录s表示。它的两个子域s.c, s.r分别代表球面中心和半径。则可写出平面与球面相交的算法如下：,plane_sphere_intersect(p, s) plane p; sphere s; d=球面中心到平面的有向距离； if(abs(d)=s.r) 二个面相交于一（切）点s.c-d * p.w; else if (abs(d)s.r) 两个面无交； else 所求交线是圆。其圆心，半径，圆所在平面法向量为 c=s.c-d * p. w; r=sqr t(s.r2-d2); w=p.w; ,一个平面与一个圆柱面可以无交、交于一条直线（切线）、二条直线、一个椭圆或一个圆，可以用两个面的定义

41、参数求出它们的相对位置关系和相对角度关系，进而判断其交属于何种情况，并求出交线的定义参数 平面与圆锥的交线也可类似求解。,（3）平面与参数曲面的交线 方法一： 把参数曲面的表示（x(s,t), y(s,t), z(s,t)）代入平面方程 ax+by+cz+d=0 得到用参数曲面的参数s、t表示的交线方程 ax(s,t)+by(s,t)+cz(s,t)+d=0 方法二： 是用平移和旋转变换对平面进行坐标变换，使平面成为新坐标系下的xoy平面。再用相同的变换应用于参数曲面方程得到参数曲面在新坐标系下的方程 （x*, y*, z*）=（x*(s,t), y*(s,t), z*(s,t)） 由此得交线

42、在新坐标系下的方程为 z*(s, t)=0,四、包含判定,在进行图形求交时，常常需要判定两个图形间是否有包含关系。如点是否包含在线段、平面区域、三维形体中，线段是否包含在平面区域、三维形体中，等等。 许多包含判定问题可转化为点的包含判定问题，如判断线段是否在平面上可以转化为判断其两端点是否在平面上。因此主要讨论关于点的包含判定算法。,判断点与线段的包含关系，也就是判断点与线的最短距离是否位于容差范围内。造型中常用的线段有三种： （1）直线段 （2）圆锥曲线段（主要是圆弧） （3）参数曲线（主要是Bezier，样条曲线）。 点与面的包含判定也类似地分为三种情况。,（1）点与直线段的包含判定 假设

43、点坐标为P(x, y, z)，直线段端点为P1(x1, y1, z1)，P2(x2,y2,z2)，则点P到线段P1P2的距离的平方为 d2=(x-x1)2+(y-y1)2+(z-z1)2-(x2-x1)(x-x1)+(y2-y1)(y-y1)+(z2-z1)(z-z1)2/(x2-x1)2+(y2-y1)2+(z2-z1)2 当d22时，判定点在线段（或其延长线）上，这时还需进一步判断点是否落在直线段的有效区间内 比较坐标分量，假设线段两端点的x分量不等（否则所有分量均相等，那么线段两端点重合，线段退化为一点），那么当x-x1与x-x2反号时，点P在线段的有效区间内。,（2）点与圆锥曲线段的包

44、含判定 以圆弧为例，假设点的坐标为(x, y, z)，圆弧的中心为(x0,y0,z0)，半径为r，起始角1，终止角2 (相对局部坐标系x轴)。 圆弧所在平面为 ax+by+cz+d=0 先判断点是否在该平面上，若不在，则点不可能被包含。若在，则通过坐标变换，把问题转换到二维的问题。 给定中心为（x0, y0），半径为r，起始角1 ，终止角2的圆弧，对平面上一点P(x, y)，判断P是否在圆弧上，可分二步进行: 第一步：判断P是否在圆心为（x0, y0），半径为r的圆的圆周上，即下式是否成立： 第二步：判断P是否在有效的圆弧段内。,（3）点与参数曲线的包含判定 设点坐标为P(x, y, z)，参

45、数曲线为Q(t)=(x(t), y(t), z(t)。点和参数曲线的求交计算包括三个步骤： （1）计算参数t值，使P到Q(t)的距离最小，即最小化 R(t)=(P-Q(t)(P-Q(t)=|P-Q(t)|2 （2）判断t是否在有效参数区间内（通常为0，1）； （3）判断Q(t)与P的距离是否小于 。,（4）点与平面区域的包含判定 设点坐标为P(x, y, z)，平面方程为ax+by+cz+d=0。则点到平面的距离为 d= 若d ，则认为点在平面上，否则认为点不在平面上。,在造型系统中，通常使用平面上的有界区域作为形体的表面。在这种情况下，对落在平面上的点还应进一步判别它是否落在有效区域内。若点

46、落在该区域内，则认为点与该面相交，否则不相交。,判断平面上一个点是否包含在同平面的一个多边形内，有许多种算法，常用的方法有：叉积判断法、夹角之和检验法以及交点计数检验法。,1）叉积判断法 假设判断点为P0。多边形顶点按顺序排列为P1P2Pn。如图所示。令Vi=Pi-P0, i=1, 2, , n, Vn+1=V1， 那么，P0在多边形内的充要条件是叉积ViVi+1(i=1, 2, , n)的符号相同 叉积判断法仅适用于凸多边形。当多边形为凹时，尽管点在多边形内也不能保证上述叉积符号都相同。这时可采用其他方法。,2）夹角之和检验法 假设某平面上有点P0和多边形P1P2P3P4P5，将点P0分别与Pi相连，构成向量Vi=Pi-P0 假设角 PiP0Pi+1=ai。如果 ，则点P0在多边形之外，如图2.5.3(a)所示。 如果 ，则点P0在多边形之内，如图2.5.3(b)所示。 ai可通过下列公式计算：令Si=Vi Vi+1, Ci=ViVi+1，