论文：如何实现三维表面建模

PAGE

分类号密级

UDC编号

硕士学位论文

论文题目如何实现三维表面建模

学科、专业计算机科学与技术

研究生姓名

导师姓名及

专业技术职务副教授

MSTHESIS

原创性声明

本人声明，所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明。

作者签名：日期：年月日

学位论文版权使用授权书

作者签名：导师签名日期年月日

[3]

。体绘制认为每一个体素都具有一定的属性，比如透明度、光亮度，然后根据光照模型和体素介质属性分配一定的不透明度和光强度，并在视线方向上积分计算，最后将计算得出的半透明图像在屏幕上显示出来，处理过程如图1-1所示。

图1-1体绘制方法处理过程

体数据的显示方法，从本质上来说都是利用光线投射的理论，可分为两种显示过程。第一种体绘制方法以空间图像为序。这种方法以像素顺序进行，即处理完一个像素后接着处理另一个像素。第二种方法是以空间对象为序。这种方法以体素顺序进行，即处理完当前体素后接着处理下一个体素。此方法需要考虑体素遍历时的顺序，从后往前和从前往后的结合顺序是有所不同的

REF_Ref259393861\r\h

[4]

。

光线投射算法就是一个典型的以空间图像为序的算法

REF_Ref259393560\r\h

[3]

。该算法的基本思想是：首先屏幕上的每一个像素点发出一条射线，此射线将横穿三维数据场的体素矩阵，接着在这条射线上进行等距采样，根据采样点最近数据点的不透明度和颜色值对采样点进行插值，求解出采样点的不透明度和颜色值；然后，根据不同的图像合成方式，对采样点的不透明度和颜色值进行合成；最后，对光线上的所有采样点都插值完后，屏幕对应像素点的颜色值和亮度值就已经计算出来了。根据上述步骤，当屏幕所有的像素点值都计算完时，就得到了整个体数据的完整图像，如图1-2所示。

（a）三维视图（b）顶视图

图1-2体的光线投射

以空间对象为序进行体绘制的方法叫做单元投影算法

REF_Ref259394068\r\h

[4]

。该方法首先需给出投影方向和投影平面，然后把所有体素依一定的顺序投影到图像平面，并计算出每个数据点对屏幕像素点的贡献度，得到最终的图像。目前有多种投影算法，如Splatting算法

REF_Ref259394385\r\h

[6]

和Shear-Warp算法等

REF_Ref259394478\r\h

[7]

。

在实际应用中，特别是在医学图像诊断中，光线投射算法速度较慢。许多学者提出了各种加速体绘制方法

REF_Ref261183657\r\h

[8]

REF_Ref261183988\r\h

[9]

，能在较短的时间内得到了较好的体绘制图像质量。因而到目前为止，该算法仍是一种使用较为广泛的体绘制方法

REF_Ref259394509\r\h

[10]

REF_Ref259394511\r\h

[11]

。

1.2.2面绘制方法

面绘制是从原始数据中重建中间的几何图元，然后用真实感图形学技术对几何图元进行绘制。面绘制可分为两种：（1）基于轮廓线拼接（切片级）的面绘制；（2）基于等值面（体素级）的面绘制。

1、基于轮廓线拼接（切片级）的面绘制

基于轮廓线拼接的面绘制是最早被用来进行面绘制的方法

REF_Ref259394677\r\h

[12]

。Keppel于1975年提出了最早的轮廓线法思想。该思想采用三角面片来覆盖物体的表面，并以面片所围成的最大体积作为约束条件，实现物体的表面建模

REF_Ref259394696\r\h

[13]

。该方法成为了三维表面建模算法的基础，随后有许多学者对该方法进行了研究和改进

REF_Ref259394712\r\h

[14]

REF_Ref259394715\r\h

[15]

。

由于基于轮廓线拼接的面绘制方法约束性不强，导致它们具有很大的随意性。在轮廓线形态复杂多变，轮廓线位置、方向和形状差异较大的情况下，重建的效果不理想，虽然许多学者作了大量的研究，但是仍然没有从根本上得到完全解决。轮廓对应、拼接和分支问题的具体的原理将在本文第二章进行详细的阐述。

2、基于等值面（体素级）的面绘制

基于等值面的面绘制思想是：首先依次对每个体素进行处理，确定出其所包含的等值面片；然后将所有的体素的面片连接起来形成整个物体表面。所谓等值面就是指如果把体数据看成是某个空间区域内关于某种物理属性的采样集合，通过插值来估计非采样点和邻近采样点上的采样值，则该空间区域内所有具有某一个属性的点集合定义成为一个或多个曲面，称之为等值面。

近年来，基于等值面的面绘制得到了广泛的关注,并取得了许多重要的成果。Herman等

REF_Ref259394741\r\h

[16]

是最早提出立方体方法的等值面绘制方法。它采用边界体素的六个面来拟合等值面。Cline等

REF_Ref259433370\r\h

[17]

提出剖分立方体的等值面构造方法。该方法采用点来构造等值面，但只有在点比较密集时，才呈现“实体”模型。Lorenson等

REF_Ref259394760\r\h

[18]

在1987年提出了一种基于体素的典型面绘制算法——MC算法。目前MC算法已成为最流行的等值面构造算法，它对科学计算可视化产生了巨大的影响。但是，MC算法同样还存在着缺陷，主要表现在等值面的拓扑结构错误

REF_Ref259394778\r\h

[19]

、绘制精度不高

REF_Ref261181922\r\h

[20]

REF_Ref259394793\r\h

[21]

、占用存储空间大和处理速度较慢

REF_Ref259394809\r\h

[22]

REF_Ref261035697\r\h

[23]

等方面。J.Durst首先提出了MC算法中的二义性问题。为了克服MC的二义性问题，人们提出了MarchingTetrahedra算法

REF_Ref259394843\r\h

[24]

。由于MC算法非常具有代表性，因此在科学计算可视化的各种杂志和会议上，还经常有关于MC算法的改进算法

REF_Ref259394857\r\h

[25]

。

基于体素级和基于切片级的建模方法分别适用于不同的原始数据。体素级面绘制会产生大量的小面片，占用额外空间，给图形的显示和更新带来麻烦。因此，如何减少冗余的小面片是一个值得研究的课题

REF_Ref259394881\r\h

[26]

。切片级建模相对于体素级而言压缩了大量冗余的数据，但是存在轮廓线拼接的多义性问题。在分支问题上，该问题尤为明显。

由于切片级的面绘制存在着轮廓对应、轮廓拼接、轮廓分支等问题，其中轮廓对应和分支问题是难点问题。现有的轮廓线拼接算法在分支问题上只侧重于解决一条轮廓线与多条轮廓线间的正确拼接问题，而在实际应用中往往并不是这么简单，这使得这些算法在轮廓线的拼接上存在着很大缺陷。为此，M.W.Jones、张勇等人将此问题转化为体数据中的等值面构造问题

REF_Ref261172371\r\h

[27]

REF_Ref261175032\r\h

[28]

。

除了上述两种主要方法，有些学者还提出了用数学方法来解决表面重建问题

REF_Ref259432922\r\h

[29]

。这些方法大多以表面上所有点的曲率之和最小为约束条件，用偏微分方法来表示表面，并求出微分方程的解。这种方法计算量大，并且最后还是要通过体数据来进行表面显示。

1.3主要研究内容

