aabsptree.h

WOW 服务模拟端 支持2.4.3版本 来自开源的ASCENT 自己REPACK

                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.bounds);

                    // 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) {
                    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 "
                        "AABSPTree 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.  

                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 at the expense of
                average performance.  It tends to have better clustering behavior when
                members are not uniformly distributed.
                */
                void balance(int valuesPerNode = 5, int numMeanSplits = 3) {
                    if (root == NULL) {
                        // Tree is empty
                        return;
                    }

                    Array<Handle> handleArray;
                    root->getHandles(handleArray);

                    // Delete the old tree
                    clear();

                    root = makeNode(handleArray, 0, handleArray.size() - 1, 
                        valuesPerNode, numMeanSplits);

                    // Walk the tree, assigning splitBounds.  We start with unbounded
                    // space.
                    root->assignSplitBounds(AABox::maxFinite());

#ifdef _DEBUG
                    root->verifyNode(Vector3::minFinite(), Vector3::maxFinite());
#endif
                }

    private:

        /**
        @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 {

                    // Test values at this node against remaining planes
                    for (int v = node->valueArray.size() - 1; v >= 0; --v) {
                        if (! node->valueArray[v].bounds.culledBy(plane, dummy, parentMask)) {
                            members.append(node->valueArray[v].value);
                        }
                    }

                    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 AABSPTree<T>;

            /** 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) : 
            box(b), isEnd(root == NULL), nextValueArrayIndex(-1), node(const_cast<Node*>(root)) {

                // 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;