等值线等值面的生成.ppt

第第3 3章章 二维标量场等值线的生成二维标量场等值线的生成 二二维维标标量量场场可可看看成成是是定定义义于于某某一一个个面面上上的的二二维维标标量量函函数数F=F(x, y)，，所所谓谓等等值值线线是是由由所所有有点点(xi, yi)构构成成，，其其中中F(xi, yi) =Ft（（为为一一给给定定值值）），，将将这这些些点点按按一一定定顺顺序序连连接接起起来来就就组组成成了了函函数数值值为为Ft的的等等值值线线对对于于二二维维标标量量场场，，其其数数据据往往往往是是分分布布在在规规则则网网格格点点上上的的，，常常用用的的等等值值线线抽抽取取方方法法有网格序列法和单元剖分法有网格序列法和单元剖分法网格序列法网格序列法 •网网格格序序列列法法(grid sequence)的的基基本本思思想想是是按按网网格格单单元元的的排排列列次次序序，，逐逐个个处处理理每每一一单单元元，，寻寻找找每每一一单单元元内内相相应应的的等等值值线线段段，，在在处处理理完完所有单元后，就自然生成了该网格中的等值线分布所有单元后，就自然生成了该网格中的等值线分布•规则网格数据等值线的生成规则网格数据等值线的生成 •设设一一规规则则网网格格数数据据如如图图所所示示，，网网格格线线是是相相互互正正交交的的，，每每一一网网格格单单元元是是一一矩矩形形，，其其中中四四个个顶顶点点分分别别为为(x0, y0)、、(x0, y1)、、(x1, y0)、、(x1, y1)，，对对应应的的值值分分别别为为F00、、F01、、F10、、F11。

要要在在该该单单元元内内生生成值为成值为Ft的等值线，其主要计算步骤为：的等值线，其主要计算步骤为：•逐个计算每一网格单元与等值线的交点；逐个计算每一网格单元与等值线的交点；•连接该单元内等值线的交点，生成在该单元中的等值线线段；连接该单元内等值线的交点，生成在该单元中的等值线线段；•由一系列单元内的等值线线段构成该网格中的等值线由一系列单元内的等值线线段构成该网格中的等值线•网网格格单单元元与与等等值值线线的的交交点点计计算算主主要要是是求求各各单单元元的的边边线线与与等等值值线线的的交交点点假假设设函函数数在在单单元元内内呈呈线线性性变变化化，，可可以以采采用用顶顶点点判判定定，，边边上上插值的方法计算交点，具体步骤为：插值的方法计算交点，具体步骤为：网格序列法网格序列法 •(1) 将将网网格格点点分分为为“IN”和和“OUT”两两种种状状态态，，表表示示该该点点在在等等值值线线内内，，或或在在等等值值线线外外如如果果Fij≤Ft，，则则顶顶点点(xi, yj)为为“IN”，，记记为为“－－”；如果；如果Fij﹥Ft，则顶点，则顶点(xi, yj)为为“OUT”，记为，记为“＋＋”。

•(2) 如如果果单单元元四四个个顶顶点点全全为为“＋＋”，，或或全全为为“－－”，，则则网网格格单单元元与值为与值为Ft的等值线无交点，否则的等值线无交点，否则•(3) 对对于于两两个个顶顶点点分分别别为为“＋＋”、、“－－”的的单单元元边边，，可可用用线线性性插插值计算等值线在这条边上的交点值计算等值线在这条边上的交点•如图所示，如图所示，(x0, y0) 为为“－－”，，(x0, y1) 为为“＋＋”，则交点为，则交点为网格序列法网格序列法 •在在每每一一单单元元内内计计算算出出等等值值线线与与该该网网格格单单元元边边的的交交点点后后，，利利用用这这些些交交点点，，就就能能构构成成在在该该单单元元内内的的等等值值线线段段为为了了正正确确地地连连接接交交点点生生成等值线段，必须规定等值线的方向等值线的方向定义如下：成等值线段，必须规定等值线的方向等值线的方向定义如下：•沿沿等等值值线线走走，，大大于于等等值值线线值值的的点点在在等等值值线线的的左左边边，，小小于于等等值值线线值值的的点点在在等等值值线线的的右右边边也也就就是是“－－”点点在在等等值值线线的的右右边边，，“＋＋”点点在在等等值值线线的的左左边边。

在在规规定定了了等等值值线线的的走走向向后后，，等等值值线线的的连连接接对对于矩形单元可分如下四种情况进行：于矩形单元可分如下四种情况进行：•(1) 顶点全为顶点全为“＋＋”，或全为，或全为“－－”，无等值线段；，无等值线段；•(2) 有一个顶点为有一个顶点为“＋＋”或或“－－”，共可求出两个交点，有一条，共可求出两个交点，有一条等值线段，如图等值线段，如图3网格序列法网格序列法 •(3) 有有两两个个“＋＋”，，两两个个“－－”顶顶点点的的情情况况，，根根据据顶顶点点的的分分布布又又可分成下面两种情况：可分成下面两种情况：•①① 有有两两个个交交点点，，即即两两个个“＋＋”或或两两个个“－－”的的顶顶点点位位于于同同一一条条单单元边上，等值线段的连接如图元边上，等值线段的连接如图4a所示•②② 有有4个个交交点点，，即即“＋＋”、、“－－”顶顶点点的的分分布布相相互互交交叉叉，，这这时时的的连连接接在在规规定定了了函函数数的的走走向向后后，，可可确确定定P，，R为为入入点点，，S，，Q为为出出点点，，连接情况如图连接情况如图4b所示•在在上上述述②②的的情情况况下下，，如如果果不不规规定定等等值值线线的的走走向向，，其其实实存存在在两两种种连连接接方方式式，，见见图图5。

在在实实际际情情况况中中，，这这两两种种方方式式都都是是可可能能的的，，这这种种二义性的主要原因是在该单元内存在一马鞍点二义性的主要原因是在该单元内存在一马鞍点网格序列法网格序列法 •如如何何从从中中选选择择一一种种正正确确的的连连接接方方式式呢呢？？这这可可从从单单元元内内的的双双线线性性插插值值函函数数分分析析入入手手由由于于在在单单元元边边上上采采用用了了线线性性插插值值，，由由此此单单元元面面上函数值的变化是双线性的，上函数值的变化是双线性的，•即即等等值值线线在在单单元元内内不不是是直直线线段段而而是是双双曲曲线线二二义义性性连连接接可可通通过过求求该该双双曲曲线线两两条条渐渐近近线线交交点点处处的的函函数数值值来来判判定定，，这这是是因因为为渐渐近近线线的的交交点点总总是是与与其其中中一一对对顶顶点点落落入入同同一一区区域域内内，，如如渐渐近近线线交交点点为为“＋＋”，，则则取取图图5a的的连连接接方方式式；；如如为为“－－”，，则则取取图图5b的的连连接接方方式式即即在在图图5a中中，，表表示示单单元元中中部部为为“＋＋”，，在在图图5b中中，，表表示示单单元元中中部部为为“－－”。

