[MOAB-dev] Why kdtree's take so long to initialize

[Tim Tautges (ANL)]

Hi all,
   I spent the morning trying to figure out why kdtree's in MOAB take so long to initialize.  As often happens, I spent 
time in the code, when I should have spent time in my brain first.  I wrote a FAQ item on it, at 
https://trac.mcs.anl.gov/projects/ITAPS/wiki/KdTreeCost.  Really, it's a simple matter of non-vertex elements not being 
wholly contained in tree node boxes, and the box-element overlap test not being a simple box comparison.

I recently implemented a BVH tree that should perform much better for searching elements rather than points, with 
initialization being much faster too.

- tim

-- 
================================================================
"You will keep in perfect peace him whose mind is
   steadfast, because he trusts in you."               Isaiah 26:3

              Tim Tautges            Argonne National Laboratory
          (tautges at mcs.anl.gov)      (telecommuting from UW-Madison)
  phone (gvoice): (608) 354-1459      1500 Engineering Dr.
             fax: (608) 263-4499      Madison, WI 53706