针对研究现状，本文主要研究了基于断层数据序列构建三维几何模型的表面建模方法及其实现。研究和实验中的数据均为危机矿山项目中的数据。

表面建模算法的研究进展很大程度上决定了三维表面建模系统的发展以及功能的开发，是实现表面重建的关键。研究选择一种最佳的表面建模算法，对表面建模有着至关重要的作用。本文通过研究现阶段一些主要的表面建模算法，分析各算法的优缺点，并根据当前项目以及应用需要，选择最适合的表面建模算法。

MC算法是被证明了的基于等值面面绘制的经典算法之一。为了实现最好的面绘制效果，本文通过对MC算法原理和算法流程的研究，从克服该算法的缺陷以及提高表面绘制质量和速度着手，提出一种新的表面建模算法——MP算法，以实现最佳的绘制效果。MP算法通过对轮廓线进行体数据的构造，并抽取体数据中等值面，实现物体表面的生成。同时为了满足用户的不同应用目的，以及对绘制质量和绘制速度的具体要求，本文从MP算法的关键步骤入手，提供了多种表面生成模式供用户选择，以最大程度地满足表面建模的需求。

在等值面与轮廓线的逼近精度问题上，本文提出了一种分类处理轮廓线的渐近算法。该算法将基于轮廓线拼接算法引入到基于等值面的面绘制算法中，利用基于轮廓线拼接算法的优点，将原轮廓线进行平移，然后在等值轮廓线与原轮廓线之间采用一种轮廓线“分段对应拼接”方法，使重建出的物体表面与轮廓线达到完全吻合。同时，该算法在投影轮廓线之间采用基于等值面的面绘制算法进行表面建模，实现整个物体的表面生成，取得了较好的效果。

基于上述研究，本文最终实现了一个高质量的表面建模子系统。此表面建模子系统作为危机矿山三维信息评价系统的一部分，主要实现矿山三维断层数据序列的读取、剖面编辑、体数据的构造、等值面的生成，以及用户对表面模型进行交互操作等功能。

1.4论文的组织结构

本文共分为六章，分别为绪论、三维表面建模技术、基于MP的三维建模方法、分类处理轮廓线的渐近算法、模型可视化与三维表面建模系统的实现、结论与展望。

第一章是绪论。该章首先介绍了三维表面建模技术的研究背景和重要意义，然后分析了三维建模技术在国内外的研究现状与水平，最后给出了本课题的研究内容和文章的组织结构。

第二章研究了三维表面建模技术。该章详细地研究了两类主要的三维表面建模方法，即基于轮廓线连接的表面建模方法和基于等值面面绘制的表面建模方法。文章分别研究了它们的方法思路、优缺点和适用情况，其中对MC算法进行了重点研究，包括该算法的基本原理和实现步骤。

第三章介绍本文提出的MP算法。该章根据MC算法的基本原理，结合当前项目中的具体应用要求，提出了基于MP的三维表面建模算法。本章重点介绍了MP算法的基本思想及步骤，并对MP算法进行了算法分析和实验验证。

第四章研究了分类处理轮廓线的渐近算法。该章在当前项目应用背景的基础上，提出了分类处理轮廓线的渐近算法，主要介绍了该算法的关键步骤，分析了算法的时间复杂性，最后本章还对分类处理轮廓线的渐近算法进行了实验验证。

第五章首先简要地研究了OpenGL实现模型可视化的基本原理，其次介绍了本文设计的一个表面建模子系统，并用本文算法实现了某矿体的三维空间模型，最后给出了效果图。

第六章是全文的最后一章，该章首先对自己的工作进行了全面的总结，然后对自己将来工作的研究和改进进行了讨论。

硕士学位论文第二章三维表面建模技术

PAGE

109

第二章三维表面建模技术

三维表面建模技术有几种比较典型的方法，通常主要可分为两种：（1）基于轮廓线拼接的建模方法；（2）基于体素级的建模方法。除了这两种方法外，还有一些其他的建模技术

REF_Ref259432945\r\h

[30]

REF_Ref261175206\r\h

[31]

，这些方法适用于不同的应用领域。本章首先介绍了基于轮廓线拼接的建模方法，分析了该方法的主要难题，然后介绍了基于体素级的建模方法，并着重研究了MC的表面建模方法，最后还简单介绍了一些其他建模技术。

2.1基于轮廓线拼接的建模方法

2.1.1基本原理

基于轮廓线拼接的建模方法基本原理是首先找出相邻断层剖面上相应的轮廓线及其对应点，然后用三角片连接起来，最后绘制出这些三角片。该方法可以看成是对规则的离散采样点进行表面建模的问题。如图2-1所示，该算法通常可分解为四个基本问题：（1）轮廓对应；（2）轮廓拼接；（3）轮廓分支；（4）表面拟合。

图2-1基于轮廓线拼接的表面重建问题示意图

2.1.2基于轮廓线拼接的主要难题

1、轮廓对应问题

轮廓线对应问题发生在相邻层剖面上或其中一个剖面上有多条轮廓线的场合。在实际应用中，这是经常会碰到情形。要解决该问题，需解决轮廓线之间的对应关系问题，也就是要确定一个剖面上的哪条轮廓线与另一个剖面的哪条轮廓线进行连接。该问题在轮廓线错位严重且形状相似度很小的情况下，更加难以解决。现常用的方法有轮廓覆盖法和基于全局的最小生成树法等。

基于轮廓覆盖法的轮廓对应只是一种局部判断准则，该准则通过对相邻剖面上轮廓线包围盒重叠大小的计算，来进行轮廓线对应关系的判定

REF_Ref259432970\r\h

[32]

。当轮廓线间的距离较远或形态差异比较大时，该方法不能可靠、准确地判断轮廓线的对应关系，这时需要综合考虑整个轮廓线组。

Meyers提出采用外接椭圆近似代表轮廓，用多边形近似表示凹轮廓，由此建立一个全部轮廓线的无向图

REF_Ref259432995\r\h

[33]

。在无向图中，每条轮廓线用节点来表示，若两条轮廓线之间是对应的，那么在图中将会有一条对应边。因此，可通过无向图的最小生成树计算来获得轮廓线之间的对应关系。最小生成树方法考虑了全局信息，能全面考虑对轮廓线的对应关系，获得了比较准确的结果。

2、轮廓拼接问题

用三角面片或者多边形构造通过相邻剖面上对应轮廓的表面的过程称为轮廓拼接

REF_Ref259433031\r\h

[34]

。该问题需要确定轮廓线上点的对应关系，并利用三角面片或多边形来表示轮廓间的物体表面。常用的拼接方法有：圆环图方法的轮廓拼接和轮廓匹配方法的轮廓拼接。

假设、为两个待进行拼接的对应轮廓，其中、上的点序列分别为：，，其中，。图2-2（a）为m=6，n=7个顶点的轮廓。连接同一轮廓上的两个相邻点所得到的边称作轮廓段，而连接不同轮廓上的两个点所得到的边称作跨段。建立一个图，用结点表示跨段，当两个跨段有一个公共点时，用弧把这两个跨段所对应的结点连接起来，这样所得到的图称之为圆环图，如图2-2（b）。

（a）轮廓拼接图（b）圆环图

图2-2基于圆环图的轮廓拼接

H.Fuchs提出了一个可接受表面的定义形式

REF_Ref259433045\r\h

[35]

：

