3D图形编程指南 6再续- 视处理

<b>5.2.5 直线和球的交叉点
　　</b>由定义，球是到一点（即球心）等距的所有的点构成的。该事实可使我们推导出球的公式如下：


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

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image525.gif"></TD></TR></TABLE>
　　在该公式中，X是球上的任何一点，M是球的中心，r是半径。该方程用到了向量<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image526.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/5.1/Image527.gif"></TD></TR></TABLE>
　　可以看出向量的长度为<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image528.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/5.1/Image529.gif">or <IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image530.gif"></TD></TR></TABLE>
　　为了求得球与直线的交叉点，我们必须同时求解表示两个图元的方程：


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

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image531.gif"></TD></TR>
<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image532.gif"></TD></TR></TABLE>
　　当解出该含t的二次曲面方程，我们要么可以得出代表直线与球只有一个交点的单根，要么得到直线穿过球的两个根，或者当交叉点不存在时没有实根。

　　<B>5.2.6 寻找合适的交叉点</B>
　　在所有的交叉点中，我们只对离观察者最近的感兴趣，因为从通过该点的平面反射的光线将无阻碍地到达我们的眼睛。
　　在前一节，我们已经解决了参数t形式的直线和图元的交叉点问题。参数t可以看作从点Q沿着直线到变量点X的，以向量<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image533.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/5.1/Image534.gif"></TD></TR></TABLE>
　　如果向量相等，那么它们的长度也是相等的，因此


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

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image535.gif"></TD></TR></TABLE>
　　根据光线投射算法，我们为屏幕上每个像素投影射线。如果我们使用观察者和当前像素的坐标定义射线，参数t就可以作为到观察者距离的度量。（参见图5.17）


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

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image536.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图5.17 寻找正确的交叉点</B></FONT></TD></TR></TABLE>
　　我们可以进一步利用该特性，并比较从不同的交叉点得到的参数t，最小的t定义了离观察者最近的交叉点。对每个像素执行这种计算将使我们解决整个图像的可见性问题。应该注意的是，该方法很容易适用于纹理映射，为了做到这一点，基本上我们只需知道定义纹理的对象空间的交叉点的坐标。知道了交叉点的世界坐标，并计算出从世界空间到对象空间的逆变换后，该坐标很容易获得。
　　正如在前面提到的，为了确保合适的光照还必须做额外的工作。考虑到该主题的广泛性和极其重要性，我们将在另一章继续讨论它。此处，我们将集中于改进光线投射方法的技术。
<A>
　　</A><B>5.2.7 优化光线投射（ray casting）</B>
　　光线投射由于其思想简单而极其吸引人。我们省去了讨厌的光栅处理和剪裁以及最后将要讨论的隐面消除。而且，我们将发现，光照和阴影生成只需通过扩展光线投射方法而轻易达到。
　　然而，最大的问题在于光线投射的个别步骤是极其昂贵的。潜在地，我们必须找到每条光线与世界中每个表面的交叉点。由于可能有成千的表面，这将导致巨大的花费。直接处理将几乎不可能达到实时帧速率，至少是在目前的硬件条件下。
　　因此，光线投射通常用于非实时应用，可以产生极好的图像，有时与照片图像难以辨别。只有放宽相当多的条件才可能允许光线追踪器的实时运行。能做到这一点的应用还是有的，如计算机游戏领域。象<I>ID</I> software的<I>DOOM</I>，它不是对每个像素作光线追踪，而是对一队像素作光线追踪。实时表现的代价就是简化世界中的几何体，只允许和想象的地面平行或垂直的多边形并减少自由度（无倾斜和俯仰）。这些放宽只是适合于室内渲染而对于飞行模拟并不可行。尽管如此，我们也不能对光线追踪方法在交互式三维应用中的作用打折扣。而且，由于光线计算是相互独立的，这将存在把问题并行处理的可能，并且在多处理器上运行的应用程序的速度将提升到可观的水平。
　　让我们考虑可能的算法来改进光线投射的性能。
　　不难看出，主要的花费来自于计算光线和场景中每个表面的交叉点。我们将努力使单独的计算花费便宜，并在较容易推出交叉点不存在时要避免计算交叉点。
　　一个可能的途径是预计算多边形在选定的参考平面上的投影以及在投影中的边方程。这将减少其它昂贵的计算。
　　然而，最大的性能提升来自于避免不必要的交叉点的计算。通常很容易推导出一条光线和某个图元的交叉点不可能存在。在前面的章节中我们已经明白了约束体方法，使用该方法可以将一个由许多图元组成的对象用简单几何体封闭起来。如果与其交叉点不存在，我们可以避免进一步分析被包围的图元。球和盒是最常用的约束体。
　　另一个采用了相似策略的途径是空间细分。如果空间被分割为单元（cell），我们可以只计算那些单元被光线分割的图元的交叉点。（参见图5.18）


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

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image537.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图5.18 空间细分</B></FONT></TD></TR></TABLE>
　　最简单的分割策略是将空间分割成一致的单元，它还允许采用基于整数的算法来寻求哪个单元被光线分割。在讨论光栅化技术的时候我们已经熟悉了基于整数的算法。其它涉及到树的分割策略将在建模和隐藏面消除中讨论。

　　<B>小结</B>
<FONT face=楷体_GB2312 color=#993300>　　总的来说，我们已经讨论了两种基本的观察三维场景的方法。世界到屏幕的方法将图元投影到屏幕，而屏幕到世界的方法将相应的屏幕像素光线投射到世界内。尽管后者从概念上较为简单，但它涉及到许多交叉点的计算，因此相当昂贵。</FONT>