CGAL users discussion list

[Andre Massing <>]

Hi Amy,

thanks for the detailed reply!

On Wednesday 29 July 2009 03:30:52 Amy Tabb wrote:
> 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.

Oh cool, thanks for the pointer.

> 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/Chap
>ter_main.html

Right, that is chapter I've looked at when I started to think about using 
CGAL 
for our mesh classes.  So basically for two overlapping meshes, I proceed 
basically as follows:
Approximate geometry primitives of each mesh by boxes
Use partite box_intersection
        if boxes intersect:
                Check for actual intersection of the corresponding 
approximated geometries  
                (via    do_intersect function)
                if geometry objects intersect:
                        if one is not a proper subset of the other:
                                Compute actual intersection as Nef_2 or Nef_3 
Polygon.

The only missing part is the do_intersect function for the case tetrahedron-
tetrahedron. But it seems to be rather complicated, since otherwise it would 
have been already added to CGAL?

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

Yes, that is has been the guiding example for the my implementation :) 

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

I (= complete novice to cg) am very likely not the right person to do that 
;-) 

>
> 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.h
> >>tml
> >
> > 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_operation
> >s_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,6
> > 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
>