（1）任意一条轮廓段能且仅能存在于一个三角面片中。因此，可以得出结论：若两轮廓线的轮廓段数分别为m、n，那么正确的三维物体表面应该有m+n个三角面片组成；

（2）如果一条跨段为某一个三角面片的左跨段，那么该跨段只能作为另一个三角面片的右跨段。

对于图2-2中的圆环图，如果没有任何条件加以约束，圆环图中将存在着很多通路。如果给圆环图的每条弧赋予一个权值（其中权值是对弧所表示的三角面片的某个度量，如跨段长度、面积等），那么一个环的费用就可以用该环上的所有弧的权值之和来表示。寻找一个环在某个度量下的最优解就是要在圆环图中搜索出某个环，并使它的费用最大或最小。目前，已有的准则有体积最大

REF_Ref259394696\r\h

[13]

、表面积最小

REF_Ref259433078\r\h

[36]

、跨度长度之和最小

REF_Ref259433093\r\h

[37]

或者方向一致

REF_Ref259433103\r\h

[38]

，即轮廓点匹配方向最大程度地与质心匹配方向一致。

基于轮廓匹配的轮廓拼接方法的基本思想是对预先给定的两条对应轮廓线，查找其中一条轮廓线上点与另一条轮廓线上点的对应关系。目前，弹性匹配

REF_Ref259433122\r\h

[39]

是解决形变匹配的有效方法之一。Burr

REF_Ref259433137\r\h

[40]

在弹性匹配算法中使用了动态协作模型模拟弹性模型实现非刚体的匹配。为克服弹性匹配方法存在的计算复杂和内部制约力不强的缺点，文献

REF_Ref259433152\r\h

[41]

提出了一种基于线性弹性模型的形变轮廓匹配方法。

当相邻层的轮廓线具有几何相似性时，苏安等提出一种基于相邻层轮廓线几何形状匹配的三维重建算法

REF_Ref261176701\r\h

[42]

。虽然该算法对一些过渡性很好的轮廓线能取得较好的重建效果，但是对突变性很大的轮廓线，该算法并不适用。李小勇等

REF_Ref261185705\r\h

[43]

采用模拟退火遗传算法实现表面拼接，提高了传统的全局法轮廓线拼接算法的效率。

3、轮廓分支问题

轮廓分支问题产生于一个物体在相邻断层上的轮廓个数不相等的情况。基于轮廓线拼接的表面建模算法中，分支问题是一个关键性问题。因为仅仅通过分支的局部信息来确定轮廓线对应关系，往往得不到很好的结果，所以需要通过全局的拓扑和几何结构来确定对应关系。目前方法主要有两类：（1）分解或组合轮廓线的方法；（2）相邻层间插入中间层轮廓线或插入中轴线的方法。

（1）分解或组合轮廓线的方法

这类方法在分解或连接轮廓线的位置选择上非常重要。何小海

REF_Ref259433165\r\h

[44]

利用数学形态学中的膨胀算法分解单支轮廓，XuMeihe

REF_Ref259433178\r\h

[45]

提出了一种根据轮廓凸包周长和轮廓中心位置分解单支轮廓的方法，黄永丽

REF_Ref259433191\r\h

[46]

采用按照周长比率解决分支问题，李小勇等

REF_Ref261179181\r\h

[47]

将Delaunay三角剖分应用到分支问题上，他们提出的这些方法对于解决独立分支有很好的效果。另外，还有一些学者

REF_Ref259433212\r\h

[48]

REF_Ref259433217\r\h

[49]

REF_Ref259433221\r\h

[50]

也采用此类方法将一条轮廓线分解为两条轮廓线来解决分支问题。

（2）在相邻层间插入中间层轮廓线或插入中轴线的方法

Christiansen和Sederberg

REF_Ref259433093\r\h

[37]

最早提出构建过渡轮廓来解决一对二分支问题。他们通过构建过渡轮廓线，在两个分支轮廓线的最小距离点之间添加一个内桥，然后将分支后的两个封闭区域通过该点合二为一，这样就把问题转化为一对一的单轮廓线的连接。这类方法一般计算量大。Meyers等

REF_Ref259433266\r\h

[51]

将分支轮廓投影到基础轮廓上，将其作为基础轮廓线的孔来处理，计算带孔轮廓的中心轴线，并用其来构造过渡轮廓，这种方法构造的轮廓形状与基础轮廓形状相似。J.Jeong，K.kim

REF_Ref259433277\r\h

[52]

通过使用距离映射插入中间轮廓线来解决分支问题。Joaquin

REF_Ref259433296\r\h

[53]

将两层的轮廓线映射到同一断层平面上，利用提取骨架的方法生成中间层。

另外，Barequet

REF_Ref259433304\r\h

[54]

提出了一种以动态规划为基础的最优三角剖分策略的方法。该算法通过其他途径来解决分支问题，避开了传统的分支处理方法。

总之，由于约束性的缺乏，基于轮廓线拼接的建模方法具有很大的随意性。特别是在轮廓线形态复杂，轮廓线位置错位严重，方向和形状差异较大时，该方法重建的结果不理想。虽然目前有大量的研究工作

REF_Ref260733121\r\h

[55]

REF_Ref259433320\r\h

[56]

，但仍然不能从根本上完全解决。

2.2基于体素级的建模方法

2.2.1体素模型定义

体素的定义分为两种

REF_Ref259433333\r\h

[57]

：一种类似于二维图像中的像素定义，将体素定义为体数据中的一个采样点；另一种则以相邻的8个采样点组成为一个体素。本文采用后一种定义方式。

对某一个区域内的三维空间进行采样，若采样间距为，，，且采样点在x，y，z三个方向上是分布均匀的，那么可以用三维数字矩阵来表示体数据

REF_Ref259433333\r\h

[57]

。一个体素由8个相邻的采样点所定义的立方体区域。8个采样点称为体素的顶点。它们的坐标分别为，，，，，，，。

图2-3体素模型

设体素内的任意一待求值点，（）为与点为同一个平面上的点，它们关系如图2-3所示。的值采用该体素的8个顶点进行三线性插值来估计。首先将物理坐标转化为图像坐标，其中，，。然后根据公式（2-1）进行计算

公式（2-1）

又因为

公式（2-2）

公式（2-3）

公式（2-4）

其中

将式（2-2）、（2-3）、（2-4）代入式（2-1）整理可得

公式（2-5）

其中（）为常数，它们由体素的8个顶点值唯一确定。

2.2.2等值面定义

等值面是三维空间中具有相同值的点的集合，采用公式（2-6）来表示

，c为常数公式（2-6）

若当前体素的8个顶点值均小于或大于常数时，那么等值面不经过该体素。

要计算边界体素与等值面的交线，可设体素中等值面的方程为，根据体素中任意一点值的计算公式（2-5），得到假设的表面方程为

公式（2-7）

由公式（2-7）可看出，所求的交线是一条双曲线。除体数据的边界处外，两个共面体素之间的交线是它们的公共面与等值面的交线，因此不存在两体素之间交线不吻合的情况。

2.2.3等值面构造

等值面的构造是实现基于面绘制方法的表面建模的关键步骤，等值面构造方法是否合理，直接影响着表面的生成效果。等值面构造方法主要有三种：（1）立方体法

REF_Ref259394741\r\h

[16]

；（2）剖分立方体法

REF_Ref259433370\r\h

[17]

；（3）移动立方体法

REF_Ref259394760\r\h

[18]

。

Lorenson

