2D/3D Mesh Generation via Different Tree Structures

For finite element analysis and computer graphics, mesh generation is usually the most time-consuming step and requires a great amount of user interactions. A fully automatic and robust mesh generator is therefore always desired by the community of these areas. In this thesis, we developed four algorithms: (a) quadtree-based all-quadrilateral (all-quad) mesh generation with guaranteed quality; (b) hexagon-based all-quad mesh generation with guaranteed angle bounds; (c) a robust 2-refinement algorithm for all-hexahedral (all-hex) mesh generation; and (d) an octree-based dual contouring method for triangular and tetrahedral mesh generation with guaranteed angle range.;First, a quadtree-based mesh generation method is introduced to create guaranteed-quality, geometry-adapted all-quad meshes with feature preservation for arbitrary planar domains. Given point cloud, our method generates all-quad meshes with these points as vertices and all the angles are within [45°, 135°]. For given planar curves, quadtree-based spatial decomposition is governed by the curvature of the boundaries and narrow regions. 2-refinement templates are chosen for local mesh refinement without creating any hanging nodes. A buffer zone is created by removing elements around the boundary. To guarantee the mesh quality, the angles facing the boundary are improved via template implementation, and two buffer layers are inserted in the buffer zone. It is proved that all the elements of the final mesh are quads with angles between 45° ± ϵ and 135° ± ϵ (ϵ < 5°).;As a follow-up, a novel hexagon-based mesh generation method is presented which creates all-quad meshes with guaranteed angle bounds and feature preservation for arbitrary planar domains. Given any planar curves, an adaptive hexagon-tree structure is constructed by using the curvature of the boundaries and narrow regions. Then a buffer zone and a hexagonal core mesh are created by removing elements outside or around the boundary. To guarantee the mesh quality, boundary edges of the core mesh are adjusted to improve their formed angles facing the boundary, and two layers of quad elements are inserted in the buffer zone. For any curve with sharp features, a corresponding smooth curve is firstly constructed and meshed, and then another layer of elements is inserted to match the smooth curve with the original one. It is proved that for any planar smooth curve all the element angles are within [60°-ϵ, 120°+ϵ] (ϵ ≤ 5°).;We then extend the algorithm from 2D to 3D, and present a robust 2-refinement algorithm for adaptive all-hex mesh generation based on two tree structures: octree and RD tree. Given a smooth boundary surface, we first use a pre-defined error function to detect the main surface features, and build a strongly-balanced octree. Then a novel 2-refinement algorithm is developed to eliminate all hanging nodes in the octree, which is robust for any unstructured meshes and induces a smooth transition with very little propagation. Later, all elements outside and around the boundary are removed to create the octree core mesh and a buffer zone. The boundary points on the core mesh are projected onto the surface and form the final mesh. Motivated from nature, a new tree structure based on RD is introduced in the proposal as well.;Finally, a novel octree-based dual contouring algorithm for adaptive triangular (tri) or tetrahedral (tet) mesh generation with guaranteed angle range is presented. Our algorithms has three steps. 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 dual contouring 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. (Abstract shortened by UMI.).