diff options
Diffstat (limited to 'contrib/vmap_debugger/G3D/AABSPTree.h')
| -rw-r--r-- | contrib/vmap_debugger/G3D/AABSPTree.h | 374 |
1 files changed, 187 insertions, 187 deletions
diff --git a/contrib/vmap_debugger/G3D/AABSPTree.h b/contrib/vmap_debugger/G3D/AABSPTree.h index 543f06a881e..30eca17d08e 100644 --- a/contrib/vmap_debugger/G3D/AABSPTree.h +++ b/contrib/vmap_debugger/G3D/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. */ @@ -201,7 +201,7 @@ namespace _AABSPTree { during the median sort, and because MSVC 6 std::sort goes into an infinite loop if we compute the midpoint on the fly (possibly a floating point roundoff issue, where B<A and A<B both are true).*/ - Vector3 center; + Vector3 center; TValue 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; @@ -279,11 +279,11 @@ public: /** Compares centers */ class CenterComparator { public: - Vector3::Axis sortAxis; + Vector3::Axis sortAxis; - CenterComparator(Vector3::Axis a) : sortAxis(a) {} + CenterComparator(Vector3::Axis a) : sortAxis(a) {} - inline int operator()(_AABSPTree::Handle<T>* A, const _AABSPTree::Handle<T>* B) const { + inline int operator()(_AABSPTree::Handle<T>* A, const _AABSPTree::Handle<T>* B) const { float a = A->center[sortAxis]; float b = B->center[sortAxis]; @@ -294,18 +294,18 @@ public: } else { return 0; } - } + } }; /** Compares bounds for strict >, <, or overlap*/ class BoundsComparator { public: - Vector3::Axis sortAxis; + Vector3::Axis sortAxis; - BoundsComparator(Vector3::Axis a) : sortAxis(a) {} + BoundsComparator(Vector3::Axis a) : sortAxis(a) {} - inline int operator()(_AABSPTree::Handle<T>* A, const _AABSPTree::Handle<T>* B) const { + inline int operator()(_AABSPTree::Handle<T>* A, const _AABSPTree::Handle<T>* B) const { const AABox& a = A->bounds; const AABox& b = B->bounds; @@ -316,33 +316,33 @@ public: } else { return 0; } - } + } }; /** Compares bounds to the sort location */ class Comparator { public: - Vector3::Axis sortAxis; - float sortLocation; + Vector3::Axis sortAxis; + float sortLocation; - Comparator(Vector3::Axis a, float l) : sortAxis(a), sortLocation(l) {} + Comparator(Vector3::Axis a, float l) : sortAxis(a), sortLocation(l) {} - inline int operator()(_AABSPTree::Handle<T>* ignore, const _AABSPTree::Handle<T>* handle) const { + inline int operator()(_AABSPTree::Handle<T>* ignore, const _AABSPTree::Handle<T>* handle) const { const AABox& box = handle->bounds; debugAssert(ignore == NULL); - if (box.high()[sortAxis] < sortLocation) { + if (box.high()[sortAxis] < sortLocation) { // Box is strictly below the sort location return -1; - } else if (box.low()[sortAxis] > sortLocation) { + } else if (box.low()[sortAxis] > sortLocation) { // Box is strictly above the sort location - return 1; - } else { + return 1; + } else { // Box overlaps the sort location - return 0; - } - } + return 0; + } + } }; // Using System::malloc with this class provided no speed improvement. @@ -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; } @@ -450,47 +450,47 @@ public: } } - void verifyNode(const Vector3& lo, const Vector3& hi) { - // debugPrintf("Verifying: split %d @ %f [%f, %f, %f], [%f, %f, %f]\n", - // splitAxis, splitLocation, lo.x, lo.y, lo.z, hi.x, hi.y, hi.z); + void verifyNode(const Vector3& lo, const Vector3& hi) { + // debugPrintf("Verifying: split %d @ %f [%f, %f, %f], [%f, %f, %f]\n", + // splitAxis, splitLocation, lo.x, lo.y, lo.z, hi.x, hi.y, hi.z); debugAssert(lo == splitBounds.low()); debugAssert(hi == splitBounds.high()); - for (int i = 0; i < valueArray.length(); ++i) { - const AABox& b = valueArray[i]->bounds; + for (int i = 0; i < valueArray.length(); ++i) { + const AABox& b = valueArray[i]->bounds; debugAssert(b == boundsArray[i]); - for(int axis = 0; axis < 3; ++axis) { - debugAssert(b.low()[axis] <= b.high()[axis]); - debugAssert(b.low()[axis] >= lo[axis]); - debugAssert(b.high()[axis] <= hi[axis]); - } - } + for(int axis = 0; axis < 3; ++axis) { + debugAssert(b.low()[axis] <= b.high()[axis]); + debugAssert(b.low()[axis] >= lo[axis]); + debugAssert(b.high()[axis] <= hi[axis]); + } + } - if (child[0] || child[1]) { - debugAssert(lo[splitAxis] < splitLocation); - debugAssert(hi[splitAxis] > splitLocation); - } + if (child[0] || child[1]) { + debugAssert(lo[splitAxis] < splitLocation); + debugAssert(hi[splitAxis] > splitLocation); + } - Vector3 newLo = lo; - newLo[splitAxis] = splitLocation; - Vector3 newHi = hi; - newHi[splitAxis] = splitLocation; + Vector3 newLo = lo; + newLo[splitAxis] = splitLocation; + Vector3 newHi = hi; + newHi[splitAxis] = splitLocation; - if (child[0] != NULL) { - child[0]->verifyNode(lo, newHi); - } + if (child[0] != NULL) { + child[0]->verifyNode(lo, newHi); + } - if (child[1] != NULL) { - child[1]->verifyNode(newLo, hi); - } - } + if (child[1] != NULL) { + child[1]->verifyNode(newLo, hi); + } + } #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); - } + 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(); - + // 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(); - + 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); @@ -846,20 +846,20 @@ public: for (int i = 0; i < node->valueArray.size(); ++i) { _AABSPTree::Handle<T> * v = node->valueArray[i]; node->boundsArray[i] = v->bounds; - memberTable.set(Member(v), node); + memberTable.set(Member(v), node); + } + + if (lt.size() > 0) { + node->child[0] = makeNode(lt, valuesPerNode, numMeanSplits - 1, temp); } - 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; + 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; @@ -1317,51 +1317,51 @@ public: BoxIntersectionIterator& operator++() { ++nextValueArrayIndex; - bool foundIntersection = false; + bool foundIntersection = false; while (! isEnd && ! foundIntersection) { - // Search for the next node if we've exhausted this one + // 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 - // 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. - - // If the right child overlaps the box, push it onto the stack for - // processing. - if ((node->child[1] != NULL) && - (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) && - (box.low()[node->splitAxis] < node->splitLocation)) { - stack.push(node->child[0]); - } - - if (stack.length() > 0) { - // 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; - } else { - // That was the last node; we're done iterating - isEnd = true; - } - } - - // Search for the next intersection at this node until we run out of children - while (! isEnd && ! foundIntersection && (nextValueArrayIndex < node->valueArray.length())) { - if (box.intersects(node->boundsArray[nextValueArrayIndex])) { - foundIntersection = true; - } else { - ++nextValueArrayIndex; - // If we exhaust this node, we'll loop around the master loop - // to find a new node. - } - } + // 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. + + // If the right child overlaps the box, push it onto the stack for + // processing. + if ((node->child[1] != NULL) && + (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) && + (box.low()[node->splitAxis] < node->splitLocation)) { + stack.push(node->child[0]); + } + + if (stack.length() > 0) { + // 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; + } else { + // That was the last node; we're done iterating + isEnd = true; + } + } + + // Search for the next intersection at this node until we run out of children + while (! isEnd && ! foundIntersection && (nextValueArrayIndex < node->valueArray.length())) { + if (box.intersects(node->boundsArray[nextValueArrayIndex])) { + foundIntersection = true; + } else { + ++nextValueArrayIndex; + // If we exhaust this node, we'll loop around the master loop + // to find a new node. + } + } } return *this; @@ -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 { |