An octree-based dual contouring method for triangular and tetrahedral mesh generation with guaranteed angle range
Tóm tắt
This paper presents a novel octree-based dual contouring (DC) algorithm for adaptive triangular or tetrahedral mesh generation with guaranteed angle range. First, an adaptive octree is constructed based on the input geometry. Then the octree grid points are adjusted such that we can maintain a minimum distance from the grid points to the input boundary. Finally, an improved DC method is applied to generate triangular and tetrahedral meshes. It is proved that we can guarantee the obtained triangle mesh has an angle range of (19.47°, 141.06°) for any closed smooth curve, and the tetrahedral mesh has a dihedral angle range of (12.04°, 129.25°) for any closed smooth surface. In practice, since the straight line/planar cutting plane assumption inside each octree leaf is not always satisfied, there is a small perturbation for the lower and upper bounds of the proved angle range.
Tài liệu tham khảo
Amdahl GM (1967) Validity of the single processor approach to achieving large-scale computing capabilities. In: AFIPS Conference Proceedings, pp 483–485
Borouchaki H, Hecht F, Saltel E, George PL (1995) Reasonably efficient Delaunay based mesh generator in 3 dimensions. In: 4th International meshing roundtable, pp 3–14
George PL, Borouchaki H (1998) Delaunay triangulation and meshing, applications to finite elements. Hermes, Paris
Ju T, Losaasso F, Schaefer S, Warren J (2002) Dual contouring of Hermite data. ACM Trans Graph 21:339–346
Labelle F, Shewchuk JR (2007) Isosurface stuffing: fast tetrahedral meshes with good dihedral angles. ACM Trans Graph 26(3):57.1–57.10
Liang X, Ebeida M, Zhang Y (2009) Guaranteed-quality all-quadrilateral mesh generation with feature preservation. In: 18th International meshing roundtable, pp 45–63
Liang X, Ebeida M, Zhang Y (2010) Guaranteed-quality all-quadrilateral mesh generation with feature preservation. Comput Method Appl Mech Eng 199(29–32):2072–2083
Liang X, Zhang Y (2011) Hexagon-based all-quadrilateral mesh generation with guaranteed angle bounds. Comput Method Appl Mech Eng 200(23–24):2005–2020
Lo SH (1991) Volume discretization into tetrahedra-I. Verification and orientation of boundary surfaces. Comput Struct 39(5):493–500
Lo SH (1991) Volume discretization into tetrahedra-II. 3D triangulation by advancing front approach. Comput Struct 39(5):501–511
Lohner R (1996) Extensions and improvements of the advancing front grid generation technique. Commun Numer Method Eng 12:683–702
Lohner R, Parikh P, Gumbert C (1988) Interactive generation of unstructured grid for three dimensional problems. In: Numerical grid generation in computational fluid mechanics 88, pp 687–697
Lopes A, Brodlie K (2003) Improving the robustness and accuracy of the marching cubes algorithm for isosurfacing. IEEE Trans Vis Comput Graph 9:16–29
Lorensen W, Cline H (1987) Marching cubes: a high resolution 3D surface construction algorithm. In: SIGGRAPH87, vol 21. pp 163–169
Pirzadeh S (1993) Unstructured viscous grid generation by advancing-layers method. AIAA-93-3453-CP AIAA pp 420–434
Ruppert J (1995) A Delaunay refinement algorithm for quality 2-dimensional mesh generation. J Algorithm 18(3):548–585
Shephard MS, Georges MK (1991) Three-dimensional mesh generation by finite octree technique. Int J Numer Methods Eng 32:709–749
Shewchuk JR (1996) Triangle: engineering a 2D quality mesh generator and Delaunay triangulator. http://www.cs.cmu.edu/quake/triangle.html
Shewchuk JR (1998) Tetrahedral mesh generation by Delaunay refinement. In: SCG’98 Proceedings of the fourteenth annual symposium on Computational geometry, pp 86–95
Wang J, Yu Z (2012) Feature-sensitive tetrahedral mesh generation with guaranteed quality. Comput Aided Des 44(5):400–412
Westermann JR, Kobbelt L, Ertl T (1999) Real-time exploration of regular volume data by adaptive reconstruction of isosurfaces. Visual Comput 15:100–111
Yerry MA, Shephard MS (1984) Three-dimensional mesh generation by modified octree technique. Int J Numer Methods Eng 20:1965–1990
Zhang Y, Bajaj C (2006) Adaptive and quality quadrilateral/hexahedral meshing from volumetric Data. Comput Method Appl Mech Eng 195(9–12):942–960
Zhang Y, Bajaj C, Sohn B-S (2005) 3D finite element meshing from imaging data. Comput Method Appl Mech Eng 194(48–49):5083–5106
Zhang Y, Hughes T, Bajaj C (2010) An automatic 3D mesh generation method for domains with multiple materials. Comput Method Appl Mech Eng 199(5–8):405–415
Zhang Y, Qian J (2012) Dual contouring for domains with topology ambiguity. Comput Method Appl Mech Eng 217–220:34–45