第34章等值线等值面的生成PPT讲稿.ppt

《第34章等值线等值面的生成PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第34章等值线等值面的生成PPT讲稿.ppt（61页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第34章等值线等值面的生成第1页，共61页，编辑于2022年，星期一网格序列法网格序列法 网网格格序序列列法法(grid sequence)的的基基本本思思想想是是按按网网格格单单元元的的排排列列次次序序，逐逐个个处处理理每每一一单单元元，寻寻找找每每一一单单元元内内相相应应的的等等值值线线段段，在在处处理理完完所所有有单单元元后后，就就自然生成了该网格中的等值线分布。自然生成了该网格中的等值线分布。规则网格数据等值线的生成规则网格数据等值线的生成 设设一一规规则则网网格格数数据据如如图图所所示示，网网格格线线是是相相互互正正交交的的，每每一一网网格格单单元元是是一一矩矩形形，其其中中四四个个

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

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

4、”，或或全全为为“”，则则网网格格单单元元与与值值为为Ft的等值线无交点，否则的等值线无交点，否则(3)对对于于两两个个顶顶点点分分别别为为“”、“”的的单单元元边边，可可用用线线性性插插值值计计算算等等值值线线在这条边上的交点。在这条边上的交点。如图所示，如图所示，(x0,y0)为为“”，(x0,y1)为为“”，则交点为，则交点为第3页，共61页，编辑于2022年，星期一网格序列法网格序列法 在在每每一一单单元元内内计计算算出出等等值值线线与与该该网网格格单单元元边边的的交交点点后后，利利用用这这些些交交点点，就就能能构构成成在在该该单单元元内内的的等等值值线线段段。为为了了正正确确地地连连

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

6、点为“”或或“”，共可求出两个交点，有一条等值线段，共可求出两个交点，有一条等值线段，如图如图3。第4页，共61页，编辑于2022年，星期一第5页，共61页，编辑于2022年，星期一网格序列法网格序列法(3)有有两两个个“”，两两个个“”顶顶点点的的情情况况，根根据据顶顶点点的的分分布布又又可可分分成下面两种情况：成下面两种情况：有有两两个个交交点点，即即两两个个“”或或两两个个“”的的顶顶点点位位于于同同一一条条单单元元边边上，等值线段的连接如图上，等值线段的连接如图4a所示。所示。有有4个个交交点点，即即“”、“”顶顶点点的的分分布布相相互互交交叉叉，这这时时的的连连接接在在规规定定了了函

7、函数数的的走走向向后后，可可确确定定P，R为为入入点点，S，Q为为出出点点，连连接接情情况况如如图图4b所示。所示。在在上上述述的的情情况况下下，如如果果不不规规定定等等值值线线的的走走向向，其其实实存存在在两两种种连连接接方方式式，见见图图5。在在实实际际情情况况中中，这这两两种种方方式式都都是是可可能能的的，这这种种二二义义性性的的主主要要原原因是在该单元内存在一马鞍点。因是在该单元内存在一马鞍点。第6页，共61页，编辑于2022年，星期一第7页，共61页，编辑于2022年，星期一第8页，共61页，编辑于2022年，星期一网格序列法网格序列法 如如何何从从中中选选择择一一种种正正确确的的连

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

9、”，则则取取图图5b的的连连接接方方式式。即即在在图图5a中中，表表示示单单元元中中部部为为“”，在在图图5b中中，表表示示单单元元中中部部为为“”。在在实实际际计计算算中中，为为简简化化计计算算，往往往往采采用用单单元对角线交点代替渐近线交点的计算。元对角线交点代替渐近线交点的计算。第9页，共61页，编辑于2022年，星期一单元剖分法单元剖分法 在在网网格格序序列列法法中中，提提出出了了解解决决矩矩形形单单元元内内等等值值线线的的生生成成算算法法，其其中中马马鞍鞍点点二二义义性性的的解解决决是是算算法法的的一一个个主主要要复复杂杂点点，除除此此之之外外人人们们还还提提出出了了单单元元剖剖分分

