计算机图形学-第4章 几何计算.ppt

1、第二篇 几 何,第4章 几何计算,判断计算 拐向判断 凸包算法 包容性测试 距离和面积 点到平面上一直线的距离 点到一空间直线的垂足 点到平面的距离 相交计算 直线与平面相交 平面与平面相交 曲线与曲线相交 ,主要内容,4.1判断计算,决定几何间的位置和方向的计算 点、线段在线段、圆、折线、多边形上、内和外的判断计算。 几何位置关系判断计算：切、交、离、含 等 。,向量叉积的模的定义： | P1P2 |= =x1y2 - x2y1，其结果是一个标量。 若|P1P2 | 0，则P2在P1的逆时针方向 若| P1P2 | 0，则P2在P1的顺时针方向 若| P1P2 | = 0，则P2与P1共线,

2、4.1.1 折线段的拐向判断_原理,4.1.2折线段的拐向判断,对于有公共端点P2的线段P1P2和P2P3 ，通过计算|(P2 - P1)(P3- P2) |的符号，即 C= 便可以确定折线段的拐向。 若C 0，则P1P2在P2点逆时针旋转后得到P2P3 若C 0，则P1P2在P2点顺时针旋转后得到P2P3 若C = 0，则P1 、 P2 、P3共线,4.1.3 凸包算法,凸包计算的基本任务就是确定两个或多个物体彼此之间是否发生接触或穿透。 一个图形的凸包就是包含这个图形的一个面积最小的凸多边形，构成凸包的点称为凸包点，其余点称为凸包内点。,在一个多边形上（包括在多边形的边界上及边界包围的范围

3、）任意取两点并以一条线段连接，如果线段上的每一点均在该多边形内，则这个多边形是凸多边形。 如三角形、正方形、平行四边形、正五边形等。,凸多边形,4.1.3 凸包算法,基本思想：用形状简单的几何体（凸包）将形状复杂的物体包围起来，由物体的凸包进行粗略检测，当两凸包不相交时，其相应的两原物体间一定不相交，从而快速排除那些不可能相交的物体。,4.1.3 凸包算法Jarris算法,设S为平面内的点的集合, 从S中将y坐标最小的点作为凸包的第一个顶点H1, 找到与以H1为起点的水平线的叉积为正且夹角最小的点,作为凸包的第二个顶点H2 , 再求与线段H1H2叉积为正且夹角最小的点,作为凸包的第三个顶点，直

4、到返回第一个顶点。,4.1.3 凸包算法Jarris步进法,令点集中最右（左/上/下）点为凸包顶点的起点，计作Pi0； 令点集中的当前顶点数为N0=N-1； While（N0） For i=1 To N0 计算向量Pi0Pi； if 其余顶点全部在向量Pi0Pi的左侧（右侧），则 Pi点加入凸包列表； Pi0 - Pi； 从当前点集中删除Pi； N0=N0-1； endif endfor endwhile,4.1.3 凸包算法Graham算法,对于一个有序点集，如果所有点都在凸包上，则每三个相继的点会组成一个左拐，若三个相继的点组成一个右拐，即中间点位于三点组成的三角形内，可以直接去除该点。,

5、4.1.3 凸包算法Graham算法,G1【找内点】：找到点列的一个内点G，从内点作水平向右的一向量L； G2【排序】：连接内点和全部点列，根据这些连线与L的夹角按递增次序对点列排序，形成一个双向链接表； G3【求凸包上的起点】：求取点列中的任一个极点P0（x或y的最小/最大者）；,Min,4.1.3 凸包算法Graham算法,G4【求凸包上的一个顶点】：从点1出发依次考察连续的三个顶点，如果是向逆向转（图中实心圆点），则表的指针加1，否则删去三个顶点中的中间点（图中空心圆点），且指针减1；,顺向点,逆向点,G5【求取凸包】：按G4遍历点表，其结果即为点列的有向凸包。这样求得的凸包是一个循环点

