等值线等值面的生成课件.ppt

1、第第3 3章章 二维标量场等值线的生成二维标量场等值线的生成 二维标量场可看成是定义于某一个面上的二维标量函二维标量场可看成是定义于某一个面上的二维标量函数数F=F(x,y)，所谓等值线是由所有点，所谓等值线是由所有点(xi,yi)构成，其中构成，其中F(xi,yi)=Ft（为一给定值），将这些点按一定顺序连接起（为一给定值），将这些点按一定顺序连接起来就组成了函数值为来就组成了函数值为Ft的等值线。对于二维标量场，其数的等值线。对于二维标量场，其数据往往是分布在规则网格点上的，常用的等值线抽取方法据往往是分布在规则网格点上的，常用的等值线抽取方法有网格序列法和单元剖分法。有网格序列法和单元剖

2、分法。网格序列法网格序列法 网格序列法网格序列法(grid sequence)的基本思想是按网格单元的排列次序，的基本思想是按网格单元的排列次序，逐个处理每一单元，寻找每一单元内相应的等值线段，在处理完逐个处理每一单元，寻找每一单元内相应的等值线段，在处理完所有单元后，就自然生成了该网格中的等值线分布。所有单元后，就自然生成了该网格中的等值线分布。规则网格数据等值线的生成规则网格数据等值线的生成 设一规则网格数据如图所示，网格线是相互正交的，每一网格单设一规则网格数据如图所示，网格线是相互正交的，每一网格单元是一矩形，其中四个顶点分别为元是一矩形，其中四个顶点分别为(x0,y0)、(x0,y1

3、)、(x1,y0)、(x1,y1)，对应的值分别为，对应的值分别为F00、F01、F10、F11。要在该单元内生成值。要在该单元内生成值为为Ft的等值线，其主要计算步骤为：的等值线，其主要计算步骤为：逐个计算每一网格单元与等值线的交点；逐个计算每一网格单元与等值线的交点；连接该单元内等值线的交点，生成在该单元中的等值线线段；连接该单元内等值线的交点，生成在该单元中的等值线线段；由一系列单元内的等值线线段构成该网格中的等值线。由一系列单元内的等值线线段构成该网格中的等值线。网格单元与等值线的交点计算主要是求各单元的边线与等值线的网格单元与等值线的交点计算主要是求各单元的边线与等值线的交点。假设函

4、数在单元内呈线性变化，可以采用顶点判定，边上交点。假设函数在单元内呈线性变化，可以采用顶点判定，边上插值的方法计算交点，具体步骤为：插值的方法计算交点，具体步骤为：网格序列法网格序列法 (1)将网格点分为将网格点分为“IN”和和“OUT”两种状态，表示该点在等值线两种状态，表示该点在等值线内，或在等值线外。如果内，或在等值线外。如果FijFt，则顶点，则顶点(xi,yj)为为“IN”，记为，记为“”；如果；如果FijFt，则顶点，则顶点(xi,yj)为为“OUT”，记为，记为“”。(2)如果单元四个顶点全为如果单元四个顶点全为“”，或全为，或全为“”，则网格单元，则网格单元与值为与值为Ft的等