在在实实际际计计算算中中，，为为简简化化计计算算，，往往往往采采用用单单元元对对角角线线交交点代替渐近线交点的计算点代替渐近线交点的计算单元剖分法单元剖分法 •在在网网格格序序列列法法中中，，提提出出了了解解决决矩矩形形单单元元内内等等值值线线的的生生成成算算法法，，其其中中马马鞍鞍点点二二义义性性的的解解决决是是算算法法的的一一个个主主要要复复杂杂点点，，除除此此之之外外人人们们还还提提出出了了单单元元剖剖分分法法，，该该方方法法与与矩矩形形单单元元法法相相比比，，其其主主要要特特点点是是采采用用三三角角片片简简化化单单元元内内等等值值线线的的抽抽取取，，无无需需再再进进行行马马鞍鞍点点的的判判定定，，但但处处理理的的单单元元数数是原来的四倍是原来的四倍•算算法法的的基基本本思思想想是是利利用用对对角角线线将将矩矩形形单单元元分分成成四四个个三三角角形形单单元元，，见见图图6，，求求出出中中心心点点的的函函数数值值，，等等值值线线的的抽抽取取直直接接在在每每个个三三角角片片中中进进行行由由于于每每一一个个三三角角片片至至多多只只包包含含一一条条等等值值线线，，因因而而在在由由三三角角片片的的三三个个点点决决定定的的平平面面内内，，可直接用直线段连接等值线。

可直接用直线段连接等值线 单元剖分法单元剖分法 •中心点函数值中心点函数值Fmid的计算可采用两种方式：的计算可采用两种方式：•如有显式函数如有显式函数F(x, y)，则，则Fmid = F(xmid, ymid)；；•如如只只有有四四个个点点的的函函数数值值，，无无法法求求显显式式函函数数形形式式，，则则可可用用四点的平均值代替四点的平均值代替Fmid•图图7列列出出了了几几种种可可能能的的情情况况，，可可以以看看出出，，通通过过利利用用矩矩形形单单元元中中点点的的函函数数值值，，等等值值线线的的精精度度提提高高了了，，其其抽抽取取过过程程也相对简单些也相对简单些第第4 4章章 等值面的生成等值面的生成 所所谓谓等等值值面面是是指指空空间间中中的的一一个个曲曲面面，，在在该该曲曲面面上上函函数数F(x, y, z)的的值值等等于于某某一一给给定定值值Ft，，即即等等值值面面是是由由所所有有点点 SFt = {(x, y, z)：：F(x, y, z) = Ft}组成的一个曲面组成的一个曲面 等等值值面面技技术术在在可可视视化化中中应应用用很很广广，，许许多多标标量量场场的的可可视视化化问问题题都都可可归归纳纳为为等等值值面面的的抽抽取取和和绘绘制制，，如如各各种种等等势势面面、、等等位位面面、、等等压压面面、、等等温温面面等等。

等等值值面面技技术术除除生生成成等等值值面面的的几几何何表表示示外外，，还还包包括括显显示示技技术术，，如如要要考考虑虑合合适适的的光光照照模模型型、、解解决决等等值值面面的的相相互互遮遮挡挡等等等等值值面面的的生生成成和和显显示示也也是是可可视视化研究中的一个重要领域化研究中的一个重要领域一一 Cuberille方法方法( (立方体方法立方体方法) ) •Cuberrille等等值值面面方方法法又又称称Opaque Cube算算法法，，最最初初由由Herman等等人提出，后来又多次改进算法主要分为两个步骤人提出，后来又多次改进算法主要分为两个步骤•(1) 确定边界单元确定边界单元•对对于于规规则则网网格格数数据据，，其其网网格格单单元元可可看看成成是是正正六六面面体体单单元元，，整整个个三三维维数数据据就就是是由由这这种种正正六六面面体体组组成成的的，，这这种种组组成成三三维维图图象象的的基基本本正正六六面面体体单单元元称称为为体体元元对对于于给给定定的的阈阈值值Ft，，遍遍历历体体数数据据中中的的各各个个单单元元，，将将组组成成体体元元8个个顶顶点点上上的的值值与与Ft进进行行比比较较，，找找出出顶顶点点值值跨跨越越Ft的的所所有有体体元元，，即即体体元元中中有有的的顶顶点点值值大大于于阈阈值值，，有有的的顶顶点点值值小小于阈值，因此体元内包含等值面片，这就是边界单元。

于阈值，因此体元内包含等值面片，这就是边界单元•(2) 绘绘制制各各边边界界单单元元的的6个个多多边边形形面面，，即即将将等等值值面面看看成成是是由由各各单单元元的六个外表面拼合而成的六个外表面拼合而成Cuberille方法方法( (立方体方法立方体方法) ) •每每个个单单元元均均为为一一正正六六面面体体，，包包括括6个个多多边边形形面面对对组组成成所所有有边边界界体体元元的的多多边边形形面面进进行行绘绘制制，，即即可可产产生生最最终终的的图图象象结结果果在在绘绘制制多多边形过程中应采用合适的光照模型和消隐技术边形过程中应采用合适的光照模型和消隐技术•如如果果在在具具有有硬硬件件深深度度缓缓存存(Z-buffer)功功能能的的计计算算机机上上运运行行立立方方体体方方法法，，可可以以将将这这组组多多边边形形不不分分次次序序地地提提交交给给硬硬件件，，由由硬硬件件完完成成消消除除隐隐藏藏面面的的任任务务如如果果以以软软件件方方式式执执行行立立方方体体方方法法，，在在算算法法中中必必须须考考虑虑多多边边形形的的遮遮挡挡问问题题一一个个有有效效的的方方法法是是把把遍遍历历体体元元集集合合与与显显示示两两个个步步骤骤合合二二为为一一，，遍遍历历体体元元集集合合时时采采用用从从后后至至前前的的次次序序。

发发现现一一个个边边界界体体元元，，就就立立刻刻显显示示它它的的6个个面面后后显显示示到到屏屏幕幕上上去去的的多多边边形形将将覆覆盖盖先先显显示示的的多多边边形形，，这这样样就就达达到到了了消消除除隐隐藏藏面面的的目目的，这就是画家算法的思想的，这就是画家算法的思想Cuberille方法方法( (立方体方法立方体方法) ) •Cuberrille算算法法的的主主要要优优点点是是简简单单易易行行，，其其主主要要缺缺点点是是出出现现严严重重的的走走样样，，显显示示的的图图象象给给人人一一种种“块块状状的的感感觉觉”，，尤尤其其在在物物体体边边界界处处锯锯齿齿形形走走样样特特别别明明显显，，而而且且画画面面较较粗糙，不能很好地显示对象的细节粗糙，不能很好地显示对象的细节•立立方方体体法法的的另另一一个个缺缺点点是是面面的的重重叠叠冗冗余余问问题题两两个个相相邻邻边边界界体体元元的的公公共共面面重重复复出出现现，，实实际际上上它它们们都都不不会会出出现现在在显显示示画画面面上上，，因因为为无无论论从从哪哪个个角角度度进进行行观观察察，，它它们们都都会会被被这这两两个个体体元元的的其其它它面面遮遮挡挡。

