thank you very much for taking the time to check out the code and
I'll gladly apply the changes you proposed.
As for the polyhedron concepts, there are two possibilities. The
algorithm that I
am aiming at is a fast intersection of two convex polyhedrons.
However, the polyhedra
I am dealing with may be slightly non-convex, in the sense that
some of the faces are
not-planar to a small extent. Because of this, I am thinking about
two concepts for a
# P1 polygon soup
# P2 doubly-linked edge graph (boost graph fits the
characteristics I believe, but I need
The goal for P1 is to optimize the intersection by implementing
the Axis Aligned Bound
Box check for the polyhedron, then a Separating Axis Collision
test, and then repeat the
same for every Polygon of P1. This should speed up the algorithm
although an intersection
between two models of P1, say p11 and p12 will still have O(np11,
np12), where n is the
number of polygons in a polyhedron. The accuracy of the P1
intersection can be increased
by tetrahedral decomposition of a P1 polyhedron and performing a
P1 is already there as a concept in a way: multi_polygon, but it
lacks volume calculation,
and tetrahedral decomposition, and there are no AABB intersection
checks and Separating
Axis Collision detection algorithms in 3D.
For P2, there is the intersection algorithm of Muller and
Preparata, and for this, boost.geometry
has all the ingredients (convex hull, etc). However, the convex
hull will erase all the
non-planarity, but the algorithm is O(n log n), where n is the
number of points involved in the
intersection. I am not sure how fast this will be if I use
tetrahedral decomposition of a polyhedron
and then execute nested intersection (Muller and Preparata
algorithm between two sets of
I would like to start with the P1 concept first, since
multi_polygon is already there in
boost.geometry, and in my library I have a similar concrete class
up and running, so I would like
to try out AABB tests and Collision Detection to speed up the
intersection. When this is done,
I would move on to defining the concept described in the Muller
& Preparata paper...
On 05/16/2013 08:08 PM, Bruno Lalande wrote:
Thanks a lot for contributing this.
Code-wise it looks good, except the way in which you output into the stream
is a bit suboptimal, a lot of strings could be joined together - e.g.
"\nPOLYGONS" << " " << 1 << " "
should rather be written
"\nPOLYGONS 1 "
There's no point incurring any overhead here.
Conceptually speaking, including the polyhedron version is going to be
difficult at this point, as Boost.Geometry has no polyhedron concept yet.
You are basically inventing your own concept in the code, adapted to what
this specific algorithm expect, which is not the idea of concepts. I don't
know yet which form the polyhedron concept will take but I expect there
will actually be several of them, following the Boost.Graph concepts :
We can also take some inspiration from CGAL here. Basically they have
adapted their polyhedron class to the Boost.Graph concepts, and they have
also added one additional concept that was not in Boost.Graph
The concept you seem to be following doesn't really seem to follow any of
those (but please double-check), it looks more like a polygon soup, so that
might also be a separate concept. How did you choose the way in which
you're accessing your polyhedron? Does that simply come from an actual
class you're working with?
Geometry mailing list