CGAL users discussion list

[Andre Massing <>]

Hi Sylvain,

Sylvain Pion wrote:
> Hi Andre,
>
> Andre Massing wrote:
> > first of all, I  want to thank the developer behind the CGAL project 
> > for providing such a well-documented, open-source computational 
> > geometry library. We just started to use it in our mesh classes of our 
> > FEM library dolfin for providing some intersection detection and 
> > computation, and it is actually quite fun to work with.
>
> Excellent !
>
> > Since we intend to use intersection quite heavily I have been 
> > wondering, why certain intersection test in 3D have not yet been 
> > implemented, such as the following
> >
> > ‘do_intersect(Point_3&, Point_3&)’
> > primitive_intersection_test.cpp:79: error: no matching function for 
> > call to ‘do_intersect(Point_3&, Segment_3&)’
> > primitive_intersection_test.cpp:81: error: no matching function for 
> > call to ‘do_intersect(Point_3&, Tetrahedron_3&)’
> > primitive_intersection_test.cpp:84: error: no matching function for 
> > call to ‘do_intersect(Segment_3&, Segment_3&)’
> > primitive_intersection_test.cpp:86: error: no matching function for 
> > call to ‘do_intersect(Segment_3&, Tetrahedron_3&)’
> > primitive_intersection_test.cpp:93: error: no matching function for 
> > call to ‘do_intersect(Tetrahedron_3&, Tetrahedron_3&)’
> >
> > in particular the Point_3/another primitive are missing. Is there any 
> > special reason for that, a principle obstacle for implementing this 
> > correctly or do I just not use the right functions?
>
> For do_intersect(Point_3 p, X x), x.has_on(p) provides a similar 
> functionality.

Oh, thanks for the hint!

> For do_intersect(Point_3, Point_3), operator== should obviously do it.

Of course, too fast copy & paste from compiler messages :)

> It's true that we could envision generalizing the do_intersect()
> to also handle these cases.

Hmm, that might be nice, since it unifies the interface for the 
intersection detection.

> > I just wonder, since for instance a Triangle_3 Tetrahedron_3 or 
> > Triangle_3 Triangle_3 intersection or intersection those objects with 
> > Bbox are implemented.
> >
> > At a first glance at
> > http://www.cgal.org/Manual/beta/doc_html/cgal_manual/Kernel_23_ref/Function_do_intersect.html 
> >
> > opposed to the 3D case, the 2d case seems fairly complete.
> >
> > Maybe you could give me some hints or pointers, how one might supply 
> > these additional tests?
>
> The 3D intersection routines are not all finalized, some of them
> in the AABB_tree package might end up being documented in the kernel
> in some future release, once they are polished enough.
> Currently, some of them are still mostly internal (aka, use at your
> own risk :) ).

No risk no fun. We already use the AABB_tree package to some extend.
I will try (and probably *only* try :)  to implemented the intersection 
cases segment-segment (maybe can be borrowed from GTS?) and the 
tetrahedron-tetrahedron cases "myself".. I found an article by  David 
Eberly  at

http://www.geometrictools.com/LibFoundation/Intersection/Intersection.html

on intersection of convex objects by the method of separating axes.

Let see how it works. But I must admit, since I am a complete greenhorn 
in CG, I feel like driving formula-1 races without a having a driver's 
license :)

Greetings,
Andre