10、法法，该该方方法法与与矩矩形形单单元元法法相相比比，其其主主要要特特点点是是采采用用三三角角片片简简化化单单元元内内等等值值线线的的抽抽取取，无无需需再再进进行行马马鞍鞍点点的的判判定定，但处理的单元数是原来的四倍。但处理的单元数是原来的四倍。算算法法的的基基本本思思想想是是利利用用对对角角线线将将矩矩形形单单元元分分成成四四个个三三角角形形单单元元，见见图图6，求求出出中中心心点点的的函函数数值值，等等值值线线的的抽抽取取直直接接在在每每个个三三角角片片中中进进行行。由由于于每每一一个个三三角角片片至至多多只只包包含含一一条条等等值值线线，因因而而在在由由三三角角片片的的三三个个点点决决定定

11、的的平平面面内内，可可直直接接用用直直线线段段连接等值线。连接等值线。第10页，共61页，编辑于2022年，星期一单元剖分法单元剖分法 中心点函数值中心点函数值Fmid的计算可采用两种方式：的计算可采用两种方式：如有显式函数如有显式函数F(x,y)，则，则Fmid=F(xmid,ymid)；如如只只有有四四个个点点的的函函数数值值，无无法法求求显显式式函函数数形形式式，则则可可用用四四点的平均值代替点的平均值代替Fmid。图图7列列出出了了几几种种可可能能的的情情况况，可可以以看看出出，通通过过利利用用矩矩形形单单元元中中点点的的函函数数值值，等等值值线线的的精精度度提提高高了了，其其抽抽取取

12、过过程程也也相相对简单些。对简单些。第11页，共61页，编辑于2022年，星期一第12页，共61页，编辑于2022年，星期一第13页，共61页，编辑于2022年，星期一第第4 4章章 等值面的生成等值面的生成 所所谓谓等等值值面面是是指指空空间间中中的的一一个个曲曲面面，在在该该曲曲面面上上函函数数F(x,y,z)的的值值等等于于某某一一给给定定值值Ft，即即等等值值面面是是由由所所有有点点 SFt=(x,y,z)：F(x,y,z)=Ft组成的一个曲面。组成的一个曲面。等等值值面面技技术术在在可可视视化化中中应应用用很很广广，许许多多标标量量场场的的可可视视化化问问题题都都可可归归纳纳为为等等

13、值值面面的的抽抽取取和和绘绘制制，如如各各种种等等势势面面、等等位位面面、等等压压面面、等等温温面面等等。等等值值面面技技术术除除生生成成等等值值面面的的几几何何表表示示外外，还还包包括括显显示示技技术术，如如要要考考虑虑合合适适的的光光照照模模型型、解解决决等等值值面面的的相相互互遮遮挡挡等等。等值面的生成和显示也是可视化研究中的一个重要领域。等值面的生成和显示也是可视化研究中的一个重要领域。第14页，共61页，编辑于2022年，星期一一一 Cuberille方法方法(立方体方法立方体方法)Cuberrille等等值值面面方方法法又又称称Opaque Cube算算法法，最最初初由由Herma

14、n等等人人提提出出，后来又多次改进。算法主要分为两个步骤。后来又多次改进。算法主要分为两个步骤。(1)确定边界单元确定边界单元对对于于规规则则网网格格数数据据，其其网网格格单单元元可可看看成成是是正正六六面面体体单单元元，整整个个三三维维数数据据就就是是由由这这种种正正六六面面体体组组成成的的，这这种种组组成成三三维维图图象象的的基基本本正正六六面面体体单单元元称称为为体体元元。对对于于给给定定的的阈阈值值Ft，遍遍历历体体数数据据中中的的各各个个单单元元，将将组组成成体体元元8个个顶顶点点上上的的值值与与Ft进进行行比比较较，找找出出顶顶点点值值跨跨越越Ft的的所所有有体体元元，即即体体元元

15、中中有有的的顶顶点点值值大大于于阈阈值值，有有的的顶顶点点值值小小于于阈阈值值，因因此此体体元元内内包包含含等等值值面面片片，这就是边界单元。这就是边界单元。(2)绘绘制制各各边边界界单单元元的的6个个多多边边形形面面，即即将将等等值值面面看看成成是是由由各各单单元元的的六六个个外表面拼合而成。外表面拼合而成。第15页，共61页，编辑于2022年，星期一Cuberille方法方法(立方体方法立方体方法)每每个个单单元元均均为为一一正正六六面面体体，包包括括6个个多多边边形形面面。对对组组成成所所有有边边界界体体元元的的多多边边形形面面进进行行绘绘制制，即即可可产产生生最最终终的的图图象象结结果

