This is the video presentation on the
meshing techniques and algorithms
presented in the paper titled "Quadrilateral
Meshes with Bounded Minimum Angle",
previously published in the
proceedings of International Meshing
Roundtable, in October 2008.
We present an algorithm that utilizes
a quadtree data structure to construct
a strictly convex quadrilateral mesh for
a simple polygonal region in which
no newly created angle is smaller than
18.43 degrees. This is the first known
result on quadrilateral mesh generation
with a provable guarantee on the minimum angle. We construct a quadtree subdivision based
only on the vertices of the polygon,
ensuring certain separation and balancing conditions.
The end-result is such that a quadtree
cell contains at most a single input vertex,
and if containing such a vertex, it is
surrounded by 24 empty cells of the same size.
In addition, neighboring quadtree cells
differ by at most one level.
We then take the dual of the quadtree,
and place additional Steiner points
in select quadtree cells by identifying
and applying one of the six templates
which are based on quadrant layout.
Additional Steiner points are necessary to
quadrangulate properly within the template.
They are denoted by empty circles in these illustrations.
Recall that quadrangulation of a polygon
requires an even number of vertices on the boundary.
The open polygonal chains on the boundary
of the templates need an even number of
vertices to be stitched together with a neighboring chain.
This is the reason for introducing additional
Steiner points on these chains.
Our recursive algorithm applies the templates
to all internal nodes of the quadtree,
starting at the deepest subdivision level,
where the node is quadrangulated exactly
as shown in the previous template
illustrations.
At an arbitrary level of subdivision,
each non-leaf child is already internally
quadrangulated and we simply stitch the
children together.
Once the meshing is completed, we warp
certain mesh vertices onto the original
input vertices. Notice that the 24 empty
cells of the same size surrounding an
input vertex guarantees a grid-like mesh
with 90-degree angles that makes the
warping possible.
This concludes our point set based meshing
algorithm and we achieve a minimum angle
guarantee of 26.57 degrees.
We now adapt this mesh to incorporate
polygonal edges. The adaptation requires
polygons with no acute angles. Thus we
first pre-process the input polygon to
cut off acute corners. We will reintroduce
and process the acute corners later.
We then apply the point set based meshing
algorithm. Notice that the cutting of the
acute corners introduces more vertices
and thus forces a finer subdivision.
A key ingredient in the adaptation
is additional edge-enforced quadtree
subdivisions to ensure proper separations
of the edges. We now switch to a more
complex model to illustrate this.
A polygonal edge intersects a finite
set of quadrilaterals in the existing mesh.
We define the quadrangulation chain
associated with this edge as the sequence
of edges of these quads that lie strictly
to the interior of the polygon. The idea
is to remove the mesh elements that lie
outside of this chain, and then
quadrangulate the region between the
quadrangulation chain and its associated edge.
We now identify this chain algorithmically.
For each edge, we identify a series of
quadtree cells whose centers lie
immediately above the associated edge.
All such centers are proven to be on the quadrangulation chain.
Moreover all such cell centers are edge or
corner neighbors in the quadtree and are
connected by subchains containing at most
4 mesh edges in limited variations.
The quadrangulation chains for consecutive
edges are then connected at the vertex
regions in a straightforward way thanks to
the strictly grid-like geometry of those
regions. Note that these corner connections
create a single complete chain.
We then unzip the mesh by removing the
mesh elements that lie outside of this
completed chain.
The region between each quadrangulation
chain and its associated edge is then
quadrangulated with a minimum angle
guarantee of 18.43 degrees. We first
drop perpendicular projections from
every cell center to the edge.
We then quadrangulate the regions
between each pair of consecutive
projections via limited case analysis.
Finally the vertex regions are
quadrangulated with the desired
angle bound.
We now show the execution of the
algorithm on two datasets that
contain holes.
All acute vertices are meshed as a
post-processing step with a minimum
angle of 22.5 degrees.