计算机图形学第三章二维图形的裁剪资料.ppt

第三章 二维图形的裁剪 重点：掌握二维图形点、线段、多边形和字符的裁剪算法。 难点：理解二维裁剪算法思想并且用C语言进行算法的实现。 课时安排：授课4学时（线段裁剪：2学时；多边形裁剪：2学时）； 上机4学时（多边形裁剪）。 第三章 二维图形的裁剪 第三章 二维图形的裁剪 　 一、裁剪的意义 　　为了描述图形对象，我们必须存储它的全部信息，但有时为了达到分区描述或重点描述某一部分的目的，往往将要描述的部分置于一个窗口内，而将窗口外的部分“剪掉”，这个处理过程叫做裁剪，裁剪在计算机图形处理中具有十分重要的意义。 　　裁剪实质上是从数据集合中抽取信息的过程，这个过程是通过一定的计算方法来实现。 裁剪就是将指定窗口作为图形边界，将窗口内的图形保留，而窗口外的图形则被舍弃。 第三章 二维图形的裁剪 二、裁剪的目的 　　裁剪的基本目的是判断某个图形元素是否落在窗口之内，如落在窗口之内则进一步求出位于窗口内的部分。 　　 三、裁剪处理涉及 　　1、图元在窗口内外的判别； 　　2、图形元素与窗口的求交。 3.1 点的裁剪 先看简单的点图元裁剪，它是线段裁剪以及后面的多边形裁剪的基础。 　　如果矩形窗口的左、右横坐标为：xmin、xmax；　　　　　　　　　上、下纵坐标为：ymin，ymax。 　　某点（x，y）在窗口内的充分必要条件是： 3.1 点的裁剪 ?xmin≤x≤xmax （3－1） ymin≤y≤ymax 如果上面四个不等式中任何一个不满足，则点（x，y）位于窗口之外。 　　对于任意多边形窗口，需要根据第二章提到的多边形内点的判别准则进行判断。 3.2 线段的裁剪 直线段的裁剪比点复杂，其裁剪方法又是多边形裁剪和三维图形裁剪的基础。 　　 一、直线裁剪的基本思想 　　判断直线与窗口的位置关系： 　　1．确定直线是完全可见； 　　2．部分可见； 　　3．还是完全不可见。 　　对部分可见线段，求出它与窗口边界的交点，并将窗口内的线段输出。 3.2 线段的裁剪 　 二、裁剪线段和窗口的关系 　 　假定窗口左下角坐标为(xmin，ymin)，右上角坐标为(xmax，ymax)，待裁剪线段和窗口的关系如图所示，这五种位置关系存在下面三种情况： 　　1、直线的两个端点均在窗口内，如图中AB线。这时直线完全可见，可被简单接受。 　　2、直线的两个端点都在窗口外，并且位于窗口某一边界的同一外侧，如图中EF线。则直线完全不可见，可被简单舍弃。 　　3、除此之外需要求交点，以确定直线在窗口某一边界内是否有可见部分,并裁掉外部线段，显示内部线段。如CD、GH、IJ线。 3.2 线段的裁剪 3.2 线段的裁剪 为了提高裁剪效率，算法设计一般可从下面两方面作出考虑： 　　(1) 快速判断情况1和情况2。 　　(2)在情况3中，设法减少求交的次数和每次求交时所需的计算量。 　　 三、直线求交计算 　　当线段P1P2穿过某边界L时，交点P的计算如图中所示。 3.2 线段的裁剪 根据直线两点式方程： (3－2) 3.2 线段的裁剪 整理后得通用交点公式： (3－3) 1、与上边界的求交公式： ? (3－4) 3.2 线段的裁剪 2、与下边界的求交公式： ? (3－5) 3、与右边界的求交公式： ? (3－6) 4、与左边界的求交公式： ? (3－7) 3.2.1 Cohen－Sutherland算法 一、Cohen－Sutherland算法思想： 　　该算法也称为编码算法，首先对线段的两个端点按所在的区域进行分区编码，根据编码可以迅速地判明全部在窗口内的线段和全部在某边界外侧的线段。只有不属于这两种情况的线段，才需要求出线段与窗口边界的交点，求出交点后，舍去窗外部分。 　　对剩余部分，把它作为新的线段看待，又从头开始