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:

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