vtk output beta ready for polygon, ring and multi_polygon

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

vtk output beta ready for polygon, ring and multi_polygon

Tomislav Maric
Hi everyone,

I've prepared the writers for the ASCII legacy .vtk format to visualize the
models polygon, ring and multi_polygon in 3D in Paraview. Attached is the
image of a multi_polygon rendered in ParaView with indexed outer rings for
each polygon.

I've put up a repo at bitbucket:

https://bitbucket.org/tmaric/boost-geometry-3d

You can get the code like this:

git clone [hidden email]:tmaric/boost-geometry-3d

The .vtk format doesn't allow for polygons with holes, so the output of a polygon
is delegated to the output for its outer ring. The interface is the same as for the
wkt format, but I am not sure about the code and would really appreciate
comments on it.

Best regards,
Tomislav

_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry

multiPolygon.png (6K) Download Attachment
Reply | Threaded
Open this post in threaded view
|

Re: vtk output beta ready for polygon, ring and multi_polygon

Bruno Lalande
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
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: vtk output beta ready for polygon, ring and multi_polygon

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


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: vtk output beta ready for polygon, ring and multi_polygon

Bruno Lalande
Hi Tomislav,

Good point, I hadn't realized you were merely using the existing multipolygon concept. I think it makes sense. Moving forward we should also propose validation functions to check it's actually is a polyhedron (as a polygon soup can be anything) but this can be done later.

Implementing the Separating Axis Collision test is one of the first thing I wanted to do when started to handle real £D stuff so I'm glad you're looking into this. The algorithm indeed relies on the polyhedron being convex. Which essentially means that our concepts are going to need a way to express that (i.e. to say "I am convex" so optimal algorithms like this one can be selected). Long ago I simply thought there would be a Polyheron and a ConvexPolyhedron concept but things are much more complicated that there are tons of ways to represent polyhedrons (not just the ones you described), all valid in some situations. I can see 2 solutions:
- ConvexPolyhedron could be a concept on its own, which a model can fulfill in addition to another one (e.g. it can be a AdjacencyGraph and a ConvexPolyhedron) - however this require changes to our current design I think.
- We could have a is_convex<Geometry> metafunction that algorithms would call when they're interested in whether a geometry is convex (could be used also with polygon and plenty other stuff - could be hardcoded to true for concepts like box).

So all in all, starting with your P1 is a valid approach. It terms of the IO stuff you've written it looks right since the format seems to be representing exactly that (a set of polygons without any strong guarantee about their spatial disposition). And you can try to work on other algorithms with this concept as well to see what it gives.

Regards
Bruno


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry
Reply | Threaded
Open this post in threaded view
|

Re: vtk output beta ready for polygon, ring and multi_polygon

Tomislav Maric
Hi Bruno,

If we use a multipolygon concept for the polyhedron, for a slightly non-convex polyhedron, the only way to compute its volume is by tetrahedral decomposition. If the tetrahedral decomposition fails for a multipolygon polyhedron, we will see inverted tetrahedrons as parts of the decomposition (negative mixed product volume). This might be our test per choice, to be used with the metafunction you mentioned. Of course, there is another way to compute the volume, which may be faster: analytical formula, but this requires strict convexity of the polyhedron. We can probably switch between those options somehow.

I'll start working with P1 as you suggested, since there is a lot to try out. When I read about intersection algorithms for polyhedra, often the complexity O is mentioned, but the real question is how much the intersection can be sped up for a naive intersection (O(m*n)) with collision detection for the polygons of the polyhedron (and or Axis Aligned Bounding Box [AABB] tests).

I'll try to get the P1, collision detection and AABB tests up and  running. Then we can apply the naive O(m*n) intersection like this:
 
P1 intersect (P1 X , P1 Y)
    P1 result
    if AABB intersect (X, Y):
        if collide (X, Y):
            for all polygons X (pX):
                for all polygons Y (pY):
                    if collide (pX, pY):
                       pResult = intersect (pX, pY)
                       append pResult to result
    return result

P2 which is graph based will wait for a while, but I would like to do that as well. The question is for reasonable number of polygons (I am dealing with polyhedra that have up to say 20 polygons), which algorithm is faster, the Preparata/Muller or the naive intersection with collision detection (and/or AABB test).

I'll start working with P1 as you suggested and see where it leads. As soon as I have something to show or to ask, I'll let you know. :)

Best regards,
Tomislav

On 05/22/2013 11:11 AM, Bruno Lalande wrote:
Hi Tomislav,

Good point, I hadn't realized you were merely using the existing multipolygon concept. I think it makes sense. Moving forward we should also propose validation functions to check it's actually is a polyhedron (as a polygon soup can be anything) but this can be done later.

Implementing the Separating Axis Collision test is one of the first thing I wanted to do when started to handle real £D stuff so I'm glad you're looking into this. The algorithm indeed relies on the polyhedron being convex. Which essentially means that our concepts are going to need a way to express that (i.e. to say "I am convex" so optimal algorithms like this one can be selected). Long ago I simply thought there would be a Polyheron and a ConvexPolyhedron concept but things are much more complicated that there are tons of ways to represent polyhedrons (not just the ones you described), all valid in some situations. I can see 2 solutions:
- ConvexPolyhedron could be a concept on its own, which a model can fulfill in addition to another one (e.g. it can be a AdjacencyGraph and a ConvexPolyhedron) - however this require changes to our current design I think.
- We could have a is_convex<Geometry> metafunction that algorithms would call when they're interested in whether a geometry is convex (could be used also with polygon and plenty other stuff - could be hardcoded to true for concepts like box).

So all in all, starting with your P1 is a valid approach. It terms of the IO stuff you've written it looks right since the format seems to be representing exactly that (a set of polygons without any strong guarantee about their spatial disposition). And you can try to work on other algorithms with this concept as well to see what it gives.

Regards
Bruno



_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry


_______________________________________________
Geometry mailing list
[hidden email]
http://lists.boost.org/mailman/listinfo.cgi/geometry