diff options
Diffstat (limited to 'dep/include/g3dlite/G3D/PointKDTree.h')
| -rw-r--r-- | dep/include/g3dlite/G3D/PointKDTree.h | 1185 |
1 files changed, 0 insertions, 1185 deletions
diff --git a/dep/include/g3dlite/G3D/PointKDTree.h b/dep/include/g3dlite/G3D/PointKDTree.h deleted file mode 100644 index 151cbd5f2f3..00000000000 --- a/dep/include/g3dlite/G3D/PointKDTree.h +++ /dev/null @@ -1,1185 +0,0 @@ -/** - @file PointKDTree.h - - @maintainer Morgan McGuire, http://graphics.cs.williams.edu - - @created 2004-01-11 - @edited 2008-11-02 - - Copyright 2000-2009, Morgan McGuire. - All rights reserved. - - */ - -#ifndef X_PointKDTree_H -#define X_PointKDTree_H - -#include "G3D/platform.h" -#include "G3D/Array.h" -#include "G3D/Table.h" -#include "G3D/Vector2.h" -#include "G3D/Vector3.h" -#include "G3D/Vector4.h" -#include "G3D/AABox.h" -#include "G3D/Sphere.h" -#include "G3D/Box.h" -#include "G3D/BinaryInput.h" -#include "G3D/BinaryOutput.h" -#include "G3D/CollisionDetection.h" -#include "G3D/GCamera.h" -#include "G3D/PositionTrait.h" -#include <algorithm> - -namespace G3D { - -/** - A set data structure that supports spatial queries using an axis-aligned - BSP tree for speed. - - PointKDTree allows you to quickly find points in 3D that lie within - a box or sphere. For large sets of objects it is much faster - than testing each object for a collision. See also G3D::KDTree; this class - is optimized for point sets, e.g.,for use in photon mapping and mesh processing. - - <B>Template Parameters</B> - - <br> - - <br>The template parameter <I>T</I> must be one for which - the following functions are overloaded: - - <pre> - T::T(); <I>(public constructor of no arguments)</I> - - template<> struct PositionTrait<class T> { - static void getPosition(const T& v, G3D::Vector3& p);}; - - template <> struct HashTrait<class T> { - static size_t hashCode(const T& key);}; - - template<> struct EqualsTrait<class T> { - static bool equals(const T& a, const T& b); }; - </pre> - - <p> - - G3D provides these for the Vector2, Vector3, and Vector4 classes. - If you use a custom class, or a pointer to a custom class, you will need - to define those functions. - - <B>Moving %Set Members</B> - <DT>It is important that objects do not move without updating the - PointKDTree. If the position of an object is about - to change, PointKDTree::remove it before they change and - PointKDTree::insert it again afterward. For objects - where the hashCode and == operator are invariant with respect - to the 3D position, - you can use the PointKDTree::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 PointKDTree. Values - are copied interally. All PointKDTree iterators convert to pointers to constant - values to reinforce this. - - If you want to mutate the objects you intend to store in a PointKDTree - simply insert <I>pointers</I> to your objects instead of the objects - themselves, and ensure that the above operations are defined. (And - actually, because values are copied, if your values are large you may - want to insert pointers anyway, to save space and make the balance - operation faster.) - - <B>Dimensions</B> - Although designed as a 3D-data structure, you can use the PointKDTree - for data distributed along 2 or 1 axes by simply returning bounds - that are always zero along one or more dimensions. - -*/ -template<class T, - class PositionFunc = PositionTrait<T>, - class HashFunc = HashTrait<T>, - class EqualsFunc = EqualsTrait<T> > -class PointKDTree { -protected: -#define TreeType PointKDTree<T, PositionFunc, HashFunc, EqualsFunc> - - // Unlike the KDTree, the PointKDTree assumes that T elements are - // small and keeps the handle and cached position together instead of - // placing them in separate bounds arrays. Also note that a copy of T - // is kept in the member table and that there is no indirection. - class Handle { - private: - Vector3 m_position; - - public: - T value; - - inline Handle() {} - inline Handle(const T& v) : value(v) { - PositionFunc::getPosition(v, m_position); - } - - /** Used by makeNode to create fake handles for partitioning. */ - void setPosition(const Vector3& v) { - m_position = v; - } - - inline const Vector3& position() const { - return m_position; - } - }; - - /** Returns the bounds of the sub array. Used by makeNode. */ - static AABox computeBounds( - const Array<Handle>& point) { - - if (point.size() == 0) { - return AABox(Vector3::inf(), Vector3::inf()); - } - - AABox bounds(point[0].position()); - - for (int p = 0; p < point.size(); ++p) { - bounds.merge(point[p].position()); - } - - return bounds; - } - - class Node { - public: - - /** Spatial bounds on all values at this node and its children, based purely on - the parent's splitting planes. May be infinite */ - AABox splitBounds; - - Vector3::Axis splitAxis; - - /** Location along the specified axis */ - float splitLocation; - - /** child[0] contains all values strictly - smaller than splitLocation along splitAxis. - - child[1] contains all values strictly - larger. - - Both may be NULL if there are not enough - values to bother recursing. - */ - Node* child[2]; - - /** Values if this is a leaf node). */ - Array<Handle> valueArray; - - /** Creates node with NULL children */ - Node() { - splitAxis = Vector3::X_AXIS; - splitLocation = 0; - splitBounds = AABox(-Vector3::inf(), Vector3::inf()); - for (int i = 0; i < 2; ++i) { - child[i] = NULL; - } - } - - /** - Doesn't clone children. - */ - Node(const Node& other) : valueArray(other.valueArray) { - splitAxis = other.splitAxis; - splitLocation = other.splitLocation; - splitBounds = other.splitBounds; - for (int i = 0; i < 2; ++i) { - child[i] = NULL; - } - } - - /** Copies the specified subarray of pt into point, NULLs the children. - Assumes a second pass will set splitBounds. */ - Node(const Array<Handle>& pt) { - splitAxis = Vector3::X_AXIS; - splitLocation = 0; - for (int i = 0; i < 2; ++i) { - child[i] = NULL; - } - valueArray = pt; - } - - - /** Deletes the children (but not the values) */ - ~Node() { - for (int i = 0; i < 2; ++i) { - delete child[i]; - } - } - - - /** Returns true if this node is a leaf (no children) */ - inline bool isLeaf() const { - return (child[0] == NULL) && (child[1] == NULL); - } - - - /** - Recursively appends all handles and children's handles - to the array. - */ - void getHandles(Array<Handle>& handleArray) const { - handleArray.append(valueArray); - for (int i = 0; i < 2; ++i) { - if (child[i] != NULL) { - child[i]->getHandles(handleArray); - } - } - } - - - 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 Vector3& b = valueArray[i].position(); - debugAssert(splitBounds.contains(b)); - } - - 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; - - if (child[0] != NULL) { - child[0]->verifyNode(lo, newHi); - } - - if (child[1] != NULL) { - child[1]->verifyNode(newLo, hi); - } - } - - - /** - 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 - calling balance. - */ - static void serializeStructure(const Node* n, BinaryOutput& bo) { - if (n == NULL) { - bo.writeUInt8(0); - } else { - bo.writeUInt8(1); - n->splitBounds.serialize(bo); - serialize(n->splitAxis, bo); - bo.writeFloat32(n->splitLocation); - for (int c = 0; c < 2; ++c) { - serializeStructure(n->child[c], bo); - } - } - } - - /** Clears the member table */ - static Node* deserializeStructure(BinaryInput& bi) { - if (bi.readUInt8() == 0) { - return NULL; - } else { - Node* n = new Node(); - n->splitBounds.deserialize(bi); - deserialize(n->splitAxis, bi); - n->splitLocation = bi.readFloat32(); - for (int c = 0; c < 2; ++c) { - n->child[c] = deserializeStructure(bi); - } - } - } - - /** Returns the deepest node that completely contains bounds. */ - Node* findDeepestContainingNode(const Vector3& point) { - - // See which side of the splitting plane the bounds are on - if (point[splitAxis] < splitLocation) { - // Point is on the low side. Recurse into the child - // if it exists. - if (child[0] != NULL) { - return child[0]->findDeepestContainingNode(point); - } - } else if (point[splitAxis] > splitLocation) { - // Point is on the high side, recurse into the child - // if it exists. - if (child[1] != NULL) { - return child[1]->findDeepestContainingNode(point); - } - } - - // There was no containing child, so this node is the - // deepest containing node. - return this; - } - - /** Appends all members that intersect the box. - If useSphere is true, members are tested against the sphere instead. */ - void getIntersectingMembers( - const AABox& sphereBounds, - const Sphere& sphere, - Array<T>& members) const { - - // Test all values at this node. Extract the - // underlying C array for speed - const int N = valueArray.size(); - const Handle* handleArray = valueArray.getCArray(); - - const float r2 = square(sphere.radius); - - // Copy the sphere center so that it is on the stack near the radius - const Vector3 center = sphere.center; - for (int v = 0; v < N; ++v) { - if ((center - handleArray[v].position()).squaredLength() <= r2) { - members.append(handleArray[v].value); - } - } - - // If the left child overlaps the box, recurse into it - if (child[0] && (sphereBounds.low()[splitAxis] < splitLocation)) { - child[0]->getIntersectingMembers(sphereBounds, sphere, members); - } - - // If the right child overlaps the box, recurse into it - if (child[1] && (sphereBounds.high()[splitAxis] > splitLocation)) { - child[1]->getIntersectingMembers(sphereBounds, sphere, members); - } - } - - /** Appends all members that intersect the box. - If useSphere is true, members are tested against the sphere instead. - - Implemented using both box and sphere tests to simplify the implementation - of a future beginSphereInteresection iterator using the same underlying - BoxIterator class. - */ - void getIntersectingMembers( - const AABox& box, - const Sphere& sphere, - Array<T>& members, - bool useSphere) const { - - // Test all values at this node - for (int v = 0; v < valueArray.size(); ++v) { - if ((useSphere && sphere.contains(valueArray[v].position())) || - (! useSphere && box.contains(valueArray[v].position()))) { - members.append(valueArray[v].value); - } - } - - // If the left child overlaps the box, recurse into it - if ((child[0] != NULL) && (box.low()[splitAxis] < splitLocation)) { - child[0]->getIntersectingMembers(box, sphere, members, useSphere); - } - - // If the right child overlaps the box, recurse into it - if ((child[1] != NULL) && (box.high()[splitAxis] > splitLocation)) { - child[1]->getIntersectingMembers(box, sphere, members, useSphere); - } - } - - /** - Recurse through the tree, assigning splitBounds fields. - */ - void assignSplitBounds(const AABox& myBounds) { - splitBounds = myBounds; - -# ifdef G3D_DEBUG - if (child[0] || child[1]) { - debugAssert(splitBounds.high()[splitAxis] > splitLocation); - debugAssert(splitBounds.low()[splitAxis] < splitLocation); - } -# endif - - AABox childBounds[2]; - myBounds.split(splitAxis, splitLocation, childBounds[0], childBounds[1]); - - for (int c = 0; c < 2; ++c) { - if (child[c]) { - child[c]->assignSplitBounds(childBounds[c]); - } - } - } - }; - - class AxisComparator { - private: - Vector3::Axis sortAxis; - - public: - - AxisComparator(Vector3::Axis s) : sortAxis(s) {} - - inline int operator()(const Handle& A, const Handle& B) const { - if (A.position()[sortAxis] > B.position()[sortAxis]) { - return -1; - } else if (A.position()[sortAxis] < B.position()[sortAxis]) { - return 1; - } else { - return 0; - } - } - }; - - /** - Recursively subdivides the subarray. - - The source array will be cleared after it is used - - Call assignSplitBounds() on the root node after making a tree. - */ - Node* makeNode( - Array<Handle>& source, - Array<Handle>& temp, - int valuesPerNode, - int numMeanSplits) { - - 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(source[i].value, node); - } - - } else { - // Make a new internal node - node = new Node(); - - const AABox bounds = computeBounds(source); - const Vector3 extent = bounds.high() - bounds.low(); - - Vector3::Axis splitAxis = extent.primaryAxis(); - - float splitLocation; - - Array<Handle> lt, gt; - - if (numMeanSplits <= 0) { - source.medianPartition(lt, node->valueArray, gt, temp, AxisComparator(splitAxis)); - splitLocation = node->valueArray[0].position()[splitAxis]; - - if ((node->valueArray.size() > source.size() / 2) && - (source.size() > 10)) { - // Our median split put an awful lot of points on the splitting plane. Try a mean - // split instead - numMeanSplits = 1; - } - } - - if (numMeanSplits > 0) { - // Compute the mean along the axis - - splitLocation = (bounds.high()[splitAxis] + - bounds.low()[splitAxis]) / 2.0; - - Handle splitHandle; - Vector3 v; - v[splitAxis] = splitLocation; - splitHandle.setPosition(v); - - source.partition(splitHandle, lt, node->valueArray, gt, AxisComparator(splitAxis)); - } - -# if defined(G3D_DEBUG) && defined(VERIFY_TREE) - for (int i = 0; i < lt.size(); ++i) { - const Vector3& v = lt[i].position(); - debugAssert(v[splitAxis] < splitLocation); - } - for (int i = 0; i < gt.size(); ++i) { - debugAssert(gt[i].position()[splitAxis] > splitLocation); - } - for (int i = 0; i < node->valueArray.size(); ++i) { - debugAssert(node->valueArray[i].position()[splitAxis] == splitLocation); - } -# endif - - node->splitAxis = splitAxis; - node->splitLocation = splitLocation; - - // Throw away the source array to save memory - source.fastClear(); - - if (lt.size() > 0) { - node->child[0] = makeNode(lt, temp, valuesPerNode, numMeanSplits - 1); - } - - if (gt.size() > 0) { - node->child[1] = makeNode(gt, temp, valuesPerNode, numMeanSplits - 1); - } - - // Add the values stored at this interior node to the member table - for(int i = 0; i < node->valueArray.size(); ++i) { - memberTable.set(node->valueArray[i].value, node); - } - - } - - return node; - } - - /** - Recursively clone the passed in node tree, setting - pointers for members in the memberTable as appropriate. - called by the assignment operator. - */ - Node* cloneTree(Node* src) { - Node* dst = new Node(*src); - - // Make back pointers - for (int i = 0; i < dst->valueArray.size(); ++i) { - memberTable.set(dst->valueArray[i].value, dst); - } - - // Clone children - for (int i = 0; i < 2; ++i) { - if (src->child[i] != NULL) { - dst->child[i] = cloneTree(src->child[i]); - } - } - - return dst; - } - - /** Maps members to the node containing them */ - typedef Table<T, Node*, HashFunc, EqualsFunc> MemberTable; - MemberTable memberTable; - - Node* root; - -public: - - /** To construct a balanced tree, insert the elements and then call - PointKDTree::balance(). */ - PointKDTree() : root(NULL) {} - - - PointKDTree(const PointKDTree& src) : root(NULL) { - *this = src; - } - - - PointKDTree& operator=(const PointKDTree& src) { - delete root; - // Clone tree takes care of filling out the memberTable. - root = cloneTree(src.root); - return *this; - } - - - ~PointKDTree() { - clear(); - } - - /** - Throws out all elements of the set and erases the structure of the tree. - */ - void clear() { - memberTable.clear(); - delete root; - root = NULL; - } - - /** Removes all elements of the set while maintaining the structure of the tree */ - void clearData() { - memberTable.clear(); - Array<Node*> stack; - stack.push(root); - while (stack.size() > 0) { - Node* node = stack.pop(); - node->valueArray.fastClear(); - - for (int i = 0; i < 2; ++i) { - if (node->child[i] != NULL) { - stack.push(node->child[i]); - } - } - } - } - - - int size() const { - return memberTable.size(); - } - - /** - Inserts an object into the set if it is not - already present. O(log n) time. Does not - cause the tree to be balanced. - */ - void insert(const T& value) { - if (contains(value)) { - // Already in the set - return; - } - - Handle h(value); - - if (root == NULL) { - // This is the first node; create a root node - root = new Node(); - } - - Node* node = root->findDeepestContainingNode(h.position()); - - // Insert into the node - node->valueArray.append(h); - - // Insert into the node table - memberTable.set(value, node); - } - - /** Inserts each elements in the array in turn. If the tree - begins empty (no structure and no elements), this is faster - than inserting each element in turn. You still need to balance - the tree at the end.*/ - void insert(const Array<T>& valueArray) { - // Pre-size the member table to avoid multiple allocations - memberTable.setSizeHint(valueArray.size() + size()); - - if (root == NULL) { - // Optimized case for an empty tree; don't bother - // searching or reallocating the root node's valueArray - // as we incrementally insert. - root = new Node(); - root->valueArray.resize(valueArray.size()); - for (int i = 0; i < valueArray.size(); ++i) { - // Insert in opposite order so that we have the exact same - // data structure as if we inserted each (i.e., order is reversed - // from array). - root->valueArray[valueArray.size() - i - 1] = Handle(valueArray[i]); - memberTable.set(valueArray[i], root); - } - } else { - // Insert at appropriate tree depth. - for (int i = 0; i < valueArray.size(); ++i) { - insert(valueArray[i]); - } - } - } - - - /** - Returns true if this object is in the set, otherwise - returns false. O(1) time. - */ - bool contains(const T& value) { - return memberTable.containsKey(value); - } - - - /** - 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. - - 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, - and then deserialized into an empty tree which can be repopulated. - */ - void remove(const T& value) { - debugAssertM(contains(value), - "Tried to remove an element from a " - "PointKDTree that was not present"); - - Array<Handle>& list = memberTable[value]->valueArray; - - // Find the element and remove it - for (int i = list.length() - 1; i >= 0; --i) { - if (list[i].value == value) { - list.fastRemove(i); - break; - } - } - memberTable.remove(value); - } - - - /** - If the element is in the set, it is removed. - The element is then inserted. - - This is useful when the == and hashCode methods - 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 - up to date. - */ - void update(const T& value) { - if (contains(value)) { - remove(value); - } - insert(value); - } - - - /** - Rebalances the tree (slow). Call when objects - 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 - 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; all querries will return in the same amount of time. - - You can override this behavior by - setting a number of <B>mean</B> (average) splits. numMeanSplits = MAX_INT - creates a full oct-tree, which tends to optimize peak performance (some areas of the scene will terminate after few recursive splits) at the expense of - peak performance. - */ - void balance(int valuesPerNode = 40, int numMeanSplits = 3) { - if (root == NULL) { - // Tree is empty - return; - } - - Array<Handle> handleArray; - root->getHandles(handleArray); - - // Delete the old tree - clear(); - - Array<Handle> temp; - root = makeNode(handleArray, temp, valuesPerNode, numMeanSplits); - temp.fastClear(); - - // Walk the tree, assigning splitBounds. We start with unbounded - // space. - root->assignSplitBounds(AABox::maxFinite()); - -# ifdef _DEBUG - root->verifyNode(Vector3::minFinite(), Vector3::maxFinite()); -# endif - } - -private: - - /** - Returns the elements - - @param parentMask The mask that this node returned from culledBy. - */ - static void getIntersectingMembers( - const Array<Plane>& plane, - Array<T>& members, - Node* node, - uint32 parentMask) { - - int dummy; - - if (parentMask == 0) { - // None of these planes can cull anything - for (int v = node->valueArray.size() - 1; v >= 0; --v) { - members.append(node->valueArray[v].value); - } - - // Iterate through child nodes - for (int c = 0; c < 2; ++c) { - if (node->child[c]) { - getIntersectingMembers(plane, members, node->child[c], 0); - } - } - } else { - - if (node->valueArray.size() > 0) { - // This is a leaf; check the points - debugAssertM(node->child[0] == NULL, "Malformed Point tree"); - debugAssertM(node->child[1] == NULL, "Malformed Point tree"); - - // Test values at this node against remaining planes - for (int p = 0; p < plane.size(); ++p) { - if ((parentMask >> p) & 1 != 0) { - // Test against this plane - const Plane& curPlane = plane[p]; - for (int v = node->valueArray.size() - 1; v >= 0; --v) { - if (curPlane.halfSpaceContains(node->valueArray[v].position())) { - members.append(node->valueArray[v].value); - } - } - } - } - } else { - - uint32 childMask = 0xFFFFFF; - - // Iterate through child nodes - for (int c = 0; c < 2; ++c) { - if (node->child[c] && - ! node->child[c]->splitBounds.culledBy(plane, dummy, parentMask, childMask)) { - // This node was not culled - getIntersectingMembers(plane, members, node->child[c], childMask); - } - } - } - } - } - -public: - - /** - 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 { - if (root == NULL) { - return; - } - - getIntersectingMembers(plane, members, root, 0xFFFFFF); - } - - /** - Typically used to find all visible - objects inside the view frustum (see also GCamera::getClipPlanes)... i.e. all objects - <B>not</B> culled by frustum. - - Example: - <PRE> - Array<Object*> visible; - tree.getIntersectingMembers(camera.frustum(), visible); - // ... Draw all objects in the visible array. - </PRE> - @param members The results are appended to this array. - */ - 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); - } - - getIntersectingMembers(plane, members); - } - - /** - C++ STL style iterator variable. See beginBoxIntersection(). - The iterator overloads the -> (dereference) operator, so this - acts like a pointer to the current member. - */ - // This iterator turns Node::getIntersectingMembers into a - // coroutine. It first translates that method from recursive to - // stack based, then captures the system state (analogous to a Scheme - // continuation) after each element is appended to the member array, - // and allowing the computation to be restarted. - class BoxIntersectionIterator { - private: - friend class TreeType; - - /** True if this is the "end" iterator instance */ - bool isEnd; - - /** The box that we're testing against. */ - AABox box; - - /** Node that we're currently looking at. Undefined if isEnd - is true. */ - Node* node; - - /** Nodes waiting to be processed */ - // We could use backpointers within the tree and careful - // state management to avoid ever storing the stack-- but - // it is much easier this way and only inefficient if the - // caller uses post increment (which they shouldn't!). - Array<Node*> stack; - - /** 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), - node(const_cast<Node*>(root)), nextValueArrayIndex(-1) { - - // We intentionally start at the "-1" index of the current - // node so we can use the preincrement operator to move - // ourselves to element 0 instead of repeating all of the - // code from the preincrement method. Note that this might - // cause us to become the "end" instance. - ++(*this); - } - - public: - - inline bool operator!=(const BoxIntersectionIterator& other) const { - return ! (*this == other); - } - - bool operator==(const BoxIntersectionIterator& other) const { - if (isEnd) { - return other.isEnd; - } else if (other.isEnd) { - return false; - } else { - // 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) || - (nextValueArrayIndex != other.nextValueArrayIndex) || - (stack.length() != other.stack.length())) { - return false; - } - - // See if the stacks are the same - for (int i = 0; i < stack.length(); ++i) { - if (stack[i] != other.stack[i]) { - return false; - } - } - - // We failed to find a difference; they must be the same - return true; - } - } - - /** - Pre increment. - */ - BoxIntersectionIterator& operator++() { - ++nextValueArrayIndex; - - bool foundIntersection = false; - while (! isEnd && ! foundIntersection) { - - // 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->valueArray[nextValueArrayIndex].bounds)) { - foundIntersection = true; - } else { - ++nextValueArrayIndex; - // If we exhaust this node, we'll loop around the master loop - // to find a new node. - } - } - } - - return *this; - } - - /** - Post increment (much slower than preincrement!). - */ - BoxIntersectionIterator operator++(int) { - BoxIntersectionIterator old = *this; - ++this; - return old; - } - - /** Overloaded dereference operator so the iterator can masquerade as a pointer - to a member */ - const T& operator*() const { - alwaysAssertM(! isEnd, "Can't dereference the end element of an iterator"); - return node->valueArray[nextValueArrayIndex].value; - } - - /** Overloaded dereference operator so the iterator can masquerade as a pointer - to a member */ - T const * operator->() const { - alwaysAssertM(! isEnd, "Can't dereference the end element of an iterator"); - return &(stack.last()->valueArray[nextValueArrayIndex].value); - } - - /** Overloaded cast operator so the iterator can masquerade as a pointer - to a member */ - operator T*() const { - alwaysAssertM(! isEnd, "Can't dereference the end element of an iterator"); - return &(stack.last()->valueArray[nextValueArrayIndex].value); - } - }; - - - /** - Iterates through the members that intersect the box - */ - BoxIntersectionIterator beginBoxIntersection(const AABox& box) const { - return BoxIntersectionIterator(box, root); - } - - BoxIntersectionIterator endBoxIntersection() const { - // The "end" iterator instance - return BoxIntersectionIterator(); - } - - /** - Appends all members whose bounds intersect the box. - See also PointKDTree::beginBoxIntersection. - */ - void getIntersectingMembers(const AABox& box, Array<T>& members) const { - if (root == NULL) { - return; - } - root->getIntersectingMembers(box, Sphere(Vector3::zero(), 0), members, false); - } - - - /** - @param members The results are appended to this array. - */ - void getIntersectingMembers(const Sphere& sphere, Array<T>& members) const { - if (root == NULL) { - return; - } - - AABox box; - sphere.getBounds(box); - root->getIntersectingMembers(box, sphere, members); - - } - - - /** - 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 - calling balance. - */ - void serializeStructure(BinaryOutput& bo) const { - Node::serializeStructure(root, bo); - } - - /** Clears the member table */ - void deserializeStructure(BinaryInput& bi) { - clear(); - root = Node::deserializeStructure(bi); - } - - /** - Returns an array of all members of the set. See also PointKDTree::begin. - */ - void getMembers(Array<T>& members) const { - memberTable.getKeys(members); - } - - - /** - C++ STL style iterator variable. See begin(). - Overloads the -> (dereference) operator, so this acts like a pointer - to the current member. - */ - class Iterator { - private: - friend class TreeType; - - // Note: this is a Table iterator, we are currently defining - // Set iterator - typename MemberTable::Iterator it; - - Iterator(const typename MemberTable::Iterator& it) : it(it) {} - - public: - inline bool operator!=(const Iterator& other) const { - return !(*this == other); - } - - bool operator==(const Iterator& other) const { - return it == other.it; - } - - /** - Pre increment. - */ - Iterator& operator++() { - ++it; - return *this; - } - - /** - Post increment (slower than preincrement). - */ - Iterator operator++(int) { - Iterator old = *this; - ++(*this); - return old; - } - - const T& operator*() const { - return it->key; - } - - T* operator->() const { - return &(it->key); - } - - operator T*() const { - return &(it->key); - } - }; - - - /** - C++ STL style iterator method. Returns the first member. - Use preincrement (++entry) to get to the next element (iteration - order is arbitrary). - Do not modify the set while iterating. - */ - Iterator begin() const { - return Iterator(memberTable.begin()); - } - - - /** - C++ STL style iterator method. Returns one after the last iterator - element. - */ - Iterator end() const { - return Iterator(memberTable.end()); - } -#undef TreeType -}; - -} - -#endif |