3D图形编程指南7 - 建模

<b>目 录
</b>　　6.1 <a href="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/6.htm#6.1" target="_blank" ><FONT color=#000000>线框模型</FONT></A>
　　6.2 <a href="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/6.htm#6.2" target="_blank" ><FONT color=#000000>多边形模型</FONT></A>
　　6.3 <a href="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/6.htm#6.3" target="_blank" ><FONT color=#000000>三次曲线和双三次曲面</FONT></A>
　　6.4 <a href="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/6.htm#6.4" target="_blank" ><FONT color=#000000>地形</FONT></A>
　　6.5 <a href="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/6.htm#6.5" target="_blank" ><FONT color=#000000>体素模型</FONT></A><B>
</B><FONT face=楷体_GB2312><FONT face=楷体_GB2312><FONT face=楷体_GB2312><B>
</B></FONT></FONT></FONT>
<HR align=center width="95%" noShade SIZE=1>
<B>
　　引言
</B>　　在前面的章节中，我们已经对三维计算机图形学的一些设备进行了讨论。使用一些算法和技术，使我们能够从不同角度和不同距离观察一个图元的图像。但是，我们想要展示的虚拟世界往往非常复杂，要由许多的图元才能组成。这样，我们就要了解模型问题，以便能够在3-D程序中表现复杂的虚拟物体。
　　选择用来表现三维模型的数据结构要考虑某些因素。这些因素包括创建和操作的便利性、精度、存储效率、对几何体进行渲染的可编程性以及其它标准。由于完全实现所有的标准是不现实的，因此我们经常被迫要牺牲一些标准来换取别的标准。有时也经常会有一些物体对某些要求会有所放松，从而使得对数据结构的选择变得十分明了。而有时又有一些物体对数据结构没有明显的选择。
例如我们在前面章节中暗示使用的一种建模方案。为光线投射（ray-casting）的目的，我们将一个球体描绘成一个数学等式。这种建模的方法非常适合于光线投射算法，因为它基本的操作 — 交点计算 — 可以通过求解球体与射线等式来得到。但是，使用从世界到屏幕渲染技术的程序不可能从这样的方法中获得什么，因为一个球体很难进行光栅化。这样，对于程序来说，用一些多边形来对球体进行模拟可能更加适用。尽管这种方法可能是一个符合国际化的选择，但它对于其他标准来说仍然是有缺陷的。用多边形来逼近一个球体的存储效率明显要比用解析方法表示球体低得多，并且随着我们所要求的精度的提高，所需的多边形数量也会大量增加。此外，在前一种方法中要改变球体的自然属性，例如半径等，是非常容易的，而对于后一种方法来说却十分复杂。
　　我们将会讨论一些用于交互式程序的不同的技术，从简单的用线框到更加复杂的用平面多边形或曲面片来表现实体。虽然这些技术都比较适合于渲染，但是对于由实际物体自动采样产生的模型的再现还是有一定缺陷的。对于这一问题，我们将在本章的最后部分对体素模型（voxel model）的介绍中予以考虑。

