《SutherlandHodgman多边形裁剪算法》由会员分享，可在线阅读，更多相关《SutherlandHodgman多边形裁剪算法（9页珍藏版）》请在金锄头文库上搜索。
1、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 ) /* 水平边界
2、*/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;/* 如果顶点 te
3、stvertex 在窗口边界 clipboundary 的内部，那么返回 TRUE；否则返回FALSE */if ( clipboundary1.x 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 (
4、 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, outver
5、texlist, 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; /* 输入
6、顶点序列的最后一个顶点 */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,outputvertex(i,outlength,outvertexlist);outputvertex(p,outlength,outvertexli
7、st);else /* 情况 2 和 3 */ if ( inside(s,clipboundary) ) /* 情况 2 */intersect(s,p,clipboundary,outputvertex(i,outlength,outvertexlist); /* 情况 3 无输出 */s = p; /* 准备处理下一条边 */观察体变换观察窗口是一个二维裁剪窗口，当三维空间中的物体被投影到投影平面（观察平面）之后，位于观察窗口内部的部分被变换到视区中显示或输出，而位于观察窗口外部的部分被裁剪掉，不再继续处理。这是一种“先投影后裁剪”的方法，需要对三维空间中的所有物体（包括投影后将要被裁剪
8、掉的物体）都进行投影变换，因而效率比较低。此外，对于一般的透视投影来说， “先投影后裁剪”还可能得到错误的结果（见习题 8） 。所以在三维观察中一般不采用这种“先投影后裁剪”的方法。观 察 平 面 vuCWVRPVPNn 投 影 中 心(PRP)图 7. 1 透视投影的观察体观 察 平 面CWVRPVPNnPRPDOP图 7. 2 平行投影的观察体如 图 7. 1 和 图 7. 2 所示，在三维观察坐标系 VRC 中，给定观察窗口、投影参考点PRP（projection reference point）和投影类型之后，我们就定义了一个观察体（view volume） 。可以用三维裁剪算法将物体
9、相对于观察体进行裁剪，对位于观察体内部的部分进行投影变换，生成其图形输出；而位于观察体外部的部分不再继续处理，不生成其图形输出。这是一种“先裁剪后投影”的方法，是在三维观察中普遍采用的方法。透视投影的观察体与平行投影的观察体有所不同。对于透视投影来说，投影参考点 PRP 就是投影中心，从投影参考点分别向观察窗口的四个角点引射线，得到一个顶端在投影参考点的无限延伸的四棱锥（pyramid） ，即为透视投影的观察体（ 图 7. 1） 。对于平行投影来说，投影方向 DOP（direction of projection）定义为从投影参考点 PRP指向窗口中心 CW 的方向向量，经过观察窗口的四个角点
10、分别作平行于投影方向的直线，得到一个两端无限延伸的平行六面体（parallelpiped） ，即为平行投影的观察体（ 图 7. 2） 。现在我们得到的观察体是无限延伸的，位于这个无限延伸的观察体内部的物体都会被投影到观察窗口中。有的时候，我们希望观察体是有限的。F B后 裁 剪 平 面VPNVRP前 裁 剪 平 面观 察 平 面图 7. 3 透视投影的有限观察体BFVPNDOPVRP后 裁 剪 平 面前 裁 剪 平 面 观 察 平 面图 7. 4 平行投影的有限观察体如 图 7. 3 和 图 7. 4 所示，我们可以用前裁剪平面（front clipping plane）和后裁剪平面（back
11、 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 轴）指向的方向
12、为正方向，其反方向为负方向。为了保证观察体不为空，前距离 F 应该大于后距离 B。对于透视投影，前平面应该在投影参考点 PRP（投影中心）与后平面之间；对于平行投影，前平面应该在正无穷远与后平面之间。虽然前平面与后平面的相对位置是确定的，但是观察平面与它们的相对位置却是可变的，观察平面可以位于前平面之前、前平面与后平面之间、后平面之后，也可以与前平面或后平面重合。加上前平面与后平面之后，透视投影的观察体由原来顶端在投影参考点的无限延伸的四棱锥变成了四棱台（frustum） （ 图 7. 3） ，平行投影的观察体由原来两端无限延伸的平行六面体变成了平行六面体（ 图 7. 4） 。有限观察体使得用
13、户可以集中注意力去观察他们感兴趣的物体，不会受到其它物体的干扰。不断地改变前距离或后距离，使得物体的某些部分出现在投影图中，某些部分从投影图中消失，有助于用户理解物体不同部分的深度关系。对于透视投影来说，加上前平面与后平面之后还带来一些额外的好处：一个离投影中心非常近的物体，它的透视投影的大小会变成原来的很多倍，占据观察窗口的大部分，甚至覆盖整个观察窗口，由于过分放大，它的形状可能会变得不可辨认；一个离投影中心非常远的物体，它的透视投影会变得非常小，以至于不可辨认，并且，如果我们用笔式绘图仪来绘制这个物体，过分集中的笔画可能会使得绘图笔穿透绘图纸，如果我们用刷新式随机扫描显示器来显示这个物体，
14、过分集中的电子束可能会烧坏荧光屏。加上前平面与后平面可以避免这些现象的发生。综上所述，观察平面上的观察窗口由其左下角坐标(umin,vmin)和右上角坐标(umax,vmax)来定义，给定观察窗口、投影参考点、投影类型、前距离、后距离等信息，就唯一地定义了一个有限观察体，透视投影的有限观察体是一个四棱台，平行投影的有限观察体是一个平行六面体。规范化观察体定义了观察体之后，我们就可以用三维裁剪算法将物体相对于观察体进行裁剪。三维裁剪是对二维裁剪的扩展。二维裁剪通常相对于边界平行于坐标轴的矩形窗口进行，要计算线段与窗口边界的交点，只要将窗口边界的 x 坐标（对于左边界和右边界）或 y 坐标（对于上
15、边界和下边界）代入线段方程即可，计算量较小；然而在一般情况下，透视投影的有限观察体是一个斜四棱台，平行投影的有限观察体是一个斜平行六面体，要计算线段与观察体表面的交点，必须求解由线段方程和观察体表面方程组成的线性方程组，计算量较大。u(v)n前 平 面后 平 面-1-11 u(v)n前 平 面后 平 面-1-11(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
16、, n=-1 (7.4.2)那么计算线段与观察体表面的交点就会容易得多。这样定义的观察体称为规范化观察体（canonical view volume ） 。现在我们把物体相对于观察体进行裁剪的问题分为两步来解决：先将观察体变换成规范化观察体，当然，对物体也要进行相同的变换；再将变换后的物体相对于规范化观察体进行裁剪。虽然这种分两步解决的方法会对位于观察体外部的物体进行观察体到规范化观察体变换，但是，将变换后的物体相对于规范化观察体进行裁剪比起原来直接将物体相对于观察体进行裁剪要容易得多。下面我们针对平行投影和透视投影分别讨论如何将观察体变换成规范化观察体。平行投影将平行投影的观察体变换成 图 7. 5(a)所示的规范化观察体可以按照如下步骤进行：对观察体
