《线上线下混合式计算机图形学基础实验教程》课件_第6章.pptx

第6章直线段和多边形裁剪;

6.1实验内容简述和实验目标

;

完成本实验后，读者能够：

(1)熟记和描述Cohen-Sutherland直线段裁剪的原理和过程(布鲁姆知识模型：记忆和理解)；

(2)熟记和描述Sutherland-Hodgman多边形裁剪的原理和过程(布鲁姆知识模型：记忆和理解)；

(3)熟记和描述Weiler-Atherton多边形裁剪的原理和过程(布鲁姆知识模型：记忆和理解)；

(4)判断交点是出点还是入点(布鲁姆知识模型：应用)；

;

(5)判断点(累积角度法)是在多边形内部还是在多边形外部(布鲁姆知识模型：应用)；

(6)结合OpenGL编程实现——Cohen-Sutherland直线段裁剪、Sutherland-Hodgman多边形裁剪和Weiler-Atherton多边形裁剪(布鲁姆知识模型：应用)。

;

6.2Cohen-Sutherland直线段裁剪

;

为了快速判断一条直线段与裁剪多边形的位置关系，可采用的编码方法是：延长裁剪多边形的边，将二维平面分成9个区域，给每个区域赋予4位编码(见图6-1)。

;

裁剪一条线段时(见图6-2)，先求出线段两端点P1、P4的编码code1、code2。若code1=0、code2=0，则线段P1P2完全在裁剪多边形内，直接完整保留该线段。若编码按位与运算code1code20，则说明两个端点同在裁剪多边形的上方、下方、左方或右方，可判断线段完全在裁剪多边形外，丢弃整条线段；否则求出线段与裁剪多边形的交点，将直线段分成两段，先丢弃完全在裁剪多边形外的线段，再对剩下的另一段线段迭代开展上述操作。

;

;

1.关键数据结构

自定义如下数据结构用以表示三维齐次坐标下的点(顶点或者交点)。该数据结构应用于本书随后所有章节的实验中。

;

2.关键函数代码实现

3.案例效果

图6-3(a)显示了直线和裁剪多边形的初始状态，平移裁剪多边形，用Cohen-Sutherland算法执行裁剪，最终效果如图6-3(b)所示。

;

;

6.3Sutherland-Hodgman多边形裁剪

;

按序考虑被裁剪多边形每条边端点S、P与裁剪线的位置关系，有以下四种情况：

(1)若S、P均在可见一侧，则保留点P(见图6-4(a))。

(2)若S、P均在不可见一??，则保留0个点(见图6-4(b))。

(3)若S可见，P不可见，则保留SP与裁剪线的交点I(见图6-4(c))。

(4)若S不可见，P可见，则保留SP与裁剪线的交点I和点P(见图6-4(d))。

;

;

1.关键数据结构

自定义点相对于多边形的空间位置关系，其数据结构如下：

;

2.关键函数代码实现

3.案例效果

图6-5(a)给定了裁剪多边形(粗线)和被裁剪多边形(细线)的初始状态，用Sutherland-Hodgman算法执行裁剪，最终效果如图6-5(b)所示。;

;

6.4Weiler-Atherton多边形裁剪

;

其算法步骤如下：

(1)定义裁剪多边形clip_polygon和被裁剪多边形subject_polygon，它们均为my_homogeneous_point_EX数组。同时，定义三个带头指针的循环链表plist、clip_polygonlist和subject_polygonlist，分别用来存储交点、插入交点的裁剪多边形和插入交点的被裁剪多边形。

(2)定义一个多边形求交函数generateIntersectPoints，实现两个多边形的所有交点存储在plist链表中，在此过程中，将上述每一交点按序(相交边的两端点之间)插入subject_polygonlist和clip_polygonlist。

(3)定义函数用来确定每个交点为出点或入点。

;

(4)定义生成所有裁剪结果区域的函数generateClipArea，其具体步骤如下：

①定义记录裁剪结果的临时数组subject_polygonClip。

②从头指针开始顺序遍历subject_polygonlist，寻找第一个未被访问过的入点，若存在，则将该入点设为当前点，并记录到subject_polygonClip中，进入步骤③，否则进入步骤⑤。

;

③从当前点开始遍历subject_polygonlist，将下一个被访问的点PC设为当前点，并记录到subject_polygonClip中。若PC为subject_polygonClip的第一个点，则将subject_polygonClip数据输出，即找到一个裁剪结果区域，之后清空subject_polygonClip，