计算机图形学 第三章图形裁剪算法.pptVIP

习题 第三章图形的裁剪算法 裁剪的含义： 裁剪是从数据集合中抽取信息的过程，是许多图形操作的基础 裁剪的目的： －从大的画面中抽取所需的具体信息 －处理图形中的隐藏线、面、体，以及阴影处理等 算法的关键： 快速，可用硬件实现 3.1 线段裁剪 一、Cohen-Sutherland 裁剪算法 算法：根据每一小段端点的编码决定对该段的取舍 3.2 线段的三维裁剪 一、二维裁剪方法推广到三维问题 二、三维 Cyrus - Beck 算法 三维 Cyrus - Beck 算法（续） 三维 Cyrus - Beck 算法 (续) 3.3 多边形的裁剪 一、多边形裁剪与线段裁剪的异同与困难 二、逐次多边形裁剪 (Sutherland-Hodgman 算法) 逐次多边形裁剪 (续) 逐次多边形裁剪 (续) 多边形裁剪的讨论 第三章小结： * * 1. 试用作图法实现对多边形的逐次裁剪(Sutherland-Hodgman算法)，显示每步产生的中间多边形，多边形顶点取(-4,2), (8,14), (8,2), (12,6), (12,-2), (4,-2), (4,6), (0,2)，裁剪窗口为(0,0,10,10) 2. 已知点 P (xp, yp)，及直线 L 的方程 ax+by+c＝0，试推导一个相对L作对称变换的矩阵 M，使点 P 对 L 的对称点为 P’＝P*M 3. 给定空间一点 P (x, y, z) 及任一平面 Q: ax+by+cz+d = 0, 求 P 对 Q 的对称点 P’(x’, y’, z’) 的变换矩阵 思路： 首先简化问题，排除无需操作的对象；然后对需要处理的对象设法简化算法 每条线段无非三种可能性： 完全不可见 完全可见 部分可见 可通过对线段端点的简单判别，判断 线段与窗口的关系 通过区域编码进行判别： 1. 定义区域编码： Bit 0：左 Bit 1：右 Bit 2：下 Bit 3：上 0000 1001 0001 0101 1000 0100 1010 0010 0110 2. 将线段两端点逐位求“与”， 若结果非零，该线段完全不可见 3. 对求“与”结果为零线段， 通过端点判别得完全可见线段 4. 对剩下的其它线段，作线段与窗口边 求交处理确定可见部分 * 特殊线段的处理：斜率无穷大或为零，一个端点编码为零等 步骤： (1) 检察线段P1P2是否为完全可见或显然不可见 (2) 若P1在窗口外，继续步骤(3)，否则交换P1，P2 (3) 用P1P2和窗口边的交点取代P1点，并重复步骤(1)-(3) 例题： P1 P2 P1：(1/2, 1/6)；编码 (0001) P2：(1/2, 3/2)；编码 (1000) (2) 求右边交点，得 P’’1(1, 11/6) P2(-1, 1/2)；并编码， 判别之 (1) 求左边交点，得P’1P2; P’1:(-1,1/2); 编码(0000) 判别知非完全可见，且P’1在窗口内， 因此交换P’1P2得新线段P1P2； P1：(1/2, 3/2)；编码 (1000) P2：(-1, 1/2)； 编码 (0000) (3) 求上边交点，得 P’’’1(-1/4, 1) P2(-1, 1/2)；并编码， 两端点编码全部为0，线段完全可见，程序结束 P1’ P1’’ 二、中点分割算法 思路：通过对线段的分割，找出可见线段，在运算过程中仅使用加法和移位运算 算法： (1) 对线段端点编码以判别可见性 (2) 在线段P1P2上分别求出离P1最远的可见点和离P2最远的可见点，此两点 间即为可见线段 算法的实现： 软件实现：两遍对数查找 硬件实现：可并行处理 通过对对分得到子线段端点的判别，抛弃不可见线段 当对分段很短时，(达到允许精度)，处理结束 P1 P2 P2 P1 三、Cyrus-Beck 算法 特点：可对任意凸多边形窗口实现二维和三维裁剪 考虑一个凸多边形 R 和一个线段 P1P2， P1 P2 与 R 最多只有两个交点 设 A 是 R 边界上一点，N 是该区域边界 在 A 点的内法向量 将P1 P2用参数方程表示：P(t) ＝ (P2－P1) t ＋ P1 则线段上任一点P(t), 与 N 的点积有三种可能 (1) P(t) 在多边形外侧：N 。(P(t)－A) 0 (2) P(t) 在多边形的边及其延长线上：N 。(P(t)－A) = 0 (3) P(t) 在多边形内侧：N 。(P(t)－A) 0 因此，P(t)在凸多边形内的充要条件是：对凸多边形边界上任