aabsptree.h

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

                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 AABSPTree::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, true);

        }

        /** See AABSPTree::beginRayIntersection */
        class RayIntersectionIterator {
        private:
            friend class AABSPTree<T>;

            /** The stack frame contains all the info needed to resume
            computation for the RayIntersectionIterator */

            struct StackFrame {
                const Node* node;

                /** the total checking bounds for this frame */
                float minTime;

                /** minTime^2 */
                float minTime2;
                float maxTime;

                /** what we're checking right now, either from minTime to the
                split, or from the split to maxTime (more or less...
                there are edge cases) */
                float startTime;
                float endTime;

                /** endTime^2 */
                float endTime2;

                int nextChild;

                /** current index into node's valueArray */
                int valIndex;


                /** cache intersection values when they're checked on the preSide,
                split so they don't need to be checked again after the split. */
                Array<float> intersectionCache;

                void init(const Node* inNode, const Ray& ray,
                    float inMinTime, float inMaxTime) {
                        node     = inNode;
                        minTime  = inMinTime;
                        maxTime  = inMaxTime;
                        minTime2 = square(minTime);
                        valIndex = -1;

                        intersectionCache.resize(node->valueArray.length());

                        if (node->child[0] == NULL && node->child[1] == NULL) {
                            startTime = minTime;
                            endTime   = maxTime;
                            endTime2  = square(maxTime);
                            nextChild = -1;
                            return;
                        }

                        Vector3::Axis splitAxis     = node->splitAxis;
                        double        splitLocation = node->splitLocation;

                        // this is the time along the ray until the split.
                        // could be negative if the split is behind.
                        double splitTime =
                            (splitLocation - ray.origin[splitAxis]) /
                            ray.direction[splitAxis];

                        // If splitTime <= minTime we'll never reach the
                        // split, so set it to inf so as not to confuse endTime.
                        // It will be noted below that when splitTime is inf
                        // only one of this node's children will be searched
                        // (the pre child). Therefore it is critical that
                        // the correct child is gone too.
                        if (splitTime <= minTime) {
                            splitTime = inf();
                        }

                        startTime = minTime;
						endTime   = std::min((double)maxTime, splitTime);
                        endTime2  = square(endTime);

                        double rayLocation = ray.origin[splitAxis] +
                            ray.direction[splitAxis] * minTime;

                        if (rayLocation == splitLocation) {
                            // We're right on the split. Look ahead.
                            rayLocation = ray.origin[splitAxis] +
                                ray.direction[splitAxis] * maxTime;
                        }

                        if (rayLocation == splitLocation) {
                            // right on the split, looking exactly along
                            // it, so consider no children.
                            nextChild = -1;
                        } else if(rayLocation <= splitLocation) {
                            nextChild = 0;
                        } else {
                            nextChild = 1;
                        }
                    }
            };

        public:
            /** A minimum bound on the distance to the intersection. */
            double minDistance;

            /** A maximum bound on the distance to the intersection. */
            double maxDistance;

            /** Counts how many bounding box intersection tests have been made so
            far. */
            int debugCounter;

        private:
            Ray                 ray;
            bool                isEnd;

            Array<StackFrame>   stack;
            int                 stackLength;
            int                 stackIndex;
            int                 breakFrameIndex;
            bool                skipAABoxTests;
            double				boxMaxDist2;

            RayIntersectionIterator(const Ray& r, const Node* root, double pMaxTime, bool skip)
                : minDistance(0), maxDistance(G3D::inf()), debugCounter(0),
                ray(r), isEnd(root == NULL),
                stackLength(20), stackIndex(0), breakFrameIndex(-1),
                skipAABoxTests(skip)
            {
                stack.resize(stackLength);
                stack[stackIndex].init(root, ray, 0, G3D::inf());
                boxMaxDist2 = pMaxTime*pMaxTime;

                ++(*this);
            }


        public:
            /* public so we can have empty ones */
            RayIntersectionIterator() : isEnd(true) {}

            inline bool operator!=(const RayIntersectionIterator& other) const {
                return ! (*this == other);
            }

            /** Compares two iterators, but will only return true if both are at
            the end. */
            bool operator==(const RayIntersectionIterator& other) const {
                if (isEnd) {
                    return other.isEnd;
                }

                return false;
            }

            /**
            Marks the node where the most recent intersection occurred. If
            the iterator exhausts this node it will stop and set itself to
            the end iterator.

            Use this after you find a true intersection to stop the iterator
            from searching more than necessary.
            <B>Beta API-- subject to change</B>
            */
            // In theory this method could be smarter: the caller could pass in
            // the distance of the actual collision and the iterator would keep
            // itself from checking nodes or boxes beyond that distance.
            void markBreakNode() {
                breakFrameIndex = stackIndex;
            }

            /**
            Clears the break node. Can be used before or after the iterator
            stops from a break.
            <B>Beta API-- subject to change</B>
            */
            void clearBreakNode() {
                if (breakFrameIndex < 0) {
                    return;
                }

                if (isEnd && stackIndex >= 0) {
                    isEnd = false;
                }

                breakFrameIndex = -1;
            }


            RayIntersectionIterator& operator++() {
                alwaysAssertM(!isEnd, "Can't increment the end element of an iterator");

                StackFrame* s = &stack[stackIndex];

                // leave the loop if:
                //    end is reached (ie: stack is empty)
                //    found an intersection

                while (true) {
                    ++s->valIndex;

                    if (s->valIndex >= s->node->valueArray.length()) {
                        // This node is exhausted, look at its