改改进进的的立立方方体体法法删删除除了了边边界界体体元元之之间间的的公公共共面面，，减减少少了了显显示示过过程程需需要要处处理理的的多多边边形的数量形的数量二二 Marching Cubes(MC)方法方法 •Marching Cubes（（ 移移 动动 立立 方方 体体 ）） 方方 法法 是是 由由 W.E.Lorenson和和H.E.Cline在在1987年年提提出出来来的的由由于于这这一一方方法法原原理理简简单单，，易易于于实实现现，，目目前前已已经经得得到到了了较较为为广广泛泛的的应应用用，，成成为为三三维维数数据据等等值值面面生生成成的的经经典算法，典算法，Marching Cubes算法又简称为算法又简称为MC算法•1．．MC方法的基本原理方法的基本原理•在在Marching Cubes方方法法中中，，假假定定原原始始数数据据是是离离散散的的三三维维空空间间规规则则数数据据，，一一个个体体元元定定义义为为由由相相邻邻层层上上的的8个个顶顶点点组组成成的的一一个个长长方方体体为为了了在在三三维维数数据据中中构构造造等等值值面面，，应应先先给给定定所所求求等等值值面面的的值值，，该该方方法法的的基基本本原原理理是是逐逐个个处处理理所所有有的的体体元元，，将将体体元元各各顶顶点点处处的的值值与与给给定定的的阈阈值值进进行行比比较较，，首首先先找找出出与与等等值值面面相相交交的的体体元元，，然然后后通通过过插插值值求求等等值值面面与与体体元元棱棱边边的的交交点点，，并并将将各各交交点点连连成成三三角角形形来来构构成成等等值值面面片片，，所所有有体体元元中中的的三三角角形形集集合合就就构构成成了了等等值值面面。

由由于于这这一一方方法法是是逐逐个个处处理理所所有有的的体体元元，，因因此此被被称称为为Marching Cubes方方法法MC方法的主要步骤如下：方法的主要步骤如下：Marching Cubes(MC)方法方法 •(1) 确定包含等值面的体元及对应的等值面片模式确定包含等值面的体元及对应的等值面片模式•一一个个体体元元由由8个个数数据据点点构构成成，，这这8个个数数据据点点分分别别位位于于该该体体元元的的8个个顶点上•首首先先对对体体元元的的8个个顶顶点点进进行行分分类类，，判判定定是是位位于于等等值值面面之之外外，，还还是是位于等值面之内再根据位于等值面之内再根据8个顶点的状态，确定等值面的模式个顶点的状态，确定等值面的模式•设等值面的值为设等值面的值为Ft，顶点分类规则为：，顶点分类规则为：•若某顶点的值若某顶点的值≥Ft，则定义该顶点位于等值面之外，记为，则定义该顶点位于等值面之外，记为“0”•若某顶点的值＜若某顶点的值＜Ft，则定义该顶点位于等值面之内，记为，则定义该顶点位于等值面之内，记为“1”•如如果果某某体体元元一一条条边边的的一一个个顶顶点点在在等等值值面面之之内内，，而而另另一一个个顶顶点点在在等等值值面面之之外外，，那那么么，，该该边边必必然然与与等等值值面面相相交交。

根根据据这这一一原原理理就就可可以以判断所求等值面将与哪些体元相交，或者说将穿过哪些体元判断所求等值面将与哪些体元相交，或者说将穿过哪些体元Marching Cubes(MC)方法方法 •由由于于每每个个体体元元有有8个个顶顶点点，，每每个个顶顶点点又又有有0、、1两两种种状状态态，，因因此此每每个个体体元元按按其其8个个顶顶点点的的0、、1分分布布而而言言，，共共有有28=256种种不不同同的的状状态态尽尽管管判判断断等等值值面面将将与与哪哪些些体体元元相相交交在在原原理理上上很很容容易易理理解解，，但但是是要要根根据据这这256种种不不同同的的情情况况求求出出每每个个体体元元中中的的等等值值面面却却是是很很繁繁琐琐的的，，而且也容易出错而且也容易出错•可以利用两种不同的对称性将可以利用两种不同的对称性将256种不同的情况简化为种不同的情况简化为15种•①① 互互补补对对称称性性：：如如果果将将一一个个体体元元的的顶顶点点状状态态颠颠倒倒，，即即“0”变变成成“1”，，“1”变变成成“0”，，则则等等值值面面与与体体元元中中8个个顶顶点点之之间间的的拓拓扑扑关关系系将将不不会会改改变变，，该该体体元元与与等等值值面面的的相相交交情情况况与与原原来来一一致致，，即即新新生生成成的的等等值值面面与与原原等等值值面面是是相相同同的的。

也也就就是是说说，，大大于于等等值值面面的的点点与与小小于于等等值值面面的的点点是是可可以以相相互互替替换换的的，，因因此此，，只只要要考考虑虑4个个以以下下（（含含4个个））的的顶顶点点值值大大于于Ft就就够够了了根根据据这这种种互互补补对对称称性性，，可可将将体元的模式由体元的模式由256种减少为种减少为128种 Marching Cubes(MC)方法方法 •②② 旋旋转转对对称称性性：：如如果果某某一一模模式式的的体体元元经经过过旋旋转转后后与与另另一一模模式式的的体体元元一一致致，，即即顶顶点点位位置置及及其其状状态态值值相相同同，，那那么么这这两两种种模模式式的的体体元元可可以以合合并并为为一一种种根根据据这这种种旋旋转转对对称称性性，，体体元元模模式式可可以以最最终终归归纳纳为为15种种，，见见图图2其其中中第第0种种情情况况表表示示所所有有8个个顶顶点点的的值值均均大大于于（（或或小小于于））Ft，，因因而而该该体体元元与与等等值值面面不不相相交交第第一一种种情情况况表表示示有有一一个个顶顶点点的的函函数数值值大大于于（（或或小小于于））Ft，，其其余余7个个顶顶点点均均与与此此相相反反，，因因而而该该体体元元内内的的等等值值面面将将是是一一个个三三角角面面片片。

在在考考虑虑了了上上面面两两种种对对称称性性后后，，这这一一种种情情况况实实际际上上代代表表了了16种种情情况况如如此此类类推推，，图图2中中的的15种模式反映了一个体元中种模式反映了一个体元中8个顶点可能存在的全部个顶点可能存在的全部256种状态•在在实实现现时时，，对对一一个个体体元元可可按按照照它它的的8个个顶顶点点的的状状态态构构造造一一个个一一字字节节（（8位位））的的状状态态表表，，如如图图3所所示示，，其其中中的的每每一一位位表表示示该该体体元元中中一一个个顶顶点点的的0或或1状状态态，，根根据据这这个个状状态态表表就就可可判判断断出出当当前前体体元元属属于于哪哪一一种种模模式式、、等等值值面面将将与与哪哪一一条条边边相相交交以以及及体体元元内内三三角角面面片片的的连连接接方式Marching Cubes(MC)方法方法 •(2) 计算等值面与体元边界的交点，并连接成三角形计算等值面与体元边界的交点，并连接成三角形•当当三三维维离离散散数数据据的的密密度度较较高高，，即即每每个个体体元元很很小小时时，，可可以以假假定定函函数数值值沿沿体体元元边边界界呈呈线线性性变变化化。

因因此此，，等等值值面面与与体体元元边边界界的的交交点点可可以以通过该边两端点函数值的线性插值求出，公式为：通过该边两端点函数值的线性插值求出，公式为：•求求出出了了等等值值面面与与体体元元边边界界的的交交点点以以后后，，就就可可以以按按对对应应的的模模式式将将这这些交点连接成三角形，构成该单元中的等值面片些交点连接成三角形，构成该单元中的等值面片Marching Cubes(MC)方法方法 •(3) 计算等值面的法向计算等值面的法向•为为了了绘绘制制等等值值面面的的真真实实感感图图象象，，还还必必须须给给出出构构成成等等值值面面的的各各三三角角面面片片的的法法向向对对于于等等值值面面上上的的每每一一点点，，沿沿该该面面切切线线方方向向的的梯梯度度分分量量应应该该是是零零，，因因此此该该点点的的梯梯度度矢矢量量的的方方向向就就代代表表了了等等值值面面的的法法向向MC方法就是利用这一原理来计算三角面片的法向即方法就是利用这一原理来计算三角面片的法向即•对对于于三三维维规规则则网网格格数数据据，，可可以以直直接接采采用用中中心心差差分分计计算算体体元元各各顶顶点点处的梯度，公式为：处的梯度，公式为：•三三角角形形顶顶点点处处的的法法向向量量可可由由体体元元边边界界两两端端点点处处的的梯梯度度再再通通过过线线性性插插值值求求得得。

