Intersection between Delaunay triangulations

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

Intersection between Delaunay triangulations

pbarletta
Hi,
      I have 2 triangulations (A and B) and I would like to compute the volume of the intersections between triangulation A and some cells of triangulation B. These intersecting cells are only a few.
      The 3 cases are possible:
            1 vertex of the cell is inside the triangulation A.
            2 vertices of the cell is inside the triangulation A.
            3 vertices of the cell is inside the triangulation A.

      I'm wondering what would be the best approach:

         -- Computing the intersection points to construct new polyhedrons and then calculate their volume?
         -- Converting the intersecting cells (and the triangulation A) to Nef_Polyhedrons and then obtain the intersection, which may be converted back to a polyhedron to calculate its volume?
         -- Any other option I'm not thinking of?

    I started off with the 1st option, but since CGAL::intersection() does not take cells as inputs, and there is the chance that the intersecting cell traverse more than 1 cell of the triangulation A, I started doubting.

Any help is appreciated.
   
Reply | Threaded
Open this post in threaded view
|

Re: Intersection between Delaunay triangulations

Thiago Milanetto Schlittler
Hello!

   Just one question: are these 2D / surface mesh triangulations, with triangular cells, or 3D triangulations with tetrahedral cells? I've had to do something similar for my work for the 3D triangulations, and ended up using the second option: converting the cells to Nef_Polyhedrons and then obtaining their intersections. This works well, is very easy to code, and is easily adaptable to meshes with hexahedral or mixed cell types, but it's a bit expensive on time. If you already have the list of intersecting cells beforehand, this is not a big problem, though.

   For the 2D triangulations, I think that you can use the 2D Nef polygons module to do something similar, but I have no ideas of how to do it for surface meshes.

Thiago

2016-11-26 4:36 GMT+01:00 pbarletta <[hidden email]>:
Hi,
      I have 2 triangulations (A and B) and I would like to compute the
volume of the intersections between triangulation *A* and some cells of
triangulation *B*. These intersecting cells are only a few.
      The 3 cases are possible:
            1 vertex of the cell is inside the triangulation *A*.
            2 vertices of the cell is inside the triangulation *A*.
            3 vertices of the cell is inside the triangulation *A*.

      I'm wondering what would be the best approach:

         -- Computing the intersection points to construct new polyhedrons
and then calculate their volume?
         -- Converting the intersecting cells (and the triangulation *A*) to
Nef_Polyhedrons and then obtain the intersection, which may be converted
back to a polyhedron to calculate its volume?
         -- Any other option I'm not thinking of?

    I started off with the 1st option, but since CGAL::intersection() does
not take cells as inputs, and there is the chance that the intersecting cell
traverse more than 1 cell of the triangulation *A*, I started doubting.

Any help is appreciated.




--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/Intersection-between-Delaunay-triangulations-tp4662395.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss



Reply | Threaded
Open this post in threaded view
|

Re: Intersection between Delaunay triangulations

pbarletta
Hi, thanks for the reply. Yes, its 3D, I forgot to mention that.

      I don't have the list of intersecting cells, I'd have to iterate over every vertex of every cell of the B triangulation to find out if its outside the  A triangulation, inside of it, or intersecting it; in which case I would then convert to Nef Polyhedron.
      I'm dealing with triangulations of (2,000 - 20,000) points. How much time did it take you to perform these volume calculations from the intersections?
     Do you think it would be (easier/faster/possible) to just convert both triangulations to Nef Polyhedrons and then calculate their intersection spaces, to then calculate its volume?

Regards.
Reply | Threaded
Open this post in threaded view
|

Re: Intersection between Delaunay triangulations

Thiago Milanetto Schlittler
Hello!

   If you only want the intersection volume, and if both your meshes are convex, maybe converting each mesh to a convex hull, then to a polyhedron, and then to a Nef polyhedron might be faster, or at least simpler to code. I never tried to do so, though, and I have no idea how the Nef polyhedron cost scales with its complexity.

   In my case, I want to mesh each intersection between two cells, and so I have no other option than finding and constructing all intersections. In my code, the conversion to Nef polyhedra, intersection construction and meshing of ~650,000 intersections takes around ~4 minutes of CPU time, while the search takes ~30 seconds. The meshes, in this case, have each 600 elements / 200 nodes and 100,000 elements / 24,000 nodes.

   I'm not using CGAL's data structures, but it has a package to find the intersections between two sets of bounding boxes (see here). It could be useful in this situation.

Regards,
Thiago

2016-11-27 1:02 GMT+01:00 pbarletta <[hidden email]>:
Hi, thanks for the reply. Yes, its 3D, I forgot to mention that.

      I don't have the list of intersecting cells, I'd have to iterate over
every vertex of every cell of the *B* triangulation to find out if its
outside the  *A* triangulation, inside of it, or intersecting it; in which
case I would then convert to Nef Polyhedron.
      I'm dealing with triangulations of (2,000 - 20,000) points. How much
time did it take you to perform these volume calculations from the
intersections?
     Do you think it would be (easier/faster/possible) to just convert both
triangulations to Nef Polyhedrons and then calculate their intersection
spaces, to then calculate its volume?

Regards.




--
View this message in context: http://cgal-discuss.949826.n4.nabble.com/Intersection-between-Delaunay-triangulations-tp4662395p4662397.html
Sent from the cgal-discuss mailing list archive at Nabble.com.

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://sympa.inria.fr/sympa/info/cgal-discuss



Reply | Threaded
Open this post in threaded view
|

Re: Intersection between Delaunay triangulations

pbarletta
Oh, good idea, I'll turn triangulation A to a convex hull and then to Nef Polyhedra.

Thanks for your answers.