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

《计算机图形学-第4章 几何计算.ppt》由会员分享，可在线阅读，更多相关《计算机图形学-第4章 几何计算.ppt（46页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、青岛农业大学第二篇 几 何青岛农业大学第第4章章 几何计算几何计算青岛农业大学r判断计算判断计算 r拐向判断拐向判断r凸包算法凸包算法r包容性测试包容性测试rr距离和面积距离和面积r点到平面上一直线的距离点到平面上一直线的距离r点到一空间直线的垂足点到一空间直线的垂足r点到平面的距离点到平面的距离rr相交计算相交计算r直线与平面相交直线与平面相交r平面与平面相交平面与平面相交r曲线与曲线相交曲线与曲线相交r主要内容主要内容青岛农业大学4.1判断计算判断计算r决定几何间的位置和方向的计算决定几何间的位置和方向的计算q点、线段在线段、圆、折线、多边形上、点、线段在线段、圆、折线、多边形上、内和外的

2、判断计算。内和外的判断计算。q几何位置关系判断计算：切、交、离、含几何位置关系判断计算：切、交、离、含 q等等。青岛农业大学r向量叉积的模的定义：向量叉积的模的定义：|P1P2|=x1y2-x2y1，其结果是一个标量。，其结果是一个标量。r若若|P1P2|0，则，则P2在在P1的逆时针方向的逆时针方向 r若若|P1P2|0，则，则P1P2在在P2点点逆逆时针旋转后得到时针旋转后得到P2P3 r若若C 0(0(或或D Di i=0)=0)，则则被被测测试试点点在在多多边边形形的的外外部部(或或在在边边界上界上)，判断结束。，判断结束。r否否则则，所所有有的的D Di i0 0 r而而T却在多边形

3、的内部。却在多边形的内部。青岛农业大学4.1.4包容性测试包容性测试角度判别法角度判别法 依次将测试点依次将测试点P P与多边形各顶点相连与多边形各顶点相连,然后计算点然后计算点P P与各与各顶点围成的角度之和顶点围成的角度之和点在多边形之外点在多边形之外点在多边形之内点在多边形之内ABCDEPABCDEP青岛农业大学4.1.4包容性测试包容性测试角度判别法角度判别法 n大小：利用余弦定理n方向：令夹角如何计算？夹角如何计算？当TBP斜率，为顺时针角yxABP当T0时，AP斜率BP斜率，为逆时针角yxBAP青岛农业大学4.1.4包容性测试包容性测试角度判别法角度判别法 r这这种种角角度度的的计

4、计算算不不需需要要很很高高的的精精度度，其其误误差甚至可以达到差甚至可以达到也不失判别的正确性也不失判别的正确性 r但但是是必必须须计计算算两两向向量量间间的的夹夹角角而而涉涉及及到到反反三角函数的计算，计算工作量较大三角函数的计算，计算工作量较大 r计计算算量量虽虽也也是是O(n)，但但要要比比符符号号判判别别法法的的工作增加几倍工作增加几倍 r其适用性能从凸多边形扩展到一般多边形其适用性能从凸多边形扩展到一般多边形青岛农业大学4.1.4包容性测试包容性测试Griffiths判别法判别法 r为为了了在在角角度度判判别别法法中中避避免免求求取取反反三三角角函函数数，Griffiths在在198

5、1年年提提出出了了一一种种近近似似的的方方法法以以加加快快运算速度。运算速度。r基本原理：基本原理：矢矢量量积积PtPiPtPi+1与与sini成成正正比比，而而数数量量积积PtPiPtPi+1与与cosi成成正正比比,于于是是tgi或或ctgi可可由由这这两个积的结果导出。两个积的结果导出。青岛农业大学4.1.4包容性测试包容性测试Griffiths判别法判别法 r角度角度i可由下列近似的线性逼近公式求得：可由下列近似的线性逼近公式求得：arctg x=/4x+C r其中其中青岛农业大学4.1.4包容性测试包容性测试半射线交点判别法半射线交点判别法 r令令R R是一条以是一条以P P为起点任

6、何方向的半射线为起点任何方向的半射线 q当当R R和和多多角角形形的的交交点点个个数数为为奇奇数数个个时时，点点P P在在多多角角形形的内部的内部 q当交点个数为偶数或为零时，点当交点个数为偶数或为零时，点P P在多角形的外部在多角形的外部 若选择的半射线通过多角形的顶点，或与多角形的边若选择的半射线通过多角形的顶点，或与多角形的边重合时，根据向量交点的特征值、重点和重边的处理原则重合时，根据向量交点的特征值、重点和重边的处理原则进行交点的取舍，然后计数。进行交点的取舍，然后计数。青岛农业大学算法算法P：半射线交点计数包容性测试算法：半射线交点计数包容性测试算法rP1P1【建建立立射射线线】由

