Fast Generation of Leakproof Surfaces from Well-Defined Objects by a Modified Marching Cubes Algorithm

Local surface reconstruction by the Marching Cubes algorithm and its derivatives has a well known ambiguity, which prevents constructed surfaces from being closed and simple. We investigate this ambiguity assuming that a 3D image samples well-defined objects. In this case it is justified to aim at tiling of extracted object voxels rather than at reconstructing iso surfaces. Compared to iso surface reconstruction, our algorithm provides essentially the same level of confidence with respect to surface location at a lower computational cost. We present a leak detection and mending scheme which resolves the Marching Cubes ambiguity and guarantees a well-defined behaviour with respect to which objects are covered by which surface. We detail how to implement our leak mending method within a completely tabulated Marching Cubes algorithm. We finally give an example of how the adapted algorithm is of benefit to a recently developed 3D MR spectroscopy technique.     

基于MC算法的MEMS光刻仿真的三维重建方法研究

以MC(Marching Cubes)算法为基础,提出了一种补全重建后生成的三维形体表面出现空洞的方法,使用该方法进行三维重建生成的三维形体具有完整的外表面和良好的可视化效果.提出了一种三维重建时对多个形体进行布尔运算的新方法,该方法以MC算法为基础,将三维重建和布尔运算相结合,可以简单、方便、高效地进行三维重建时的布尔运算.     

基于气象雷达回波3D重建的Marching Cubes改进算法

根据气象雷达回波数据的三维极坐标分布特点,提出一种改进的Marching Cubes三维重建算法.该算法将Marching Cubes常规算法中的单位正立方体构建转换为直接对回波极坐标数据的拟柱体构建,生成相应的等值三角面,并对三角面的顶点数据进行地曲订正,供OpenGL显示.为进一步提高重建算法的效率,该算法避免了对高仰角远距离无回波区的重建.实验表明,该算法有效实现了雷达回波的三维重建.     

一种面向三维点集的快速表面重构算法

在对目前比较流行的空间三角化算法进行对比研究的基础上 ,对 Hugues Hoppe提出的算法进行了改进 ,即借鉴 Marching Cubes算法的基本思想 ,首先通过自动选取适当的参数 ,用包围盒方法将三维散乱点划分为数据区域 ;然后求取点的切平面及法向 ,同时采用广度优先算法遍历数据点来调整法向和快速地求取 Marching Cubes的等势函数 ;最后用基于查表法的 Marching Cubes来输出三角面片 ,即得到表面模型 .实验结果表明 ,改进后的算法效率有较大的提高 .新算法不仅适用于表面三维散乱点数据 ,也可以对体数据进行重构 ,具有一定的通用性 .     

离散Marching Cubes算法在骨科手术模拟系统的应用

为保证模型相对准确和满足模拟手术过程中三维交互的实时性要求,手术模拟系统要求在保持模型拓扑结构的前提下简化模型。该文详细介绍了离散MarchingCubes(DiscMC)算法及其实现,在实现过程中使用查表法,解决了二义性问题,提高了程序的运行效率。实验表明,DiscMC算法在保持模型的拓扑结构基础上大幅度减少了三角面片数目,缩减比例达66%。DiscMC算法作为计算机模拟骨科手术系统的三维表面模型重构和简化算法是合适的。     

基于图像分割的三维重构

三维重构方法是医学图像可视化系统、治疗计划系统的重要技术。基于图像分割的三维重构方法结合了图像分割、等值面抽取、网格简化三种技术,是不同于传统Marching Cubes算法的一种三维重构方法。它首先将医学图像分割为二值图,然后利用Marching Cubes方法进行等值面抽取,最后对得到的网格模型进行简化。实验结果表明,基于图像分割的三维重构方法加快了Marching Cubes的运算速度,改善了重构的效果,有利于实现对基于三维重构的大型几何模型的实时绘制和交互。     

Edge Transformations for Improving Mesh Quality of Marching Cubes