16、果。在在绘绘制制多多边边形形过过程中应采用合适的光照模型和消隐技术。程中应采用合适的光照模型和消隐技术。如如果果在在具具有有硬硬件件深深度度缓缓存存(Z-buffer)功功能能的的计计算算机机上上运运行行立立方方体体方方法法，可可以以将将这这组组多多边边形形不不分分次次序序地地提提交交给给硬硬件件，由由硬硬件件完完成成消消除除隐隐藏藏面面的的任任务务。如如果果以以软软件件方方式式执执行行立立方方体体方方法法，在在算算法法中中必必须须考考虑虑多多边边形形的的遮遮挡挡问问题题。一一个个有有效效的的方方法法是是把把遍遍历历体体元元集集合合与与显显示示两两个个步步骤骤合合二二为为一一，遍遍历历体体元元

17、集集合合时时采采用用从从后后至至前前的的次次序序。发发现现一一个个边边界界体体元元，就就立立刻刻显显示示它它的的6个个面面。后后显显示示到到屏屏幕幕上上去去的的多多边边形形将将覆覆盖盖先先显显示示的的多多边边形形，这这样样就就达达到到了了消消除除隐隐藏面的目的，这就是画家算法的思想。藏面的目的，这就是画家算法的思想。第16页，共61页，编辑于2022年，星期一Cuberille方法方法(立方体方法立方体方法)Cuberrille算算法法的的主主要要优优点点是是简简单单易易行行，其其主主要要缺缺点点是是出出现现严严重重的的走走样样，显显示示的的图图象象给给人人一一种种“块块状状的的感感觉觉”，尤

18、尤其其在在物物体体边边界界处处锯锯齿齿形形走走样样特特别别明明显显，而而且且画画面面较较粗粗糙糙，不不能能很很好地显示对象的细节。好地显示对象的细节。立立方方体体法法的的另另一一个个缺缺点点是是面面的的重重叠叠冗冗余余问问题题。两两个个相相邻邻边边界界体体元元的的公公共共面面重重复复出出现现，实实际际上上它它们们都都不不会会出出现现在在显显示示画画面面上上，因因为为无无论论从从哪哪个个角角度度进进行行观观察察，它它们们都都会会被被这这两两个个体体元元的的其其它它面面遮遮挡挡。改改进进的的立立方方体体法法删删除除了了边边界界体体元元之之间间的的公公共共面面，减减少少了了显显示示过过程程需要处理的

19、多边形的数量。需要处理的多边形的数量。第17页，共61页，编辑于2022年，星期一二二 Marching Cubes(MC)方法方法 Marching Cubes（移移动动立立方方体体）方方法法是是由由W.E.Lorenson和和H.E.Cline在在1987年年提提出出来来的的。由由于于这这一一方方法法原原理理简简单单，易易于于实实现现，目目前前已已经经得得到到了了较较为为广广泛泛的的应应用用，成成为为三三维维数数据据等等值值面面生生成成的的经经典典算算法法，Marching Cubes算法又简称为算法又简称为MC算法。算法。1MC方法的基本原理方法的基本原理在在Marching Cubes

20、方方法法中中，假假定定原原始始数数据据是是离离散散的的三三维维空空间间规规则则数数据据，一一个个体体元元定定义义为为由由相相邻邻层层上上的的8个个顶顶点点组组成成的的一一个个长长方方体体。为为了了在在三三维维数数据据中中构构造造等等值值面面，应应先先给给定定所所求求等等值值面面的的值值，该该方方法法的的基基本本原原理理是是逐逐个个处处理理所所有有的的体体元元，将将体体元元各各顶顶点点处处的的值值与与给给定定的的阈阈值值进进行行比比较较，首首先先找找出出与与等等值值面面相相交交的的体体元元，然然后后通通过过插插值值求求等等值值面面与与体体元元棱棱边边的的交交点点，并并将将各各交交点点连连成成三三

21、角角形形来来构构成成等等值值面面片片，所所有有体体元元中中的的三三角角形形集集合合就就构构成成了了等等值值面面。由由于于这这一一方方法法是是逐逐个个处处理理所所有有的的体体元，因此被称为元，因此被称为Marching Cubes方法。方法。MC方法的主要步骤如下：方法的主要步骤如下：第18页，共61页，编辑于2022年，星期一Marching Cubes(MC)方法方法(1)确定包含等值面的体元及对应的等值面片模式确定包含等值面的体元及对应的等值面片模式一个体元由一个体元由8个数据点构成，这个数据点构成，这8个数据点分别位于该体元的个数据点分别位于该体元的8个顶点上。个顶点上。首首先先对对体体

