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

<b>5.2、从屏幕到世界的方法
</b>　　从屏幕到世界的方法，与前面考虑的不一样，它是通过从观察者的眼睛逆追踪光线到空间来寻找虚拟世界的图象。
　　一个通用的策略是产生一束光线遍历屏幕上的每个象素，并计算世界中所有图元导致的交叉点。在所有的交叉点中，我们感兴趣的是离观察者最近的点，因为这是在所选的屏幕象素中的可见点（参见图5.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/5.1/Image437.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图5.6 光线投射(<I>Ray casting</I>)</B></FONT></TD></TR></TABLE>
　　尽管该方法解决了可见性问题，但它对于决定分配给屏幕上象素的颜色却没有帮助。尽管我们将在专门的章节中讨论光照和颜色问题，就目前而言，让我们假设可以通过分析被光线分割的表面属性来推演出颜色。
　　同时我们必须注意到，我们可以通过应用与从世界到屏幕方法中所采用的完全相同的坐标变换从对象空间坐标得到单个对象在世界空间中的坐标。然而，对这种观察方法来说，我们并不需要明确地将坐标变换到视空间，继而变换到屏幕空间。由于是通过计算交叉点得到视点，我们可以直接在世界空间中形成需要的光线，并在此执行所有将来的计算（参见图5.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/5.1/Image438.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图5.7 用于光线投射的摄像机定义</B></FONT></TD></TR></TABLE>
　　图5.7表明，如果摄象机通过如下的方式：点O描述世界中屏幕中心的位置，正交向量<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image439.gif">描述屏幕方向以及点V指定观察者的位置来指定，则将很容易按以下方法得到任意屏幕象素<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image440.gif">的世界坐标<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image441.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/Image442.gif"></TD></TR>
<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image443.gif"></TD></TR>
<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image444.gif"></TD></TR></TABLE>
　　这些表达式可以通过与第二章中我们考虑透视纹理映射时所用的相同的方法得到。进一步，当我们得到点R的世界坐标，我们将能够定义一条通过它且源于点V的光线。
　　尽管其他定义摄象机的方法也是可行的，在所有的情形中，我们应构建世界空间中必须的射线，避免额外的坐标变换。因此，剩下的主要问题是如何找到射线和几何原始图元之间的交叉点。让我们首先考虑表示基本图元的数学形式：直线、平面、多边形和圆，然后考虑如何计算交叉点的坐标。

<B>5.2.1 直线方程</B>
　　有许多方法可以指定一条直线。让我们假设直线通过给定的点Q， 向量<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image445.gif">与直线同向。我们用变量X描述直线上的任意点（参见图5.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/5.1/Image446.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图5.8 直线和它的同向向量</B></FONT></TD></TR></TABLE>
　　不难看出，任何其他的表示直线的方法都可以归结为以上的情况。比如，给定属于该直线的两点<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image447.gif">和<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image448.gif">，我们就可以找到向量<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image449.gif">和该直线同向。为了按要求彻底地描述，除了这个向量外， 我们还可以任取两点构成向量。
　　使用变量点X和给定的点Q， 我们可以得到另一个同向向量<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image450.gif">。向量<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image451.gif">和 <IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image450.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/Image452.gif"></TD></TR></TABLE>
　　在该方程中，t是某个标量。方程可以进一步改写成如下熟悉的参数形式：


<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/Image453.gif"></TD></TR></TABLE>
　　由此，通过该变参t，我们可以得到直线上的不同的点。应该注意的是，<I>X</I>、 <I>Q</I> 和<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image454.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/Image455.gif"></TD></TR></TABLE>
　　这种形式给出了几种与向量形式不同的，用分量表示的形式。比如：如果两个二元组相等，那么他们各自的分量也相等，从这个事实中，我们得出三个方程。从每个方程中，我们都可以表示出参数t。


<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/Image456.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/Image457.gif"></TD></TR></TABLE>
　　大多数情况下我们使用参数形式，因为我们寻找直线和几个几何对象的交点时，使用参数t比较交点之间的距离比较方便。同时，射线方程可以通过将点Q作为起点，并限制参数t为正来计算直线方程得到。