在在实实际际绘绘制制等等值值面面时时，，为为了了消消除除各各三三角角面面片片之之间间明明暗暗的的不不连连续续变变化化，，只只要要给给出出三三角角面面片片各各顶顶点点处处的的法法向向并并采采用用哥哥罗罗得得(Gouraud)模型绘制各个三角面片即可模型绘制各个三角面片即可•在在计计算算机机图图形形学学中中，，光光滑滑的的曲曲面面常常用用多多边边形形来来逼逼近近，，这这是是因因为为处处理理平平面面比比处处理理曲曲面面容容易易得得多多例例如如，，为为了了表表示示一一个个磨磨光光的的立立方方体体的的顶顶角角，，可可使使用用7个个平平面面片片来来近近似似但但是是，，若若单单纯纯使使用用平平面面来来绘绘制制这这种种近近似似表表面面，，生生成成的的图图形形将将失失去去原原有有曲曲面面的的光光滑滑性性，，而而呈呈现现多多面面体体状状这这是是由由于于平平面面上上所所有有点点的的法法向向相相同同，，不不同同平平面面块块之之间间存在不连续的法向量变化，从而引起不连续的光亮度跳跃存在不连续的法向量变化，从而引起不连续的光亮度跳跃•如如何何能能以以较较少少的的计计算算量量来来解解决决上上述述问问题题呢呢?最最简简单单的的方方法法就就是是Gouraud明明暗暗处处理理技技术术。

Gouraud明明暗暗处处理理的的思思想想是是对对离离散散的的光光亮亮度度作作双双线线性性插插值值以以获获得得连连续续的的光光亮亮度度函函数数具具体体做做法法是是：：先先计计算算出出多多边边形形顶顶点点处处的的光光亮亮度度值值，，把把它它们们作作为为曲曲面面光光亮亮度度的的采采样样点点，，然然后后根根据据多多边边形形顶顶点点处处的的光光亮亮度度值值进进行行插插值值求求多多边边形形内内任任一一点点的的光亮度•若若采采用用扫扫描描线线绘绘制制算算法法，，则则可可沿沿当当前前扫扫描描线线进进行行双双线线性性插插值值，，这这是是一一种种简简便便易易行行的的插插值值方方法法即即先先用用多多边边形形顶顶点点的的光光亮亮度度值值由由线线性性插插值值求求出出当当前前扫扫描描线线与与多多边边形形交交点点处处的的光光亮亮度度，，然然后后根根据据交交点点的的光光亮亮度度值值再再通通过过线线性性插插值值求求出出扫扫描描线线上上位位于于多多边边形形内内每每一一象象素素点点的的光光亮亮度度值值图图4(a)显显示示一一扫扫描描线线与与多多边边形形相相交交，，交交点点为为a点点和和b点点，，p是是扫扫描描线线上上位位于于多多边边形形内内的的任任一一点点，，多多边边形形三三个个顶顶点点的的光光亮亮度度分分别别为为I1，，I2和和I3。

取取a点点的的光光亮亮度度Ia为为I1和和I2的的线线性性插插值值，，b点点的的光光亮亮度度Ib为为I1和和I3的的线线性性插插值值，，p点点的的光光亮亮度度则则为为Ia和和Ib的的线线性性插值，即：插值，即：•其其中中u,v,t称称为为插插值值参参数数(相相当当于于以以端端点点为为原原点点归归一一化化后后的的长长度度坐坐标标)•采采用用Gouraud明明暗暗处处理理不不但但可可以以克克服服用用多多边边形形表表示示曲曲面面时时光光亮亮度度的的不不连连续续现现象象，，而而且且计计算算量量也也很很小小事事实实上上，，由由于于线线性性插插值值可可使使用用增增量量法法进进行行计计算算，，其其运运算算量量仅仅涉涉及及一一次次加加法法运运算算如如在在上上例例中中，，可可沿沿扫扫描描线线从从左左至至右右的的顺顺序序计计算算AB区区段段上上所所有有象象素素的的光光亮亮度度设设Ia和和Ib已已经经确确定定，，p1和和p2点点是是相相邻邻两两象象素素的的坐坐标标，，a、、b两两点点的的插插值值参参数数之之差差为为 t，，那那么么，，不不难难发发现现p2点点光光亮亮度度Ip2和和p1点点光光亮亮度度Ip1之间有下列关系：之间有下列关系：•由由于于 I在在同同一一扫扫描描线线上上为为常常数数，，因因此此计计算算一一相相邻邻象象素素的的光光亮亮度度仅仅需需一一次次加加法法运运算算。

这这种种增增量量方方式式的的光光亮亮度度计计算算使使Gouraud明明暗暗处处理广泛用于实时图形生成理广泛用于实时图形生成•在在Gouraud明明暗暗处处理理中中，，计计算算多多边边形形顶顶点点的的光光亮亮度度可可采采用用Phong光照模型光照模型Marching Cubes(MC)方法方法 •(4) 用用MC方法求等值面的算法流程方法求等值面的算法流程•①① 将三维离散规则数据分层读入内存；将三维离散规则数据分层读入内存；•②② 扫扫描描其其中中两两层层数数据据，，逐逐个个构构造造这这两两层层之之间间的的体体元元，，每每个个体体元元中中的的8个顶点取自相邻的两层；个顶点取自相邻的两层；•③③ 将将体体元元各各个个顶顶点点的的值值与与给给定定的的等等值值面面值值Ft进进行行比比较较，，根根据据比比较较的结果进行分类，构造该体元的状态表；的结果进行分类，构造该体元的状态表；•④④ 根根据据状状态态表表，，查查得得与与该该状状态态值值对对应应的的等等值值面面分分布布模模式式，，确确定定将将与等值面相交的体元边界；与等值面相交的体元边界；•⑤⑤ 通通过过线线性性插插值值，，计计算算体体元元边边界界与与等等值值面面的的交交点点坐坐标标，，按按对对应应的的模式将这些交点连接成三角形，构成该单元中的等值面片；模式将这些交点连接成三角形，构成该单元中的等值面片；•⑥⑥ 利利用用中中心心差差分分方方法法，，求求出出体体元元各各顶顶点点处处的的梯梯度度，，再再次次通通过过线线性性插值方法，求出三角形各顶点处的法向；插值方法，求出三角形各顶点处的法向；•⑦⑦ 根据各三角面片各顶点的坐标值及法向量绘制等值面图象。

根据各三角面片各顶点的坐标值及法向量绘制等值面图象Marching Cubes (MC)方法方法 •2．．MC方法的加速算法方法的加速算法•Marching Cube方方法法是是逐逐个个单单元元地地检检测测是是否否存存在在等等值值面面，，还还要要计计算算等等值值面面与与体体元元边边界界的的交交点点，，再再由由标标准准的的连连接接模模式式将将各各个个交交点点连连接接成成等等值值面面片片事事实实上上，，据据研研究究，，真真正正与与等等值值面面相相交交的的体体元元占占总总数数据据量量很很小小的的一一部部分分（（至至多多10%左左右右）），，计计算算过过程程中中30-70%的的时时间间用用在在了了空空体体元元的的检检测测上上，，从从加加快快Marching Cube方方法法的的角角度度出出发发，，有有必必要要研研究究一一种种快快速速有有效效的的空空间间数数据据的的遍遍历历方方法法和和相相应应的的数数据据表表达达形形式式，，以以加加速速对对空空体体元元的的检检测测和和排排除除另另一一方方面面，，对对于于一一条条与与等等值值面面相相交交的的体体元元的的边边，，它它同同时时被被四四个个单单元元共共用用，，这这表表明明在在这这四四个个单单元元内内求求等等值值面面时时都都要要用用到到这这个个交交点点，，保保存存该该交交点点的的位位置及法向量对于加速算法具有重要意义。

