[MOAB-dev] r3741 - MOAB/trunk/src

[kraftche at cae.wisc.edu]

Author: kraftche
Date: 2010-04-05 12:08:45 -0500 (Mon, 05 Apr 2010)
New Revision: 3741

Modified:
   MOAB/trunk/src/AdaptiveKDTree.cpp
Log:
More tweaks to kD-tree code:

o Fix possible inadvertent increase in tolerance value used for ray 
  intersections as tree is descended.
  
o Increase tolerance used in tree construction even more, because while
  false positives might result in a slightly less efficient tree, false
  negatives result in incorrect trees.



Modified: MOAB/trunk/src/AdaptiveKDTree.cpp
===================================================================
--- MOAB/trunk/src/AdaptiveKDTree.cpp	2010-04-02 19:15:01 UTC (rev 3740)
+++ MOAB/trunk/src/AdaptiveKDTree.cpp	2010-04-05 17:08:45 UTC (rev 3741)
@@ -797,7 +797,8 @@
   const CartVect left_dim = 0.5*(left_max - box_min);
   const CartVect right_cen = 0.5*(box_max + right_min);
   const CartVect right_dim = 0.5*(box_max - right_min);
-  //const CartVect dim = box_max - box_min;
+  const CartVect dim = box_max - box_min;
+  const double max_tol = std::max(dim[0], std::max(dim[1], dim[2]))/10;
   
   
     // test each entity
@@ -856,9 +857,9 @@
       // sides of plane, do more precise test to ensure that it is really
       // in both.
     if (lo && ro) {
-      double tol = eps/1000;
+      double tol = eps;
       lo = ro = false;
-      while (!lo && !ro && tol <= eps) {
+      while (!lo && !ro && tol <= max_tol) {
         lo = GeomUtil::box_elem_overlap( coords, TYPE_FROM_HANDLE(*i), left_cen, left_dim+CartVect(tol) );
         ro = GeomUtil::box_elem_overlap( coords, TYPE_FROM_HANDLE(*i),right_cen,right_dim+CartVect(tol) );
         tol *= 10.0;
@@ -2091,7 +2092,18 @@
         // Otherwise we want the right child (index == 1);
       list.push_back( NodeSeg( children[fwd_child], seg.beg, seg.end ) );
     }
-      // Otherwise we must intersect the plane
+      // Otherwise we must intersect the plane.
+      // Note: be careful not to grow the segment if t is slightly
+      // outside the current segment, as doing so would effectively
+      // increase the tolerance as we descend the tree.
+    else if (t <= seg.beg) {
+      list.push_back( NodeSeg( children[1-fwd_child], seg.beg, seg.beg ) );
+      list.push_back( NodeSeg( children[  fwd_child], seg.beg, seg.end ) );
+    }
+    else if (t >= seg.end) {
+      list.push_back( NodeSeg( children[1-fwd_child], seg.beg, seg.end ) );
+      list.push_back( NodeSeg( children[  fwd_child], seg.end, seg.end ) );
+    }
     else {
       list.push_back( NodeSeg( children[1-fwd_child], seg.beg, t ) );
       list.push_back( NodeSeg( children[  fwd_child], t, seg.end ) );