　　<B>5.2.2 平面方程</B>
　　在我们得出平面方程的公式之前，我们必须考虑一个重要的概念：向量乘。在向量空间定义了两种不同的乘积：向量积和标量积。正如其名，前者两个向量相乘得到一个向量，后者则得到一个标量值。
　　按照定义，向量积表示成<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image458.gif">，它满足以下三条特性：

　　1.<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image459.gif">-两个向量积的长度是各自长度和它们夹角的sin 值的乘积（标准符号<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image460.gif">表示向量<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image461.gif">的长度）。
　　2.<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image458.gif">和<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image462.gif">和<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image463.gif">正交。
　　3.<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image462.gif">,<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image463.gif"> 和<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image458.gif">形成右旋三向量。即如果从<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image458.gif">的底端看，从<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image462.gif"> 到<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image463.gif">的旋转是反时针方向的。（参见图5.9）

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

<TR align=middle>
<TD colSpan=3>
<TABLE cellSpacing=0 cellPadding=0 width="100%" bgColor=#ffffff border=0>

<TR>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image464.gif"></TD></TR></TABLE></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图5.9 右旋三向量（<I>Right triple of vectors</I>）</B></FONT></TD></TR></TABLE>
　　我们感兴趣的是第二条特性：两个向量的向量积与这两个给定的向量正交。对于一个平面来说，其法向量可以通过平面内的任意两条向量的向量积来计算得到。特性3说明向量积两个可能的指向。
　　让我们通过计算两条给定的向量的向量积来推出公式。任何向量都可以表示成基向量的线性组合。3D空间中常用的基向量是三个相互正交的右旋单位向量：


<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/Image465.gif"></TD></TR></TABLE>
　　任意向量A可以表示为：


<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/Image466.gif"></TD></TR></TABLE>
　　上式是基向量的线性组合。由向量积的定义容易看出任何两个基向量的向量积等于第三个基向量或为其负向量。如<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image467.gif">和<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image468.gif">的向量积必和它们都正交。由于<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image469.gif">，并且<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image467.gif">和<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image468.gif">都为正交的单位向量，向量积的长度也为单位长度。这将自动得出<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image470.gif"> 或<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image471.gif">。考虑特性 3 以及从<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image470.gif">底端观察从<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image467.gif">到<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image468.gif">的旋转为反时针方向的事实，我们得出<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image475.gif">。
　　同样的，<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image476.gif">。通过指定任意两个由基向量的线性组合形成的向量，并注意向量积的定义<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image477.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/Image478.gif"></TD></TR>
<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image479.gif"></TD></TR></TABLE>
　　进一步，考虑到相同的定义，由于向量自身形成的夹角为0以及<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image480.gif">。我们可以得出<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image481.gif">。代入已知的向量积，并结合因子<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image482.gif">和<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image470.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/Image484.gif"></TD></TR></TABLE>
　　习惯上将上述公式表示成矩阵行列式，因为公式和如何计算这个3×3行列式是一致的，这个行列式的第一行包括<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image482.gif">和<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image470.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/Image487.gif"></TD></TR>
<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image488.gif"></TD></TR></TABLE>
　　与向量积不同，两个向量的标量积为一个标量。定义这个标量为两个向量的长度和它们夹角的cos值的乘积：


<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/Image489.gif"></TD></TR></TABLE>
　　正如我们对向量积所做的一样，让我们考虑一下基向量的标量积。这一次将更加简单，由于<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image490.gif">，我们可以得出<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image491.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/Image492.gif"></TD></TR>
<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image493.gif"></TD></TR></TABLE>
　　由定义<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image494.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/Image495.gif"></TD></TR></TABLE>
　　我们经常用到的一个重要特性是，由于<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image496.gif">，两个正交的向量的标量积为0。如果给定一个位于平面内的点P，我们可以将属于平面的任何向量表示为<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image497.gif">，此处X是同一平面内的变化的点。如果又给了一个该平面的法向量<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image498.gif">，那么平面方程可以表示为两个向量标量积为0的等式。（参见图5.10）


<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/Image499.gif"></TD></TR></TABLE>
　　只有位于平面内的点X才会使上式为0。