6、列，选取任一个起点均可作为凸包的起点。,4.1.4 包容性测试,决定平面上的一个点是在图形的内部还是在它的外部 符号判别法 角度判别法 Griffiths判别法 半射线交点计数判别法,4.1.4包容性测试符号判别法,对于一个凸n多边形，按照同一方向（保证边向量的左侧为多边形的内部）计算通过各边向量的直线的方程系数 (Ai , Bi , Ci) (i=1,2,n) 设被测试点为T(Xt，Yt)，计算 Di=Aixt+Biyt+Ci (i=1,2,n) 若Di0(或Di=0)，则被测试点在多边形的外部(或在边界上)，判断结束。 否则，所有的Di0 (i=1,2,n)，表示被测试点在图形的内部。,4

7、.1.4包容性测试符号判别法,在此判别法中，多边形为凸的条件不能少 虽然有 A45xt +B45yt + C45 0 而T却在多边形的内部。,4.1.4包容性测试角度判别法,依次将测试点P与多边形各顶点相连,然后计算点P与各顶点围成的角度之和,点在多边形之外,点在多边形之内,4.1.4包容性测试角度判别法,大小：利用余弦定理 方向：令,夹角如何计算？,4.1.4包容性测试角度判别法,这种角度的计算不需要很高的精度，其误差甚至可以达到也不失判别的正确性 但是必须计算两向量间的夹角而涉及到反三角函数的计算，计算工作量较大 计算量虽也是O(n)，但要比符号判别法的工作增加几倍 其适用性能从凸多边形扩

8、展到一般多边形,4.1.4包容性测试Griffiths判别法,为了在角度判别法中避免求取反三角函数，Griffiths在1981年提出了一种近似的方法以加快运算速度。 基本原理： 矢量积PtPiPtPi+1与sini成正比，而数量积PtPiPtPi+1与cosi成正比,于是tgi或ctgi可由这两个积的结果导出。,4.1.4包容性测试Griffiths判别法,角度i可由下列近似的线性逼近公式求得： arctg x=/4x+C 其中,4.1.4包容性测试半射线交点判别法,令R是一条以P为起点任何方向的半射线 当R和多角形的交点个数为奇数个时，点P在多角形的内部 当交点个数为偶数或为零时，点P在多

9、角形的外部,若选择的半射线通过多角形的顶点，或与多角形的边重合时，根据向量交点的特征值、重点和重边的处理原则进行交点的取舍，然后计数。,算法P：半射线交点计数包容性测试算法,P1【建立射线】由点Pt(Xt，Yt)向点(X，Yt)建立一射线向量。其中X是一个多角形顶点不可能达到的X大值，Yt意味着射线和X轴平行； P2【求交点】将此射线向量和多角形的各边向量求交。并记录交点几何参数和相对于射线的特征值，并将交点按其射线方向排队；,算法P：半射线交点计数包容性测试算法,P3【合并重点】判别相邻交点的几何参数，如为重点，则求其特征值的代数和，如代数和为零，则取消两个交点，否则取消其中一个交点； P4

10、【合并相邻同特征交点】判别相邻两个交点的特征，如果相邻两个特征相同，则取消其中一个交点； P5【判别】计算交点个数，如为奇数，则点在多角形内部，否则在多角形外部。,4.1.5最大最小判别法,如果两个图形元素的最小矩形包围盒子不相重迭，则这 两个图形元素不可能相交。 最小最大判定法提供了这样一种快速拒绝判定法，这个 判定法是用图形元素的最小外接矩形(或矩形盒子)来 替代，用以粗略地判定两个图形元素之间的某种关系。 虽然，这种判定条件是一种充分条件，在某些情况下， 这种替代是不正确的，但由于其比较速度很快的优点 弥点补了这种不足。,4.1.5最大最小判别法,a.外接矩形不相迭，图形也不相迭 b.外

11、接矩形相迭，但图形并不相迭 c.外接矩形相迭，图形也相迭,4.1.5最大最小判别法,1）找出多边形的最小包含矩形,该矩形的4条边分别平行于两坐标轴，矩形的位置和大小可以用Xmax、Xmin、Ymax、Ymin来定义，而这4个参数就是多边形顶点坐标中的极值。,2）重叠性检验,如果两个多边形的最小包含矩形不发生重叠，则这两个多边形必定不会重叠，则下式必有一个成立：,4.1.6 线与面的关系,令： D1= Ax1+By1+Cz1+D D2= Ax2+By2+Cz2+D D1(D2)0 1 且令：N=N1+N2,4.1.6 线与面的关系,则当N-2，线在面的后面（ N=-2 ） N=0， 线在面上（正