REF_Ref259394760\r\h

[18]

等在1987年提出的MC算法是基于体素的一种典型的面绘制算法。本文提出的算法是以MC算法思想为基础，所以在下一节将对MC算法做重点研究。

2.3MC算法

MC算法基本原理是

REF_Ref259393516\r\h

[1]

：将数据场中上下相邻两层剖面的8个数据点组成一个体素，依次遍历数据场中的体素，查找包含等值面的体素，即边界体素，然后进行等值面的抽取，形成最终的物体表面。

2.3.1确定体素中等值面的剖分方式

MC算法求取等值面与体素棱边的交点是以数据场值沿棱边连续线性变化为前提的。因此，如果体素的一个顶点的数据场值大于或等于预先设定的阀值，说明该点位于等值面之内，标记该点状态值为“1”。反之，则说明该点位于等值面之外，标记该点状态值为“0”。在这两个顶点所在的棱边上有且仅有一点是等值面与该边的交点。每个体素有8个顶点，对于每个顶点，它们都有0、1两个状态值。若按顶点标志值的不同划分体素，则共有种状态。由于分别识别和处理256种情况将会是一个复杂而又容易出错的过程。因此，MC算法根据互补对称性和旋转对称性对这256种情况简化成15种

REF_Ref259433419\r\h

[58]

。

（a）互补对称性（b）旋转对称性

图2-4对称性对体素构型种类的简化

图2-5体素中等值面的15种基本构型

在实际应用中，为了能够构造图2-5中所示的MC等值面的基本构型，需设计两个长度为256的查找表。一个为边查找表，用它来记录所有情况下的等值面连接方式，即等值面与体素的哪些棱边有交点的情况。另一个为三角形结构查找表，它记录着对应边查找表中的等值面交点的连接方式。体素每个顶点可代表一个状态位，用一个字节来存储一个体素8个顶点索引号，即通过索引可得到一个0~255之间的索引值，每一个值说明了等值面与体素棱边的相交情况。

图2-6体素中等值面剖面的确定过程

如图2-6所示，分别表示体素8个顶点的状态值，由它组成一个边查找表的索引值cubeIndex，分别为体素的12条棱与等值面的相交情况状态值，由它组成三角形结构查找表的索引值triIndex。根据cubeIndex查找到对应的triIndex，最终根据triIndex的索引内容，即等值面接方式，确定体素中等值面的基本构型。

2.3.2等值面与体素边界的交点

对于当前被处理体素的某一条棱边，如果其两顶点，的标记值不同，那么等值面一定与此边相交，且仅有一个交点，并可利用线性插值的方法来求取该交点。线性插值方法定义为：如果为体元的一条棱，，为的两端点，，分别为，的场函数值，那么给定等值面值，棱上的插值点可用下面表达式来计算：

公式（2-8）

其中。

2.3.3等值面的法向计算

为了获得真实感的等值面图形，需要给图形选择适当的局部面光照模型进行光照计算，因而必须给出形成等值面的各三角面片的法向分量。由于等值面上的任意一点，其沿面的切线方向的梯度分量应该是零，因此，该点的梯度矢量的方向也就代表了等值面在该点的法向

REF_Ref259433462\r\h

[59]

，MC算法就是利用这一原理获得三角面片的法向向量。

设体数据规模为，点为三维数据场中的任意一点，的空间坐标和数据值分别为、（，，）。计算点的梯度值，可首先采用中心差分法计算体素点处的梯度。即

公式（2-9）

公式中的，，分别为体素的棱长。通过公式求出后，需对进行单位化，即，得出的即为点的法向量。

采用上述方法，依次计算出体素8个顶点法向量，并通过线性插值可以求得体素棱边与等值面片的交点法向量：

公式（2-10）

上述公式中表示交点的法向量，,表示棱边两个端点的法向量，两个端点的像素值用、表示，isovalue为该等值面的阀值。整个三角面片的法向量可由三角面片的三个顶点法向量的平均值来计算，即。

2.4其他建模技术

除了前面介绍的两种主要表面建模技术外，还有其它一些物体表面建模技术，大致可分为曲面拟合、显示重建、分段线性重建和基于人工神经网络的重建四大类

REF_Ref259433558\r\h

[60]

。每类方法都有其自己的特点和适用范围。在实际应用中，可以有选择性地采用不同的方法来满足实际要求。

曲面拟合方法又可分为B样条曲面拟合、NURBS曲面拟合、细分曲面拟合和隐函数曲面拟合四种方法。其中B样条曲面拟合适合于形状复杂的曲面，NURBS曲面拟合适合于小规模数据集、拓扑简单的曲面。对任意拓扑、复杂的光滑曲面宜采用光滑细分的曲面拟合方法，结果会比较理想。

2.5本章小结

本章研究了三维表面建模技术。本章首先介绍了基于轮廓线拼接的表面建模技术，并重点研究了该方法存在的难点问题，然后研究了基于体素级的建模方法，并重点介绍了标准MC算法，研究了MC算法的基本原理，最后还对其他建模技术进行了简单介绍。

硕士学位论文第三章基于MP的三维表面建模算法

第三章基于MP的三维表面建模算法

3.1MP算法概述

MC算法对于体数据而言是一种非常有效的等值面建模方法。在医学方面，通过MC算法将核磁共振图像（MRI）进行表面建模，构造出三维表面模型，指导医生进行手术，这大大提高了医生的手术成功率。由2.1.2节可知，基于轮廓线的拼接算法存在着轮廓线对应、分支和拼接等难题。如果剖面的间距比较小且能保持相互平行，同时两对应轮廓线能保持较高的重合程度且形状相似，那么该算法基本能满足实际需要。但是该算法在分支问题上只侧重于解决一条轮廓线与多条轮廓线间的正确拼接问题，实际中却往往不是这么单一的情况，造成这些算法对相邻轮廓线的拼接存在很大缺陷，而MC算法能弥补基于轮廓线拼接算法中许多缺陷。为此，M.W.Jones

REF_Ref261172371\r\h

[27]

等人曾提出将多轮廓线间形体重建问题转化为体数据中等值面构造问题的思想，先后又有许多学者对该算法进行了改进

REF_Ref261175032\r\h

[28]

。

本章首先根据MC算法思想，提出一种新的基于轮廓线重建物体表面算法——移动棱台算法。该算法能解决轮廓线的对应和分支问题。同时，还能解决当轮廓线重合度低时，MC算法重建表面失败的问题。最后，本文对所提出的算法进行了时间复杂度分析以及实验效果对比。

3.2基本定义

定义3-1有序连接所有体素上下面棱边上的等值点，所生成的连线称为等值轮廓线。在上剖面的等值轮廓线称为上等值轮廓线，下剖面的等值轮廓线称为下等值轮廓线。

定义3-2剖面P上的等值轮廓线L与原轮廓线L’之间的吻合程度称为逼近度，用Cd表示。L与L’的吻合程度越高，逼近度Cd也就越高，反之亦然。

定义3-3设两相邻剖面、，和上待重建轮廓线分别为C1和C2。将C1平行投影到上形成轮廓线C1’，C1’与C2交集的大小称为重合度，用Cs表示。C1’与C2交集越大，Cs也越大，反之亦然。

3.3数据结构

为了更好地表达MP算法，本文先介绍几个基本的数据类型。它们是MP表面建模算法的数据基础。

（1）CPoint类

