CGAL users discussion list

[Amy Tabb <>]

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