计算机图形学裁剪算法详解

.

if(ClipT(dx,XR-x1, &u1,&u2)

if(ClipT(-dy,y1-YB, &u1,&u2) if(ClipT(dy,YT-y1, &u1,&u2)

{ displayline(x1+u1*dx,y1+u1*dy, x1+u2*dx,y1+u2*dy) return; } }

bool ClipT(p,q,u1,u2) float p,q,*u1,*u2; { float r; if(p<0) { r=q/p;

if(r>*u2)return FALSE; else if(r>*u1) { *u1=r;

return TRUE; } }

else if(p>0) { r=p/q;

if(r<*u1) return FALSE; else if(r<*u2) { *u2=r;

return TRUE;

.

.

} }

else if(q<0) return FALSE; return TRUE; }

2 多边形裁剪

对于一个多边形，可以把它分解为边界的线段逐段进行裁剪。但这样做会使原来封闭的多边形变成不封闭的或者一些离散的线段。当多边形作为实区域考虑时，封闭的多边形裁剪后仍应当是封闭的多边形，以便进行填充。为此，可以使用Sutherland-Hodgman算法。该算法的基本思想是一次用窗口的一条边裁剪多边形。

算法的每一步，考虑窗口的一条边以及延长线构成的裁剪线。该线把平面分成两个部分：一部分包含窗口，称为可见一侧；另一部分称为不可见一侧。依序考虑多边形的各条边的两端点S、P。它们与裁剪线的位置关系只有四种。(1)S,P均在可见一侧（2）S,P均在不可见一侧(3)S可见,P不可见(4)S不可见,P可见。

图1.3 S、P与裁剪线的四种位置关系

每条线段端点S、P与裁剪线比较之后，可输出0至两个顶点。对于情况（1）仅输出顶点P；情况（2）输出0个顶点；情况（3）输出线段SP与裁剪线的交点I； 情况（4）输出线段SP与裁剪线的交点I和终点P

上述算法仅用一条裁剪边对多边形进行裁剪，得到一个顶点序列，作为下一条裁剪边处理过程的输入。对于每一条裁剪边，算法框图一样，只是判断点在窗口哪一侧以及求线段SP与裁剪边的交点算法应随之改变。 基于divide and conquer策略的Sutherland-Hodgman算法 typedef struct

.

.

{ float x; float y; }Vertex; typedef Vertex Edge[2];

typedef Vertex VertexArray[MAX];

SutherlandHodgmanClip（VertexArray InVertexArray, VertexArray

OutVertexArray, edge ClipBoundary, int &Inlength, int &Outlength） { Vertex s, p, ip; int j;

Outlength = 0;

S = InVertexArray [InLength -1]; For (j = 0; j < Inlength; j++) {

P = InVertexArray [j]; if(Inside (P, ClipBoundary))

{ if(Inside (S, ClipBoundary)) //SP在窗口内，情况1 Output(p, OutLength, OutVertex Array) else{ //S在窗口外, 情况4

Intersect (S, P, ClipBoundary, &ip); Output (ip, OutLength, OutVertexArray); Output (P, OutLength, OutVertexArray); } }

else if (Inside (S, WindowsBoundary)) { //S在窗口内，P在窗口外,情况3

Intersect (S, P, ClipBoundary, &ip);

.

.

Output (ip, OutLength, OutVertexArray); } //情况2没有输出 S = P; } }

//判点在窗口内

bool Inside (Vertex &TestPt, Edge ClipBoundary)

{ if(ClipBoundary[1].x> ClipBoundary[0].x)//裁剪边为窗口下边 if(testpt.y>= ClipBoundary[0].y) return TRUE;

else if(ClipBoundary[1].x< ClipBoundary[0].x) //裁剪边为窗口上边 if(testpt.y<= ClipBoundary[0].y) return TRUE;

else if(ClipBoundary[1].y> ClipBoundary[0].y) //裁剪边为窗口右边 if(testpt.x<= ClipBoundary[0].x) return TRUE;

else if(ClipBoundary[1].y< ClipBoundary[0].y) //裁剪边为窗口左边 if(testpt.x>= ClipBoundary[0].x) return TRUE; Return FALSE; }

//直线段SP和窗口边界求交，返回交点；

void Intersect (Vertex&S,Vertex &P,Edge ClipBoundary,Vertex& IntersectPt)

.

.

{ if(ClipBoundary[0].y== ClipBoundary[1].y)//水平裁剪边 { IntersectPt.y = ClipBoundary[0].y;

IntersectPt.x = S.x+( ClipBoundary[0].y -s.y)*(p.x - s.x) / (p.y - s.y); }

else //垂直裁剪边

{ Intersect.x = ClipBoundary[0].x;

Intersect.y = s.y + (ClipBoundary[0].x - s.x)*(p.y - s.y) / (p.x. - s.x)； } }

.