CPoint类是整个程序中最基础的类，后面的介绍的几个类都是以这个类为基础。该类对应于三角形的顶点，基本属性包括三维空间一点的x、y、z坐标（双精度浮点型），m_ID为顶点的索引号。我们还要建立一个动态数组m_points对网格的所有顶点进行统一管理。类的具体形式如下：

classCPoint{

public:

……

//Attributes

doublem_dX;

doublem_dY;

doublem_dZ;

int m_ID;

};

typedefCArray<CPoint,&CPoint>CPointArray;

CPointArraym_points;

（2）CEdge类

CEdge类表示三角形的边，其基本属性包括线段两个端点编号以及共用此边的两个三角形的索引号（如图3-1（a）所示）。使用一个动态数组m_edges统一管理三角边。其具体形式如下：

classCEdge{

public:

……

//Attributes

intm_startPointID;

intm_endPointID;

intm_adjTriaID[2];

intm_ID;

};

typedefCArray<CEdge,&CEdge>CEdgeArray;

CEdgeArraym_edges;

（3）CTriangle类

CTriangle类表示三角面片，它包含三角形的三个顶点的索引、三条边的索引（三个顶点和边以逆时针方式排列编号）、此三角形相邻的三个三角形的索引（如图3-1（a）所示）以及此三角形的序号和三角形的法向量，以动态数组m_triangles统一管理。具体形式如下：

classCTriangle{

public:

……

//Attributes

intm_pointIndex[3];

intm_edgeIndex[3];

intm_adjTriaID[3];

int m_ID;

doublem_norma[3];

};

typedefCArray<CTriangle,&CTriangle>CTriangleArray;

CTriangleArraym_triangles;

（4）CCube类

CCube类对应MP算法所处理的体素单元，基本属性包含了八个体素顶点索引。体素顶点类型由CCubePoint类定义，是CPoint类的子类，增加了顶点的权重值m_value

，当前体素的前后左右上下的体素编号以及当前体素单元的编号。当前的体素有与等值面有交的状态值m_hasFace，用动态数组m_meshArray来存储所有的体素，具体形式如下：

classCCube{

public:

……

//Attributes

int m_cubePointID[8];

intm_ID;

intm_leftCubeID;

intm_rightCubeID;

intm_upCubeID;

intm_bottomCubeID;

int m_frontCubeID;

intm_backCubeID;

BOOLm_hasFace;

};

classCCubePoint:publicCPoint{

public:

……

//Attributes

doublem_value

;

};

typedefCArray<CCube,&CCube>CMeshArray;

CMeshArraym_meshArray;

（a）点、边和三角形拓扑关系（b）体素之间拓扑关系

图3-1点、边、三角形和体素的拓扑关系

3.4MP算法基本原理

与MC算法类似，MP算法所处理的数据也是三维空间体数据。各种影像设备是体数据获得的主要途径，比如核磁共振、CT和超声等影像数据。在地质学中，地层体数据主要来源于自然或者人工爆炸产生的地震波，从而对地质进行结构分析。

图3-2MP算法实现轮廓线生成等值面的处理过程

本项目主要是通过对矿山剖面的编辑，圈出矿体轮廓线。矿体轮廓线并非是三维空间体数据，要采用MP算法实现基于轮廓线的物体表面建模，则需增加对轮廓线向体数据转化的步骤。如图3-2所示，MP算法实现物体表面建模主要有两个关键步骤：（1）体数据的构造；（2）等值面的生成。

3.4.1体数据的构造

体数据是MP算法的基础。算法首先将轮廓线所在的剖面统一定义为规模为Nx×Ny的二维网格，在与一系列平面相垂直的方向上定义一个Z轴后,每一个网格点可以被认为是Nx×Ny×Nz空间的一个点，这里网格点取为像素点。体数据的构造就是将每一个网格顶点的场函数值作为体素顶点的权值,形成规模为Nx×Ny×Nz的体数据

REF_Ref261175032\r\h

[28]

。

设一系列平面上的多条轮廓线及场函数，对与轮廓线所在平面上的每个网格点v，定义其场函数值符号为

REF_Ref259393516\r\h

[1]

：（1）如果点v在全部轮廓线之外，则函数值为负；（2）如果点v在某一条轮廓线上，则函数值为0；（3）如果点v在某一条轮廓线之内，则函数值为正。场函数的选择合理与否直接关系到体数据构造的优劣，优良的场函数能消除明显的突变现象。其中，欧式距离函数是常用的场函数。欧式距离函数定义如下：

公式（3-1）

其中是由点到同层剖面上所有轮廓线上点的最近距离。

虽然采用欧式距离函数作为场函数能消除明显的突变现象，但由于体素顶点与轮廓线的关联性不是很紧密，丢失了与轮廓线相关的大部分有用信息，例如轮廓线的精确轨迹以及走向，这样使得等值轮廓线与原轮廓线存在着空隙，即逼近度Cd低。因此，需要首先对轮廓线进行预处理。

1、轮廓线的预处理

假设待重建表面的轮廓线组均为封闭的轮廓线。现计算第i层（）的轮廓线所在剖面上的每个网格点的状态函数值。图3-3（a）显示了一个剖面网格化之后当中的三个网格单元。其中，ABCD网格单元的四个顶点分别为A、B、C、D，线段EF为剖面上轮廓线的一段，A、C点轮廓线的外部，B、D点轮廓线的里面。根据公式（3-1）可知：每个网格点的状态函数值就是网格点到当前剖面上轮廓线上点的最短距离，因此，可以得出A、B点到点E以及C、D点到点F是最短的，设场函数值分别为、、、。

（a）等值轮廓线与原轮廓线出现的不吻合

（b）在整个剖面上出现逼近度Cd差的问题

图3-3未对轮廓线上点插值时等值轮廓线的连线情况

在计算等值面与单元格边界的交点时，本文采用线性插值法。如果P1、P2为要进行线性插值的线段的两端点，V1、V2分别为他们的场函数值，那么插值点P可用下面表达式来计算：

公式（3-2）

其中isovalue是等值面值，本文的等值面值设为0。理想状态下，只有AB和CD边计算出的等值点I、J分别落在点G和H上。这样等值点的连线才能与轮廓线边EF吻合。假设A、C点位于线段EF的外侧，B、D点位于线段EF的内侧，此时需要满足式（3-3）才能实现式（3-4）点与点重合，即

公式（3-3）

公式（3-4）

其中符号表示AE两点间的欧式距离。

（a）对轮廓线点插值后的逼近度

（b）对轮廓线点插值后整个剖面上的吻合情况

图3-4增加轮廓线上点后的等值轮廓线

在大多数实际情况下，由于体素顶点的权值不能很好的反映轮廓线的信息，因此公式（3-3）和公式（3-4）并不完全成立，这时计算得出的等值轮廓线与轮廓线重合度低，造成重建出的物体表面将会有很大的误差（如图3-3中边所示）。如果能在线段EF上找到一点使其到A、B点的距离最短，且Q尽量接近点G，那么将在很大程度上减少这个误差。如图3-4所示，在线段EF中间适当地进行点等距插值（图中星号标示），此时，点A、B、C、D到线段EF的最近点已经逼近G和H。按照公式（3-4）计算得出的等值点I、J的连线IJ已经与EF边近似吻合，如果再增加插值点的个数，那么在容忍的误差范围内，可以把边与轮廓线段EF看作近似重合，即：。这样在很大程度上提高了重建表面的质量。