5、值线无交点，否则的等值线无交点，否则(3)对于两个顶点分别为对于两个顶点分别为“”、“”的单元边，可用线性插的单元边，可用线性插值计算等值线在这条边上的交点。值计算等值线在这条边上的交点。如图所示，如图所示，(x0,y0)为为“”，(x0,y1)为为“”，则交点为，则交点为00010010100100010000)()()(FFFFyFFyyyFFFFyyxxttttt网格序列法网格序列法 在每一单元内计算出等值线与该网格单元边的交点后，利用这些在每一单元内计算出等值线与该网格单元边的交点后，利用这些交点，就能构成在该单元内的等值线段。为了正确地连接交点生交点，就能构成在该单元内的等值线段。为

6、了正确地连接交点生成等值线段，必须规定等值线的方向。等值线的方向定义如下：成等值线段，必须规定等值线的方向。等值线的方向定义如下：沿等值线走，大于等值线值的点在等值线的左边，小于等值线值沿等值线走，大于等值线值的点在等值线的左边，小于等值线值的点在等值线的右边。也就是的点在等值线的右边。也就是“”点在等值线的右边，点在等值线的右边，“”点在等值线的左边。在规定了等值线的走向后，等值线的连接对点在等值线的左边。在规定了等值线的走向后，等值线的连接对于矩形单元可分如下四种情况进行：于矩形单元可分如下四种情况进行：(1)顶点全为顶点全为“”，或全为，或全为“”，无等值线段；，无等值线段；(2)有一个

7、顶点为有一个顶点为“”或或“”，共可求出两个交点，有一条，共可求出两个交点，有一条等值线段，如图等值线段，如图3。网格序列法网格序列法 (3)有两个有两个“”，两个，两个“”顶点的情况，根据顶点的分布又顶点的情况，根据顶点的分布又可分成下面两种情况：可分成下面两种情况：有两个交点，即两个有两个交点，即两个“”或两个或两个“”的顶点位于同一条的顶点位于同一条单元边上，等值线段的连接如图单元边上，等值线段的连接如图4a所示。所示。有有4个交点，即个交点，即“”、“”顶点的分布相互交叉，这时的顶点的分布相互交叉，这时的连接在规定了函数的走向后，可确定连接在规定了函数的走向后，可确定P，R为入点，为入

8、点，S，Q为出点，为出点，连接情况如图连接情况如图4b所示。所示。在上述在上述的情况下，如果不规定等值线的走向，其实存在两种连的情况下，如果不规定等值线的走向，其实存在两种连接方式，见图接方式，见图5。在实际情况中，这两种方式都是可能的，这种。在实际情况中，这两种方式都是可能的，这种二义性的主要原因是在该单元内存在一马鞍点。二义性的主要原因是在该单元内存在一马鞍点。网格序列法网格序列法 如何从中选择一种正确的连接方式呢？这可从单元内的双线性插如何从中选择一种正确的连接方式呢？这可从单元内的双线性插值函数分析入手。由于在单元边上采用了线性插值，由此单元面值函数分析入手。由于在单元边上采用了线性插

9、值，由此单元面上函数值的变化是双线性的，上函数值的变化是双线性的，即等值线在单元内不是直线段而是双曲线。二义性连接可通过求即等值线在单元内不是直线段而是双曲线。二义性连接可通过求该双曲线两条渐近线交点处的函数值来判定，这是因为渐近线的该双曲线两条渐近线交点处的函数值来判定，这是因为渐近线的交点总是与其中一对顶点落入同一区域内，如渐近线交点为交点总是与其中一对顶点落入同一区域内，如渐近线交点为“”，则取图，则取图5a的连接方式；如为的连接方式；如为“”，则取图，则取图5b的连接方的连接方式。即在图式。即在图5a中，表示单元中部为中，表示单元中部为“”，在图，在图5b中，表示单元中，表示单元中部为

10、中部为“”。在实际计算中，为简化计算，往往采用单元对角。在实际计算中，为简化计算，往往采用单元对角线交点代替渐近线交点的计算。线交点代替渐近线交点的计算。xyayaxaayxF3210),(单元剖分法单元剖分法 在网格序列法中，提出了解决矩形单元内等值线的生成在网格序列法中，提出了解决矩形单元内等值线的生成算法，其中马鞍点二义性的解决是算法的一个主要复杂算法，其中马鞍点二义性的解决是算法的一个主要复杂点，除此之外人们还提出了单元剖分法，该方法与矩形点，除此之外人们还提出了单元剖分法，该方法与矩形单元法相比，其主要特点是采用三角片简化单元内等值单元法相比，其主要特点是采用三角片简化单元内等值线的

11、抽取，无需再进行马鞍点的判定，但处理的单元数线的抽取，无需再进行马鞍点的判定，但处理的单元数是原来的四倍。是原来的四倍。算法的基本思想是利用对角线将矩形单元分成四个三角算法的基本思想是利用对角线将矩形单元分成四个三角形单元，见图形单元，见图6，求出中心点的函数值，等值线的抽取，求出中心点的函数值，等值线的抽取直接在每个三角片中进行。由于每一个三角片至多只包直接在每个三角片中进行。由于每一个三角片至多只包含一条等值线，因而在由三角片的三个点决定的平面内，含一条等值线，因而在由三角片的三个点决定的平面内，可直接用直线段连接等值线。可直接用直线段连接等值线。单元剖分法单元剖分法 中心点函数值中心点函

12、数值Fmid的计算可采用两种方式：的计算可采用两种方式：如有显式函数如有显式函数F(x,y)，则，则Fmid=F(xmid,ymid)；如只有四个点的函数值，无法求显式函数形式，则可用如只有四个点的函数值，无法求显式函数形式，则可用四点的平均值代替四点的平均值代替Fmid。图图7列出了几种可能的情况，可以看出，通过利用矩形列出了几种可能的情况，可以看出，通过利用矩形单元中点的函数值，等值线的精度提高了，其抽取过程单元中点的函数值，等值线的精度提高了，其抽取过程也相对简单些。也相对简单些。第第4 4章章 等值面的生成等值面的生成 所谓等值面是指空间中的一个曲面，在该曲面上函数所谓等值面是指空间中

13、的一个曲面，在该曲面上函数F(x,y,z)的值等于某一给定值的值等于某一给定值Ft，即等值面是由所有点，即等值面是由所有点 SFt=(x,y,z)：F(x,y,z)=Ft组成的一个曲面。组成的一个曲面。等值面技术在可视化中应用很广，许多标量场的可视等值面技术在可视化中应用很广，许多标量场的可视化问题都可归纳为等值面的抽取和绘制，如各种等势面、化问题都可归纳为等值面的抽取和绘制，如各种等势面、等位面、等压面、等温面等。等值面技术除生成等值面的等位面、等压面、等温面等。等值面技术除生成等值面的几何表示外，还包括显示技术，如要考虑合适的光照模型、几何表示外，还包括显示技术，如要考虑合适的光照模型、解

14、决等值面的相互遮挡等。等值面的生成和显示也是可视解决等值面的相互遮挡等。等值面的生成和显示也是可视化研究中的一个重要领域。化研究中的一个重要领域。一一 Cuberille方法方法(立方体方法立方体方法)Cuberrille等值面方法又称等值面方法又称Opaque Cube算法，最初由算法，最初由Herman等等人提出，后来又多次改进。算法主要分为两个步骤。人提出，后来又多次改进。算法主要分为两个步骤。(1)确定边界单元确定边界单元 对于规则网格数据，其网格单元可看成是正六面体单元，整个三对于规则网格数据，其网格单元可看成是正六面体单元，整个三维数据就是由这种正六面体组成的，这种组成三维图象的基

15、本正维数据就是由这种正六面体组成的，这种组成三维图象的基本正六面体单元称为体元。对于给定的阈值六面体单元称为体元。对于给定的阈值Ft，遍历体数据中的各个，遍历体数据中的各个单元，将组成体元单元，将组成体元8个顶点上的值与个顶点上的值与Ft进行比较，找出顶点值跨进行比较，找出顶点值跨越越Ft的所有体元，即体元中有的顶点值大于阈值，有的顶点值小的所有体元，即体元中有的顶点值大于阈值，有的顶点值小于阈值，因此体元内包含等值面片，这就是边界单元。于阈值，因此体元内包含等值面片，这就是边界单元。(2)绘制各边界单元的绘制各边界单元的6个多边形面，即将等值面看成是由各单元个多边形面，即将等值面看成是由各单

16、元的六个外表面拼合而成。的六个外表面拼合而成。Cuberille方法方法(立方体方法立方体方法)每个单元均为一正六面体，包括每个单元均为一正六面体，包括6个多边形面。对组成所有边界个多边形面。对组成所有边界体元的多边形面进行绘制，即可产生最终的图象结果。在绘制多体元的多边形面进行绘制，即可产生最终的图象结果。在绘制多边形过程中应采用合适的光照模型和消隐技术。边形过程中应采用合适的光照模型和消隐技术。如果在具有硬件深度缓存如果在具有硬件深度缓存(Z-buffer)功能的计算机上运行立方体功能的计算机上运行立方体方法，可以将这组多边形不分次序地提交给硬件，由硬件完成消方法，可以将这组多边形不分次序

17、地提交给硬件，由硬件完成消除隐藏面的任务。如果以软件方式执行立方体方法，在算法中必除隐藏面的任务。如果以软件方式执行立方体方法，在算法中必须考虑多边形的遮挡问题。一个有效的方法是把遍历体元集合与须考虑多边形的遮挡问题。一个有效的方法是把遍历体元集合与显示两个步骤合二为一，遍历体元集合时采用从后至前的次序。显示两个步骤合二为一，遍历体元集合时采用从后至前的次序。发现一个边界体元，就立刻显示它的发现一个边界体元，就立刻显示它的6个面。后显示到屏幕上去个面。后显示到屏幕上去的多边形将覆盖先显示的多边形，这样就达到了消除隐藏面的目的多边形将覆盖先显示的多边形，这样就达到了消除隐藏面的目的，这就是画家算

18、法的思想。的，这就是画家算法的思想。Cuberille方法方法(立方体方法立方体方法)Cuberrille算法的主要优点是简单易行，其主要缺点是算法的主要优点是简单易行，其主要缺点是出现严重的走样，显示的图象给人一种出现严重的走样，显示的图象给人一种“块状的感觉块状的感觉”，尤其在物体边界处锯齿形走样特别明显，而且画面较粗尤其在物体边界处锯齿形走样特别明显，而且画面较粗糙，不能很好地显示对象的细节。糙，不能很好地显示对象的细节。立方体法的另一个缺点是面的重叠冗余问题。两个相邻立方体法的另一个缺点是面的重叠冗余问题。两个相邻边界体元的公共面重复出现，实际上它们都不会出现在边界体元的公共面重复出现

19、，实际上它们都不会出现在显示画面上，因为无论从哪个角度进行观察，它们都会显示画面上，因为无论从哪个角度进行观察，它们都会被这两个体元的其它面遮挡。改进的立方体法删除了边被这两个体元的其它面遮挡。改进的立方体法删除了边界体元之间的公共面，减少了显示过程需要处理的多边界体元之间的公共面，减少了显示过程需要处理的多边形的数量。形的数量。二二 Marching Cubes(MC)方法方法 Marching Cubes（移动立方体）方法是由（移动立方体）方法是由W.E.Lorenson和和H.E.Cline在在1987年提出来的。由于这一方法原理简单，易于实年提出来的。由于这一方法原理简单，易于实现，目

20、前已经得到了较为广泛的应用，成为三维数据等值面生成现，目前已经得到了较为广泛的应用，成为三维数据等值面生成的经典算法，的经典算法，Marching Cubes算法又简称为算法又简称为MC算法。算法。1MC方法的基本原理方法的基本原理 在在Marching Cubes方法中，假定原始数据是离散的三维空间规则方法中，假定原始数据是离散的三维空间规则数据，一个体元定义为由相邻层上的数据，一个体元定义为由相邻层上的8个顶点组成的一个长方体。个顶点组成的一个长方体。为了在三维数据中构造等值面，应先给定所求等值面的值，该方为了在三维数据中构造等值面，应先给定所求等值面的值，该方法的基本原理是逐个处理所有的

21、体元，将体元各顶点处的值与给法的基本原理是逐个处理所有的体元，将体元各顶点处的值与给定的阈值进行比较，首先找出与等值面相交的体元，然后通过插定的阈值进行比较，首先找出与等值面相交的体元，然后通过插值求等值面与体元棱边的交点，并将各交点连成三角形来构成等值求等值面与体元棱边的交点，并将各交点连成三角形来构成等值面片，所有体元中的三角形集合就构成了等值面。由于这一方值面片，所有体元中的三角形集合就构成了等值面。由于这一方法是逐个处理所有的体元，因此被称为法是逐个处理所有的体元，因此被称为Marching Cubes方法。方法。MC方法的主要步骤如下：方法的主要步骤如下：Marching Cubes

22、(MC)方法方法 (1)确定包含等值面的体元及对应的等值面片模式确定包含等值面的体元及对应的等值面片模式 一个体元由一个体元由8个数据点构成，这个数据点构成，这8个数据点分别位于该体元的个数据点分别位于该体元的8个个顶点上。顶点上。首先对体元的首先对体元的8个顶点进行分类，判定是位于等值面之外，还是个顶点进行分类，判定是位于等值面之外，还是位于等值面之内。再根据位于等值面之内。再根据8个顶点的状态，确定等值面的模式。个顶点的状态，确定等值面的模式。设等值面的值为设等值面的值为Ft，顶点分类规则为：，顶点分类规则为：若某顶点的值若某顶点的值Ft，则定义该顶点位于等值面之外，记为，则定义该顶点位于

23、等值面之外，记为“0”。若某顶点的值若某顶点的值Ft，则定义该顶点位于等值面之内，记为，则定义该顶点位于等值面之内，记为“1”。如果某体元一条边的一个顶点在等值面之内，而另一个顶点在等如果某体元一条边的一个顶点在等值面之内，而另一个顶点在等值面之外，那么，该边必然与等值面相交。根据这一原理就可以值面之外，那么，该边必然与等值面相交。根据这一原理就可以判断所求等值面将与哪些体元相交，或者说将穿过哪些体元。判断所求等值面将与哪些体元相交，或者说将穿过哪些体元。Marching Cubes(MC)方法方法 由于每个体元有由于每个体元有8个顶点，每个顶点又有个顶点，每个顶点又有0、1两种状态，因此每两

24、种状态，因此每个体元按其个体元按其8个顶点的个顶点的0、1分布而言，共有分布而言，共有28=256种不同的状态。种不同的状态。尽管判断等值面将与哪些体元相交在原理上很容易理解，但是要尽管判断等值面将与哪些体元相交在原理上很容易理解，但是要根据这根据这256种不同的情况求出每个体元中的等值面却是很繁琐的，种不同的情况求出每个体元中的等值面却是很繁琐的，而且也容易出错。而且也容易出错。可以利用两种不同的对称性将可以利用两种不同的对称性将256种不同的情况简化为种不同的情况简化为15种。种。互补对称性互补对称性：如果将一个体元的顶点状态颠倒，即：如果将一个体元的顶点状态颠倒，即“0”变成变成“1”，

25、“1”变成变成“0”，则等值面与体元中，则等值面与体元中8个顶点之间的拓扑关个顶点之间的拓扑关系将不会改变，该体元与等值面的相交情况与原来一致，即新生系将不会改变，该体元与等值面的相交情况与原来一致，即新生成的等值面与原等值面是相同的。也就是说，大于等值面的点与成的等值面与原等值面是相同的。也就是说，大于等值面的点与小于等值面的点是可以相互替换的，因此，只要考虑小于等值面的点是可以相互替换的，因此，只要考虑4个以下个以下（含（含4个）的顶点值大于个）的顶点值大于Ft就够了。根据这种互补对称性，可将就够了。根据这种互补对称性，可将体元的模式由体元的模式由256种减少为种减少为128种。种。Mar

26、ching Cubes(MC)方法方法 旋转对称性旋转对称性：如果某一模式的体元经过旋转后与另一模式的：如果某一模式的体元经过旋转后与另一模式的体元一致，即顶点位置及其状态值相同，那么这两种模式的体元体元一致，即顶点位置及其状态值相同，那么这两种模式的体元可以合并为一种。根据这种旋转对称性，体元模式可以最终归纳可以合并为一种。根据这种旋转对称性，体元模式可以最终归纳为为15种，见图种，见图2。其中第。其中第0种情况表示所有种情况表示所有8个顶点的值均大于个顶点的值均大于（或小于）（或小于）Ft，因而该体元与等值面不相交。第一种情况表示有，因而该体元与等值面不相交。第一种情况表示有一个顶点的函数

27、值大于（或小于）一个顶点的函数值大于（或小于）Ft，其余，其余7个顶点均与此相反，个顶点均与此相反，因而该体元内的等值面将是一个三角面片。在考虑了上面两种对因而该体元内的等值面将是一个三角面片。在考虑了上面两种对称性后，这一种情况实际上代表了称性后，这一种情况实际上代表了16种情况。如此类推，图种情况。如此类推，图2中中的的15种模式反映了一个体元中种模式反映了一个体元中8个顶点可能存在的全部个顶点可能存在的全部256种状态。种状态。在实现时，对一个体元可按照它的在实现时，对一个体元可按照它的8个顶点的状态构造一个一字个顶点的状态构造一个一字节（节（8位）的状态表，如图位）的状态表，如图3所示

28、，其中的每一位表示该体元中一所示，其中的每一位表示该体元中一个顶点的个顶点的0或或1状态，根据这个状态表就可判断出当前体元属于哪状态，根据这个状态表就可判断出当前体元属于哪一种模式、等值面将与哪一条边相交以及体元内三角面片的连接一种模式、等值面将与哪一条边相交以及体元内三角面片的连接方式。方式。Marching Cubes(MC)方法方法 (2)计算等值面与体元边界的交点，并连接成三角形计算等值面与体元边界的交点，并连接成三角形 当三维离散数据的密度较高，即每个体元很小时，可以假定函数当三维离散数据的密度较高，即每个体元很小时，可以假定函数值沿体元边界呈线性变化。因此，等值面与体元边界的交点可

29、以值沿体元边界呈线性变化。因此，等值面与体元边界的交点可以通过该边两端点函数值的线性插值求出，公式为：通过该边两端点函数值的线性插值求出，公式为：求出了等值面与体元边界的交点以后，就可以按对应的模式将这求出了等值面与体元边界的交点以后，就可以按对应的模式将这些交点连接成三角形，构成该单元中的等值面片。些交点连接成三角形，构成该单元中的等值面片。)/()(,1,kjikjikjitFFFFiXMarching Cubes(MC)方法方法 (3)计算等值面的法向计算等值面的法向 为了绘制等值面的真实感图象，还必须给出构成等值面的各三角为了绘制等值面的真实感图象，还必须给出构成等值面的各三角面片的法

30、向。对于等值面上的每一点，沿该面切线方向的梯度分面片的法向。对于等值面上的每一点，沿该面切线方向的梯度分量应该是零，因此该点的梯度矢量的方向就代表了等值面的法向。量应该是零，因此该点的梯度矢量的方向就代表了等值面的法向。MC方法就是利用这一原理来计算三角面片的法向。即方法就是利用这一原理来计算三角面片的法向。即 对于三维规则网格数据，可以直接采用中心差分计算体元各顶点对于三维规则网格数据，可以直接采用中心差分计算体元各顶点处的梯度，公式为：处的梯度，公式为：),(),(zyxfzyxgzzyxfzyxfgyzyxfzyxfgxzyxfzyxfgkjikjizkjikjiykjikjix2/),