置及法向量对于加速算法具有重要意义•对对于于规规则则网网格格数数据据，，其其体体元元是是一一个个六六面面体体单单元元，，若若采采用用空空间间八八叉叉树来表示这种体数据，则可以加快运算速度树来表示这种体数据，则可以加快运算速度•Marching Cube方方法法的的另另一一个个重重要要问问题题是是抽抽取取的的等等值值面面三三角角片片数数量量巨巨大大，，有有时时一一个个体体元元可可以以生生成成多多达达12个个三三角角片片，，当当三三维维数数据据的的数数据据量量很很大大时时，，三三角角片片的的数数量量也也非非常常大大这这给给等等值值面面的的绘绘制制和和交交互互操操作作带带来来很很大大困困难难Schroeder提提出出了了在在不不影影响响图图形形质质量量的的情情况况下下，，通通过过对对原原等等值值面面三三角角片片网网重重排排结结点点，，合合并并简简化化，，生生成成最最优优化化意意义义下下的的Delaunay三三角角化化网网，，可可以以有有效效加加快快图图形形的的实实时时显显示示，，这对于这对于Marching Cube方法的实用是非常有意义的方法的实用是非常有意义的Marching Cubes (MC)方法方法 •3．．MC方法存在的问题方法存在的问题•(1) MC方法构造的三角面片是三维等值面的近似表示方法构造的三角面片是三维等值面的近似表示•首首先先，，在在MC方方法法中中，，等等值值面面与与体体元元边边界界的的交交点点是是基基于于函函数数值值在在体体元元边边界界上上呈呈线线性性变变化化这这一一假假设设而而求求出出的的。

当当数数据据密密度度高高、、体体元元很很小小时时，，这这一一假假设设接接近近于于实实际际情情况况但但是是，，在在稀稀疏疏数数据据中中，，体体元元较较大大，，如如果果仍仍然然认认为为函函数数值值在在体体元元边边界界上上呈呈线线性性变变化化，，将将会会产产生生较较大大误误差差这这时时，，需需要要根根据据不不同同的的具具体体情情况况对对函函数数值值沿沿体体元元边边界界的变化作其它适当的假设，才能较准确地求出等值面的变化作其它适当的假设，才能较准确地求出等值面•其其次次，，即即使使函函数数值值沿沿体体元元边边界界作作线线性性变变化化这这一一假假设设符符合合实实际际，，那那么么通通过过线线性性插插值值求求得得的的交交点点位位置置是是准准确确的的，，但但是是，，将将体体元元中中同同一一个个面面上上两两条条相相邻邻边边上上的的交交点点简简单单地地用用直直线线连连接接起起来来也也是是一一种种近近似似(如下图所示如下图所示)•为为了了说说明明这这一一问问题题，，需需要要引引入入当当体体元元各各边边界界上上函函数数值值均均为为线线性性变变化化时时的的等等值值面面模模型型如如图图3.5所所示示，，P(x, y, z)为为小小体体元元中中的的任任意意点点，，体体元元中中的的数数据据沿沿x, y, z三三个个方方向向均均是是线线性性变变化化的的。

如如果果点点P1，，P2为为点点P沿沿y轴轴在在立立方方体体两两个个面面上上的的投投影影，，P11、、P12、、P21、、P22分分别别为为P1，，P2点点沿沿z轴轴在在立立方方体体平平面面上上的的投投影影设设V为为y轴轴上上的的坐坐标标分分量量，，f为函数值，那么，通过三次线性插值，可得：为函数值，那么，通过三次线性插值，可得：• (1)•其其中中P1，，P2两两点点的的值值可可由由P11，，P12和和P21，，P22插插值值求求得得，，而而P11、、P12、、P21、、P22四四个个点点的的值值又又可可以以由由它它们们所所在在体体元元内内的的一一条条边边上上的的两两个个顶顶点点插插值值得得到到这这样样，，通通过过三三次次线线性性插插值值运运算算，，就就可可以以求求得得P(x, y, z)点的函数值，（点的函数值，（1）式可具体展开为：）式可具体展开为：•其其中中系系数数ai ( i= 0, …7 )取取决决于于体体元元8个个顶顶点点处处的的函函数数值值，，如如果果给给定定的的等等值值面面的的值值为为Ft，，那那么么，，等等值值面面就就被被定定义义为为满满足足如如下下方方程程的的点的集合点的集合• (2)• •改变改变Ft的值，就可以得到不同等值面的表达式。

的值，就可以得到不同等值面的表达式•由由上上述述等等值值面面方方程程可可以以方方便便地地求求出出某某等等值值面面与与体体元元边边界界面面的的交交线线方方程程不不失失一一般般性性，，设设某某边边界界面面所所在在平平面面的的方方程程为为z=z0，，代代入入方方程式程式(2)，可得，可得• (3)•上式可进一步表示为：上式可进一步表示为：• （（4））•显显然然，，上上述述方方程程表表示示的的是是一一条条双双曲曲线线，，即即等等值值面面与与体体元元中中某某一一个个面面的的交交线线是是一一条条双双曲曲线线或或其其中中的的一一支支如如果果用用一一条条直直线线来来表表示示这这条条双双曲曲线线，，则则会会引引起起误误差差（（如如图图所所示示））。

如如果果体体元元很很小小，，这这一一误误差差是是可可以以忽忽略略不不记记的的对对于于稀稀疏疏的的三三维维数数据据，，这这种种近近似似引引起起的的误误差差是是难难以以接接受受的的，，可可通通过过自自适适应应剖剖分分算算法法将将三三角角形形按按给给定定的的逼逼近近精精度度递递归归地地分分成成子子三三角角形形，，使使这这些些子子三三角角形形的的顶顶点点满满足足方方程程(3)，且子三角形与等值面的最大距离小于给定的容差且子三角形与等值面的最大距离小于给定的容差Marching Cubes (MC)方法方法 •(2) 连接方式上的二义性连接方式上的二义性•Marching Cubes方方法法可可以以看看成成是是二二维维等等值值线线网网格格序序列列法法在在三三维维空空间间中中的的推推广广在在网网格格序序列列法法中中，，如如果果矩矩形形网网格格单单元元4个个顶顶点点中中有有两两个个顶顶点点的的值值大大于于等等值值线线的的值值，，另另两两个个顶顶点点的的值值小小于于等等值值线线的的值值，，且且这这两两个个顶顶点点交交叉叉分分布布，，那那么么等等值值线线的的连连接接就就出出现现二二义义性性同同理理，，在在Marching Cubes方方法法中中，，如如果果正正六六面面体体单单元元的的6个个矩矩形形表表面面中中出出现现与与此此相相同同的的情情形形，，那那么么该该正正六六面面体体单单元元中中的的等等值值面面连连接接必必然然会会出出现现二二义义性性，，这这样样的的面面称称为为二二义义性性面面，，包包含含1个个以以上上的的二二义义性性面面的的体体元元，，即即为为具具有有二二义义性性的的体体元元，，如如下下图图所所示示。

