图形编程指南chapter4new

《图形编程指南chapter4new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、14第四章2D和3D裁剪目录4.12D裁剪策略4.1.1点的裁剪4.1.2裁剪线段4.1.3裁剪多边形4.23D裁剪策略引言在前几章的讨论中，我们假设光栅化的图元都在屏幕的边界中。当然，通常说来，这种假设是不可能成立的。在实际的生活中，视处理可能产生全部在屏幕边界外或者部分在边界外的图元。在这两种情况中，一些像素的地址可能超出了分配给位图的存储空间。为了避免这种不希望的效果，我们必须严格限制图元坐标在屏幕的边界内。我们也看到在透视变换中存在着另一种对坐标的约束。我们不能在屏幕空间中变换的点。而且

2、，具有负z的对象位置在观察者的后面，因此是不可见的。为了避免这个问题，例如被0除，或者对象的部分被透视变换过剪切，我们必须确保只有有效点被变换，进入透视屏幕空间。定位适合这种空间约束的图元部分的过程称之为裁剪。上面这两种情况中，对前一种情况，我们必须执行2D或屏幕边界裁剪，对第二种情况是3D或体裁剪。在这一章中我们必须考虑这两种情况，讨论可能的实现方法。4.12D裁剪策略作为某种图元的输入描述，裁剪算法同时也是依此执行裁剪的图元（2D区域或3D域）规范。同光栅处理一样，通常也很难找出一种适合任意

3、形状和任意裁剪体的策略，这主要是受到开销的约束。对2D裁剪，我们可以定义三个不同的途径。第一种途径是在光栅处理阶段前裁剪。这种方法用于处理简单图元，比如说被矩形等简单裁剪区域约束的多边形等。在某些情形下，尤其对复杂图元来说，在光栅处理阶段进行裁剪比较合适。在得到像素的屏幕坐标后，首先要检查它是否在合适的边界内，只有在这种情况下才进行标绘像素的处理。当裁剪区域几何结构比较复杂的时候，选择的策略可能是在一些较大的缓冲区里光栅化图元，然后只从缓冲区里选择在该复杂裁剪区域内部的像素。（参见图4.1）14

4、图4.1:不同的裁剪类型通常，对开销的考虑确定了应用哪种裁剪策略。第一种策略在分析寻找和描述裁剪区域内部图元中耗费的开销不太大的时候工作得很好。当开销相对大一些的时候，比如说寻找和分析描述圆和矩形的交叉点，可以使用第二种策略：在光栅处理过程中裁剪。当在运行中进行的预裁剪和验证像素关于裁剪区域的位置耗费的开销比较大的时候，可以考虑第三种策略。比如说，当裁剪区域是圆或椭圆的时候我们可以使用这种策略。既然大多数时间，我们在以矩形裁剪区域——计算机屏幕，进行处理，也由于简单的几何图元通常也适用于其它的算

5、法，我们主要集中考虑第一种策略。因此，在下面我们讨论一下如何在矩形区域内裁剪点、线段和多边形。4.1.1点的裁剪我们最感兴趣的是矩形裁剪区域，区域以四个有限线段描述，限制了屏幕的最小和最大的水平坐标以及最小和最大的垂直坐标。对这个区域来说，点的裁剪可以通过沿着这四个约束来检查点的坐标完成。尽管这种做法已经相当的廉价，但我们还可以在区域的限制线段通过坐标起点的时候改善一下性能。由于负数在重新解释为无符号数值类型的时候看起来象是个非常大的正数（回忆一下第二章，第2.8节），在这种特别的情形下，沿着另

6、两条限制直线比较点已经足以做出正确的决定了。4.1.2裁剪线段我们可以为直线裁剪扩展上面的方法，在标绘每个像素之前，每次都要检查它是否在边界内。然而，在光栅处理同时应用这种策略则增加了光栅处理内循环的复杂性。而且，在图象位图内以点的地址优化线段的绘制要好于以屏幕坐标优化。这种预裁剪方法分析了图元相对约束的位置并且找出符合这一点的图元部分。在线段裁剪的情况下，需要找出交叉点或线段与裁剪边界的交叉点。通常不是直接就能把这种交叉发生的地方看得一清二楚的。（参见图4.2）14图4.2:线段与矩形裁剪区域

7、交叉一种普通的策略是使用第一次由Cohen和Sutherland在七十年代提出的算法，通过沿着边界裁剪，可能的话定位交叉点，然后作为子问题来处理另一个边界，这样可以保证找到符合所有情形的线段的端点。考虑在图4.3的例子。线段AB第一次被边界裁剪，我们找到交叉点并且进一步地以边界处理段，这也就是原始问题的子问题。这种策略非常普通，可以被用于在任意多边形区域内裁剪线段，而不一定非得是矩形。图4.3:一条线段与矩形裁剪区域相交叉当我们可能需要找出多个交叉点的时候，这些点中的某些可能是无用的，只要有可能

8、，避免计算它非常重要。有时，当可以很简单地推断出某条线在裁剪区域内部或外部的时候，我们可以简单地排斥或接受一条线。举例来说，当线段两个端点的水平坐标小于最小的可接受的屏幕坐标的时候，这种线段可以被安全地排斥。同样的做法也可用于其它的边界和水平坐标之间。有一种简单地接受或排斥的方法，它加速了比较环节，这种方法被称之为区域外编码（regionoutcodes）。我们为平面分配一个位编码样式，通过这种方法，每个编码位注明了图元是否出现在某个矩形裁剪区域外。（参见图4.4）14图4.4:外编码（Outc