31、(),(2/),(),(2/),(),(111111 三角形顶点处的法向量可由体元边界两端点处的梯度再通过线性三角形顶点处的法向量可由体元边界两端点处的梯度再通过线性插值求得。在实际绘制等值面时，为了消除各三角面片之间明暗插值求得。在实际绘制等值面时，为了消除各三角面片之间明暗的不连续变化，只要给出三角面片各顶点处的法向并采用哥罗得的不连续变化，只要给出三角面片各顶点处的法向并采用哥罗得(Gouraud)模型绘制各个三角面片即可。模型绘制各个三角面片即可。在计算机图形学中，光滑的曲面常用多边形来逼近，这是因为处在计算机图形学中，光滑的曲面常用多边形来逼近，这是因为处理平面比处理曲面容易得多。例

32、如，为了表示一个磨光的立方体理平面比处理曲面容易得多。例如，为了表示一个磨光的立方体的顶角，可使用的顶角，可使用7个平面片来近似。但是，若单纯使用平面来绘个平面片来近似。但是，若单纯使用平面来绘制这种近似表面，生成的图形将失去原有曲面的光滑性，而呈现制这种近似表面，生成的图形将失去原有曲面的光滑性，而呈现多面体状。这是由于平面上所有点的法向相同，不同平面块之间多面体状。这是由于平面上所有点的法向相同，不同平面块之间存在不连续的法向量变化，从而引起不连续的光亮度跳跃。存在不连续的法向量变化，从而引起不连续的光亮度跳跃。如何能以较少的计算量来解决上述问题呢如何能以较少的计算量来解决上述问题呢?最简

33、单的方法就是最简单的方法就是Gouraud明暗处理技术。明暗处理技术。Gouraud明暗处理的思想是对离散的光明暗处理的思想是对离散的光亮度作双线性插值以获得连续的光亮度函数。具体做法是：先计亮度作双线性插值以获得连续的光亮度函数。具体做法是：先计算出多边形顶点处的光亮度值，把它们作为曲面光亮度的采样点，算出多边形顶点处的光亮度值，把它们作为曲面光亮度的采样点，然后根据多边形顶点处的光亮度值进行插值求多边形内任一点的然后根据多边形顶点处的光亮度值进行插值求多边形内任一点的光亮度。光亮度。若采用扫描线绘制算法，则可沿当前扫描线进行双线性插值，这若采用扫描线绘制算法，则可沿当前扫描线进行双线性插值

34、，这是一种简便易行的插值方法。即先用多边形顶点的光亮度值由线是一种简便易行的插值方法。即先用多边形顶点的光亮度值由线性插值求出当前扫描线与多边形交点处的光亮度，然后根据交点性插值求出当前扫描线与多边形交点处的光亮度，然后根据交点的光亮度值再通过线性插值求出扫描线上位于多边形内每一象素的光亮度值再通过线性插值求出扫描线上位于多边形内每一象素点的光亮度值。图点的光亮度值。图4(a)显示一扫描线与多边形相交，交点为显示一扫描线与多边形相交，交点为a点和点和b点，点，p是扫描线上位于多边形内的任一点，多边形三个顶点的光是扫描线上位于多边形内的任一点，多边形三个顶点的光亮度分别为亮度分别为I1，I2和和

35、I3。取。取a点的光亮度点的光亮度Ia为为I1和和I2的线性插值，的线性插值，b点的光亮度点的光亮度Ib为为I1和和I3的线性插值，的线性插值，p点的光亮度则为点的光亮度则为Ia和和Ib的线性的线性插值，即：插值，即：其中其中u,v,t称为插值参数称为插值参数(相当于以端点为原点归一化后的长度坐相当于以端点为原点归一化后的长度坐标标)。,)1(,)1(,)1(3121bapbaIttIIIvvIIIuuIIabpbtVVbVvVVaVu/313212 采用采用Gouraud明暗处理不但可以克服用多边形表示曲面时光亮度明暗处理不但可以克服用多边形表示曲面时光亮度的不连续现象，而且计算量也很小。事

36、实上，由于线性插值可使的不连续现象，而且计算量也很小。事实上，由于线性插值可使用增量法进行计算，其运算量仅涉及一次加法运算。如在上例中，用增量法进行计算，其运算量仅涉及一次加法运算。如在上例中，可沿扫描线从左至右的顺序计算可沿扫描线从左至右的顺序计算AB区段上所有象素的光亮度。区段上所有象素的光亮度。设设Ia和和Ib已经确定，已经确定，p1和和p2点是相邻两象素的坐标，点是相邻两象素的坐标，a、b两点的插两点的插值参数之差为值参数之差为 t，那么，不难发现，那么，不难发现p2点光亮度点光亮度Ip2和和p1点光亮度点光亮度Ip1之间有下列关系：之间有下列关系：由于由于 I在同一扫描线上为常数，因

37、此计算一相邻象素的光亮度仅在同一扫描线上为常数，因此计算一相邻象素的光亮度仅需一次加法运算。这种增量方式的光亮度计算使需一次加法运算。这种增量方式的光亮度计算使Gouraud明暗处明暗处理广泛用于实时图形生成。理广泛用于实时图形生成。在在Gouraud明暗处理中，计算多边形顶点的光亮度可采用明暗处理中，计算多边形顶点的光亮度可采用Phong光照模型。光照模型。IItIIIIpbapp112/)(aKIKIKIIsnssddaacoscos Marching Cubes(MC)方法方法 (4)用用MC方法求等值面的算法流程方法求等值面的算法流程 将三维离散规则数据分层读入内存；将三维离散规则数据

38、分层读入内存；扫描其中两层数据，逐个构造这两层之间的体元，每个体元扫描其中两层数据，逐个构造这两层之间的体元，每个体元中的中的8个顶点取自相邻的两层；个顶点取自相邻的两层；将体元各个顶点的值与给定的等值面值将体元各个顶点的值与给定的等值面值Ft进行比较，根据比较进行比较，根据比较的结果进行分类，构造该体元的状态表；的结果进行分类，构造该体元的状态表；根据状态表，查得与该状态值对应的等值面分布模式，确定根据状态表，查得与该状态值对应的等值面分布模式，确定将与等值面相交的体元边界；将与等值面相交的体元边界；通过线性插值，计算体元边界与等值面的交点坐标，按对应通过线性插值，计算体元边界与等值面的交点

39、坐标，按对应的模式将这些交点连接成三角形，构成该单元中的等值面片；的模式将这些交点连接成三角形，构成该单元中的等值面片；利用中心差分方法，求出体元各顶点处的梯度，再次通过线利用中心差分方法，求出体元各顶点处的梯度，再次通过线性插值方法，求出三角形各顶点处的法向；性插值方法，求出三角形各顶点处的法向；根据各三角面片各顶点的坐标值及法向量绘制等值面图象。根据各三角面片各顶点的坐标值及法向量绘制等值面图象。Marching Cubes(MC)方法方法 2MC方法的加速算法方法的加速算法 Marching Cube方法是逐个单元地检测是否存在等值面，还要计方法是逐个单元地检测是否存在等值面，还要计算等

40、值面与体元边界的交点，再由标准的连接模式将各个交点连算等值面与体元边界的交点，再由标准的连接模式将各个交点连接成等值面片。事实上，据研究，真正与等值面相交的体元占总接成等值面片。事实上，据研究，真正与等值面相交的体元占总数据量很小的一部分（至多数据量很小的一部分（至多10%左右），计算过程中左右），计算过程中30-70%的的时间用在了空体元的检测上，从加快时间用在了空体元的检测上，从加快Marching Cube方法的角度方法的角度出发，有必要研究一种快速有效的空间数据的遍历方法和相应的出发，有必要研究一种快速有效的空间数据的遍历方法和相应的数据表达形式，以加速对空体元的检测和排除。另一方面，

41、对于数据表达形式，以加速对空体元的检测和排除。另一方面，对于一条与等值面相交的体元的边，它同时被四个单元共用，这表明一条与等值面相交的体元的边，它同时被四个单元共用，这表明在这四个单元内求等值面时都要用到这个交点，保存该交点的位在这四个单元内求等值面时都要用到这个交点，保存该交点的位置及法向量对于加速算法具有重要意义。置及法向量对于加速算法具有重要意义。对于规则网格数据，其体元是一个六面体单元，若采用空间八叉对于规则网格数据，其体元是一个六面体单元，若采用空间八叉树来表示这种体数据，则可以加快运算速度。树来表示这种体数据，则可以加快运算速度。Marching Cube方法的另一个重要问题是抽取

42、的等值面三角片数方法的另一个重要问题是抽取的等值面三角片数量巨大，有时一个体元可以生成多达量巨大，有时一个体元可以生成多达12个三角片，当三维数据的个三角片，当三维数据的数据量很大时，三角片的数量也非常大。这给等值面的绘制和交数据量很大时，三角片的数量也非常大。这给等值面的绘制和交互操作带来很大困难。互操作带来很大困难。Schroeder提出了在不影响图形质量的情提出了在不影响图形质量的情况下，通过对原等值面三角片网重排结点，合并简化，生成最优况下，通过对原等值面三角片网重排结点，合并简化，生成最优化意义下的化意义下的Delaunay三角化网，可以有效加快图形的实时显示，三角化网，可以有效加快

43、图形的实时显示，这对于这对于Marching Cube方法的实用是非常有意义的。方法的实用是非常有意义的。Marching Cubes(MC)方法方法 3MC方法存在的问题方法存在的问题(1)MC方法构造的三角面片是三维等值面的近似表示方法构造的三角面片是三维等值面的近似表示 首先，在首先，在MC方法中，等值面与体元边界的交点是基于函数值在方法中，等值面与体元边界的交点是基于函数值在体元边界上呈线性变化这一假设而求出的。当数据密度高、体元体元边界上呈线性变化这一假设而求出的。当数据密度高、体元很小时，这一假设接近于实际情况。但是，在稀疏数据中，体元很小时，这一假设接近于实际情况。但是，在稀疏数

44、据中，体元较大，如果仍然认为函数值在体元边界上呈线性变化，将会产生较大，如果仍然认为函数值在体元边界上呈线性变化，将会产生较大误差。这时，需要根据不同的具体情况对函数值沿体元边界较大误差。这时，需要根据不同的具体情况对函数值沿体元边界的变化作其它适当的假设，才能较准确地求出等值面。的变化作其它适当的假设，才能较准确地求出等值面。其次，即使函数值沿体元边界作线性变化这一假设符合实际，那其次，即使函数值沿体元边界作线性变化这一假设符合实际，那么通过线性插值求得的交点位置是准确的，但是，将体元中同一么通过线性插值求得的交点位置是准确的，但是，将体元中同一个面上两条相邻边上的交点简单地用直线连接起来也

45、是一种近似个面上两条相邻边上的交点简单地用直线连接起来也是一种近似(如下图所示如下图所示)。为了说明这一问题，需要引入当体元各边界上函数值均为线性变为了说明这一问题，需要引入当体元各边界上函数值均为线性变化时的等值面模型。如图化时的等值面模型。如图3.5所示，所示，P(x,y,z)为小体元中的任意点，为小体元中的任意点，体元中的数据沿体元中的数据沿x,y,z三个方向均是线性变化的。如果点三个方向均是线性变化的。如果点P1，P2为点为点P沿沿y轴在立方体两个面上的投影，轴在立方体两个面上的投影，P11、P12、P21、P22分别为分别为P1，P2点沿点沿z轴在立方体平面上的投影。设轴在立方体平面

46、上的投影。设V为为y轴上的坐标分量，轴上的坐标分量，f为函数值，那么，通过三次线性插值，可得：为函数值，那么，通过三次线性插值，可得：(1)其中其中P1，P2两点的值可由两点的值可由P11，P12和和P21，P22插值求得，而插值求得，而P11、P12、P21、P22四个点的值又可以由它们所在体元内的一条边上的四个点的值又可以由它们所在体元内的一条边上的两个顶点插值得到。这样，通过三次线性插值运算，就可以求得两个顶点插值得到。这样，通过三次线性插值运算，就可以求得P(x,y,z)点的函数值，（点的函数值，（1）式可具体展开为：）式可具体展开为：)()()(),(212122PfPfVVVVPf

47、zyxfPPPP 其中系数其中系数ai(i=0,7)取决于体元取决于体元8个顶点处的函数值，如果给个顶点处的函数值，如果给定的等值面的值为定的等值面的值为Ft，那么，等值面就被定义为满足如下方程的，那么，等值面就被定义为满足如下方程的点的集合点的集合 (2)改变改变Ft的值，就可以得到不同等值面的表达式。的值，就可以得到不同等值面的表达式。由上述等值面方程可以方便地求出某等值面与体元边界面的交线由上述等值面方程可以方便地求出某等值面与体元边界面的交线方程。不失一般性，设某边界面所在平面的方程为方程。不失一般性，设某边界面所在平面的方程为z=z0，代入方，代入方程式程式(2)，可得，可得 (3)

48、上式可进一步表示为：上式可进一步表示为：xyzazxayzaxyazayaxaazyxf76543210),(tFzyxf),(tFxybybxbb3210 （4）显然，上述方程表示的是一条双曲线，即等值面与体元中某一个显然，上述方程表示的是一条双曲线，即等值面与体元中某一个面的交线是一条双曲线或其中的一支。如果用一条直线来表示这面的交线是一条双曲线或其中的一支。如果用一条直线来表示这条双曲线，则会引起误差（如图所示）。如果体元很小，这一误条双曲线，则会引起误差（如图所示）。如果体元很小，这一误差是可以忽略不记的。对于稀疏的三维数据，这种近似引起的误差是可以忽略不记的。对于稀疏的三维数据，这种

49、近似引起的误差是难以接受的，可通过自适应剖分算法将三角形按给定的逼近差是难以接受的，可通过自适应剖分算法将三角形按给定的逼近精度递归地分成子三角形，使这些子三角形的顶点满足方程精度递归地分成子三角形，使这些子三角形的顶点满足方程(3)，且子三角形与等值面的最大距离小于给定的容差。且子三角形与等值面的最大距离小于给定的容差。032313)(bFbbxbbybtMarching Cubes(MC)方法方法 (2)连接方式上的二义性连接方式上的二义性 Marching Cubes方法可以看成是二维等值线网格序列法在三维空方法可以看成是二维等值线网格序列法在三维空间中的推广。在网格序列法中，如果矩形网

50、格单元间中的推广。在网格序列法中，如果矩形网格单元4个顶点中有个顶点中有两个顶点的值大于等值线的值，另两个顶点的值小于等值线的值，两个顶点的值大于等值线的值，另两个顶点的值小于等值线的值，且这两个顶点交叉分布，那么等值线的连接就出现二义性。同理，且这两个顶点交叉分布，那么等值线的连接就出现二义性。同理，在在Marching Cubes方法中，如果正六面体单元的方法中，如果正六面体单元的6个矩形表面中个矩形表面中出现与此相同的情形，那么该正六面体单元中的等值面连接必然出现与此相同的情形，那么该正六面体单元中的等值面连接必然会出现二义性，这样的面称为二义性面，包含会出现二义性，这样的面称为二义性面