aabsptree.h

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

                        // children.

                        Node* child = (s->nextChild >= 0) ?
                            s->node->child[s->nextChild] : NULL;
                        double childStartTime = s->startTime;
                        double childEndTime   = s->endTime;

                        if (s->endTime < s->maxTime) {
                            // we can come back to this frame,
                            // so reset it
                            s->valIndex  = -1;
                            s->startTime = s->endTime;
                            s->endTime   = s->maxTime;
                            s->endTime2  = square(s->maxTime);
                            s->nextChild = (s->nextChild >= 0) ?
                                (1 - s->nextChild) : -1;

                            // this could be changed somehow,
                            // since Array already does the
                            // power-of-two growth stuff
                            if (stackIndex == stackLength) {
                                stackLength *= 2;
                                stack.resize(stackLength);
                            }
                        } else {
                            // tail-recursion: we won't come
                            // back to this frame, so we can
                            // remove it.

                            if (stackIndex == breakFrameIndex) {
                                // This will be the case if the
                                // break frame is set on a node, but
                                // the node is exhausted so it won't
                                // be put on the stack. Here we
                                // decrement the break frame so that
                                // the break occurs when the current
                                // frame's parent is resumed.
                                --breakFrameIndex;
                            }

                            --stackIndex;
                        }

                        // There could have been a resize on the array, so
                        // do not use s (pointer into the array)!

                        if (child != NULL) {
                            ++stackIndex;
                            stack[stackIndex].init(
                                child, ray,
                                childStartTime, childEndTime);
                        }

                        if ((stackIndex < 0) || (stackIndex == breakFrameIndex)) {
                            isEnd = true;
                            break;
                        }

                        s = &stack[stackIndex];
                        continue;
                    }

                    if (skipAABoxTests) {
                        // No AABox test-- return everything
                        minDistance = s->startTime;
                        maxDistance = s->endTime;
                        break;
                    } else {
                        double t2;
                        // this can be an exact equals because the two
                        // variables are initialized to the same thing
                        if (s->startTime == s->minTime) {
                            Vector3 location;
                            bool insiteOk;
                            Vector3 mynormal;
                            if (
                                VMAP::MyCollisionDetection::collisionLocationForMovingPointFixedAABox(
                                ray.origin, ray.direction,
                                s->node->valueArray[s->valIndex].bounds,
                                location,insiteOk, mynormal )) {
                                    // Optimization: store t-squared 
                                    t2 = (location - ray.origin).squaredLength();
                                } else {
                                    t2 = inf();
                                }
                                if(t2 > boxMaxDist2) 
                                    t2=inf(); // too far off
                                //t = ray.intersectionTime(s->node->valueArray[s->valIndex].bounds);
                                s->intersectionCache[s->valIndex] = t2;
                                ++debugCounter;
                        } else {
                            t2 = s->intersectionCache[s->valIndex];
                        }

                        // use minTime here because intersection may be
                        // detected pre-split, but be valid post-split, too.
                        if ((t2 >= s->minTime2) && (t2 < s->endTime2)) {
                            // Gives slightly tighter bounds but runs slower:
                            // minDistance = max(t, s->startTime);
                            minDistance = s->startTime;
                            maxDistance = s->endTime;
                            break;
                        }
                    }

                }

                return *this;
            }


            /** 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 stack[stackIndex].node->valueArray[stack[stackIndex].valIndex].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[stackIndex].node->valueArray[stack[stackIndex].valIndex].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[stackIndex].node->valueArray[stack[stackIndex].valIndex].value);
            }

        };


        /**
        Generates a RayIntersectionIterator that produces successive
        elements from the set whose bounding boxes are intersected by the ray.
        Typically used for ray tracing, hit-scan, and collision detection.

        The elements are generated mostly in the order that they are hit by the
        ray, so that iteration may end abruptly when the closest intersection to
        the ray origin has been reached. Because the elements within a given
        kd-tree node are unordered, iteration may need to proceed a little past
        the first member returned in order to find the closest intersection. The
        iterator doesn't automatically find the first intersection because it is
        looking at bounding boxes, not the true intersections.

        When the caller finds a true intersection it should call markBreakNode()
        on the iterator. This will stop the iterator (setting it to the end
        iterator) when the current node and relevant children are exhausted.

        Complicating the matter further, some members straddle the plane. The
        iterator produces these members <I>twice</I>. The first time it is
        produced the caller should only consider intersections on the near side of
        the split plane. The second time, the caller should only consider
        intersections on the far side. The minDistance and maxDistance fields
        specify the range on which intersections should be considered. Be aware
        that they may be inf or zero.

        An example of how to use the iterator follows. Almost all ray intersection
        tests will have identical structure.

        <PRE>

        void findFirstIntersection(
        const Ray&  ray,
        Object*&    firstObject,
        double&     firstTime) {

        firstObject   = NULL;
        firstDistance = inf();

        typedef AABSPTree<Object*>::RayIntersectionIterator IT;
        const IT end = tree.endRayIntersection();

        for (IT obj = tree.beginRayIntersection(ray);
        obj != end;
        ++obj) {  // (preincrement is *much* faster than postincrement!) 

        // Call your accurate intersection test here.  It is guaranteed
        // that the ray hits the bounding box of obj.  (*obj) has type T,
        // so you can call methods directly using the "->" operator.
        double t = obj->distanceUntilIntersection(ray);

        // Often methods like "distanceUntilIntersection" can be made more
        // efficient by providing them with the time at which to start and
        // to give up looking for an intersection; that is, 
        // obj.minDistance and iMin(firstDistance, obj.maxDistance).

        static const double epsilon = 0.00001;
        if ((t < firstDistance) && 
        (t <= obj.maxDistance + epsilon) &&
        (t >= obj.minDistance - epsilon)) {

        // This is the new best collision time
        firstObject   = obj;
        firstDistance = t;

        // Tell the iterator that we've found at least one 
        // intersection.  It will finish looking at all
        // objects in this node and then terminate.
        obj.markBreakNode();
        }
        }
        }
        </PRE>


        @param skipAABoxTests Set to true when the intersection test for a
        member is faster than an AABox-ray intersection test.  In that case, 
        the iterator will not use a bounding box test on values that are
        returned.  Leave false (the default) for objects with slow intersection
        tests.  In that case, the iterator guarantees that the ray hits the
        bounds of any object returned.

        @cite Implementation by Pete Hopkins
        */
        RayIntersectionIterator beginRayIntersection(const Ray& ray, double pMaxTime, bool skipAABoxTests = false) const
        {
            return RayIntersectionIterator(ray, root, pMaxTime, skipAABoxTests);
        }

        RayIntersectionIterator endRayIntersection() const
        {
            return RayIntersectionIterator();
        }


        /**
        Returns an array of all members of the set.  See also AABSPTree::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 AABSPTree<T>;

            // Note: this is a Table iterator, we are currently defining
            // Set iterator
            typename Table<T, Node*>::Iterator it;

            Iterator(const typename Table<T, Node*>::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());
        }
    };

#define KDTreeSet AABSPTree

}

#endif