事事实实上上，，在在Marching Cubes方方法法的的15种种模模式式中中，，第第3、、6、、7、、10、、12、、13等等6种情况是具有二义性的种情况是具有二义性的Marching Cubes (MC)方法方法 •4．用双曲线渐近线方法判别和消除二义性．用双曲线渐近线方法判别和消除二义性•MC方方法法存存在在连连接接方方式式的的二二义义性性问问题题在在该该方方法法提提出出后后不不久久，，就就由由M.J.Durst提提出出来来了了，，这这一一问问题题如如果果不不解解决决，，将将造造成成等等值值面面连连接接上上的的错错误误如如在在两两个个相相邻邻体体元元的的公公共共面面上上，，可可能能会会出出现现两两种种不不同同的连接方式，从而形成空洞的连接方式，从而形成空洞•尽尽管管人人们们已已经经提提出出了了几几种种不不同同的的判判别别和和消消除除二二义义性性的的方方法法，，但但以以G.M.Nielson等人提出的渐近线法等人提出的渐近线法(1991)最为常用最为常用•如如前前所所述述，，在在一一般般情情况况下下，，等等值值面面与与体体元元边边界界面面所所在在平平面面的的交交线线是是一一条条双双曲曲线线或或其其中中的的一一支支。

该该双双曲曲线线的的两两支支及及其其渐渐近近线线与与体体元元的的一一个个边边界界面面的的相相对对位位置置关关系系可可用用下下图图5来来表表示示在在该该图图所所列列的的四四种种状状态态中中，，当当双双曲曲线线的的两两支支均均与与体体元元的的某某边边界界面面相相交交时时，，就就会会出现连接方式的二义性出现连接方式的二义性•在在出出现现二二义义性性的的情情况况中中，，双双曲曲线线的的两两支支将将边边界界面面划划分分为为3个个区区域域，，显显然然，，双双曲曲线线渐渐近近线线的的交交点点总总是是和和边边界界面面中中呈呈对对角角分分布布的的一一对对顶顶点落在同一区域内，这一性质就成为解决二义性问题的基础点落在同一区域内，这一性质就成为解决二义性问题的基础•根据根据(4)式，渐近线方程可写为：式，渐近线方程可写为：•当当出出现现二二义义性性时时，，需需要要计计算算f(x, y, z0)的的值值如如果果f(x, y, z0)＞＞Ft，，则则渐渐近近线线的的交交点点应应与与数数值值大大于于Ft的的一一对对顶顶点点落落在在同同一一区区域域，，如如图图6(a)所所示示，，可可连连接接M1M2、、M3M4，，否否则则渐渐近近线线交交点点与与数数值值小小于于Ft的的一一对对顶顶点点落落在在同同一一区区域域，，如如图图6(b)所所示示，，可可连连接接M1M3、、M2M4。

在在图图6中中，，当当f(x, y, z0)＞＞Ft时时，，对对渐渐进进线线的的交交点点标标以以正正值值，，其其对对应应的的二二义义面面称称为为正正值值二二义义面面(记记为为PAF)当当f(x, y, z0)＜＜Ft时时，，对对渐渐进进线线的的交交点点标标以以负负值值，，其其对对应应的的二二义义面面称称为为负负值值二二义义面面(记记为为NAF) •在在所所列列的的全全部部15种种模模式式中中，，第第0、、1、、2、、4、、5、、8、、9、、11、、14这这9种种模模式式下下不不存存在在二二义义性性面面，，因因而而它它们们只只存存在在1种种连连接接方方式式第第3、、6两两种种模模式式，，各各存存在在一一个个二二义义性性面面，，因因此此各各有有两两种种连连接接方方式式第第10、、12两两种种模模式式，，各各存存在在两两个个二二义义性性面面，，因因而而各各有有4种种连连接接方方式式第第7种种模模式式有有3个个二二义义性性面面，，因因而而有有8种种连连接接方方式式。

第第13种种模模式式有有6个个二二义义性性面面，，因因而而有有64种种连连接接方方式式将将以以上上各各种种情情况况加加在在一一起起，，共共有有93种种不不同同的的连连接接方方式式对对于于存存在在二二义义性性的的体体元元，，按按上上述述方方法法解解决决二二义义性性问问题题，，虽虽然然增增加加了了计计算算工工作作量量，，但但是是为为了了得得出出完完全全正正确的结果却是十分必要的确的结果却是十分必要的三三 Marching Tetrahedra (MT)方法方法 •Marching Tetrahedra方方法法简简称称为为MT方方法法，，亦亦称称四四面面体体剖剖分分法法，，它它是是在在MC方方法法的的基基础础上上发发展展起起来来的的该该方方法法首首先先将将立立方方体体单单元元剖剖分分为为四四面面体体，，然然后后在在其其中中构构造造等等值值面面提提出出这这种种方方法法的的原原因因很很多多首首先先，，由由于于四四面面体体是是最最简简单单的的多多面面体体，，其其它它类类型型的的多多面面体体都都能能剖剖分分为为四四面面体体其其次次，，将将立立方方体体剖剖分分为为四四面面体体后后，，在在四四面面体体中中构构造造的的等等值值面面的的精精度度要要比比在在立立方方体体中中构构造造的的等等值值面面要要高高。

而而最最直直接接的的原原因因是是企企图图通通过过在在四四面面体体内内构构造造等等值值面面来来避避免免MC方方法法中中存存在的二义性问题在的二义性问题•1．．MT方法的基本原理及存在的问题方法的基本原理及存在的问题•可可以以将将一一个个立立方方体体剖剖分分为为5个个、、6个个和和24个个四四面面体体，，5个个或或6个个四四面面体体的的剖剖分分是是一一种种不不对对称称的的剖剖分分，，剖剖分分后后的的四四面面体体不不全全等等，，24个个四四面面体体的的剖剖分分是是一一种种全全等等四四面面体体的的剖剖分分常常用用的的MT方方法法是是将将一一个个立立方方体体剖剖分分为为5个个四四面面体体与与前前述述的的方方法法一一样样，，假假定定待待求求的的等等值值面面的的值值为为Ft，，如如果果四四面面体体顶顶点点的的值值大大于于（（或或等等于于））Ft，，则则将将该该顶顶点赋以点赋以“+”号；如果小于号；如果小于Ft，则将该顶点赋以，则将该顶点赋以“－－”号•假假设设在在四四面面体体的的边边上上数数据据呈呈线线性性变变化化，，在在考考虑虑了了“+”、、“－－”号号反反号号造造成成的的对对称称情情况况后后，，对对于于每每个个四四面面体体，，等等值值面面模模式式只只有有三三种种情情况况，，如如图图7所所示示。

如如果果4个个顶顶点点全全为为“+”或或全全为为“－－”，，等等值值面面与与该该四四面面体体无无交交点点；；如如一一个个顶顶点点为为“+”，，而而另另外外3个个顶顶点点为为“－－”，，则则该该四四面面体体中中等等值值面面是是一一个个三三角角片片；；如如有有两两个个顶顶点点为为“+”，，而而另另外外2个个顶顶点点为为“－－”，，则则该该四四面面体体中中等等值值面面是是一一个个四四边边形形，，可可分分解解为为两两个个三三角角片片将将各各三三角角片片拼拼接接起起来来即即可可构构成成等等值值面，这就是面，这就是MT方法的基本原理方法的基本原理•虽虽然然在在每每一一个个四四面面体体内内，，等等值值面面的的生生成成是是由由顶顶点点函函数数值值的的分分布布情情况况唯唯一一确确定定的的，，但但是是，，对对于于一一个个立立方方体体来来说说，，却却有有两两种种不不同同的的四四面面体体剖剖分分方方式式不不同同的的剖剖分分方方式式将将生生成不同的等值面，即等值面的结果依赖于剖分方式成不同的等值面，即等值面的结果依赖于剖分方式•另另一一方方面面，，为为了了在在相相邻邻体体元元的的公公共共面面上上不不出出现现裂裂缝缝，，必必须须保保证证在在这这个个面面上上的的剖剖分分一一致致性性，，也也就就是是说说，，四四面面体体的的剖剖分分方方式式在在一一系系列列体体元元中中是是交交替替变变化化的的。

