Isosurface stuffing: fast tetrahedral meshes with good dihedral angles
Isosurface stuffing: fast tetrahedral meshes with good dihedral angles
复制标题
DOI：
10.1145/1275808.1276448
复制
发表时间：
2007-07
期刊：
影响因子：
--
通讯作者：
F. Labelle;J. Shewchuk
中科院分区：
文献类型：
--
作者：
F. Labelle;J. Shewchuk
等值面填充算法用大小均匀的四面体网格填充等值面，四面体网格的二面角在10.7°和164.8°之间，或者（参数变化时）在8.9°和158.8°之间。该算法速度快，数值稳定，易于实现，因为像Marching Cubes一样，它从一小组预先计算的支架中生成四面体。该算法的一个变体创建了一个具有内部分级的网格：在边界上，通常需要高分辨率，元素很细且大小均匀，而在内部，它们可能更粗糙且大小不同。这些功能的组合使等值面填充成为动态流体模拟、大变形力学和需要交互式重新网格化或使用由平滑隐式曲面定义的对象的应用程序的强大工具。它是第一个严格保证四面体适用于其形状比盒子更具挑战性的域中的有限元方法的算法。我们的角度界限是由计算机辅助证明保证。如果等值面是具有有界曲率的光滑2-流形，并且四面体足够小，则网格的边界保证是等值面的几何和拓扑精确近似。
The isosurface stuffing algorithm fills an isosurface with a uniformly sized tetrahedral mesh whose dihedral angles are bounded between 10.7° and 164.8°, or (with a change in parameters) between 8.9° and 158.8°. The algorithm is whip fast, numerically robust, and easy to implement because, like Marching Cubes, it generates tetrahedra from a small set of precomputed stencils. A variant of the algorithm creates a mesh with internal grading: on the boundary, where high resolution is generally desired, the elements are fine and uniformly sized, and in the interior they may be coarser and vary in size. This combination of features makes isosurface stuffing a powerful tool for dynamic fluid simulation, large-deformation mechanics, and applications that require interactive remeshing or use objects defined by smooth implicit surfaces. It is the first algorithm that rigorously guarantees the suitability of tetrahedra for finite element methods in domains whose shapes are substantially more challenging than boxes. Our angle bounds are guaranteed by a computer-assisted proof. If the isosurface is a smooth 2-manifold with bounded curvature, and the tetrahedra are sufficiently small, then the boundary of the mesh is guaranteed to be a geometrically and topologically accurate approximation of the isosurface.