图形学学习笔记4——平面图形裁剪

平面图形裁剪

基础概念

空间中的图形尺寸任意，显示设备尺寸有限，如何判断图形哪些部分在显示区外，哪些部分在显示区内这一过程就是对图形的裁剪。

当有大量图形需要显示时，裁剪就很耗时，在软件裁剪速度无法达到要求时，可以用硬件加速。

直线裁剪

求出所属直线与各个边界的交点，通过交点是在边界上还是在延长线上，判断线段哪部分在区域内。

科恩-萨塞兰德算法

适用于矩形窗口的直线裁剪。将窗口四条边所属直线分割成的9个区域编码，每条直线内侧（窗口一侧）编码0，外侧1.

将线段两个端点的编码作如下判断：

1. 若编码都是0，则两点都可见。
2. 作与运算，如果非0，说明至少在某条直线的外侧，肯定不在显示区。
3. 否则需要进一步判断，计算线段与边界的交点，交点将线段分为两段，一段肯定不可见，舍去，继续判断另一段，重复1.

该方法需要求直线交点，需要精确计算。

中点分割法

在科恩-萨塞兰德算法算法中第3步需要计算交点对线段分割，如果直接用中点分割，可移位操作。中点分割后的对两段分别再判断。精度到一定范围内，停止分割。
对编码方式无法判断线段完全在区域内或区域外的情形，计算中点，中点有如下情况：

1. 若中点在边界或区域外，那么分割出来的两段线段中，一定有一段在区域外，舍去。继续判断另一段。
2. 若中点在区域内 且 有一个端点在区域内，那么其中一段完全可见，另一段继续判断。
3. 若中点在区域内 且 两个端点都在区域外，那么该线段与边界有两个交点，分别对两段继续分割。
4. 若分割的线段长度小于精度阈值，此时就认定中点即为交点。

梁友栋-Barsky算法

基本思想：对于非水平或竖直的直线，如果穿过矩形区域，则有必定有先穿过一组横纵边界所在直线，再穿过另一组横纵边界所在实现。

如上图所示线段pq所在直线与边界直线交于a,b,c,d四个点。如果直线是水平或竖直，很容易计算裁剪区域，此处只考虑斜线。

此处只考虑k>０的情形（k<0类似推到），如果该线段有部分在区域内。必定先经过两条直线 lleft和lbottom ，再经过两条直线 lright和ltop 。设线段两端点 xp<xq ，定义一个正方向 p→q ， Δx=xq−xp ， Δy=yq−yp 。该直线用参数表示为：

{xy=xp+tΔx=yp+tΔy

其中 tp=0 。 tq=1 ，表示点ｑ。 ti(i=left,right,bottom,top) 表示 li 与直线的交点。那么 直线与区域相交的 充要条件

t1=max(tleft,tbottom)<t2=min(tright,ttop)

t1 和 t2 代表的点是直线在区域内裁剪线段的前后端点，该线段和线段pq相交就表示线段pq能在区域内显示。
1. 若 tp>t2 或者　 tq<t1 :　pq在完全在区域外.
2. 若 tp<=t1 时：如果 t1<tq<=t2 ， pointt1q 为裁剪后的线段,如果 t2<tq ， pointt1pointt2 是裁剪后的线段。
3. 若 t1<tp<t2 时： 如果 tq>t2 ， ppointt2 是裁剪后的线段。如果 tq<t2 ，则为pq.

多边形裁剪

逐边裁剪法

用窗口边界的四条直线一次对多边形进行裁剪。
直线裁剪中中我们通过编码方式可以很容易判断点是否在边界直线的窗口侧还是非窗口侧。
用一条边界直线进行裁剪：从窗口侧一个点出发，沿着多边形的边依次判断是否与直线相交，若相交则求出交点，进入非窗口侧，直到下一次交点时进入窗口侧，最终回到出发点。这样就可以裁剪掉窗口外侧的。
注意：若边与直线平行，边的两个端点可视为同一个点。

多边形双边裁剪法

有时窗口并非规则的矩形，也会有内部有空的多边形。由Weiler和Atherton提出的双边裁剪法可以解决该问题。
Wikipedia:Weiler–Atherton clipping algorithm

• 定义边的正方向：外部边界顺时针，内部边界逆时针，保证窗口区域始终在边的右侧。被裁剪多边形也市顺时针。
• 窗口多边形称为主多边形。目标就是找到主多边形和被裁剪多边形的重叠区域。
• 被裁剪多边形和主多边形的交点总是成对出现，一个入点，必有一个出点。

首先找出裁剪多边形和窗口交点以及交点类型：

1. 若一条裁剪多边形的边与一条主多边形的边相交，计算交点，根据顺时针和逆时针判断是入点还是出点。
2. 若平行，则这条边起点不看做交点。
3. 若裁剪多边形一边的交点在主多边形一条边上，看该边的终点在主多边形这条边的内侧还是外侧，内侧入点，外侧出点。

裁剪步骤：

1. 建立主多边形和裁剪多边形各自的环形顶点表,外边界顶点顺时针次序存放,内边界顶点逆时针次序存放,并且每个边界顶点表中最后一个是第一个的重复。
2. 计算主多边形各边和裁剪多边形各边的交点,对每个交点标号,并插入到两个多边形的顶点表中,对同一交点,在主多边形和裁剪多边形的顶点表之间建立双向指针。
3. 第三步: 建立两类交点表,即进入交点表和离开交点表。进入交点表存放主多边形进入裁剪多边形时产生的交点,离开交点表存放主多边形离开裁剪多边形时产生的交点,沿着多边形边界,两类交点将交替出现,因此只要测试其中一个即可决定所有交点的类型。
4. 建立两个装入表,存放裁剪后多边形的顶点。其中一个称为窗内装
   入表,存放位于裁剪多边形内部的多边形,另一个称为窗外装入表,存放位于裁剪多边形外部的多边形。建立这两个表,可根据主多边形和裁剪窗口的关系来进行。

确定裁剪多边形内的主多边形过程如下:

1. 从进入交点表中取出一交点,如果该交点没有处理过,则执行以下操作,否则取出下一个交点,直至表空过程结束。
2. 沿着主多边形顶点表正向查找直到发现下一个交点,将主多边形顶点表中到该交点为止的部分复制到窗内装入表中。
3. 把连接指针转到裁剪多边形的顶点表中。
4. 沿裁剪多边形顶点表正向查找直到发现下一个交点,将裁剪多边形顶点表中到该交点为止的部分复制到窗内装入表中。
5. 把连接指针转回至主多边形顶点表。
6. 重复步骤(2)到(5)直到回到过程开始的进入交点、此时在窗内装入表中存放了裁剪后在窗内的封闭多边形顶点表。
7. 转到步骤(1)寻找可能的其它窗内封闭多边形。

文本裁剪

文本裁剪根据裁剪精细程度分为:1.字符串裁剪。2.字符裁剪。3.笔划裁剪。

• 字符串裁剪：得到字符串的外包围矩形，若矩形并非完全在区域内，则舍弃。这样虽然速度快，但裁剪太多内容。
• 字符裁剪：得到字符的外包围矩形，判断是否完全在区域内。
• 笔划裁剪：笔划看做一些点和线的集合，按点和先的裁剪规则进行裁剪。这种方法精度高，但需要直到笔划结构，计算量更大。

---

该系列学习笔记主要参考 郑州师范大学 柳朝阳的《计算机图形学的概念与方法》，如需要查阅更详细的公式推导，可参考原著。