第3-4章等值线等值面的生成.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,3,章 二维标量场等值线的生成,二维标量场可看成是定义于某一个面上的二维标量函数,F,=,F,(,x,y,),，所谓等值线是由所有点,(,x,i,y,i,),构成，其中,F,(,x,i,y,i,)=,F,t,（为一给定值），将这些点按一定顺序连接起来就组成了函数值为,F,t,的等值线。对于二维标量场，其数据往往是分布在规则网格点上的，常用的等值线抽取方法有网格序列法和单元剖分法。,网格序列法,网格序列法,(grid sequence),的基本思想是按网格单元的排列次序，逐个处理每一单元，寻找每一单元内相应的等值线段，在处理完所有单元后，就自然生成了该网格中的等值线分布。,规则网格数据等值线的生成,设一规则网格数据如图所示，网格线是相互正交的，每一网格单元是一矩形，其中四个顶点分别为,(,x,0,y,0,),、,(,x,0,y,1,),、,(,x,1,y,0,),、,(,x,1,y,1,),，对应的值分别为,F,00,、,F,01,、,F,10,、,F,11,。要在该单元内生成值为,F,t,的等值线，其主要计算步骤为：,逐个计算每一网格单元与等值线的交点；,连接该单元内等值线的交点，生成在该单元中的等值线线段；,由一系列单元内的等值线线段构成该网格中的等值线。,网格单元与等值线的交点计算主要是求各单元的边线与等值线的交点。假设函数在单元内呈线性变化，可以采用顶点判定，边上插值的方法计算交点，具体步骤为：,网格序列法,(1),将网格点分为“,IN”,和“,OUT”,两种状态，表示该点在等值线内，或在等值线外。如果,F,ij,F,t,，则顶点,(,x,i,y,j,),为“,IN”,，记为“”；如果,F,ij,F,t,，则顶点,(,x,i,y,j,),为“,OUT”,，记为“”。,(2),如果单元四个顶点全为“”，或全为“”，则网格单元与值为,F,t,的等值线无交点，否则,(3),对于两个顶点分别为“”、“”的单元边，可用线性插值计算等值线在这条边上的交点。,如图所示，,(,x,0,y,0,),为“”，,(,x,0,y,1,),为“”，则交点为,网格序列法,在每一单元内计算出等值线与该网格单元边的交点后，利用这些交点，就能构成在该单元内的等值线段。为了正确地连接交点生成等值线段，必须规定等值线的方向。等值线的方向定义如下：,沿等值线走，大于等值线值的点在等值线的左边，小于等值线值的点在等值线的右边。也就是“”点在等值线的右边，“”点在等值线的左边。在规定了等值线的走向后，等值线的连接对于矩形单元可分如下四种情况进行：,(1),顶点全为“”，或全为“”，无等值线段；,(2),有一个顶点为“”或“”，共可求出两个交点，有一条等值线段，如图,3,。,网格序列法,(3),有两个“”，两个“”顶点的情况，根据顶点的分布又可分成下面两种情况：,有两个交点，即两个“”或两个“”的顶点位于同一条单元边上，等值线段的连接如图,4a,所示。,有,4,个交点，即“”、“”顶点的分布相互交叉，这时的连接在规定了函数的走向后，可确定,P,，,R,为入点，,S,，,Q,为出点，连接情况如图,4b,所示。,在上述,的情况下，如果不规定等值线的走向，其实存在两种连接方式，见图,5,。在实际情况中，这两种方式都是可能的，这种二义性的主要原因是在该单元内存在一马鞍点。,网格序列法,如何从中选择一种正确的连接方式呢？这可从单元内的双线性插值函数分析入手。由于在单元边上采用了线性插值，由此单元面上函数值的变化是双线性的，,即等值线在单元内不是直线段而是双曲线。二义性连接可通过求该双曲线两条渐近线交点处的函数值来判定，这是因为渐近线的交点总是与其中一对顶点落入同一区域内，如渐近线交点为“”，则取图,5a,的连接方式；如为“”，则取图,5b,的连接方式。即在图,5a,中，表示单元中部为“”，在图,5b,中，表示单元中部为“”。在实际计算中，为简化计算，往往采用单元对角线交点代替渐近线交点的计算。,单元剖分法,在网格序列法中，提出了解决矩形单元内等值线的生成算法，其中马鞍点二义性的解决是算法的一个主要复杂点，除此之外人们还提出了单元剖分法，该方法与矩形单元法相比，其主要特点是采用三角片简化单元内等值线的抽取，无需再进行马鞍点的判定，但处理的单元数是原来的四倍。,算法的基本思想是利用对角线将矩形单元分成四个三角形单元，见图,6,，求出中心点的函数值，等值线的抽取直接在每个三角片中进行。由于每一个三角片至多只包含一条等值线，因而在由三角片的三个点决定的平面内，可直接用直线段连接等值线。,单元剖分法,中心点函数值,F,mid,的计算可采用两种方式：,如有显式函数,F,(,x,y,),，则,F,mid,=,F,(,x,mid,y,mid,),；,如只有四个点的函数值，无法求显式函数形式，则可用四点的平均值代替,F,mid,。,图,7,列出了几种可能的情况，可以看出，通过利用矩形单元中点的函数值等值线的精度提高了，其抽取过程也相对简单些。,第,4,章 等值面的生成,所谓等值面是指空间中的一个曲面，在该曲面上函数,F,(,x,y,z,),的值等于某一给定值,F,t,，即等值面是由所有点,S,Ft,=(,x,y,z,),：,F,(,x,y,z,)=,F,t,组成的一个曲面。,等值面技术在可视化中应用很广，许多标量场的可视化问题都可归纳为等值面的抽取和绘制，如各种等势面、等位面、等压面、等温面等。等值面技术除生成等值面的几何表示外，还包括显示技术，如要考虑合适的光照模型、解决等值面的相互遮挡等。等值面的生成和显示也是可视化研究中的一个重要领域。,一,Cuberille,方法,(,立方体方法,),Cuberrille,等值面方法又称,Opaque Cube,算法，最初由,Herman,等人提出，后来又多次改进。算法主要分为两个步骤。,(1),确定边界单元,对于规则网格数据，其网格单元可看成是正六面体单元，整个三维数据就是由这种正六面体组成的，这种组成三维图象的基本正六面体单元称为体元。对于给定的阈值,F,t,，遍历体数据中的各个单元，将组成体元,8,个顶点上的值与,F,t,进行比较，找出顶点值跨越,F,t,的所有体元，即体元中有的顶点值大于阈值，有的顶点值小于阈值，因此体元内包含等值面片，这就是边界单元。,(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,个顶点的状态，确定等值面的模式。,设等值面的值为,F,t,，顶点分类规则为：,若某顶点的值,F,t,，则定义该顶点位于等值面之外，记为“,0”,。,若某顶点的值,F,t,，则定义该顶点位于等值面之内，记为“,1”,。,如果某体元一条边的一个顶点在等值面之内，而另一个顶点在等值面之外，那么，该边必然与等值面相交。根据这一原理就可以判断所求等值面将与哪些体元相交，或者说将穿过哪些体元。,Marching,Cubes(MC,),方法,由于每个体元有,8,个顶点，每个顶点又有,0,、,1,两种状态，因此每个体元按其,8,个顶点的,0,、,1,分布而言，共有,2,8,=256,种不同的状态。尽管判断等值面将与哪些体元相交在原理上很容易理解，但是要根据这,256,种不同的情况求出每个体元中的等值面却是很繁琐的而且也容易出错。,可以利用两种不同的对称性将,256,种不同的情况简化为,15,种。,互补对称性,：如果将一个体元的顶点状态颠倒，即“,0”,变成“,1”,，“,1”,变成“,0”,，则等值面与体元中,8,个顶点之间的拓扑关系将不会改变，该体元与等值面的相交情况与原来一致，即新生成的等值面与原等值面是相同的。也就是说，大于等值面的点与小于等值面的点是可以相互替换的，因此，只要考虑,4,个以下（含,4,个）的顶点值大于,F,t,就够了。根据这种互补对称性，可将体元的模式由,256,种减少为,128,种。,Marching,Cubes(MC,),方法,旋转对称性,：如果某一模式的体元经过旋转后与另一模式的体元一致，即顶点位置及其状态值相同，那么这两种模式的体元可以合并为一种。根据这种旋转对称性，体元模式可以最终归纳为,15,种，见图,2,。其中第,0,种情况表示所有,8,个顶点的值均大于（或小于）,F,t,，因而该体元与等值面不相交。第一种情况表示有一个顶点的函数值大于（或小于）,F,t,，其余,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,是扫描线上位于多边形内的任一点，多边形三个顶点的光亮度分别为,I,1,，,I,2,和,I,3,。取,a,点的光亮度,I,a,为,I,1,和,I,2,的线性插值，,b,点的光亮度,I,b,为,I,1,和,I,3,的线性插值，,p,点的光亮度则为,I,a,和,I,b,的线性插值，即：,其中,u,v,t,称为插值参数,(,相当于以端点为原点归一化后的长度坐标,),。,采用,Gouraud,明暗处理不但可以克服用多边形表示曲面时光亮度的不连续现象，而且计算量也很小。事实上，由于线性插值可使用增量法进行计算，其运算量仅涉及一次加法运算。如在上例中，可沿扫描线从左至右的顺序计算,AB,区段上所有象素的光亮度。设,I,a,和,I,b,已经确定，,p,1,和,p,2,点是相邻两象素的坐标，,a,、,b,两点的插值参数之差为,t,，那么，不难发现,p,2,点光亮度,I,p,2,和,p,1,点光亮度,I,p,1,之间有下列关系：,由于,I,在同一扫描线上为常数，因此计算一相邻象素的光亮度仅需一次加法运算。这种增量方式的光亮度计算使,Gouraud,明暗处理广泛用于实时图形生成。,在,Gouraud,明暗处理中，计算多边形顶点的光亮度可采用,Phong,光照模型。,Marching,Cubes(MC,),方法,(4),用,MC,方法求等值面的算法流程,将三维离散规则数据分层读入内存；,扫描其中两层数据，逐个构造这两层之间的体元，每个体元中的,8,个顶点取自相邻的两层；,将体元各个顶点的值与给定的等值面值,F,t,进行比较，根据比较的结果进行分类，构造该体元的状态表；,根据状态表，查得与该状态值对应的等值面分布模式，确定将与等值面相交的体元边界；,通过线性插值，计算体元边界与等值面的交点坐标，按对应的模式将这些交点连接成三角形，构成该单元中的等值面片；,利用中心差分方法，求出体元各顶点处的梯度，再次通过线性插值方法，求出三角形各顶点处的法向；,根据各三角面片各顶点的坐标值及法向量绘制等值面图象。,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,三个方向均是线性变化的。如果点,P,1,，,P,2,为点,P,沿,y,轴在立方体两个面上的投影，,P,11,、,P,12,、,P,21,、,P,22,分别为,P,1,，,P,2,点沿,z,轴在立方体平面上的投影。设,V,为,y,轴上的坐标分量，,f,为函数值，那么，通过三次线性插值，可得：,(1),其中,P,1,，,P,2,两点的值可由,P,11,，,P,12,和,P,21,，,P,22,插值求得，而,P,11,、,P,12,、,P,21,、,P,22,四个点的值又可以由它们所在体元内的一条边上的两个顶点插值得到。这样，通过三次线性插值运算，就可以求得,P,(,x,y,z,),点的函数值，（,1,）式可具体展开为：,其中系数,a,i,(,i,=0,7),取决于体元,8,个顶点处的函数值，如果给定的等值面的值为,F,t,，那么，等值面就被定义为满足如下方程的点的集合,(2),改变,F,t,的值，就可以得到不同等值面的表达式。,由上述等值面方程可以方便地求出某等值面与体元边界面的交线方程。不失一般性，设某边界面所在平面的方程为,z,=,z,0,，代入方程式,(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,z,0,),的值。如果,f,(,x,y,z,0,),F,t,，则渐近线的交点应与数值大于,F,t,的一对顶点落在同一区域，如图6(a),所示，可连接,M,1,M,2,、,M,3,M,4,，否则渐近线交点与数值小于,F,t,的一对顶点落在同一区域，如图,6(b),所示，可连接,M,1,M,3,、,M,2,M,4,。在图,6,中，当,f,(,x,y,z,0,),F,t,时，对渐进线的交点标以正值，其对应的二义面称为正值二义面,(,记为,PAF),。当,f,(,x,y,z,0),F,t,时，对渐进线的交点标以负值，其对应的二义面称为负值二义面,(,记为,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,个四面体。与前述的方法一样，假定待求的等值面的值为,F,t,，如果四面体顶点的值大于（或等于）,F,t,，则将该顶点赋以“,+”,号；如果小于,F,t,，则将该顶点赋以“”号。,假设在四面体的边上数据呈线性变化，在考虑了“,+”,、“”号反号造成的对称情况后，对于每个四面体，等值面模式只有三种情况，如图,7,所示。如果,4,个顶点全为“,+”,或全为“”，等值面与该四面体无交点；如一个顶点为“,+”,，而另外,3,个顶点为“”，则该四面体中等值面是一个三角片；如有两个顶点为“,+”,，而另外,2,个顶点为“”，则该四面体中等值面是一个四边形，可分解为两个三角片。将各三角片拼接起来即可构成等值面，这就是,MT,方法的基本原理。,虽然在每一个四面体内，等值面的生成是由顶点函数值的分布情况唯一确定的，但是，对于一个立方体来说，却有两种不同的四面体剖分方式。不同的剖分方式将生成不同的等值面，即等值面的结果依赖于剖分方式。,另一方面，为了在相邻体元的公共面上不出现裂缝，必须保证在这个面上的剖分一致性，也就是说，四面体的剖分方式在一系列体元中是交替变化的。这样一来，三维数据内等值面的构造是与最初一个体元的剖分方式有关的。因此,MT,方法并不能消除等值面构造中的二义性，这仍然是一个有待解决的问题。,2,MT,方法中二义性的判别和消除,当一个立方体剖分为,5,个四面体时，在每一个四面体的6,条边中，有些是原有立方体的棱，而另一些则是立方体,6,个面上的对角线。经过仔细研究，在,5,个四面体的,30,条边中，只有,12,条边是原有立方体的棱，而其余,18,条则均为立方体面上的对角线。这就提出了一个问题，即当立方体每条棱上的函数值呈线性变化时，立方体每个面中对角线上的函数值是否也呈线性变化呢？如果不是，那么当该对角线两端点均为“”（或“”）时，就认为在该线段上没有交点，又是否能成立呢？,前面论述过，当体元每条棱上的函数值均呈线性变化时，体元内等值面与体元边界面的交线是由（,3,）式表示的一条双曲线。设体元中一个面所在的平面为,z,=,z,0,，该面上某一对顶点的坐标为,(,x,a,y,a,z,0,),及,(,x,b,y,b,z,0,),，则由该对顶点构成的对角线方程为,(5),将（,5,）式代入（,3,）式，经过整理后可知，沿对角线的函数值分布为一个二次函数，并可写成如下形式：,(6),其中,A,，,B,，,C,是由对角线端点坐标及体元的,8,个顶点的函数值决定的常数。既然沿对角线的函数值分布为二次函数，那么当对角线两端点均为“”（或“”）时，就不能简单地认为在该对角线上无交点，而需要求解（,6,）式才能得出结果。,于是，判断对应于阈值为,F,t,的等值面是否与该对角线相交，就需要判断方程式（,6,）在区间,0,，,1,内是否有解。,若,C0,，且，则方程,(6),式将有两个不同的解,t,1,和,t,2,。如果,t,1,和,t,2,都在区间,0,，,1,内，那么等值面与对角线有两个不同的交点，这是当对角线两端点的函数值为同号时的情况，是不能被忽略的。在这种情况下，等值面与体元对角线相交的多种可能性如图,8,所示。,图,8,等值面与体元对角线相交的多种可能性,图,8,（,a,）表明，只有一条双曲线通过体元的面并与对角线有两个交点，但此刻，该对角线两端点的函数值均为“,+”,。,图,8(b),和,(c),表示两条双曲线都通过该面，这是,MC,方法中的二义面。在图,8(b),中，两条渐近线的交点与为“,+”,的对角线两端点取异号，而在图,8(c),中，两条渐近线的交点与为“,+”,的对角线两端点取同号。在这两种情况下，根据判别式计算结果，该等值线均与对角线有两个交点。如果认为该对角线两端点的函数值均为“,+”,而忽略这两个交点，将导致等值线的错误连接（如图,8(d),所示）或等值线的连接不准确（如图,8(e),所示），而这正是传统的,MT,方法所存在的问题。,综上所述，在,MT,方法中判断四面体的一条边与等值面是否有交点及计算交点的算法可描述如下：,如果,E,1,E,2,是原体元的一条边,如果该边两端点所赋值异号，,则通过线性插值计算交点（等值点）并输出,否则，,没有交点,否则,如果两端点函数值同号而相应的判别式非负,则解一元二次方程式计算两个交点并输出落在两端点间的交点,如果两端点函数值异号,计算两交点，取落在两端点间的点为交点，并输出,舍去另一点,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),面点跟踪的相关性算法,当一个与等值面相交的体元剖分为小体元以后，需要继续检测哪些小体元与等值面相交。当体元数目较大时，逐个计算小体元顶点处的函数值，并且检测是否与等值面相交的计算量也较大。一般说来，与等值面相交的小体元总是相邻的，我们可以利用这一相关性来排除不必要的小体元检测计算。,