Marching Cubes is a popular choice for isosurface extraction from regular grids due to its simplicity, robustness, and efficiency. One of the key shortcomings of this approach is the quality of the resulting meshes, which tend to have many poorly shaped and degenerate triangles. This issue is often addressed through post processing operations such as smoothing. As we demonstrate in experiments with several datasets, while these improve the mesh, they do not remove all degeneracies, and incur an increased and unbounded error between the resulting mesh and the original isosurface. Rather than modifying the resulting mesh, we propose a method to modify the grid on which Marching Cubes operates. This modification greatly increases the quality of the extracted mesh. In our experiments, our method did not create a single degenerate triangle, unlike any other method we experimented with. Our method incurs minimal computational overhead, requiring at most twice the execution time of the original Marching Cubes algorithm in our experiments. Most importantly, it can be readily integrated in existing Marching Cubes implementations, and is orthogonal to many Marching Cubes enhancements (particularly, performance enhancements such as out-of-core and acceleration structures).     

The Mesh Propagation Algorithm for Isosurface Construction

A new algorithm, Mesh Propagation, is presented for the generation of isosurfaces from three-dimensional discrete data sets. While producing the same surface mesh as that generated by a corrected Marching Cubes algorithm, its characteristic is that it constructs an isosurface using connected strips of dynamically triangulated polygons. This compact data structure speeds up surface construction and reduces surface storage requirements. The surface can also be displayed more quickly, particularly where there is hardware support for rendering triangle strips. With engineering as well as medical imaging applications in mind, the algorithm can be used with both irregular and rectilinear grids of data, the primitive volume elements need not be hexahedral only, and volumes of heterogeneous polyhedral elements are supported without traversal complications. The algorithm propagates through the cells in the grid and uses the same lookup table topologies as Marching Cubes to determine patches of surface-element intersection; additional tables are used for non-hexahedral elements. The surface patches are dynamically coded into triangle strips which are then concatenated and linked to construct the surface. The data structures used for propagating through the volume overcome the topological ambiguities associated with table-based methods of surface construction and no holes are generated in the final mesh.     

Quality Isosurface Mesh Generation Using an Extended Marching Cubes Lookup Table

The Marching Cubes Algorithm may return degenerate, zero area isosurface triangles, and often returns isosurface triangles with small areas, edges or angles. We show how to avoid both problems using an extended Marching Cubes lookup table. As opposed to the conventional Marching Cubes lookup table, the extended lookup table differentiates scalar values equal to the isovalue from scalar values greater than the isovalue. The lookup table has 3⁸= 6561 entries, based on three possible labels, ‘?’ or ‘=’ or ‘+’, of each cube vertex. We present an algorithm based on this lookup table which returns an isosurface close to the Marching Cubes isosurface, but without any degenerate triangles or any small areas, edges or angles.     

High-quality extraction of isosurfaces from regular and irregular grids

Isosurfaces are ubiquitous in many fields, including visualization, graphics, and vision. They are often the main computational component of important processing pipelines (e.g. , surface reconstruction), and are heavily used in practice. The classical approach to compute isosurfaces is to apply the Marching Cubes algorithm, which although robust and simple to implement, generates surfaces that require additional processing steps to improve triangle quality and mesh size. An important issue is that in some cases, the surfaces generated by Marching Cubes are irreparably damaged, and important details are lost which can not be recovered by subsequent processing. The main motivation of this work is to develop a technique capable of constructing high-quality and high-fidelity isosurfaces. We propose a new advancing front technique that is capable of creating high-quality isosurfaces from regular and irregular volumetric datasets. Our work extends the guidance field framework of Schreiner et al. to implicit surfaces, and improves it in significant ways. In particular, we describe a set of sampling conditions that guarantee that surface features will be captured by the algorithm. We also describe an efficient technique to compute a minimal guidance field, which greatly improves performance. Our experimental results show that our technique can generate high-quality meshes from complex datasets.     

基于Double Marching Cubes的表面重建算法

为克服基于Marching Cubes的表面重建算法在绘制三维表面时因二义性面的存在而使生成的表面网格易出现错误连接而形成层间空洞的不足,提出了基于Double Marching Cubes的表面重建算法.该算法采用双立方体体素作为生成表面网格的基本单元,以双立方体的12个特征点的标记情况为依据,建立一个双立方体体素索引表,通过查找索引表的方法绘制三维表面.该算法在建立双立方体索引表时就排除掉了二义性面的所有错误连接方式,因而生成的表面网格不会出现层间空洞,避免了为消除二义性面所进行的复杂计算,加快了表面重建的速度.     

Marching Boxes：一个多精度等值面抽取算法

