二维图形裁剪
文章目录
一、点裁剪
对于点在窗口内的充分必要条件是:
满足上述条件的不等式组的点应该在窗口内;
二、线段裁剪
2.1 基本概念
- 线段相对于该窗口的情况有
(1)线段全部位于窗口的内部(A);
(2)线段全部位于窗口外部(B、C);
(3)线段的中间部分在窗口内,而二端点在窗口外部(D);
(4)线段的一端在窗口内,而另一端在窗口外(E);
- 待裁剪线段和窗口的关系
(1)线段完全可见;
(2)显然不可见 ;
(3)线段至少有一端点在窗口之外,但非显然不可见;
2.2 直接求交算法
- 基本思想:判断直线与窗口的位置关系,确定该直线是完全可见、部分可见或完全不可见,然后输出处于窗口内线段的端点,并显示此线段。
根据直线段和窗口的关系可知:
(1)整条线在窗口之内。此时,不需剪裁,显示整条线段;
(2)整条线在窗口之外,此时,不需剪裁,不显示整条线段;
(3)部分线在窗口之内,部分线在窗口之外。此时,需要求出线段与窗口边界的交点,并将窗口外的线段部分剪裁掉,显示窗口内的部分;
2.3 Cohen-Sutherland 算法
- 基本思想:对于每条待裁剪的线段分三种情况处理:
(1)若完全在窗口内,则显示该线段,简称“取”之;
(2)若完全在窗口外,则丢弃该线段,简称“舍”之;
(3)若线段既不满足“取”的条件,也不满足“舍”的条件,则求线段与窗口边界的交点,在交点处把线段分为两段,其中一段完全在窗口外,可舍弃之,然后对另一段重复上述处理。 - 编码原则:图形区域划分成九个区域,四位编码表示端点所处的位置。
(1)第一位为“1”时,表示点在的上方;
(2)第二位为“1”时,表示点在的下方;
(3)第三位为“1”时,表示点在的右方;
(4)第四位为“1”时,表示点在的左方;
-
算法步骤
(1)第一步 判别线段两端点是否都落在窗口内,如果是,则线段完全可见;否则进入第二步;
(2)第二步 判别线段是否为显然不可见,如果是,则裁剪结束;否则进行第三步;
(3)第三步:求线段与窗口边延长线的交点,这个交点将线段分为两段,其中一段显然不可见,丢弃。对余下的另一段重新进行第一步,第二步判断,直至结束; -
编码判断
对一条线段的可见性测试方法:
(1)若线段两个端点的四位二进制编码全为0000,即两端点编码逻辑或运算为0,那么该线段完全位于窗口内,可直接保留;
(2)对两端点的四位二进制编码进行逻辑与运算,若结果不为零,那么整条线段必位于窗口外,可直接舍弃;
(3)否则,这条线段既不能直接保留,也不能直接舍弃,它可能与窗口相交。此时,需要对线段进行再分割,即找到与窗口边线的一个交点,根据交点位置,赋予四位二进制编码,并对分割后的线段按照一定的顺序(如左右下上)进行检查,决定保留、舍弃或再次进行分割。重复这一过程,直到全部线段均被舍弃或保留为止。
三、多边形裁剪
3.2 Sutherland-Hodgman算法
- 思路:用窗口的四条边所在的直线依次裁剪多边形。窗口的每条边所在直线将二维平面分成两部分,包含窗口一部分为内侧,称为可见侧,另一部分不包含窗口,称为外侧,称不可见侧。
以窗口左边界为例我们看一下四种情况如何进行处理。假设当前处理的多边形的边为SP;
- 栽剪过程
(1)使用左边栽剪,计算以及与左边框的交点和。保留可见侧和并重新编号各顶点,得到裁剪结果(a)
(2)使用上边栽剪,计算以及与上边框的交点和。保留可见侧和并重新编号各顶点,得到裁剪结果(b)
(3)使用右边栽剪,计算以及与上边框的交点和。保留可见侧和并重新编号各顶点,得到裁剪结果(c)
(4)使用下边栽剪,计算以及与上边框的交点和。保留可见侧和并重新编号各顶点,得到裁剪结果(d)
(5)依次连接各顶点得到栽剪完的多边形(e)
- 特点:裁剪算法采用流水线方式,适合硬件实现,可推广到任意凸多边形裁剪窗口;
- 问题:一个凹多边形可能被裁剪成几个小的多边形,如何确定这些小多边形的边界?
输入顶点BAFEDC,输出顶点:V1 A V2 V3 E D V4
3.3 Weiler-Athenton算法
- 裁剪窗口为任意多边形(凸、凹、带内环)的情况;
- 原理:可以用一个有内孔的凹多边形去裁剪另一个也有内孔的凹多边形。各多边形的外部边界取顺时针方向,而其内部边界或孔取逆时针方向。因此,沿多边形的一条边走动,其右边为多边形的内部。
- 基本概念:
(1)被裁剪的多边形称为主多边形 PS;
(2)裁剪窗口称为裁剪多边形 PW;
(3)主多边形和裁剪多边形的边界若相交,交点必定成对地出现,其中一个交点为主多边形边进入裁剪多边形内部时的交点(称进点),另一个交点则为离开时的交点(称出点)。这两类交点分别用进点表和出点表来存放。 - 思想:从Ps的任一顶点出发,跟踪检测PS的每一条边,当PS与Pw的有效边相交时,按如下规则处理:
(1)若Ps的边进入Pw,则输出可见直线段,沿Ps的边继续。
(2)若Ps的边从Pw出来, Ps与Pw交点为前交点,输出Ps中到前交点的可见部分,从前交点开始,沿窗口边界顺时针检测Pw的边,找到Ps与Pw最靠近前交点的新交点,同时输出由前交点以此新交点这间窗边上的线段。
(3)返回前交点,再沿Ps处理各条边,直到处理完Ps的所有边,回到起点为止。 - 交点的奇异情况处理
(1)与裁剪多边形边重合的主多边形的边不参与求交点;
(2)对于顶点落在裁剪多边形的边上的主多边的边,如果落在该裁剪边的内侧,将该顶点算作交点;而如果这条边落在该裁剪边的外侧,将该顶点不看作交点
四、字符裁剪方法
4.1 字符的裁剪
- 简单裁剪方法:用点阵字符的掩膜或矢量字符的网格大小作为字符的包围框,若该包围框在窗口内,则显示字符;否则,不予显示。
- 精确裁剪方法:对于点阵字符,判断组成其笔画的每个像素点是否位于窗口内。对于矢量字符,对组成其笔画的每条线段进行裁剪。
4.2 字符串的剪裁
字符串剪裁3种可选择的方法。
- 串精度裁剪
- 字符精度裁剪
- 字符的精密(笔画、像素精度)剪裁
4.3 凸包
- 引入:为了减少计算量,在进行真正的求交计算之前,往往先用凸包等辅助结构进行粗略地比较,排除那些显然不相交的情形。
2.定义:一个图形的凸包,就是包含这个图形的凸区域(凸多边形、凸多面体),它不是唯一的。