7、由点点P Pt t(X(Xt t，Y Yt t)向向点点(X(X，YtYt)建建立立一一射射线线向向量量。其其中中X X是是一一个个多多角角形形顶顶点点不不可可能能达达到到的的X X大值，大值，Y Yt t意味着射线和意味着射线和X X轴平行；轴平行；rP2P2【求求交交点点】将将此此射射线线向向量量和和多多角角形形的的各各边边向向量量求求交交。并并记记录录交交点点几几何何参参数数和和相相对对于于射射线线的的特特征征值值，并将交点按其射线方向排队；并将交点按其射线方向排队；青岛农业大学算法算法P：半射线交点计数包容性测试算法：半射线交点计数包容性测试算法rP3【合合并并重重点点】判判别别相相邻

8、邻交交点点的的几几何何参参数数，如如为为重重点点，则则求求其其特特征征值值的的代代数数和和，如如代代数数和和为为零零，则则取取消消两两个个交点，否则取消其中一个交点；交点，否则取消其中一个交点；rP4【合合并并相相邻邻同同特特征征交交点点】判判别别相相邻邻两两个个交交点点的的特特征征，如果相邻两个特征相同，则取消其中一个交点；如果相邻两个特征相同，则取消其中一个交点；rP5【判判别别】计计算算交交点点个个数数，如如为为奇奇数数，则则点点在在多多角角形形内部，否则在多角形外部。内部，否则在多角形外部。青岛农业大学4.1.5最大最小判别法最大最小判别法 如果两个图形元素的最小矩形包围盒子不相重迭，

9、则这如果两个图形元素的最小矩形包围盒子不相重迭，则这 两个图形元素不可能相交。两个图形元素不可能相交。最小最大判定法提供了这样一种快速拒绝判定法，这个最小最大判定法提供了这样一种快速拒绝判定法，这个 判定法是用图形元素的最小外接矩形判定法是用图形元素的最小外接矩形(或矩形盒子或矩形盒子)来来 替代，用以粗略地判定两个图形元素之间的某种关系。替代，用以粗略地判定两个图形元素之间的某种关系。虽然，这种判定条件是一种充分条件，在某些情况下，虽然，这种判定条件是一种充分条件，在某些情况下，这种替代是不正确的，但由于其比较速度很快的优点这种替代是不正确的，但由于其比较速度很快的优点 弥点补了这种不足。弥

10、点补了这种不足。青岛农业大学4.1.5最大最小判别法最大最小判别法 a.a.外接矩形不相迭，图形也不相迭外接矩形不相迭，图形也不相迭b.b.外接矩形相迭，但图形并不相迭外接矩形相迭，但图形并不相迭c.c.外接矩形相迭，图形也相迭外接矩形相迭，图形也相迭青岛农业大学4.1.5最大最小判别法最大最小判别法 1 1）找出多边形的最小包含矩形）找出多边形的最小包含矩形 该矩形的该矩形的4 4条边分别平行于两坐标轴，矩形的位置和大小可以条边分别平行于两坐标轴，矩形的位置和大小可以用用XmaxXmax、XminXmin、YmaxYmax、YminYmin来定义，而这来定义，而这4 4个参数就是多边形顶点个

11、参数就是多边形顶点坐标中的极值。坐标中的极值。2 2）重叠性检验）重叠性检验 如果两个多边形的最小包含矩形不发生重叠，则这两个多边如果两个多边形的最小包含矩形不发生重叠，则这两个多边形必定不会重叠，则下式必有一个成立：形必定不会重叠，则下式必有一个成立：青岛农业大学4.1.6 线与面的关系线与面的关系 r令：令：D1=Ax1+By1+Cz1+D D2=Ax2+By2+Cz2+D r D1(D2)0 1 r且令：且令：N=N1+N2 青岛农业大学4.1.6 线与面的关系线与面的关系 r则当则当N-2，线在面的后面（，线在面的后面（N=-2）r N=0，线在面上（正面或背面）线在面上（正面或背面）

12、以此线两顶点为端点的两相邻线的另两个端点的状态决定以此线两顶点为端点的两相邻线的另两个端点的状态决定q若若另另两两个个端端点点中中有有一一端端点点在在面面的的前前面面，则则此此线线棱棱在在面面的的正正面；面；q若另两端点均在面之后，此时线在面的背面若另两端点均在面之后，此时线在面的背面qN0，线在面之前，线在面之前（N=1 和和 N=2）青岛农业大学4.1.6线与面的关系线与面的关系 rN=-1，线贯穿面；线贯穿面；令令=D1/(D1+D2)q若若N2 zq P1P2在在Q1Q2的前面的前面 qzp=zq P1P2与与Q1Q2在同一平面上在同一平面上 qzp bmax，超越范围，则结束，否则转超越范围，则结束，否则转S4。