Hi Bruno,

thank you very much for taking the time to check out the code and your comments,
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
polyhedron:

# P1 polygon soup

# P2 doubly-linked edge graph (boost graph fits the characteristics I believe, but I need
to check)

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 nested intersection.
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
tetrahedra).

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...

Best regards,
Tomislav

On 05/16/2013 08:08 PM, Bruno Lalande wrote:
Hi Tomislav,

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.
things like

"\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 :

http://www.boost.org/doc/libs/1_53_0/libs/graph/doc/graph_concepts.html

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
(HalfedgeGraph).

www.cgal.org/Manual/latest/doc_html/cgal_manual/BGL/Chapter_main.html

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?

Regards
Bruno




_______________________________________________
Geometry mailing list
Geometry@lists.boost.org
http://lists.boost.org/mailman/listinfo.cgi/geometry