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

<b>目 录
　　</b>4.1 <a href="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/4.htm#4.1" target="_blank" ><FONT color=#000000>2D裁剪策略</FONT></A>
　　　4.1.1 <a href="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/4.htm#4.1.1" target="_blank" ><FONT color=#000000>点的裁剪</FONT></A>
　　　4.1.2 <a href="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/4.htm#4.1.2" target="_blank" ><FONT color=#000000>裁剪线段</FONT></A>
　　　4.1.3 <a href="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/4.htm#4.1.3" target="_blank" ><FONT color=#000000>裁剪多边形</FONT></A>
　　4.2 <a href="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/4.htm#4.2" target="_blank" ><FONT color=#000000>3D裁剪策略</FONT></A>


<HR align=center width="95%" noShade SIZE=1>

　　<B>引言</B>
　　在前几章的讨论中，我们假设光栅化的图元都在屏幕的边界中。当然，通常说来，这种假设是不可能成立的。在实际的生活中，视处理可能产生全部在屏幕边界外或者部分在边界外的图元。在这两种情况中，一些像素的地址可能超出了分配给位图的存储空间。为了避免这种不希望的效果，我们必须严格限制图元坐标在屏幕的边界内。
　　我们也看到在透视变换中存在着另一种对坐标的约束。我们不能在屏幕空间中变换<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image215.gif">的点。而且，具有负z的对象位置在观察者的后面，因此是不可见的。为了避免这个问题，例如被0除，或者对象的部分被透视变换过剪切， 我们必须确保只有有效点被变换，进入透视屏幕空间。定位适合这种空间约束的图元部分的过程称之为裁剪。上面这两种情况中，对前一种情况，我们必须执行2D或屏幕边界裁剪，对第二种情况是3D或体裁剪。在这一章中我们必须考虑这两种情况，讨论可能的实现方法。
<B></B>
<B>4.1、2D 裁剪策略
</B>　　作为某种图元的输入描述，裁剪算法同时也是依此执行裁剪的图元（2D区域或3D域）规范。同光栅处理一样，通常也很难找出一种适合任意形状和任意裁剪体的策略，这主要是受到开销的约束。
　　对2D裁剪，我们可以定义三个不同的途径。第一种途径是在光栅处理阶段前裁剪。这种方法用于处理简单图元，比如说被矩形等简单裁剪区域约束的多边形等。在某些情形下，尤其对复杂图元来说，在光栅处理阶段进行裁剪比较合适。在得到像素的屏幕坐标后，首先要检查它是否在合适的边界内，只有在这种情况下才进行标绘像素的处理。当裁剪区域几何结构比较复杂的时候，选择的策略可能是在一些较大的缓冲区里光栅化图元，然后只从缓冲区里选择在该复杂裁剪区域内部的像素。（参见图4.1）