22、元元的的8个个顶顶点点进进行行分分类类，判判定定是是位位于于等等值值面面之之外外，还还是是位位于于等等值值面面之内。再根据之内。再根据8个顶点的状态，确定等值面的模式。个顶点的状态，确定等值面的模式。设等值面的值为设等值面的值为Ft，顶点分类规则为：，顶点分类规则为：若某顶点的值若某顶点的值Ft，则定义该顶点位于等值面之外，记为，则定义该顶点位于等值面之外，记为“0”。若某顶点的值若某顶点的值Ft，则定义该顶点位于等值面之内，记为，则定义该顶点位于等值面之内，记为“1”。如如果果某某体体元元一一条条边边的的一一个个顶顶点点在在等等值值面面之之内内，而而另另一一个个顶顶点点在在等等值值面面之之外

23、外，那那么么，该该边边必必然然与与等等值值面面相相交交。根根据据这这一一原原理理就就可可以以判判断断所所求求等值面将与哪些体元相交，或者说将穿过哪些体元。等值面将与哪些体元相交，或者说将穿过哪些体元。第19页，共61页，编辑于2022年，星期一Marching Cubes(MC)方法方法 由由于于每每个个体体元元有有8个个顶顶点点，每每个个顶顶点点又又有有0、1两两种种状状态态，因因此此每每个个体体元元按按其其8个个顶顶点点的的0、1分分布布而而言言，共共有有28=256种种不不同同的的状状态态。尽尽管管判判断断等等值值面面将将与与哪哪些些体体元元相相交交在在原原理理上上很很容容易易理理解解，

24、但但是是要要根根据据这这256种种不不同的情况求出每个体元中的等值面却是很繁琐的，而且也容易出错。同的情况求出每个体元中的等值面却是很繁琐的，而且也容易出错。可以利用两种不同的对称性将可以利用两种不同的对称性将256种不同的情况简化为种不同的情况简化为15种。种。互互补补对对称称性性：如如果果将将一一个个体体元元的的顶顶点点状状态态颠颠倒倒，即即“0”变变成成“1”，“1”变变成成“0”，则则等等值值面面与与体体元元中中8个个顶顶点点之之间间的的拓拓扑扑关关系系将将不不会会改改变变，该该体体元元与与等等值值面面的的相相交交情情况况与与原原来来一一致致，即即新新生生成成的的等等值值面面与与原原等

25、等值值面面是是相相同同的的。也也就就是是说说，大大于于等等值值面面的的点点与与小小于于等等值值面面的的点点是是可可以以相相互互替替换换的的，因因此此，只只要要考考虑虑4个个以以下下（含含4个个）的的顶顶点点值值大大于于Ft就就够够了了。根根据据这这种种互互补补对对称称性性，可将体元的模式由可将体元的模式由256种减少为种减少为128种。种。第20页，共61页，编辑于2022年，星期一Marching Cubes(MC)方法方法 旋旋转转对对称称性性：如如果果某某一一模模式式的的体体元元经经过过旋旋转转后后与与另另一一模模式式的的体体元元一一致致，即即顶顶点点位位置置及及其其状状态态值值相相同同

26、，那那么么这这两两种种模模式式的的体体元元可可以以合合并并为为一一种种。根根据据这这种种旋旋转转对对称称性性，体体元元模模式式可可以以最最终终归归纳纳为为15种种，见见图图2。其其中中第第0种种情情况况表表示示所所有有8个个顶顶点点的的值值均均大大于于（或或小小于于）Ft，因因而而该该体体元元与与等等值值面面不不相相交交。第第一一种种情情况况表表示示有有一一个个顶顶点点的的函函数数值值大大于于（或或小小于于）Ft，其其余余7个个顶顶点点均均与与此此相相反反，因因而而该该体体元元内内的的等等值值面面将将是是一一个个三三角角面面片片。在在考考虑虑了了上上面面两两种种对对称称性性后后，这这一一种种情

