CGAL users discussion list

[Andre Massing <>]

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
>