<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/Image216.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.1 不同的裁剪类型</B></FONT></TD></TR></TABLE>
　　通常，对开销的考虑确定了应用哪种裁剪策略。第一种策略在分析寻找和描述裁剪区域内部图元中耗费的开销不太大的时候工作得很好。当开销相对大一些的时候，比如说寻找和分析描述圆和矩形的交叉点，可以使用第二种策略：在光栅处理过程中裁剪。当在运行中进行的预裁剪和验证像素关于裁剪区域的位置耗费的开销比较大的时候，可以考虑第三种策略。比如说，当裁剪区域是圆或椭圆的时候我们可以使用这种策略。
　　既然大多数时间，我们在以矩形裁剪区域 — 计算机屏幕，进行处理，也由于简单的几何图元通常也适用于其它的算法，我们主要集中考虑第一种策略。因此，在下面我们讨论一下如何在矩形区域内裁剪点、线段和多边形。
<B></B>
　　<B>4.1.1 点的裁剪</B>
　　我们最感兴趣的是矩形裁剪区域，区域以四个有限线段描述，限制了屏幕的最小和最大的水平坐标以及最小和最大的垂直坐标。对这个区域来说，点的裁剪可以通过沿着这四个约束来检查点的坐标完成。
　　尽管这种做法已经相当的廉价，但我们还可以在区域的限制线段通过坐标起点的时候改善一下性能。由于负数在重新解释为无符号数值类型的时候看起来象是个非常大的正数（回忆一下第二章，第2.8节），在这种特别的情形下，沿着另两条限制直线比较点已经足以做出正确的决定了。
<B></B>
　　<B>4.1.2 裁剪线段</B>
　　我们可以为直线裁剪扩展上面的方法，在标绘每个像素之前，每次都要检查它是否在边界内。然而，在光栅处理同时应用这种策略则增加了光栅处理内循环的复杂性。而且，在图象位图内以点的地址优化线段的绘制要好于以屏幕坐标优化。
　　这种预裁剪方法分析了图元相对约束的位置并且找出符合这一点的图元部分。在线段裁剪的情况下，需要找出交叉点或线段与裁剪边界的交叉点。通常不是直接就能把这种交叉发生的地方看得一清二楚的。（参见图4.2）


<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/Image217.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.2 线段与矩形裁剪区域交叉</B></FONT></TD></TR></TABLE>
　　一种普通的策略是使用第一次由<I>Cohen</I>和<I>Sutherland</I>在七十年代提出的算法，通过沿着边界裁剪，可能的话定位交叉点，然后作为子问题来处理另一个边界，这样可以保证找到符合所有情形的线段的端点。考虑在图4.3的例子。线段AB第一次被边界<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image218.gif">裁剪，我们找到交叉点<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image219.gif">并且进一步地以边界<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image220.gif">处理<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image221.gif">段， 这也就是原始问题的子问题。这种策略非常普通，可以被用于在任意多边形区域内裁剪线段，而不一定非得是矩形。


<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/Image222.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.3 一条线段与矩形裁剪区域相交叉</B></FONT></TD></TR></TABLE>
　　当我们可能需要找出多个交叉点的时候，这些点中的某些可能是无用的，只要有可能，避免计算它非常重要。有时，当可以很简单地推断出某条线在裁剪区域内部或外部的时候，我们可以简单地排斥或接受一条线。举例来说，当线段两个端点的水平坐标小于最小的可接受的屏幕坐标的时候，这种线段可以被安全地排斥。同样的做法也可用于其它的边界和水平坐标之间。
　　有一种简单地接受或排斥的方法，它加速了比较环节， 这种方法被称之为区域外编码（<I>region outcodes</I>）。我们为平面分配一个位编码样式，通过这种方法，每个编码位注明了图元是否出现在某个矩形裁剪区域外。（参见图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/Image223.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.4 外编码(<I>Outcodes</I>)</B></FONT></TD></TR></TABLE>
　　在图4.4中演示的这种技术的典型例子中，外编码的第一位描述了在裁剪矩形上方的区域。如果我们对线段的两个端点分配这种外编码，有可能使用位运算来检查它们在平面中的组合位置。如果某些位对两个端点来说是置位的（为“1”），则说明在那个区域内的整个线段在裁剪区域的外部。这个事实可以通过对整个位都进行位“与”运算来校验。如果结果是非零，线段可以安全地被排斥。另一方面，如果任一位对线段的端点来说是置位的，则要进行裁剪处理。只有线段没有被置位的位（全部为“0”），才可以简单地接受它。这个事实可以通过位“或”运算来校验。外编码也帮助确定线段交叉了哪一个裁剪边，以及我们要在哪里计算交叉点。
　　只要线段不能简单地被接受或排斥，就要进行裁剪处理。正如我们已经注意到的，这个过程要涉及到寻找交叉点。在垂直和水平裁剪边的情况下，要寻找与线段的交叉点非常地容易。（参见图4.5）


