A Comprehensive Survey of Isocontouring Methods: Applications, Limitations and Perspectives
- Abstract:
- 1. Introduction
- 2. Marching Squares and Marching Cubes Algorithms
- 3. Tessellation-Based Algorithms
- 4. Surface Nets Algorithms
- 5. Ray Tracing Algorithms
- 6. Proposed Future Research Activities
- 6.1. Condition
- 6.2. Stability
- 6.3. Consistency
- 6.4. Convergence
- 7. Discussion
- 7.1. Marching Squares and Marching Cubes Algorithms
- 7.2. Tessellation-Based Algorithms
- 7.3. Surface Nets Algorithms
- 7.4. Ray Tracing Algorithms
- 8. Conclusions
A Comprehensive Survey of Isocontouring Methods: Applications, Limitations and Perspectives
Published: 15 February 2024
Abstract:
This paper provides a comprehensive overview of approaches to the determination of isocontours and isosurfaces from given data sets. Different algorithms are reported in the literature for this purpose, which originate from various application areas, such as computer graphics or medical imaging procedures. In all these applications, the challenge is to extract surfaces with a specific isovalue from a given characteristic, so called isosurfaces. These different application areas have given rise to solution approaches that all solve the problem of isocontouring in their own way. Based on the literature, the following four dominant methods can be identified: the marching cubes algorithms, the tessellation-based algorithms, the surface nets algorithms and the ray tracing algorithms. With regard to their application, it can be seen that the methods are mainly used in the fields of medical imaging, computer graphics and the visualization of simulation results. In our work, we provide a broad and compact overview of the common methods that are currently used in terms of isocontouring with respect to certain criteria and their individual limitations. In this context, we discuss the individual methods and identify possible future research directions in the field of isocontouring.
本文全面概述了从给定数据集中确定等值线和等值面的方法。为此目的，文献中报道了不同的算法，这些算法源自不同的应用领域，例如计算机图形或医学成像程序。在所有这些应用中，面临的挑战是从给定特征中提取具有特定等值的表面，即所谓的等值面。这些不同的应用领域催生了各种解决方案，它们都以自己的方式解决等高线问题。根据文献，可以确定以下四种主要方法：行进立方体算法、基于曲面细分的算法、表面网络算法和光线追踪算法。从应用来看，这些方法主要应用于医学成像、计算机图形学和仿真结果可视化领域。在我们的工作中，我们根据某些标准及其各自的局限性，对当前在等值轮廓方面使用的常用方法进行了广泛而紧凑的概述。在此背景下，我们讨论了各个方法并确定了等值轮廓领域未来可能的研究方向。
1. Introduction
In many scientific areas, one is interested in identifying, from a set of given data, those that have a constant value. A classic field of application here is cartography for the representation of lines of different levels. These are represented as so-called contour lines on a two-dimensional plane (in this case, a map). In this context, the contour lines represent height levels that have the same value in relation to a defined reference level. This approach enables information from three-dimensional space to be graphically illustrated in a compact form and the characteristics of the existing data set to be visualized appropriately.
In practice, however, it is easy to see that this type of problem is not limited to geography but can be found in many different areas. These include, for example, medical imaging, image processing or the creation of weather maps. In most cases, three-dimensional or four-dimensional data sets are examined in order to extract two-dimensional isocontours or three-dimensional isosurfaces. Regardless of the particular application, however, the overarching task of iscontour extraction is mathematically identical, which can be defined in principle as follows, based on [1].
在许多科学领域，人们都希望从一组给定的数据中找出那些具有恒定值的数据。这里的一个经典应用领域是用于表示不同级别的线的制图学。它们被表示为二维平面（在本例中为地图）上的所谓等高线。在本文中，等高线代表相对于定义的参考水平具有相同值的高度水平。这种方法使得来自三维空间的信息能够以紧凑的形式以图形方式示出，并且现有数据集的特征能够被适当地可视化。
然而，在实践中，很容易看出此类问题并不局限于地理，而是在许多不同的领域都存在。例如，这些包括医学成像、图像处理或天气图的创建。在大多数情况下，检查三维或四维数据集以提取二维等值线或三维等值面。然而，无论具体应用如何，轮廓提取的总体任务在数学上都是相同的，原则上可以根据[1]定义如下。
Definition 1 (Isocontour extraction). Let U ⊆ R n U ⊆ R^n U⊆Rn and V ⊆ R m V ⊆ R^m V⊆Rm be sets with n , m ∈ N \ { 0 } n, m ∈ N \backslash \{0\} n,m∈N\{0} and corresponding mapping φ : U → V φ : U → V φ:U→V. Consider a given sample set D = U × V D = U × V D=U×V over φ : U → V φ : U → V φ:U→V and a constant value v ∈ V v ∈ V v∈V; then, find the set S ⊆ U S ⊆ U S⊆U so that φ ( s ) − v = 0 , ∀ s ∈ S φ(s) − v = 0, ∀s ∈ S φ(s)−v=0,∀s∈S applies. The set S S S is referred to as the isocontour.
定义 1（等值轮廓提取）。令 U ⊆ R n U ⊆ R^n U⊆Rn 和 V ⊆ R m V ⊆ R^m V⊆Rm 被设置为 n , m ∈ N \ { 0 } n, m ∈ N \backslash \{0\} n,m∈N\{0} 和相应的映射 φ : U → V φ : U → V φ:U→V。考虑给定样本集 D = U × V D = U × V D=U×V 在 φ : U → V φ : U → V φ:U→V 上以及常数值 v ∈ V v ∈ V v∈V；然后，找到集合 S ⊆ U S ⊆ U S⊆U，使得 φ ( s ) − v = 0 , ∀ s ∈ S φ(s) − v = 0, ∀s ∈ S φ(s)−v=0,∀s∈S 适用。集合 S S S 称为等值轮廓。
The task described in Definition 1 is qualitatively illustrated in this context in Figure 1.
图 1. 从 MATLAB© 中提取等值线的示例，考虑到峰值函数（表示为
φ
(
x
1
,
x
2
)
φ(x1,x2)
φ(x1,x2)）的恒定值
v
1
,
v
2
v1, v2
v1,v2。
For a given mapping φ : R 2 → R φ : R^2 → R φ:R2→R (here, the Peaks function of the MATLAB© software environment), the sets S 1 S_1 S1 and S 2 S_2 S2 for which φ ( s 1 ) − v 1 = 0 , ∀ s 1 ∈ S 1 , φ ( s 2 ) − v 2 = 0 , ∀ s 2 ∈ S 2 φ(s_1) − v_1 = 0, ∀s_1 ∈ S_1, φ(s_2) − v_2 = 0, ∀s_2 ∈ S_2 φ(s1)−v1=0,∀s1∈S1,φ(s2)−v2=0,∀s2∈S2, respectively, applies are to be identified. The results are then the according isocontours.
对于给定的映射 φ : R 2 → R φ : R^2 → R φ:R2→R（此处使用 MATLAB© 软件环境中的 Peaks 函数），需要确定分别适用于 φ ( s 1 ) − v 1 = 0 , ∀ s 1 ∈ S 1 , φ ( s 2 ) − v 2 = 0 , ∀ s 2 ∈ S 2 φ(s_1) - v_1 = 0, ∀s_1∈ S_1, φ(s_2) - v_2 = 0, ∀s_2∈ S_2 φ(s1)−v1=0,∀s1∈S1,φ(s2)−v2=0,∀s2∈S2 的集合 S 1 S_1 S1 和 S 2 S_2 S2。结果就是相应的等值线。
In our work, we focus on methods that are relevant to the task described in Definition 1 and are referred to as isocontouring methods in the following. When analyzing research carried out in this area, it first becomes apparent that the problem, as described at the beginning, occurs in different application areas. As a result, methods have been developed that solve the isocontouring problem in their own way for each specific application. This is particularly related to the structure of the available data. For example, medical applications often use pixel-based and structured data sets from which isosurfaces must be extracted. In the context of measurement series, on the other hand, unstructured data sets often occur, which require a different solution approach for the extraction of isosurfaces. In addition, the presentation of the results plays an important role in the respective methods used.
Based on our investigations in this area, it can be stated that the methods for isosurface extraction can be classified into four dominant representatives:
在我们的工作中，我们重点关注与定义 1 中描述的任务相关的方法，在下文中称为等值轮廓方法。当分析该领域的研究时，首先会发现，如开头所述的问题出现在不同的应用领域。因此，已经开发出针对每个特定应用以自己的方式解决等高线问题的方法。这尤其与可用数据的结构有关。例如，医疗应用程序通常使用基于像素的结构化数据集，必须从中提取等值面。另一方面，在测量系列的背景下，经常出现非结构化数据集，这需要不同的求解方法来提取等值面。此外，结果的呈现在所使用的相应方法中起着重要作用。
根据我们在该领域的调查，可以说等值面提取方法可分为四种主要代表：
• Marching cubes algorithms;
• Tessellation-based algorithms;
• Surface nets algorithms; and
• Ray tracing algorithms.
These groups are the subject of our investigation and will be examined in more detail in the further course of the paper.
- 行进立方体算法；
- 基于细分的算法
- 曲面网算法；
- 光线跟踪算法。
这几组算法是我们的研究对象，本文将对它们进行更详细的研究。
2. Marching Squares and Marching Cubes Algorithms
The marching cubes algorithm (MC) was introduced in [2] by W. E. Lorensen and H. E. Cline to find isovalues in medical imaging techniques such as magnetic resonance imaging (MRI), computed tomography scans (CT scan) and single-photon emission computed tomography (SPECT). Therefore, the initial data can be interpreted as pixels in a threedimensional picture. A schematic representation of the data is shown in Figure 2. The k dimension represents the individual pictures, where the position of each pixel within one slice is represented by i and j. Hence, the cube presented in Figure 2 is constructed by four opposing pixels in two neighboring slices.
W. E. Lorensen 和 H. E. Cline 在 [2] 中引入了行进立方体算法 (MC)，用于在医学成像技术中查找等值，例如磁共振成像 (MRI)、计算机断层扫描 (CT 扫描) 和单光子发射计算机断层扫描 ( SPECT）。因此，初始数据可以解释为三维图片中的像素。数据的示意性表示如图 2 所示。k 维度表示各个图片，其中一个切片内每个像素的位置由 i 和 j 表示。因此，图 2 中呈现的立方体由两个相邻切片中的四个相对像素构成。
To be able to interpret the data in a medical context, points of equal value must be found. This value can represent a specific tissue density, for example, so that the result of the analysis yields the three-dimensional surface of individual parts of the scan. The marching cubes algorithm follows a divide-and-conquer approach, where each cube is analyzed individually, resulting in small triangles of the surface that, when put together, reconstruct the surface formed by the isovalue. The first step is to mark all vertices of the individual cubes that have a value smaller than, equal to or greater than the isovalue of interest. Since a cube has eight vertices, which themselves can have two states, 256 patterns are possible. Using the symmetries between the individual cases, only 14 different general cases are necessary according to [2]. Cubes where all vertices have values smaller or greater than the isovalue are outside or inside the surface, do not contribute to the surface itself and thus must not be considered in the further process. All other combinations do contribute and are investigated in the following steps. In Figure 3, the different combinations are shown. Here, the highlighted triangles in the individual cubes are part of the surface.
为了能够在医学背景下解释数据，必须找到等值的点。例如，该值可以代表特定的组织密度，以便分析结果产生扫描的各个部分的三维表面。行进立方体算法遵循分而治之的方法，其中每个立方体都被单独分析，产生表面的小三角形，当它们放在一起时，重建由等值形成的表面。第一步是标记各个立方体的所有顶点，这些顶点的值小于、等于或大于感兴趣的等值。由于立方体有 8 个顶点，而顶点本身可以有两种状态，因此可能有 256 种模式。根据[2]，利用个别情况之间的对称性，只需要 14 种不同的一般情况。所有顶点的值都小于或大于等值的立方体位于表面外部或内部，对表面本身没有贡献，因此在进一步的过程中不得考虑。所有其他组合确实有所贡献，并在以下步骤中进行研究。图 3 显示了不同的组合。在这里，各个立方体中突出显示的三角形是表面的一部分。
Based on the values of the cube vertices, the position of the point of the isovalue on the edges of the cube can be determined by linear interpolation. The final step of the proposed algorithm uses the interpolated points, the vertices of the cube under investigation and the vertices of the neighboring cubes to calculate the unit normal used for Gourardshaded images. This is not necessary for the interpolation itself but for the imaging and the subsequent medical analysis. To calculate the unit normal of the density D D D on each interpolated vertex, first, the normal at the cube vertices is calculated in the x , y x, y x,y and z z z directions. For this purpose, the density gradient G G G is calculated, using the expressions presented in Equations (1)–(3). The distance between two pixels in the same slice is ∆ x ∆x ∆x and ∆ y ∆y ∆y, while the distance between two slices is ∆ z ∆z ∆z.
根据立方体顶点的值，可以通过线性插值确定立方体边缘上等值点的位置。该算法的最后一步使用插值点、所研究的立方体的顶点以及相邻立方体的顶点来计算用于 Gourardshaded 图像的单位法线。这对于插值本身不是必需的，而是对于成像和随后的医学分析来说是必需的。为了计算每个插值顶点上密度 D D D 的单位法线，首先，在 x 、 y x、y x、y 和 z z z 方向上计算立方体顶点处的法线。为此，使用方程 (1)-(3) 中的表达式计算密度梯度 G G G。同一切片中两个像素之间的距离为 Δ x Δx Δx和 Δ y Δy Δy，而两个切片之间的距离为 Δ z Δz Δz。
After calculating the gradient at the cube vertices, the gradient at the isovalue vertices can be determined using linear interpolation. Since the component of the gradient vector in the tangential direction of the isovalue surface is always zero, the gradient vector itself represents a normal vector of the respective vertex. In Figure 4, an example is depicted where the gradients of the cube vertices are known and yield the normal unit vectors at the vertices of the isovalue triangle.
计算立方体顶点处的梯度后，可以使用线性插值确定等值顶点处的梯度。由于梯度矢量在等值面的切线方向上的分量始终为零，因此梯度矢量本身表示各个顶点的法线矢量。在图 4 中，描述了一个示例，其中立方体顶点的梯度已知，并在等值三角形的顶点处产生法向单位向量。
The original marching cubes algorithm is the subject of various other scientific works. Authors P. Shirley and A. Tuchman propose, in [4], a method to decompose the cubes into tetrahedral cells before linearization, to increase the calculation efficiency. A problem in the original algorithm is the ambiguities of the 14 patterns depicted in Figure 3. This eventually leads to erroneous artifacts in the resulting three-dimensional object. The Asymptotic Decider, by G. M. Nielson and B. Hamann, proposed in [5], aims to achieve exact solutions. Hyperbolas are used to determine the exact solutions for ambiguous cases. On the other hand, E. Chernyaev proposes 33 patterns in [6] instead of 14 to fully describe all necessary patterns in the marching cubes 33 algorithm (MC33). In [7], B. K. Natarajan shows the ambiguities of the isosurfaces inside the cubes. To obtain definite solutions, an extension of the original algorithm is proposed that recognizes the shape of the interpolation surface. For this purpose, decision paths are implemented that recognize and correctly assign saddle surfaces. Another approach to deal with erroneous parts in the surface is presented in [8] by X. Wang et al. The improvement is implemented by combining the surface results of adjacent individual cubes to determine the final shape. The algorithm detects common edges and uses this information throughout the whole surface generation process. Further improvements regarding the computation time of the algorithm are proposed by C. Henn et al. in [3]. Instead of calculating and storing the normal unit vectors in Cartesian coordinates, discretized polar coordinates are proposed. Since the length of the normal unit vectors is not needed in the later process, in polar coordinates, only two coordinates are necessary to receive all relevant information. In addition, the use of floating point numbers is omitted and, instead, the discretization of the space angles is proposed to reduce the memory requirements. Z. Xu et al. also introduce improvements to the calculation time in [9] by eliminating linearization and using the centroid of the cubes instead. According to the authors, this is permissible for high-resolution data spaces. In addition, calculations of cube vertices that are already calculated are omitted and edges are combined under special conditions, yielding an overall reduced calculation load. First named by G. Nielson in [10], the dual marching cubes algorithm (DMC) enables a higher resolution of the surface. The triangles created by the original algorithm are used to construct new surface patches. The new patches are formed using the centroids of four adjacent marching cube triangles, forming a new surface mesh. Authors S. Gong and T. S. Newman improve, in [11], the performance for two-dimensional data. R. Grosso and D. Zint enable, in [12], the algorithm to be calculated in parallel. Furthermore, to enable the algorithm to detect sharp edges within a cube, S. Gong and T. S. Newman implement, in [13,14], an extension of the marching cubes algorithm. Neighboring cubes are taken into account to detect sharp edges within one cube and the creation of the isosurface triangles is adopted accordingly. Another problem in the original algorithm is surface construction using too small or sharp triangles. This issue is solved by S. Raman and R. Wenger in [15] by taking cube vertices into account that are equal to the isovalue. This eventually leads to more patterns than the original 14 but yields a more robust surface construction. In [16], L. Custodio et al. apply the same approach to the marching cubes 33 algorithm. A further improvement in the reconstructed surface can be achieved, according to S. Gong and T. S. Newman in [17], by comparing the value of the estimated voxel with the original voxel. If deviations occur, a post-processing step can adjust the estimated voxel so that the original data are matched. Measured data that are subject to noise are the focus of the work of Y. He et al. in [18], where probability theory is used to improve the isovaluing result of noisy input data. Further literature for the marching cubes algorithm can be found in [19], while a compact summary of marching cubes algorithms can be obtained from Table 1.
原始的行进立方体算法是各种其他科学著作的主题。作者P. Shirley和A. Tuchman在[4]中提出了一种在线性化之前将立方体分解为四面体单元的方法，以提高计算效率。原始算法中的一个问题是图 3 中描绘的 14 种模式的模糊性。这最终会导致生成的三维对象中出现错误的伪影。 G. M. Nielson 和 B. Hamann 在 [5] 中提出的渐近决策器旨在获得精确解。双曲线用于确定不明确情况的精确解。另一方面，E. Chernyaev 在[6]中提出了 33 种模式，而不是 14 种，以充分描述行进立方体 33 算法（MC33）中的所有必要模式。在[7]中，B.K. Natarajan 展示了立方体内等值面的模糊性。为了获得确定的解，提出了原始算法的扩展来识别插值表面的形状。为此，实施了识别并正确分配鞍形表面的决策路径。 X. Wang 等人在 [8] 中提出了另一种处理表面错误部分的方法。该改进是通过组合相邻单个立方体的表面结果来确定最终形状来实现的。该算法检测公共边缘并在整个表面生成过程中使用该信息。C. Henn 等人在[3]中提出了进一步改进算法计算时间的方法。他们提出了离散极坐标，而不是以直角坐标计算和存储法线单位向量。由于后续过程中不需要法向单位向量的长度，因此在极坐标中，只需要两个坐标即可接收所有相关信息。此外，省略了浮点数的使用，而是提出了空间角度的离散化以减少内存需求。 Z.Xu等人。还通过消除线性化并使用立方体的质心来改进[9]中的计算时间。作者表示，这对于高分辨率数据空间是允许的。此外，已经计算过的立方体顶点的计算被省略，并且在特殊条件下组合边，从而总体上减少了计算量。双行进立方体算法 (DMC) 首次由 G. Nielson 在 [10] 中命名，可实现更高分辨率的表面。原始算法创建的三角形用于构造新的曲面片。新的面片是使用四个相邻的行进立方体三角形的质心形成的，从而形成新的表面网格。作者 S.Gong 和 T.S.Newman 在 [11] 中改进了二维数据的性能。 R. Grosso 和 D. Zint 在[12]中使算法能够并行计算。此外，为了使算法能够检测立方体内的锐利边缘，S.Gong 和 T.S.Newman 在[13,14]中实现了行进立方体算法的扩展。考虑相邻立方体来检测一个立方体内的尖锐边缘，并相应地采用等值面三角形的创建。原始算法中的另一个问题是使用太小或尖锐的三角形进行表面构造。 S. Raman 和 R. Wenger 在 [15] 中通过考虑等于等值的立方体顶点来解决这个问题。这最终会产生比最初 14 个更多的图案，但会产生更坚固的表面结构。在[16]中，L. Custodio 等人。对 Marching Cubes 33 算法应用相同的方法。根据 S.Gong 和 T.S.Newman 在 [17] 中的说法，通过将估计体素的值与原始体素进行比较，可以实现重建表面的进一步改进。如果出现偏差，后处理步骤可以调整估计的体素，以便与原始数据匹配。受噪声影响的测量数据是 Y. He 等人工作的重点。在[18]中，概率论用于改进噪声输入数据的等值结果。关于移动立方体算法的更多文献可以在 [19] 中找到，而移动立方体算法的简洁总结可以从表 1 中获得。
3. Tessellation-Based Algorithms
Tessellation-based algorithms have their origins in representing the inner surfaces of three-dimensional objects. For the first time, B. A. Payne and A. W. Toga introduced a tessellation-based method in [20], which aims to display the inner surfaces and functions of a human brain. This requires the outer surface, the subcortex, to be removed. To do this, a volume, the so-called minimum distance field, is first determined, where each point within the volume is assigned the minimum distance to the nearest point on the cortical surface as a value. The thresholding of the volume is then performed so that a set of surfaces with a constant minimum distance to the cortex is created. Then, the surface elements generated by thresholding are divided into connected components so that the desired inner surfaces are separated from the surfaces equidistant from the brain. The authors use a modified marching cubes algorithm for thresholding. Since the marching cubes algorithm can lead to ambiguous situations that can lead to topologically unconnected surfaces, each cube is divided into five tetrahedra and each tetrahedron through which the surface passes is then polygonized. As previously mentioned, the basic idea of building cubes of eight pixels each over two neighboring slices is therefore initially based on the marching cubes algorithm. In [20], the authors show that, apart from possible holes at the edges of the sampled field, the method produces topologically correct, closed surfaces that can then be subjected to both quantitative analysis and rendering.
In [21], J. Bloomenthal describes an algorithm for the polygonization of implicit surfaces. In the method, an initial cube is first centered on a surface point and then a new cube is generated on each face that contains corners with opposite polarity. If the entire surface contains cubes, the surface in each cube is approximated by one or two polygons. To do this, the cube is divided into five tetrahedra, which are then polygonized. The polygonization is based on a table that has an entry for every possible configuration. In contrast to the 256 entries with possible configurations in the marching cubes algorithm, there are only 16 entries when using tetrahedra. Each tetrahedral configuration produces either nothing, a triangle or a quadrilateral, i.e., two triangles, as shown in Figure 5.
In [22], A. Guéziec and R. Hummel present an approach, based on the algorithm of B. A. Payne and A. W. Toga, for the fast and efficient extraction and visualization of surfaces defined as isosurfaces in three-dimensional interpolated data. The surface is extracted as a collection of closed triangles, where each triangle is an oriented closed curve within a single tetrahedron. Thus, the entire surface is wrapped with triangles. A. Guéziec and R. Hummel have extended the algorithm in [23,24] in terms of surface simplification and the necessary memory capacity.
基于曲面细分的算法起源于表示三维物体的内表面。 B. A. Payne 和 A. W. Toga 在[20]中首次引入了基于曲面细分的方法，旨在显示人脑的内表面和功能。这需要去除外表面，即皮层下。为此，首先确定一个体积，即所谓的最小距离场，其中为该体积内的每个点分配到皮质表面上最近点的最小距离作为值。然后执行体积的阈值处理，以便创建一组与皮层具有恒定最小距离的表面。然后，通过阈值化生成的表面元素被分成连接的组件，使得所需的内表面与距大脑等距的表面分离。作者使用改进的行进立方体算法进行阈值处理。由于行进立方体算法可能会导致不明确的情况，从而导致拓扑不连接的表面，因此每个立方体被分为五个四面体，然后将表面穿过的每个四面体进行多边形化。如前所述，因此，在两个相邻切片上构建每个包含八个像素的立方体的基本思想最初基于行进立方体算法。在[20]中，作者表明，除了采样场边缘可能存在的孔之外，该方法还可以生成拓扑正确的封闭表面，然后可以对其进行定量分析和渲染。
在[21]中，J. Bloomenthal 描述了一种隐式曲面多边形化算法。在该方法中，初始立方体首先以表面点为中心，然后在每个面上生成包含极性相反的角的新立方体。如果整个表面包含立方体，则每个立方体中的表面由一个或两个多边形近似。为此，将立方体分为五个四面体，然后将其多边形化。多边形化基于一个表，该表具有针对每种可能的配置的条目。与行进立方体算法中具有可能配置的 256 个条目相比，使用四面体时只有 16 个条目。每个四面体配置要么什么也不产生，要么产生一个三角形，要么产生一个四边形，即两个三角形，如图 5 所示。
在[22]中，A. Guéziec 和 R. Hummel 提出了一种基于 B. A. Payne 和 A. W. Toga 算法的方法，用于快速有效地提取和可视化定义为三维插值数据中的等值面的表面。表面被提取为闭合三角形的集合，其中每个三角形都是单个四面体内的定向闭合曲线。因此，整个表面都被三角形包裹着。 A. Guéziec 和 R. Hummel 在表面简化和必要的内存容量方面扩展了[23,24]中的算法。
Y. Zhou et al. clarify in [25] that, despite the decomposition of the cubes into tetrahedra, the ambiguity problem has not yet been solved. Therefore, the authors propose a method of determining the intersection points and a criterion to test the intersection between the isosurface and the edge of the tetrahedron, which are based on the assumption that the function is linear along the edge of a cube. However, the authors deduce in [25] that there is a quadratic variation in the function value
f
(
t
)
f (t)
f(t) along the triangle edge
t
t
t, as can be seen in Equation (4).
Y. Zhou 等人在 [25] 中阐明，尽管已将立方体分解为四面体，但模糊性问题仍未解决。因此，作者提出了一种确定交点的方法和一种检验等值面与四面体边缘交点的标准，这些方法和标准都基于函数沿立方体边缘呈线性的假设。然而，作者在 [25] 中推导出函数值
f
(
t
)
f (t)
f(t) 沿着三角形边缘
t
t
t 存在二次变化，如等式 (4) 所示。
The values for
c
0
,
c
1
c_0, c_1
c0,c1 and
c
2
c_2
c2 are determined by the function values at the vertices. If one or both zeros of the function
are an element of the interval [0, 1], the isocontour with the isovalue C intersects the triangle edge. In addition, the connection of intersection points in the tetrahedra to construct the polygons and the triangulation of the polygons are discussed. They show that, with the proposed method, the isosurfaces are independent of the exact distribution of the tetrahedra resulting from the decomposition of the cubes.
c
0
、
c
1
c_0、c_1
c0、c1 和
c
2
c_2
c2 的值由顶点处的函数值确定。如果函数的一个或两个零点是区间 [0, 1] 的元素，则具有等值 C 的等值线与三角形边相交。此外，还讨论了四面体中交点的连接来构造多边形以及多边形的三角剖分。他们表明，使用所提出的方法，等值面与立方体分解产生的四面体的精确分布无关。
In [26], G. M. Nielson and R. Franke present an algorithm that computes a triangulated surface that separates a collection of data points segmented into several different classes instead of only two. The algorithm can be used for both structured, rectilinear and scattered data sets. For tetrahedrization, each cell is decomposed into five or six tetrahedra for structured data sets, while tetrahedrization is assumed for scattered data sets. However, the algorithm assumes that the data are already segmented.
在[26]中，G. M. Nielson 和 R. Franke 提出了一种计算三角曲面的算法，该三角曲面将数据点集合分成几个不同的类别，而不是仅分为两个类别。该算法可用于结构化、直线和分散数据集。对于四面体化，对于结构化数据集，每个单元被分解为五个或六个四面体，而对于分散数据集则假设四面体化。然而，该算法假设数据已经被分段。
Authors K. S. Bonnell et al. describe, in [27], a new algorithm for the reconstruction of material interfaces from data sets with volume fractions. The algorithm is based on a dual tetrahedral mesh constructed from the original mesh, where each vertex in the dual mesh is assigned an associated barycentric coordinate representing a fraction of each material present. The material boundaries are determined by mapping a tetrahedron into barycentric space and calculating the intersection points with Voronoi cells in barycentric space. These intersections are then mapped back into the original physical space and triangulated to approximate the surface boundary.
The so-called marching tetrahedra algorithm (MT) was developed and improved in parallel to the polygonization method already presented, where cubes are divided into tetrahedra. This method is also based on the basic idea of the marching cubes algorithm, but, unlike the polygonization method described above, it does not first create cubes, which are then divided into triangles, but the grid is divided directly into triangles. In the new method, which was first presented by S. L. Chan and E. O. Purisima in [28], the space is divided directly into tetrahedra to create a regular and symmetrical tessellation. This can be achieved by using a space-centered cubic grid, as shown in Figure 6. In this way, all tetrahedra have the same shape, even if they differ in orientation.
作者 K. S. Bonnell 等人。在[27]中描述了一种从具有体积分数的数据集重建材料界面的新算法。该算法基于从原始网格构建的双四面体网格，其中双网格中的每个顶点都分配有一个关联的重心坐标，表示存在的每种材料的一部分。通过将四面体映射到重心空间并计算与重心空间中的 Voronoi 单元的交点来确定材料边界。然后将这些交叉点映射回原始物理空间并进行三角测量以近似表面边界。
所谓的行进四面体算法（MT）是与已经提出的多边形化方法并行开发和改进的，其中立方体被划分为四面体。该方法同样基于行进立方体算法的基本思想，但是与上述多边形化方法不同，它不是先创建立方体，然后将其划分为三角形，而是将网格直接划分为三角形。在 S. L. Chan 和 E. O. Purisima 在[28]中首次提出的新方法中，空间被直接划分为四面体以创建规则且对称的镶嵌。这可以通过使用空间中心立方网格来实现，如图 6 所示。这样，所有四面体都具有相同的形状，即使它们的方向不同。
The tetrahedra thus obtained have two different types of edges, the longer ones, i.e., AB and CD, and the shorter ones, i.e., AC, AD, BC and BD, as shown in Figure 6. Each long edge is used in four tetrahedra and each short edge is used in six. In contrast to the 15 ways in which the surface can intersect a cube, there are only four with the tetrahedrons constructed in this way. The first case is that all vertices have the same state and the surface therefore does not intersect the tetrahedron. If one vertex has a different state from the other three, the surface can be constructed parallel to the triangle formed by the three vertices. If two vertices have the same state, there are two ways in which the surface can intersect the tetrahedron, whereby a quadrilateral surface element can be formed for both cases. The two cases are that the identical vertices can be connected either with a short or with a long edge. Another advantage is that the sampling efficiency is improved compared to using the standard cubic grid. However, the space-centered cubic grid is not available per se for applications that include a scan, so the values in the center of each cube must be interpolated.
由此获得的四面体有两种不同类型的边，较长的边，即AB和CD，以及较短的边，即AC、AD、BC和BD，如图6所示。每个长边用于四个四面体每个短边用了六个。与表面与立方体相交的 15 种方式相比，用这种方式构造的四面体只有四种。第一种情况是所有顶点具有相同的状态，因此表面不与四面体相交。如果一个顶点的状态与其他三个顶点不同，则可以将曲面构造为平行于由三个顶点形成的三角形。如果两个顶点具有相同的状态，则表面与四面体相交的方式有两种，由此两种情况都可以形成四边形表面单元。这两种情况是相同的顶点可以用短边连接，也可以用长边连接。另一个优点是与使用标准立方网格相比，采样效率得到了提高。然而，以空间为中心的立方网格本身不适用于包含扫描的应用程序，因此必须对每个立方体中心的值进行插值。
In [29], S. L. Chan and E. O. Purisima extend the marching tetrahedra algorithm for the generation and triangulation of molecular surfaces. The triangulated surface generated in this way can be used both for molecular graphic display and for boundary element continuum dielectric calculations. T. Lu and F. Chen present, in [30], an algorithm that has been improved in terms of computing time and employ it for a quantitative analysis of molecular surfaces.
As an extension to the original marching tetrahedra algorithm, authors G. M. Treece et al. proposed the regularized marching tetrahedra algorithm in [31]. The method combines the marching tetrahedra algorithm with the vertex clustering algorithm so that isosurfaces are generated that match the data topologically and, at the same time, contain an appropriate number of triangles with improved aspect ratios for the sampling resolution. This significantly reduces the number of triangles used to represent the surface and improves the smooth, shaded representation of the surface. The surface triangulations generated using the method are presented for implicit surfaces, medical data with thresholds and surfaces created from object cross-sections.
在[29]中，S. L. Chan 和 E. O. Purisima 扩展了行进四面体算法，用于分子表面的生成和三角化。以这种方法生成的三角化表面既可用于分子图形显示，也可用于边界元连续介质计算。T. Lu 和 F. Chen 在文献[30]中提出了一种在计算时间方面有所改进的算法，并将其用于分子表面的定量分析。
作为原始行进四面体算法的扩展，作者 G. M. Treece 等人在[31]中提出了正则化行进四面体算法。该方法将行进四面体算法与顶点聚类算法相结合，生成的等值面在拓扑结构上与数据相匹配，同时包含适当数量的三角形，并根据采样分辨率改进了长宽比。这大大减少了用于表示曲面的三角形数量，并改善了曲面的平滑、阴影表示。本文介绍了使用该方法生成的隐式曲面、带阈值的医疗数据以及由物体横截面生成的曲面三角剖面图。
In [32], A. Cong et al. propose the mulitregional marching tetrahedra method, which is used for the extraction of surface and volume meshes from segmented CT, micro-CT or MRI image volumes of a small experimental animal. The method is used to extract the triangulated surface mesh and construct a volumetric mesh for all anatomical components within a sweep over all segmented CT slices. Since the volume of all components is meshed with a finite element mesh, it can be used directly for finite element calculations. In addition, compared to the marching tetrahedra method, two further cases are considered during surface extraction within the tetrahedra and a seamless transition between anatomical components is ensured. The surface is then smoothed and simplified without losing the seamless transition. The method is used by the authors in bioluminescence tomography.
In [33], G. M. Nielson presents a further extension of the classical marching tetrahedra method, the dual marching tetrahedra method. The method is a generalization of the cuberille method from cubes to tetrahedra and is used to render surfaces in a three-dimensional space. The dual marching tetrahedra method solves a fundamental problem in the original cuberille method, in which the separating surfaces are not necessarily manifolds. The method can be used for both structured and unstructured point clouds.
V. d’Otreppe et al. use the marching tetrahedra method to generate smooth surface meshes from multi-region medical images. For this purpose, the marching tetrahedra method is extended in [34] for use in multi-domain data, so that multi-region meshes are generated as a set of triangular surface pieces that consistently connect to each other at the material boundaries, combined with a method for the reconstruction of implicit surfaces. With this mesh generation strategy, it is possible to produce surface meshes using triangles from segmented medical data sets with multiple tissues. In addition, the terracing artifacts are avoided by the smooth description of the tissue boundaries before triangulation.
在[32]中，A. Cong 等人。提出多区域行进四面体方法，用于从小型实验动物的分段 CT、显微 CT 或 MRI 图像体积中提取表面和体积网格。该方法用于提取三角表面网格，并为所有分段 CT 切片扫描内的所有解剖组件构建体积网格。由于所有部件的体积均采用有限元网格划分，因此可以直接用于有限元计算。此外，与行进四面体方法相比，在四面体内的表面提取过程中还考虑了两种情况，并确保了解剖组件之间的无缝过渡。然后对表面进行平滑和简化，同时不失无缝过渡。作者将这种方法用于生物发光层析成像。
在[33]中，G. M. Nielson 提出了经典行进四面体方法的进一步扩展，即双行进四面体方法。该方法是立方体方法从立方体到四面体的推广，用于渲染三维空间中的表面。双行进四面体方法解决了原始立方体方法中的一个基本问题，其中分离表面不一定是流形。该方法可用于结构化和非结构化点云。
V. d’Otreppe 等人。使用行进四面体方法从多区域医学图像生成平滑的表面网格。为此，在[34]中扩展了行进四面体方法以用于多域数据，以便将多区域网格生成为一组在材料边界处一致相互连接的三角形表面片，并结合一种隐式曲面重建方法。通过这种网格生成策略，可以使用来自多个组织的分段医学数据集的三角形来生成表面网格。此外，通过在三角测量之前平滑描述组织边界，可以避免梯田伪影。
T. Shen et al. pursue a deep learning approach for high-resolution three-dimensional shape synthesis in [35], where the marching tetrahedra method is integrated into the deep learning framework. In the proposed approach, implicit and explicit surface representations are combined and the quality of shape synthesis is improved by the additional supervision defined directly on the extracted surface from the implicit field.
Further research on the use of the marching tetrahedra method in the field of geological modeling can be found in [36,37].
Another approach to determining isocontours in the field of tessellation-based algorithms comprises methods incorporating the triangulation of the point cloud to be analyzed. In [38], C. L. Bajaj et al. present a fast isocontouring algorithm for scalar volume data. In a preprocessing step, seed cells are selected so that at least one cell per connected component of each isocontour is present. For the given isovalue, all cells of the previously defined seed cells that intersect the isocontour are then extracted. This leads to a significant reduction in calculation complexity.
Another mesh-based method of approximating isocontours in a three-dimensional scalar field is the RooTri() function, introduced by J. Oellerich et al. in [39]. A specific feature of the proposed algorithm is that unstructured three-dimensional point clouds can be processed. Furthermore, intersection points with an arbitrarily oriented plane can be determined. First, the unstructured three-dimensional point cloud is projected onto a two-dimensional plane so that the third component describing the variable under investigation is neglected for each point. The point cloud is then triangulated using Delaunay triangulation. Subsequently, each triangular vertex, i.e., each point from the point cloud, is again supplemented by the corresponding third component. This creates a three-dimensional, triangulated surface, as shown in Figure 7.
TT. Shen 等人在论文[35]中提出了一种用于高分辨率三维形状合成的深度学习方法，将行进四面体方法集成到深度学习框架中。在所提出的方法中，隐式和显式表面表示相结合，并通过直接对从隐式场提取的表面进行额外监督来提高形状合成的质量。
关于在地质建模领域使用行进四面体方法的进一步研究，可参见文献[36,37]。
在基于镶嵌的算法领域，另一种确定等值线的方法包括结合待分析点云的三角剖分法。在 [38] 中，C. L. Bajaj 等人提出了一种用于标量体积数据的快速等值线算法。在预处理步骤中，选择种子单元，以便每个等值线的每个连接分量至少有一个单元存在。然后，针对给定的等值线，提取与等值线相交的先前定义的种子单元中的所有单元。这大大降低了计算复杂度。
J. Oellerich 等人在文献[39]中提出了另一种基于网格的三维标量场等值线近似方法，即 RooTri() 函数。该算法的一个特点是可以处理非结构化的三维点云。此外，还可以确定与任意方向平面的交点。首先，将非结构化三维点云投影到二维平面上，从而忽略每个点的描述变量的第三分量。然后使用 Delaunay 三角剖分法对点云进行三角剖分。随后，每个三角形顶点，即点云中的每个点，都会再次补充相应的第三分量。这样就形成了一个三维三角剖分曲面，如图 7 所示。
Next, the method verifies whether there is an intersection point with the plane for each triangle generated in this way. To do this, we proceed as shown in Figure 8 for each triangle, interpolating linearly between the vertices
v
1
,
v
2
v_1, v_2
v1,v2 and
v
3
v_3
v3.
Using the vertices
v
j
v_j
vj (or the edge midpoints
a
j
a_j
aj),
j
∈
{
1
,
2
,
3
}
j ∈ \{1, 2, 3\}
j∈{1,2,3} of the k-th triangle, it is possible to set up the vectors
t
j
,
j
∈
{
1
,
2
,
3
}
tj, j ∈ \{1, 2, 3\}
tj,j∈{1,2,3}, as in Equations (5)–(7).
接下来，该方法验证以此方式生成的每个三角形是否与平面存在交点。为此，我们对每个三角形按图 8 所示进行操作，在顶点
v
1
、
v
2
v_1、v_2
v1、v2 和
v
3
v_3
v3 之间进行线性插值。
使用第 k 个三角形的顶点
v
j
v_j
vj （或边中点
a
j
a_j
aj），
j
∈
{
1
,
2
,
3
}
j ∈ \{1, 2, 3\}
j∈{1,2,3}，可以建立向量 KaTeX parse error: Expected '}', got 'EOF' at end of input: … ∈ \ {1, 2, 3\}，如等式(5)–(7)。
Here,
λ
∈
[
0
,
1
]
λ ∈ [0, 1]
λ∈[0,1] applies. Inserting the plane in coordinate form
and solving for lambda leads to
Substituting
λ
λ
λ from Equation (8) into Equations (5)–(7) results in the coordinates
of the intersection point. If λ ∗ \lambda^∗ λ∗ is an element of the interval [0, 1], it is a valid intersection point. The code is implemented by the authors in vectorized form, which significantly increases the performance of the algorithm, although each triangle must be checked for intersection points. The validity of the algorithm is checked by comparing it with the contourc() function provided by MATLAB©. In addition to the quality of the results obtained, the number of intersections calculated, the time required and the estimated memory requirements are moreover considered for various functions. In addition to the significantly higher quality of the intersection points, RooTri() also has a significantly greater number of intersection points, which simplifies the determination of connected isocontours. Furthermore, RooTri() is, on average, 12.85 % faster than contourc() and requires only half the memory. The use of the algorithm is not limited to the analysis of functions, but it can also be used in the evaluation of unstructured data, such as in measurements. In [39], the algorithm was used to evaluate the measurement results of a permanently excited synchronous machine. Equipotential lines of constant torque were determined. Another use case of the algorithm is topology optimization, which is a subarea of structural optimization. The aim here is to find a suitable material distribution within a given design domain. With the help of RooTri(), zeros of a higher-dimensional scalar function can be determined that correspond to the material boundary.
如果
λ
∗
\lambda^∗
λ∗ 是区间 [0, 1] 的元素，则它是有效的交点。该代码由作者以矢量化形式实现，这显着提高了算法的性能，尽管必须检查每个三角形的交点。通过与MATLAB©提供的contourc()函数进行比较来检验算法的有效性。除了获得的结果的质量之外，还考虑了各种功能所计算的交叉点数量、所需时间和估计的内存需求。除了交点质量显着提高之外，RooTri() 还具有显着更多的交点数量，这简化了连接等值线的确定。此外，RooTri() 平均比 Contourc() 快 12.85%，并且只需要一半的内存。该算法的用途不仅限于函数分析，还可以用于非结构化数据的评估，例如测量。在[39]中，该算法用于评估永磁同步电机的测量结果。确定了恒扭矩的等势线。该算法的另一个用例是拓扑优化，它是结构优化的一个子领域。这里的目的是在给定的设计领域内找到合适的材料分布。借助 RooTri()，可以确定与材料边界相对应的高维标量函数的零点。
Research on the extraction and compression of hierarchical isocontours from image data using dynamic tessellation can be reviewed in the papers [40,41] of T. Lewiner et al. In [42], a computational framework for two-dimensional shape-enclosing contours based on the application of Delaunay tessellation is presented by B. R. Schlei. Research on the use of tessellation-based methods for terrain models and topography can be found in [43,44]. A summary of the tessellation-based algorithms cited in this work can be found in Table 2.
T. Lewiner 等人的论文 [40,41] 综述了使用动态细分从图像数据中提取和压缩分层等值线的研究。在[42]中，B. R. Schlei 提出了一种基于 Delaunay 曲面细分应用的二维形状包围轮廓的计算框架。关于使用基于曲面细分的方法进行地形模型和地形的研究可以在[43,44]中找到。表 2 总结了本工作中引用的基于曲面细分的算法。
Figure 7. Basic approach of the RooTri() function from [39]: ➀ three-dimensional point cloud
P
P
P and defined contour level, ➁ projection of the point cloud onto the original plane to obtain the set
P
′
P ′
P′, ➂ Delaunay triangulation of the point cloud to receive triangle set
K
K
K, ➃ re-adding the z-component to each triangle vertex
k
∈
K
k ∈ K
k∈K.
图 7. [39] 中 RooTri() 函数的基本方法： ➀ 三维点云 P P P 和定义的轮廓水平，➁ 将点云投影到原始平面上以获得集合 P ′ P ′ P′，➂对点云进行 Delaunay 三角剖分以接收三角形集 K K K，➃ 将 z 分量重新添加到每个三角形顶点 k ∈ K k ∈ K k∈K。
4. Surface Nets Algorithms
The surface nets algorithm was first presented by S. F. F. Gibson in [45] for the creation of a globally smooth surface model from a set of three-dimensional data points. The method is commonly used in computer graphics, e.g., medical imaging, and computational geometry to create smooth surfaces from binary segmented data. The advantage of this method is its simplicity and effectiveness, which makes it a popular choice for the creation of surface models from structured three-dimensional point clouds, such as binary-segmented MRI or CT image volumes. However, it may not always produce the most accurate or detailed meshes, especially in regions with complex geometry or high curvature. Overall, this method follows a similar approach to the marching cubes algorithm in the initial steps. Nevertheless, the two methods differ with regard to the exact determination of the surface area within a cube.
The basic idea of the surface nets algorithm is to link the surface nodes of the binarysegmented volume and relax the node positions within a given dimension in such a way that a smooth surface is generated. The linked surface nodes form the surface nets. To generate the surface net, the first step is to find the surface nodes in the data. To do this, the three-dimensional point cloud is first divided into cubes with eight voxels each. If all eight voxels have the same binary value, this means that the cube is either completely inside or outside the object. If at least one voxel has a different binary value from its neighbors, then the surface travels through this cube. A node is placed in the centroid of all cubes through which the surface travels and connected to the node in the neighboring surface cubes to create the surface net; see Figure 9a. One node can thereby have up to six connections. The positions of the nodes of the surface net are then iteratively relaxed so that an energy measure in the links is reduced. Here, the energy E is determined in [46] by the sum of the length of the connections between the nodes within a surface net, as shown in Equation (9).
表面网络算法最初由 S. F. F. Gibson 在 [45] 中提出，用于从一组三维数据点创建全局平滑的表面模型。该方法通常用于计算机图形学（例如医学成像）和计算几何中，以从二进制分段数据创建平滑表面。该方法的优势在于其简单性和有效性，这使其成为从结构化三维点云（例如二进制分段 MRI 或 CT 图像体积）创建表面模型的流行选择。然而，它可能并不总是产生最准确或最详细的网格，特别是在具有复杂几何形状或高曲率的区域。总体而言，该方法在初始步骤中遵循与行进立方体算法类似的方法。然而，这两种方法在立方体内表面积的精确测定方面有所不同。
表面网络算法的基本思想是将二元分段体积的表面节点链接起来，并松弛给定维度内的节点位置，从而生成光滑的表面。链接的表面节点形成表面网络。要生成表面网络，第一步是查找数据中的表面节点。为此，首先将三维点云划分为每个包含八个体素的立方体。如果所有八个体素都具有相同的二进制值，则意味着立方体要么完全在对象内部，要么完全在对象外部。如果至少一个体素与其相邻体素具有不同的二进制值，则表面穿过该立方体。将节点放置在表面经过的所有立方体的质心中，并连接到相邻表面立方体中的节点以创建表面网；见图 9a。因此，一个节点最多可以有六个连接。然后迭代地放松表面网络的节点的位置，从而减少链路中的能量测量。这里，能量 E 在[46]中由表面网络内节点之间的连接长度之和确定，如方程（9）所示。
In this connection,
(
x
1
,
y
1
,
z
1
)
(x_1, y_1, z_1)
(x1,y1,z1) and
(
x
2
,
y
2
,
z
2
)
(x_2, y_2, z_2)
(x2,y2,z2) describe the two linked nodes and n represents all links within a surface net. Subsequently, the total energy is reduced by reducing the length of all links in a surface net and a local minimum of energy is achieved by moving the nodes to a position between two neighboring nodes, as shown in Equation (10) for node i.
在这方面，
(
x
1
,
y
1
,
z
1
)
(x_1, y_1, z_1)
(x1,y1,z1) 和
(
x
2
,
y
2
,
z
2
)
(x_2, y_2, z_2)
(x2,y2,z2) 描述两个链接节点，n 表示表面网络内的所有链接。随后，通过减少表面网络中所有链接的长度来减少总能量，并通过将节点移动到两个相邻节点之间的位置来实现能量的局部最小值，如节点 i 的方程（10）所示。
The number of neighboring links for node i is described here via
N
i
N_i
Ni. However, a node can only be moved within the surface cube in which it was defined, in order to remain true to the original segmentation; see Figure 9b. This makes it possible to reduce the aliasing and terracing artifacts on the surface. In contrast to the marching cubes algorithm, the surfaces in the surface nets algorithm are not drawn arbitrarily through the surface cubes, which have identical elements at the opposite corners. In marching cubes, there are two different ways in which the surface can run through the cube, which leads to topologically different surfaces; see Figure 9➀,➁. One of the two possibilities is chosen arbitrarily. In surface nets, the surface is pinched at the net node, whereby the surface is neither divided nor connected; see Figure 9➂. Since the topological decision is not made arbitrarily, it is possible that higher-level algorithms can be used to separate or connect the surface at the ambiguous points after smoothing. S. F. F. Gibson shows, in [45], that the surface nets algorithm is capable of generating relatively smooth surfaces for curved objects and sharp corners for rectangular objects, as well as obtaining thin structures and cracks. The smoothed surface net can then be triangulated to create a three-dimensional surface model. To render these surfaces, distance maps are determined from the triangulated surface, which can be determined from the distance of the respective point from the distance map to the next surface triangle. S. F. F. Gibson later patented the approach for the calculation of isosurfaces from binary-segmented data and the subsequent smoothing of these surfaces in [46].
节点 i 的相邻链路数量在此通过 N i N_i Ni 进行描述。然而，节点只能在定义它的表面立方体内移动，以保持原始分割；见图 9b。这使得减少表面上的锯齿和阶梯伪影成为可能。与行进立方体算法相比，表面网络算法中的表面不是通过表面立方体任意绘制的，表面立方体在对角处具有相同的元素。在行进立方体中，表面可以通过两种不同的方式穿过立方体，从而导致拓扑不同的表面；参见图 9➀,➁。任意选择两种可能性之一。在表面网络中，表面在网络节点处被挤压，因此表面既不分开也不连接；参见图 9➂。由于拓扑决策不是任意做出的，因此可以使用更高级别的算法在平滑后的模糊点处分离或连接表面。 S.F.F.Gibson 在[45]中表明，表面网络算法能够为弯曲物体生成相对光滑的表面，为矩形物体生成尖角，以及获得薄结构和裂缝。然后可以对平滑的表面网进行三角测量以创建三维表面模型。为了渲染这些表面，根据三角化表面确定距离图，可以根据从距离图到下一个表面三角形的相应点的距离来确定距离图。 S. F. F. Gibson 后来在[46]中获得了根据二进制分段数据计算等值面以及随后对这些表面进行平滑处理的方法的专利。
In [47], S. F. F. Gibson used the distance maps generated with the surface nets algorithm to comprehensively demonstrate its quality and effectiveness for surface reconstruction in sampled volumetric data. This is shown primarily using the example of medical images from MRI or CT data. For this purpose, the values for the distance to the nearest surface are mapped to each sample point and the surface is reconstructed using the zero value of the distance map.
在[47]中，S.F.F.Gibson使用表面网络算法生成的距离图全面证明了其在采样体积数据中表面重建的质量和有效性。这主要通过 MRI 或 CT 数据的医学图像示例来说明。为此，将到最近表面的距离值映射到每个采样点，并使用距离图的零值重建表面。
Figure 9. Qualitative illustration of the surface nets algorithm based on [45]. (a) The underlying net with linked surface nodes in the center of each surface cube. (b) The relaxed net with smoothed out terraces. ➀ and ➁ Possible surface constructions for a two-dimensional surface cube with matched diagonal elements, whereby one of the two topologies is selected arbitrarily in marching cubes. ➂ In surface nets, the surface is pinched together at the ambiguous node point.
图 9. 基于 [45] 的表面网络算法的定性说明。 (a) 每个表面立方体中心具有链接表面节点的底层网络。 (b) 经过平滑处理的松弛网。 ➀ 和 ➁ 具有匹配对角线元素的二维表面立方体的可能表面结构，其中在行进立方体中任意选择两种拓扑之一。 ➂ 在表面网络中，表面在不明确的节点处被挤压在一起。
M. E. Leventon and S. F. F. Gibson present, in [48], the dual surface nets algorithm, which combines two orthogonal scans. In this way, a model can be generated with a higher resolution than with both scans alone. This reduces the most severe artifacts, caused by a low sampling rate between image slices of a scan, which is important in the field of medical diagnosis, treatment, surgical guidance and surgical simulation. To achieve this, the two scans are first registered to each other and then a net of connected surface nodes is initialized for each of the two scans.
An extension of the surface nets algorithm with regard to the quality of the triangular mesh is proposed in [49] by the authors P. W. de Bruin et al. The increase in mesh quality is achieved by first moving the nodes in the direction of the isosurface and then distributing them as evenly as possible. The high quality of the triangular mesh is important for a finite element analysis, which is also used in the field of surgical simulations for the calculation of soft tissue deformations. The mesh is generated from MRI or CT image data. The authors conclude that the meshes generated with the extended surface nets algorithm are better suited for finite element modeling than those generated with a marching cubes algorithm.
M.E.Leventon 和 S.F.F.Gibson 在[48]中提出了双表面网络算法，该算法结合了两个正交扫描。通过这种方式，可以生成比单独两次扫描具有更高分辨率的模型。这减少了由扫描图像切片之间的低采样率引起的最严重的伪影，这在医学诊断、治疗、手术指导和手术模拟领域非常重要。为了实现这一点，首先将两个扫描相互配准，然后为两个扫描中的每一个初始化连接的表面节点的网络。
作者 P. W. de Bruin 等人在 [49] 中提出了关于三角形网格质量的表面网络算法的扩展。网格质量的提高是通过首先沿等值面方向移动节点，然后尽可能均匀地分布它们来实现的。三角网格的高质量对于有限元分析非常重要，有限元分析也用于手术模拟领域，用于计算软组织变形。网格是根据 MRI 或 CT 图像数据生成的。作者得出的结论是，使用扩展表面网络算法生成的网格比使用行进立方体算法生成的网格更适合有限元建模。
In [50], J. S. H. Baxter et al. demonstrate a unified framework for voxel classification and triangulation for medical images, allowing surface meshes for different anatomical structures to be generated in one process. In the proposed method, for volumetric data, the voxels are labeled by a two-dimensional classification function based on the voxel intensity and gradient. The surface nets algorithm, which is modified with respect to the reduction of image artifacts and a relaxation criterion for the surface nodes, is integrated into the classification function. Thus, the method enables the fast visualization of a suitable surface model of the anatomical structure.
In [51], S. F. F. Frisken extends the original three-dimensional surface nets algorithm for medical images consisting of several materials represented as indexed labels. The author states that the presented extension of the surface nets algorithm produces smooth, highquality triangle meshes that are suitable for rendering and tetrahedralization and preserves the topology and sharp boundaries between materials. The method also guarantees user-defined accuracy and ensures efficient processing. Further research work and application examples for the surface nets algorithm can be found in [52–54]. A summary of the main results regarding the surface nets algorithms can be found in Table 3.
在[50]中，J. S. H. Baxter 等人。展示了一种用于医学图像体素分类和三角测量的统一框架，允许在一个过程中生成不同解剖结构的表面网格。在所提出的方法中，对于体积数据，通过基于体素强度和梯度的二维分类函数来标记体素。表面网络算法针对图像伪影的减少和表面节点的松弛标准进行了修改，并集成到分类功能中。因此，该方法能够快速可视化解剖结构的合适表面模型。
在[51]中，S.F.F.Frisken 扩展了原始的三维表面网络算法，用于由几种表示为索引标签的材料组成的医学图像。作者指出，所提出的表面网络算法的扩展可生成平滑、高质量的三角形网格，适合渲染和四面体化，并保留拓扑结构和材料之间的清晰边界。该方法还保证了用户定义的精度并确保高效处理。表面网络算法的进一步研究工作和应用示例可以在[52-54]中找到。表 3 总结了有关表面网络算法的主要结果。
5. Ray Tracing Algorithms
In connection with the algorithms described previously, a related class of methods is often used for the visual representation of primarily three-dimensional scenes. The socalled ray tracing techniques are a frequently used method in the field of computer graphics for the generation of realistic light and shadow effects and thus contribute to a realistic representation of three-dimensional objects, as is the case with rendering, for example. Accordingly, the calculation of the isosurfaces precedes the application of ray tracing, but this method certainly offers added value with regard to the visual representation of simulation results, for instance. The basic idea of ray tracing is to expose the (previously calculated) isosurfaces to artificial light rays from a virtual light source and to observe the course of the light rays in order to determine the lighting conditions in the image; see Figure 10.
In the first step, the image is divided into pixels, whereby a ray is generated for each pixel of the image. Here, the ray is described by a parameterized line in Equation (11), which is defined by two points
x
1
,
x
2
∈
R
d
,
d
∈
2
,
3
x_1, x_2 ∈ R^d, d ∈ {2, 3}
x1,x2∈Rd,d∈2,3 and a scaling factor
λ
∈
R
λ ∈ R
λ∈R [55].
结合先前描述的算法，一类相关的方法通常用于主要三维场景的视觉表示。所谓的光线追踪技术是计算机图形学领域中经常使用的用于生成真实光影效果的方法，因此有助于真实地表示三维对象，例如渲染的情况。因此，等值面的计算先于光线追踪的应用，但这种方法无疑在例如模拟结果的视觉表示方面提供了附加值。光线追踪的基本思想是将（先前计算的）等值面暴露于来自虚拟光源的人造光线，并观察光线的路径以确定图像中的照明条件；参见图 10。
第一步，将图像划分为像素，从而为图像的每个像素生成一条光线。这里，射线由方程（11）中的参数化线描述，该线由两个点
x
1
,
x
2
∈
R
d
,
d
∈
2
,
3
x_1, x_2 ∈ R^d, d ∈ {2, 3}
x1,x2∈Rd,d∈2,3 和缩放因子
λ
∈
R
λ ∈ R
λ∈R [55 ]。
This ray then travels from the viewer through the pixel into the respective scene and represents the viewer’s line of sight. The generated rays are of particular importance in this context, as they are used to calculate the light and shadow ratios. The rays are followed as they propagate through the scene and their interaction with the objects in the scene is observed. Here, we are particularly interested in where the ray intersects the corresponding scene. In the event that the ray has crossed an object in the scene, it is then checked whether this point is in shadow. This is done by determining whether the point is illuminated by a light source. If, for example, an obstacle blocks the direct connecting line between the point and the light source, the point is in the shadow. In the event that the point is not in shadow, lighting calculations are subsequently carried out that take into account, among other aspects, the incident ambient light and the effects caused by the irradiation of direct and indirect light resulting from reflections. Other influencing variables in this context are, for example, the surface properties, which take into account the respective color tones and the reflexion coefficients. The stored reflexion coefficients can be used to determine whether the ray hits a reflective surface. If this is the case, a new reflexion ray is generated and the entire process is repeated for this ray. For transparent materials, on the other hand, a refracted ray is generated. The calculated color values for each ray are accumulated to obtain the final color value for the pixel. In the event that reflections or refractions occur, the described process is continued recursively, which means that, for each reflected or refracted ray, the ray tracing process is performed again. The entire process is then repeated for each pixel on the image surface to obtain the final image. As mentioned above, the ray tracing method offers the possibility of displaying realistic scenes. However, this is counteracted by the high level of computational effort.
然后，这条光线从观看者穿过像素进入相应的场景，并代表观看者的视线。生成的光线在这种情况下特别重要，因为它们用于计算光影比。当光线在场景中传播时，我们会对其进行跟踪，并观察它们与场景中对象的相互作用。在这里，我们特别感兴趣的是光线与相应场景相交的位置。如果光线穿过场景中的对象，则检查该点是否在阴影中。这是通过确定该点是否被光源照亮来完成的。例如，如果障碍物阻挡了该点和光源之间的直接连接线，则该点位于阴影中。如果该点不在阴影中，则随后执行照明计算，该计算除其他方面外还考虑了入射环境光以及由反射产生的直接和间接光的照射所造成的影响。在本文中，其他影响变量例如是表面特性，其考虑了相应的色调和反射系数。存储的反射系数可用于确定光线是否击中反射表面。如果是这种情况，则会生成新的反射光线，并针对该光线重复整个过程。另一方面，对于透明材料，会产生折射射线。将计算出的每条光线的颜色值累加以获得像素的最终颜色值。如果发生反射或折射，则递归地继续所描述的过程，这意味着对于每条反射或折射的光线，再次执行光线追踪过程。然后对图像表面上的每个像素重复整个过程以获得最终图像。如上所述，光线追踪方法提供了显示真实场景的可能性。然而，这被高水平的计算工作所抵消。
In this context, it can be stated that the technique of ray tracing is the subject of current research work, with the first preliminary work in this field having been carried out by A. Appel [56] and intensified in the 1980s, especially by T. Whitted [57]. At that time, the potential of the method was already recognized, but it was hindered by the intensive computational effort required. For this reason, the initial research work in this field focused on developing approaches to reduce the computational cost. For example, J. Amanatides and A. Woo present, in [58], a simplified method to reduce the computational effort and introduce an incremental transversal algorithm; see Figure 11. The idea is to first identify the voxel in which the ray origin lies and then determine the value at which the ray passes the boundary of the first vertical voxel.
在这种情况下，可以说射线追踪技术是当前研究工作的主题，A. Appel [56]首先在这一领域开展了初步工作，20 世纪 80 年代，特别是 T. Whitted [57]加强了这一工作。当时，人们已经认识到这种方法的潜力，但由于需要大量的计算工作而受到阻碍。因此，该领域最初的研究工作主要集中在开发降低计算成本的方法上。例如，J. Amanatides 和 A. Woo 在文献[58]中提出了一种简化方法来减少计算量，并引入了增量横向算法；见图 11。其思路是首先确定射线原点所在的体素，然后确定射线通过第一个垂直体素边界的值。
An identical step is performed for the other spatial direction. The minimum of both calculated values then indicates the extent to which it is possible to move along the beam without leaving the voxel.
In their work, the authors S. Parker et al. show how the isosurface of an object can be determined using the ray tracing method on the basis of analytical approaches [59]. The ray under consideration is interpreted as a vector. Each cell is checked to determine whether its data range is bounded by a defined isovalue. If this is the case, an analytical calculation is performed to determine the ray parameter t that defines the intersection point. The entire procedure is then carried out for all cells. To validate the procedure, the authors apply the method developed to the Visible Woman data set [60].
Y. Livnat and C. Hansen present, in [61], a ray tracing method to visualize the polygonal isosurface of the visible part of the isosurface. In the first phase, coarse visibility tests are performed to identify the visible cells. The visible parts of the extracted triangles are then resolved and processed by the graphics hardware.
The possible integration of implicit kd-trees ([62], p. 99) for the determination of the isosurface and simultaneous rendering is presented by I. Wald et al. in [63]. Here, Figure 12 illustrates the method.
对于另一个空间方向执行相同的步骤。两个计算值的最小值表示在不离开体素的情况下可以沿光束移动的程度。
在他们的工作中，作者 S. Parker 等人。展示了如何使用基于分析方法的光线追踪方法来确定物体的等值面[59]。所考虑的射线被解释为矢量。检查每个单元格以确定其数据范围是否受定义的等值限制。如果是这种情况，则执行分析计算以确定定义交点的光线参数 t。然后对所有单元执行整个过程。为了验证该过程，作者将开发的方法应用于 Visible Woman 数据集 [60]。
Y. Livnat 和 C. Hansen 在 [61] 中提出了一种光线追踪方法，用于可视化等值面可见部分的多边形等值面。在第一阶段，进行粗略可见性测试以识别可见细胞。然后，提取的三角形的可见部分由图形硬件解析和处理。
I. Wald 等人提出了用于确定等值面和同步渲染的隐式 kd 树（[62]，第 99 页）的可能集成。在[63]中。此处，图 12 说明了该方法。
图 12. 基于 [63] 的 kd-tress 在光线追踪中的应用：(a) 传统方法，(b) 利用 kd-tree 的特性跳过大的空白区域。
The idea of the approach essentially consists of two parts: on the one hand, a kd-tree contains information about which isosurfaces are contained and a modified transversal algorithm runs through the kd-tree and also implicitly classifies whether the corresponding node contains the defined isovalue. This also allows large empty areas to be skipped more quickly, which is also adressed by N. Morrical et al. in [64]. Therefore, the method presented has the advantage that it requires less memory than conventional methods. An extension of the approach can be found in [65]. Further applications of kd-trees can be found in [1,66–68], for example. Another alternative for the efficient handling of large data sets is the use of so-called octree-based, hierarchical data structures. As indicated in their name, octrees describe the recursive decomposition of a space into eight sub-volumes (or four cells in the two-dimensional case). The root of the octree represents the entire volume; see Figure 13.
该方法的思想本质上由两部分组成：一方面，kd 树包含有关包含哪些等值面的信息，修改后的横向算法贯穿 kd 树，并隐式分类相应节点是否包含定义的等值。这还允许更快地跳过大的空白区域，N. Morrical 等人也解决了这一问题。在[64]中。因此，所提出的方法具有比传统方法需要更少内存的优点。该方法的扩展可以在[65]中找到。例如，kd 树的进一步应用可以在 [1,66–68] 中找到。有效处理大型数据集的另一种选择是使用所谓的基于八叉树的分层数据结构。正如其名称所示，八叉树描述了将空间递归分解为八个子体（或二维情况下的四个单元）。八叉树的根代表整个体；参见图 13。
Research on the use of octree-based approaches can be found in [69–72]. A. Knoll et al. present, in [73], an approach based on an octree volume format and a traversal method that allows the faster ray tracing of compressed scalar volume data. The method is particularly suitable for large volume data, whereas GPU volume renderers are preferable for smaller volume data, according to the authors. In [74], a further development of the procedure is described.
In [75], authors B. Nelson and R. M. Kirby develop a ray tracing isosurface algorithm for spectral/hp element methods, which are higher-order finite element methods. The method can be used to both quantify and minimize the visualization error that occurs. The intersection point between the ray and the isosurface is determined on the basis of analytical methods. The advantage of this method is that the polynomial approximation can be adapted to the true solution as precisely as required. In addition, the convergence speed is higher than with other classical low-order methods, such as marching cubes algorithms.
To process unstructured data sets, P. Rosenthal and L. Linsen present an approach in [76] that is based on the use of partial differential equations (PDE). The advantage of the method is that no resampling of the data or mesh generation is required. The authors use the information regarding the neighborhood relationships to estimate the gradients and mean curvature at each individual sampling point using a four-dimensional least-square fitting approach, as these are necessary for the use of the PDE-based method.
In [77], A. Schollmeyer and B. Froehlich propose a method of determining the isosurface that incorporates a NURBS-based isogeometric analysis. The main aspects of the novel approach include a ray generation scheme that only generates rays that tend to contribute to the subsequent image creation. In addition, there is a method to determine all intersection points of the rays with the curved surface and a solution approach for memory management. In the course of validating the method, the authors find that the approach that they present is both faster and more accurate than GPU-based ray casting approaches. Further research work in the field of ray tracing can be found in [78–80]. Table 4 provides a condensed overview of the ray tracing methods described in the literature.
关于使用基于八叉树的方法的研究可以在[69-72]中找到。 A.诺尔等人。在[73]中提出了一种基于八叉树体积格式和遍历方法的方法，该方法允许更快地对压缩标量体积数据进行光线追踪。作者表示，该方法特别适合大容量数据，而 GPU 体渲染器更适合小容量数据。在[74]中，描述了该过程的进一步发展。
在[75]中，作者 B. Nelson 和 R. M. Kirby 开发了一种用于谱/hp 元方法（高阶有限元方法）的光线追踪等值面算法。该方法可用于量化和最小化发生的可视化误差。射线与等值面之间的交点是根据解析方法确定的。该方法的优点是多项式近似可以根据需要精确地适应真实解。此外，收敛速度高于其他经典的低阶方法，例如行进立方体算法。
为了处理非结构化数据集，P. Rosenthal 和 L. Linsen 在 [76] 中提出了一种基于使用偏微分方程 (PDE) 的方法。该方法的优点是不需要对数据进行重采样或网格生成。作者使用有关邻域关系的信息，使用四维最小二乘拟合方法来估计每个单独采样点的梯度和平均曲率，因为这些对于使用基于偏微分方程的方法是必要的。
在[77]中，A. Schollmeyer 和 B. Froehlich 提出了一种确定等值面的方法，该方法结合了基于 NURBS 的等几何分析。该新颖方法的主要方面包括一种光线生成方案，该方案仅生成有助于后续图像创建的光线。此外，还有一种确定光线与曲面的所有交点的方法和一种内存管理的解决方法。在验证该方法的过程中，作者发现他们提出的方法比基于 GPU 的光线投射方法更快、更准确。光线追踪领域的进一步研究工作可以在[78-80]中找到。表 4 提供了文献中描述的光线追踪方法的简要概述。
6. Proposed Future Research Activities
The investigation carried out in this paper shows that the assessment of the suitability of the algorithms presented is primarily based on a quantitative analysis in the form of a visual representation of the results. This is mainly the consequence of the original objective for the respective application. Another criterion that is often the subject of evaluation is the computing capacity required, as large volumes of data are usually analyzed. This applies in particular to ray tracing methods.
However, we note that there is no general scheme for the evaluation of the developed algorithms according to a defined standard. We therefore propose, as future research work, to develop and establish a standardized test procedure in order to be able to generate reliable statements regarding the performance of the procedures to be examined with regard to the fulfillment of the task described in Definition 1 and to create a basis for the comparison of the individual procedures. In the field of numerics, the following categories are of particular interest, which we propose as evaluation criteria for isocontouring methods:
• condition;
• stability;
• consistency; and
• convergence.
本文进行的调查表明，对所提出算法的适用性的评估主要基于结果的可视化表示形式的定量分析。这主要是各个应用程序最初目标的结果。另一个经常成为评估主题的标准是所需的计算能力，因为通常要分析大量数据。这尤其适用于光线追踪方法。
然而，我们注意到，没有根据定义的标准评估所开发的算法的通用方案。因此，作为未来的研究工作，我们建议开发和建立标准化测试程序，以便能够生成关于要检查的程序性能的可靠声明，以完成定义 1 中描述的任务，并创建比较各个程序的基础。在数值领域，以下类别特别令人感兴趣，我们建议将其作为等值线方法的评估标准：
• 条件;
• 稳定性;
• 一致性;
• 收敛性。
6.1. Condition
The condition of the problem describes the extent to which the problem oscillates in the event of any perturbations. This is particularly important for so-called inverse problems, where the cause of the problem must be deduced from the effect. This often occurs when calculating inverse matrices, where a variation in the entries of the matrix can have a significant effect on the solution. In this context, one can also speak of ill-posed problems. Various regularization techniques exist to mitigate these effects, such as Tikhonov regularization [81]. However, the extent to which this category needs to be examined in relation to isocontouring methods depends on the method proposed.
问题的条件描述了问题在受到任何扰动时的振荡程度。这对于所谓的逆问题尤为重要，因为在逆问题中，必须从影响中推断出问题的原因。这种情况经常发生在计算逆矩阵时，矩阵条目的变化会对解法产生重大影响。在这种情况下，我们也可以说这是一个假问题。有各种正则化技术可以减轻这些影响，例如 Tikhonov 正则化[81]。不过，这类问题在多大程度上需要结合等轴法进行研究，取决于所提出的方法。
6.2. Stability
In contrast to condition, stability refers to the oscillation of the numerical algorithm in the event of possible perturbations, i.e., how sensitively the algorithm reacts to a perturbation in the input parameters. An example of this would be the extent to which the distortion of an originally structured data set affects the quality of the result.
与条件相反，稳定性是指在可能的扰动情况下数值算法的振荡，即算法对输入参数的扰动做出反应的敏感程度。一个例子是原始结构化数据集的失真对结果质量的影响程度。
6.3. Consistency
The consistency of the method refers to the actual solution to the original problem. If it is assumed that the analytical solution to a problem is known, the consistency checks the extent to which the algorithm deviates from the analytical solution if the input is exact. An example of this would be the numerical calculation of one-dimensional zeros, whereby the analytically known zero is passed to the procedure in order to subsequently check how large the deviation from the target value (in this case, 0) is.
方法的一致性是指对原问题的实际解。如果假设问题的解析解已知，则一致性检查在输入准确的情况下算法偏离解析解的程度。一个例子是一维零值的数值计算，由此将分析已知的零值传递给程序，以便随后检查与目标值（在本例中为 0）的偏差有多大。
6.4. Convergence
Convergence is similar to the consistency of the algorithm and examines the extent to which the problem is solved with perturbed input data. In the context of convergence, the speed with which the solution is approximated is of central importance.
Although the above categories allow a standardized examination of the developed methods, they require knowledge of the analytical solution. For this reason, we suggest introducing suitable test functions that have an appropriate degree of complexity and whose analytical solution is known. A possible function for two-dimensional solution sets would be, for example, the simple parabolic function of the form
f
(
x
1
,
x
2
)
=
x
1
2
+
x
2
2
f (x_1, x_2) = x^2_1 + x^2_2
f(x1,x2)=x12+x22. In this case, a value
[
x
1
‾
,
x
2
‾
]
[\overline{x_1}, \overline{x_2}]
[x1,x2] calculated by the algorithm, which should result in a previously defined function value v, can then be inserted into the analytical form in order to review the quality with which the nominal value was approximated, i.e.,
f
(
x
1
‾
,
x
2
‾
)
−
v
=
ε
f (\overline{x_1}, \overline{x_2}) − v = ε
f(x1,x2)−v=ε is calculated, with ε being the deviation according to the nominal value. Note that the use of test functions is common practice in the field of nonlinear optimization—for instance, in order to verify the solution quality of developed algorithms. Examples include Himmelblau’s function [82] or the Rosenbrock function [83]. To obtain a statistically reliable statement, a certain number of experiments must also be carried out. Here, it is important to limit the number of parameters to be varied in the experiments to a manageable level. In this context, the authors J. Loeppky et al. propose, in [84], that the number of computer experiments
n
t
n_t
nt to be carried out should be determined by the relation
n
t
≈
10
⋅
n
D
n_t ≈ 10 · n_D
nt≈10⋅nD, where
n
D
n_D
nD describes the number of parameters to be varied. Subsequent statistical evaluation can then be used to draw conclusions about the quality of the procedure by using the arithmetic mean and the corresponding standard deviation. However, the method that we propose requires that the results obtained by the algorithm are available in a form that is suitable for evaluation in the categories mentioned, such as the generation of point clouds that can be used as raw data.
收敛性类似于算法的一致性，检查使用扰动的输入数据解决问题的程度。在收敛的情况下，近似解的速度至关重要。
尽管上述类别允许对所开发的方法进行标准化检查，但它们需要分析解决方案的知识。因此，我们建议引入合适的测试函数，这些函数具有适当的复杂度并且其解析解是已知的。例如，二维解集的可能函数是
f
(
x
1
,
x
2
)
=
x
1
2
+
x
2
2
f (x_1, x_2) = x^2_1 + x^2_2
f(x1,x2)=x12+x22 形式的简单抛物线函数。在这种情况下，由算法计算出的值
[
x
1
‾
,
x
2
‾
]
[\overline{x_1}, \overline{x_2}]
[x1,x2] 应该会产生先前定义的函数值 v，然后可以将其插入到分析形式中，以便检查近似标称值的质量，即计算
f
(
x
1
‾
,
x
2
‾
)
−
v
=
ε
f (\overline{x_1}, \overline{x_2}) − v = ε
f(x1,x2)−v=ε，其中 ε 是根据标称值的偏差。请注意，使用测试函数是非线性优化领域的常见做法，例如，为了验证所开发算法的解质量。例子包括 Himmelblau 函数 [82] 或 Rosenbrock 函数 [83]。为了获得统计上可靠的陈述，还必须进行一定数量的实验。在这里，将实验中要改变的参数数量限制在可管理的水平是很重要的。在这种背景下，作者 J. Loeppky 等人。在[84]中提出，要进行的计算机实验的数量
n
t
n_t
nt应该由关系式
n
t
≈
10
⋅
n
D
n_t ≈ 10·n_D
nt≈10⋅nD来确定，其中
n
D
n_D
nD描述了要改变的参数的数量。随后的统计评估可用于通过使用算术平均值和相应的标准差来得出有关程序质量的结论。然而，我们提出的方法要求算法获得的结果以适合在上述类别中进行评估的形式提供，例如生成可用作原始数据的点云。
Key aspects of the proposed method have already been successfully demonstrated in [39] through the systematic comparison of two functions in MATLAB© for isocontouring. The categories considered include the quality of the results achieved, taking into account perturbations in the input data and the computing time required. Test functions were defined in analytical form in advance in order to be able to compare the calculated results with the exact solution in each case. With the help of the procedure, it was thus possible to make quantitative statements with regard to the investigated aspects, in addition to the qualitative presentation of the results.
通过对 MATLAB© 中用于等值轮廓的两个函数进行系统比较，所提出方法的关键方面已在 [39] 中得到成功证明。考虑的类别包括所实现结果的质量，同时考虑输入数据的扰动和所需的计算时间。测试函数预先以分析形式定义，以便能够将计算结果与每种情况下的精确解进行比较。在该程序的帮助下，除了结果的定性呈现之外，还可以对所调查的方面做出定量陈述。
7. Discussion
The previous sections describing the various methods reveal that they all have specific limitations and are used in certain areas of application. Therefore, the methods are first summarized, compared and discussed. As the methods presented were all developed and implemented in different application areas, the algorithms are first discussed within their method families which finally leads to a cross-method analysis.
从前面介绍各种方法的章节中可以看出，它们都有特定的局限性，并在某些领域得到应用。因此，我们首先对这些方法进行了总结、比较和讨论。由于所介绍的方法都是在不同的应用领域开发和实施的，因此首先讨论的是其方法系列中的算法，最后进行交叉方法分析。
7.1. Marching Squares and Marching Cubes Algorithms
Overall, the marching squares and marching cubes algorithms provide a robust method to calculate isovalues within a given data set. The main application of the process is in imaging techniques, such as for medical purposes. The original data are therefore structured as image recordings and divided into pixels. It is not possible to vectorize the algorithm, as the data cubes have to be analyzed individually, which has a significant impact on the overall speed of the algorithms. Since structured data in grid form must be available for the application of the algorithm, transferability is only possible to problems that incorporate exactly these types of data structures. This limits the applicability of the algorithm to predominantly imaging problems. Furthermore, the results of the marching cubes algorithms are mainly tested using visual inspections, or, in some cases, a comparison is carried out with the original marching cubes algorithm of W. E. Lorensen and H. E. Cline.
总体而言，行进方块和行进立方体算法提供了一种强大的方法来计算给定数据集中的等值。该过程的主要应用是成像技术，例如用于医疗目的。因此，原始数据被构造为图像记录并被划分为像素。无法对算法进行矢量化，因为必须单独分析数据立方体，这对算法的整体速度有重大影响。由于网格形式的结构化数据必须可用于算法的应用，因此只有精确包含这些类型的数据结构的问题才可能具有可转移性。这限制了该算法对主要成像问题的适用性。此外，行进立方体算法的结果主要通过目视检查进行测试，或者在某些情况下与W. E. Lorensen和H. E. Cline的原始行进立方体算法进行比较。
7.2. Tessellation-Based Algorithms
The tessellation-based algorithms are made up of several different approaches, all of which are based on polygonization or the general use of triangles or tetrahedra. The polygonization algorithms, and the marching tetrahedra algorithm in particular, are based on the fundamental idea of the marching cubes algorithm and therefore originate primarily from the field of medical imaging. However, the methods have also been extended to the generation and triangulation of molecular surfaces, for example. These methods require structured data but often provide topologically more correct surfaces than the marching cubes algorithm. Mesh-based algorithms, on the other hand, originate from a different problem-solving context, where primarily technical problems need to be solved. Structured data are generally not available for these problems, meaning that the algorithms must also provide results with unstructured data. This means that these algorithms could also be used in other areas.
Thus, it can be concluded that the tessellation-based algorithms are primarily used for structured data sets and are only occasionally used for unstructured data sets. The data sets can be two- or three-dimensional. The quality of the various algorithms, if validation is carried out, is predominantly analyzed via a visual inspection. The RooTri() algorithm in [39] is an exception, as it can be used for unstructured data sets and a test routine based on statistically sound methods is performed to evaluate the quality of the algorithm.
基于曲面细分的算法由几种不同的方法组成，所有这些方法都基于多边形化或三角形或四面体的一般使用。多边形化算法，特别是行进四面体算法，基于行进立方体算法的基本思想，因此主要起源于医学成像领域。然而，这些方法也已扩展到例如分子表面的生成和三角测量。这些方法需要结构化数据，但通常提供比行进立方体算法在拓扑上更正确的表面。另一方面，基于网格的算法源自不同的问题解决环境，其中主要需要解决技术问题。结构化数据通常不适用于这些问题，这意味着算法还必须提供非结构化数据的结果。这意味着这些算法也可以用于其他领域。
因此，可以得出结论，基于曲面细分的算法主要用于结构化数据集，仅偶尔用于非结构化数据集。数据集可以是二维或三维的。如果进行验证，各种算法的质量主要通过目视检查进行分析。 [39]中的RooTri()算法是一个例外，因为它可以用于非结构化数据集，并且执行基于统计合理方法的测试例程来评估算法的质量。
7.3. Surface Nets Algorithms
The general concept of the surface nets algorithm is based on the approach of the marching cubes algorithm, whereby cubes are constructed from layered, structured data. The method is therefore preferably used in the field of medical imaging, which provides structured data for evaluation. In addition to medical imaging, the method is also used in computer geometry and offers a simple and effective procedure for the determination of isocontours or isosurfaces. By smoothing the surfaces, the terracing effect can also be significantly reduced. However, the method does not always produce the most accurate or precise surface meshes, especially for complex geometries or strong curvatures. It can also be observed that the quality of the surface nets algorithms is only evaluated by means of visual inspection, while a comparison with the original marching cubes algorithm by W. E. Lorensen and H. E. Cline is only carried out in one case.
表面网络算法的一般概念基于行进立方体算法的方法，其中立方体是由分层的结构化数据构造的。因此，该方法优选地用于医学成像领域，其提供用于评估的结构化数据。除了医学成像之外，该方法还用于计算机几何，并为确定等值线或等值面提供简单而有效的程序。通过平滑表面，也可以显着减少梯田效应。然而，该方法并不总是产生最准确或精确的表面网格，特别是对于复杂的几何形状或强曲率。还可以看出，表面网络算法的质量仅通过目视检查来评估，而与 W. E. Lorensen 和 H. E. Cline 的原始行进立方体算法的比较仅在一种情况下进行。
7.4. Ray Tracing Algorithms
In the field of computer graphics, such as the visualization of simulation results, ray tracing algorithms offer the possibility of generating realistic light and shadow effects for three-dimensional scenes. However, this leads to great computational effort overall. The method also requires predominantly structured data, although approaches that can also process unstructured data have recently been pursued. It is found that the quality of the ray tracing method is mainly determined by visual inspections. However, due to the overall great computational effort of the method, the resulting computational cost of the algorithms is also a frequently used criterion.
In summary, it can be stated that the methods were all developed from their respective areas of application and therefore require a specific form of data, often structured data. However, this frequently makes it difficult to transfer them to other areas of application that provide different data. Furthermore, the assessment of the algorithm quality largely relies on visual inspection, posing challenges in comparing different method families.
在计算机图形学领域，例如模拟结果的可视化，光线追踪算法为三维场景生成逼真的光影效果提供了可能。然而，这总体上会导致大量的计算工作。该方法还主要需要结构化数据，尽管最近也在寻求也可以处理非结构化数据的方法。研究发现，射线追踪方法的质量主要通过目视检查来确定。然而，由于该方法的总体计算量很大，因此算法的计算成本也是一个经常使用的标准。
总之，可以说这些方法都是从各自的应用领域发展而来的，因此需要特定形式的数据，通常是结构化数据。然而，这常常使得将它们转移到提供不同数据的其他应用程序领域变得困难。此外，算法质量的评估很大程度上依赖于视觉检查，这给比较不同方法系列带来了挑战。
8. Conclusions
This paper provides a comprehensive overview of approaches for the determination of isocontours and isosurfaces from given data sets. Based on the review of existing algorithms for iscontouring, four dominant methods can be identified: marching cubes algorithms, tessellation-based algorithms, surface nets algorithms and ray tracing algorithms. The algorithms have each been developed from specific problem areas; thus, the corresponding solution strategies for isocontouring have also resulted from these contexts. Nevertheless, all algorithms must solve the same task from a mathematical point of view. With regard to their application, it can be seen that the methods are mainly used in the fields of medical imaging, computer graphics and the visualization of simulation results. The preferred areas of application of the algorithms also imply that they have different requirements for the necessary input data. Marching cubes and surface nets algorithms, for example, can only process structured data sets. In contrast, tessellation-based methods and ray tracing algorithms are also able to process unstructured data sets. This is particularly advantageous when using measurement data, as these can be subject to errors due to measurement inaccuracies. Another key finding of the literature review is that there is no standardized scheme for the evaluation of the quality of the algorithms developed. Depending on the use case, different categories are examined, most of which involve a visual inspection of the results. Therefore, a possible scheme for the statistical analysis of the developed algorithms is proposed in this paper.
本文全面概述了从给定数据集中确定等值线和等值面的方法。基于对现有轮廓算法的回顾，可以确定四种主要方法：行进立方体算法、基于曲面细分的算法、表面网络算法和光线追踪算法。这些算法都是根据特定的问题领域开发的；因此，相应的等值线解决方案策略也是从这些背景中产生的。然而，所有算法都必须从数学角度解决相同的任务。从应用来看，这些方法主要应用于医学成像、计算机图形学和仿真结果可视化领域。算法的首选应用领域也意味着它们对必要的输入数据有不同的要求。例如，行进立方体和表面网络算法只能处理结构化数据集。相比之下，基于曲面细分的方法和光线追踪算法也能够处理非结构化数据集。这在使用测量数据时特别有利，因为这些数据可能由于测量不准确而出现误差。文献综述的另一个重要发现是，没有标准化的方案来评估所开发算法的质量。根据用例，检查不同的类别，其中大多数涉及对结果的目视检查。因此，本文提出了一种对所开发算法进行统计分析的可能方案。