<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/Image500.gif"> </TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图5.10 平面</B></FONT></TD></TR></TABLE>
　　在计算机图形学中，我们经常要寻找给定的多边形的平面方程。这时，我们并不是马上就有法向量。然而，我们可以找到属于平面的两个向量，法向量可以由这两个向量的向量积得到。
　　正如我们所见到的，考虑向量积和标量积可以使平面方程的表达变得简易。为了光线追踪方法的目的，我们需要找到射线和图元的交点。因此，让我们来考虑如何计算一条直线和一个平面的交叉点。
<B>
　　5.2.3 直线和平面的交叉点</B>
　　几何对象的等式掌握了在空间中的属于该对象的任意点。这样，解决包含描述多个几何图元公式的方程组就可以帮助我们找到系统中属于所有图元的点，即交点。
　　 假设由一条参数形式表示的直线<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image501.gif">和一个表示成<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image502.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/Image503.gif"></TD></TR>
<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image504.gif"></TD></TR></TABLE>
　　通过联立两个等式，我们发现参数t的表达式和直线上的点的表达式相一致，当然也属于该平面。交叉点的坐标可以通过进一步将参数t代入直线方程进行演算得到。

　　<B>5.2.4</B><B> 直线和多边形的交叉点</B>
　　直线和平面的交叉点的计算很重要，然而3D场景是由多边形组成，而多边形只是各自平面的一块。这样，即使我们可以定出平面上交叉点的位置，但如果该交叉点不在多边形边界内的话，也将是没有用处的。
　　一旦我们定位出交叉点，所有进一步的计算实质上是在平坦的多边形平面上进行的。即使是对于一个纯粹平坦的例子来说，确定一个点是否在一个任意多边形的边界内也是有困难的。通常的方法是使用所谓的垂线法（<I>plumb-line</I>）或奇数交叉（<I>odd intersection </I>rule）规则。该规则是Jordan曲线理论的直接结果，它认为任何简单的多边形将一个平面分为两个部分：多边形内部和其外部。这样，如果我们通过一个给定点画一条水平线，这条线将和多边形的几个边界相交。如果在给定点的任何一边有奇数个交叉点，则该点一定在多边形内，反之则在多边形外部。注意到0为偶数，这样当直线不与任何边界相交时，该点则归入第二类（参见图5.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/5.1/Image505.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图5.11 奇数交叉规则</B></FONT></TD></TR></TABLE>
　　既然该方法是用于整个平面，我们就需要关于该平面所有点的坐标，但是我们只有其三维坐标。当然，通过采用在5.1.4节中使用过的技术，我们有可能推演出该信息。在该节，我们已经找到两个空间中一些向量之间的映射，并使用它们的坐标推演出将一个空间映射到另一个空间的变换。在这个特别的情形下，我们可以构建平面的法向量并选择平面内两个正交的向量，其目的是寻求将这三个向量映射成通常的基向量的变换。进一步，当我们有了变换矩阵，把它应用到世界空间中的点上，就得到了坐标，其中的两个分量可被进一步用作平面内点的坐标。
　　应用该策略稍微有些昂贵。如果我们寻求一个便宜的解决方案，那么很明显，我们在求交叉点时可以采用这么一种方法：将所有的点投影到坐标系中的一个参考平面上。如果一个点在给定平面的多边形内部，那么它就在该平面任意投影中的多边形内部。参考平面具有如此吸引力是因为在其上的投影是最容易寻求的。这只涉及到舍弃点的三维坐标中之一的分量的问题。比如，点<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image506.gif">在<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image507.gif">平面的投影为<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image508.gif">。（参见图5.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/5.1/Image509.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图5.12 多边形在参考平面上的投影</B></FONT></TD></TR></TABLE>
　　使用该方法的一个小问题是：一个给定平面在某个投影上映射为一条直线不是不可能的。如果发生这种情况，所有进一步的计算都将受阻。因此，在我们选择使用哪一个投影之前，我们必须分析平面在空间的位置并选择三个投影的最大投影。做出此决定的信息暗含在平面的法向量中。如果法向量三维坐标的某个分量的绝对值最大，我们就可以选择与该坐标轴垂直的平面作为投影平面。
　　基于奇数交叉规则的方法涉及到寻求直线和多边形每条边界的交叉点，这相对来说也是很昂贵的。我们可以很容 易地推演出另一个技术 — 这里正是好好回忆一下裁剪的时候。然而该技术牺牲了通用性，限制为只考虑凸多边形。
　　凸多边形是一系列相连的线段。由于凸多边形的性质，通过每条边的直线使得所有的顶点在其一边。空间中在一条直线一侧所有的点定义了半平面（<I>half-plane</I>）。由此，多边形区域就是由每条边形成的半平面的交叉区域。（参见图5.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/5.1/Image510.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图5.13 被作为半平面交叉区域的多边形</B></FONT></TD></TR></TABLE>
　　如果我们能够决定某一点是否在恰当的半平面，我们就能通过检查所有的由每条边形成的半平面来决定某一点是否在多边形内。
　　应该注意到该算法与前面考虑过的算法相似，都涉及到分析每条边。然而，正如我们所见，寻求一个点是否属于一个半平面相对不太昂贵，所以单个步骤也要廉价一些。这种算法可以很容易地改进，也很容易求出采用二分搜索技术时要考虑的顶点数的对数。考虑图5.14中的多边形，通过使用图示的扇形分割，我们可以采用二分搜索来寻求点在哪一个区域，并如前面的算法一样来作进一步测试以决定点是否在合适的半平面内，半平面由边限制的部分确定。（参见图5.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/5.1/Image511.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图5.14 在扇形子域中使用二分搜索</B></FONT></TD></TR></TABLE>
　　如图5.14所示，我们首先找到多边形顶点列表的中间点，这样当我们将第一个顶点<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image512.gif">和中间点<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image513.gif">连接时，将有一半的顶点在直线的一侧而另一半在另一侧。通过检测该点关于直线的位置，我们可以放弃一半的区域，如此重复直到只剩下一个部分。然而必须注意大多数情况下处理的多边形只有几个顶点，而第二种算法的优势只有在多边形有大量的顶点时才能体现出来。鉴于此，第一种算法因为简单而常常受到欢迎。
　　在凹多边形包含点测试时可以采用一个稍微相似的细分策略。图5.15展示了一种可能的层状细分（slab-subdivision）。通过这种细分，使用合适的预计算的数据结构，我们可以在每个层内对边预排序，然后进一步采用二分搜索来定位出对包含测试必需的层，此后在层内用二分搜索来寻求给定点是否在多边形内或外。（参见图5.15）


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

