Geometry Boost List: Re: [geometry] vtk output beta ready for polygon, ring and multi_polygon

Subject: Re: [geometry] vtk output beta ready for polygon, ring and multi_polygon
From: Tomislav Maric (tomislav.maric_at_[hidden])
Date: 2013-05-16 18:37:33

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_at_[hidden]
> http://lists.boost.org/mailman/listinfo.cgi/geometry