rayintersectioniterator.h

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

/* 
 * Copyright (C) 2005,2006,2007 MaNGOS <http://www.mangosproject.org/>
 * Copyright (C) 2007-2008 Ascent Team <http://www.ascentemu.com/>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
 */

#ifndef _RAYINTERSECTIONITERATOR_H
#define _RAYINTERSECTIONITERATOR_H

#include <G3D/CollisionDetection.h>
#include <G3D/AABox.h>

#include "NodeValueAccess.h"

using namespace G3D;

/**
The Class is mainly taken from G3D/AABSPTree.h but modified to be able to use our internal data structure.
This is an iterator that helps us analysing the BSP-Trees.
The collision detection is modified to return true, if we are inside an object.
*/

namespace VMAP
{

    class MyCollisionDetection
    {
        public:
            static bool collisionLocationForMovingPointFixedAABox(
                const Vector3&          origin,
                const Vector3&          dir,
                const AABox&            box,
                Vector3&                location,
                bool&                   Inside,
                Vector3&                normal)
            {

                // Integer representation of a floating-point value.
            #define IR(x)   ((uint32&)x)

                Inside = true;
                const Vector3& MinB = box.low();
                const Vector3& MaxB = box.high();
                Vector3 MaxT(-1.0f, -1.0f, -1.0f);

                // Find candidate planes.
                for (int i = 0; i < 3; ++i)
                {
                    if (origin[i] < MinB[i])
                    {
                        location[i] = MinB[i];
                        Inside      = false;

                        // Calculate T distances to candidate planes
                        if (IR(dir[i]))
                        {
                            MaxT[i] = (MinB[i] - origin[i]) / dir[i];
                        }
                    }
                    else if (origin[i] > MaxB[i])
                    {
                        location[i] = MaxB[i];
                        Inside      = false;

                        // Calculate T distances to candidate planes
                        if (IR(dir[i]))
                        {
                            MaxT[i] = (MaxB[i] - origin[i]) / dir[i];
                        }
                    }
                }

                if (Inside)
                {
                    // definite hit
                    location = origin;
                    return true;
                }

                // Get largest of the maxT's for final choice of intersection
                int WhichPlane = 0;
                if (MaxT[1] > MaxT[WhichPlane])
                {
                    WhichPlane = 1;
                }

                if (MaxT[2] > MaxT[WhichPlane])
                {
                    WhichPlane = 2;
                }

                // Check final candidate actually inside box
                if (IR(MaxT[WhichPlane]) & 0x80000000)
                {
                    // Miss the box
                    return false;
                }

                for (int i = 0; i < 3; ++i)
                {
                    if (i != WhichPlane)
                    {
                        location[i] = origin[i] + MaxT[WhichPlane] * dir[i];
                        if ((location[i] < MinB[i]) ||
                            (location[i] > MaxB[i]))
                        {
                            // On this plane we're outside the box extents, so
                            // we miss the box
                            return false;
                        }
                    }
                }

                // Choose the normal to be the plane normal facing into the ray
                normal = Vector3::zero();
                normal[WhichPlane] = (dir[WhichPlane] > 0) ? -1.0 : 1.0;

                return true;

            #undef IR
            }
    };

    #ifdef _DEBUG_VMAPS
    extern Vector3 p1,p2,p3,p4,p5,p6,p7;
    extern Array<AABox>gBoxArray;
    extern int gCount1, gCount2, gCount3, gCount4;
    extern bool myfound;
    #endif

    template<class TNode, class TValue>  class RayIntersectionIterator
    {
        private:

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

            struct StackFrame
            {
                const TNode* 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;

                NodeValueAccess<TNode, TValue>* iNodeValueAccess;

                void init(NodeValueAccess<TNode, TValue>* pNodeValueAccess, const TNode* inNode, const Ray& ray, float inMinTime, float inMaxTime)
                {
                    node     = inNode;
                    minTime  = inMinTime;
                    maxTime  = inMaxTime;
                    minTime2 = square(minTime);
                    valIndex = -1;

                    iNodeValueAccess = pNodeValueAccess;
                    intersectionCache.resize(node->getNValues());

                    if (node->getChild(iNodeValueAccess->getNodePtr(),0) == NULL && node->getChild(iNodeValueAccess->getNodePtr(), 1) == NULL)
                    {
                        startTime = minTime;
                        endTime   = maxTime;
                        endTime2  = square(maxTime);
                        nextChild = -1;
                        return;
                    }
                    /*
                    // check if we can hit the box
                    AABox checkBox;
                    Vector3 location;
                    inNode->getBounds(checkBox);
                    double t2;
                    if(checkBox.contains(ray.origin)) {
                    t2=0;
                    } else {
                    if(CollisionDetection::collisionLocationForMovingPointFixedAABox(
                    ray.origin, ray.direction,
                    checkBox,
                    location)) {
                    t2 = (location - ray.origin).squaredLength();
                    } else {
                    t2 = inf();
                    }
                    }
                    double inMaxTime2 = square(inMaxTime);
                    if(t2 > inMaxTime2 || t2 < -inMaxTime2) {
                    // The box is too far of to be hit
                    valIndex = INT_MAX-1;
                    }
                    */

                    Vector3::Axis splitAxis     = node->getSplitAxis();
                    double        splitLocation = node->getSplitLocation();

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

                    if(nextChild != -1) {
                    Vector3 endPoint = ray.origin + ray.direction * pGlobalMaxTime;
                    const TNode* nextNode = inNode->getChild(pNodeValueAccess->getNodePtr() ,nextChild);
                    AABox box;
                    nextNode->getBounds(box);
                    if(box.contains(ray.origin) && box.contains(endPoint)) {
                    valIndex = INT_MAX-1; // directly go into that box
                    }
                    }
                    */
                }
            };

        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;
            Ray                 reverseRay;
            bool                isEnd;

            Array<StackFrame>   stack;
            int                 stackLength;
            int                 stackIndex;
            int                 breakFrameIndex;
            bool                skipAABoxTests;
            NodeValueAccess<TNode, TValue> iNodeValueAccess;
            double              boxMaxDist2;
            double              boxMaxDist;

        public:
            RayIntersectionIterator(const NodeValueAccess<TNode, TValue> pNodeValueAccess, const Ray& r, const TNode* root,  double pMaxTime, bool skip)
                : minDistance(0), maxDistance(inf()), debugCounter(0),
                ray(r), isEnd(root == NULL),
                stackLength(20), stackIndex(0), breakFrameIndex(-1),
                skipAABoxTests(skip)
            {
                iNodeValueAccess = pNodeValueAccess;
                stack.resize(stackLength);
                stack[stackIndex].init(&iNodeValueAccess, root, ray, 0, inf());
                //stack[stackIndex].init(&iNodeValueAccess, root, ray, 0, pMaxTime);
                boxMaxDist2 = pMaxTime*pMaxTime;
                boxMaxDist = pMaxTime;
                ++(*this);
            }

            /* 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)