SutherlandHodgman多边形裁剪算法.doc

Sutherland_Hodgman多边形裁剪算法#define TRUE 1#define FALSE 0typedef struct float x, y; vertex;void intersect(p1, p2, clipboundary, intersectp)vertex p1, p2, *clipboundary, *intersectpt;/* p1和p2为多边形的边的起点和终点，clipboundary为窗口边界，intersectpt中返回边与窗口边界的交点 */ if ( clipboundary0.y= clipboundary1.y ) /* 水平边界 */ intersectpt-y = clipboundary0.y; intersectpt-x = p1.x + (clipboundary0.y-p1.y)*(p2.x-p1.x)/(p2.y-p1.y); else /* 垂直边界 */ intersectpt-x = clipboundary0.x; intersectpt-y = p1.y + (clipboundary0.x-p1.x)*(p2.y-p1.y)/(p2.x-p1.x); int inside(testvertex, clipboundary)vertex testvertex, *clipboundary;/* 如果顶点testvertex在窗口边界clipboundary的内部，那么返回TRUE；否则返回FALSE */ if ( clipboundary1.x clipboundary0.x ) /* 上边界 */ if ( testvertex.y clipboundary0.x ) /* 下边界 */ if ( testvertex.y = clipboundary0.y ) return TRUE; if ( clipboundary1.y clipboundary0.y ) /* 右边界 */ if ( testvertex.x = clipboundary0.x ) return TRUE; if ( clipboundary1.y clipboundary0.y ) /* 左边界 */ if ( testvertex.y = clipboundary0.x ) return TRUE; return FALSE;outputvertex(outvertex, outlength, outvertexlist)vertex outvertex;int *outlength;vertex *outvertexlist/* 向输出顶点序列中输出顶点outvertex */ outvertexlist*outlength = outvertex; (*outlength)+;void Sutherland_Hodgman_Polygon_Clipping(invertexlist, outvertexlist, inlength, outlength, clipboundary)vertex *invertexlist, *outvertexlist;int inlength, *outlength;vertex *clipboundary;/* invertexlist为输入顶点序列，inlength为输入序列长度；outvertexlist为输出顶点序列，outlenght中返回输出序列长度；clipboundary为窗口边界 */ vertex s, p, i; int j; *outlength = 0; s = invertexlistinlength-1; /* 输入顶点序列的最后一个顶点 */ for ( j=0; jinlength; j+ ) p = invertexlistj; if ( inside(p,clipboundary) ) /* 情况1和4 */ if ( inside(s,clipboundary) ) /* 情况1 */ outputvertex(p,outlength,outvertexlist); else /* 情况4 */ intersect(s,p,clipboundary,&i); outputvertex(i,outlength,outvertexlist); outputvertex(p,outlength,outvertexlist); else /* 情况2和3 */ if ( inside(s,clipboundary) ) /* 情况2 */ intersect(s,p,clipboundary,&i); outputvertex(i,outlength,outvertexlist); /* 情况3无输出 */ s = p; /* 准备处理下一条边 */ 观察体变换观察窗口是一个二维裁剪窗口，当三维空间中的物体被投影到投影平面（观察平面）之后，位于观察窗口内部的部分被变换到视区中显示或输出，而位于观察窗口外部的部分被裁剪掉，不再继续处理。这是一种“先投影后裁剪”的方法，需要对三维空间中的所有物体（包括投影后将要被裁剪掉的物体）都进行投影变换，因而效率比较低。此外，对于一般的透视投影来说，“先投影后裁剪”还可能得到错误的结果（见习题8）。所以在三维观察中一般不采用这种“先投影后裁剪”的方法。图7. 1 透视投影的观察体图7. 2 平行投影的观察体如图7. 1和图7. 2所示，在三维观察坐标系VRC中，给定观察窗口、投影参考点PRP（projection reference point）和投影类型之后，我们就定义了一个观察体（view volume）。可以用三维裁剪算法将物体相对于观察体进行裁剪，对位于观察体内部的部分进行投影变换，生成其图形输出；而位于观察体外部的部分不再继续处理，不生成其图形输出。这是一种“先裁剪后投影”的方法，是在三维观察中普遍采用的方法。透视投影的观察体与平行投影的观察体有所不同。对于透视投影来说，投影参考点PRP就是投影中心，从投影参考点分别向观察窗口的四个角点引射线，得到一个顶端在投影参考点的无限延伸的四棱锥（pyramid），即为透视投影的观察体（图7. 1）。对于平行投影来说，投影方向DOP（direction of projection）定义为从投影参考点PRP指向窗口中心CW的方向向量，经过观察窗口的四个角点分别作平行于投影方向的直线，得到一个两端无限延伸的平行六面体（parallelpiped），即为平行投影的观察体（图7. 2）。现在我们得到的观察体是无限延伸的，位于这个无限延伸的观察体内部的物体都会被投影到观察窗口中。有的时候，我们希望观察体是有限的。图7. 3 透视投影的有限观察体图7. 4 平行投影的有限观察体如图7. 3和图7. 4所示，我们可以用前裁剪平面（front clipping plane）和后裁剪平面（back clipping plane）将无限延伸的观察体变成有限观察体。前裁剪平面简称前平面（front plane），也称为近平面（near plane，hither plane），后裁剪平面简称后平面（back plane），也称为远平面（far plane，yon plane），它们都平行于观察平面，也就是说，它们的法向量方向与观察平面法向量VPN（n轴）相同。前平面到观察平面的距离称为前距离F（front distance），后平面到观察平面的距离称为后距离B（back distance），前距离F与后距离B都是有符号数，观察平面法向量VPN（n轴）指向的方向为正方向，其反方向为负方向。为了保证观察体不为空，前距离F应该大于后距离B。对于透视投影，前平面应该在投影参考点PRP（投影中心）与后平面之间；对于平行投影，前平面应该在正无穷远与后平面之间。虽然前平面与后平面的相对位置是确定的，但是观察平面与它们的相对位置却是可变的，观察平面可以位于前平面之前、前平面与后平面之间、后平面之后，也可以与前平面或后平面重合。加上前平面与后平面之后，透视投影的观察体由原来顶端在投影参考点的无限延伸的四棱锥变成了四棱台（frustum）（图7. 3），平行投影的观察体由原来两端无限延伸的平行六面体变成了平行六面体（图7. 4）。有限观察体使得用户可以集中注意力去观察他们感兴趣的物体，不会受到其它物体的干扰。不断地改变前距离或后距离，使得物体的某些部分出现在投影图中，某些部分从投影图中消失，有助于用户理解物体不同部分的深度关系。对于透视投影来说，加上前平面与后平面之后还带来一些额外的好处：一个离投影中心非常近的物体，它的透视投影的大小会变成原来的很多倍，占据观察窗口的大部分，甚至覆盖整个观察窗口，由于过分放大，它的形状可能会变得不可辨认；一个离投影中心非常远的物体，它的透视投影会变得非常小，以至于不可辨认，并且，如果我们用笔式绘图仪来绘制这个物体，过分集中的笔画可能会使得绘图笔穿透绘图纸，如果我们用刷新式随机扫描显示器来显示这个物体，过分集中的电子束可能会烧坏荧光屏。加上前平面与后平面可以避免这些现象的发生。综上所述，观察平面上的观察窗口由其左下角坐标(umin,vmin)和右上角坐标(umax,vmax)来定义，给定观察窗口、投影参考点、投影类型、前距离、后距离等信息，就唯一地定义了一个有限观察体，透视投影的有限观察体是一个四棱台，平行投影的有限观察体是一个平行六面体。规范化观察体定义了观察体之后，我们就可以用三维裁剪算法将物体相对于观察体进行裁剪。三维裁剪是对二维裁剪的扩展。二维裁剪通常相对于边界平行于坐标轴的矩形窗口进行，要计算线段与窗口边界的交点，只要将窗口边界的x坐标（对于左边界和右边界）或y坐标（对于上边界和下边界）代入线段方程即可，计算量较小；然而在一般情况下，透视投影的有限观察体是一个斜四棱台，平行投影的有限观察体是一个斜平行六面体，要计算线段与观察体表面的交点，必须求解由线段方程和观察体表面方程组成的线性方程组，计算量较大。(a)平行投影 (b)透视投影图7. 5 规范化观察体如图7. 5所示，如果平行投影的观察体由如下六个平面定义u=-1, u=1, v=-1, v=1, n=0, n=-1 (7.4.1)透视投影的观察体由如下六个平面定义u=n, u=-n, v=n, v=-n, n=nmin, n=-1 (7.4.2)那么计算线段与观察体表面的交点就会容易得多。这样定义的观察体称为规范化观察体（canonical view volume）。现在我们把物体相对于观察体进行裁剪的问题分为两步来解决：先将观察体变换成规范化观察体，当然，对物体也要进行相同的变换；再将变换后的物体相对于规范化观察体进行裁剪。虽然这种分两步解决的方法会对位于观察体外部的物体进行观察体到规范化观察体变换，但是，将变换后的物体相对于规范化观察体进行裁剪比起原来直接将物体相对于观察体进行裁剪要容易得多。下面我们针对平行投影和透视投影分别讨论如何将观察体变换成规范化观察体。平行投影将平行投影的观察体变换成图7. 5(a)所示的规范化观察体可以按照如下步骤进行：对观察体进行相对于n轴的错切变换，使得投影方向DOP平行于n轴；(a)错切前 (b)错切后图7. 6 平行投影的观察体到规范化观察体变换（错切）如图7. 6所示，令投影参考点PRP=prpu prpv prpn 1T (7.4.3)窗口中心CW=(umax+umin)/2 (vmax+vmin)/2 0 1T (7.4.4)因为平行投影的投影方向DOP定义为从投影参考点PRP指向窗口中心CW的方向向量，所以DOP=CW-PRP =(umax+umin)/2 (vmax+vmin)/2 0 1T-prpu prpv prpn 1T =dopu dopv dopn 0T (7.4.5)假设相对于n轴的错切变换矩阵为SHn(shu,shv)= (7.4.6)该矩阵将投影方向向量DOP变换成平行于n轴的方向向量DOP。我们知道，相对于n轴的错切变换只改变u、v坐标，不改变n坐标，所以应该有DOP=SHn(shu,shv)DOP = = = (7.4.7)于是有shu=-dopu/dopn, shv=-dopv/dopn (7.4.8)我们将相对于n轴的错切变换矩阵SHn(shu,shv)记为SHparallel，即SHparallel= (7.4.9)对于正平行投影，投影方向DOP垂直于投影平面（平行于n轴），dopu=dopv=0，错切变换矩阵SHparallel是单位矩阵。比较公式(7.4.9)中的错切变换矩阵SHparallel与公式(7.2.15)中的斜投影矩阵Moblique，可以发现斜平行投影是由错切变换与正平行投影复合而成的。进行过相对于n轴的错切变换之后，平行投影的观察体由如下六个平面定义（图7. 6(b)）u=umin, u=umax, v=vmin, v=vmax, n=B, n=F (7.4.10)将观察体前表面的中心平移到坐标原点；从图7. 6(b)可以看出，观察体前表面的中心的坐标为(umax+umin)/2,(vmax+vmin)/2,F)，因此平移变换矩阵Tparallel=T(-(umax+umin)/2,-(vmax+vmin)/2,-F) (7.4.11)图7. 7 平行投影的观察体到规范化观察体变换（平移）图7. 7为平移后的结果。对图7. 7所示观察体进行缩放变换，得到平行投影的规范化观察体。图7. 5(a)所示平行投影的规范化观察体的大小为2*2*1，因此缩放变换矩阵Sparallel=S(2/(umax-umin),2/(vmax-vmin),1/(F-B) (7.4.12)如果没有给观察体加上前平面和后平面，那么F和B可以取满足BF的任意值，比如说，可以取F=1，B=0。综上所述，对于平行投影来说，观察体到规范化观察体变换矩阵为SparallelTparallelSHparallel (7.4.13)上述变换不但将平行投影的观察体从平行六面体变成长方体，而且将斜平行投影变成投影平面在uv平面的正平行投影，正平行投影的变换矩阵如公式(7.2.10)所示。透视投影将透视投影的观察体变换成图7. 5(b)所示的规范化观察体可以按照如下步骤进行：将投影参考点PRP（投影中心）平移到坐标原点，平移变换矩阵为T(-PRP)；对观察体进行相对于n轴的错切变换，使得观察体中心线与n轴重合；(a)错切前 (b)错切后图7. 8 透视投影的观察体到规范化观察体变换（错切）如图7. 8所示，观察体中心线是从投影参考点PRP指向窗口中心CW的方向向量，即为CW-PRP，并且步骤(1)平移变换不会改变该方向向量。将该方向向量变换成平行于n轴的方向向量，错切变换矩阵与平行投影时相同，也是公式(7.4.9)中的SHparallel。对观察体中心线也可以这样来理解：窗口中心CW经过步骤(1)平移变换到达新位置CW-PRP，观察体中心线是从投影参考点（在坐标原点）指向窗口中心（在CW-PRP）的方向向量，也为CW-PRP。考虑观察平面的位置，最初为n=0平面，经过步骤(1)平移变换变成n=-prpn平面，步骤(2)相对于n轴的错切变换对观察平面的位置没有影响，因此现在观察平面仍然为n=-prpn平面。因为观察窗口的大小不会受到步骤(1)平移变换和步骤(2)相对于n轴的错切变换的影响，并且现在窗口中心在n轴上，所以现在观察窗口的左下角坐标为(-(umax-umin)/2,-(vmax-vmin)/2,-prpn)，右上角坐标为(umax-umin)/2,(vmax-vmin)/2,-prpn)。前平面为n=-prpn+F平面，后平面为n=-prpn+B平面。对图7. 8(b)所示观察体进行缩放变换，得到图7. 9所示透视投影的规范化观察体。图7. 9 透视投影的规范化观察体步骤(3)缩放变换可以看作由两次缩放变换复合而成：首先，沿着u轴和v轴方向进行差值缩放，使得观察窗口的宽度和高度都变成2prpn，也就是使得观察体的四个侧面分别变成u=n、u=-n、v=n和v=-n平面，缩放变换矩阵为S(2prpn/(umax-umin),2prpn/(vmax-vmin),1)；接着，沿着u轴、v轴和n轴方向进行一致缩放，使得观察体的后平面从n=-prpn+B平面变成n=-1平面，缩放变换矩阵为S(-1/(-prpn+B),-1/(-prpn+B),-1/(-prpn+B)。由于本次缩放是一致缩放，因此观察体的四个侧面仍然是u=n、u=-n、v=n和v=-n平面，但是前平面变成了n=-(-prpn+F)/(-prpn+B)平面，记为n=nmin平面，投影平面变成了n=prpn/(-prpn+B)平面，记为n=npro平面，当然，后平面变成了z=-1平面。总的说来，步骤(3)缩放变换矩阵为Sperspective=S(-2prpn/(umax-umin)(-prpn+B),-2prpn/(vmax-vmin)(-prpn+B),-1/(-prpn+B) (7.4.14)综上所述，对于透视投影来说，观察体到规范化观察体变换矩阵为SperspectiveSHparallelT(-PRP) (7.4.15)上述变换不但将透视投影的观察体从斜四棱台变成正四棱台，而且将一般透视投影变成投影中心在坐标原点、投影平面在n=npro平面的透视投影，该透视投影的变换矩阵如公式(7.2.5)所示。如果除了观察参考点、观察平面法向量、观察向上向量之外，观察窗口、投影参考点也是在三维世界坐标系中定义的，那么我们可以将观察变换与观察体到规范化观察体变换结合起来，形成规范化变换（normalizing transformation）。规范化变换将物体从三维世界坐标系变换到三维规范化观察坐标系中，并且将三维世界坐标系中的观察体变换成三维规范化观察坐标系中的规范化观察体。平行投影的规范化变换矩阵Nparallel=Sp