27、情况况实实际际上上代代表表了了16种种情情况况。如如此此类类推推，图图2中中的的15种种模模式式反反映映了了一一个个体体元元中中8个个顶顶点点可可能能存存在在的的全全部部256种状态。种状态。第21页，共61页，编辑于2022年，星期一第22页，共61页，编辑于2022年，星期一在在实实现现时时，对对一一个个体体元元可可按按照照它它的的8个个顶顶点点的的状状态态构构造造一一个个一一字字节节（8位位）的的状状态态表表，如如图图3所所示示，其其中中的的每每一一位位表表示示该该体体元元中中一一个个顶顶点点的的0或或1状状态态，根根据据这这个个状状态态表表就就可可判判断断出出当当前前体体元元属属于于哪

28、哪一一种种模模式式、等等值值面面将将与与哪哪一条边相交以及体元内三角面片的连接方式。一条边相交以及体元内三角面片的连接方式。第23页，共61页，编辑于2022年，星期一Marching Cubes(MC)方法方法(2)计算等值面与体元边界的交点，并连接成三角形计算等值面与体元边界的交点，并连接成三角形当当三三维维离离散散数数据据的的密密度度较较高高，即即每每个个体体元元很很小小时时，可可以以假假定定函函数数值值沿沿体体元元边边界界呈呈线线性性变变化化。因因此此，等等值值面面与与体体元元边边界界的的交交点点可可以以通通过过该该边边两两端端点点函函数数值值的线性插值求出，公式为：的线性插值求出，公

29、式为：求求出出了了等等值值面面与与体体元元边边界界的的交交点点以以后后，就就可可以以按按对对应应的的模模式式将将这这些些交交点点连连接接成三角形，构成该单元中的等值面片。成三角形，构成该单元中的等值面片。第24页，共61页，编辑于2022年，星期一Marching Cubes(MC)方法方法(3)计算等值面的法向计算等值面的法向为为了了绘绘制制等等值值面面的的真真实实感感图图象象，还还必必须须给给出出构构成成等等值值面面的的各各三三角角面面片片的的法法向向。对对于于等等值值面面上上的的每每一一点点，沿沿该该面面切切线线方方向向的的梯梯度度分分量量应应该该是是零零，因因此此该该点点的的梯梯度度矢

30、矢量量的的方方向向就就代代表表了了等等值值面面的的法法向向。MC方方法法就就是是利利用用这这一一原原理理来来计计算算三角面片的法向。即三角面片的法向。即对对于于三三维维规规则则网网格格数数据据，可可以以直直接接采采用用中中心心差差分分计计算算体体元元各各顶顶点点处处的的梯梯度度，公式为：公式为：第25页，共61页，编辑于2022年，星期一三三角角形形顶顶点点处处的的法法向向量量可可由由体体元元边边界界两两端端点点处处的的梯梯度度再再通通过过线线性性插插值值求求得得。在在实实际际绘绘制制等等值值面面时时，为为了了消消除除各各三三角角面面片片之之间间明明暗暗的的不不连连续续变变化化，只只要要给给出

31、出三三角角面面片片各各顶顶点点处处的的法法向向并并采采用用哥哥罗罗得得(Gouraud)模模型型绘绘制制各各个个三三角角面面片即可。片即可。在在计计算算机机图图形形学学中中，光光滑滑的的曲曲面面常常用用多多边边形形来来逼逼近近，这这是是因因为为处处理理平平面面比比处处理理曲曲面面容容易易得得多多。例例如如，为为了了表表示示一一个个磨磨光光的的立立方方体体的的顶顶角角，可可使使用用7个个平平面面片片来来近近似似。但但是是，若若单单纯纯使使用用平平面面来来绘绘制制这这种种近近似似表表面面，生生成成的的图图形形将将失失去去原原有有曲曲面面的的光光滑滑性性，而而呈呈现现多多面面体体状状。这这是是由由于

32、于平平面面上上所所有有点点的的法法向向相相同同，不不同同平平面面块块之之间间存存在在不不连连续续的的法法向向量量变变化化，从从而而引引起起不不连连续续的光亮度跳跃。的光亮度跳跃。如如何何能能以以较较少少的的计计算算量量来来解解决决上上述述问问题题呢呢?最最简简单单的的方方法法就就是是Gouraud明明暗暗处处理理技技术术。Gouraud明明暗暗处处理理的的思思想想是是对对离离散散的的光光亮亮度度作作双双线线性性插插值值以以获获得得连连续续的的光光亮亮度度函函数数。具具体体做做法法是是：先先计计算算出出多多边边形形顶顶点点处处的的光光亮亮度度值值，把把它它们们作作为为曲曲面面光光亮亮度度的的采采