由以上分析，对轮廓线进行预处理算法较简单，主要步骤如下：

算法3.1对轮廓线进行插值的算法——ContourAddPoints(contour,nx,ny,newContour)

输入：轮廓线contour，网格规模nx×ny；

输出：进过对轮廓线进行点加密后的新轮廓线newContour；

Step1根据剖面的长和宽以及网格规模大小nx×ny，计算出网格单元的长和宽值，并取较小的值作为阀值f，即f=min；

Step2取轮廓线contour的第i条线段li（，n为轮廓线上的线段数目）；

Step3计算的线段li的长度d，，判断d与f的大小，若，转Step2，否则转Step4；

Step4在线段li上线性插入个点，若i<n，则转Step2，否则转Step5；

Step5算法结束。

对原轮廓线的点进行插值提高了原轮廓线与等值轮廓线的逼近度，使得重建出的物体表面能更精确的接近原始物体真正形状。但是，简单地增加原轮廓线上的点，也不能使等值轮廓线无限地逼近。此外，欧式距离的计算是一个很耗时的过程，因此还需要对剖面进行更进一步处理。

2、外包棱台的求取

轮廓线的预处理对于体数据的构造有着非常重要的作用。它既能提高等值轮廓线的逼近程度，又能更好的反映原轮廓线的信息属性。要构造出逼近度更高的等值轮廓线，需要对网格规模进行调整。网格规模的大小与图像的分辨率相似，规模大则逼近度高些，反之亦然。在图3-5（a）中网格规模大小为6×5，等值轮廓线与原轮廓线逼近度较低，图3-5（b）中增大了网格规模至12×10，此时逼近度有了显著的提高。

提高轮廓线上点的密度和增大网格规模都会增加网格顶点的场函数值的求解次数，影响表面重建速度。设网格规模为n1×n2，轮廓线总的点数目为n3，其中，，均大于0。根据公式（3-1）可知，求取每一个网格顶点权值需要对当前剖面上轮廓线上的所有点进行欧式距离计算，计算的次数为n1×n2，总计算次数为C1=n1×n2×n3，若提高网格规模为m1×m2，轮廓线进行点的插值后个数为m3，总计算次数为C2=m1×m2×m3，其中m1>n1，m2>n2，m3>n3，则增加了C2-C1次场函数值的求解。由于计算各剖面的所有网格点的状态函数值将会十分耗时，所以需减少网格点的计算以求得理想的重建速度。

（a）网格规模为6×5（b）网格规模为12×10

图3-5网格规模与等值轮廓线逼近度

W.M.Jones采用等值面是否通过某体素的方法来判断是否计算该体素顶点的距离函数值。这样虽然节约了一些计算时间，但还是计算了许多冗余点

REF_Ref261172371\r\h

[27]

。纪凤欣等

REF_Ref261175032\r\h

[28]

通过“连接表面投影区”比较两相邻剖面上对应像素点的状态值，以确定影响等值面生成的像素点。在像素点的距离函数计算过程中，只对有等值面生成有影响的像素点进行距离函数计算，达到节约计算时间的目的。但是等值轮廓线与原轮廓线的逼近度Cd不高，且生成的物体表面精确度不高，在两剖面上的轮廓线重合度Cs为空的极端情况下，无法实现表面重建。为此，本文采用相邻轮廓线投影区域的集合运算来提高重建表面的速度。

（a）投影在一个剖面上的轮廓线 （b）有效投影区域对应的体表面

图3-6相邻剖面上的轮廓线区域R

如图3-6（a）中所示，剖面Si+1上有两条轮廓线Ci’与Ci+1，轮廓线Ci’为平面Si上的轮廓线Ci在Si+1平面上的投影（Si与Si+1为平行的剖面），现假设轮廓线Ci+1对重建表面有影响的区域为A，轮廓线Ci’对重建表面有影响的区域为B，则从图3-6（b）中可以看出，需重建的物体表面在平面Si+1的投影正好位于有阴影的区域内，因此，在计算网格点的场函数值时，可以忽略一些对表面重建无影响的网格点的场函数值计算。用R表示阴影部分，则R的范围为A和B的并集结果再差上A和B的交集，用公式（3-5）表示为：

公式（3-5）

判断剖面上网格点是否位于区域R内，主要通过网格点与轮廓线内外关系来求解。设当前剖面上的所有网格顶点集为，轮廓线，，k、n分别为顶点数和两相邻剖面上的轮廓线数，为k个标示位（），标示每个顶点跟区域R的内外关系，在轮廓线内用1表示，否则用0表示。算法主要步骤描述如下：

算法3.2求取有效区域R的算法——GetEffectiveRegion(V,C,,)

输入：网格点集，上剖面轮廓线，下剖面轮廓线；

输出：顶点的权值；

Step1取当前网格顶点（），判断是否在任意一条轮廓线内，若在，则，否则；

Step2判断跟轮廓线组的关系，若位于的任意一条中，则将mi与1进行异或，否则mi与0进行异或，并将结果存入mi中；

Step3，若i<k，则转Step1，否则转Step4；

Step4算法结束。

根据mi的值，就可以省略mi值为0的网格点的场函数值计算，从而加快了体数据的构造速度。

当相邻的两剖面上的轮廓线投影到同一个剖面没有公共部分时，即重合度，公式（3-5）的解，说明在三维空间上没有具有影响体表面的有效区域。而实际上，这只是两轮廓线错开的程度很大所生成的错误结果。

现以图3-7为例进行说明，在图3-7（a）中，p，q为两相邻剖面，v1、v2为剖面上的对应网格点，即线段v1v2同时垂直于p，q剖面，剖面上的轮廓线c1和c2的重合度为0。根据公式（3-1）可知，剖面上每个网格顶点的场函数值仅跟各自剖面上的轮廓线位置有关，构成体素一条棱的上下顶点，它们的场函数值不存在任何关联性。将v1、v2同时沿着图3-7（a）中竖截线左右移动，可以发现v1、v2的场函数值符号将不存在同时为正的情况。图3-7（b）为采用MC算法重建表面的结果（纵截面图），剖面p，q上的网格点场函数值如图中数字标示所示，上下剖面并没有拼接起来，而是各自形成凸起的表面，导致表面拓扑结构不正确。

（a）重合度为空的两轮廓线（b）一组体素顶点的场函数值分布（纵截图）

图3-7相邻剖面轮廓线重合度低时的表面重建

导致上述问题的原因在于：如果为空，那么根据公式（3-1）的定义，体素的上下面8个顶点的场函数值都只可能异号。按照MC抽取等值面原则，等值点只可能落在体素上下对应顶点之间，即体素的侧棱上，使生成的上下表面成为互不连接单独等值面（图3-7（b））。重合区域越大，能连接上下面的体素个数越多，所重建出的表面越接近真实形态。由此可知，轮廓线重合度越高，重建的效果越好，反之越差。解决这类问题的常规方法就是在两轮廓线之间插入中间轮廓线，使轮廓线合理过渡，但该方法增加了额外的操作负担。

为克服上述问题的出现，本文采用外包棱台来解决。本文先假定所有的剖面是相互平行且大小一致的矩形，轮廓线均位于对应的剖面内。外包棱台是指对应连接剖面上下轮廓线的矩形包围盒顶点后得到的棱台。外包棱台确定了待重建轮廓线之间的对应关系，它是MP算法的关键。如图3-8所示，计算外包棱台的主要步骤如下：

