3D图形编程指南5 续- 2D和3D裁剪

<b>4.1.3 裁剪多边形
</b>　　让我们讨论一下沿着矩形裁剪区域裁剪多边形。同上面讨论的线段裁剪相同，多边形裁剪涉及到在多边形边和裁剪区域的边上寻找交叉点。同线段裁剪使用的方法的不同之处在于，作为裁剪的结果，多边形的形状可能产生很大的变化。图4.7所示，边和顶点的数量会变得不同。


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image236.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.7 多边形裁剪的不同情形</B></FONT></TD></TR></TABLE>
　　多边形裁剪算法首次由<I>Sutherland</I>和<I>Hodgman</I>提出。在直线的情形中，我们要使用的方法非常具有概括性，可以沿着任意多边形裁剪区域裁剪多边形。在矩形屏幕这种情形中，我们将要为每个裁剪边计算裁剪例程一次，最后，获得符合所有强制标准的多边形。（参见图4.8）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image237.gif" border=0></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.8 迭代裁剪边</B></FONT></TD></TR></TABLE>
　　在每次迭代中，我们得到了改小了一些的问题，在这里，创建了精确地符合强制标准的新多边形。我们已经考虑了能够查找线段和裁剪边的交叉点的技术。再让我们讨论一下如何以单个有限线段来裁剪由一系列边形成的多边形。一个多边形通常表示为一定顺序的顶点。每对连接的顶点描述了一条边。只要其中一条边与裁剪边发生了交叉，我们就要找出一个交点，而它也必然成为裁剪后的多边形的顶点。（参见图4.9）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image238.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.9 沿着单个的裁剪边迭代多边形的边</B></FONT></TD></TR></TABLE>
　　在图4.9中，多边形ABCD在裁剪后变成了<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image239.gif">。为了推出这个事实，我们以在多边形的描述中出现的顺序来考虑多边形的边。当AB边跨过裁剪线的时候，我们在构建的多边形中增加一个顶点。进一步，顺着多边形定义的顺序，某些边必须穿回裁剪线。在这种情况下是交叉点<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image240.gif">。在交叉点之间的裁剪线限制了裁剪区域并且因此定义了裁剪多边形的边<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image241.gif">。
　　必须认识到，属于两条边的每个顶点以及多边形的描述都是一定顺序的顶点，每个顶点与列表中后一个顶点和前一个顶点分别形成了一条边。因此，在分析边的时候，我们必须考虑这么一个事实，即，在每一对中的第一个顶点可能已经被前一次迭代计算过了。让我们列出所有可能遭遇的情形。当一条边被简单地接受的时候，我们必须只从结果列表中复制它的第二个顶点，假定第一个已经先被考虑过了。当每对中第二个顶点超出裁剪区的时候，我们必须找出交叉点，并复制到结果列表中去。当一条边被抛除的时候，不复制任何顶点。最后可能的情形是，每对中的第一个顶点就超出裁剪区。对此，我们必须找出交叉点，把它同该对中的第二个顶点一起复制到结果中，因为第二个顶点仍没被计算。
　　完全被裁剪过的多边形下一步要传递给光栅处理例程，该例程把多边形作为一系列像素线绘制出来。在这里，裁剪边的水平边没有任何应用于光栅处理例程的附加信息。既然任意水平边与其它两个边共享端点，它唯一的像素线能从邻边找到，因此，我们可以不把水平边传递给扫描例程，同时并没有丢失连续性。（参见图4.10）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image242.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.10 扫描线与水平边相符</B></FONT></TD></TR></TABLE>
　　下面的例程实现了沿着两个垂直裁剪边同时裁剪多边形。这个算法确定了哪一个顶点复制到结果中而不需要因此进行修改。进一步，当我们有一个垂直裁剪过的多边形时，它的边一次一个地传递给边扫描函数，该函数寻找像素线的参数。扫描函数必须首先水平地裁剪边，因为我们只对在屏幕内的扫描线感兴趣。这两步走的方法确保了多边形的水平线不会被明确地创建，这样就改善了整体性能。（参见程序清单4.3）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image243.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>程序清单4.3 裁剪一个多边形</B></FONT></TD></TR></TABLE>
　　注意在程序清单4.3中出现的函数调用了边裁剪函数，边裁剪函数必须沿着两个垂直边界裁剪而且还要报告哪个顶点被裁剪掉了，这样，多边形裁剪例程就能够把正确的顶点复制到结果中的多边形描述中。必须提到，上面建议的算法不仅仅可以用于凸多边形，也可以用于凹多边形。然而，在大多数情况下，凹多边形可能被裁剪分割为多个部分。举例来说，在图4.11中的多边形<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image244.gif">被裁剪为两块：<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image245.gif">和<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image246.gif">。不太困难地就能看出，在这种情况中，这种算法实际就是单个的多边形合并了两块<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image247.gif">和<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image248.gif">，成为<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image249.gif">（参见图4.11）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image250.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.11 多边形裁剪分割</B></FONT></TD></TR></TABLE>
　　产生的这个多边形严格地说来不是简单多边形，因为<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image251.gif">和<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image252.gif">边在某一段上相同。这种多边形通常被称作“弱简单（<I>weakly-simple</I>）多边形”， 因为许多几何算法对此没有什么变化，我们考虑这个不是什么例外情况，而且无需什么变动或只需很小的变动就能够正确地绘制弱简单多边形。
<B></B>
<B>4.2、3D裁剪策略</B>
　　正如我们已经讨论过的，透视投影只适用于空间中所有点的子集。因为透视变换倒转了与观察者的距离，对z=0的点来说，它的结果是无穷远。它也忽略了在观察者后面的点，3D裁剪的目标就是确保只有有效的点进行变换。
　　因此，透视变换限制了在观察者前面的点的世界空间。在前几节，我们已经看到了沿着水平边和垂直边裁剪图元。在稍微概括一点的形式上，同样的解决方案也可适用于视平面裁剪的目的。唯一的不同是，必须考虑三个维而不是两个。
　　在透视变换之前沿着在观察者前方一点点的平面执行裁剪，抛除了在某方面可能引起除以零这种非法计算的点。然而，在该平面上已经被严格限制了的点仍然有可能以很大的绝对坐标值被映射到屏幕空间。但实际上，不太可能某些变换坐标太大以至于超出存储它们的变量位的大小。（参见图4.12）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image253.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.12 溢出的效果</B></FONT></TD></TR></TABLE>
　　存储在有符号表达式中的值很容易遇到溢出这个问题。因为负数被表示为了很大的正数，在数字上很大的被投影的点的坐标可能突然改变了符号，出现在平面的不同区域。如果它碰巧是描述某些图元的顶点，投影的连贯性将要丢失，在最可能想象到的情形中，这个图元可能突然占有了屏幕空间相当大的区域。比如说，一条直线，如果端点溢出，可能从左到右或从上到下地跨越整个屏幕。
　　一个简单的修补是尝试移动裁剪面远离视平面。这个不解决根本问题，只是把不可避免的点移得更远。在世界空间大小有限的情形下这就足够了。然而，大部分应用程序可能要考虑根本的解决方案。
　　注意到渲染算法的最终目标是在屏幕上绘制，我们能够在空间中根据它们被投影到屏幕上的能力来分离点。所有被投影到屏幕内部的点属于“视体（<I>view volume</I>）” 。投影到屏幕外的点当然也就在空间中视体的外部。同上面说的溢出的点可能不能在屏幕内显示出来的这个问题联系起来，如果我们在空间中导入某些把它限制在视体内的约束，我们就能避免这个问题。
　　让我们考虑一下平行投影和透视投影这两种情况，并且找出它们的视体。在这两种情况中，投影到屏幕边界的点把视体内的点和其余的点分割开来。在平行投影的情形中，投影线相互平行并通常与投影面正交。穿过屏幕边界的直线因而在同屏幕平面相符的投影面的前方定义了一个类似棱柱的视体。在透视投影的情形中，投影线与观察者的视线相交。穿过屏幕边界的投影线在空间中也形成了类似金字塔的视体（有时候我们把它称之为“视锥” — 译者），同样也限制了观察者前方较近处的裁剪面。（参见图4.13）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image254.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.13 透视投影和平行投影的视体</B></FONT></TD></TR></TABLE>
　　对使用平行投影的应用来说，2D屏幕边界裁剪限制了类棱柱视体。使用透视变换的应用程序通过某些办法限制了类金字塔的视体（视锥）的坐标，不需要屏幕边界裁剪，因为体裁剪的措施确保了所有的图元被投影到屏幕的内部。
　　除了确保透视变换和光栅处理函数的正确应用外，体裁剪也限制了一同进行处理的图元的数量。当然，我们越早确定无需出现在图象中的图元，我们要做的处理过程就越少。在透视变换中，由于使用了距离反转，远离观察者的图元在屏幕上看起来非常的小。在这些情况中，既然这类对象视觉效果微不足道，那么就有理由不用花费太多的时间去进行绘制。我们通常也向视体中加入后裁剪面，这样就可以抛除一些不想要的对象。
　　沿着透视视体裁剪附加了一个复杂问题：我们不得不沿着可能在空间任意位置的平面裁剪。在所有早先的情形中，我们能够利用裁剪边和裁剪面的简单几何结构，然而这里我们面临着一个相当一般化的情形。限制视体的6个面中只有两个有简单的方位，即前裁剪面和后裁剪面。其它的4个面的位置非常不方便。
　　在下一章中，我们准备检查一下如何在数学上描述这类平面的几何图元，以及如何在一般的情形下找出交叉点。问题解决方案的一般性通常要付出性能上的代价。在这个情形下也不例外。尽管我们能够在理论分析上解决交叉点问题，但通常这种方法可能是非常昂贵的以至于不能采用。下面让我们来看看可能的用于处理体裁剪问题的选择方案。
　　我们面临的主要的复杂性在于视体几何结构的不方便。因此第一个解决方案尝试改正这种情形。比较方便的视体是视域的角度为90度。在那种情形中，平面形成的透视视锥具有非常简单的等式：<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image255.gif">（参见图4.14）。沿着这种平面非常容易裁剪。


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image256.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.14 90度角的透视投影视体</B></FONT></TD></TR></TABLE>
　　然而，通常的情形是选择的视角域小于90度。在这些情形中，我们可以尝试缩放原始空间得到视体。裁剪能够沿着简单几何结构被执行，一旦这一步结束之后，空间被缩放回原始构造。
　　一个代替这种多步骤处理过程的选择是，我们可以决定在简单体内裁剪，进一步在较小的视角域中使用透视变换。作为这么做的结果，我们丢失了3D裁剪的重要品质。被投影的点可能位于屏幕外部，因此必须执行2D屏幕边界裁剪。
　　当然，进行这两种昂贵的裁剪处理过程并不合理。因此我们能够导入另一种简化的办法。在体裁剪阶段，我们沿着前后裁剪面裁剪，剩下的几个面只执行简单的接收和抛除测试。进一步，图元将要在屏幕空间中进行彻底的2D裁剪处理。
　　在第一步，我们避免了沿着前裁剪面裁剪时可能导致的除零问题。我们也在统计意义上避免了可能的溢出问题，因为可能导致溢出的大多数点被抛除测试删除了。只有在世界空间中跨越很长距离而仍然在视体和坐标最大数值的边界内的对象上的点可能仍然导致溢出。大多数时间我们假定这种情形不存在。
　　沿着90度角的视体进行的抛除处理很大程度上得到了体的简单几何结构的帮助。考虑一下图4.13。既然由等式<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image255.gif">描述的裁剪面。那么就很容易观察出在体外的空间（由<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image257.gif">描述）。如果某些图元所有的点都符合上面的不等式，图元被抛除。
　　在世界空间中个别的图元通常与某些复杂对象组合在一起。这些对象可能由几百个图元组成。如果某些顶点被抛除了，其它的顶点可能也要同样被抛除。我们可以利用这个位置属性，并且对对象上的图元执行抛除测试。对这些测试来说，我们需要一些精确的对象属性，这些属性告诉我们它是否可以被抛除。举例来说，在对象的中心在视体外的时候，这个中心不再合适了，因为对象的某些部分可能还在视体内。一个更好的途径是以某些简单几何结构边界来封闭这个对象。如果边界体与视体没有交叉，这种抛除可以安全地完成。通常使用的边界体是边界盒或边界球。（参见图4.15）


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image258.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.15 用于复杂几何结构对象的边界盒和边界球</B></FONT></TD></TR></TABLE>
　　边界盒表达了对象最小和最大的空间坐标，但边界球的半径要由从对象中心算起的最远点决定。
　　使用边界盒参数，我们能够检查来自视体的可能的抛除。举例来说，当盒最小的x坐标大于最大z坐标时，在X=Z平面外的对象可以被抛除。尽管我们已经考虑了用于复杂对象的边界盒可能在抛除个别图元的时候有帮助，但这类可能有很多顶点的多边形又出现了对个别图元计算的顺序的麻烦。
　　在程序清单4.4中的例程实现了抛除某些图元或抛除沿着边界盒参数指定的对象。


<TABLE cellSpacing=0 cellPadding=2 align=center border=0>

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image259.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>程序清单4.4 基于近似裁剪的的边界盒</B></FONT></TD></TR></TABLE>
　　边界球可以用同样的方式处理。在这种情况下，我们必须计算从裁剪面到球心的距离。如果这个距离大于球的半径，对象被抛除。在下一章中，我们将讨论计算从点到面的距离的数学算法。
<B>
　　小结</B>
<FONT face=楷体_GB2312 color=#993300>　　总的来说，我们讨论的裁剪算法必须确保同其他算法的一致性，比如说光栅处理算法或透视变换，它们也用于在世界空间中抛除对最终图象没什么用处的对象。考虑在2D多边形区域或3D多面体中通用的算法通常代价很昂贵，必须考虑某些简化的解决方案</FONT>。<FONT face=楷体_GB2312><FONT face=楷体_GB2312><FONT face=楷体_GB2312>
</FONT></FONT></FONT>