Many applications such as finite element methods, computer graphics, and numerical simulations require meshing a surface or the volume enclosed by one in three dimensions. We consider polyhedral surfaces and volumes and mesh them with Delaunay refinement. We present four algorithms, QUALMESH, POLYSURFMESH, WQUALMESH, and SURFREMESH. The first one, QUALMESH, computes a Delaunay mesh of the volume enclosed by an input polyhedron possibly with small input angles. The generated mesh conforms to the input, and the circumradius to shortest edge ratio, also called radius-edge ratio, of most of the tetrahedra in the output mesh are bounded above by a constant. Some of the output tetrahedra do remain "bad", but they are only in the vicinity of small input angles. Second, we present POLYSURFMESH, a modification of the QUALMESH algorithm, to generate a triangular surface mesh of an input polyhedra such that the output mesh conforms to every vertex, edge, and facet of the input and the radius-edge ratio of most of the triangles are bounded from above. Those triangles which are "bad" also remain in the vicinity of sharp input angles.One deficiency of QUALMESH is that its output mesh might have a particular kind of bad tetrahedra called slivers. The third algorithm, WQUALMESH extends QUALMESH using the weighted Delaunay triangulation to remove most of the slivers from the output of QUALMESH. Some of the slivers do remain in the output but they are again only in the vicinity of sharp angles.Finally, SURFREMESH remeshes a polygonal surface approximating a smooth surface. The output surface is guaranteed to be homeomorphic to the input, and the output triangles have bounded radius-edge ratio. This algorithm starts with a few points chosen from the input surface and gradually builds the entire surface to satisfy user-defined thresholds for parameters capturing the geometric closeness to the input surface. These parameters allow the user to extract the surface at different levels of detail. Implementation results of all the algorithms are presented, and they corroborate with the theory.
展开▼