算法3.3计算外包棱台的算法——GetPrismoid(P,S,B)

输入：剖面上轮廓线的所有点集（n>0），两相邻剖面（）；

输出：外包棱台B的八个顶点ABCD；

Step1计算所有点集到剖面上边的欧式距离，并找出最短与最长距离距离值minDis，masDis；

Step2将点集投影到上，得到投影点集，计算点集中两点间的最大的距离值；

Step3以为长度，对边分别平移minDis，masDis，得到AB、CD边，连接两边得到包围矩形盒ABCD；

Step4对另外一条轮廓线重复Step1—Step3操作步骤，得到另外一个包围矩形盒EFGH，并有序连接ABCDEFGH形成外包棱台；

Step5算法结束。

图3-8（2）显示的是将相邻剖面、上的矩形包围盒、进行对应顶点的连接，形成整个外包棱台。

（a）剖面上棱台四个顶点的求取（b）整个外包棱台

图3-8相邻剖面上轮廓线的外包棱台

对于图3-7中的情形，首先将轮廓线进行外包棱台的构建，然后将外包棱台网格化。如图3-9（a）所示，C1为剖面P上轮廓线，其影响区域为A，C2为剖面Q上的轮廓线，影响区域为B。从图3-9（b）中可知，棱台的上下底是相邻剖面上对应轮廓线矩形包围盒，强制性地使C1斜对应于C2，使得A与B的交集。根据公式（3-5）可知，体表面有影响的区域，上下相邻网格点的场函数值符号同为正的棱对数也一定不为0，则体素的上下面上将会有等值交点，因而可正确抽取出等值面。

（a）外包棱台的构建（b）一组体素顶点的场函数值分布（纵截图）

图3-9MP算法解决轮廓线重合度低的表面重建

外包棱台进行网格化的步骤相对简单，只需将棱台上下底面分别按给定的体数据规模进行等距网格化分，并将对应网格顶点组合成体素，最终构造出规模为的体素组。采用外包棱台构造体素主要目的在于解决轮廓线重合度的问题。如图3-10所示，图中网格规模Nx×Ny×Nz为5×3×1。按体素的定义方式，将8个相邻的网格点进行组合形成一个棱台。通过把外包棱台细分，得到一系列的体素组。由图中可知，得到的体素的15种基本构型与MC算法的构型略有不同。但每个体素的形态仅仅是上下矩形偏移或者是缩放，彼此能够很好地对应起来，故不影响体素中等值面生成。

图3-10外包棱台的网格化

根据算法3.1、3.2和3.3，可以得出构造体数据的算法3.4。本文先假定轮廓线均不超出剖面上的区域范围，且剖面是规则的平行矩形，并做如下变量说明：设一系列剖面Si（，n为总共的剖面数且大小一致），轮廓线组Cj（，m为总共的轮廓线数），vk为一个剖面上的网格点组，为剖面Si上的每个网格点是否位于有效区域R的标示位，每个由Nx×Ny个标志位组成。通过前面的阐述，得到构造规模为Nx×Ny×Nz的体数据的算法，算法步骤如下：

算法3.4体数据构造的算法——CreateVolumeData(sections,contours,volumeData)

输入：剖面组sections，它由一系列剖面Si组成，contours为剖面上的轮廓线组，它由一系列轮廓线Ci组成；

输出：体数据volumeData；

Step1根据算法3.3计算剖面Si与Si+1上的轮廓线Ci和Ci+1的外包棱台BP；

Step2对外包棱台BP进行规模为Nx×Ny的网格化，取剖面Si和Si+1以及对应剖面上的轮廓线Ci和Ci+1，根据算法3.1对轮廓线进行点插值；

Step3按算法3.2进行进行有效区域计算，并将结果赋值给和；

Step4依次取Si和Si+1上的网格点vk（），判断vk点对应的标志位，若标示位为1，则按公式（3-1）计算vk的场函数值，否则不计算，直接赋值成浮点数的负最大值；

Step5，若，转Step4，否则转Step6；

Step6，若，转Step1，否则转Step7；

Step7将结果赋值给volumeData，算法结束。

3.4.2等值面的生成

假定预先给定的等值面阀值C0，等值面的生成就是根据两相邻顶点的场函数值生成等值点，然后将每个体元中的所有等值点按组合方式连接起来形成边界多边形，最后进行三角化，生成数值为C0的等值面的过程。MP算法的等值面与体素棱边交点求取原则是以数据场值沿棱边连续线性变化为前提的。因此，如果体素的一个顶点的数据场值大于或等于给定的预先设定的阀值，说明该点位于等值面之内，标记该点状态值为“1”。反之，则说明该点位于等值面之外，标记该点状态值为“0”。这两个顶点所在的棱边之间有且仅有一个等值面与该边的交点。根据上述的分类规则和体素顶点的数据场值，可对体素的8个顶点进行分类，最终确定等值面的剖分方式。

每个体素有8个顶点，对于每个顶点，它们都有0、1两个状态值。若按顶点标志值的不同划分体素，则共有种状态。类似于MC算法，对256种不同的情况分别进行识别和处理虽然可以实现，但会是一个复杂而又容易出错的过程。所以需要采用旋转对称性和互补对称性将256种情况进行简化，最终得出15种等值面抽取情况。由于15种基本构型跟MC算法相似（图2-5），在此不再介绍。

（a）体素顶点的场函数值计算（b）体素中等值面的抽取

图3-11体数据的构造与等值面的抽取

图3-11（b）为外包棱台中网格化后一个的小棱台，网格点v0、v2在轮廓线内，场函数值为正，、在轮廓线外，场函数值为负，所以在棱v0v3、v2v3、v4v7和v6v7上分别有等值点，根据MC算法的等值点连接方式生成等值面。

假设体素顶点的函数值沿体素棱边是线性变化的，可以线性插值方法求出等值面与棱边的等值点值。将这些交点连接起来，构成等值多边形。按照类似于MC算法的15种基本构型，将等值多边形进行三角剖分，生成最终的三角片。

为了获得更具有真实感的等值面图形，图形需要选择适当的局部面光照模型进行光照计算。但是，光照计算又需要计算等值面片的三角面片的法向量。MP算法跟MC算法中的等值面的法向计算过程相同，利用公式（2-9）和（2-10）可求出三角片的法向量，实现真实的等值面绘制。

3.4.3MP算法抽取等值面的算法流程

根据前面对MP算法的介绍，MP进行表面建模的步骤如下：

Step1将剖面和轮廓线数据读入内存；

Step2读取两层剖面和剖面上的轮廓线数据，计算外包棱台，并将外包棱台进行网格化，生成体素；

Step3根据网格规模，对轮廓线进行预处理，并进行体素顶点场函数值的计算；

Step4将体素每个顶点的函数值与给定的等值面值做比较，根据比较结果，得到该体素的MC边查找表的索引值；

Step5采用MC边查找表，查找对应的体素等值面连接方式；

Step6通过线性插值方法，计算出边界体素的棱与等值面的交点；

Step7利用公式（2-9）求出体素各顶点处的法向，再利用公式（2-10）求出三角形各顶点处的法向；

Step8根据各三角面片各顶点的坐标值及法向量绘制局部等值面图象；

Step9检测所有体素是否全部处理完毕，如否，则进行到下一个体素，转到Step2步处理；

Step10算法结束。

3.5MP算法的优缺点

