diff options
Diffstat (limited to 'src/shared/vmap/AABSPTree.h')
| -rw-r--r-- | src/shared/vmap/AABSPTree.h | 166 |
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 { |