这这样样一一来来，，三三维维数数据据内内等等值值面面的的构构造造是是与与最最初初一一个个体体元元的的剖剖分分方方式式有有关关的的因因此此MT方方法法并并不不能能消消除除等等值值面面构构造造中中的的二二义义性性，，这仍然是一个有待解决的问题这仍然是一个有待解决的问题•2．．MT方法中二义性的判别和消除方法中二义性的判别和消除 •当当一一个个立立方方体体剖剖分分为为5个个四四面面体体时时，，在在每每一一个个四四面面体体的的6条条边边中中，，有有些些是是原原有有立立方方体体的的棱棱，，而而另另一一些些则则是是立立方方体体6个个面面上上的的对对角角线线经经过过仔仔细细研研究究，，在在5个个四四面面体体的的30条条边边中中，，只只有有12条条边边是是原原有有立立方方体体的的棱棱，，而而其其余余18条条则则均均为为立立方方体体面面上上的的对对角角线线这这就就提提出出了了一一个个问问题题，，即即当当立立方方体体每每条条棱棱上上的的函函数数值值呈呈线线性性变变化化时时，，立立方方体体每每个个面面中中对对角角线线上上的的函函数数值值是是否否也也呈呈线线性性变变化化呢呢？？如如果果不不是是，，那那么么当当该该对对角角线线两两端端点点均均为为“＋＋”（（或或“－－”））时时，，就就认认为为在在该该线线段上没有交点，又是否能成立呢？段上没有交点，又是否能成立呢？•前前面面论论述述过过，，当当体体元元每每条条棱棱上上的的函函数数值值均均呈呈线线性性变变化化时时，，体体元元内内等等值值面面与与体体元元边边界界面面的的交交线线是是由由（（3））式式表表示示的的一一条条双双曲曲线线。

设设体体元元中中一一个个面面所所在在的的平平面面为为z = z0，，该该面面上上某某一一对对顶顶点点的的坐坐标标为为(xa, ya, z0)及及(xb, yb, z0)，则由该对顶点构成的对角线方程为，则由该对顶点构成的对角线方程为• (5)•将将（（5））式式代代入入（（3））式式，，经经过过整整理理后后可可知知，，沿沿对对角角线线的的函函数数值值分分布为一个二次函数，并可写成如下形式：布为一个二次函数，并可写成如下形式：• (6)•其其中中A，，B，，C是是由由对对角角线线端端点点坐坐标标及及体体元元的的8个个顶顶点点的的函函数数值值决决定定的的常常数数既既然然沿沿对对角角线线的的函函数数值值分分布布为为二二次次函函数数，，那那么么当当对对角角线线两两端端点点均均为为“＋＋”（（或或“－－”））时时，，就就不不能能简简单单地地认认为为在在该该对对角线上无交点，而需要求解（角线上无交点，而需要求解（6）式才能得出结果。

式才能得出结果•于于是是，，判判断断对对应应于于阈阈值值为为Ft的的等等值值面面是是否否与与该该对对角角线线相相交交，，就就需需要判断方程式（要判断方程式（6）在区间）在区间[0，，1]内是否有解内是否有解 •若若C≠0，，且且，，则则方方程程(6)式式将将有有两两个个不不同同的的解解t1和和t2如如果果t1和和t2都都在在区区间间[0，，1]内内，，那那么么等等值值面面与与对对角角线线有有两两个个不不同同的的交交点点，，这这是是当当对对角角线线两两端端点点的的函函数数值值为为同同号号时时的的情情况况，，是是不不能能被被忽忽略略的的在在这种情况下，等值面与体元对角线相交的多种可能性如图这种情况下，等值面与体元对角线相交的多种可能性如图8所示 图8 等值面与体元对角线相交的多种可能性•图图8（（a））表表明明，，只只有有一一条条双双曲曲线线通通过过体体元元的的面面并并与与对对角角线线有有两两个个交交点点，，但但此此刻刻，，该该对对角角线线两两端端点点的的函函数数值值均均为为“+”。

•图图8(b)和和(c)表表示示两两条条双双曲曲线线都都通通过过该该面面，，这这是是MC方方法法中中的的二二义义面面在在图图8(b)中中，，两两条条渐渐近近线线的的交交点点与与为为“+”的的对对角角线线两两端端点点取取异异号号，，而而在在图图8(c)中中，，两两条条渐渐近近线线的的交交点点与与为为“+”的的对对角角线线两两端端点点取取同同号号在在这这两两种种情情况况下下，，根根据据判判别别式式计计算算结结果果，，该该等等值值线线均均与与对对角角线线有有两两个个交交点点如如果果认认为为该该对对角角线线两两端端点点的的函函数数值值均均为为“+”而而忽忽略略这这两两个个交交点点，，将将导导致致等等值值线线的的错错误误连连接接（（如如图图8(d)所所示示））或或等等值值线线的的连连接接不不准准确确（（如如图图8(e)所所示示）），，而而这这正是传统的正是传统的MT方法所存在的问题方法所存在的问题综综上上所所述述，，在在MT方方法法中中判判断断四四面面体体的的一一条条边边与与等等值值面面是是否否有有交交点点及及计计算算交交点点的的算法可描述如下：算法可描述如下： 如果如果E1E2是原体元的一条边是原体元的一条边 {如果该边两端点所赋值异号，如果该边两端点所赋值异号，则通过线性插值计算交点（等值点）并输出则通过线性插值计算交点（等值点）并输出否则，否则，没有交点没有交点 } 否则否则 {如果两端点函数值同号而相应的判别式非负如果两端点函数值同号而相应的判别式非负则解一元二次方程式计算两个交点，并输出落在两端点间的交点则解一元二次方程式计算两个交点，并输出落在两端点间的交点如果两端点函数值异号如果两端点函数值异号计算两交点，取落在两端点间的点为交点，并输出计算两交点，取落在两端点间的点为交点，并输出舍去另一点舍去另一点 }•3．连接等值点构造多边形．连接等值点构造多边形•在在正正确确地地计计算算出出四四面面体体各各条条边边上上的的交交点点，，即即等等值值点点以以后后，，下下一一步步就就应应该该将将一一个个四四面面体体内内所所有有等等值值点点连连接接成成有有效效的的多多边边形形。

