1
2
直线生成算法圆与椭圆的绘制算法5图元的概念4
3
6
区域填充算法裁剪
反走样技术
4.5 裁剪—
4.5 裁剪—
4.5 裁剪—
4.5 裁剪—
4.5 裁剪—
4.5 裁剪—
算法实现
◆第一步
◆第二步
4.5 裁剪—
编码实现（第一步）
九个区域，每一个区域采用四位编码对于任一端点
左），赋予一个
◆左：若
◆右：若
◆下：若
◆上：若
4.5 裁剪—
编码实现（第一步）
对要被裁剪的线段的两个端点，如果其所在的区域的编码均是
如果两个编码的
见的，可简弃之；
如果两个编码的
少一个端点非
在交点处把线段一分为二，其中必有一
段完全在窗口外，可弃之。
再对另一段
重复进行上述处理，直到该线段完全被
舍弃或找到位于窗口内的一段线段为止。
4.5 裁剪—
析出
点。
求出其交点
见的，因而只要对
上述处理步骤。
y=
裁剪结束。
算法步骤
界坐标：
code2(0100)
之，转
则交换
段与窗口边界的交点除p
算法的编码实现
到另一端点间的线段重复上述过程直到接受或拒绝;
计算线段
if(LEFT&code
else if(RIGHT&code
else if(BOTTOM&code {y=YB;
else if(TOP & code !=0) {y=YT;
Cohen-Sutherland
Nicholl et al. An efficient new algorithm for 2-D line clipping: its
4.5 裁剪—
4.5 裁剪—
4.5 裁剪—
（
（
（
4.5 裁剪—）
界L
上；
要条件
A和该处内法向量
P(t)
4.5 裁剪—）。
4.5 裁剪—）
终点组:N i ⋅(P 2-P 1)<0 起点组:N i ⋅(P 2-P 1)>0 特殊情况：N i ⋅(P 2-P 1)=0
这时，
，P 1P 2与对应边平行， 这时有两种情况：线段在区域外侧或内侧：
前一种情况对应于N i ⋅(P 2-P 1)<0，
可直接判断线段在多边形之外
前一种情况对应于N i ⋅(P 2-P 1)>0，
则不于考虑，继续处理其他边。
)(12P P i -⊥N 解的几何意义
起点组P 2P 1
4.5 裁剪—
A1A2
A4
P1
P2
当凸多边形是矩形窗口，且矩形的边平行于坐标轴时，上述算法可简化为梁友栋-Barsky 算法。
对于窗口的每条边，后面的表格列出了其内法向量N i ，该边上一点A i ，从A i 指向线段起点P 1的向量P 1-A i ，以及线段与该边（或延长线）的交点参数。
由于每条边上法向量只有一个非零分量，所以任意一个向量与法向量求内积的运算很简单。
4.5 裁剪—直线裁剪：Liang-Barsky 算法（1）
4.5 裁剪—
4.5 裁剪—
4.5 裁剪—
展开后有：
令：
则有：
4.5 裁剪—
对任何
中k=1,2,3,4
(1)
线段。
(2)
需求与边界的实交点。
4.5 裁剪—
(1)
遇到的剪裁窗口边界所
对于这些边界
u
遇到的剪裁窗口边界所决定
各个
4.5 裁剪—
,0)
4.5 裁剪—
算法描述
更新
u2的值，
点坐标，画出直线。
4.5 裁剪—
算法的程序实现
#define
#define
double
bool
void
double
{double
visible=False;
dx=x[1]-x[0];
*u1=0;
if(clipt(-dx,x[0]-xL,u1,u2))
}
4.5 裁剪—
Cyrus-Beck
性。
但当裁剪窗口为矩形时，效率不高。
Liang-barsky
作业与思考题（
9.设矩形窗口左下角为
Sutherland
感谢各位同学观看！。
