src/shared/vmap/TreeNode.h

   1 /*
   2 * Copyright (C) 2005-2009 MaNGOS <http://getmangos.com/>
   3 *
   4 * This program is free software; you can redistribute it and/or modify
   5 * it under the terms of the GNU General Public License as published by
   6 * the Free Software Foundation; either version 2 of the License, or
   7 * (at your option) any later version.
   8 *
   9 * This program is distributed in the hope that it will be useful,
  10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 * GNU General Public License for more details.
  13 *
  14 * You should have received a copy of the GNU General Public License
  15 * along with this program; if not, write to the Free Software
  16 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
  17 */
  18
  19 #ifndef _TREENODE_H
  20 #define _TREENODE_H
  21
  22 #include "ShortVector.h"
  23 #include "ShortBox.h"
  24 #include "NodeValueAccess.h"
  25 #include "VMapTools.h"
  26
  27 #include <G3D/Vector3.h>
  28 #include <G3D/AABox.h>
  29
  30 namespace VMAP
  31 {
  32     /**
  33     This Class is mainly taken from G3D/AABSPTree.h and modified to match our data structure.
  34     It is the node within our static BSP-Trees.
  35     It does not use pointers but indexes to access the values and other nodes.
  36     */
  37
  38     //=====================================================
  39
  40     class TreeNode
  41     {
  42     private:
  43         /** Location along the specified axis */
  44         float iSplitLocation;
  45         // Offest or the clients
  46         int iChilds[2];
  47         //Position within the TriangleBox array
  48         unsigned int iStartPosition;
  49         G3D::Vector3::Axis iSplitAxis;
  50         G3D::AABox iBounds;
  51         unsigned short iNumberOfValues;
  52     public:
  53         TreeNode() {}
  54         TreeNode(unsigned short pNValues, unsigned int pStartPosition)
  55         {
  56             iChilds[0] = -1;
  57             iChilds[1] = -1;
  58             iStartPosition = pStartPosition;
  59             iNumberOfValues = pNValues;
  60         }
  61
  62         bool hasChilds() const { return(iChilds[0] >= 0 || iChilds[1] >= 0); }
  63
  64         TreeNode const* getChild(TreeNode const* pValueArray, int pNo) const;
  65         // pChildNo = 0 or 1
  66         inline void setChildPos(int pChildNo, int pChildPosInTreeNodeArray) { iChilds[pChildNo] = pChildPosInTreeNodeArray; }
  67
  68         inline G3D::Vector3::Axis getSplitAxis() const { return(iSplitAxis); }
  69
  70         inline void setSplitAxis(G3D::Vector3::Axis a) { iSplitAxis = a; }
  71         inline void setSplitLocation(float l) { iSplitLocation = l; }
  72
  73         inline void setBounds(const G3D::AABox& pBox) { iBounds = pBox; }
  74
  75         inline void setBounds(const G3D::Vector3& lo, const G3D::Vector3& hi) { iBounds.set(lo,hi); }
  76
  77         inline void getBounds(G3D::AABox& pBox) const { pBox.set(iBounds.low(),iBounds.high()); }
  78
  79         inline float getSplitLocation() const { return(iSplitLocation); }
  80
  81         inline unsigned short getNValues() const { return (iNumberOfValues); }
  82
  83         inline unsigned int getStartPosition() const { return(iStartPosition); }
  84
  85         inline bool operator==(const TreeNode& n) const
  86         {
  87             return ((iSplitLocation == n.iSplitLocation) &&
  88                 (iChilds[0] == n.iChilds[0]) && (iChilds[1] == n.iChilds[1]) &&
  89                 (iStartPosition == n.iStartPosition) &&
  90                 (iSplitAxis == n.iSplitAxis) &&
  91                 (iBounds == n.iBounds) &&
  92                 (iNumberOfValues == n.iNumberOfValues));
  93         }
  94
  95         inline bool operator!=(const TreeNode& n) const
  96         {
  97             return !((iSplitLocation == n.iSplitLocation) &&
  98                 (iChilds[0] == n.iChilds[0]) && (iChilds[1] == n.iChilds[1]) &&
  99                 (iStartPosition == n.iStartPosition) &&
 100                 (iSplitAxis == n.iSplitAxis) &&
 101                 (iBounds == n.iBounds) &&
 102                 (iNumberOfValues == n.iNumberOfValues));
 103         }
 104
 105         /** Returns true if the ray intersects this node */
 106         bool intersects(const G3D::Ray& ray, float distance) const {
 107             // See if the ray will ever hit this node or its children
 108             G3D::Vector3 location;
 109             bool alreadyInsideBounds = false;
 110             bool rayWillHitBounds =
 111                 MyCollisionDetection::collisionLocationForMovingPointFixedAABox(
 112                 ray.origin, ray.direction, iBounds, location, alreadyInsideBounds);
 113
 114             bool canHitThisNode = (alreadyInsideBounds ||
 115                 (rayWillHitBounds && ((location - ray.origin).squaredLength() < (distance*distance))));
 116
 117             return canHitThisNode;
 118         }
 119
 120         template<typename RayCallback, typename TNode, typename TValue>
 121         void intersectRay(
 122             const G3D::Ray& ray,
 123             RayCallback& intersectCallback,
 124             float& distance,
 125             const NodeValueAccess<TNode, TValue>& pNodeValueAccess,
 126             bool pStopAtFirstHit,
 127             bool intersectCallbackIsFast) const {
 128                 float enterDistance = distance;
 129                 if (! intersects(ray, distance)) {
 130                     // The ray doesn't hit this node, so it can't hit the children of the node.
 131                     return;
 132                 }
 133
 134                 // Test for intersection against every object at this node.
 135                 for (unsigned int v = iStartPosition; v < (iNumberOfValues+iStartPosition); ++v) {
 136                     const TValue& nodeValue = pNodeValueAccess.getValue(v);
 137                     bool canHitThisObject = true;
 138                     if (! intersectCallbackIsFast) {
 139                         // See if
 140                         G3D::Vector3 location;
 141                         const G3D::AABox& bounds = nodeValue.getAABoxBounds();
 142                         bool alreadyInsideBounds = false;
 143                         bool rayWillHitBounds =
 144                             MyCollisionDetection::collisionLocationForMovingPointFixedAABox(
 145                             ray.origin, ray.direction, bounds, location, alreadyInsideBounds);
 146
 147                         canHitThisObject = (alreadyInsideBounds ||
 148                             (rayWillHitBounds && ((location - ray.origin).squaredLength() < (distance*distance))));
 149                     }
 150
 151                     if (canHitThisObject) {
 152                         // It is possible that this ray hits this object.  Look for the intersection using the
 153                         // callback.
 154                         intersectCallback(ray, &nodeValue, pStopAtFirstHit, distance);
 155                     }
 156                     if(pStopAtFirstHit && distance < enterDistance)
 157                         return;
 158                 }
 159
 160                 // There are three cases to consider next:
 161                 //
 162                 //  1. the ray can start on one side of the splitting plane and never enter the other,
 163                 //  2. the ray can start on one side and enter the other, and
 164                 //  3. the ray can travel exactly down the splitting plane
 165
 166                 enum {NONE = -1};
 167                 int firstChild = NONE;
 168                 int secondChild = NONE;
 169
 170                 if (ray.origin[iSplitAxis] < iSplitLocation) {
 171
 172                     // The ray starts on the small side
 173                     firstChild = 0;
 174
 175                     if (ray.direction[iSplitAxis] > 0) {
 176                         // The ray will eventually reach the other side
 177                         secondChild = 1;
 178                     }
 179
 180                 } else if (ray.origin[iSplitAxis] > iSplitLocation) {
 181
 182                     // The ray starts on the large side
 183                     firstChild = 1;
 184
 185                     if (ray.direction[iSplitAxis] < 0) {
 186                         secondChild = 0;
 187                     }
 188                 } else {
 189                     // The ray starts on the splitting plane
 190                     if (ray.direction[iSplitAxis] < 0) {
 191                         // ...and goes to the small side
 192                         firstChild = 0;
 193                     } else if (ray.direction[iSplitAxis] > 0) {
 194                         // ...and goes to the large side
 195                         firstChild = 1;
 196                     }
 197                 }
 198
 199                 // Test on the side closer to the ray origin.
 200                 if ((firstChild != NONE) && iChilds[firstChild]>0) {
 201                     getChild(pNodeValueAccess.getNodePtr() , firstChild)->intersectRay(ray, intersectCallback, distance, pNodeValueAccess, pStopAtFirstHit,intersectCallbackIsFast);
 202                     if(pStopAtFirstHit && distance < enterDistance)
 203                         return;
 204                 }
 205                 if (ray.direction[iSplitAxis] != 0) {
 206                     // See if there was an intersection before hitting the splitting plane.
 207                     // If so, there is no need to look on the far side and recursion terminates.
 208                     float distanceToSplittingPlane = (iSplitLocation - ray.origin[iSplitAxis]) / ray.direction[iSplitAxis];
 209                     if (distanceToSplittingPlane > distance) {
 210                         // We aren't going to hit anything else before hitting the splitting plane,
 211                         // so don't bother looking on the far side of the splitting plane at the other
 212                         // child.
 213                         return;
 214                     }
 215                 }
 216                 // Test on the side farther from the ray origin.
 217                 if ((secondChild != NONE) && iChilds[secondChild]>0) {
 218                     getChild(pNodeValueAccess.getNodePtr() , secondChild)->intersectRay(ray, intersectCallback, distance, pNodeValueAccess, pStopAtFirstHit,intersectCallbackIsFast);
 219                 }
 220         }
 221     };
 222 }
 223 #endif