Skip to Content.
Sympa Menu

cgal-discuss - Re: [cgal-discuss] do_intersect for pairs of tetrahedrons?

Subject: CGAL users discussion list

List archive

Re: [cgal-discuss] do_intersect for pairs of tetrahedrons?


Chronological Thread 
  • From: Amy Tabb <>
  • To:
  • Subject: Re: [cgal-discuss] do_intersect for pairs of tetrahedrons?
  • Date: Tue, 28 Jul 2009 21:30:52 -0400

Hi Andre,

Okay, I had responded to the second part about computing the actual intersection, which you knew about, but not the first part, about detecting the intersection.

The equivalent of the CGAL `do_intersect' function in 3D is what is usually called the `intersection detection' or `intersection counting/reporting' problem. There has been a lot of work done on this, with different strategies depending on the complexity of the objects involved. Luckily, the portion of the Handbook of Discrete and Computational Geometry (a pretty expensive and heavy book) that talks about this subject is provided online: http://www.cs.umd.edu/~mount/Papers/crc-intersect.pdf. Briefly, there are two options described there. The bounding box preprocessing option associates a bounding box with every polyhedron (or triangle in the mesh); the bounding boxes are first tested for intersection before more complicated intersection tests on the actual objects within the bounding boxes. CGAL provides such a scheme in this package:

http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Box_intersection_d/Chapter_main.html

There's an example program that I think might be applicable to your problem, in section 51.5 of the above web page.

The other option is to detect the intersection of convex polyhedra via a Dobkin-Kirkpatrick decomposition; this is a more complicated option.

Good luck.

Best
Amy


Andre Massing wrote:
Hi Amy,

thanks for the fast reply.

On Tuesday 28 July 2009 21:41:38 Amy Tabb wrote:
Hello Andre,

There is section of the manual on the intersection (or generally,
Boolean ops) of Nef Polyhedra:
http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Nef_3/Chapter_main.html

Yepp, I've already scanned a bit through the documentation and was wondering, how difficult it might be to provide (or find?) a do_intersect function for 3D Polygons similar to those described on
http://www.cgal.org/Manual/3.4/doc_html/cgal_manual/Boolean_set_operations_2_ref/Function_do_intersect.html#Cross_link_anchor_894

Actually I have no clue about what happens behind the curtain of CG (although it is quite fascinating) since I am more affiliated to the PDE FEM world. But I guess a (suitable) check if 2 polyhedrons intersect or not should be much faster then computing the actual intersection Nef poyhedron and checking it if it is empty. That's why I want to provide a dedicated "do_intersect" function. Since I want to deal with 2 overlapping meshes, and at least one will move during simulation, I must assure do sort out the overlapped cell afap.

I have been thinking about implementing it myself based on the do_intersect function taking triangles and tetrahedrons and its implementation in include/CGAL/Triangle_3_Tetrahedron_3_do_intersect.h
but I am not sure, whether this is the best approach, both in terms of clumsy programming hacks and efficiency, especially since a comment in that files indicates that already that implementation is not optimized.

Sorry for being so unfamiliar with all concepts/algorithm and maybe asking some simple to answer question, but I' ve just entered the formerly unknown country of CG :-)

Best wishes,
Andre

There are two papers that discuss the complexity of the operations in
depth; I cannot vouch for the speed however as I have not used this
feature.

Best
Amy

Andre Massing wrote:
Hi,

ATM I am studying a certain kind of finite element methods with
overlapping meshes. Therefore I am adding some intersection functionality
to our mesh classes (belonging to the problem solving environment
http://www.fenics.org/wiki/DOLFIN). These corresponds to the
functionality provided by CGAL: A boolean function "do_intersect" and an
"intersection" function, which computes the actual intersection in terms
of Nef Polygons. Depending on the dimension a mesh is purely build up by
segments, triangles or tetrahedrons.
Everything is fine except that I am sticking with 3d case. So is there an
easy (and fast?) work around for the missing do_intersect function, which
takes two tetrahedrons (or even 2 Nef_3 polyhedrons)? Any hints or
pointers are very much appreciated!

Kind regards,
Andre
--
Amy Tabb
PhD candidate
Robot Vision Laboratory
Electrical and Computer Engineering Department
465 Northwestern Avenue
West Lafayette, Indiana 47907-2035




--
Amy Tabb
PhD candidate
Robot Vision Laboratory
Electrical and Computer Engineering Department
465 Northwestern Avenue
West Lafayette, Indiana 47907-2035




Archive powered by MHonArc 2.6.16.

Top of Page