Ｍａｒｃｈｉｎｇ Ｃｕｂｅｓ算法是生成三维数据场等值面的经典算法，适用于数据密度较高的体数据。结合显示所需精度提出的Ｍａｒｃｈｉｎｇ Ｂｏｘｅｓ算法，对ＭＣ算法作了优化，减少了由ＭＣ算法生成的三角面片数，使实时观察体数据成为可能。     

Contouring Discrete Indicator Functions

We present a method for calculating the boundary of objects from Discrete Indicator Functions that store 2‐material volume fractions with a high degree of accuracy. Although Marching Cubes and its derivatives are effective methods for calculating contours of functions sampled over discrete grids, these methods perform poorly when contouring non‐smooth functions such as Discrete Indicator Functions. In particular, Marching Cubes will generate surfaces that exhibit aliasing and oscillations around the exact surface. We derive a simple solution to remove these problems by using a new function to calculate the positions of vertices along cell edges that is efficient, easy to implement, and does not require any optimization or iteration. Finally, we provide empirical evidence that the error introduced by our contouring method is significantly less than is introduced by Marching Cubes.     

一种由轮廓线重建物体表面的方法

针对基于轮廓线拼接重建物体表面所出现的轮廓对应和分叉问题,提出了一种通过体数据转换由轮廓线实现重建物体表面的方法。在分析体数据构造中出现逼近精度问题的前提下,通过提高轮廓线上点的密度,生成精确度较高的体数据。该方法通过对相邻层轮廓线区域的集合运算,只对处于集合运算解中的像素点进行距离函数值的计算。采用MC（Marching Cubes）算法生成等值面,完成物体的表面重建。实验结果表明,该方法能顺利解决基于轮廓线拼接重建物体表面中出现的轮廓对应问题和分叉问题,既提高重建表面精确度,又加快整个表面的重建速度,是一种可行的方法。     

Edge groups: an approach to understanding the mesh quality of marching methods

Marching Cubes is the most popular isosurface extraction algorithm due to its simplicity, efficiency and robustness. It has been widely studied, improved, and extended. While much early work was concerned with efficiency and correctness issues, lately there has been a push to improve the quality of Marching Cubes meshes so that they can be used in computational codes. In this work we present a new classification of MC cases that we call Edge Groups, which helps elucidate the issues that impact the triangle quality of the meshes that the method generates. This formulation allows a more systematic way to bound the triangle quality, and is general enough to extend to other polyhedral cell shapes used in other polygonization algorithms. Using this analysis, we also discuss ways to improve the quality of the resulting triangle mesh, including some that require only minor modifications of the original algorithm.     

Marching Cubes算法改进研究及应用

对MC算法进行了改进和优化,运用渐近线判别法解决了原有算法的二义性问题,改善了生成图形的质量;利用线性八叉树结构提高了图形的绘制速度,使实时绘制和交互操作成为可能。运用改进后的MC算法,结合某铁矿实测数据进行矿体表面三维重构,得到了满意的效果。     

基于三维栅格模型的最短距离等值面提取

通过研究三维最短距离分析及MC算法,提出基于三维栅格模型的最短距离等值面提取算法,通过导入费用数据和源点数据,即可自动输出到达源点任意有效取值的最短距离等值面。该算法允许输入多个源点,并可应用于非均质三维空间中。实验结果表明,该算法设计合理、可行。     

基于近平面合并的三角网格简化算法

提出一种基于近平面合并的三角网格简化算法,针对三维重建MarchingCubes算法中产生的大量三角片进行简化。首先依据近平面判断条件将近似共面的三角形合并成一个大的多边形,然后按相应的准则将其重新进行三角化得到更少的三角形面片,以达到简化的目的。该算法在最大化的保留图像细节的前提下,精简了三角片的数目,提高了重建后图像绘制和传输的速率,节省了存储空间和处理时间。     

基于GPU的医学图像快速面绘制

提出了一种医学图像快速面绘制的方法,该方法将新一代图形处理器GeForce 8800的特性和MC（Marching Cubes）算法相结合。利用几何着色器的数据批处理能力在每个立方体中提取等值面并生成三角形带;在片段着色器上采用Phong光照模型对生成三角形渲染显示。建模和显示过程均在GPU上完成,对CPU的依赖低。实验表明,在保证绘制效果的前提下,该方法可在通用PC平台上实现大小为512×512×400的CT数据的实时建模,有很好的实用价值。