33、样样点点，然然后后根根据据多多边边形形顶顶点点处的光亮度值进行插值求多边形内任一点的光亮度。处的光亮度值进行插值求多边形内任一点的光亮度。第26页，共61页，编辑于2022年，星期一若若采采用用扫扫描描线线绘绘制制算算法法，则则可可沿沿当当前前扫扫描描线线进进行行双双线线性性插插值值，这这是是一一种种简简便便易易行行的的插插值值方方法法。即即先先用用多多边边形形顶顶点点的的光光亮亮度度值值由由线线性性插插值值求求出出当当前前扫扫描描线线与与多多边边形形交交点点处处的的光光亮亮度度，然然后后根根据据交交点点的的光光亮亮度度值值再再通通过过线线性性插插值值求求出出扫扫描描线线上上位位于于多多边边形

34、形内内每每一一象象素素点点的的光光亮亮度度值值。图图4(a)显显示示一一扫扫描描线线与与多多边边形形相相交交，交交点点为为a点点和和b点点，p是是扫扫描描线线上上位位于于多多边边形形内内的的任任一一点点，多多边边形形三三个个顶顶点点的的光光亮亮度度分分别别为为I1，I2和和I3。取取a点点的的光光亮亮度度Ia为为I1和和I2的的线线性性插插值值，b点点的的光光亮亮度度Ib为为I1和和I3的的线线性性插插值值，p点点的的光光亮亮度度则则为为Ia和和Ib的的线线性插值，即：性插值，即：其中其中u,v,t称为插值参数称为插值参数(相当于以端点为原点归一化后的长度坐标相当于以端点为原点归一化后的长度坐

35、标)。第27页，共61页，编辑于2022年，星期一采采用用Gouraud明明暗暗处处理理不不但但可可以以克克服服用用多多边边形形表表示示曲曲面面时时光光亮亮度度的的不不连连续续现现象象，而而且且计计算算量量也也很很小小。事事实实上上，由由于于线线性性插插值值可可使使用用增增量量法法进进行行计计算算，其其运运算算量量仅仅涉涉及及一一次次加加法法运运算算。如如在在上上例例中中，可可沿沿扫扫描描线线从从左左至至右右的的顺顺序序计计算算AB区区段段上上所所有有象象素素的的光光亮亮度度。设设Ia和和Ib已已经经确确定定，p1和和p2点点是是相相邻邻两两象象素素的的坐坐标标，a、b两两点点的的插插值值参参

36、数数之之差差为为 t，那么，不难发现那么，不难发现p2点光亮度点光亮度Ip2和和p1点光亮度点光亮度Ip1之间有下列关系：之间有下列关系：由由于于 I在在同同一一扫扫描描线线上上为为常常数数，因因此此计计算算一一相相邻邻象象素素的的光光亮亮度度仅仅需需一一次次加加法法运运算算。这这种种增增量量方方式式的的光光亮亮度度计计算算使使Gouraud明明暗暗处处理理广广泛泛用用于于实实时时图形生成。图形生成。在在Gouraud明明暗暗处处理理中中，计计算算多多边边形形顶顶点点的的光光亮亮度度可可采采用用Phong光光照照模型。模型。第28页，共61页，编辑于2022年，星期一第29页，共61页，编辑于

37、2022年，星期一Marching Cubes(MC)方法方法(4)用用MC方法求等值面的算法流程方法求等值面的算法流程 将三维离散规则数据分层读入内存；将三维离散规则数据分层读入内存；扫扫描描其其中中两两层层数数据据，逐逐个个构构造造这这两两层层之之间间的的体体元元，每每个个体体元元中中的的8个顶点取自相邻的两层；个顶点取自相邻的两层；将将体体元元各各个个顶顶点点的的值值与与给给定定的的等等值值面面值值Ft进进行行比比较较，根根据据比比较较的的结结果进行分类，构造该体元的状态表；果进行分类，构造该体元的状态表；根根据据状状态态表表，查查得得与与该该状状态态值值对对应应的的等等值值面面分分布布

38、模模式式，确确定定将将与与等等值值面面相相交的体元边界；交的体元边界；通通过过线线性性插插值值，计计算算体体元元边边界界与与等等值值面面的的交交点点坐坐标标，按按对对应应的的模模式式将这些交点连接成三角形，构成该单元中的等值面片；将这些交点连接成三角形，构成该单元中的等值面片；利利用用中中心心差差分分方方法法，求求出出体体元元各各顶顶点点处处的的梯梯度度，再再次次通通过过线线性性插插值值方法，求出三角形各顶点处的法向；方法，求出三角形各顶点处的法向；根据各三角面片各顶点的坐标值及法向量绘制等值面图象。根据各三角面片各顶点的坐标值及法向量绘制等值面图象。第30页，共61页，编辑于2022年，星期

