Re: Question on concave to convexs converting alorithm

"kiplring" <kiplring@xxxxxxxxxxx> wrote in message
news:1127723323.471129.9040@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
> How can I get optimized convexs from an 3D concave?
>
> This is what I'm planning.
<snip>

If only it were that easy. What you are describing sounds similar
to "ear clipping" for triangulating a simple polygon in 2D. In the
2D case, you locate a "convex" vertex V0 (the interior angle at
the vertex has angle smaller than pi radians). Let Vm and Vp
be its adjacent vertices. If the triangle <Vm,V0,Vp> does not
contain any other vertices of the polygon, then this triangle is
part of the triangulation and is removed from the current polygon.
The new polygon is simple and has fewer vertices, so you can
repeat this process until the last triangle is removed.

Your 3D description sounds like you are attempting to find
a "convex" vertex of the 3D polyhedron. If that vertex is
shared by three triangular faces, you could test if the remaining
polyhedron vertices are outside the tetrahedron formed by
the vertex and three faces. If so, remove the tetrahedron and
repeat the process. However, if that vertex is shared by four
or more faces, it is not apparent that you can test/remove the
polyhedron formed by the vertex and the faces. In particular,
the edges formed by those faces and adjacent to the given
vertex do not necessarily form a planar polygon.

What you want is generally a hard problem to solve. You will
need to split faces and/or add more points to the data set. One
method that comes to mind is decomposition with BSP (binary
space partitioning) trees. The leaf nodes represent the convex
subregions of your original polyhedron.

--
Dave Eberly
http://www.geometrictools.com


.

Relevant Pages

  • Re: 2D Line crossing Non-Convex Polyhedron
    ... You can just call it a "polygon" if it's 2D. ... The idea is that if there is an object inside the 2D polyhedron ... solutions for point and line segment versus convex polyhedra. ...
    (comp.graphics.algorithms)
  • Re: Quake performance SGI vs Sun
    ... he said a triangle is a polygon. ... You answered saying that a triangle ... Just the facts. ...
    (comp.sys.sun.hardware)
  • Re: Finding closest Triangle to a point
    ... a convex mesh is such that all its polygons are contained in the boundary of the convex hull formed by the vertices of the mesh. ... This also simplifies the evaluation of the potential function to a simple distance calculation between points. ... the answer to the question "which is the closest triangle to a point?" ...
    (comp.graphics.algorithms)
  • Re: Arrange points so polygon is not self intersecting
    ... Find the convex hull of the points and draw a convex polygon. ... Let A be a point with maximum y-coordinate. ...
    (sci.math)
  • Re: Arrange points so polygon is not self intersecting
    ... Find the convex hull of the points and draw a convex polygon. ... Let A be a point with maximum y-coordinate. ...
    (sci.math)