为为此此，，需需要要首首先先考考虑虑四四面面体体中中任任一一三三角角面面片片上上等等值值点点的的连连接接为为了了保保证证相相邻邻四四面面体体在在公公共共面面上上等等值值面面的的连连接接不不出出现现裂裂缝缝，，等等值值面面被被公公共共面面所所截截得得的的交交线线应应该该由由公公共共面面的的性性质质唯唯一一决决定定，，而而不不受受它它所所在在的的四四面面体体中中其其它它顶顶点点的的影影响响与与此此同同时时，，三三角角形形上上等等值值点点的的连连线线不不能能与与三三角角形形的的任任何何一一条条边边重重合合，，且且连连线线不不能能交交叉叉由由于于等等值值点点的的连线就是等值线，所以这样的假设自然是合理的连线就是等值线，所以这样的假设自然是合理的•对对于于一一个个三三角角形形来来说说，，根根据据顶顶点点的的函函数数值值所所赋赋予予的的符符号号及及等等值值点点的的分分布布，，可可以以分分为为6种种状状态态具具体体可可参参见见唐唐泽泽圣圣《《三三维维数数据据场场可可视化视化》》P101-P103•当当实实现现了了四四面面体体每每一一个个三三角角形形内内等等值值点点的的连连接接以以后后，，不不同同三三角角形形内内的的连连接接线线在在三三角角形形的的公公共共边边上上首首尾尾相相连连即即可可形形成成多多边边形形。

首首先先从从一一个个三三角角形形内内任任取取一一条条连连线线，，在在该该线线段段末末端端点点所所在在的的另另一一个个三三角角形形内内找找到到以以该该点点为为起起点点的的下下一一条条边边，，并并对对访访问问过过的的线线段段做做上上标标记记，，依依次次找找下下去去，，直直到到与与最最初初的的边边相相遇遇，，即即构构成成一一封封闭闭的的多多边边形形接接着着，，判判断断是是否否还还有有未未访访问问过过的的线线段段如如果果有有，，从从中中取取出出一一条条重重复上述的过程，直至所有的多边形都输出为止复上述的过程，直至所有的多边形都输出为止•由由此此可可以以看看出出，，四四面面体体每每一一个个面面上上的的等等值值点点的的连连线线完完全全由由三三角角形形的的三三个个顶顶点点来来决决定定因因而而，，对对于于任任何何相相邻邻的的四四面面体体，，在在公公共共面面上上的的连连接接必必然然是是一一致致的的，，从从而而保保证证了了在在公公共共面面上上等等值值面面连连接接的的一一致致性四四 剖分立方体方法剖分立方体方法 •在在W.E.Lorenson和和H.E.Cline于于1987年年提提出出Marching Cubes方方法法之之后后不不久久，，他他们们就就发发现现，，当当离离散散三三维维数数据据的的密密度度很很高高时时，，由由Marching Cubes方方法法在在体体元元中中产产生生的的小小三三角角面面片片常常常常很很小小，，在在图图像像空空间间中中的的投投影影面面积积与与屏屏幕幕上上一一个个像像素素点点的的大大小小差差不不多多，，甚甚至至还还要要小小，，因因此此，，通通过过插插值值来来计计算算小小三三角角面面片片是是不不必必要要的的。

随随着着新新一一代代CT和和MRI等等设设备备的的出出现现，，二二维维切切片片中中图图象象的的分分辨辨率率不不断断提提高高，，断断层层不不断断变变薄薄，，已已经经接接近近并并超超过过计计算算机机屏屏幕幕显显示示的的分分辨辨率率在在这这种种情情况况下下，，常常用用于于三三维维表表面面生生成成的的Marching Cubes方方法法已已不不适适用用于于是是，，在在1988年年，，仍仍由由W.E.Lorenson和和H.E.Cline两两人人提提出出了了剖剖分立方体分立方体(Dividing Cubes)方法•1．剖分立方体方法的基本原理．剖分立方体方法的基本原理•与与MC方方法法一一样样，，剖剖分分立立方方体体方方法法对对各各体体元元逐逐层层、、逐逐行行、、逐逐列列地地进进行行处处理理当当某某一一个个体体元元8个个顶顶点点的的函函数数值值均均大大于于（（或或小小于于））给给定定的的等等值值面面的的数数值值时时，，这这就就表表明明，，等等值值面面不不通通过过该该体体元元，，因因而而不不予予处处理理当当某某一一个个体体元元8个个顶顶点点的的函函数数值值中中有有的的大大于于等等值值面面的的值值，，有有的的又又小小于于等等值值面面的的值值，，而而此此体体元元在在屏屏幕幕上上的的投投影影又又大大于于一一个个像像素素时时，，则则将将此此体体元元沿沿x，，y，，z三三个个方方向向进进行行剖剖分分直直至至其其投投影影等等于于或或小小于于像像素素时时，，再再对对所所有有剖剖分分后后的的小小体体元元的的8个个顶顶点点进进行行检检测测。

当当部部分分顶顶点点的的函函数数值值大大于于等等值值面面的的值值、、部部分分顶顶点点的的函函数数值值又又小小于于等等值值面面的的值值时时，，将将此此小小体体元元投投影影到到屏屏幕幕上上，，形形成成所所需需要要的的等等值值面面图图象象否否则则，，也也不不予予处处理理当当将将一一个个体体元元剖剖分分为为小小体体元元时时，，子子体体元元各各顶顶点点的的函函数数值值及及法法向向量量是是由由体体元元的的函函数数值值及及法法向向量量通通过过三三次次线性插值得到的线性插值得到的 •当当一一个个小小体体元元需需要要投投影影到到屏屏幕幕上上时时，，将将该该小小体体元元处处理理成成通通过过该该体体元元中中心心点点的的一一个个小小面面片片，，一一般般称称为为表表面面点点(surface-point)该该小小面面片片含含有有空空间间几几何何位位置置、、等等值值面面的的值值及及法法向向量量等等信信息息当当投投影影方方向向确确定定后后，，即即可可利利用用计计算算机机图图形形学学中中的的光光照照模模型型计计算算出出光光强强，，并并利利用用Z-Buffer算算法法实实现现消消隐隐，，最最后后得得出出相相应应像像素素点点的的光光强强度度值值。

采采用用绘绘制制表表面面点点而而不不是是绘绘制制体体元元内内等等值值面面的的办办法法来来绘绘制制整整个个等等值值面面，，可可以以节节省省大大量量的的计计算算时时间间当当然然，，其其结结果果仅仅为为等等值值面面的的近近似似表表示示，，但但对对于于数数据据密密度度很很高高的的医医学学图图象象来来说说，，其其视视觉觉效效果果是是可可以以接受的•2．．剖分立方体算法的改进剖分立方体算法的改进 •(1) 插值系数检索表插值系数检索表•当当一一个个体体元元剖剖分分为为小小体体元元时时，，小小体体元元顶顶点点处处的的函函数数值值及及法法向向量量是是通通过过对对体体元元顶顶点点处处的的函函数数值值及及法法向向量量作作三三次次线线性性插插值值得得到到的的，，由由于于要要多多次次进进行行剖剖分分，，因因而而存存在在着着大大量量的的插插值值运运算算，，如如为为插插值值运运算算建建立立一一个个插插值值系系数数表表，，用用查查表表来来代代替替插插值值运运算算，，则则可可加加快快计计算算速速度•(2) 面点跟踪的相关性算法面点跟踪的相关性算法•当当一一个个与与等等值值面面相相交交的的体体元元剖剖分分为为小小体体元元以以后后，，需需要要继继续续检检测测哪哪些些小小体体元元与与等等值值面面相相交交。

当当体体元元数数目目较较大大时时，，逐逐个个计计算算小小体体元元顶顶点点处处的的函函数数值值，，并并且且检检测测是是否否与与等等值值面面相相交交的的计计算算量量也也较较大大一一般般说说来来，，与与等等值值面面相相交交的的小小体体元元总总是是相相邻邻的的，，我我们们可可以以利利用用这这一一相关性来排除不必要的小体元检测计算相关性来排除不必要的小体元检测计算。