第4章 计算机图形学.ppt

1、第二个几何图形，定义矢量叉积的强度：| P1P2 |=x1y2-x2y1，结果为标量。|P1P2 | 0时，P2的逆时针方向为P1 | | p1p 2 | | 0时，P1的顺时针方向为| | P1P2 | |=0时，P2与P1共线且为4.1.如果C 0，P1P2将逆时针旋转P2点，然后得到P2P3。如果C 0，P1P2将顺时针旋转P2点，然后得到P2P3。C=0时，P1，P2，P3共线，4.1.3凸形轮廓算法，凸形轮廓计算的基本任务，其中图形的凸形轮廓是包含牙齿图形的面积最小的凸形多边形，构成凸形轮廓的点称为凸形点，其馀点称为凸形轮廓内部点。，凸多边形，4.1.3凸壳算法，基本思路，4.1.3

2、凸壳算法Jarris算法，将s设置为平面内的点集，将s中y坐标最小的点用作凸壳的第一个顶点H1，与从H1开始的水平线相交计算为。命令集的当前顶点数为n0=n-1。While (n0) for I=1至n0向量Pi0Pi计算；计算。其馀所有if顶点都位于向量Pi0Pi之上，Pi点添加到凸面包列表中。pi0-Pi；从当前点集中删除交点。n0=n0-1；Endif endfor endwhile，4.1.3凸壳算法Graham算法，4.1.3凸壳算法Graham算法，G1 查找内部点:查找“点”列中的内部点G，从内部点水平定位G2 排序:连接内部点和所有点列，根据这些连接和L之间的角度以升序对点列进

3、行排序，以形成双向链接表。G3 查找凸面包的起点:获取点行中的所有极P0(x或y的最小/最大值)。Min，4.1.3凸形轮廓算法Graham算法，G4 查找凸形轮廓的顶点:从点1开始依次查看连续的三个顶点，如果是反向旋转(图中的实心点)，则将表中的指针加1，否则删除这三个，方向点，反向这样得到的凸包是周期点列，无论选择哪个起点，都可以用作凸包的起点。，4.1.4包容性测试，平面上的一点是否位于图形内部，或外部符号判别法角度判别法Griffiths判别法反射线交叉数判别法，4.1.4包容性测试符号判别法，对于凸面N多边形，4.1.4凸多边形，包含4.1.4测试角度确定方法，依次将测试点P连接到多

4、边形的每个顶点，然后计算点P和每个顶点包围的角度之和。点位于多边形外部。、4.1.4包容性测试角度判别法，从凸面多边形到规则多边形角度的适用性能计算不需要高精度。误差也可以达到。必须计算两个矢量之间的角度，而不会失去判断的准确性。与倒三角形函数计算有关。计算工作量大的计算量也是O(n)，但需要比符号判别法多做几倍的工作。4.1.4包容性测试Griffiths判别法，为了避免角度判别法中的倒三角函数，Griffiths在1981年提出了加快运算速度的近似值。基本原则：向量乘积PtPiPtPi 1与Sini成比例，数量乘积PtPiPtPi 1与cosi成比例，因此tgi或ctgi可以从两个乘积的结

5、果中导出。包含、4.1.4的测试Griffiths判别法，角度I可以通过以下近似线性近似公式得出：arctg x=/4x C，测试反射线交叉判别式点P位于多边形外部。如果选定的半射线通过多边形的顶点或与多边形的边重合，则根据矢量交点的特性值、焦点和重边的处理原则选择和计算交点。算法P:反光线交叉包容测试算法，创建从P1 创建光线点Pt(Xt，Yt)到点(X，Yt)的光线向量。其中x是多边形顶点无法到达的x的较大值，Yt表示光线与x轴平行。P2 查找交点使牙齿射线矢量与多边形的每个角矢量相交。记录相对于相交几何图元参数和射线的特征值，并在射线方向对齐交点。算法P:包含半射线交点数的测试算法，P3

6、 积分中点确定相邻交点的几何参数(例如中点)。求特征值的代数总和(例如代数和0)将取消两个交点。否则，其中一个交点将被取消。P4 合并相邻的相同要素交集标识两个相邻交点的要素，如果两个相邻的要素相同，则放弃其中一个交点。P5 判别计算交点数。奇数是多边形内部的点，否则是多边形外部的点。4.1.5最大最小判别法，最小最大判别法使用图形元素的最小外部矩形(或矩形方块)粗略确定两个图形元素之间的关系。显然，牙齿判定条件是充分的条件，在某些情况下，这种替代不正确，但由于比较快的优点，弥补了这种不足。a .外部矩形没有重叠，图形也没有重叠。b .外部矩形重叠，但图形不重叠。外部矩形也重叠，图形也重叠。、