39、一Marching Cubes(MC)方法方法 2MC方法的加速算法方法的加速算法Marching Cube方方法法是是逐逐个个单单元元地地检检测测是是否否存存在在等等值值面面，还还要要计计算算等等值值面面与与体体元元边边界界的的交交点点，再再由由标标准准的的连连接接模模式式将将各各个个交交点点连连接接成成等等值值面面片片。事事实实上上，据据研研究究，真真正正与与等等值值面面相相交交的的体体元元占占总总数数据据量量很很小小的的一一部部分分（至至多多10%左左右右），计计算算过过程程中中30-70%的的时时间间用用在在了了空空体体元元的的检检测测上上，从从加加快快Marching Cube方方法

40、法的的角角度度出出发发，有有必必要要研研究究一一种种快快速速有有效效的的空空间间数数据据的的遍遍历历方方法法和和相相应应的的数数据据表表达达形形式式，以以加加速速对对空空体体元元的的检检测测和和排排除除。另另一一方方面面，对对于于一一条条与与等等值值面面相相交交的的体体元元的的边边，它它同同时时被被四四个个单单元元共共用用，这这表表明明在在这这四四个个单单元元内内求求等等值值面面时时都都要要用用到到这这个个交交点点，保保存存该该交交点点的的位位置置及法向量对于加速算法具有重要意义。及法向量对于加速算法具有重要意义。第31页，共61页，编辑于2022年，星期一对对于于规规则则网网格格数数据据，其

41、其体体元元是是一一个个六六面面体体单单元元，若若采采用用空空间间八八叉叉树树来来表表示示这这种体数据，则可以加快运算速度。种体数据，则可以加快运算速度。Marching Cube方方法法的的另另一一个个重重要要问问题题是是抽抽取取的的等等值值面面三三角角片片数数量量巨巨大大，有有时时一一个个体体元元可可以以生生成成多多达达12个个三三角角片片，当当三三维维数数据据的的数数据据量量很很大大时时，三三角角片片的的数数量量也也非非常常大大。这这给给等等值值面面的的绘绘制制和和交交互互操操作作带带来来很很大大困困难难。Schroeder提提出出了了在在不不影影响响图图形形质质量量的的情情况况下下，通通

42、过过对对原原等等值值面面三三角角片片网网重重排排结结点点，合合并并简简化化，生生成成最最优优化化意意义义下下的的Delaunay三三角角化化网网，可可以以有有效效加加快快图图形形的的实实时时显显示示，这这对对于于Marching Cube方方法法的的实实用用是是非非常常有有意意义义的。的。第32页，共61页，编辑于2022年，星期一Marching Cubes(MC)方法方法 3MC方法存在的问题方法存在的问题(1)MC方法构造的三角面片是三维等值面的近似表示方法构造的三角面片是三维等值面的近似表示首首先先，在在MC方方法法中中，等等值值面面与与体体元元边边界界的的交交点点是是基基于于函函数数

43、值值在在体体元元边边界界上上呈呈线线性性变变化化这这一一假假设设而而求求出出的的。当当数数据据密密度度高高、体体元元很很小小时时，这这一一假假设设接接近近于于实实际际情情况况。但但是是，在在稀稀疏疏数数据据中中，体体元元较较大大，如如果果仍仍然然认认为为函函数数值值在在体体元元边边界界上上呈呈线线性性变变化化，将将会会产产生生较较大大误误差差。这这时时，需需要要根根据据不不同同的的具具体体情情况况对对函函数数值值沿沿体体元元边边界界的的变变化化作作其其它它适适当当的的假假设设，才才能能较较准准确确地地求求出出等值面。等值面。其其次次，即即使使函函数数值值沿沿体体元元边边界界作作线线性性变变化化

