[svn] * Proper SVN structureinit

--HG--
branch : trunk

1 files changed, 223 insertions, 0 deletions

diff --git a/src/shared/vmap/TreeNode.h b/src/shared/vmap/TreeNode.h
new file mode 100644
index 00000000000..c034b3c88f3
--- /dev/null
+++ b/src/shared/vmap/TreeNode.h
@@ -0,0 +1,223 @@
+/* 
+* Copyright (C) 2005-2008 MaNGOS <http://www.mangosproject.org/>
+*
+* 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 _TREENODE_H
+#define _TREENODE_H
+
+#include "ShortVector.h"
+#include "ShortBox.h"
+#include "NodeValueAccess.h"
+#include "VMapTools.h"
+
+#include <G3D/Vector3.h>
+#include <G3D/AABox.h>
+
+namespace VMAP
+{
+    /**
+    This Class is mainly taken from G3D/AABSPTree.h and modified to match our data structure.
+    It is the node within our static BSP-Trees.
+    It does not use pointers but indexes to access the values and other nodes.
+    */
+
+    //=====================================================
+
+    class TreeNode
+    {
+    private:
+        /** Location along the specified axis */
+        float iSplitLocation;
+        // Offest or the clients
+        int iChilds[2];
+        //Position within the TriangleBox array
+        unsigned int iStartPosition;
+        G3D::Vector3::Axis iSplitAxis;
+        G3D::AABox iBounds;
+        unsigned short iNumberOfValues;
+    public:
+        TreeNode() {}
+        TreeNode(unsigned short pNValues, unsigned int pStartPosition)
+        {
+            iChilds[0] = -1;
+            iChilds[1] = -1;
+            iStartPosition = pStartPosition;
+            iNumberOfValues = pNValues;
+        }
+
+        bool hasChilds() const { return(iChilds[0] >= 0 || iChilds[1] >= 0); }
+
+        TreeNode const* getChild(TreeNode const* pValueArray, int pNo) const;
+        // pChildNo = 0 or 1
+        inline void setChildPos(int pChildNo, int pChildPosInTreeNodeArray) { iChilds[pChildNo] = pChildPosInTreeNodeArray; }
+
+        inline G3D::Vector3::Axis getSplitAxis() const { return(iSplitAxis); }
+
+        inline void setSplitAxis(G3D::Vector3::Axis a) { iSplitAxis = a; }
+        inline void setSplitLocation(float l) { iSplitLocation = l; }
+
+        inline void setBounds(const G3D::AABox& pBox) { iBounds = pBox; }
+
+        inline void setBounds(const G3D::Vector3& lo, const G3D::Vector3& hi) { iBounds.set(lo,hi); }
+
+        inline void getBounds(G3D::AABox& pBox) const { pBox.set(iBounds.low(),iBounds.high()); }
+
+        inline float getSplitLocation() const { return(iSplitLocation); }
+
+        inline unsigned short getNValues() const { return (iNumberOfValues); }
+
+        inline unsigned int getStartPosition() const { return(iStartPosition); }
+
+        inline bool operator==(const TreeNode& n) const
+        {
+            return ((iSplitLocation == n.iSplitLocation) &&
+                (iChilds[0] == n.iChilds[0]) && (iChilds[1] == n.iChilds[1]) &&
+                (iStartPosition == n.iStartPosition) &&
+                (iSplitAxis == n.iSplitAxis) &&
+                (iBounds == n.iBounds) &&
+                (iNumberOfValues == n.iNumberOfValues));
+        }
+
+        inline bool operator!=(const TreeNode& n) const
+        {
+            return !((iSplitLocation == n.iSplitLocation) &&
+                (iChilds[0] == n.iChilds[0]) && (iChilds[1] == n.iChilds[1]) &&
+                (iStartPosition == n.iStartPosition) &&
+                (iSplitAxis == n.iSplitAxis) &&
+                (iBounds == n.iBounds) &&
+                (iNumberOfValues == n.iNumberOfValues));
+        }
+
+        /** Returns true if the ray intersects this node */
+        bool intersects(const G3D::Ray& ray, float distance) const {
+            // See if the ray will ever hit this node or its children
+            G3D::Vector3 location;
+            bool alreadyInsideBounds = false;
+            bool rayWillHitBounds = 
+                MyCollisionDetection::collisionLocationForMovingPointFixedAABox(
+                ray.origin, ray.direction, iBounds, location, alreadyInsideBounds);
+
+            bool canHitThisNode = (alreadyInsideBounds ||                
+                (rayWillHitBounds && ((location - ray.origin).squaredLength() < (distance*distance))));
+
+            return canHitThisNode;
+        }
+
+        template<typename RayCallback, typename TNode, typename TValue>
+        void intersectRay(
+            const G3D::Ray& ray, 
+            RayCallback& intersectCallback, 
+            float& distance,
+            const NodeValueAccess<TNode, TValue>& pNodeValueAccess,
+            bool pStopAtFirstHit,
+            bool intersectCallbackIsFast) const {
+                float enterDistance = distance;
+                if (! intersects(ray, distance)) {
+                    // The ray doesn't hit this node, so it can't hit the children of the node.
+                    return;
+                }
+
+                // Test for intersection against every object at this node.
+                for (unsigned int v = iStartPosition; v < (iNumberOfValues+iStartPosition); ++v) {        
+                    const TValue& nodeValue = pNodeValueAccess.getValue(v);
+                    bool canHitThisObject = true;
+                    if (! intersectCallbackIsFast) {
+                        // See if
+                        G3D::Vector3 location;
+                        const G3D::AABox& bounds = nodeValue.getAABoxBounds();
+                        bool alreadyInsideBounds = false;
+                        bool rayWillHitBounds = 
+                            MyCollisionDetection::collisionLocationForMovingPointFixedAABox(
+                            ray.origin, ray.direction, bounds, location, alreadyInsideBounds);
+
+                        canHitThisObject = (alreadyInsideBounds ||                
+                            (rayWillHitBounds && ((location - ray.origin).squaredLength() < (distance*distance))));
+                    }
+
+                    if (canHitThisObject) {
+                        // It is possible that this ray hits this object.  Look for the intersection using the
+                        // callback.
+                        intersectCallback(ray, &nodeValue, pStopAtFirstHit, distance);
+                    }
+                    if(pStopAtFirstHit && distance < enterDistance)
+                        return;
+                }
+
+                // There are three cases to consider next:
+                // 
+                //  1. the ray can start on one side of the splitting plane and never enter the other,
+                //  2. the ray can start on one side and enter the other, and
+                //  3. the ray can travel exactly down the splitting plane
+
+                enum {NONE = -1};
+                int firstChild = NONE;
+                int secondChild = NONE;
+
+                if (ray.origin[iSplitAxis] < iSplitLocation) {
+
+                    // The ray starts on the small side
+                    firstChild = 0;
+
+                    if (ray.direction[iSplitAxis] > 0) {
+                        // The ray will eventually reach the other side
+                        secondChild = 1;
+                    }
+
+                } else if (ray.origin[iSplitAxis] > iSplitLocation) {
+
+                    // The ray starts on the large side
+                    firstChild = 1;
+
+                    if (ray.direction[iSplitAxis] < 0) {
+                        secondChild = 0;
+                    }
+                } else {
+                    // The ray starts on the splitting plane
+                    if (ray.direction[iSplitAxis] < 0) {
+                        // ...and goes to the small side
+                        firstChild = 0;
+                    } else if (ray.direction[iSplitAxis] > 0) {
+                        // ...and goes to the large side
+                        firstChild = 1;
+                    }
+                }
+
+                // Test on the side closer to the ray origin.
+                if ((firstChild != NONE) && iChilds[firstChild]>0) {
+                    getChild(pNodeValueAccess.getNodePtr() , firstChild)->intersectRay(ray, intersectCallback, distance, pNodeValueAccess, pStopAtFirstHit,intersectCallbackIsFast);
+                    if(pStopAtFirstHit && distance < enterDistance)
+                        return;
+                }
+                if (ray.direction[iSplitAxis] != 0) {
+                    // See if there was an intersection before hitting the splitting plane.  
+                    // If so, there is no need to look on the far side and recursion terminates.
+                    float distanceToSplittingPlane = (iSplitLocation - ray.origin[iSplitAxis]) / ray.direction[iSplitAxis];
+                    if (distanceToSplittingPlane > distance) {
+                        // We aren't going to hit anything else before hitting the splitting plane,
+                        // so don't bother looking on the far side of the splitting plane at the other
+                        // child.
+                        return;
+                    }
+                }
+                // Test on the side farther from the ray origin.
+                if ((secondChild != NONE) && iChilds[secondChild]>0) {
+                    getChild(pNodeValueAccess.getNodePtr() , secondChild)->intersectRay(ray, intersectCallback, distance, pNodeValueAccess, pStopAtFirstHit,intersectCallbackIsFast);
+                }
+        }
+    };
+}
+#endif