第三章二维图形生成技术.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 2.5 图形求交----包含判定算法 4、点与平面区域的包含判定 (3)点与二次曲面/参数曲面的包含判定 (4)点与三维形体的包含判定 2.5 图形求交----重叠判定算法 进行求交计算时，常涉及判断两个几何形体是否重叠。下面讨论几种常见的情况。 判断空间一点与另一点是否重叠，只要判断两点之间的距离是否小于0即可。 判断两条线段是否重叠，可先判断它们是否共直线，只要判断一条线段上任意两点是否在另一条线段所在的直线上，或是比较两条线段的方向向量并判断一条线段上任意一点是否在另一条线段所在的直线上。若两条线段不共线，则它们不可能重叠；否则可通过端点坐标的比较来判断两线段的重叠部分。 判断两个平面的重叠关系，一种方法是判断一个平面上的不共线三点是否在另一平面上；另一种方法是先比较两个平面的法向量，再判断一个平面上的某点是否在另一平面上。 2.5 图形求交----凸包计算 一个图形的凸包，就是包含这个图形的一个凸的区域。例如，一个平面图形的凸包可以是一个凸多边形，一个三维物体的凸包可以是一个凸多面体。一个图形的凸包不是唯一的。 在进行图形求交计算时，为了减小计算量，经常要在求交之前先进行凸包计算。如果两个图形的凸包不相交，那么显然它们不可能相交，就不必再对它们进行求交了。否则这两个图形有可能相交，需要进一步计算。 包围盒是一种特殊而又十分常用的凸包。二维的包围盒是二维平面上的一个矩形，它的两条边分别与两条坐标轴x，y平行，可以表示为两个不等式：xmin≤x≤xmax，ymin≤y≤ymax；三维空间中的包围盒是一个长方体，其长、宽、高分别与三条坐标轴平行，表示为三个不等式：xmin≤x≤xmax，ymin≤y≤ymax，zmin≤z≤zmax。两个包围盒相交的充要条件是它们在每一个坐标轴方向上都相交。 由于判定两个包围盒的相交情况比较容易，所以包围盒成为最常用的一种凸包。 求多边形或多面体的包围盒是相当简便的。只要遍历其所有顶点，就可以找出多边形或多面体在各个坐标轴方向上的最大、最小坐标值，从而确定包围盒。对于已近似化为多边形或多面体的含有曲线曲面的几何体，也可以用同样的方法求出包围盒。对于一般的几何形体，则要根据其具体性质来求取其包围盒。 2.7曲线生成与求交----Bezier曲线生成 2.7曲线生成与求交----Bezier曲线生成 2.7曲线生成与求交----Bezier曲线生成 2.7曲线生成与求交----Bezier曲线生成 2.7曲线生成与求交----Bezier曲线生成 2.7曲线生成与求交----Bezier曲线生成 2.7曲线生成与求交----Bezier曲线生成 下一页 2.7曲线生成与求交----Bezier曲线生成 下一页 2.7曲线生成与求交----Bezier曲线生成 下一页 2.7曲线生成与求交----Bezier曲线生成 2.7曲线生成与求交----Bezier曲线生成 下一页 2.7曲线生成与求交----Bezier曲线生成 下一页 2.7曲线生成与求交----Bezier曲线生成 下一页 2.7曲线生成与求交----Bezier曲线生成 下一页 2.7曲线生成与求交----Bezier曲线生成 下一页 2.7曲线生成与求交----Bezier曲线生成 2.7曲线生成与求交----Bezier曲线生成 下一页 2.7曲线生成与求交----Bezier曲线生成 2.7曲线生成与求交----Bezier曲线求交 直线段与参数曲线的交点 以直线段与三次参数曲线求交为例。这时交点可以有一至三个。假设直线参数方程为 　　　　　　　　P(t)=A+Bt 曲线的参数方程为 　　　　　　　　q(u)=Cu3+Du2+Eu+F 在交点处有方程 P(t)=q(u) 即 Cu3+Du2+Eu+F=A+Bt 用（A B）点乘两边得 　　　　　　　　（A B）·（Cu3+Du2+Eu+F）=0 可以用求根公式或数值方法解出一至三个u的实根。 本章习题 1、DDA法生成直线的基本原理是什么？ 2、简述二维图形裁剪的基本原理及可选用的裁剪策略。 3、简述种子法多边形填充算法. * * * * * * * * * 1、边界填充算法 在区域内测试（x，y）点的象素是否在区域之内同时又未被访问过。一般采用堆栈的方法，对边界定义的区域进行填充，基本流程如下： （1）种子象素入栈， （2）当栈非空时，执行如下三步操作：