aabsptree.h

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

/**
@file AABSPTree.h

@maintainer Morgan McGuire, [e-mail]

@created 2004-01-11
@edited  2005-02-24

Copyright 2000-2005, Morgan McGuire.
All rights reserved.

*/

#ifndef G3D_AABSPTREE_H
#define G3D_AABSPTREE_H

#include "G3D/platform.h"
#include "G3D/Array.h"
#include "G3D/Table.h"
#include "G3D/Vector3.h"
#include "G3D/AABox.h"
#include "G3D/Sphere.h"
#include "G3D/Box.h"
#include "G3D/Triangle.h"
#include "G3D/GCamera.h"
//#include "G3D/BinaryInput.h"
//#include "G3D/BinaryOutput.h"
#include "G3D/CollisionDetection.h"
#include <algorithm>

#include "RayIntersectionIterator.h"

#ifdef _ASSEMBLER_DEBUG
#ifndef g_df
extern FILE *g_df;
#endif
#endif


inline void getBounds(const G3D::Vector3& v, G3D::AABox& out) {
    out = G3D::AABox(v);
}


inline void getBounds(const G3D::AABox& a, G3D::AABox& out) {
    out = a;
}


inline void getBounds(const G3D::Sphere& s, G3D::AABox& out) {
    s.getBounds(out);
}


inline void getBounds(const G3D::Box& b, G3D::AABox& out) {
    b.getBounds(out);
}


inline void getBounds(const G3D::Triangle& t, G3D::AABox& out) {
    t.getBounds(out);
}

namespace G3D {

    /**
    A set that supports spatial queries using an axis-aligned
    BSP tree for speed.

    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 
    axis-aligned bounds.  This increases the cost of insertion to
    O(log n) but allows fast overlap queries.

    <B>Template Parameters</B>
    <DT>The template parameter <I>T</I> must be one for which
    the following functions are overloaded:

    <P><CODE>void ::getBounds(const T&, G3D::AABox&);</CODE>
    <DT><CODE>bool operator==(const T&, const T&);</CODE>
    <DT><CODE>size_t ::hashCode(const T&);</CODE>
    <DT><CODE>T::T();</CODE> <I>(public constructor of no arguments)</I>

    <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 
    AABSPTree::insert it again afterward.  For objects
    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
    values to reinforce this.

    If you want to mutate the objects you intend to store in a AABSPTree 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 AABSPTree
    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 AABSPTree {
    private:
    public:
        /** Wrapper for a value that includes a cache of its bounds. */
        class Handle {
        public:
            T                   value;

            /** The bounds of each object are constrained to AABox::maxFinite */
            AABox               bounds;

            /** Center of bounds.  We cache this value to avoid recomputing it
            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;

            Handle() {}

            inline Handle(const T& v) : value(v) {
                getBounds(v, bounds);
                bounds = bounds.intersect(AABox::maxFinite());
                center = bounds.center();
            }
        };

        /** Returns the bounds of the sub array. Used by makeNode. */
        static AABox computeBounds(
            const Array<Handle>&  point, 
            int                   beginIndex,
            int                   endIndex) {

                Vector3 lo = Vector3::inf();
                Vector3 hi = -lo;

                for (int p = beginIndex; p <= endIndex; ++p) {
                    lo = lo.min(point[p].bounds.low());
                    hi = hi.max(point[p].bounds.high());
                }

                return AABox(lo, hi);
            }


            /**
            A sort predicate that returns true if the midpoint of the
            first argument is less than the midpoint of the second
            along the specified axis.

            Used by makeNode.
            */
            class CenterLT {
            public:
                Vector3::Axis           sortAxis;

                CenterLT(Vector3::Axis a) : sortAxis(a) {}

                inline bool operator()(const Handle& a, const Handle& b) const {
                    return a.center[sortAxis] < b.center[sortAxis];
                }
            };


            /**
            A sort predicate based on a box's location on the specified axis. Each
            box is given a value -1, 0, or 1 based on whether it is strictly less
            than, overlapping, or strictly greater than the value on the specified
            axis. This predicate compares the values for two boxes. The result is
            that the array is separated into three contiguous (though possibly empty)
            groups: less than, overlapping, or greater than.
            */
            class PivotLT {
            public:
                Vector3::Axis sortAxis;
                float sortLocation;

                PivotLT(Vector3::Axis a, float l) : sortAxis(a), sortLocation(l) {}

                inline int location(const AABox& box) const {
                    if(box.low()[sortAxis] < sortLocation) {
                        if(box.high()[sortAxis] < sortLocation) {
                            return -1;
                        } else {
                            return 0;
                        }
                    } else if(box.low()[sortAxis] > sortLocation) {
                        return 1;
                    } else {
                        return 0;
                    }
                }

                inline bool operator()(const Handle&a, const Handle& b) const {
                    const AABox& A = a.bounds;
                    const AABox& B = b.bounds;

                    return location(A) < location(B);
                }
            };

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

                /** Array of values at this node (i.e. values
                straddling the split plane + all 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, int beginIndex, int endIndex) {
                    splitAxis     = Vector3::X_AXIS;
                    splitLocation = 0;
                    for (int i = 0; i < 2; ++i) {
                        child[i] = NULL;
                    }

                    int n = endIndex - beginIndex + 1;

                    valueArray.resize(n);
                    for (int i = n - 1; i >= 0; --i) {
                        valueArray[i] = pt[i + beginIndex];
                    }
                }


                /** 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 AABox& b = valueArray[i].bounds;

                        for(int axis = 0; axis < 3; ++axis) {
                            debugAssert(b.low()[axis] <= b.high()[axis]);