OregonCore  revision fb2a440-git
Your Favourite TBC server
DynamicTree.cpp
Go to the documentation of this file.
1 /*
2  * This file is part of the OregonCore Project. See AUTHORS file for Copyright information
3  *
4  * This program is free software; you can redistribute it and/or modify it
5  * under the terms of the GNU General Public License as published by the
6  * Free Software Foundation; either version 2 of the License, or (at your
7  * option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful, but WITHOUT
10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11  * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for
12  * more details.
13  *
14  * You should have received a copy of the GNU General Public License along
15  * with this program. If not, see <http://www.gnu.org/licenses/>.
16  */
17 
18 #include "DynamicTree.h"
19 #include "Log.h"
20 #include "Timer.h"
22 #include "RegularGrid.h"
23 #include "GameObjectModel.h"
24 
25 using G3D::Ray;
26 
27 template<> struct HashTrait< GameObjectModel>
28 {
29  static size_t hashCode(const GameObjectModel& g) { return (size_t)(void*)&g; }
30 };
31 
32 template<> struct PositionTrait< GameObjectModel>
33 {
34  static void getPosition(const GameObjectModel& g, Vector3& p) { p = g.getPosition(); }
35 };
36 
37 template<> struct BoundsTrait< GameObjectModel>
38 {
39  static void getBounds(const GameObjectModel& g, G3D::AABox& out) { out = g.getBounds();}
40  static void getBounds2(const GameObjectModel* g, G3D::AABox& out) { out = g->getBounds();}
41 };
42 
43 /*
44 static bool operator == (const GameObjectModel& mdl, const GameObjectModel& mdl2){
45  return &mdl == &mdl2;
46 }
47 */
48 
49 // int valuesPerNode = 5, numMeanSplits = 3;
50 
51 // int UNBALANCED_TIMES_LIMIT = 5;
53 
55 
56 struct DynTreeImpl : public ParentTree/*, public Intersectable*/
57 {
59  typedef ParentTree base;
60 
62  rebalance_timer(CHECK_TREE_PERIOD),
63  unbalanced_times(0)
64  {
65  }
66 
67  void insert(const Model& mdl)
68  {
69  base::insert(mdl);
70  ++unbalanced_times;
71  }
72 
73  void remove(const Model& mdl)
74  {
75  base::remove(mdl);
76  ++unbalanced_times;
77  }
78 
79  void balance()
80  {
81  base::balance();
82  unbalanced_times = 0;
83  }
84 
85  void update(uint32 difftime)
86  {
87  if (!size())
88  return;
89 
90  rebalance_timer.Update(difftime);
91  if (rebalance_timer.Passed())
92  {
93  rebalance_timer.Reset(CHECK_TREE_PERIOD);
94  if (unbalanced_times > 0)
95  balance();
96  }
97  }
98 
101 };
102 
104 {
105 }
106 
108 {
109  delete &impl;
110 }
111 
113 {
114  impl.insert(mdl);
115 }
116 
118 {
119  impl.remove(mdl);
120 }
121 
123 {
124  return impl.contains(mdl);
125 }
126 
128 {
129  impl.balance();
130 }
131 
133 {
134  return impl.size();
135 }
136 
138 {
139  impl.update(t_diff);
140 }
141 
143 {
144  bool did_hit;
146  bool operator()(const Ray& r, const GameObjectModel& obj, float& distance)
147  {
148  did_hit = obj.intersectRay(r, distance, true);
149  return did_hit;
150  }
151  bool didHit() const { return did_hit;}
152 };
153 
155 {
156  bool did_hit;
158  {
159  DEBUG_LOG("Dynamic Intersection log");
160  }
161  bool operator()(const Ray& r, const GameObjectModel& obj, float& distance)
162  {
163  DEBUG_LOG("testing intersection with %s", obj.name.c_str());
164  bool hit = obj.intersectRay(r, distance, true);
165  if (hit)
166  {
167  did_hit = true;
168  DEBUG_LOG("result: intersects");
169  }
170  return hit;
171  }
172  bool didHit() const { return did_hit;}
173 };
174 
179 bool DynamicMapTree::getIntersectionTime(const G3D::Ray& ray, const Vector3& endPos, float& maxDist) const
180 {
181  float distance = maxDist;
183  impl.intersectRay(ray, callback, distance, endPos);
184  if (callback.didHit())
185  maxDist = distance;
186  return callback.didHit();
187 }
188 
193 bool DynamicMapTree::getObjectHitPos(const Vector3& startPos, const Vector3& endPos, Vector3& resultHit, float modifyDist) const
194 {
195  bool result = false;
196  float maxDist = (endPos - startPos).magnitude();
197  // valid map coords should *never ever* produce float overflow, but this would produce NaNs too
198  ASSERT(maxDist < std::numeric_limits<float>::max());
199  // prevent NaN values which can cause BIH intersection to enter infinite loop
200  if (maxDist < 1e-10f)
201  {
202  resultHit = endPos;
203  return false;
204  }
205  Vector3 dir = (endPos - startPos) / maxDist; // direction with length of 1
206  G3D::Ray ray(startPos, dir);
207  float dist = maxDist;
208  if (getIntersectionTime(ray, endPos, dist))
209  {
210  resultHit = startPos + dir * dist;
211  if (modifyDist < 0)
212  {
213  if ((resultHit - startPos).magnitude() > -modifyDist)
214  resultHit = resultHit + dir * modifyDist;
215  else
216  resultHit = startPos;
217  }
218  else
219  resultHit = resultHit + dir * modifyDist;
220 
221  result = true;
222  }
223  else
224  {
225  resultHit = endPos;
226  result = false;
227  }
228  return result;
229 }
230 
231 bool DynamicMapTree::isInLineOfSight(float x1, float y1, float z1, float x2, float y2, float z2) const
232 {
233  Vector3 v1(x1,y1,z1), v2(x2,y2,z2);
234 
235  float maxDist = (v2 - v1).magnitude();
236 
237  if (!G3D::fuzzyGt(maxDist, 0) )
238  return true;
239 
240  Ray r(v1, (v2-v1) / maxDist);
242  impl.intersectRay(r, callback, maxDist, v2);
243 
244  return !callback.did_hit;
245 }
246 
247 float DynamicMapTree::getHeight(float x, float y, float z, float maxSearchDist) const
248 {
249  Vector3 v(x,y,z);
250  Ray r(v, Vector3(0,0,-1));
252  impl.intersectZAllignedRay(r, callback, maxSearchDist);
253 
254  if (callback.didHit())
255  return v.z - maxSearchDist;
256  else
257  return -G3D::inf();
258 }
static void getPosition(const GameObjectModel &g, Vector3 &p)
Definition: DynamicTree.cpp:34
ParentTree base
Definition: DynamicTree.cpp:59
void balance()
Definition: DynamicTree.cpp:79
RegularGrid2D< GameObjectModel, BIHWrap< GameObjectModel > > ParentTree
Definition: DynamicTree.cpp:54
static size_t hashCode(const GameObjectModel &g)
Definition: DynamicTree.cpp:29
bool operator()(const Ray &r, const GameObjectModel &obj, float &distance)
void intersectZAllignedRay(const Ray &ray, RayCallback &intersectCallback, float &max_dist)
Definition: RegularGrid.h:205
void update(uint32 difftime)
Definition: DynamicTree.cpp:85
void remove(const Model &mdl)
Definition: DynamicTree.cpp:73
NULL Dbg ErrDB Arena Chat Char Map MMap false
Definition: Log.cpp:556
void update(uint32 diff)
struct DynTreeImpl & impl
Definition: DynamicTree.h:52
const G3D::Vector3 & getPosition() const
void remove(const GameObjectModel &)
void intersectRay(const Ray &ray, RayCallback &intersectCallback, float max_dist)
Definition: RegularGrid.h:112
int CHECK_TREE_PERIOD
Definition: DynamicTree.cpp:52
GameObjectModel Model
Definition: DynamicTree.cpp:58
const G3D::AABox & getBounds() const
#define DEBUG_LOG(...)
Definition: Log.h:194
void insert(const Model &mdl)
Definition: DynamicTree.cpp:67
static void getBounds(const GameObjectModel &g, G3D::AABox &out)
Definition: DynamicTree.cpp:39
bool contains(const GameObjectModel &) const
static void getBounds2(const GameObjectModel *g, G3D::AABox &out)
Definition: DynamicTree.cpp:40
void insert(const GameObjectModel &)
TimeTrackerSmall rebalance_timer
Definition: DynamicTree.cpp:99
bool contains(const T &value) const
Definition: RegularGrid.h:79
int size() const
Definition: RegularGrid.h:80
#define ASSERT
Definition: Errors.h:29
bool getObjectHitPos(const G3D::Vector3 &pPos1, const G3D::Vector3 &pPos2, G3D::Vector3 &pResultHitPos, float pModifyDist) const
bool isInLineOfSight(float x1, float y1, float z1, float x2, float y2, float z2) const
bool intersectRay(const G3D::Ray &Ray, float &MaxDist, bool StopAtFirstHit) const
float getHeight(float x, float y, float z, float maxSearchDist) const
ACE_UINT32 uint32
Definition: Define.h:71
bool operator()(const Ray &r, const GameObjectModel &obj, float &distance)
bool getIntersectionTime(const G3D::Ray &ray, const G3D::Vector3 &endPos, float &maxDist) const
int unbalanced_times
std::string name
int size() const