source: Revenant/marslib/include/mars_lookup.h@ 25c4774

port/mars-tycoon
Last change on this file since 25c4774 was 80a6a52, checked in by Jonathan Neufeld <support@…>, 3 years ago

Get to a compile state for terrain procedural generation
  • Property mode set to 100755
File size: 34.1 KB
Line 
1#ifndef __MARSLOOKUP_H__
2#define __MARSLOOKUP_H__
3
4#include <list>
5#include <iterator>
6#include <stack>
7#include <set>
8
9#include "coroutines.h"
10#include "mars_linalg.h"
11#include "mars_calc.h"
12#include "mars_ptr.h"
13
14/**
15 * Purpose for this library:
16 * This library is used (instead of for example Boost uBLAS) because it is optimized for 3D and 2D operations (since operations in any
17 * other Euclidian dimensions are unnecessary for this video game application). 3D and 2D classes and operations are static and computed
18 * at compile-time rather than runtime as in the case of every other linear algebra library (i.e. this library doesn't use for-loops EVER).
19 * An obvious disadvantage of this is that there is a lot of redundant code that would normally lead to a much larger code maintenance
20 * burden, but basic linear algebra does not evolve, so this disadvantage is permissible.
21 *
22 * TODO: Implement expression classes to optimize machine-code generation for vector expressions and reduce/eliminate temporaries
23 */
24
25namespace mars
26{
27 template <typename Tag> class RectRegion;
28 template <typename Tag> class RadialRegion;
29 template <typename Tag> class PointRegion;
30 template <typename E, typename R, typename Tag> class TreeDegree;
31 template <typename E, typename R> class Entity;
32 template <typename Tag> class DegreeBounds;
33 template< typename E, typename R, typename Tag > struct TreeIteratorTraits;
34 template <typename E, typename R, typename QR, typename Tag, typename TIT = TreeIteratorTraits< E, R, Tag > > class DegreeNicheIterator;
35
36 template <typename E, typename R>
37 class Entity
38 {
39 public:
40 ptr< E > pData;
41 const R region;
42
43 inline Entity (const ptr< E > & pData, const R & r)
44 : pData(pData), region(r) {}
45 };
46
47 template <typename T>
48 inline T lkmax (T a, T b, T c, T d)
49 {
50 if (a < b)
51 if (b < c)
52 if (c < d)
53 return d;
54 else
55 return c;
56 else
57 if (b < d)
58 return d;
59 else
60 return b;
61 else
62 if (a < c)
63 if (c < d)
64 return d;
65 else
66 return c;
67 else
68 if (a < d)
69 return d;
70 else
71 return a;
72 }
73
74 template <typename T>
75 inline T lkmin (T a, T b, T c, T d)
76 {
77 if (a > b)
78 if (b > c)
79 if (c > d)
80 return d;
81 else
82 return c;
83 else
84 if (b > d)
85 return d;
86 else
87 return b;
88 else
89 if (a > c)
90 if (c > d)
91 return d;
92 else
93 return c;
94 else
95 if (a > d)
96 return d;
97 else
98 return a;
99 }
100
101 template <typename T, typename V>
102 class DegreeRect
103 {
104 public:
105 V p;
106 T m;
107 };
108
109 template <typename T>
110 struct TreeTag3D
111 {
112 static const unsigned int DEGREES = 8;
113 typedef vector3D <T> VECTOR;
114 typedef T SCALAR;
115 };
116
117 template <typename T>
118 struct TreeTag2D
119 {
120 static const unsigned int DEGREES = 4;
121 typedef vector2D <T> VECTOR;
122 typedef T SCALAR;
123 };
124
125 /* General contract of regions:
126 * - x & y: Tests that y is contained completely within x, that is the intersection of x with y is equivalent to y
127 * - x ^ y: Tests that x and y at least overlap, that is the intersection of x with y is non-empty
128 */
129
130 class AmbientRegion {};
131
132 template <typename Tag>
133 class RadialRegion
134 {
135 public:
136 typedef typename Tag::VECTOR VECTOR;
137 typedef typename Tag::SCALAR SCALAR;
138
139 VECTOR p;
140 SCALAR r;
141
142 inline RadialRegion () {}
143
144 inline RadialRegion (const VECTOR & p, const SCALAR & r)
145 : p(p), r(r) {}
146
147 inline bool operator ^ (const VECTOR & v) const
148 {
149 return MAG(v - p) <= r;
150 }
151
152 inline bool operator ^ (const RadialRegion< Tag > & rval) const
153 {
154 return MAG(p - rval.p) + rval.r <= r;
155 }
156
157 inline bool operator ^ (const PointRegion< TreeTag3D< SCALAR > > & rval) const
158 {
159 return MAGSQ(p - rval.v) < SQ(r);
160 }
161
162 inline bool operator ^ (const PointRegion< TreeTag2D< SCALAR > > & rval) const
163 {
164 return MAGSQ(static_cast< typename TreeTag2D< SCALAR >::VECTOR > (p) - rval.v) < SQ(r);
165 }
166
167 inline bool operator ^ (const AmbientRegion &) const
168 {
169 return true;
170 }
171
172#define CODE_RadialRegion_Amp_RectRegion \
173 { \
174 const VECTOR d2 = (rval.v2 - rval.v1) / 2; \
175 const VECTOR dist = (p - (rval.v1 + d2)); \
176\
177 if (radialContainment(d2, dist)) \
178 return true; \
179\
180 return MAGSQ(dist - d2) <= SQ(r); \
181 }
182
183 bool operator & (const RectRegion< TreeTag2D< SCALAR > > & rval) const CODE_RadialRegion_Amp_RectRegion ;
184 bool operator & (const RectRegion< TreeTag3D< SCALAR > > & rval) const CODE_RadialRegion_Amp_RectRegion ;
185
186 inline bool operator & (const RadialRegion< Tag > & rval) const
187 {
188 return rval.r < r && MAGSQ(p - rval.p) < SQ(r - rval.r); // TODO: Verify, I think I fixed a bug, used to be "MAGSQ(p - rval.p) < SQ(r + rval.r)"
189 }
190 inline bool operator & (const PointRegion< TreeTag3D< SCALAR > > & rval) const
191 {
192 return r <= static_cast< SCALAR > (1) &&
193 p.x == rval.p.x &&
194 p.y == rval.p.y &&
195 p.z == rval.p.z;
196 }
197 inline bool operator & (const PointRegion< TreeTag2D< SCALAR > > & rval) const
198 {
199 return r <= static_cast< SCALAR > (1) &&
200 p.x == rval.p.x &&
201 p.y == rval.p.y;
202 }
203 inline bool operator & (const AmbientRegion &) const
204 {
205 return true;
206 }
207
208 inline bool operator == (const RadialRegion< Tag > & b) const
209 {
210 return p == b.p && r == b.r;
211 }
212
213 inline bool isNiche (const DegreeBounds <Tag> & b) const
214 {
215 // Comparing with diameter, not radius
216 return r * 2 > static_cast <SCALAR> (b.m2) && r * 2 < static_cast <SCALAR> (b.m2) * 2;
217 }
218
219 protected:
220 inline bool radialContainment (const vector3D< SCALAR > & d2, const vector3D< SCALAR > & dist) const
221 {
222 return (dist.x <= (d2.x + r) && dist.y <= (d2.y + r) && dist.z <= (d2.z + r) &&
223 (dist.x <= d2.x || dist.y <= d2.y || dist.z <= d2.z));
224 }
225
226 inline bool radialContainment (const vector2D< SCALAR > & d2, const vector2D< SCALAR > & dist) const
227 {
228 return dist.x <= (d2.x + r) && dist.y <= (d2.y + r) &&
229 (dist.x <= d2.x || dist.y <= d2.y);
230 }
231 };
232
233 template <typename T>
234 class CylindricalRegion : public RadialRegion< TreeTag2D< T > >
235 {
236 private:
237 typedef RadialRegion< TreeTag2D< T > > Base;
238
239 public:
240 using typename Base::VECTOR;
241 using typename Base::SCALAR;
242 using Vec3D = typename TreeTag3D< T >::VECTOR;
243
244 SCALAR z;
245
246 inline CylindricalRegion () {}
247
248 inline CylindricalRegion (const RadialRegion< TreeTag3D< T > > & rr)
249 : Base(static_cast < typename TreeTag2D< T >::VECTOR > (rr.p), rr.r), z(rr.p.z) {}
250 inline CylindricalRegion (const Vec3D & p, const T & r)
251 : Base(static_cast < typename TreeTag2D< T >::VECTOR > (p), r), z(p.z) {}
252
253 inline bool operator ^ (const VECTOR & v) const
254 {
255 return MAG(v - p3()) <= this->r;
256 }
257
258 inline bool operator ^ (const RadialRegion< TreeTag3D< T > > & rval) const
259 {
260 return MAG(p3() - rval.p) + rval.r <= this->r;
261 }
262
263 inline bool operator ^ (const PointRegion< TreeTag3D< SCALAR > > & rval) const
264 {
265 return MAGSQ(p3() - rval.v) < SQ(this->r);
266 }
267
268 inline bool operator ^ (const AmbientRegion &) const
269 {
270 return true;
271 }
272
273 inline bool operator & (const PointRegion< TreeTag3D< SCALAR > > & rval) const
274 {
275 return this->r <= static_cast< SCALAR > (1) &&
276 this->p.x == rval.p.x &&
277 this->p.y == rval.p.y &&
278 z == rval.p.z;
279 }
280
281 bool operator & (const RectRegion< TreeTag3D< SCALAR > > & rval) const
282 {
283 const VECTOR d2 = (rval.v2 - rval.v1) / 2;
284 const VECTOR dist = (p3() - (rval.v1 + d2));
285
286 if (radialContainment(d2, dist))
287 return true;
288
289 return MAGSQ(dist - d2) <= SQ(this->r);
290 }
291 inline bool operator & (const RectRegion< TreeTag2D< SCALAR > > & rval) const
292 { return RadialRegion< TreeTag2D< T > > ::operator & (rval); }
293
294 inline bool operator & (const RadialRegion< TreeTag3D< T > > & rval) const
295 {
296 return MAGSQ(p3() - rval.p) < SQ(this->r + rval.r);
297 }
298
299 inline bool operator & (const AmbientRegion &) const
300 {
301 return true;
302 }
303
304 inline Vec3D p3() const { return Vec3D(this->p.x, this->p.y, z); }
305 inline operator RadialRegion< TreeTag3D< T > > () const
306 { return RadialRegion< TreeTag3D< T > > (p3(), this->r); }
307 };
308
309 template <typename Tag>
310 class RectRegion
311 {
312 public:
313 typedef typename Tag::VECTOR VECTOR;
314 typedef typename Tag::SCALAR SCALAR;
315
316 VECTOR v1, v2;
317
318 inline RectRegion (const VECTOR & v1, const VECTOR & v2)
319 : v1(v1), v2(v2)
320 { assertDimensions(v1, v2); }
321
322 inline bool operator ^ (const vector3D <SCALAR> & v) const
323 {
324 return
325 v.x >= this->v1.x && v.x <= this->v2.x &&
326 v.y >= this->v1.y && v.y <= this->v2.y &&
327 v.z >= this->v1.z && v.z <= this->v2.z;
328 }
329 inline bool operator ^ (const vector2D <SCALAR> & v) const
330 {
331 return
332 v.x >= this->v1.x && v.x <= this->v2.x &&
333 v.y >= this->v1.y && v.y <= this->v2.y;
334 }
335 inline bool operator ^ (const PointRegion < TreeTag3D< SCALAR > > & rval) const
336 {
337 return
338 v1.x <= rval.p.x && v2.x >= rval.p.x &&
339 v1.y <= rval.p.y && v2.y >= rval.p.y &&
340 v1.z <= rval.p.z && v2.z >= rval.p.z;
341 }
342 inline bool operator ^ (const PointRegion < TreeTag2D< SCALAR > > & rval) const
343 {
344 return
345 v1.x <= rval.p.x && v2.x >= rval.p.x &&
346 v1.y <= rval.p.y && v2.y >= rval.p.y;
347 }
348 inline bool operator ^ (const AmbientRegion &) const
349 {
350 return true;
351 }
352
353 inline bool operator ^ (const RectRegion< TreeTag3D< SCALAR > > & rval) const
354 {
355 return
356 this->v1.x <= rval.v1.x &&
357 this->v1.y <= rval.v1.y &&
358 this->v1.z <= rval.v1.z &&
359
360 this->v2.x >= rval.v2.x &&
361 this->v2.y >= rval.v2.y &&
362 this->v2.z >= rval.v2.z;
363 }
364 inline bool operator ^ (const RectRegion< TreeTag2D< SCALAR > > & rval) const
365 {
366 return
367 this->v1.x <= rval.v1.x &&
368 this->v1.y <= rval.v1.y &&
369
370 this->v2.x >= rval.v2.x &&
371 this->v2.y >= rval.v2.y;
372 }
373
374 inline bool operator & (const RectRegion< TreeTag3D< SCALAR > > & rval) const
375 {
376 return
377 this->v2.x >= rval.v1.x &&
378 this->v2.y >= rval.v1.y &&
379 this->v2.z >= rval.v1.z &&
380
381 this->v1.x <= rval.v2.x &&
382 this->v1.y <= rval.v2.y &&
383 this->v1.z <= rval.v2.z;
384 }
385 inline bool operator & (const RectRegion< TreeTag2D< SCALAR > > & rval) const
386 {
387 return
388 this->v2.x >= rval.v1.x &&
389 this->v2.y >= rval.v1.y &&
390
391 this->v1.x <= rval.v2.x &&
392 this->v1.y <= rval.v2.y;
393 }
394 inline bool operator & (const PointRegion< TreeTag3D< SCALAR > > & rval) const
395 {
396 return v1 == rval.v2 &&
397 v1.x == rval.p.x &&
398 v1.y == rval.p.y &&
399 v1.z == rval.p.z;
400 }
401 inline bool operator & (const PointRegion< TreeTag2D< SCALAR > > & rval) const
402 {
403 return v1 == rval.v2 &&
404 v1.x == rval.p.x &&
405 v1.y == rval.p.y;
406 }
407
408 inline bool operator & (const RadialRegion <Tag> & rval) const
409 {
410 return rval & *this;
411 }
412
413 inline bool operator & (const AmbientRegion &) const
414 {
415 return true;
416 }
417
418 inline bool isNiche (const DegreeBounds <Tag> & b) const
419 {
420 const SCALAR
421 mrsq = MAGSQ(v2 - v1),
422 m2sq = SQ(b.m2);
423
424 return mrsq > m2sq && mrsq < m2sq * 2;
425 }
426
427 private:
428 static inline void assertDimensions (const vector3D <SCALAR> & v1, const vector3D <SCALAR> & v2)
429 { assert(v1.x <= v2.x && v1.y <= v2.y && v1.z <= v2.z); }
430 static inline void assertDimensions (const vector2D <SCALAR> & v1, const vector2D <SCALAR> & v2)
431 { assert(v1.x <= v2.x && v1.y <= v2.y); }
432 };
433
434 template <typename Tag>
435 class PointRegion
436 {
437 public:
438 typedef typename Tag::VECTOR VECTOR;
439 typedef typename Tag::SCALAR SCALAR;
440
441 VECTOR p;
442
443 inline PointRegion (const VECTOR & v)
444 : p(v)
445 {}
446
447 inline bool operator ^ (const vector3D <SCALAR> & v) const
448 {
449 return
450 v.x == this->p.x &&
451 v.y == this->p.y &&
452 v.z == this->p.z;
453 }
454 inline bool operator ^ (const vector2D <SCALAR> & v) const
455 {
456 return
457 v.x == this->p.x &&
458 v.y == this->p.y;
459 }
460
461 inline bool operator ^ (const RectRegion< TreeTag3D< SCALAR > > & rval) const
462 {
463 return rval.v1 == rval.v2 &&
464 rval.v1.x == p.x &&
465 rval.v1.y == p.y &&
466 rval.v1.z == p.z;
467 }
468 inline bool operator ^ (const RectRegion< TreeTag2D< SCALAR > > & rval) const
469 {
470 return rval.v1 == rval.v2 &&
471 rval.v1.x == p.x &&
472 rval.v1.y == p.y;
473 }
474
475 inline bool operator & (const RectRegion< TreeTag3D< SCALAR > > & rval) const
476 {
477 return
478 this->p.x >= rval.v1.x &&
479 this->p.y >= rval.v1.y &&
480 this->p.z >= rval.v1.z &&
481
482 this->p.x <= rval.v2.x &&
483 this->p.y <= rval.v2.y &&
484 this->p.z <= rval.v2.z;
485 }
486 inline bool operator & (const RectRegion< TreeTag2D< SCALAR > > & rval) const
487 {
488 return
489 this->p.x >= rval.v1.x &&
490 this->p.y >= rval.v1.y &&
491
492 this->p.x <= rval.v2.x &&
493 this->p.y <= rval.v2.y;
494 }
495 inline bool operator & (const RadialRegion <Tag> & rval) const
496 {
497 return MAGSQ(rval.p - p) < SQ(rval.r);
498 }
499 inline bool isNiche (const DegreeBounds <Tag> & b) const
500 { return false; }
501 };
502
503 template <typename Tag>
504 class DegreeBounds
505 {
506 public:
507 typedef typename Tag::VECTOR VECTOR;
508 typedef typename Tag::SCALAR SCALAR;
509 typedef unsigned int W;
510
511 private:
512 static inline unsigned int ao2qbs2D (const unsigned int ao)
513 {
514 const unsigned int iao = ~ao;
515
516 return
517 (iao & ((1 << 0) | (1 << 2)) ? 0 : 1 << 0) |
518 (iao & ((1 << 1) | (1 << 2)) ? 0 : 1 << 1) |
519 (iao & ((1 << 0) | (1 << 3)) ? 0 : 1 << 2) |
520 (iao & ((1 << 1) | (1 << 3)) ? 0 : 1 << 3);
521 }
522 static inline unsigned int ao2qbs3D (const unsigned int ao)
523 {
524 const unsigned int iao = ~ao;
525
526 return
527 (iao & ((1 << 0) | (1 << 2) | (1 << 4)) ? 0 : 1 << 0) |
528 (iao & ((1 << 1) | (1 << 2) | (1 << 4)) ? 0 : 1 << 1) |
529 (iao & ((1 << 0) | (1 << 3) | (1 << 4)) ? 0 : 1 << 2) |
530 (iao & ((1 << 1) | (1 << 3) | (1 << 4)) ? 0 : 1 << 3) |
531 (iao & ((1 << 0) | (1 << 2) | (1 << 5)) ? 0 : 1 << 4) |
532 (iao & ((1 << 1) | (1 << 2) | (1 << 5)) ? 0 : 1 << 5) |
533 (iao & ((1 << 0) | (1 << 3) | (1 << 5)) ? 0 : 1 << 6) |
534 (iao & ((1 << 1) | (1 << 3) | (1 << 5)) ? 0 : 1 << 7);
535 }
536
537 static inline unsigned int quad (const DegreeBounds <Tag> & b, const SCALAR x, const SCALAR y)
538 {
539 const vector2D <SCALAR> c = b.center();
540 return
541 (y >= c.y ? 1 << 1 : 0 << 1) |
542 (x >= c.x ? 1 << 0 : 0 << 0);
543 }
544 static inline unsigned int quad (const DegreeBounds <TreeTag3D<SCALAR>> & b, const SCALAR x, const SCALAR y, const SCALAR z)
545 {
546 const vector3D <SCALAR> c = b.center();
547 return
548 (z >= c.z ? 1 << 2 : 0 << 2) |
549 (y >= c.y ? 1 << 1 : 0 << 1) |
550 (x >= c.x ? 1 << 0 : 0 << 0);
551 }
552
553 template< typename TagLVal >
554 static inline unsigned int intersects (const DegreeBounds< TagLVal > & b, const AmbientRegion & ar, TagLVal * = NULL)
555 { return true; }
556
557 template< typename TagLVal, typename TagRVal >
558 static inline unsigned int intersects (const DegreeBounds< TagLVal > & b, const PointRegion< TagRVal > & pr, TagLVal * = NULL, TagRVal * = NULL)
559 {
560 const vector2D <SCALAR> c = b.center();
561 return ao2qbs2D (
562 (pr.p.x < c.x ? 1 << 0 : 0) |
563 (pr.p.x >= c.x ? 1 << 1 : 0) |
564 (pr.p.y < c.y ? 1 << 2 : 0) |
565 (pr.p.y >= c.y ? 1 << 3 : 0)
566 );
567 }
568 static inline unsigned int intersects (const DegreeBounds <TreeTag3D< SCALAR >> & b, const PointRegion <TreeTag3D< SCALAR > > & pr)
569 {
570 const vector3D <SCALAR> c = b.center();
571 return ao2qbs3D (
572 (pr.p.x < c.x ? 1 << 0 : 0) |
573 (pr.p.x >= c.x ? 1 << 1 : 0) |
574 (pr.p.y < c.y ? 1 << 2 : 0) |
575 (pr.p.y >= c.y ? 1 << 3 : 0) |
576 (pr.p.z < c.z ? 1 << 4 : 0) |
577 (pr.p.z >= c.z ? 1 << 5 : 0)
578 );
579 }
580
581 template< typename TagLVal, typename TagRVal >
582 static inline unsigned int intersects (const DegreeBounds< TagLVal > & b, const RectRegion< TagRVal > & rr, TagLVal * = NULL, TagRVal * = NULL)
583 {
584 const vector2D <SCALAR> c = b.center();
585 return ao2qbs2D (
586 (rr.v1.x < c.x ? 1 << 0 : 0) |
587 (rr.v2.x >= c.x ? 1 << 1 : 0) |
588 (rr.v1.y < c.y ? 1 << 2 : 0) |
589 (rr.v2.y >= c.y ? 1 << 3 : 0)
590 );
591 }
592 static inline unsigned int intersects (const DegreeBounds <TreeTag3D< SCALAR >> & b, const RectRegion <TreeTag3D< SCALAR > > & rr)
593 {
594 const vector3D <SCALAR> c = b.center();
595 return ao2qbs3D (
596 (rr.v1.x < c.x ? 1 << 0 : 0) |
597 (rr.v2.x >= c.x ? 1 << 1 : 0) |
598 (rr.v1.y < c.y ? 1 << 2 : 0) |
599 (rr.v2.y >= c.y ? 1 << 3 : 0) |
600 (rr.v1.z < c.z ? 1 << 4 : 0) |
601 (rr.v2.z >= c.z ? 1 << 5 : 0)
602 );
603 }
604
605 template< typename TagLVal, typename TagRVal >
606 static inline unsigned int intersects (const DegreeBounds< TagLVal > & b, const RadialRegion< TagRVal > & rr, TagLVal * = NULL, TagRVal * = NULL)
607 {
608 using namespace mars;
609
610 const vector2D <SCALAR> c = b.center();
611 unsigned int j =
612 SQ(rr.p.x - c.x) + SQ(rr.p.y - c.y) >= SQ(rr.r) ?
613 1 << quad (b, c.x + (b.m2 - rr.p.x), c.y + (b.m2 - rr.p.y)) :
614 0;
615
616 return ao2qbs2D (
617 (rr.p.x < (c.x + rr.r) ? 1 << 0 : 0) |
618 (rr.p.x > (c.x - rr.r) ? 1 << 1 : 0) |
619 (rr.p.y < (c.y + rr.r) ? 1 << 2 : 0) |
620 (rr.p.y > (c.y - rr.r) ? 1 << 3 : 0)
621 ) & ~j;
622 }
623 static inline unsigned int intersects (const DegreeBounds <TreeTag3D <SCALAR> > & b, const RadialRegion < TreeTag3D <SCALAR> > & rr)
624 {
625 using namespace mars;
626
627 const vector3D <SCALAR> c = b.center();
628 unsigned int
629 j = SQ(rr.p.x - c.x) + SQ(rr.p.y - c.y) >= SQ(rr.r) ?
630 1 << quad (b, c.x + (b.m2 - rr.p.x), c.y + (b.m2 - rr.p.y), rr.p.z) :
631 0,
632 k = SQ(rr.p.x - c.x) + SQ(rr.p.z - c.z) >= SQ(rr.r) ?
633 1 << quad (b, c.x + (b.m2 - rr.p.x), c.y + (b.m2 - rr.p.y), c.z + (b.m2 - rr.p.z)) :
634 0;
635
636 return ao2qbs3D (
637 (rr.p.x < (c.x + rr.r) ? 1 << 0 : 0) |
638 (rr.p.x > (c.x - rr.r) ? 1 << 1 : 0) |
639 (rr.p.y < (c.y + rr.r) ? 1 << 2 : 0) |
640 (rr.p.y > (c.y - rr.r) ? 1 << 3 : 0) |
641 (rr.p.z < (c.z + rr.r) ? 1 << 4 : 0) |
642 (rr.p.z > (c.z - rr.r) ? 1 << 5 : 0)
643 ) & ~(j | k);
644 }
645 static inline void slide (DegreeBounds <TreeTag2D <SCALAR> > & b, const unsigned int q0, const unsigned int q)
646 {
647 const SCALAR m = b.m2 * static_cast <SCALAR> (2);
648
649 b.loc.x += m * static_cast <SCALAR> ((q & (1 << 0)) - (q0 & (1 << 0)));
650 b.loc.y += m * static_cast <SCALAR> ((q & (1 << 1)) - (q0 & (1 << 1)));
651 }
652 static inline void slide (DegreeBounds <TreeTag3D <SCALAR> > & b, const unsigned int q0, const unsigned int q)
653 {
654 const SCALAR m = b.m2 * static_cast <SCALAR> (2);
655
656 b.loc.x += m * static_cast <SCALAR> ((q & (1 << 0)) - (q0 & (1 << 0)));
657 b.loc.y += m * static_cast <SCALAR> ((q & (1 << 1)) - (q0 & (1 << 1)));
658 b.loc.z += m * static_cast <SCALAR> ((q & (1 << 2)) - (q0 & (1 << 2)));
659 }
660
661 public:
662 VECTOR loc;
663 SCALAR m2;
664
665 inline DegreeBounds (const VECTOR & loc, const SCALAR m2)
666 : loc(loc), m2(m2) {}
667
668 inline VECTOR center() const { return loc + m2; }
669
670 template< typename Tag2 >
671 inline unsigned int intersects (const PointRegion < Tag2 > & pr) const { return intersects(*this, pr); }
672
673 template< typename Tag2 >
674 inline unsigned int intersects (const RadialRegion < Tag2 > & rr) const { return intersects(*this, rr); }
675
676 template< typename Tag2 >
677 inline unsigned int intersects (const RectRegion < Tag2 > & rr) const { return intersects(*this, rr); }
678
679 inline unsigned int intersects (const AmbientRegion & ar) const { return intersects(*this, ar); }
680
681 inline void slide (const unsigned int q0, const unsigned int q) { slide (*this, q0, q); }
682 inline void descend () { m2 /= 2; }
683 };
684
685 template <typename E, typename R, typename Tag>
686 class TreeDegree
687 {
688 public:
689 typedef typename Tag::SCALAR SCALAR;
690 typedef typename Tag::VECTOR VECTOR;
691 typedef std::list < Entity <E, R> > ListType;
692
693 private:
694 TreeDegree <E, R, Tag> * _degrees [Tag::DEGREES];
695 ListType * _list;
696
697 inline void push (const ptr< E > & pData, const R & rr)
698 {
699 if (_list == NULL)
700 _list = new ListType ();
701
702 _list->push_back(Entity <E, R> (pData, rr));
703 }
704
705 template <typename QR>
706 void add2 (const QR & rad, const ptr< E > & pData, const DegreeBounds <Tag> &b)
707 {
708 for (DegreeNicheIterator <E, R, QR, Tag> it (this, rad, b); it; ++it)
709 it->push(pData, rad);
710 }
711
712 public:
713 inline bool hasEntities () const { return _list != NULL && !_list->empty(); }
714 inline typename ListType::iterator begin () { return _list->begin(); }
715 inline typename ListType::iterator end() { return _list->end(); }
716 inline typename ListType::const_iterator begin () const { return _list->begin(); }
717 inline typename ListType::const_iterator end() const { return _list->end(); }
718
719 TreeDegree (unsigned short ndegs, SCALAR m)
720 : _list(NULL)
721 {
722 if (--ndegs)
723 {
724 SCALAR m2 = m / static_cast <SCALAR> (2);
725 for (unsigned int c = 0; c < Tag::DEGREES; c++)
726 _degrees[c] = new TreeDegree <E, R, Tag> (ndegs, m2);
727 } else
728 {
729 for (unsigned int c = 0; c < Tag::DEGREES; c++)
730 _degrees[c] = NULL;
731 }
732 }
733
734 inline void add (const CylindricalRegion <SCALAR> & cyl, const ptr< E > & pData, const DegreeBounds <Tag> & b)
735 { add2(cyl, pData, b); }
736 inline void add (const RadialRegion <Tag> & rad, const ptr< E > & pData, const DegreeBounds <Tag> & b)
737 { add2(rad, pData, b); }
738 inline void add (const RectRegion <Tag> & rect, const ptr< E > & pData, const DegreeBounds <Tag> & b)
739 { add2(rect, pData, b); }
740
741 inline bool bottom () const { return _degrees[0] == NULL; }
742 inline const TreeDegree <E, R, Tag> * operator [] (int i) const { return _degrees[i]; }
743 inline TreeDegree <E, R, Tag> * operator [] (int i) { return _degrees[i]; }
744
745 ~TreeDegree ()
746 {
747 for (unsigned int i = 0; i < Tag::DEGREES; ++i)
748 if (_degrees[i])
749 delete _degrees[i];
750
751 if (_list != NULL)
752 delete _list;
753 }
754 };
755
756 template< typename E, typename R, typename Tag >
757 struct TreeIteratorTraits
758 {
759 typedef TreeDegree< E, R, Tag > MyTreeDegree;
760 typedef ptr< E > PtrE;
761 };
762 template< typename E, typename R, typename Tag >
763 struct ConstTreeIteratorTraits
764 {
765 typedef const TreeDegree< E, R, Tag > MyTreeDegree;
766 typedef const ptr< E > PtrE;
767 };
768
769 template <typename E, typename R, typename QR, typename Tag, typename TIT = TreeIteratorTraits< E, R, Tag >>
770 class DegreeIteratorBase
771 {
772 public:
773 typedef typename TIT::MyTreeDegree TreeDegree;
774
775 protected:
776 class State
777 {
778 public:
779 TreeDegree * window;
780 DegreeBounds <Tag> subbounds;
781 unsigned int intersection, idxlast;
782 int idx;
783
784 inline State (TreeDegree * const & window, const DegreeBounds <Tag> & bounds)
785 : subbounds(bounds), window(window), intersection(0), idxlast(0), idx(-1) {}
786
787 } _state;
788
789 std::stack <State> _stack;
790 const QR _q;
791 TreeDegree * _degcurr;
792
793 inline bool undrill ()
794 {
795 if (_stack.empty())
796 return false;
797 else
798 {
799 _state = _stack.top();
800 _stack.pop();
801 return true;
802 }
803 }
804 inline void initDegree()
805 {
806 // Some weirdness here, for optimization reasons, we're going to reuse the "subbounds" property and treat it as the
807 // present window's "bounds" in order to compute the sub-division intersection bitset. This is the only time we need
808 // "bounds" for the window, so we can throw it away from here-on in and convert it to "subbounds" for the current
809 // window proper.
810 _state.intersection = _state.subbounds.intersects(_q);
811 _state.subbounds.descend();
812
813 _state.idx = -1;
814 _state.idxlast = 0;
815 }
816 inline void drill(TreeDegree * const & deg)
817 {
818 _stack.push(_state);
819 _state.window = deg;
820 // Do not call subbounds.descend() yet, we need its present state somewhere else for a bit yet
821 }
822 inline void slideTo(const int i)
823 {
824 _degcurr = (*_state.window)[i];
825 _state.subbounds.slide(_state.idxlast, i);
826 _state.idxlast = i;
827 }
828
829 inline DegreeIteratorBase (TreeDegree * top, const DegreeBounds <Tag> & bounds, const QR & q)
830 : _state(top, bounds), _q(q), _degcurr(NULL) {}
831 };
832
833 template <typename E, typename R, typename QR, typename Tag, typename TIT >
834 class DegreeNicheIterator : public DegreeIteratorBase< E, R, QR, Tag, TIT >, public std::iterator <std::input_iterator_tag, TreeDegree <E, R, Tag> >
835 {
836 private:
837 typedef DegreeIteratorBase< E, R, QR, Tag, TIT > Base;
838 using typename Base::TreeDegree;
839
840 CR_CONTEXT;
841
842 void process()
843 {
844 CR_START();
845 if (this->_q.isNiche(this->_state.subbounds))
846 {
847 this->_degcurr = this->_state.window;
848 CR_RETURN_VOID;
849 } else
850 {
851 this->initDegree();
852
853 do
854 {
855 while (++this->_state.idx < Tag::DEGREES)
856 {
857 if (this->_state.intersection & (1 << this->_state.idx))
858 {
859 this->slideTo(this->_state.idx);
860
861 if (this->_q.isNiche(this->_state.subbounds) || this->_degcurr->bottom())
862 {
863 CR_RETURN_VOID;
864 } else
865 { // Recurse downwards
866 this->drill(this->_degcurr);
867 this->initDegree();
868 continue;
869 }
870 }
871 }
872 } while (this->undrill());
873 }
874
875 this->_degcurr = NULL;
876 CR_END();
877 }
878
879 public:
880 inline DegreeNicheIterator (TreeDegree * top, const QR & q, const DegreeBounds <Tag> & bounds)
881 : Base(top, bounds, q)
882 {
883 CR_INIT();
884 process();
885 }
886 inline operator bool () { return this->_degcurr != NULL; }
887 inline DegreeNicheIterator & operator++()
888 {
889 process();
890 return *this;
891 }
892 inline DegreeNicheIterator operator++(int)
893 {
894 DegreeNicheIterator old = *this;
895 process();
896 return old;
897 }
898 inline const TreeDegree * operator -> () const { return &(*this->_degcurr); }
899 inline const TreeDegree & operator * () const { return *this->_degcurr; }
900 inline TreeDegree * operator -> () { return &(*this->_degcurr); }
901 inline TreeDegree & operator * () { return *this->_degcurr; }
902 };
903
904 template <typename E, typename R, typename QR, typename Tag, typename TIT = TreeIteratorTraits< E, R, Tag >>
905 class DegreeIterator : public DegreeIteratorBase <E, R, QR, Tag, TIT >, public std::iterator <std::input_iterator_tag, TreeDegree <E, R, Tag> >
906 {
907 private:
908 typedef DegreeIteratorBase <E, R, QR, Tag, TIT > Base;
909 using typename Base::TreeDegree;
910
911 CR_CONTEXT;
912
913 void process()
914 {
915 CR_START();
916
917 this->initDegree();
918 do
919 {
920 while (++this->_state.idx < Tag::DEGREES)
921 {
922 if (this->_state.intersection & (1 << this->_state.idx))
923 {
924 this->slideTo(this->_state.idx);
925 CR_RETURN_VOID;
926
927 // Recurse downwards
928 if (!this->_degcurr->bottom())
929 {
930 this->drill (this->_degcurr);
931 this->initDegree();
932 continue;
933 }
934 }
935 }
936 } while (this->undrill());
937
938 this->_degcurr = NULL;
939 CR_END();
940 }
941 public:
942 inline DegreeIterator (TreeDegree * top, const QR & q, const DegreeBounds <Tag> & bounds)
943 : Base(top, bounds, q)
944 {
945 CR_INIT();
946 process();
947 }
948 inline operator bool () { return this->_degcurr != NULL; }
949 inline DegreeIterator & operator++()
950 {
951 process();
952 return *this;
953 }
954 inline DegreeIterator operator++(int)
955 {
956 DegreeIterator old = *this;
957 process();
958 return old;
959 }
960 inline const TreeDegree * operator -> () const { return &(*this->_degcurr); }
961 inline const TreeDegree & operator * () const { return *this->_degcurr; }
962 inline TreeDegree * operator -> () { return &(*this->_degcurr); }
963 inline TreeDegree & operator * () { return *this->_degcurr; }
964 };
965
966 template <typename E, typename R, typename QR, typename Tag, typename TIT = ConstTreeIteratorTraits< E, R, Tag > >
967 class ConstEntityIterator : public std::iterator <std::input_iterator_tag, E>
968 {
969 public:
970 typedef typename Tag::SCALAR SCALAR;
971 typedef typename Tag::VECTOR VECTOR;
972 typedef typename TIT::PtrE ElemPtr;
973
974 private:
975 typedef typename TIT::MyTreeDegree::ListType::const_iterator ListIterator;
976
977 const QR _q;
978 DegreeIterator <E, R, QR, Tag, TIT> _itD;
979 ListIterator _itE;
980 std::set < const E * > _set;
981 bool _more;
982
983 CR_CONTEXT;
984
985 protected:
986 void process ()
987 {
988 CR_START();
989
990 _more = true;
991
992 while (_itD)
993 {
994 if (_itD->hasEntities())
995 {
996 for (_itE = _itD->begin(); _itE != _itD->end(); ++_itE)
997 {
998 if (_itE->region & _q)
999 {
1000 if (_set.find(_itE->pData.pointer()) == _set.end())
1001 {
1002 _set.insert(_itE->pData.pointer());
1003 CR_RETURN_VOID;
1004 }
1005 }
1006 }
1007 }
1008 ++_itD;
1009 }
1010
1011 _more = false;
1012
1013 CR_END();
1014 }
1015
1016 public:
1017 inline ConstEntityIterator (typename TIT::MyTreeDegree & top, const QR & query, const VECTOR & ptOffset, const SCALAR magnitude)
1018 : _itD (&top, query, DegreeBounds <Tag> (ptOffset, magnitude / 2)), _q(query), _more(false)
1019 {
1020 CR_INIT();
1021 process();
1022 }
1023
1024 inline operator bool () const { return _more; }
1025 inline bool hasMore () const { return _more; }
1026 inline const ConstEntityIterator & operator++()
1027 {
1028 process();
1029 return *this;
1030 }
1031 inline const ConstEntityIterator operator++(int)
1032 {
1033 const ConstEntityIterator old = *this;
1034 process();
1035 return old;
1036 }
1037 inline const R & region () const { return _itE->region; }
1038 inline const ptr< E > & operator -> () const { return _itE->pData; }
1039 inline const E & operator * () const { return *_itE->pData; }
1040 inline operator ElemPtr () const { return _itE->pData; }
1041 };
1042
1043 template <typename E, typename R, typename QR, typename Tag >
1044 class EntityIterator : public ConstEntityIterator< E, R, QR, Tag, TreeIteratorTraits< E, R, Tag > >
1045 {
1046 private:
1047 typedef ConstEntityIterator< E, R, QR, Tag, TreeIteratorTraits< E, R, Tag > > Base;
1048 using typename Base::VECTOR;
1049 using typename Base::SCALAR;
1050
1051 public:
1052 inline EntityIterator (typename TreeIteratorTraits< E, R, Tag >::MyTreeDegree & top, const QR & query, const VECTOR & ptOffset, const SCALAR magnitude)
1053 : Base(top, query, ptOffset, magnitude) {}
1054
1055 inline ptr< E > & operator -> () { return this->_itE->pData; }
1056 inline E & operator * () { return *this->_itE->pData; }
1057 };
1058
1059 template <typename E, typename R, typename Tag>
1060 class LookupTree
1061 {
1062 public:
1063 template< typename Tag2 >
1064 class Explicit
1065 {
1066 public:
1067 typedef typename Tag2::VECTOR VECTOR;
1068 typedef typename Tag2::SCALAR SCALAR;
1069 typedef mars::RectRegion <Tag2> RectRegion;
1070 typedef mars::RadialRegion <Tag2> RadialRegion;
1071 typedef mars::CylindricalRegion <SCALAR> CylindricalRegion;
1072 typedef mars::PointRegion <Tag2> PointRegion;
1073 typedef EntityIterator <E, R, PointRegion, Tag> EntityPointIterator;
1074 typedef EntityIterator <E, R, RectRegion, Tag> EntityRectIterator;
1075 typedef EntityIterator <E, R, RadialRegion, Tag> EntityRadialIterator;
1076 typedef ConstEntityIterator <E, R, PointRegion, Tag > const_EntityPointIterator;
1077 typedef ConstEntityIterator <E, R, RectRegion, Tag > const_EntityRectIterator;
1078 typedef ConstEntityIterator <E, R, RadialRegion, Tag > const_EntityRadialIterator;
1079 };
1080
1081 typedef typename Tag::VECTOR VECTOR;
1082 typedef typename Tag::SCALAR SCALAR;
1083 typedef TreeTag3D< SCALAR > Tag3D;
1084 typedef TreeTag2D< SCALAR > Tag2D;
1085 typedef Entity <E, R> MyEntity;
1086 typedef RectRegion <Tag> MyRectRegion;
1087 typedef RadialRegion <Tag> MyRadialRegion;
1088 typedef CylindricalRegion <SCALAR> MyCylindricalRegion;
1089 typedef PointRegion <Tag> MyPointRegion;
1090 typedef R Region;
1091 typedef EntityIterator <E, R, MyPointRegion, Tag> EntityPointIterator;
1092 typedef EntityIterator <E, R, MyRectRegion, Tag> EntityRectIterator;
1093 typedef EntityIterator <E, R, MyRadialRegion, Tag> EntityRadialIterator;
1094 typedef EntityIterator <E, R, AmbientRegion, Tag> EntityAllIterator;
1095 typedef ConstEntityIterator <E, R, MyPointRegion, Tag > const_EntityPointIterator;
1096 typedef ConstEntityIterator <E, R, MyRectRegion, Tag > const_EntityRectIterator;
1097 typedef ConstEntityIterator <E, R, MyRadialRegion, Tag > const_EntityRadialIterator;
1098 typedef ConstEntityIterator <E, R, AmbientRegion, Tag > const_EntityAllIterator;
1099 typedef TreeDegree <E, R, Tag> MyTreeDegree;
1100
1101 private:
1102 MyTreeDegree _top;
1103
1104 static inline unsigned short computeSuitableOrder (const SCALAR m)
1105 {
1106 return static_cast <unsigned short> (floor (log(static_cast<float> (m)) / log(4.0f)));
1107 }
1108
1109 public:
1110 const SCALAR magnitude;
1111 const VECTOR offset;
1112
1113 inline LookupTree(const SCALAR m, const VECTOR & offset = VECTOR()) : _top (computeSuitableOrder(m), m), magnitude(m), offset(offset) {}
1114 inline LookupTree(const SCALAR m, const unsigned short o, const VECTOR & offset = VECTOR()) : _top (o, m), magnitude(m), offset(offset) {}
1115
1116 inline EntityAllIterator contents () { return EntityAllIterator (_top, AmbientRegion(), offset, magnitude); }
1117 inline const_EntityAllIterator contents () const { return const_EntityAllIterator (_top, AmbientRegion(), offset, magnitude); }
1118
1119 template <typename QR>
1120 inline ConstEntityIterator <E, R, QR, Tag> contents (const QR & region) const
1121 { return ConstEntityIterator <E, R, QR, Tag> (_top, region, offset, magnitude); }
1122
1123 template <typename QR>
1124 inline EntityIterator <E, R, QR, Tag> contents (const QR & region)
1125 { return EntityIterator <E, R, QR, Tag> (_top, region, offset, magnitude); }
1126
1127 inline void add (const ptr< E > & pData, const R & r)
1128 {
1129 _top.add (r, pData, DegreeBounds <Tag> (offset, magnitude / static_cast <SCALAR> (2)));
1130 }
1131 };
1132
1133 template <typename E, typename T>
1134 class QuadTree_CircleIndexed : public LookupTree <E, RadialRegion < TreeTag2D <T> >, TreeTag2D <T> >
1135 {
1136 private:
1137 typedef LookupTree <E, RadialRegion < TreeTag2D <T> >, TreeTag2D <T> > Base;
1138
1139 public:
1140 using typename Base::VECTOR;
1141 using typename Base::SCALAR;
1142
1143 QuadTree_CircleIndexed (const SCALAR m, const VECTOR & offset = VECTOR()) : Base (m, offset) {}
1144 QuadTree_CircleIndexed (const SCALAR m, const unsigned short o, const VECTOR & offset = VECTOR()) : Base (m, o, offset) {}
1145 };
1146
1147 template <typename E, typename T>
1148 class OctTree_SphereIndexed : public LookupTree <E, RadialRegion < TreeTag3D <T> >, TreeTag3D <T> >
1149 {
1150 private:
1151 typedef LookupTree <E, RadialRegion < TreeTag3D <T> >, TreeTag3D <T> > Base;
1152
1153 public:
1154 using typename Base::VECTOR;
1155 using typename Base::SCALAR;
1156
1157 OctTree_SphereIndexed (const SCALAR m, const VECTOR & offset = VECTOR()) : Base (m, offset) {}
1158 OctTree_SphereIndexed (const SCALAR m, const unsigned short o, const VECTOR & offset = VECTOR()) : Base (m, o, offset) {}
1159 };
1160
1161 template <typename E, typename T>
1162 class QuadTree_BBoxIndexed : public LookupTree <E, RectRegion < TreeTag2D <T> >, TreeTag2D <T> >
1163 {
1164 private:
1165 typedef LookupTree <E, RectRegion < TreeTag2D <T> >, TreeTag2D <T> > Base;
1166
1167 public:
1168 using typename Base::VECTOR;
1169 using typename Base::SCALAR;
1170
1171 QuadTree_BBoxIndexed (const SCALAR m, const VECTOR & offset = VECTOR()) : Base (m, offset) {}
1172 QuadTree_BBoxIndexed (const SCALAR m, const unsigned short o, const VECTOR & offset = VECTOR()) : Base (m, o, offset) {}
1173 };
1174
1175 template <typename E, typename T>
1176 class QuadTree_SphereIndexed : public LookupTree <E, CylindricalRegion <T>, TreeTag2D <T> >
1177 {
1178 private:
1179 typedef LookupTree <E, CylindricalRegion <T>, TreeTag2D <T> > Base;
1180
1181 public:
1182 using typename Base::VECTOR;
1183 using typename Base::SCALAR;
1184
1185 QuadTree_SphereIndexed (const SCALAR m, const VECTOR & offset = VECTOR()) : Base (m, offset) {}
1186 QuadTree_SphereIndexed (const SCALAR m, const unsigned short o, const VECTOR & offset = VECTOR()) : Base (m, o, offset) {}
1187 };
1188}
1189
1190
1191#endif
Note: See TracBrowser for help on using the repository browser.