44、这这一一假假设设符符合合实实际际，那那么么通通过过线线性性插插值值求求得得的的交交点点位位置置是是准准确确的的，但但是是，将将体体元元中中同同一一个个面面上上两两条条相相邻邻边边上的交点简单地用直线连接起来也是一种近似上的交点简单地用直线连接起来也是一种近似(如下图所示如下图所示)。第33页，共61页，编辑于2022年，星期一第34页，共61页，编辑于2022年，星期一为为了了说说明明这这一一问问题题，需需要要引引入入当当体体元元各各边边界界上上函函数数值值均均为为线线性性变变化化时时的的等等值值面面模模型型。如如图图3.5所所示示，P(x,y,z)为为小小体体元元中中的的任任意意点点，体体元

45、元中中的的数数据据沿沿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四四个个点点的的值值又又可可以以由由它它们们所所在在体体元元内内的的一一条

46、条边边上上的的两两个个顶顶点点插插值值得得到到。这这样样，通通过过三三次次线线性性插插值值运运算算，就就可可以以求求得得P(x,y,z)点点的的函函数数值值，（1）式式可可具体展开为：具体展开为：第35页，共61页，编辑于2022年，星期一其其中中系系数数ai(i=0,7)取取决决于于体体元元8个个顶顶点点处处的的函函数数值值，如如果果给给定定的的等等值面的值为值面的值为Ft，那么，等值面就被定义为满足如下方程的点的集合，那么，等值面就被定义为满足如下方程的点的集合 (2)改变改变Ft的值，就可以得到不同等值面的表达式。的值，就可以得到不同等值面的表达式。由由上上述述等等值值面面方方程程可可以

47、以方方便便地地求求出出某某等等值值面面与与体体元元边边界界面面的的交交线线方方程程。不不失一般性，设某边界面所在平面的方程为失一般性，设某边界面所在平面的方程为z=z0，代入方程式，代入方程式(2)，可得，可得 (3)上式可进一步表示为：上式可进一步表示为：第36页，共61页，编辑于2022年，星期一 （4）显显然然，上上述述方方程程表表示示的的是是一一条条双双曲曲线线，即即等等值值面面与与体体元元中中某某一一个个面面的的交交线线是是一一条条双双曲曲线线或或其其中中的的一一支支。如如果果用用一一条条直直线线来来表表示示这这条条双双曲曲线线，则则会会引引起起误误差差（如如图图所所示示）。如如果果

48、体体元元很很小小，这这一一误误差差是是可可以以忽忽略略不不记记的的。对对于于稀稀疏疏的的三三维维数数据据，这这种种近近似似引引起起的的误误差差是是难难以以接接受受的的，可可通通过过自自适适应应剖剖分分算算法法将将三三角角形形按按给给定定的的逼逼近近精精度度递递归归地地分分成成子子三三角角形形，使使这这些些子子三三角角形形的的顶顶点点满满足足方方程程(3)，且且子子三三角角形形与与等等值面的最大距离小于给定的容差。值面的最大距离小于给定的容差。第37页，共61页，编辑于2022年，星期一Marching Cubes(MC)方法方法(2)连接方式上的二义性连接方式上的二义性Marching Cub

49、es方方法法可可以以看看成成是是二二维维等等值值线线网网格格序序列列法法在在三三维维空空间间中中的的推推广广。在在网网格格序序列列法法中中，如如果果矩矩形形网网格格单单元元4个个顶顶点点中中有有两两个个顶顶点点的的值值大大于于等等值值线线的的值值，另另两两个个顶顶点点的的值值小小于于等等值值线线的的值值，且且这这两两个个顶顶点点交交叉叉分分布布，那那么么等等值值线线的的连连接接就就出出现现二二义义性性。同同理理，在在Marching Cubes方方法法中中，如如果果正正六六面面体体单单元元的的6个个矩矩形形表表面面中中出出现现与与此此相相同同的的情情形形，那那么么该该正正六六面面体体单单元元中

50、中的的等等值值面面连连接接必必然然会会出出现现二二义义性性，这这样样的的面面称称为为二二义义性性面面，包包含含1个个以以上上的的二二义义性性面面的的体体元元，即即为为具具有有二二义义性性的的体体元元，如如下下图图所所示示。事事实实上上，在在Marching Cubes方方法法的的15种种模模式式中中，第第3、6、7、10、12、13等等6种种情况是具有二义性的。情况是具有二义性的。第38页，共61页，编辑于2022年，星期一第39页，共61页，编辑于2022年，星期一Marching Cubes(MC)方法方法 4用双曲线渐近线方法判别和消除二义性用双曲线渐近线方法判别和消除二义性MC方方法法