MP算法解决了基于轮廓线拼接以及MC算法实现轮廓线重建中一系列问题。当然，MP算法同时存在着自己的缺陷，主要归纳如下：

1、解决了基于轮廓线拼接的分支和对应问题

轮廓线的对应和轮廓线分支一直是基于轮廓线拼接算法的两大问题，MP算法有效地避开了这两大问题，省去了人工干预，取得了比较好的结果。同时，MP算法重建的表面形态要比基于轮廓线拼接的形态更为理想。

2、克服了轮廓线重合度低的建模问题

MP算法克服了MC算法中轮廓线重合度低和空时的表面建模问题。传统的方法通过在待重建的轮廓线之间插入中间轮廓线的方法来解决这个问题。该方法在解决轮廓线重合度低的问题上能起到一定的效果，但给用户带来额外的负担，特别是当轮廓线密集时，额外的工作量会使用户难以接受。同时，要使两剖面之间的轮廓线能顺利地自然过渡，插入中间轮廓线的方法还存在着一定的难度。

3、降低了等值轮廓线与原轮廓线间的逼近误差

MP算法从增加轮廓线上点的数目和提高网格规模大小两个方面来提高轮廓线的逼近度，起到了很好的效果。同时为了防止表面建模的计算量随着网格规模和轮廓线点数目的增加而上升，MP算法采用了轮廓线投影有效区域策略来减少场函数值的计算量，节约了表面建模时间。

4、MP算法无法适用于开曲线的建模

由于MP算法是基于体数据的表面建模方法，所以在对轮廓线进行表面建模时需要加入体数据的构造过程。而体数据是通过闭合轮廓线来构造的，使得MP算法只适合于闭合轮廓线的表面建模。

3.6算法分析与实验效果

为分析算法的时间复杂度，本文先作如下假设：网格规模大小为，两剖面的轮廓线条数分别为、，每条轮廓线的平均顶点数为，其中、、、、均大于0。

1、MP算法的时间复杂度

算法整个计算时间主要与体数据的构造、等值面的生成相关。体数据的构造又分为外包棱台的求取、轮廓线的预处理以及轮廓线投影有效区域的计算三部分。而等值面的生成由边查找表的查询、面查找表的查询两部分组成。

本文首先在计算外包棱台时，计算量主要集中在对当前剖面上的轮廓线点集到剖面一条边的投影以及距离值的计算，总需计算的次数为，由于，，因此算法的复杂度为线性时间复杂度。轮廓线预处理环节中，只需对每条轮廓线的每条边进行插值，总次数为，所以时间复杂度也为。在有效区域的求取中，对每个网格点需要对两剖面上的所有轮廓线进行内外关系判断，判断一次的时间复杂度为，总计算次数为，由于，，所以时间复杂度为，又因为

所以算法的时间复杂度近似为，其中。综合以上各步骤，体数据的构造的总的算法时间复杂性近似为：

等值面的生成主要是依次对每个体素进行等值面的抽取，包括对边查找表和面查找表的操作，计算总次数为，由于边查找表和面查找表操作的时间复杂度为线性时间复杂度，所以时间复杂度为。

综上分析，MP算法的总的时间复杂度近似为，其中。

2、算法实验效果

本文通过实验对算法进行了仿真和验证，试验硬件平台为一台主频为3.0G的双核PC，1G内存，软件开发环境为WindowsXP操作系统，VisualC++7.0，显示处理库OpenGL，C0取值为0。

（1）分支和对应问题的实验效果

本章提出的MP算法具有解决轮廓线对应问题和分支问题方面的优点，还能处理每层轮廓线含有多条闭合轮廓线的情况，不需要人工干预，自动完成拼接。在图3-12中，分别采用文献

REF_Ref259433558\r\h

[60]

中的人工手动分支的轮廓线拼接方法和MP算法进行了表面重建。（a）、（c）显示了采用文献

REF_Ref259433558\r\h

[60]

中的手动分支的轮廓线拼接方法重建的表面效果，（b）、（d）为采用MP算法的重建效果。由图可知，（b）、（d）图重建的表面形态显然要优于（a）、（c），且无需进行手动分支操作。

（a）手动分支重建结果（b）MP算法重建结果

（c）手动分支重建的结果（d）MP算法重建结果

图3-12对有分支问题和对应问题的轮廓线重建效果

（2）轮廓线重合度和逼近精度的实验效果

图3-13中显示了两种不同情况的轮廓线，图3-13（a）中是两条规则轮廓线且它们的轮廓线重合度为空，图3-14（b）中的轮廓线重合度为空，同时它们的形态差异比较大。图3-14（a）为采用MC算法重建的表面效果，结果为两个凸的表面。采用MP算法解决了重合度为空时的重建问题（如图3-14（b）所示）。图3-15（a）是MP算法对图3-13（b）中轮廓线重建的线框模型，图3-15（b）为采用光照渲染后的实验效果。

（a）重合度为空的两轮廓线（b）形状差异很大的两轮廓线

图3-13两种不同形态的轮廓线

（a）MC算法重建结果（b）MP算法重建结果

图3-14轮廓线重合度为0时MP算法与MC算法重建表面效果对比

（a）MP算法重建的线框模型（b）MP算法重建的表面模型

图3-15轮廓线重合度不高且形态差异很大时MP算法重建表面效果

从结果中可以看出，MP算法能较好的解决轮廓线重合度不高时的重建问题，弥补了需插入中间轮廓线才能完成表面重建的缺陷。同时，当两轮廓线形态差异大时，重建的表面形态也较理想。

（3）实际数据的实验效果与分析

通过某矿体剖面数据进行实验对算法进行了效率分析，建立矿体模型如图3-16所示。

（a）某矿体实际建模可视化效果（b）带分支的矿体轮廓线可视化效果

图3-16MP算法实际数据试验结果

表3-1给出了网格规模和轮廓线条数两方面因素对MP算法的影响，并对实验数据进行了统计。

表3-1MP算法对不同网格规模和轮廓线条数的性能测试

图号

网格规模

轮廓线条数

三角面片数

时间消耗（s）

平均每层时间（s）

图3-16（a）

图3-16（a）

图3-16（b）

图3-16（b）

30×30

40×40

30×30

40×40

21

21

4

4

8294

12876

1324

2080

2.611

4.464

0.204

0.343

0.13055

0.2232

0.102

0.1715

从表中可知，MP算法运算效率比较高，同时重建的表面效果比较理想。但是随着网格规模的增加，算法所耗费的时间也随之增加。因此，在实际应用中可以根据具体应用需求对算法的网格规模进行合理设置，使MP算法在速度和绘制质量上都能获得一个较优的结果。从表中还可以得出，MP算法重建的物体表面存在着三角面片过多的情况，随着网格规模的增大，三角面片数量呈上升的趋势。该问题将导致表面模型占用较多的存储空间，影响数据的实时显示。

3.7本章小结

本章根据MC算法原理提出了MP表面建模算法。MP算法具有MC算法的优点，能成功解决基于轮廓线拼接中所出现的分支和对应问题，分析了MC算法在实现轮廓线的表面建模中所出现的轮廓线重合度问题，并通过构造外包棱台模型、计算轮廓线投影有效区域、增大轮廓线点数目和网格规模等方法来解决该问题。最后本章对MP算法进行了复杂度分析和实验验证，得出了较合理的结果。

硕士学位论文第四章分类处理轮廓线的渐近