CGAL users discussion list

["Laurent Rineau (GeometryFactory)" <>]

On Monday 17 August 2009 13:30:15 Andre Massing wrote:
> Hi again,
>
> thanks for the reply!
>
> On Monday 17 August 2009 12:13:27 Laurent Rineau (GeometryFactory) wrote:
> > 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_m
> > >ai n. html I am wondering  how it compares to
> > > http://www.cgal.org/Manual/3.5/doc_html/cgal_manual/Box_intersection_d/
> > >Ch ap 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_
> > >re f/ 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
> > >_A AB 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.
>
> Hmm, ok, even I don't use distance and don't call
> accelerate_distance_queries? In the intended application there will be one
> fixed background mesh and another moving mesh, which means that I have to
> compute the intersection with the background mesh at each single time step.

If you have a fixed mesh and a lot of queries on it, then the AABB will 
probably be the better solution.

> This rises also another question. Since there might be some grid
> refinement/coarsing, is there any opportunity to successively supplement
> either the tree or the (sorted) list of bounding boxes by new boxes? Or do
> I have to reinit the whole thing?

The modification of the AABB tree is not doable for the moment. That is a 
difficult task in my opinion. Maybe the authors of that package will reply on 
that point and contradict me. Let's hope so.

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