<B>6.1、线框模型</B>
　　线框模型用一系列关键顶点以及顶点间的关键连线来表现物体。在实际生活中，很少有物体能够用这种方法来进行描绘。尽管如此，它在计算机图形学中还是非常重要的。对这些模型采用从世界到屏幕渲染技术进行绘制可能是最容易的，因为它不用考虑复杂图元的光栅化或是隐面消除问题。当我们在编辑阶段仅仅需要一个复杂场景的近似轮廓时，我们可以很容易的用线框来对场景进行描绘，并表现在观察者面前。(参见图6.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/6.1/Image628.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图6.1 线框模型</B></FONT></TD></TR></TABLE>
　　在使用从屏幕到世界技术时，我们从这种表度方法中很难有所收获，因为这种算法的复杂性会是很高的。我们还将为屏幕的每一个像素投射一条射线。这样，计算射线与模型边的交点的计算量无论在概念上还是在数学精度水平上都还是很大的。从而，当观察者使用从屏幕到世界技术时，线框模型并不会有多大的好处。
　　如果使用从世界到屏幕的视处理方法，线框模型的边必须经过坐标变换、裁剪、投影以及光栅化等处理过程。这些边可以通过对两个端点的声明来进行描述。由于有些边会共用一些端点，并且处理管道的第一阶段是坐标变换，因此我们就有必要用一个数据结构来描述这些端点的共享情况。边的顶点可以分别进行放置，并且可以用两个参数来描述，而不必使用真实的坐标来进行存储。
　　从透视的角度来说，这种方法也是非常有用的。如果有些顶点的坐标改变了，我们不必检查每一个边来进行调整。

<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/6.1/Image629.gif"></B></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图6.2 线框模型的一个数据结构</B></FONT></TD></TR></TABLE>
　　这一模型的视处理过程包含坐标变换过程。然后，边必须经过裁剪处理，将一些端点去除掉，而有些边可能由一些新建的端点来描述。这样，从裁剪处理开始，我们就必须明确的使用坐标来描述边了。裁剪以及最后两个处理过程（投影和光栅化）对每一个边进行处理，最终产生出模型的完整图象。

<B>6.2、多边形模型</B>
　　在实际生活中，由许多实体模型是不适合用线框模型来进行描述的。这样，一种符合逻辑的用面来描述实体的模型就产生了。由于实际生活中的许多实体都包含由一些共面的多边形，并且对这种模型进行光栅化处理也是可行的，因此，我们就可以用一系列的多边形面片来表示物体。(见图6.3)


<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/6.1/Image630.gif"></B></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图6.3 一个多边形描述的模型</B></FONT></TD></TR></TABLE>
<B></B>　　从屏幕到世界和从世界到屏幕的渲染技术对于这种模型来说都是可以实现的。在前面的章节中，我们已经讨论过在考虑单个多边形时执行这两种渲染技术的方法。使用射线投射方法时，最重要的操作就是坐标变换和计算射线与模型多边形的交点。如果使用从世界到屏幕的投影，与讨论过的处理线框模型的过程一样，我们必须对顶点执行坐标变换，然后对所有的多边形执行后续的渲染管道操作，包括裁剪处理、投影变换和光栅化。
　　由于多边形也会有共享的顶点，并且只包括顶点设置的坐标变化的计算量非常大，所以我们通常选择一个数据结构来反映这种共享情况。(见图6.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/6.1/Image631.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图6.4 一个基于顶点的数据结构</B></FONT></TD></TR></TABLE>
　　在运行时，这个数据结构可能会进行一些修改或者是扩容来进行一些特殊的处理。例如，一个射线发生器可能象计算物体的边界盒以及多边形平面的表达式。
　　为了进行从世界到屏幕的视处理，我们对顶点设置进行坐标变换，然后对每一个多边形进行后续的渲染管道处理。由于在进行裁剪过程时，多边形描述可能会发生一些改变（一些新的顶点会被创建，老的会被删除）因此我们不能再使用共享顶点的形式。这样，在每一个多边形进入裁剪阶段之前，我们就需要用它的真实坐标来对它进行描述。
　　再来考虑一下我们要描述的物体，可以看到，物体的许多边都被两个多边形所共享。当进行裁剪处理时，我们就会对这些边进行两次处理。为了避免这种情况的发生，我们就要用它的边来对多边形进行描述而不是使用顶点来进行描述。(见图6.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/6.1/Image632.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图6.5 一个基于边的数据结构</B></FONT></TD></TR></TABLE>
　　当然，这种表示方法在渲染时还有很多要牵扯到的问题，并且它通常都使用基于隐面消除的扫描线方法，以及光栅处理。在这种方法中，对所有多边形的渲染处理将同时进行，而不是一次只对一个多边形进行处理。对于这种表示方法，射线投射方法没有明显的作用。

<B>6.3、三次曲线和双三次曲面</B>
　　我们在前面已经看到，在用多边形表示实体时有一定的问题。这种表示法的精度就是一个最大的问题。在实际生活中，有很多物体的表面都是弯曲的。要使用多边形面片来对曲面进行很好描述，就需要多边形的数量足够地多。 (见图6.6和图6.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/6.1/Image633.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图6.6 使用线段来逼近曲线时增加精度的方法</B></FONT></TD></TR></TABLE>
　　对大量的多边形来说，除了处理存储和处理过程十分复杂之外，对于建模阶段也不是一个十分适合的方法。由多边形构成的多面体的离散的点不利于对表面属性进行处理。表面上一个属性的改变，比如表面曲率改变，就要求对许多点的坐标进行修改。要提高精度，同时又不增加建模时的难度，还要减少多边形的数量，我们通常使用较简单的曲面片来对一些更复杂的曲面区域进行描述。在这一部分中，我们将讨论一些操作和存储简单曲面的方法。


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

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image634.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图6.7 分别用18、 50、 98和162个多边形来模拟球体</B></FONT></TD></TR></TABLE>
　　上面所说的方法实际上是对用平面多边形对曲面进行逼近方法的一种扩展。实际上，平面多边形也是曲面的一种特例，它的表达式的最高次数为1。
　　这样，我们经常用来对物体进行逼近的是三次多项式：


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

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image635.gif"></TD></TR></TABLE>
　　次数低于三的多项式称为二次多项式，我们有时也使用它，但是由于它只定义了一个灵活点，因此在逼近曲面时还是有一定的缺陷。另一方面， 次数高于3的多项式虽然更加灵活，但表达起来也更加复杂，并且缺少必要的稳定性，只要稍微改变一下参数可能就会产生很大的变化。
　　我们先来考虑一下平面参数曲线，它是讨论三维曲线和曲形表面片的基础。
　　参数三次曲线的表达式如下：


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

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image636.gif"></TD></TR></TABLE>
　　这种形式被称为参数（parametric）不是因为它直接给出了y和x的关系式(y=f(x) 或者f(x,y)=0)，而是因为它们都是一个第三变量的函数：参数t。对于一个给定的t，我们可以分别得到x和y。我们通常将这两个式子合并在一起：


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

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image637.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/6.1/Image638.gif"></TD></TR></TABLE>
　　这种形式并不是非常适用的，因为我们很难将系数<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image639.gif">与特定的曲线联系起来。
　　为了较好的处理曲线的属性，我们使用了几个不同的表达形式。这些形式对于曲线属性的控制各自不同。
　　Hermite形式基于对四个量的控制：两个声明曲线开始与结束的点<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image640.gif">，两个声明曲线在端点处切线的向量<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image641.gif">。(见图6.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/6.1/Image642.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图6.8 三次曲线</B></FONT></TD></TR></TABLE>
　　如图6.8所示，这些控制点对于声明曲线的形状是非常有效的。它们同样适合于曲线等式中系数的推导。我们来讨论一下一个可能的推导技巧。
　　我们可以在端点间通过一个参数t的函数进行内插来计算其它点。在端点间，t的变化范围为[<I>0,1</I>]，这样，在点<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image643.gif">处t等于0，在点<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image644.gif">处t等于1。这样，我们就找到了下面的表达式，在端点处该表达式为真：


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

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image645.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/6.1/Image646.gif"></TD></TR></TABLE>
　　这两个的等式对于推导系数A,B,C和D还不够。我们还要用剩下的向量控制来推导另外两个等式。向量<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image647.gif">声明了曲线在端点<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image648.gif">和<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image649.gif">处的切线。曲线在一个点的切线可以用这一点处的导数来计算：

<P align=center><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image650.gif"></P>　　点的切线几何意义如下所示：


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

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image651.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图6.9 曲线在某一点的切线</B></FONT></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/6.1/Image652.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/6.1/Image653.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/6.1/Image654.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/6.1/Image655.gif"></TD></TR></TABLE>
　　等式是以向量形式来写的，因此D就应该是<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image656.gif">，同样，<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image657.gif">就是<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image658.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/6.1/Image659.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/6.1/Image660.gif"></TD></TR></TABLE>
　　如果我们将A,B,C和D的表达式代入上式：


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

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image661.gif"></TD></TR></TABLE>
　　这个4x4的矩阵通常称为基矩阵（basis matrix）。当前描述的是Hermite形式的基矩阵。其它的曲线形式都有各自不同的基矩阵。这些矩阵的目的是要指明我们使用了哪些控制点。包含了<IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image662.gif">控制点的向量通常被称作一个几何向量或是几何矩阵，并且它对曲线的特定情形指定了其属性。
　　　在实际的程序中，直接指定正切向量并不太好。这时，我们可以用另外的形式来代替它，在这种形式中，正切向量并不直接指定。这种形式的发明人是法国的数学家<I>P. Bézier</I>，这种形式有四个控制点：


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

<TR align=middle>
<TD colSpan=3><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image663.gif"></TD></TR>
<TR align=middle>
<TD colSpan=3><FONT color=#cccccc><B>图6.10 Bézier曲线的控制点</B></FONT></TD></TR></TABLE>
　　Bézier控制与Hermite控制有下面的关系：


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

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image664.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/6.1/Image665.gif"></TD></TR></TABLE>
　　为了得到Bézier形式的表达式，我们将上面的关系式带入Hermite形式的公式中：


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

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image666.gif"></TD></TR></TABLE>
　　矩阵相乘之后，得到下面Bézier形式的等式：


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

<TR align=middle>
<TD><IMG src="mk:@MSITStore:E:\3D图形编程指南.chm::/3D图形编程指南/image/6.1/Image667.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/6.1/Image668.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/6.1/Image669.gif"></TD></TR></TABLE>