12、面或背面） 以此线两顶点为端点的两相邻线的另两个端点的状态决定 若另两个端点中有一端点在面的前面，则此线棱在面的正面； 若另两端点均在面之后，此时线在面的背面 N0，线在面之前（ N=1 和 N=2 ）,4.1.6线与面的关系,N=-1， 线贯穿面； 令=D1/ (D1+D2) 若N20（P2点在面后）， 则棱的0,间的部份（P1P）在面的前面； 否则，棱的0,间的部份在面的后面。,4.1.7 线与线的关系,设空间有两条线，其端点分别为P1、P2和Q1、Q2，方程分别为：,4.1.7 线与线的关系,求得它们在XOY投影面上的交点S（P1P2上的P点和Q1Q2上的Q点在XOY上的重合投影点）的参

13、数s和s 若s0,1且 s0,1， 则这两条线在空间存在遮挡关系,4.1.7 线与线的关系,将s和s分别代入深度方程 zp=zp1+(zp2-zp1)s zq=zq1+(zq2-zq1)s 若 zp zq P1P2在Q1Q2的前面 zp = zq P1P2与Q1Q2在同一平面上 zp zq P1P2在Q1Q2后面,4.2 距离和面积,将点的坐标代入直线方程即可。,1、点到平面上直线的距离,2、点到空间直线的垂足,设nL是直线L的单位方向向量，P0是L上的任意一点，P是空间中的任意一点，则P在L上的垂足Pv为：,例：已知点P0(0,0,0),PL(1,1,1)，直线L由P0、PL决定，求点P(0

14、.5,1,0)到直线L的垂足PV。,4.2 距离与面积,3、点到空间直线的距离,例：求点P（2，-1，1）到直线L的距离D。,其中：NL是直线的方向向量，P0是直线上任意点。,4.2 距离与面积,4、点到平面的距离,其中：Ns为平面的法向量。,注意： 1、若空间平面方程是规格化的，则点到面的距离直接把点 的坐标代入平面方程即可。 2、点到平面的距离符号标示点在面的方位。,4.2 距离与面积,5、空间两直线的距离,L1与L2是空间任意两条直线，方向向量分别为Nl1，Nl2，则两直线之间的距离为：,其中P1和P2分别为L1和L2上的任意点。,例：求直线L1与直线L2之间的距离。,4.2 距离与面积

15、,6、直线与平面的距离,空间直线L的方向向量为NL，平面S的法向量为Ns，若NL与NS的点积不为0，则线面相交，距离为0，否则，距离为：,其中：PL与Ps分别为直线和平面上的任意点。,例：求直线 与平面S：2y-z=0之间的距离。,4.2 距离与面积,7、空间两平面的距离,若两平面平行，则两者之间的距离为：,4.3 相交计算,1、线面相交,设空间直线L的方向向量为NL，平面S的法向量为Ns，若NLNs不为0，则线面相交，交点为：,其中：PL与Ps分别为直线和平面上的任意点。,4.3 相交计算,2、面面相交,设空间任意平面S1、S2，法向量分别为Ns1、Ns2，Ps1和Ps2分别是两平面上的任意点。若两平面相交，交线方向为Ns1Ns2，交点为：,4.4 图形填充,对图形有界区域的矢量化填充 直线段和图形公共部份的求取是区域填充算法的基础； 在隐藏线消除中，则是对画面上的线段作相反的判断，公共部份是被隐藏的，而非公共部份则是需要绘制的。,4.4 图形填充,S1【建立方程】根据图形描述(圆弧曲线XYR)，对直线连接的，是根据二点式建立过二点的有向法线式系数，对圆弧连接的则求取圆心位置。 S2【求取填充线范围】对各图形顶点求取斜率为K的截距；并在所有截距中求取最大值bmax和最小值bmin。,4.4 图形填充,S3【建立初始填充线】令b=bmin+D，过点(0，b)，斜