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算法的一种三维重构方法。它首先将医学图像分割为二值图,然后利用Marching Cubes方法进行等值面抽取,最后对得到的网格模型进行简化。实验结果表明,基于图像分割的三维重构方法加快了Marching Cubes的运算速度,改善了重构的效果,有利于实现对基于三维重构的大型几何模型的实时绘制和交互。     

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.     

Efficient and Quality Contouring Algorithms on the GPU

Interactive isosurface extraction has recently become possible through successful efforts to map algorithms such as Marching Cubes (MC) and Marching Tetrahedra (MT) to modern Graphics Processing Unit (GPU) architectures. Other isosurfacing algorithms, however, are not so easily portable to GPUs, either because they involve more complex operations or because they are not based on discrete case tables, as is the case with most marching techniques. In this paper, we revisit the Dual Contouring (MC) and Macet isosurface extraction algorithms and propose, respectively: (i) a novel, efficient and parallelizable version of Dual Contouring and (ii) a set of GPU modules which extend the original Marching Cubes algorithm. Similar to marching methods, our novel technique is based on a case table, which allows for a very efficient GPU implementation. In addition, we enumerate and evaluate several alternatives to implement efficient contouring algorithms on the GPU, and present trade‐offs among all approaches. Finally, we validate the efficiency and quality of the tessellations produced in all these alternatives.     

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

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

Mesh filtering algorithm using an adaptive 3D convolution kernel applied to a volume-based vector distance field

This paper addresses the problem of feature preserving mesh filtering, which occurs in surface reconstruction of scanned objects, which include acquisition noise to be removed without altering sharp edges. We propose a method based on a vector field distance transform of the mesh to process. It is a volume-based implicit surface modeling, which provides an alternative representation of meshes. We use an adaptive 3D convolution kernel applied to the voxels of the distance transform model. Weights of the kernel elements are determined according to the angle between the vectors of the implicit field. We also propose a new adaptation of the Marching Cubes algorithm in order to extract the isosurface from the vector implicit field after the filtering process. We compare our method to the previous one introduced using the vector field representation and to other feature preserving adaptive filtering algorithms. According to error metric evaluations, we show that our new design provides high quality filtering results while better preserving geometric features.     

移动立方体算法的三重线性插值研究

移动立方体算法是目前最有影响的等值面构造方法,已经过了许多改进。现在采用的是三重线性插值模型,用三重线性插值计算等值面与体单元的交点。文章对三重线性插值生成的等值面进行了分析,分析了等值面的一些特点,重点讨论了等值面与边界体单元的交线的两种例外情况,基于这两种情况,给出了改进算法,最后通过实验验证了考虑这两种情况后算法的可行性。     

Convex contouring of volumetric data

In this paper, we present a fast, table-driven isosurface extraction technique on volumetric data. Unlike Marching Cubes or other cell-based algorithms, the proposed polygonization generates convex negative space inside individual cells, enabling fast collision detection on the triangulated isosurface. In our implementation, we are able to perform over 2 million point classifications per second. The algorithm is driven by an automatically constructed lookup table that stores compact decision trees by sign configurations. The decision trees determine triangulations dynamically by values at cell corners. Using the same technique, we can perform fast, crack-free multiresolution contouring on nested grids of volumetric data. The method can also be extended to extract isosurfaces on arbitrary convex, space-filling polyhedra.     

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.     

一种改进的MC算法

为了对等值面与子等值面进行提取和分组,在MC算法原理的基础上,提出了一种改进的等值面提取与子等值面分组算法。该算法首先将数据场分解为点、棱边、面与体元的拓扑结构;然后在整个数据场范围内求所有棱边与等值面的交点,并在面内连接交点形成面与等值面的交线,交线在体元内连接生成空间多边形;接着通过三角化各个体元内的空间多边形得到由顶点表与三角形表组成的等值面数据;最后根据三角形在顶点处的连接关系,采用种子算法对属于同一子等值面的三角形与顶点进行标记,属于同一子等值面的顶点与三角形将被存放在独立的顶点表与三角形表中。实验结果表明,该算法可以高效地实现等值面提取与子等值面的分组。     

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.     

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

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

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

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

Parallel isosurface extraction for 3D data analysis workflows in distributed environments

In this paper we discuss the issues related to the development of efficient parallel implementations of the Marching Cubes algorithm, one of the most used methods for isosurface extraction, which is a fundamental operation for 3D data analysis and visualization. We present three possible parallelization strategies and we outline the pros and cons of each of them, considering isosurface extraction as stand‐alone operation or as part of a dynamic workflow. Our analysis shows that none of these implementations represents the most efficient solution for arbitrary situations. This is a major issue, because in many cases the quality of the service provided by a workflow depends on the possibility of selecting dynamically the operations to perform and, consequently, the more efficient basic building block for each stage. In this paper we present a set of guidelines that permits to achieve the highest performance for the extraction of isosurface in the most common situations, considering the characteristics of the data to process and of the workflow. These guidelines represent a suitable example to support the efficient configurations of workflows for 3D data processing in a dynamic and complex computing environment. Copyright © 2011 John Wiley & Sons, Ltd.     

基于MC算法的医学建模方法与研究

针对现有医学图像特点,提出了一种医学三维建模的新方法.该方法基于传统MC算法,结合种子填充思想进行等值面扩展,并利用DMC方法进行插值位置取代,最后直接连接等值点生成多边形网,从而减少了面片数量,很好的解决了二义性问题.实验表明,该方法较传统方法在拓扑结构、存储空间和处理速度方面均有较大改善.     

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个特征点的标记情况为依据,建立一个双立方体体素索引表,通过查找索引表的方法绘制三维表面.该算法在建立双立方体索引表时就排除掉了二义性面的所有错误连接方式,因而生成的表面网格不会出现层间空洞,避免了为消除二义性面所进行的复杂计算,加快了表面重建的速度.     

Controlled topology simplification

We present a simple, robust, and practical method for object simplification for applications where gradual elimination of high frequency details is desired. This is accomplished by converting an object into multi resolution volume rasters using a controlled filtering and sampling technique. A multiresolution triangle mesh hierarchy can then be generated by applying the Marching Cubes algorithm. We further propose an adaptive surface generation algorithm to reduce the number of triangles generated by the standard Marching Cubes. Our method simplifies the topology of objects in a controlled fashion. In addition, at each level of detail, multilayered meshes can be used for an efficient antialiased rendering     

基于CUDA架构的改进Marching Cubes算法

Marching Cubes是医学体数据可视化的经典算法,但生产的网格质量差、算法执行速度慢成为阻碍其用于数值分析的两个主要缺点。文中提出一种基于硬件加速的Marching Cubes改进算法。该算法采用统一设备架构(CUDA)充分发挥Marching Cubes算法分而治之的优点,利用CUDA的可编程性并行分类体数据,加快了活跃体素和活跃边的提取;同时,该改进算法将得到的活跃边按照中点投影方式进行偏移,从而达到了改善网格质量的目的。最后通过实验表明,该算法可以保证在阈值未知的情况下,进行交互式的高质量网格建模。