第4章 计算机图形学.ppt

《第4章 计算机图形学.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二篇几何第4章几何计算判断计算拐向判断凸包算法包容性测试……距离和面积点到平面上一直线的距离点到一空间直线的垂足点到平面的距离……相交计算直线与平面相交平面与平面相交曲线与曲线相交……主要内容4.1判断计算决定几何间的位置和方向的计算点、线段在线段、圆、折线、多边形上、内和外的判断计算。几何位置关系判断计算：切、交、离、含等。向量叉积的模的定义：

2、

3、P1×P2

4、

5、==x1y2-x2y1，其结果是一个标量。若

6、

7、P1×P2

8、

9、>0，则P2在P1的逆时针方向若

10、

11、P1×P2

12、

13、<0，则P2在P1的顺时针

14、方向若

15、

16、P1×P2

17、

18、=0，则P2与P1共线4.1.1折线段的拐向判断_原理4.1.2折线段的拐向判断对于有公共端点P2的线段P1P2和P2P3，通过计算

19、

20、(P2-P1)×(P3-P2)

21、

22、的符号，即C=便可以确定折线段的拐向。若C>0，则P1P2在P2点逆时针旋转后得到P2P3若C<0，则P1P2在P2点顺时针旋转后得到P2P3若C=0，则P1、P2、P3共线4.1.3凸包算法凸包计算的基本任务就是确定两个或多个物体彼此之间是否发生接触或穿透。一个图形的凸包就是包含这个图形的一个面积最小的凸多边

23、形，构成凸包的点称为凸包点，其余点称为凸包内点。在一个多边形上（包括在多边形的边界上及边界包围的范围）任意取两点并以一条线段连接，如果线段上的每一点均在该多边形内，则这个多边形是凸多边形。如三角形、正方形、平行四边形、正五边形等。凸多边形4.1.3凸包算法基本思想：用形状简单的几何体（凸包）将形状复杂的物体包围起来，由物体的凸包进行粗略检测，当两凸包不相交时，其相应的两原物体间一定不相交，从而快速排除那些不可能相交的物体。4.1.3凸包算法——Jarris算法设S为平面内的点的集合,从S中将y坐标最小

24、的点作为凸包的第一个顶点H1,找到与以H1为起点的水平线的叉积为正且夹角最小的点,作为凸包的第二个顶点H2,再求与线段H1H2叉积为正且夹角最小的点,作为凸包的第三个顶点，……，直到返回第一个顶点。4.1.3凸包算法——Jarris步进法令点集中最下点为凸包顶点的起点，计作Pi0；令点集中的当前顶点数为N0=N-1；While（N0）Fori=1ToN0{计算向量Pi0Pi；if其余顶点全部在向量Pi0Pi的上方，则Pi点加入凸包列表；Pi0<-Pi；从当前点集中删除Pi；N0=N0-1；endife

25、ndforendwhile4.1.3凸包算法——Graham算法对于一个有序点集，如果所有点都在凸包上，则每三个相继的点会组成一个左拐，若三个相继的点组成一个右拐，即中间点位于三点组成的三角形内，可以直接去除该点。4.1.3凸包算法——Graham算法G1【找内点】：找到点列的一个内点G，从内点作水平向右的一向量L；G2【排序】：连接内点和全部点列，根据这些连线与L的夹角按递增次序对点列排序，形成一个双向链接表；G3【求凸包上的起点】：求取点列中的任一个极点P0（x或y的最小/最大者）；Min4.1.

26、3凸包算法——Graham算法G4【求凸包上的一个顶点】：从点1出发依次考察连续的三个顶点，如果是向逆向转（图中实心圆点），则表的指针加1，否则删去三个顶点中的中间点（图中空心圆点），且指针减1；顺向点逆向点G5【求取凸包】：按G4遍历点表，其结果即为点列的有向凸包。这样求得的凸包是一个循环点列，选取任一个起点均可作为凸包的起点。4.1.4包容性测试决定平面上的一个点是在图形的内部还是在它的外部符号判别法角度判别法Griffiths判别法半射线交点计数判别法4.1.4包容性测试——符号判别法对于一个凸

27、n多边形，按照同一方向（保证边向量的左侧为多边形的内部）计算通过各边向量的直线的方程系数(Ai,Bi,Ci)(i=1,2,……n)设被测试点为T(Xt，Yt)，计算Di=Aixt+Biyt+Ci(i=1,2,……n)若Di>0(或Di=0)，则被测试点在多边形的外部(或在边界上)，判断结束。否则，所有的Di<0(i=1,2,……n)，表示被测试点在图形的内部。4.1.4包容性测试——符号判别法该方法适用于凸多边形4.1.4包容性测试——角度判别法依次将测试点P与多边形各顶点相连,然后计算点P与各顶点围

28、成的角度之和点在多边形之外点在多边形之内ABCDEPABCDEP4.1.4包容性测试——角度判别法大小：利用余弦定理方向：令夹角如何计算？当T<0时，AP斜率>BP斜率，为顺时针角yxABP当T>0时，AP斜率