CGAL users discussion list

["Laurent Rineau (GeometryFactory)" <>]

On Monday 17 August 2009 11:40:14 Andre Massing wrote:
> Hi all,
>
> I am working on intersection of overlapping meshes, used in a certain
> finite element method. Since the upcoming CGAL 3.5 release will offer an
> additional package implementing an AABB Tree
> http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/AABB_tree/Chapter_main.
>html I am wondering  how it compares to
> http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/Box_intersection_d/Chap
>ter_main.html .
> Since I am going to intersect two meshes (which could contain many cells) I
> am thinking to use the bipartite version of the CGAL::box_intersection_d
> function.
> http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/Box_intersection_d_ref/
>Function_box_self_intersection_d.html#Cross_link_anchor_1587
>
> Would this function be (theoretically) faster than building up a tree of
> the first mesh and query each bbox of the 2nd mesh via
> http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/AABB_tree_ref/Class_AAB
>B_tree.html by simply iterating through the  bounding box list of the 2nd
> mesh? I could imagine that in the bipartite case some performance tweaks
> are used?

I think Box_intersection_d is more appropriate when you want to intersect two 
given surface meshes. The AABB tree query times are great but the 
construction 
time of the tree will penalize the total computation time.

> BTW does the new AABB tree build up on the former package or is this module
> a completly independent implementation?

The AABB tree is a completely new implementation.

> Any pointers/hints are really appreciated :-)

I think there are bibliography entries in the user manuals of these two 
packages.

-- 
Laurent Rineau, PhD
Release Manager of the CGAL Project
http://www.cgal.org/
R&D Engineer at GeometryFactory
http://www.geometryfactory.com/