Delaunay quadrangulation by two-coloring vertices
Mitchell, Scott A. and Mohammed A. Mohammed, Ahmed H. Mahmoud, Mohamed S. Ebeida
23rd International Meshing Roundtable, Elsevier Ltd., October 12-15 2014
23rd International Meshing Roundtable
Sandia National Laboratories, Albuquerque, U.S.A.
Alexandria University, Alexandria, Egypt
We introduce a bichromatic Delaunay quadrangulation principle by assigning the vertices of a Delaunay triangulation one of two
colors, then discarding edges between vertices of the same color. We present algorithms for generating quadrangulations using
this principle and simple refinements. The global vertex coloring ensures that only local refinements are needed to get all quads.
This is in contrast to triangle-pairing algorithms, which get stuck with isolated triangles that require global refinement. We present
two new sphere-packing algorithms for generating the colored triangulation, and we may also take as input a Delaunay refinement
mesh and color it arbitrarily. These mesh non-convex planar domains with provable quality: quad angles in [10", 174"] and edges
in [0.1, 2]r. The algorithms extend to curved surfaces and graded meshes. The ìrandomî algorithm generates points with blue
noise. The ìadvancing-frontî algorithm produces large patches of boundary-aligned square tilings.
Download Full Paper (PDF Format)
Contact author(s) or publisher for availability and copyright information on above referenced article