<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/Image224.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.5 沿垂直边裁剪线段</B></FONT></TD></TR></TABLE>
　　作为图4.5中的例子，其解决方案涉及到分析两个同样的三角形的关系。既然交叉点属于已知<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image225.gif">坐标的裁剪边，因此剩下的工作是寻找对应的<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image226.gif">坐标。我们可以这么计算：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image227.gif"></TD></TR></TABLE>
　　同样的表达式也用于已知垂直边<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image228.gif">求<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image229.gif">的情况 。裁剪线段的开销通常不是很大。每个点只涉及到一次乘法和一次除法。然而，正如我们在第三章所看到的，在某些情况下，线段可能已经乘上了在每个顶点中定义的值。举例来说，明暗处理多边形除了空间坐标外，也处理光线强度值；还有纹理多边形要处理纹理坐标等。因此，作为裁剪处理的结果，我们必须为所用的坐标（空间的或非空间的）寻找正确的值。当然，这个可以通过多次计算查找公式，每次对应一个坐标来完成。然而，这么做，我们增加了阶次的开销，因此要考虑一种替代解决方案。
　　对图形应用来说，不涉及到乘法或除法的方法通常是很吸引人的，因为这么做的花费很小。在裁剪这种情况中，我们能使用“二分搜索（<I>binary search</I>）”这种方法，它只涉及到不是很昂贵的整数运算。（参见图4.6）


<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/Image230.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图4.6 二分搜索裁剪</B></FONT></TD></TR></TABLE>
　　二分搜索算法，通常用于寻找方程的根，通过反复迭代减小问题空间的大小，直到得出答案。应用到裁剪问题上，这种算法寻找线段的中点并沿着裁剪边比较它的位置。在此阶段得到的两个线段，其中一个被抛除，下一次迭代在剩下的范围中进行，这个范围要小于原始的线段。举例来说，在图4.6中的线段AB被分割为两部分：从端点A到中点<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image231.gif">，以及从<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image231.gif">到另一个端点B。通过比较中点的x坐标和裁剪边的x坐标，我们推断出边位于中点的右侧，即线段<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image232.gif">。剩下的线段<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image233.gif">被抛除。算法不断重复迭代，直到中点的x坐标和边的相等或足够接近。
　　尽管，这里可能涉及到好几次迭代，但在每一次迭代中，新的子问题的空间只有原先的一半，因此这种迭代应该很快就能终止。在计算中点时只需要非常廉价的运算：


<TABLE cellSpacing=0 cellPadding=0 width="90%" align=center border=0>

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/4.1/Image234.gif"></TD></TR></TABLE>
　　正如我们看到的，只使用加法和除2的除法，后者我们已经讨论过，可以通过移位运算来完成。然而，需要特别注意的是迭代终止条件。由于整数的截断，迭代可能会进入死循环，不能完全使等式的x坐标达到精确。我们必须仔细地考虑中点计算的特别的性能并且确保不出现意料之外的情形。后面的程序清单4.1是一个使用二分搜索技术沿着最小垂直边界裁剪的实现例程。沿着其它边界的裁剪可以使用同样的方式完成，组合全部的四个，就产生了沿着矩形屏幕区域裁剪的效果。


<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/Image235.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>程序清单4.1 二分搜索裁剪</B></FONT></TD></TR></TABLE>
　　注意，在程序清单4.1中的例程设计为在每个顶点内处理多个维，不仅仅用于线段的裁剪，但也可用于明暗处理或纹理多边形的边裁剪。对裁剪函数的调用必须放在线段光栅处理的前面，在这里假设了整个图元都在屏幕边界内。
　　尽管我们已经考虑的仅仅是水平或垂直裁剪的简单情形，但我们看到的这两种算法都是非常概括的，可以被用于任何裁剪区域。即，可以处理寻找任意方向线段的交叉点。在下一章中，我们将要讨论如何在数学上描述几何图元，以及如何使用通过交叉点进行计算的图元方程。