*Merge.

--HG--
branch : trunk

1 files changed, 83 insertions, 83 deletions

diff --git a/src/shared/vmap/AABSPTree.h b/src/shared/vmap/AABSPTree.h
index 9b44470e7d9..5107676d48e 100644
--- a/src/shared/vmap/AABSPTree.h
+++ b/src/shared/vmap/AABSPTree.h
@@ -1,14 +1,14 @@
 /**
   @file AABSPTree.h
-  
+
   @maintainer Morgan McGuire, matrix@graphics3d.com
- 
+
   @created 2004-01-11
   @edited  2007-02-16
 
   Copyright 2000-2007, Morgan McGuire.
   All rights reserved.
-  
+
   */
 
 #ifndef G3D_AABSPTREE_H
@@ -89,7 +89,7 @@ namespace G3D {
 
     /**
      Wraps a pointer value so that it can be treated as the instance itself;
-     convenient for inserting pointers into a Table but using the 
+     convenient for inserting pointers into a Table but using the
      object equality instead of pointer equality.
     */
     template<class Type>
@@ -136,9 +136,9 @@ namespace G3D {
  AABSPTree is as powerful as but more general than a Quad Tree, Oct
  Tree, or KD Tree, but less general than an unconstrained BSP tree
  (which is much slower to create).
- 
+
  Internally, objects
- are arranged into an axis-aligned BSP-tree according to their 
+ are arranged into an axis-aligned BSP-tree according to their
  axis-aligned bounds.  This increases the cost of insertion to
  O(log n) but allows fast overlap queries.
 
@@ -158,13 +158,13 @@ namespace G3D {
  <B>Moving %Set Members</B>
  <DT>It is important that objects do not move without updating the
  AABSPTree.  If the axis-aligned bounds of an object are about
- to change, AABSPTree::remove it before they change and 
+ to change, AABSPTree::remove it before they change and
  AABSPTree::insert it again afterward.  For objects
- where the hashCode and == operator are invariant with respect 
+ where the hashCode and == operator are invariant with respect
  to the 3D position,
  you can use the AABSPTree::update method as a shortcut to
  insert/remove an object in one step after it has moved.
- 
+
 
  Note: Do not mutate any value once it has been inserted into AABSPTree. Values
  are copied interally. All AABSPTree iterators convert to pointers to constant
@@ -185,9 +185,9 @@ namespace G3D {
 */
 namespace _AABSPTree {
 
-    /** Wrapper for a value that includes a cache of its bounds. 
+    /** Wrapper for a value that includes a cache of its bounds.
         Except for the test value used in a set-query operation, there
-        is only ever one instance of the handle associated with any 
+        is only ever one instance of the handle associated with any
         value and the memberTable and Nodes maintain pointers to that
         heap-allocated value.
      */
@@ -261,10 +261,10 @@ public:
 
     /** Returns the bounds of the sub array. Used by makeNode. */
     static AABox computeBounds(
-    const Array<_AABSPTree::Handle<T>*>& point, 
+    const Array<_AABSPTree::Handle<T>*>& point,
         int                   beginIndex,
         int                   endIndex) {
-    
+
         Vector3 lo = Vector3::inf();
         Vector3 hi = -lo;
 
@@ -357,8 +357,8 @@ public:
 
         /** Location along the specified axis */
         float               splitLocation;
- 
-        /** child[0] contains all values strictly 
+
+        /** child[0] contains all values strictly
             smaller than splitLocation along splitAxis.
 
             child[1] contains all values strictly
@@ -371,15 +371,15 @@ public:
 
         /** Array of values at this node (i.e., values
             straddling the split plane + all values if
-            this is a leaf node). 
+            this is a leaf node).
 
             This is an array of pointers because that minimizes
-            data movement during tree building, which accounts 
+            data movement during tree building, which accounts
             for about 15% of the time cost of tree building.
           */
         Array<_AABSPTree::Handle<T> * >      valueArray;
 
-        /** For each object in the value array, a copy of its bounds. 
+        /** For each object in the value array, a copy of its bounds.
             Packing these into an array at the node level
             instead putting them in the valueArray improves
             cache coherence, which is about a 3x performance
@@ -403,7 +403,7 @@ public:
         Node(const Node& other) : valueArray(other.valueArray), boundsArray(other.boundsArray) {
             splitAxis       = other.splitAxis;
             splitLocation   = other.splitLocation;
-            splitBounds     = other.splitBounds;            
+            splitBounds     = other.splitBounds;
             for (int i = 0; i < 2; ++i) {
                 child[i] = NULL;
             }
@@ -490,7 +490,7 @@ public:
 #if 0
         /**
           Stores the locations of the splitting planes (the structure but not the content)
-          so that the tree can be quickly rebuilt from a previous configuration without 
+          so that the tree can be quickly rebuilt from a previous configuration without
           calling balance.
          */
         static void serializeStructure(const Node* n, BinaryOutput& bo) {
@@ -546,7 +546,7 @@ public:
         }
 
 
-        /** Appends all members that intersect the box. 
+        /** Appends all members that intersect the box.
             If useSphere is true, members that pass the box test
             face a second test against the sphere. */
         void getIntersectingMembers(
@@ -604,11 +604,11 @@ public:
             // See if the ray will ever hit this node or its children
             Vector3 location;
             bool alreadyInsideBounds = false;
-            bool rayWillHitBounds = 
+            bool rayWillHitBounds =
                 VMAP::MyCollisionDetection::collisionLocationForMovingPointFixedAABox(
                     ray.origin, ray.direction, splitBounds, location, alreadyInsideBounds);
-           
-            bool canHitThisNode = (alreadyInsideBounds ||                
+
+            bool canHitThisNode = (alreadyInsideBounds ||
                 (rayWillHitBounds && ((location - ray.origin).squaredLength() < square(distance))));
 
             return canHitThisNode;
@@ -616,20 +616,20 @@ public:
 
         template<typename RayCallback>
         void intersectRay(
-            const Ray& ray, 
-            RayCallback& intersectCallback, 
+            const Ray& ray,
+            RayCallback& intersectCallback,
             float& distance,
             bool pStopAtFirstHit,
             bool intersectCallbackIsFast) const {
                 float enterDistance = distance;
-            
+
             if (! intersects(ray, distance)) {
                 // The ray doesn't hit this node, so it can't hit the children of the node.
                 return;
             }
 
             // Test for intersection against every object at this node.
-            for (int v = 0; v < valueArray.size(); ++v) {        
+            for (int v = 0; v < valueArray.size(); ++v) {
                 bool canHitThisObject = true;
 
                 if (! intersectCallbackIsFast) {
@@ -637,11 +637,11 @@ public:
                     Vector3 location;
                     const AABox& bounds = boundsArray[v];
                     bool alreadyInsideBounds = false;
-                    bool rayWillHitBounds = 
+                    bool rayWillHitBounds =
                         VMAP::MyCollisionDetection::collisionLocationForMovingPointFixedAABox(
                             ray.origin, ray.direction, bounds, location, alreadyInsideBounds);
 
-                    canHitThisObject = (alreadyInsideBounds ||                
+                    canHitThisObject = (alreadyInsideBounds ||
                         (rayWillHitBounds && ((location - ray.origin).squaredLength() < square(distance))));
                 }
 
@@ -656,7 +656,7 @@ public:
             }
 
             // There are three cases to consider next:
-            // 
+            //
             //  1. the ray can start on one side of the splitting plane and never enter the other,
             //  2. the ray can start on one side and enter the other, and
             //  3. the ray can travel exactly down the splitting plane
@@ -666,7 +666,7 @@ public:
             int secondChild = NONE;
 
             if (ray.origin[splitAxis] < splitLocation) {
-                
+
                 // The ray starts on the small side
                 firstChild = 0;
 
@@ -702,7 +702,7 @@ public:
             }
 
             if (ray.direction[splitAxis] != 0) {
-                // See if there was an intersection before hitting the splitting plane.  
+                // See if there was an intersection before hitting the splitting plane.
                 // If so, there is no need to look on the far side and recursion terminates.
                 float distanceToSplittingPlane = (splitLocation - ray.origin[splitAxis]) / ray.direction[splitAxis];
                 if (distanceToSplittingPlane > distance) {
@@ -724,43 +724,43 @@ public:
 
     /**
      Recursively subdivides the subarray.
-    
+
      Clears the source array as soon as it is no longer needed.
 
      Call assignSplitBounds() on the root node after making a tree.
      */
     Node* makeNode(
-        Array<_AABSPTree::Handle<T> * >& source, 
-        int valuesPerNode, 
+        Array<_AABSPTree::Handle<T> * >& source,
+        int valuesPerNode,
         int numMeanSplits,
         Array<_AABSPTree::Handle<T> * >& temp)  {
 
 	    Node* node = NULL;
-	    
+
 	    if (source.size() <= valuesPerNode) {
 		    // Make a new leaf node
 		    node = new Node(source);
-		    
+
 		    // Set the pointers in the memberTable
 		    for (int i = 0; i < source.size(); ++i) {
 			    memberTable.set(Member(source[i]), node);
 		    }
             source.clear();
-		    
+
         } else {
 		    // Make a new internal node
 		    node = new Node();
-		    
+
             const AABox bounds = computeBounds(source, 0, source.size() - 1);
 		    const Vector3 extent = bounds.high() - bounds.low();
-		    
+
 		    Vector3::Axis splitAxis = extent.primaryAxis();
-		    
+
             float splitLocation;
 
             // Arrays for holding the children
             Array<_AABSPTree::Handle<T> * > lt, gt;
-                
+
             if (numMeanSplits <= 0) {
 
                 source.medianPartition(lt, node->valueArray, gt, temp, CenterComparator(splitAxis));
@@ -788,13 +788,13 @@ public:
                         // is swapped in in its place.
                         gt.fastRemove(i); --i;
                     }
-                }            
+                }
 
                 if ((node->valueArray.size() > (source.size() / 2)) &&
                     (source.size() > 6)) {
-                    // This was a bad partition; we ended up putting the splitting plane right in the middle of most of the 
-                    // objects.  We could try to split on a different axis, or use a different partition (e.g., the extents mean, 
-                    // or geometric mean).  This implementation falls back on the extents mean, since that case is already handled 
+                    // This was a bad partition; we ended up putting the splitting plane right in the middle of most of the
+                    // objects.  We could try to split on a different axis, or use a different partition (e.g., the extents mean,
+                    // or geometric mean).  This implementation falls back on the extents mean, since that case is already handled
                     // below.
                     numMeanSplits = 1;
                 }
@@ -805,9 +805,9 @@ public:
 
             if (numMeanSplits > 0) {
                 // Split along the mean
-                splitLocation = (bounds.high()[splitAxis] + 
+                splitLocation = (bounds.high()[splitAxis] +
                                  bounds.low()[splitAxis]) / 2.0;
-                
+
                 source.partition(NULL, lt, node->valueArray, gt, Comparator(splitAxis, splitLocation));
 
                 // The Comparator ensures that elements are strictly on the correct side of the split
@@ -817,7 +817,7 @@ public:
 #           if defined(G3D_DEBUG) && defined(VERIFY_TREE)
                 debugAssert(lt.size() + node->valueArray.size() + gt.size() == source.size());
                 // Verify that all objects ended up on the correct side of the split.
-                // (i.e., make sure that the Array partition was correct) 
+                // (i.e., make sure that the Array partition was correct)
                 for (int i = 0; i < lt.size(); ++i) {
                     const AABox& bounds  = lt[i]->bounds;
                     debugAssert(bounds.high()[splitAxis] < splitLocation);
@@ -849,16 +849,16 @@ public:
 			    memberTable.set(Member(v), node);
             }
 
-            if (lt.size() > 0) {		    
+            if (lt.size() > 0) {
 			    node->child[0] = makeNode(lt, valuesPerNode, numMeanSplits - 1, temp);
 		    }
-		    
+
 		    if (gt.size() > 0) {
 			    node->child[1] = makeNode(gt, valuesPerNode, numMeanSplits - 1, temp);
 		    }
-		    
+
 	    }
-	    
+
 	    return node;
     }
 
@@ -927,7 +927,7 @@ public:
      */
     void clear() {
         typedef typename Table<_internal::Indirector<_AABSPTree::Handle<T> >, Node* >::Iterator It;
-  
+
         // Delete all handles stored in the member table
         It cur = memberTable.begin();
         It end = memberTable.end();
@@ -970,7 +970,7 @@ public:
         // Insert into the node
         node->valueArray.append(h);
         node->boundsArray.append(h->bounds);
-        
+
         // Insert into the node table
         Member m(h);
         memberTable.set(m, node);
@@ -1022,8 +1022,8 @@ public:
     /**
      Removes an object from the set in O(1) time.
      It is an error to remove members that are not already
-     present.  May unbalance the tree.  
-     
+     present.  May unbalance the tree.
+
      Removing an element never causes a node (split plane) to be removed...
      nodes are only changed when the tree is rebalanced.  This behavior
      is desirable because it allows the split planes to be serialized,
@@ -1075,7 +1075,7 @@ public:
      on <I>T</I> are independent of the bounds.  In
      that case, you may call update(v) to insert an
      element for the first time and call update(v)
-     again every time it moves to keep the tree 
+     again every time it moves to keep the tree
      up to date.
      */
     void update(const T& value) {
@@ -1091,15 +1091,15 @@ public:
      have moved substantially from their original positions
      (which unbalances the tree and causes the spatial
      queries to be slow).
-     
+
      @param valuesPerNode Maximum number of elements to put at
      a node.
 
-     @param numMeanSplits numMeanSplits = 0 gives a 
+     @param numMeanSplits numMeanSplits = 0 gives a
      fully axis aligned BSP-tree, where the balance operation attempts to balance
      the tree so that every splitting plane has an equal number of left
-     and right children (i.e. it is a <B>median</B> split along that axis).  
-     This tends to maximize average performance.  
+     and right children (i.e. it is a <B>median</B> split along that axis).
+     This tends to maximize average performance.
 
      You can override this behavior by
      setting a number of <B>mean</B> (average) splits.  numMeanSplits = MAX_INT
@@ -1126,7 +1126,7 @@ public:
         }
 
         Array<_AABSPTree::Handle<T> * > temp;
-        // Make a new root.  Work with a copy of the value array because 
+        // Make a new root.  Work with a copy of the value array because
         // makeNode clears the source array as it progresses
         Array<_AABSPTree::Handle<T> * > copy(oldRoot->valueArray);
         root = makeNode(copy, valuesPerNode, numMeanSplits, temp);
@@ -1195,7 +1195,7 @@ protected:
 public:
 
     /**
-     Returns all members inside the set of planes.  
+     Returns all members inside the set of planes.
       @param members The results are appended to this array.
      */
     void getIntersectingMembers(const Array<Plane>& plane, Array<T>& members) const {
@@ -1221,7 +1221,7 @@ public:
       */
     void getIntersectingMembers(const GCamera::Frustum& frustum, Array<T>& members) const {
         Array<Plane> plane;
-        
+
         for (int i = 0; i < frustum.faceArray.size(); ++i) {
             plane.append(frustum.faceArray[i].plane);
         }
@@ -1260,14 +1260,14 @@ public:
         // caller uses post increment (which they shouldn't!).
         Array<Node*>    stack;
 
-        /** The next index of current->valueArray to return. 
+        /** The next index of current->valueArray to return.
             Undefined when isEnd is true.*/
         int             nextValueArrayIndex;
 
         BoxIntersectionIterator() : isEnd(true) {}
-        
-        BoxIntersectionIterator(const AABox& b, const Node* root) : 
-           isEnd(root == NULL), box(b), 
+
+        BoxIntersectionIterator(const AABox& b, const Node* root) :
+           isEnd(root == NULL), box(b),
            node(const_cast<Node*>(root)), nextValueArrayIndex(-1) {
 
            // We intentionally start at the "-1" index of the current
@@ -1290,10 +1290,10 @@ public:
             } else if (other.isEnd) {
                 return false;
             } else {
-                // Two non-end iterators; see if they match.  This is kind of 
+                // Two non-end iterators; see if they match.  This is kind of
                 // silly; users shouldn't call == on iterators in general unless
                 // one of them is the end iterator.
-                if ((box != other.box) || (node != other.node) || 
+                if ((box != other.box) || (node != other.node) ||
                     (nextValueArrayIndex != other.nextValueArrayIndex) ||
                     (stack.length() != other.stack.length())) {
                     return false;
@@ -1322,7 +1322,7 @@ public:
 
 				// Search for the next node if we've exhausted this one
                 while ((! isEnd) &&  (nextValueArrayIndex >= node->valueArray.length())) {
-					// If we entered this loop, then the iterator has exhausted the elements at 
+					// If we entered this loop, then the iterator has exhausted the elements at
 					// node (possibly because it just switched to a child node with no members).
 					// This loop continues until it finds a node with members or reaches
 					// the end of the whole intersection search.
@@ -1333,7 +1333,7 @@ public:
 						(box.high()[node->splitAxis] > node->splitLocation)) {
 						stack.push(node->child[1]);
 					}
-                
+
 					// If the left child overlaps the box, push it onto the stack for
 					// processing.
 					if ((node->child[0] != NULL) &&
@@ -1342,7 +1342,7 @@ public:
 					}
 
 					if (stack.length() > 0) {
-						// Go on to the next node (which may be either one of the ones we 
+						// Go on to the next node (which may be either one of the ones we
 						// just pushed, or one from farther back the tree).
 						node = stack.pop();
 						nextValueArrayIndex = 0;
@@ -1358,7 +1358,7 @@ public:
 						foundIntersection = true;
 					} else {
 						++nextValueArrayIndex;
-						// If we exhaust this node, we'll loop around the master loop 
+						// If we exhaust this node, we'll loop around the master loop
 						// to find a new node.
 					}
 				}
@@ -1431,7 +1431,7 @@ public:
      Invoke a callback for every member along a ray until the closest intersection is found.
 
      @param callback either a function or an instance of a class with an overloaded operator() of the form:
-             
+
             <code>void callback(const Ray& ray, const T& object, float& distance)</code>.  If the ray hits the object
             before travelling distance <code>distance</code>, updates <code>distance</code> with the new distance to
             the intersection, otherwise leaves it unmodified.  A common example is:
@@ -1482,12 +1482,12 @@ public:
      */
     template<typename RayCallback>
     void intersectRay(
-        const Ray& ray, 
-        RayCallback& intersectCallback, 
+        const Ray& ray,
+        RayCallback& intersectCallback,
         float& distance,
         bool pStopAtFirstHit,
         bool intersectCallbackIsFast = false) const {
-        
+
         root->intersectRay(ray, intersectCallback, distance, pStopAtFirstHit, intersectCallbackIsFast);
 
     }
@@ -1509,7 +1509,7 @@ public:
 #if 0
     /**
       Stores the locations of the splitting planes (the structure but not the content)
-      so that the tree can be quickly rebuilt from a previous configuration without 
+      so that the tree can be quickly rebuilt from a previous configuration without
       calling balance.
      */
     void serializeStructure(BinaryOutput& bo) const {
@@ -1593,9 +1593,9 @@ public:
 
 
     /**
-     C++ STL style iterator method.  Returns the first member.  
+     C++ STL style iterator method.  Returns the first member.
      Use preincrement (++entry) to get to the next element (iteration
-     order is arbitrary).  
+     order is arbitrary).
      Do not modify the set while iterating.
      */
     Iterator begin() const {