对某线段的两个端点的区号进行位与运算，可知这两个端点是否同在视区的上、下、左、右；
‐如果两端点的编码均为0000，表示直线在窗口内。
‐如果两端点的编码相与不为0000，表示直线在窗口外。
‐如果两端点的编码不全为0000，但相与为0000，则该直线部分可见，需计算直线与窗口的交点，确定哪一部分可见。
‐
算法描述：
BOOLdone,draw；（done表示是否完成，draw表示是否可见）
Unsignedcharcode1,code2；端点1，端点2的编码
While（!
done）
begin
if（判断code1,code2,若为第1种情况）
begin
done=TRUE；
draw=TRUE；
end
elseif（为第2种情况）
begin
done=TRUE；
draw=FALSE；
end
elseif（检查code1，若在窗口内）/*第3种情况*/
begin
交换端点及端点的编码；以左，上，右，下的次序对端点1进行判断及求交；将交点的值赋给端点1；
end
end
算法分析：
本算法的优点在于简单，易于实现。
用编码方法可快速判断线段的完全可见和显然不可见，他可以简单的描述为将直线在窗口左边的部分删去，按左，右，下，上的顺序依次进行，处理之后，剩余部分就是可见的了。
在这个算法中求交点是很重要的，他决定了算法的速度。
本算法对于其他形状的窗口是否同样有效就值得讨论了，这也证明了在图形算法中，没有几个是对大多数情况有效的。
特别适用二种情形：
大窗口场合；窗口特别小场合（光标拾取图形，光标看作小的裁剪窗口）。
多边形裁减
Sutherland-Hodgema算法
算法原理：
通过对单一边或面的裁剪来实现多边形的裁剪
分割处理策略：
将多边形关于矩形窗口的裁剪分解为多边形关于窗口四边所在直线的裁剪。
一次用窗口的一条边裁剪多边形。
流水线过程（左上右下）：
前边的结果是后边的输入。
亦称逐边裁剪算法。
算法的每一次输出（包括中间结果）都是一个多边形的顶点表，且所有顶点均位于相应窗口裁剪边或面的可见一侧。
由于多边形的每一条边需要与裁剪边或面分别进行比较，因此只需要讨论单条边和单个裁剪边或面之间可能的位置关系。
假设S，P为多边形的两个相邻顶点，且S为该边的起点，P为该边的终点，则变SP与裁剪边或面之间只有4种可能的关系。
如下图：
由上可见，每一次将多边形的边与裁剪边或面比较后，输出一个或两个顶点，也可能无输出点。
如果SP边完全可见，则输出P点，不必输出起点S，因为顶点是按顺序处理的，S是作为前一边的终点输出的。
如果SP边完全不可见，则无输出。
如果SP边部分可见，则SP边可能进入或离开裁剪边或面的可见一侧。
如果SP边离开裁剪边或面的可见一侧，则输出SP与裁剪边或面交点。
如果SP边进入裁剪边或面的可见一侧，则输出两点，一个为SP与裁剪边或面的交点，一个是P点。
对于多边形的第一个顶点，只需判断其可见性。
如果可见，则输出且作为起点S；否则无输出，但还是要作为S保存，以便后续点处理。
对于最后一条边PnP1，其处理方法是：
标志第一顶点为F，这样最后一条边则为PnF，可与其他边作相同的处理。
实现方法：
⏹设置二个表：
◆输入顶点表：
用于存放被裁剪多边形的顶点p1-pm。
◆输出顶点表：
用于存放裁剪过程中及结果的顶点q1-qn。
⏹输入顶点表中各顶点要求按一定顺序排列，一般可采用顺时针或逆时针方向。
⏹相对于裁剪窗口的各条边界，按顶点表中的顺序，逐边进行裁剪
思考？
点的可见性判断；
交点的计算。
算法描述：
1.while对于每一个窗口边或面do
begin
2.ifP1在窗口边的可见一侧then输出P1
3.fori=1到ndo
begin
4.ifPi在窗口边的可见一侧then
5.ifPi+1在窗口边的可见一侧then输出Pi+1
6.else计算交点并输出交点
7.elseifPi+1在窗口边的可见一侧，then
计算交点并输出交点，同时输出Pi+1
end
end
8.endofalgorithm
Roberts消隐算法
算法原理：
Roberts消隐算法是在图像空间实现的消隐算法，数学处理严谨，计算量甚大。
Roberts算法要求所有被显示的物体都是凸的，因此对凹体要先分割成许多个凸体的组合。
此算法的基本步骤是：
●逐个的独立的考虑每个物体自身，找出为其自身所遮挡的边和面；
●将每一物体上留下的边再与其它物体逐个的进行比较，以确定其是完全可见还是部分或全部被遮挡；
●确定由于物体之间的相互贯穿等原因，是否要形成新的显示边等。
从而使被显示各物体更接近现实。
下面先介绍一些用到的一些基本概念以及有关的数学方法。
●体矩阵：
假设在三维空间中，一平面的方程表示为：
ax+by+cz+d=0,令P=[a,b,c,d]，表示平面的系数向量；又令S=[x,y,z,1]，表示三维空间重点的其次坐标。
上式改写为：
S·PT=0。
所以凸体可由平面方程系数组成的体矩阵表示：
矩阵的每一列表示物体的对应平面方程的系数，其列数与物体的面数一致。
由于当PT是一平面系数时，-PT也是该平面的系数，因此为了计算的需要，Roberts算法规定：
对平面多面体内部的任一点S0，要使得[S0]·[V]=[Q]=[q1,q2,q3,…,qn]式中的每一个分量qi都不小于零（i=1,2,…,n）。
适当选取物体内部一点S0，用以测试单调态平面系数的符号，使其满足Roberts算法的规定，这是本算法最基本的一步。
平面系数的计算方法：
•方法一：
根据平面上的已知点，求解线性方程组。
已知平面上不共线三点（x1,y1,z1），（x2,y2,z2），（x3,y3,z3），得到规范方程组：
写成矩阵形式为：
记为：
[X][C]=[D]，
解得平面方程系数为：
[C]=[X]-1[D]
•方法二：
根据平面的法矢量和平面上一已知点，求得平面系数。
已知平面的法矢量为：
n=ai+bj+ck，其中i，j，k分别为x，y，z方向的单位矢量，且又已知平面上一点（x1,y1,z1）。
则平面方程是：
ax+by+cz+d=0，其中 d=-（ax1+by1+cz1）
•方法三：
采用MartinNewell方法，即最佳逼近法，计算任何平面多边形所在平面的精确方程或接近于平面的多边形的最佳逼近平面方程。
假设给定n个点（xi,yi,zi）（i=1,2,…,n），则平面系数可用于下式计算：
其中：
若i≠n，则j=i+1，否则j=1。
d可由下式求得：
d=-（ax1+by1+cz1）
•体矩阵的变换
在消隐算法执行之前，为了得到从一指定的试点以给定的观察方向来看所需要显示的物体，常常先要对物体进行三维坐标变换。
因此，在变换确定之后，或给定了变换矩阵[T]以后，需要对每一个物体的体矩阵[V]作一个相应的变换，得到变换后的体矩阵[VT]。
同时，还要对物体的顶点齐次坐标矩阵[B]作一个相应的变换，得到变换后的顶点齐次坐标矩阵[BT]。
有两种常用的计算[VT]的方法：
•方法一：
假设[B]与[BT]分别为在体矩阵变换前后的物体顶点齐次坐标构成的矩阵，则[BT]=[B][T]
因为有[X][C]=[D]，所以可得到该物体原各平面的方程为：
[B][V]=[D]其中：
[D]为零矩阵。
同样，变换后的平面方程也可表示为：
[BT][VT]=[D]
并且：
[BT][VT]=[B][V]代入到[BT]=[B][T]，方程两边消去[B]并左乘[T]-1，得到：
[VT]=[T]-1[V];所以，变换后的体矩阵是由原来的体矩阵左乘变换矩阵的逆矩阵而得到的。
•方法二：
假设原先并未计算形体矩阵[V]，也不希望计算[T]的逆矩阵，则可光计算：
[BT]=[B][T],然后用变换后的物体顶点坐标[BT]，按照前面介绍的MartinNewell方法，直接计算变换后的体矩阵[VT]，两种方法所得结果完全一致。
•
自消隐方法:
自消隐是对物体自身所遮挡的面（自隐面）和边（自隐边）的消除。
对于不同的视点及视方向，既是对同一个物体来说，也会产生不同的自隐面和自隐边。
因此自隐面和自隐边不仅取决于物体的形状，而且与视点方向相关。
假设视点位于z的负无穷远处，视方向为z轴的正向，即视方向朝z轴正向无穷远处，在齐次坐标系中，该方向矢量为：
[E]=[0,0,1,0]显然，若视方向[E]和体矩阵[VT]的乘积中有负的元素，则[E]在这此元素对应的面与形体相对的另一侧，而这正说明这些面被物体自身所遮挡。
所以利用[E]·[VT]=[w1,w2,…,wn]（表示视线与表面内法线矢量夹角关系）寻找所有wi＜0的i值，其对应面即为自隐面，可被消除。
•当找到了所有的自隐面之后，就可以确定自隐线，自隐线的确定方法是：
若相交的两各平面都是自隐面的话，它们的相交边线就是自隐线，可以消除，否则为物体的可见边线。
在确定了自隐面和自隐线之后，该物体余下的边线应当与其它物体一一比较，以确定他们是否为其他物体所遮挡。
为了提高算法的执行效率，应先将一些很明显由很容易确定的不必要的比较排除在外，常用的一些方法是最大最小测试法和边框测试法等。
最大最小测试法是对要被显示的每一个物体，以其最小Z值（即最靠近视点的点）进行排序，由大到小组成一个Z值的表，比较某一边线，若它的最大Z值小于表中某一元素，则从该元素起及其以后的元素所对应的物体均不可能遮挡该边线，所以不用进一步的比较。
边框测试法是为较复杂物体加上如球或长方体之类的边框，这样只要能确定某些边线完全处于这些框的上面、下面、左面、右面后前面时，边框内的物体就不会遮挡该边线。
最大最小测试法如下：
若物体1的最大Z值≤物体2的最小Z值,则物体1的优先级为1,物体2的优先级为2
–优先级小的物体离视点距离较近
–优先级小的物体可能遮挡优先极大的物体
–优先级小的物体先投影
边框测试法如下：
判断下式：
x_minp＞x_maxeOR
x_mine＞x_maxpOR
y_minp＞y_maxeORy_mine＞y_maxp
●若上式为真，边与多边形不相交；若上式为假，二边框相交，但边与多边形可能相交，可能不相交，需进行第二次边框测试。
●第二次边框测试：
把边的边框和多边形的每条边的边框进行比较，进行交点测试。
●交点测试：
对求出的交点，判别其是否同时在边或多边形边上（交点的x,y值是否在边的范围内），若是，边与多边形的边相交；若不是，边与多边形的边不相交。
边线与物体的比较方法:
完成上述工作后，还有一定数量的边要通过与其它物体的比较后方能确定其可见性。
假设考虑边线P1P2的可见性，被比较的物体体矩阵为[VT]。
采用直线的参数表示形式：
P（t）=P1+（P2-P1）t0≤t≤1或v=s+dt0≤t≤1
其中：
v是边线上点的位置矢量，s是起始点，d为直线的方向。
再构造由P1P2上一点至视点的直线，其参数表示形式为：
Q（α,t）=u=v+gα=s+dt+gα（0≤t≤1,α＞0）
其中：
g=[0,0,-1,0],与视线方向[E]=[0,0,1,0]相反，且α与t的意义相同。
给定一个t值，对应边线P1P2上的一点P（t），同样对于给定一个α值，则决定了从该点至视点线段上的一点。
所以Q（α,t）可以看作是定义了这平面π上的一点集,给定α和t，就确定了这个平面上的一点。
α总是取正值，这是因为只有平面的这一区域才能包含遮挡上述边线的物体。
如果物体于平面π的交集不定，且落在点集Q（α,t）中，则这个物体部分或全部地遮挡边线P1P2。
否则，P1P2就不会被这个物体所遮挡。
•现在把边线的对于给定物体的可见性问题，转为物体与整个点集之交是否为空集的问题。
因为前面已经规定：
物体中的点与体矩阵的乘积所产生的向量中所有元素均为非负数。
所以，
H=u·[VT]=s·[VT]+t·d[VT]+α·g[VT]≥0（0≤t≤1，α≥0）
对于物体中的每个面j=1,2,…n，使得hj=pj+tqj+αwj≥0（0≤t≤1，α≥0）
其中pj，qj，wj，hj分别为向量P，Q，W，H的分量：
P=（p1,p2,…,pn）=s·[VT]
Q=（q1,q2,…,qn）=d·[VT]
W=（w1,w2,…,wn）=g·[VT]
H=（h1,h2,…,hn）=Q（α,t）·[VT]
于是，可见与不可见的临界条件是hj=0。
当hj=0时，该点恰好位于对应的平面上。
若对物体的每一平面取hj=0，可得有关α和t的联立方程组。
为了求解这个方程组，可将其中的方程两两联立，得到所有可能的α和t值。
可能的解的总数为n（n-1）/2。
然后在（0≤t≤1,α≥0）范围内求出t的最小值tmin和最大值tmax和相应的α值。
对于tmin≤t≤tmax,必须α≥0，使得Q（α,t）落在物体中，所有这样的t值是边线上被遮挡的点，对于那些α=0的解，说明边线真正贯穿了物体。
要保存这些贯穿点，然后连接这些贯穿点，得到的贯穿线再与其它物体相比较，其中可见部分就是可见贯穿线。
可见贯穿线若下图所示:
上述方法的计算量很大，下面介绍一种判别完全可见线段的方法，可节省计算量。
•该方法的基本思想是判断一线段的两端点是否位于视点和一可见面之间，若是，则完全可见。
根据u=s+dt+gα（0≤t≤1,α＞0）当α=0时，u表示该边线本身，此时当t=0和t=1是，分别表示该边线的两个端点，则：
hj=u·[VT]=pj+qj·t+w·α
当α=0和t=1时，pj+qj表示该边线另一端点和物体上j个平面的点积。
因为wj≤0表示物体的第j个平面可见，所以，如果wj≤0和pj+qj≤0，则表示该端点位于可见面上或位于视点与可见面之间。
综上，在物体中只要存在一个j，使得wj≤0&pj≤0&pj+qj≤0成立，则该边线完全可见。
算法描述：
完整的Roberts算法分为三个部分：
●对每一个物体进行分析，消去自隐面和自隐线；
●对余留下的边与其它所有物体一一比较以确定被其他物体所遮挡的部分；
●确定物体见可能由于相互穿透而增加的贯穿线是否可见。
假定物体是由面构成的，而面是由边构成，边则由顶点构成。
所有顶点、棱边、面都是已知的。
/*消除自隐线和自隐面*/
1.while对于要被显示的每一个物体do
begin
2.物体的顶点表构造各表面多边形及棱边
3.计算物体上每一多边形表面的平面方程
4./*检查平面方程的符号*/
5.取物体各顶点的平均值，作为一个物体内部点
6.计算该物体内部点与平面方程的点积
7.if点积＜0then改变平面方程系数的符号
8.建立物体的体矩阵
9.体矩阵左乘包括透视变换在内的视变换的逆矩阵
10.计算并保存变换后物体包围盒值xmin,xmax,ymin,ymax,zmin,zmax
/*判断自消隐面和线*/
10.取位于负无穷处的试验点和变换后体矩阵的点积
11.if点积＜0then标志相应平面为隐藏面
12.消除相应与该平面的多边形（也消除两隐藏面相交形成的隐藏线）
end
/*消除每一物体被其他物体遮挡面产生的隐藏线*/
13.if要显示的物体只有一个thengotoendofalgorithm
/*建立物体的优先级*/
14.while对于优先表上的每一个物体do
begin
/*检查每一非自隐线的棱边是否被其他物体遮挡。
含被检查棱边的物体称试验体，所有用来判断遮挡关系的其他物体称检查体。
试验体通常只需对比它优先级低的检查体进行遮挡检查*/
/*对试验体和检查体进行包围盒试验*/
15.ifxmin（检查体）＞xmax（试验体）或xmax（检查体）＜xmin（试验体）或ymin（检查体）＞ymax（试验体）或ymax（检查体）＜ymin（试验体）
then检查体不可能遮挡试验体任何棱边goto14
/*进行初步的贯穿检查判断试验体是否贯穿检查体而部分的被遮挡*/
/*比较试验体上的最小z值和检查体的最大z值*/
16.ifzmin（试验体）＞zmax（检查体）
then试验体和检查体不可能形成贯穿goto14
/*检查是否存在可见性贯穿*/
17.ifzmin（试验体）＜zmax（检查体）
then检查体可能贯穿试验体的前面，建立可见性贯穿标志goto20
18.ifxmax（试验体）＞xmin（检查体）或xmin（试验体）＜xmax（检查体）
then检查体可能贯穿试验体的侧面，建立可见性贯穿标志goto20
19.ifymax（试验体）＞ymin（检查体）或ymin（试验体）＜ymax（检查体）
then检查体可能贯穿试验体的底面或顶面，建立可见性贯穿标志goto20
20.if可见性贯穿标志非空，then检查体记入贯穿表
/*进行试验体棱边检查*/
21.while对于试验体中每一条棱边do
begin
计算试验体棱边的s和d
22.计算检查体的每一表面的p,q,w
/*检查试验体棱边是否完全可见*/
23.if完全可见thengoto21
24.计算联立的方程组hj=0的解
25.while对于每一组（α,t）解do
begin
27.if0≤t≤1&α≥0&hj＞0（j=1,2,…,n）then计算tmin和tmax
28.if（α=0） then计算和保存贯穿点
end
29.计算和保存棱边上的可见段
end
/*决定贯穿体之间的可见相贯线*/
30.if可见性贯穿标志为空thengoto32
31.if无贯穿点存在thengoto32
else将两贯穿提上的全部贯穿注意连接，构成可能的相贯边；对两个贯穿体逐一检查每一相贯边的可见性；对其它物体，检查余留下的相贯边的可见性并保存其可见段
32.显示剩下棱边上的可见段
end
33.endofalgorithm
实验环境
VS2010（C#）
实验步骤
1.掌握算法原理；
2.依据算法，编写源程序并进行调试；
下面是一些算法实现的关键代码：
直线裁剪算法的实现代码:
//直线裁剪
privatevoidSutherland（）
{
floatxL=-50,xR=50,yB=50,yT=-50;//四个边界
floatxa=0,ya=0,xb=0,yb=0;
floatQL,QR,QB,QT,DL,DR,DB,DT,TL,TR,TB,TT,t,t0;
if（!
（"".Equals（textx0.Text）||"".Equals（texty0.Text）||"".Equals（textx1.Text）||"".Equals（texty1.Text）））
{
floatx0=Convert.ToInt32（textx0.Text）;
floaty0=-Convert.ToInt32（texty0.Text）;
floatx1=Convert.ToInt32（textx1.Text）;
floaty1=-Convert.ToInt32（texty1.Text）;
QL=-（x1-x0）;QR=x1-x0;QB=-（y1-y0）;QT=y1-y0;
DL=x0-xL;DR=xR-x0;DB=y0-yB;DT=yT-y0;
TL=DL/QL;TR=DR/QR;TB=DB/QB;TT=DT/QT;
if（TB>TL）
{
t=TB;TB=TL;TL=t;
}
if（TL<0）
{
TL=0;
}
if（TL>=0&&TL<1）
{
xa=x0+TL*QR;
ya=y0+TL*QT;
}
elseif（TL>1）
{
xa=-y1+TL*QR;
ya=y0+（-TB*QT）;
}
if（TT{
t0=TT;TT=TR;TR=t0;
}
if（TR>1）
{
TR=1;
}
if（TR<0）
{
xb=x0+TR*QR;
yb=y0+TR*QT;
}
elseif（TR==0）
{
xb=x1;
yb=y1;
}
elseif（TR<1）
{
xb=x0+TR*QR;
yb=y0+TR*QT;
}
if（TR0）
{
Penpen=newPen（Color.DarkBlue,3）;
graphics.DrawLine（pen,x0,y0,x1,y1）;
}
else
{
graphics.DrawLine（pen,xa,ya,xb,yb）;
}
}
}
多边形裁剪算法代码实现如下：
//多边形裁剪
privatevoidplogSutherland1（）
{
SolidBrushbrush=newSolidBrush（Color.Red）;
PointFp11=ne
升级会员 