浙江大学信息学院 计算机图形学裁剪算法反走样方法第五章 裁剪、反走样方法浙江大学信息学院 计算机图形学二维裁剪直线段裁剪直接求交算法
Cohen-Sutherland算法中点分割算法参数化裁剪算法
Liang-Barskey算法多边形裁剪
Sutlerland_Hodgman算法
Weiler-Athenton算法浙江大学信息学院 计算机图形学裁剪
裁剪,确定图形中哪些部分落在显示区之内，
哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为 裁剪 。
图形裁剪算法，直接影响图形系统的效率。
浙江大学信息学院 计算机图形学点的裁剪
图形裁剪中最基本的问题。
假设窗口的左下角坐标为
(xL,yB),右上角坐标为
(xR,yT)，对于给定点 P(x,y),
则 P点在窗口内的条件是要满足下列不等式：
xL <= x <= xR
并且 yB <= y <= yT
否则,P点就在窗口外。
问题：对于任何多边形窗口，
如何判别？
(xL,yB )
(xR,yT )
浙江大学信息学院 计算机图形学直线段裁剪
直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。
直接求交算法
Cohen-Sutherland算法中点算法梁友栋－ barskey算法参数化裁剪算法浙江大学信息学院 计算机图形学直线段裁剪
裁剪线段与窗口的关系,(1)线段完全可见； (2)
显然不可见； (3)其它
提高裁剪效率：
快速判断情形 (1)(2)，
对于情形 (3)，设法减少求交次数和每次求交时所需的计算量。
浙江大学信息学院 计算机图形学直接求交算法直线与窗口边都写成参数形式，
求参数值。
浙江大学信息学院 计算机图形学
Cohen-Sutherland裁剪
基本思想：
对于每条线段 P1P2分为三种情况处理,
（ 1）若 P1P2完全在窗口内，则显示该线段 P1P2。
（ 2）若 P1P2明显在窗口外，则丢弃该线段。
（ 3）若线段不满足（ 1）或（ 2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。
为快速判断，采用如下编码方法：
浙江大学信息学院 计算机图形学实现方法：
将窗口边线两边沿长，得到九个区域，每一个区域都用一个四位二进制数标识，直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。
1001
0001
0101
1000
0000
0100
1010
0010
0110
A
B
C
D
Cohen-Sutherland裁剪
Cohen-Sutherland算法
将区域码的各位从右到左编号，则坐标区域与各位的关系为：
上 下 右 左
X X X X
任何位赋值为 1，代表端点落在相应的位置上，否则该位为 0。若端点在剪取矩形内，区域码为 0000。如果端点落在矩形的左下角，则区域码为 0101。
Cohen-Sutherland算法一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律：
浙江大学信息学院 计算机图形学
Cohen-Sutherland裁剪
– 若 P1P2完全在窗口内 code1=0,且 code2=0,则,取,
– 若 P1P2明显在窗口外 code1&code2≠0,则,弃,
– 在交点处把线段分为两段。其中一段完全在窗口外，
可弃之。然后对另一段重复上述处理。
– 编码 线段裁剪
1001 1000 1010
0001 0000 0010
0101 0100 0110
P1
P2
P3
P4
浙江大学信息学院 计算机图形学
Cohen-Sutherland裁剪如何判定应该与窗口的哪条边求交呢？
编码中对应位为 1的边。
计算线段 P1(x1,y1)P2(x2,y2)与窗口边界的交点
if(LEFT&code !=0)
{ x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);}
else if(RIGHT&code !=0)
{ x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);}
else if(BOTTOM&code !=0)
{ y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);}
else if(TOP & code !=0)
{ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);}
具体算法见 p201
浙江大学信息学院 计算机图形学
Cohen-Sutherland
直线裁剪算法小结
本算法的优点在于简单，易于实现。他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，
剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。另外，本算法对于其他形状的窗口未必同样有效。
特点：用编码方法可快速判断线段的完全可见和显然不可见。
浙江大学信息学院 计算机图形学中点分割裁剪算法
基本思想,从 P0点出发找出离 P0最近的可见点，和从 P1
点出发找出离 P1最近的可见点。这两个可见点的连线就是原线段的可见部分。
与 Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。 A,B分别为距 P0,
P1最近的可见点,Pm为 P0P1中点。
P0
P1
Pm
A
B
浙江大学信息学院 计算机图形学中点分割算法 -求线段与窗口的交点
从 P0出发找距离 P0最近可见点采用中点分割方法
– 先求出 P0P1的中点 Pm,
– 若 P0Pm不是显然不可见的，并且 P0P1在窗口中有可见部分，则距 P0最近的可见点一定落在 P0Pm上，所以用
P0Pm代替 P0P1；
– 否则取 PmP1代替 P0P1。
– 再对新的 P0P1求中点 Pm。重复上述过程，直到 PmP1长度小于给定的控制常数为止，此时 Pm收敛于交点。
从 P1出发找距离 P1最近可见点采用上面类似方法。
P0
P1
Pm
A
B
浙江大学信息学院 计算机图形学中点分割裁剪算法浙江大学信息学院 计算机图形学
对分辩率为 2N*2N的显示器，上述二分过程至多进行 N次。
主要过程只用到加法和除法运算，适合硬件实现,它可以用左右移位来代替乘除法，这样就大大加快了速度 。
中点分割裁剪算法浙江大学信息学院 计算机图形学设要裁剪的线段是 P0P1。 P0P1和窗口边界交于 A,B,C,D四点，见图。
算法的基本思想是从 A,B和 P0三点中找出最靠近的 P1点，图中要找的点是 P0。从 C,D和 P1中找出最靠近 P0的点。图中要找的点是 C点。那么 P0C
就是 P0P1线段上的可见部分。
梁友栋 -Barsky算法浙江大学信息学院 计算机图形学梁友栋 -Barsky算法线段的 参数表示
x=x0+t△ x
y=y0+t△ y 0<=t<=1
△ x=x1-x0 △ y=y1-y0
窗口边界的四条边分为两类：始边和终边。
为始边。为终边，若为终边。为始边，若为始边。为终边，若为终边。为始边，若
TB
TB
RL
RL
yyyyy
yyyyy
xxxxx
xxxxx
0
0
0
0
浙江大学信息学院 计算机图形学
– 求出 P0P1与两条始边的交点参数 t0,t1,令 tl=max(t0,t1,0)，
则 tL即为三者中离 p1最近的点的参数
– 求出 p0p1与两条终边的交点参数 t2,t3,令 tu=min(t2,t3,1),
则 tU即为三者中离 p0最近的点的参数
– 若 tu > tl,则可见线段区间
[tl,tu]
t0 t1
t2 t3
0
1
梁友栋 -Barsky算法,交点计算浙江大学信息学院 计算机图形学梁友栋 -Barsky算法始边和终边的确定及交点计算：
令 QL= - △ x DL= x0-xL
QR= △ x DR= xR-x0
QB= - △ y DB= y0-yB
QT= △ y DT= yT-y0
交点为 ti= Di / Qi i=L,R,B,T
Qi <0 ti为与始边交点参数
Qi >0 ti为与终边交点参数
Qi =0 Di <0 时,线段不可见
Di >0 时,分析另一 D,
E
F
A
B
浙江大学信息学院 计算机图形学梁友栋 -Barsky算法当 Qi =0时若 Di <0 时,线段不可见
（如图中 AB，有 QR=0,DR<0）
若 Di >0 时,分析另一 D,
（如图中的 EF就是这种情况，它使 QL=0,DL>0
和 QR=0,DR>0。这时由于 EF和 x=xL及 x=xR平行，
故不必去求出 EF和 x=xL及 x=xR的交点，而让 EF
和 y=yT及 y=yB的交点决定直线段上的可见部分。）
E
F
A
B
浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
考虑凸多边形区域 R和直线段 P1P2
P(t)=(P2-P1)*t+P1
设 A是区域 R的边界上一点,N是区域边界在
A点的内法线向量
A
P2
R
N
P1
浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
则对于线段 P1P2上任一点 P(t)
N ·(P(t)-A)<0->外侧
N ·(P(t)-A)>0->内侧
N ·(P(t)-A)=0->边界或其延长线上
A
P2
R
N
P1
浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
凸多边形的性质：点 P(t)在凸多边形内的充要条件是，对于凸多边形边界上任意一点 A和该点处内法向 N，都有
N·(P(t)-A)>0
浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
k条边的多边形，可见线段参数区间的解,
Ni· (p(t)-Ai)>=0,i=0,…,k,0≤t ≤1.
即,Ni· (P1-Ai)+ Ni· (P2-P1) t>=0 (1)式
可得：
令 ti= Ni· (P1-Ai)/[Ni· (P2-P1) ]
1212
12
1
12
12
1
12
0
0
0
PPNPPN
PPN
APN
tPPN
PPN
APN
tPPN
ii
i
ii
i
i
ii
i
浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
Ni· (P2-P1) =0-> 平行于对应边。
此时判断 Ni· (P1-Ai)
若 Ni· (P1-Ai) <0->P1 P2在多边形外侧 ->不可见，
若 Ni· (P1-Ai) >0->P1 P2在多边形内侧 ->继续其它边的判断浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
对于 t值的选择：首先，要符合 0≤t≤1 ；其次，对于凸窗口来说，每一个线段与其至多有两个交点，即有两个相应的 t值。所以我们可以把计算出的 t值分成两组：一组为下限组，是分布在线段起点一侧的；一组为上限组，是分布在线段终点一侧的。这样，只要找出下限组中的最大值及上限组中的最小值，就可确定线段了。
分组的依据是：
– 如果 Ni·(P2-P1) ＜ 0，则计算出的值属于上限组
– 如果 Ni·(P2-P1) ＞ 0，则计算出的值属于下限组浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
因此，线段可见的交点参数：
tl=max{0,max{ti,Ni· (P2-P1) >0}}
tu=min{1,min{ti,Ni· (P2-P1)<0}}
若 tl <= tu,[tl,tu]是可见线段的交点参数区间，否则，线段不可见。
浙江大学信息学院 计算机图形学下限上限
P1
P2
参数化算法的几何意义
下限组以 Ni· (P2-P1) >0为特征，表示在该处沿
P1P2方向前进将接近或进入多边形内侧。
上限组以 Ni·(P2-P1)
<0为特征，表示在该处沿 P1P2方向前进将越来越远地离开多边形区域。
浙江大学信息学院 计算机图形学参数化算法
当凸多边形是矩形窗口且矩形的边与坐标轴平行时，该算法退化为 Liang-Barsky
算法。
浙江大学信息学院 计算机图形学非矩形窗口的线段裁剪
Cyrus-Beck扩充到凸多边形
思考：
凹多边形窗口的线段裁剪
圆和曲线窗口的线段裁剪浙江大学信息学院 计算机图形学多边形裁剪
错觉,直线段裁剪的组合？
新的问题,1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？
浙江大学信息学院 计算机图形学多边形裁剪
2）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？
浙江大学信息学院 计算机图形学
Sutherland-Hodgman算法
分割处理策略,将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。
流水线过程 (左上右下 ),前边的结果是后边的输入 。
亦称 逐边裁剪算法浙江大学信息学院 计算机图形学
Sutherland-Hodgman算法
基本思想是一次用窗口的一条边裁剪多边形。
考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分,可见一侧；不可见一侧
多边形的各条边的两端点 S,P。它们与裁剪线的位置关系只有四种可见一侧可见一侧可见一侧可见一侧
S
p S
S Sp
p p
(1) (2) (3) (4)
浙江大学信息学院 计算机图形学
Sutherland-Hodgman算法
情况（ 1）仅输出顶点 P；
情况（ 2）输出 0个顶点；
情况（ 3）输出线段 SP与裁剪线的交点 I；
情况（ 4）输出线段 SP与裁剪线的交点 I和终点 P
可见一侧可见一侧可见一侧可见一侧
S
p S
S Sp
p p
(1) (2) (3) (4)
浙江大学信息学院 计算机图形学
Sutherland-Hodgman算法 框图处理线段 SP过程子框图浙江大学信息学院 计算机图形学
Sutherland-Hodgman算法
– 上述算法仅用一条裁剪边对多边形进行裁剪，
得到一个顶点序列，作为下一条裁剪边处理过程的输入。
– 对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段 SP与裁剪边的交点算法应随之改变。
浙江大学信息学院 计算机图形学
Sutherland-Hodgeman算法
对凸多边形应用本算法可以得到正确的结果，
但是对凹多边形的裁剪将如图所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。
解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再有就是 Weiler-Atherton算法。
浙江大学信息学院 计算机图形学
Sutherland-Hodgman算法思考：
如何推广到任意凸多边形
裁剪窗口？
浙江大学信息学院 计算机图形学
Weiler-Athenton算法裁剪窗口为任意多边形（ 凸、凹、带内环） 的情况：
– 主多边形：被裁剪多边形，记为 A
– 裁剪多边形：裁剪窗口，记为 B
浙江大学信息学院 计算机图形学
Weiler-Athenton算法多边形顶点的排列顺序（使多边形区域位于有向边的左侧 ）外环：逆时针 ；内环：顺时针
主多边形和裁剪多边形把二维平面分成两部分。
内裁剪,A∩B
外裁剪,A-B
裁剪结果区域的边界由 A的部分边界和 B的部分边界两部分构成，并且在交点处边界发生交替，即由 A的边界转至 B的边界，或由 B的边界转至 A的边界浙江大学信息学院 计算机图形学
Weiler-Athenton算法
– 如果主多边形与裁剪多边形有交点，则 交点成对出现,它们被分为如下两类：
进点,主多边形边界由此进入裁剪多边形内如,I1,I3,I5,I7,I9,I11
出点,主多边形边界由此离开裁剪多边形区域,
如,I0,I2,I4,I6,I8,I10
浙江大学信息学院 计算机图形学
Weiler-Athenton算法
1）建顶点表；
2）求交点；
3）裁剪 … …
1、建立主多边形和裁剪多边的顶点表．
2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针 。
3、裁剪,如果存在没有被跟踪过的交点，执行以下步骤：
浙江大学信息学院 计算机图形学
Weiler-Athenton算法浙江大学信息学院 计算机图形学
Weiler-Athenton算法
(1)建立空的裁剪结果多边形的顶点表．
(2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中．
(3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界．
(4) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点．
(5)将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界）．
(6)重复 (4),(5)直至回到起点
取 I7为起点，所得裁剪结果多边形
I7I0q0I3I4I5I6I7。取 I8为起点，所得裁剪结果多边形为 I8I9I10I11I2q2I1I8。
浙江大学信息学院 计算机图形学
Weiler-Athenton算法
– 交点的奇异情况处理
1、与裁剪多边形的边重合的主多边形的边不参与求交点；
2、对于顶点落在裁剪多边形的边上的主多边形的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点浙江大学信息学院 计算机图形学反走样
用离散量表示连续量引起的失真现象 称之为 走样
(aliasing) 。
光栅图形的走样现象
– 阶梯状边界；
– 图形细节失真；
– 狭小图形遗失：动画序列中时隐时现，产生闪烁。
浙江大学信息学院 计算机图形学走样现象举例
不光滑 (阶梯状）的图形边界例子,PaintBrush
浙江大学信息学院 计算机图形学走样现象举例
图形细节失真浙江大学信息学院 计算机图形学走样现象举例
狭小图形的遗失与动态图形的闪烁浙江大学信息学院 计算机图形学反走样概念及方法
用于减少或消除走样现象的技术称为 反走样 (antialiasing)
提高分辨率
简单区域取样
加权区域取样浙江大学信息学院 计算机图形学提高分辨率
把显示器分辨率提高一倍，
– 直线经过两倍的象素，锯齿也增加一倍，
– 但同时每个阶梯的宽度也减小了一倍，
– 所以显示出的直线段看起来就平直光滑了一些。
浙江大学信息学院 计算机图形学提高分辨率
方法简单，但代价非常大。显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的 4倍，而扫描转换同样大小的图元却要花 4倍时间。
而且它也只能减轻而不能消除锯齿问题另一种方法（软件方法）：
用较高的分辨率的显示模式下计算，（对各自像属下计算，再求（非）加权平均的颜色值），
在较低的分辨率模式下显示。 只能减轻而不能消除锯齿问题。
浙江大学信息学院 计算机图形学软件方法 1
把每个像素分为四个子像素,扫描转换算法求得各子像素的灰度值,然后对四像素的灰度值简单平均,作为该像素的灰度值 。
浙江大学信息学院 计算机图形学软件方法 2
设 分 辨 率 为 m?n,把 显 示 窗 口 分 为
(2m+1)?(2n+1)个子像素,对每个子像素进行灰度值计算,然后根据权值表所规定的权值,对位于像素中心及四周的九个子像素加权平均,作为显示像素的颜色 。
设 m=4,n=3
浙江大学信息学院 计算机图形学简单区域取样
方法由来
– 两点假设
1,象素是数学上抽象的点,它的面积为 0,它的亮度由覆盖该点的图形的亮度所决定；
2、直线段是数学上抽象直线段，它的宽度为 0。
– 现实
像素的面积不为 0；
直线段的宽度至少为 1个像素；
– 假设与现实的矛盾是导致混淆出现的原因之一浙江大学信息学院 计算机图形学简单区域取样
– 解决方法：改变直线段模型，由此产生算法
– 方法步骤,
1、将直线段看作具有一定宽度的狭长矩形；
2、当直线段与某象素有交时，求出两者相交区域的面积；
3、根据相交区域的面积，确定该象素的亮度值浙江大学信息学院 计算机图形学简单区域取样
基本思想：
– 每个象素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与象素有交时，
求出两者相交区域的面积，然后根据相交区域面积的大小确定该象素的亮度值。
有宽度的线条轮廓 象素相交的五种情况及用于计算面积的量
0 1
1
2
2 3
3
4
4 5
5
6 7 8 9 10 11
D
D / m
D
m
(1) (2) (3) (4) (5)
浙江大学信息学院 计算机图形学简单区域取样
面积计算
– 情况⑴（ 5)阴影面积为,D2/2m；
– 情况⑵（ 4)阴影面积为,D - m/2；
– 情况⑶阴影面积为,1 - D2/m
为了简化计算可以采用离散的方法浙江大学信息学院 计算机图形学简单区域取样
– 求相交区域的近似面积的离散计算方法
1、将屏幕象素分割成 n个更小的子象素；
2、计算中心点落在直线段内的子象素的个数，记为 k，
3,k/n为线段与象素相交区域面积的近似值目的：简化计算
n = 16,k = 3
近似面积 = 3/16
浙江大学信息学院 计算机图形学简单区域取样
简单区域取样采用的是一个盒式滤波器，
它是一个二维加权函数，以 w表示。
w =1 若在当前像素所代表的正方形上
w =0 其它区域上
直线条经过该像素时，该像素的灰度值可以通过在像素与直线条的相交区域上对 w求积分获得。
此时，面积值 =体积值浙江大学信息学院 计算机图形学简单区域取样
– 缺点：
– 象素的亮度与相交区域的面积成正比，
而与相交区域落在象素内的位置无关，
这仍然会导致锯齿效应。
– 直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差。
浙江大学信息学院 计算机图形学加权区域取样
采用圆锥形滤波器，圆锥的底圆中心在当前像素，底圆半径为一个像素，锥高为 1。当直线条经过该像素时，该像素的灰度值是在二者相交区域上对滤波器进行积分的积分值。
见 p213的图 4.7.9
浙江大学信息学院 计算机图形学加权区域取样
特点：
接近理想直线的像素将被分配更多的灰度值。
相邻的两个像素的滤波器相交，有利于缩小直线条上相邻像素的灰度差。
具体算法见 p213
浙江大学信息学院 计算机图形学半色调技术
简单区域取样和加权区域取样技术的前提是多级灰度,利用多级灰度来提高视觉分辨率 。 但是,若只有两级灰度呢？
能否使用上述技术呢？
对于给定的分辨率,通过将几个像素组合成一个单元来获得多级灰度 。
例：在一个显示器中将四个像素组成一个单元,可产生 5种光强 。
浙江大学信息学院 计算机图形学半色调技术
可用如下矩阵来表示：
它表示黑色像素填入 2?2个位置中的次序,每一级灰度再添上一个黑色像素就得到下一级灰度 。
注意：
1,要尽量避免连成一条直线的花样 。
2,花样是可以选择的 。
单元也可以是长方形,如
42
13
236
514
浙江大学信息学院 计算机图形学半色调技术
一般来说,对于两级灰度显示器可能构成的灰度数等于单元中像素个数加 1
∴ 单元越大,灰度级别越高
它是以牺牲空间分辨率为代价的 。
浙江大学信息学院 计算机图形学半色调技术
例：灰度级别 =4,每个单元 =2*2
若有 m级灰度,n?n个像素组成一个单元,则灰度级别数为 n?n?(m-1)+1
Cohen-Sutherland算法中点分割算法参数化裁剪算法
Liang-Barskey算法多边形裁剪
Sutlerland_Hodgman算法
Weiler-Athenton算法浙江大学信息学院 计算机图形学裁剪
裁剪,确定图形中哪些部分落在显示区之内，
哪些落在显示区之外,以便只显示落在显示区内的那部分图形。这个选择过程称为 裁剪 。
图形裁剪算法，直接影响图形系统的效率。
浙江大学信息学院 计算机图形学点的裁剪
图形裁剪中最基本的问题。
假设窗口的左下角坐标为
(xL,yB),右上角坐标为
(xR,yT)，对于给定点 P(x,y),
则 P点在窗口内的条件是要满足下列不等式：
xL <= x <= xR
并且 yB <= y <= yT
否则,P点就在窗口外。
问题：对于任何多边形窗口，
如何判别？
(xL,yB )
(xR,yT )
浙江大学信息学院 计算机图形学直线段裁剪
直线段裁剪算法是复杂图形裁剪的基础。复杂的曲线可以通过折线段来近似，从而裁剪问题也可以化为直线段的裁剪问题。
直接求交算法
Cohen-Sutherland算法中点算法梁友栋－ barskey算法参数化裁剪算法浙江大学信息学院 计算机图形学直线段裁剪
裁剪线段与窗口的关系,(1)线段完全可见； (2)
显然不可见； (3)其它
提高裁剪效率：
快速判断情形 (1)(2)，
对于情形 (3)，设法减少求交次数和每次求交时所需的计算量。
浙江大学信息学院 计算机图形学直接求交算法直线与窗口边都写成参数形式，
求参数值。
浙江大学信息学院 计算机图形学
Cohen-Sutherland裁剪
基本思想：
对于每条线段 P1P2分为三种情况处理,
（ 1）若 P1P2完全在窗口内，则显示该线段 P1P2。
（ 2）若 P1P2明显在窗口外，则丢弃该线段。
（ 3）若线段不满足（ 1）或（ 2）的条件，则在交点处把线段分为两段。其中一段完全在窗口外，可弃之。然后对另一段重复上述处理。
为快速判断，采用如下编码方法：
浙江大学信息学院 计算机图形学实现方法：
将窗口边线两边沿长，得到九个区域，每一个区域都用一个四位二进制数标识，直线的端点都按其所处区域赋予相应的区域码，用来标识出端点相对于裁剪矩形边界的位置。
1001
0001
0101
1000
0000
0100
1010
0010
0110
A
B
C
D
Cohen-Sutherland裁剪
Cohen-Sutherland算法
将区域码的各位从右到左编号，则坐标区域与各位的关系为：
上 下 右 左
X X X X
任何位赋值为 1，代表端点落在相应的位置上，否则该位为 0。若端点在剪取矩形内，区域码为 0000。如果端点落在矩形的左下角，则区域码为 0101。
Cohen-Sutherland算法一旦给定所有的线段端点的区域码，就可以快速判断哪条直线完全在剪取窗口内，哪条直线完全在窗口外。所以得到一个规律：
浙江大学信息学院 计算机图形学
Cohen-Sutherland裁剪
– 若 P1P2完全在窗口内 code1=0,且 code2=0,则,取,
– 若 P1P2明显在窗口外 code1&code2≠0,则,弃,
– 在交点处把线段分为两段。其中一段完全在窗口外，
可弃之。然后对另一段重复上述处理。
– 编码 线段裁剪
1001 1000 1010
0001 0000 0010
0101 0100 0110
P1
P2
P3
P4
浙江大学信息学院 计算机图形学
Cohen-Sutherland裁剪如何判定应该与窗口的哪条边求交呢？
编码中对应位为 1的边。
计算线段 P1(x1,y1)P2(x2,y2)与窗口边界的交点
if(LEFT&code !=0)
{ x=XL; y=y1+(y2-y1)*(XL-x1)/(x2-x1);}
else if(RIGHT&code !=0)
{ x=XR; y=y1+(y2-y1)*(XR-x1)/(x2-x1);}
else if(BOTTOM&code !=0)
{ y=YB; x=x1+(x2-x1)*(YB-y1)/(y2-y1);}
else if(TOP & code !=0)
{ y=YT; x=x1+(x2-x1)*(YT-y1)/(y2-y1);}
具体算法见 p201
浙江大学信息学院 计算机图形学
Cohen-Sutherland
直线裁剪算法小结
本算法的优点在于简单，易于实现。他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，
剩余部分就是可见的了。在这个算法中求交点是很重要的，他决定了算法的速度。另外，本算法对于其他形状的窗口未必同样有效。
特点：用编码方法可快速判断线段的完全可见和显然不可见。
浙江大学信息学院 计算机图形学中点分割裁剪算法
基本思想,从 P0点出发找出离 P0最近的可见点，和从 P1
点出发找出离 P1最近的可见点。这两个可见点的连线就是原线段的可见部分。
与 Cohen-Sutherland算法一样首先对线段端点进行编码，并把线段与窗口的关系分为三种情况，对前两种情况，进行一样的处理；对于第三种情况，用中点分割的方法求出线段与窗口的交点。 A,B分别为距 P0,
P1最近的可见点,Pm为 P0P1中点。
P0
P1
Pm
A
B
浙江大学信息学院 计算机图形学中点分割算法 -求线段与窗口的交点
从 P0出发找距离 P0最近可见点采用中点分割方法
– 先求出 P0P1的中点 Pm,
– 若 P0Pm不是显然不可见的，并且 P0P1在窗口中有可见部分，则距 P0最近的可见点一定落在 P0Pm上，所以用
P0Pm代替 P0P1；
– 否则取 PmP1代替 P0P1。
– 再对新的 P0P1求中点 Pm。重复上述过程，直到 PmP1长度小于给定的控制常数为止，此时 Pm收敛于交点。
从 P1出发找距离 P1最近可见点采用上面类似方法。
P0
P1
Pm
A
B
浙江大学信息学院 计算机图形学中点分割裁剪算法浙江大学信息学院 计算机图形学
对分辩率为 2N*2N的显示器，上述二分过程至多进行 N次。
主要过程只用到加法和除法运算，适合硬件实现,它可以用左右移位来代替乘除法，这样就大大加快了速度 。
中点分割裁剪算法浙江大学信息学院 计算机图形学设要裁剪的线段是 P0P1。 P0P1和窗口边界交于 A,B,C,D四点，见图。
算法的基本思想是从 A,B和 P0三点中找出最靠近的 P1点，图中要找的点是 P0。从 C,D和 P1中找出最靠近 P0的点。图中要找的点是 C点。那么 P0C
就是 P0P1线段上的可见部分。
梁友栋 -Barsky算法浙江大学信息学院 计算机图形学梁友栋 -Barsky算法线段的 参数表示
x=x0+t△ x
y=y0+t△ y 0<=t<=1
△ x=x1-x0 △ y=y1-y0
窗口边界的四条边分为两类：始边和终边。
为始边。为终边，若为终边。为始边，若为始边。为终边，若为终边。为始边，若
TB
TB
RL
RL
yyyyy
yyyyy
xxxxx
xxxxx
0
0
0
0
浙江大学信息学院 计算机图形学
– 求出 P0P1与两条始边的交点参数 t0,t1,令 tl=max(t0,t1,0)，
则 tL即为三者中离 p1最近的点的参数
– 求出 p0p1与两条终边的交点参数 t2,t3,令 tu=min(t2,t3,1),
则 tU即为三者中离 p0最近的点的参数
– 若 tu > tl,则可见线段区间
[tl,tu]
t0 t1
t2 t3
0
1
梁友栋 -Barsky算法,交点计算浙江大学信息学院 计算机图形学梁友栋 -Barsky算法始边和终边的确定及交点计算：
令 QL= - △ x DL= x0-xL
QR= △ x DR= xR-x0
QB= - △ y DB= y0-yB
QT= △ y DT= yT-y0
交点为 ti= Di / Qi i=L,R,B,T
Qi <0 ti为与始边交点参数
Qi >0 ti为与终边交点参数
Qi =0 Di <0 时,线段不可见
Di >0 时,分析另一 D,
E
F
A
B
浙江大学信息学院 计算机图形学梁友栋 -Barsky算法当 Qi =0时若 Di <0 时,线段不可见
（如图中 AB，有 QR=0,DR<0）
若 Di >0 时,分析另一 D,
（如图中的 EF就是这种情况，它使 QL=0,DL>0
和 QR=0,DR>0。这时由于 EF和 x=xL及 x=xR平行，
故不必去求出 EF和 x=xL及 x=xR的交点，而让 EF
和 y=yT及 y=yB的交点决定直线段上的可见部分。）
E
F
A
B
浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
考虑凸多边形区域 R和直线段 P1P2
P(t)=(P2-P1)*t+P1
设 A是区域 R的边界上一点,N是区域边界在
A点的内法线向量
A
P2
R
N
P1
浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
则对于线段 P1P2上任一点 P(t)
N ·(P(t)-A)<0->外侧
N ·(P(t)-A)>0->内侧
N ·(P(t)-A)=0->边界或其延长线上
A
P2
R
N
P1
浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
凸多边形的性质：点 P(t)在凸多边形内的充要条件是，对于凸多边形边界上任意一点 A和该点处内法向 N，都有
N·(P(t)-A)>0
浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
k条边的多边形，可见线段参数区间的解,
Ni· (p(t)-Ai)>=0,i=0,…,k,0≤t ≤1.
即,Ni· (P1-Ai)+ Ni· (P2-P1) t>=0 (1)式
可得：
令 ti= Ni· (P1-Ai)/[Ni· (P2-P1) ]
1212
12
1
12
12
1
12
0
0
0
PPNPPN
PPN
APN
tPPN
PPN
APN
tPPN
ii
i
ii
i
i
ii
i
浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
Ni· (P2-P1) =0-> 平行于对应边。
此时判断 Ni· (P1-Ai)
若 Ni· (P1-Ai) <0->P1 P2在多边形外侧 ->不可见，
若 Ni· (P1-Ai) >0->P1 P2在多边形内侧 ->继续其它边的判断浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
对于 t值的选择：首先，要符合 0≤t≤1 ；其次，对于凸窗口来说，每一个线段与其至多有两个交点，即有两个相应的 t值。所以我们可以把计算出的 t值分成两组：一组为下限组，是分布在线段起点一侧的；一组为上限组，是分布在线段终点一侧的。这样，只要找出下限组中的最大值及上限组中的最小值，就可确定线段了。
分组的依据是：
– 如果 Ni·(P2-P1) ＜ 0，则计算出的值属于上限组
– 如果 Ni·(P2-P1) ＞ 0，则计算出的值属于下限组浙江大学信息学院 计算机图形学参数化算法 (Cyrus-Beck)
因此，线段可见的交点参数：
tl=max{0,max{ti,Ni· (P2-P1) >0}}
tu=min{1,min{ti,Ni· (P2-P1)<0}}
若 tl <= tu,[tl,tu]是可见线段的交点参数区间，否则，线段不可见。
浙江大学信息学院 计算机图形学下限上限
P1
P2
参数化算法的几何意义
下限组以 Ni· (P2-P1) >0为特征，表示在该处沿
P1P2方向前进将接近或进入多边形内侧。
上限组以 Ni·(P2-P1)
<0为特征，表示在该处沿 P1P2方向前进将越来越远地离开多边形区域。
浙江大学信息学院 计算机图形学参数化算法
当凸多边形是矩形窗口且矩形的边与坐标轴平行时，该算法退化为 Liang-Barsky
算法。
浙江大学信息学院 计算机图形学非矩形窗口的线段裁剪
Cyrus-Beck扩充到凸多边形
思考：
凹多边形窗口的线段裁剪
圆和曲线窗口的线段裁剪浙江大学信息学院 计算机图形学多边形裁剪
错觉,直线段裁剪的组合？
新的问题,1）边界不再封闭，需要用窗口边界的恰当部分来封闭它，如何确定其边界？
浙江大学信息学院 计算机图形学多边形裁剪
2）一个凹多边形可能被裁剪成几个小的多边形，如何确定这些小多边形的边界？
浙江大学信息学院 计算机图形学
Sutherland-Hodgman算法
分割处理策略,将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。
流水线过程 (左上右下 ),前边的结果是后边的输入 。
亦称 逐边裁剪算法浙江大学信息学院 计算机图形学
Sutherland-Hodgman算法
基本思想是一次用窗口的一条边裁剪多边形。
考虑窗口的一条边以及延长线构成的裁剪线该线把平面分成两个部分,可见一侧；不可见一侧
多边形的各条边的两端点 S,P。它们与裁剪线的位置关系只有四种可见一侧可见一侧可见一侧可见一侧
S
p S
S Sp
p p
(1) (2) (3) (4)
浙江大学信息学院 计算机图形学
Sutherland-Hodgman算法
情况（ 1）仅输出顶点 P；
情况（ 2）输出 0个顶点；
情况（ 3）输出线段 SP与裁剪线的交点 I；
情况（ 4）输出线段 SP与裁剪线的交点 I和终点 P
可见一侧可见一侧可见一侧可见一侧
S
p S
S Sp
p p
(1) (2) (3) (4)
浙江大学信息学院 计算机图形学
Sutherland-Hodgman算法 框图处理线段 SP过程子框图浙江大学信息学院 计算机图形学
Sutherland-Hodgman算法
– 上述算法仅用一条裁剪边对多边形进行裁剪，
得到一个顶点序列，作为下一条裁剪边处理过程的输入。
– 对于每一条裁剪边，算法框图同上，只是判断点在窗口哪一侧以及求线段 SP与裁剪边的交点算法应随之改变。
浙江大学信息学院 计算机图形学
Sutherland-Hodgeman算法
对凸多边形应用本算法可以得到正确的结果，
但是对凹多边形的裁剪将如图所示显示出一条多余的直线。这种情况在裁剪后的多边形有两个或者多个分离部分的时候出现。因为只有一个输出顶点表，所以表中最后一个顶点总是连着第一个顶点。
解决这个问题有多种方法，一是把凹多边形分割成若干个凸多边形，然后分别处理各个凸多边形。二是修改本算法，沿着任何一个裁剪窗口边检查顶点表，正确的连接顶点对。再有就是 Weiler-Atherton算法。
浙江大学信息学院 计算机图形学
Sutherland-Hodgman算法思考：
如何推广到任意凸多边形
裁剪窗口？
浙江大学信息学院 计算机图形学
Weiler-Athenton算法裁剪窗口为任意多边形（ 凸、凹、带内环） 的情况：
– 主多边形：被裁剪多边形，记为 A
– 裁剪多边形：裁剪窗口，记为 B
浙江大学信息学院 计算机图形学
Weiler-Athenton算法多边形顶点的排列顺序（使多边形区域位于有向边的左侧 ）外环：逆时针 ；内环：顺时针
主多边形和裁剪多边形把二维平面分成两部分。
内裁剪,A∩B
外裁剪,A-B
裁剪结果区域的边界由 A的部分边界和 B的部分边界两部分构成，并且在交点处边界发生交替，即由 A的边界转至 B的边界，或由 B的边界转至 A的边界浙江大学信息学院 计算机图形学
Weiler-Athenton算法
– 如果主多边形与裁剪多边形有交点，则 交点成对出现,它们被分为如下两类：
进点,主多边形边界由此进入裁剪多边形内如,I1,I3,I5,I7,I9,I11
出点,主多边形边界由此离开裁剪多边形区域,
如,I0,I2,I4,I6,I8,I10
浙江大学信息学院 计算机图形学
Weiler-Athenton算法
1）建顶点表；
2）求交点；
3）裁剪 … …
1、建立主多边形和裁剪多边的顶点表．
2、求主多边形和裁剪多边形的交点，并将这些交点按顺序插入两多边形的顶点表中。在两多边表形顶点表中的相同交点间建立双向指针 。
3、裁剪,如果存在没有被跟踪过的交点，执行以下步骤：
浙江大学信息学院 计算机图形学
Weiler-Athenton算法浙江大学信息学院 计算机图形学
Weiler-Athenton算法
(1)建立空的裁剪结果多边形的顶点表．
(2)选取任一没有被跟踪过的交点为始点，将其输出到结果多边形顶点表中．
(3)如果该交点为进点，跟踪主多边形边边界；否则跟踪裁剪多边形边界．
(4) 跟踪多边形边界，每遇到多边形顶点，将其输出到结果多边形顶点表中，直至遇到新的交点．
(5)将该交点输出到结果多边形顶点表中，并通过连接该交点的双向指针改变跟踪方向（如果上一步跟踪的是主多边形边界，现在改为跟踪裁剪多边形边界；如果上一步跟踪裁剪多边形边界，现在改为跟踪主多边形边界）．
(6)重复 (4),(5)直至回到起点
取 I7为起点，所得裁剪结果多边形
I7I0q0I3I4I5I6I7。取 I8为起点，所得裁剪结果多边形为 I8I9I10I11I2q2I1I8。
浙江大学信息学院 计算机图形学
Weiler-Athenton算法
– 交点的奇异情况处理
1、与裁剪多边形的边重合的主多边形的边不参与求交点；
2、对于顶点落在裁剪多边形的边上的主多边形的边，如果落在该裁剪边的内侧，将该顶点算作交点；而如果这条边落在该裁剪边的外侧，将该顶点不看作交点浙江大学信息学院 计算机图形学反走样
用离散量表示连续量引起的失真现象 称之为 走样
(aliasing) 。
光栅图形的走样现象
– 阶梯状边界；
– 图形细节失真；
– 狭小图形遗失：动画序列中时隐时现，产生闪烁。
浙江大学信息学院 计算机图形学走样现象举例
不光滑 (阶梯状）的图形边界例子,PaintBrush
浙江大学信息学院 计算机图形学走样现象举例
图形细节失真浙江大学信息学院 计算机图形学走样现象举例
狭小图形的遗失与动态图形的闪烁浙江大学信息学院 计算机图形学反走样概念及方法
用于减少或消除走样现象的技术称为 反走样 (antialiasing)
提高分辨率
简单区域取样
加权区域取样浙江大学信息学院 计算机图形学提高分辨率
把显示器分辨率提高一倍，
– 直线经过两倍的象素，锯齿也增加一倍，
– 但同时每个阶梯的宽度也减小了一倍，
– 所以显示出的直线段看起来就平直光滑了一些。
浙江大学信息学院 计算机图形学提高分辨率
方法简单，但代价非常大。显示器的水平、竖直分辩率各提高一倍，则显示器的点距减少一倍，帧缓存容量则增加到原来的 4倍，而扫描转换同样大小的图元却要花 4倍时间。
而且它也只能减轻而不能消除锯齿问题另一种方法（软件方法）：
用较高的分辨率的显示模式下计算，（对各自像属下计算，再求（非）加权平均的颜色值），
在较低的分辨率模式下显示。 只能减轻而不能消除锯齿问题。
浙江大学信息学院 计算机图形学软件方法 1
把每个像素分为四个子像素,扫描转换算法求得各子像素的灰度值,然后对四像素的灰度值简单平均,作为该像素的灰度值 。
浙江大学信息学院 计算机图形学软件方法 2
设 分 辨 率 为 m?n,把 显 示 窗 口 分 为
(2m+1)?(2n+1)个子像素,对每个子像素进行灰度值计算,然后根据权值表所规定的权值,对位于像素中心及四周的九个子像素加权平均,作为显示像素的颜色 。
设 m=4,n=3
浙江大学信息学院 计算机图形学简单区域取样
方法由来
– 两点假设
1,象素是数学上抽象的点,它的面积为 0,它的亮度由覆盖该点的图形的亮度所决定；
2、直线段是数学上抽象直线段，它的宽度为 0。
– 现实
像素的面积不为 0；
直线段的宽度至少为 1个像素；
– 假设与现实的矛盾是导致混淆出现的原因之一浙江大学信息学院 计算机图形学简单区域取样
– 解决方法：改变直线段模型，由此产生算法
– 方法步骤,
1、将直线段看作具有一定宽度的狭长矩形；
2、当直线段与某象素有交时，求出两者相交区域的面积；
3、根据相交区域的面积，确定该象素的亮度值浙江大学信息学院 计算机图形学简单区域取样
基本思想：
– 每个象素是一个具有一定面积的小区域，将直线段看作具有一定宽度的狭长矩形。当直线段与象素有交时，
求出两者相交区域的面积，然后根据相交区域面积的大小确定该象素的亮度值。
有宽度的线条轮廓 象素相交的五种情况及用于计算面积的量
0 1
1
2
2 3
3
4
4 5
5
6 7 8 9 10 11
D
D / m
D
m
(1) (2) (3) (4) (5)
浙江大学信息学院 计算机图形学简单区域取样
面积计算
– 情况⑴（ 5)阴影面积为,D2/2m；
– 情况⑵（ 4)阴影面积为,D - m/2；
– 情况⑶阴影面积为,1 - D2/m
为了简化计算可以采用离散的方法浙江大学信息学院 计算机图形学简单区域取样
– 求相交区域的近似面积的离散计算方法
1、将屏幕象素分割成 n个更小的子象素；
2、计算中心点落在直线段内的子象素的个数，记为 k，
3,k/n为线段与象素相交区域面积的近似值目的：简化计算
n = 16,k = 3
近似面积 = 3/16
浙江大学信息学院 计算机图形学简单区域取样
简单区域取样采用的是一个盒式滤波器，
它是一个二维加权函数，以 w表示。
w =1 若在当前像素所代表的正方形上
w =0 其它区域上
直线条经过该像素时，该像素的灰度值可以通过在像素与直线条的相交区域上对 w求积分获得。
此时，面积值 =体积值浙江大学信息学院 计算机图形学简单区域取样
– 缺点：
– 象素的亮度与相交区域的面积成正比，
而与相交区域落在象素内的位置无关，
这仍然会导致锯齿效应。
– 直线条上沿理想直线方向的相邻两个象素有时会有较大的灰度差。
浙江大学信息学院 计算机图形学加权区域取样
采用圆锥形滤波器，圆锥的底圆中心在当前像素，底圆半径为一个像素，锥高为 1。当直线条经过该像素时，该像素的灰度值是在二者相交区域上对滤波器进行积分的积分值。
见 p213的图 4.7.9
浙江大学信息学院 计算机图形学加权区域取样
特点：
接近理想直线的像素将被分配更多的灰度值。
相邻的两个像素的滤波器相交，有利于缩小直线条上相邻像素的灰度差。
具体算法见 p213
浙江大学信息学院 计算机图形学半色调技术
简单区域取样和加权区域取样技术的前提是多级灰度,利用多级灰度来提高视觉分辨率 。 但是,若只有两级灰度呢？
能否使用上述技术呢？
对于给定的分辨率,通过将几个像素组合成一个单元来获得多级灰度 。
例：在一个显示器中将四个像素组成一个单元,可产生 5种光强 。
浙江大学信息学院 计算机图形学半色调技术
可用如下矩阵来表示：
它表示黑色像素填入 2?2个位置中的次序,每一级灰度再添上一个黑色像素就得到下一级灰度 。
注意：
1,要尽量避免连成一条直线的花样 。
2,花样是可以选择的 。
单元也可以是长方形,如
42
13
236
514
浙江大学信息学院 计算机图形学半色调技术
一般来说,对于两级灰度显示器可能构成的灰度数等于单元中像素个数加 1
∴ 单元越大,灰度级别越高
它是以牺牲空间分辨率为代价的 。
浙江大学信息学院 计算机图形学半色调技术
例：灰度级别 =4,每个单元 =2*2
若有 m级灰度,n?n个像素组成一个单元,则灰度级别数为 n?n?(m-1)+1
