Re: From Triangle tiles to convex Polygons.
- From: "Dave Eberly" <dNOSPAMeberly@xxxxxxxxxxxxxxx>
- Date: Tue, 29 Jul 2008 07:03:05 -0700
"Nils" <n.pipenbrinck@xxxxxxxxx> wrote in message
news:488EEDC8.4000605@xxxxxxxxxxxx
I think you can do this by taking your triangulation and merge triangles
to build multiple convex polygons from it. One way to do this is to remove
all internal edges that don't have a connection to a convex vertex. With a
good data-structure this is very easy and fast to do.
You don't get the minimal convex decomposition that way. IIRC the convex
decomposition you get that way can't be worse than factor four over the
optimial composition though.
This is called the Hertel-Mehlhorn algorithm, discussed in Section 2.5
Polygon
Partitioning of Joseph O'Rourke's book "Computational Geometry in C".
Optimal in this case beeing: Split a polygon into the minimal number of
convex pieces.
A result by Chazelle: If p is the minimum number of convex pieces and
r is the number of reflex vertices, then ceil(r/2)+1 <= p <= r+1.
For an approach using dynamic programming, search for the paper
"M. Keil and J. Snoeyink. On the time bound for convex decomposition
of simple polygons." A bit tedious to implement...
I tried that a couple of month ago to improve the triangulation of
polygons for a triangulation algorithm that kinda works like the GLU
tesselator.
My plan was to first get the triangulation, build the convex decomposition
from it and then triangulate each convex piece on it's own using a voroni
like metric to avoid all the long and thin triangles.
It worked, but the improvement to the mesh was not worth the extra
processing time.
I agree that usually this does not help much on performance. Moreover,
the OP needs the preprocessing step that adds double edges to convert
the polygon with holes to a simple polygon.
Most likely, the convex subpolygons will be converted to triangle fans by
the OpenGL driver, so the work of grouping triangles is effectively undone,
although you get some performance gain for a triangle fan because of not
having to re-transform vertices.
To the OP: My suggestion is to use one of the publicly available triangle
stripping programs on the triangulated polygon with holes. The goal is
to improve performance by reducing transformations of vertices (i.e. by
taking advantage of caching of transformed vertices).
One final thing: Every triangulation of a simple polygon with N vertices
has N-2 triangles. Thus, when you say "a few hundred triangles is
way too many", you might not have a choice :) [Unless the OpenGL
GLU tessellator is inserting additional vertices, leading to more triangles
than a tessellator that does not insert additional vertices.]
--
Dave Eberly
http://www.geometrictools.com
.
- References:
- From Triangle tiles to convex Polygons.
- From: Yuri
- Re: From Triangle tiles to convex Polygons.
- From: Nils
- From Triangle tiles to convex Polygons.
- Prev by Date: Re: Question about Pluecker coordinates
- Next by Date: Re: Question about Pluecker coordinates
- Previous by thread: Re: From Triangle tiles to convex Polygons.
- Index(es):
Relevant Pages
|