<TR align=middle>
<TD colSpan=3><B><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image514.gif"></B></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图5.15 在层状细分中使用二分搜索</B></FONT></TD></TR></TABLE>
　　在所有的这些技术中，我们需要一种方法测出一点是否在某个半平面内。为了做到这一点，我们需要平面内一条直线的方程。我们已经得出三维空间直线的方程，当前的任务将更简单。习惯上为了方便将一条直线方程表示为<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image515.gif">，此处<I>A,B,C</I>是某个常量。为了推出该公式有两种等价的方法。我们已经见到了基于同向向量的直线方程的推演：


<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/Image516.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/Image517.gif"></TD></TR>
<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image518.gif"></TD></TR>
<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image519.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/Image516.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/Image520.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/Image521.gif"></TD></TR>
<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image522.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/Image523.gif"></TD></TR></TABLE>
　　如果两条向量之间的夹角小于90度，cos(x)为正，又由于长度恒为正，使得整个表达式为正。然而如果夹角大于90度，cos(x)为负，将使整个表达式为负。恰好为90度使得表达式值为0。这有如下的几何解释：直线方程对于其上任何点的值为0（90度），对于位于法向量方向的半平面的点值为正，余下的值为负。（参见图5.16）


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

<TR align=middle>
<TD colSpan=3><B><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/5.1/Image514.gif"></B></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图5.16 标量积的符号</B></FONT></TD></TR></TABLE>
　　这样，无论何时用其中之一算法执行多边形内含计算时，需要测试一点是否在某个半平面内，我们可以首先采用第一种推导中的公式计算必需的直线方程。既然推导是等价的，我们可以进一步利用在第二种情况中得到的性质，通过对该点求解直线方程推断点在直线的哪一边。
　　由此，对于基于多边形是由边形成的半平面的交叉点的事实的算法，对给定点，当所有的直线方程的值都为正，我们就断定该点在多边形内。