7、4.1.5最大最小判别法，1)查找多边形的最小包含矩形。，2)检查重叠，如果两个多边形的最小包含矩形没有重叠，则两个多边形不能重叠。以下内容之一必须为真：4.1.6直线与面的关系；D1=ax1 by1 cz1 D2=N-2，直线位于面之后(N=-2) N=0，直线位于面上方(前面或后面)的两个牙齿善意顶点作为端点的两个相邻善意如果其他两个端点都在面之后，则线位于面的背面N0，线穿过面之前(N=1和n=2)，4.1.6线与面的关系，N=-1，线穿过面。指令=D1/(D1 D2) N20(P2点在面之后)，则位于棱柱的0，之间的部分(P1P)牙齿面之前。否则，边的0，之间的部分位于面的后面。4.1

8、.7直线和直线之间的关系；安装空间中分别存在P1、P2、Q1、Q2、方程式：4.1.7直线和直线之间的关系。将4.1.7直线和善意关系，S和S分别赋值到深度表达式ZP=zp1(zp2-zp1)szq=zq1(zq2-zq1)S，ZP zq P1P2在Q1Q2之前为ZP=，1，其中：NL是善意方向向量，P0是善意的任意点。4.2距离和面积、4、点到平面的距离。其中Ns是平面的法线向量。注意：1，空间平面方程规范化时，点对面距离只需将点的坐标直接赋给平面方程。2、点到平面的距离符号指示面上点的方向。4.2距离和面积，5，空间两条善意距离，L1和L2是空间中的两条直线，方向矢量分别为Nl1，Nl2，

9、则两条直线之间的距离为：其中P1和P2分别是L1和L2的随机点。范例：寻找线L1和线L2之间的距离。4.2距离和面积，6，直线和平面之间的距离，空间直线l的方向矢量是NL，平面s的法线矢量是NS，NL和Ns的点积不是0牙齿，则直线面相交，距离为0。否则，距离将查找：其中：PP，例如直线和平面s: 2y-z=0之间的距离。4.2距离和面积，7，空间两个平面之间的距离，如果两个平面平行，则两个平面之间的距离为，相交计算4.3，1，直线面，将空间直线L的方向矢量设置为NL，将平面S的法线矢量设置为Ns，以及如果两个平面相交，则相交方向为Ns1Ns2，交点为、4.4图形填充、4.0S2 计算填充线实际

10、范围取得每个图形顶点的坡度比为K的断面。从所有截断点中获取最大值bmax和最小值bmin。，4.4图形填充，S3 创建初始图案填充 b=bmin D，指针经过(0，b)，坡率k的直线ax by c=0，直线方向可以是任意的，但是一旦选定取得牙齿无限长直线与所有图形(包括S4 寻找填充线几何参数和图征)的交点。如果与弧线段的交点相切，则切线点不会相交，而是以直线方向对齐交点。4.4图形填充，S5 重点处理中点的话，以重点特征值为代数，如果该代数等于零，则取消重点。S6 输出图案填充依次输出从负要素交点到相邻正要素交点的直线段。S7 下一图案填充命令b=b D，如果bbmax超出范围，则退出，否则

11、旋转到S4。练习题、1、平面几何投影的以下叙述语句中正确的论述为()A，在平面几何投影中，如果投影中心从投影面向无限远移动，则平行投影。b，透视投影比平行投影具有更真实的视觉效果，真实地反映对象的精确大小和大小。c，在透视投影变换中，平行线集可以投影到平行的投影面上，从而产生消失点。d，三维空间中的物体可以执行透视投影变换，产生三个或更多的主要消失点。、练习题、2、包含角和判别点将点P连接到区域内外的多边形顶点，点P位于区域外的是_ _ _ _ _ _ _ _ _ _ _。a，点p与每个顶点包围的角度之和为0 B，点p与每个顶点包围的角度之和为c，点p与每个顶点包围的角度之和为2 D，点p与每个顶点包围的角度之和为3，练习中的问题，3，如果多边形外部的点a与点B和线段连接，则牙齿线段与多边形边界相交的