source: trunk/VUT/GtpVisibilityPreprocessor/src/AxisAlignedBox3.cpp @ 492

Revision 492, 54.8 KB checked in by bittner, 19 years ago (diff)

Large merge - viewcells seem not functional now
Line 
1
2// GOLEM library
3#include <assert.h>
4#include <iostream>
5using namespace std;
6#include "AxisAlignedBox3.h"
7#include "Ray.h"
8#include "Polygon3.h"
9#include "Mesh.h"
10
11#define FATAL Debug
12#define FATAL_ABORT exit(1)
13
14
15// AxisAlignedBox3 implementations
16
17// Overload << operator for C++-style output
18ostream&
19operator<< (ostream &s, const AxisAlignedBox3 &A)
20{
21  return s << '[' << A.mMin.x << ", " << A.mMin.y << ", " << A.mMin.z << "]["
22           << A.mMax.x << ", " << A.mMax.y << ", " << A.mMax.z << ']';
23}
24
25// Overload >> operator for C++-style input
26istream&
27operator>> (istream &s, AxisAlignedBox3 &A)
28{
29  char a;
30  // read "[min.x, min.y, min.z][mMax.x, mMax.y, mMax.z]"
31  return s >> a >> A.mMin.x >> a >> A.mMin.y >> a >> A.mMin.z >> a >> a
32    >> A.mMax.x >> a >> A.mMax.y >> a >> A.mMax.z >> a;
33}
34
35bool
36AxisAlignedBox3::Unbounded() const
37{
38  return (mMin == Vector3(-MAXFLOAT)) ||
39         (mMax == Vector3(-MAXFLOAT));
40}
41
42void
43AxisAlignedBox3::Include(const Vector3 &newpt)
44{
45  Minimize(mMin, newpt);
46  Maximize(mMax, newpt);
47}
48
49void
50AxisAlignedBox3::Include(const Polygon3 &newpoly)
51{
52        VertexContainer::const_iterator it, it_end = newpoly.mVertices.end();
53
54        for (it = newpoly.mVertices.begin(); it != it_end; ++ it)
55                Include(*it);
56}
57
58void
59AxisAlignedBox3::Include(const AxisAlignedBox3 &bbox)
60{
61  Minimize(mMin, bbox.mMin);
62  Maximize(mMax, bbox.mMax);
63}
64
65bool
66AxisAlignedBox3::IsCorrect()
67{
68  if ( (mMin.x > mMax.x) ||
69       (mMin.y > mMax.y) ||
70       (mMin.z > mMax.z) )
71    return false; // box is not formed
72  return true;
73}
74
75void
76AxisAlignedBox3::GetEdge(const int edge, Vector3 *a, Vector3 *b) const
77{
78  switch(edge) {
79  case 0:
80    a->SetValue(mMin.x, mMin.y, mMin.z);
81    b->SetValue(mMin.x, mMin.y, mMax.z);
82    break;
83  case 1:
84    a->SetValue(mMin.x, mMin.y, mMin.z);
85    b->SetValue(mMin.x, mMax.y, mMin.z);
86    break;
87  case 2:
88    a->SetValue(mMin.x, mMin.y, mMin.z);
89    b->SetValue(mMax.x, mMin.y, mMin.z);
90    break;
91  case 3:
92    a->SetValue(mMax.x, mMax.y, mMax.z);
93    b->SetValue(mMax.x, mMax.y, mMin.z);
94    break;
95  case 4:
96    a->SetValue(mMax.x, mMax.y, mMax.z);
97    b->SetValue(mMax.x, mMin.y, mMax.z);
98    break;
99  case 5:
100    a->SetValue(mMax.x, mMax.y, mMax.z);
101    b->SetValue(mMin.x, mMax.y, mMax.z);
102    break;
103   
104  case 6:
105    a->SetValue(mMin.x, mMin.y, mMax.z);
106    b->SetValue(mMin.x, mMax.y, mMax.z);
107    break;
108  case 7:
109    a->SetValue(mMin.x, mMin.y, mMax.z);
110    b->SetValue(mMax.x, mMin.y, mMax.z);
111    break;
112  case 8:
113    a->SetValue(mMin.x, mMax.y, mMin.z);
114    b->SetValue(mMin.x, mMax.y, mMax.z);
115    break;
116  case 9:
117    a->SetValue(mMin.x, mMax.y, mMin.z);
118    b->SetValue(mMax.x, mMax.y, mMin.z);
119    break;
120  case 10:
121    a->SetValue(mMax.x, mMin.y, mMin.z);
122    b->SetValue(mMax.x, mMax.y, mMin.z);
123    break;
124  case 11:
125    a->SetValue(mMax.x, mMin.y, mMin.z);
126    b->SetValue(mMax.x, mMin.y, mMax.z);
127    break;
128  }
129}
130
131// returns the vertex indices in the range <0..7>, v = 4.x + 2.y + z, where
132// x,y,z are either 0 or 1; (0 .. min coordinate, 1 .. max coordinate)
133void
134AxisAlignedBox3::GetEdge(const int edge, int  &aIdx, int &bIdx) const
135{
136  switch(edge) {
137  case 0: aIdx = 0; bIdx = 1; break;
138  case 1: aIdx = 0; bIdx = 2; break;
139  case 2: aIdx = 0; bIdx = 4; break;
140  case 3: aIdx = 7; bIdx = 6; break;
141  case 4: aIdx = 7; bIdx = 5; break;
142  case 5: aIdx = 7; bIdx = 3; break;
143  case 6: aIdx = 1; bIdx = 3; break;
144  case 7: aIdx = 1; bIdx = 5; break;
145  case 8: aIdx = 2; bIdx = 3; break;
146  case 9: aIdx = 2; bIdx = 6; break;
147  case 10: aIdx = 4; bIdx = 6; break;
148  case 11: aIdx = 4; bIdx = 5; break;
149  }
150}
151
152void
153AxisAlignedBox3::Include(const int &axis, const float &newBound)
154{
155  switch (axis) {
156    case 0: { // x-axis
157      if (mMin.x > newBound)
158        mMin.x = newBound;
159      if (mMax.x < newBound)
160        mMax.x = newBound;
161      break;
162    }
163    case 1: { // y-axis
164      if (mMin.y > newBound)
165        mMin.y = newBound;
166      if (mMax.y < newBound)
167        mMax.y = newBound;
168      break;
169    }
170    case 2: { // z-axis
171      if (mMin.z > newBound)
172        mMin.z = newBound;
173      if (mMax.z < newBound)
174        mMax.z = newBound;
175      break;
176    }
177  }
178}
179
180#if 0
181// ComputeMinMaxT computes the minimum and maximum signed distances
182// of intersection with the ray; it returns 1 if the ray hits
183// the bounding box and 0 if it does not.
184int
185AxisAlignedBox3::ComputeMinMaxT(const Ray &ray,
186                                float *tmin,
187                                float *tmax) const
188{
189  float minx, maxx, miny, maxy, minz, maxz;
190
191  if (fabs(ray.dir.x) < 0.001) {
192    if (mMin.x < ray.loc.x && mMax.x > ray.loc.x) {
193      minx = -MAXFLOAT;
194      maxx = MAXFLOAT;
195    }
196    else
197      return 0;
198  }
199  else {
200    float t1 = (mMin.x - ray.loc.x) / ray.dir.x;
201    float t2 = (mMax.x - ray.loc.x) / ray.dir.x;
202    if (t1 < t2) {
203      minx = t1;
204      maxx = t2;
205    }
206    else {
207      minx = t2;
208      maxx = t1;
209    }
210    if (maxx < 0)
211      return 0;
212  }
213
214  if (fabs(ray.dir.y) < 0.001) {
215    if (mMin.y < ray.loc.y && mMax.y > ray.loc.y) {
216      miny = -MAXFLOAT;
217      maxy = MAXFLOAT;
218    }
219    else
220      return 0;
221  }
222  else {
223    float t1 = (mMin.y - ray.loc.y) / ray.dir.y;
224    float t2 = (mMax.y - ray.loc.y) / ray.dir.y;
225    if (t1 < t2) {
226      miny = t1;
227      maxy = t2;
228    }
229    else {
230      miny = t2;
231      maxy = t1;
232    }
233    if (maxy < 0.0)
234      return 0;
235  }
236
237  if (fabs(ray.dir.z) < 0.001) {
238    if (mMin.z < ray.loc.z && mMax.z > ray.loc.z) {
239      minz = -MAXFLOAT;
240      maxz = MAXFLOAT;
241    }
242    else
243      return 0;
244  }
245  else {
246    float t1 = (mMin.z - ray.loc.z) / ray.dir.z;
247    float t2 = (mMax.z - ray.loc.z) / ray.dir.z;
248    if (t1 < t2) {
249      minz = t1;
250      maxz = t2;
251    }
252    else {
253      minz = t2;
254      maxz = t1;
255    }
256    if (maxz < 0.0)
257      return 0;
258  }
259
260  *tmin = minx;
261  if (miny > *tmin)
262    *tmin = miny;
263  if (minz > *tmin)
264    *tmin = minz;
265
266  *tmax = maxx;
267  if (maxy < *tmax)
268    *tmax = maxy;
269  if (maxz < *tmax)
270    *tmax = maxz;
271
272  return 1; // yes, intersection was found
273}
274#else
275// another variant of the same, with less variables
276int
277AxisAlignedBox3::ComputeMinMaxT(const Ray &ray,
278                                float *tmin,
279                                float *tmax) const
280{
281  register float minx, maxx;
282  ray.ComputeInvertedDir();
283 
284  if (fabs(ray.dir.x) < 0.001) {
285    if (mMin.x < ray.loc.x && mMax.x > ray.loc.x) {
286      minx = -MAXFLOAT;
287      maxx = MAXFLOAT;
288    }
289    else
290      return 0;
291  }
292  else {
293    float t1 = (mMin.x - ray.loc.x) * ray.invDir.x;
294    float t2 = (mMax.x - ray.loc.x) * ray.invDir.x;
295    if (t1 < t2) {
296      minx = t1;
297      maxx = t2;
298    }
299    else {
300      minx = t2;
301      maxx = t1;
302    }
303        //    if (maxx < 0.0)
304        //      return 0;
305  }
306
307  *tmin = minx;
308  *tmax = maxx;
309 
310  if (fabs(ray.dir.y) < 0.001) {
311    if (mMin.y < ray.loc.y && mMax.y > ray.loc.y) {
312      minx = -MAXFLOAT;
313      maxx = MAXFLOAT;
314    }
315    else
316      return 0;
317  }
318  else {
319    float t1 = (mMin.y - ray.loc.y) * ray.invDir.y;
320    float t2 = (mMax.y - ray.loc.y) * ray.invDir.y;
321    if (t1 < t2) {
322      minx = t1;
323      maxx = t2;
324    }
325    else {
326      minx = t2;
327      maxx = t1;
328    }
329        //    if (maxx < 0.0)
330        //      return 0;
331  }
332
333  if (minx > *tmin)
334    *tmin = minx;
335  if (maxx < *tmax)
336    *tmax = maxx;
337 
338  if (fabs(ray.dir.z) < 0.001) {
339    if (mMin.z < ray.loc.z && mMax.z > ray.loc.z) {
340      minx = -MAXFLOAT;
341      maxx = MAXFLOAT;
342    }
343    else
344      return 0;
345  }
346  else {
347    float t1 = (mMin.z - ray.loc.z) * ray.invDir.z;
348    float t2 = (mMax.z - ray.loc.z) * ray.invDir.z;
349    if (t1 < t2) {
350      minx = t1;
351      maxx = t2;
352    }
353    else {
354      minx = t2;
355      maxx = t1;
356    }
357        //    if (maxx < 0.0)
358        //      return 0;
359  }
360
361  if (minx > *tmin)
362    *tmin = minx;
363  if (maxx < *tmax)
364    *tmax = maxx;
365
366  return 1; // yes, intersection was found
367}
368#endif
369
370// ComputeMinMaxT computes the minimum and maximum parameters
371// of intersection with the ray; it returns 1 if the ray hits
372// the bounding box and 0 if it does not.
373int
374AxisAlignedBox3::ComputeMinMaxT(const Ray &ray, float *tmin, float *tmax,
375                                EFaces &entryFace, EFaces &exitFace) const
376{
377  float minx, maxx, miny, maxy, minz, maxz;
378  int swapped[3];
379 
380  if (fabs(ray.dir.x) < 0.001) {
381    if (mMin.x < ray.loc.x && mMax.x > ray.loc.x) {
382      minx = -MAXFLOAT;
383      maxx = MAXFLOAT;
384    }
385    else
386      return 0;
387  }
388  else {
389    float t1 = (mMin.x - ray.loc.x) / ray.dir.x;
390    float t2 = (mMax.x - ray.loc.x) / ray.dir.x;
391    if (t1 < t2) {
392      minx = t1;
393      maxx = t2;
394      swapped[0] = 0;
395    }
396    else {
397      minx = t2;
398      maxx = t1;
399      swapped[0] = 1;
400    }
401    if (maxx < 0)
402      return 0;
403  }
404
405  if (fabs(ray.dir.y) < 0.001) {
406    if (mMin.y < ray.loc.y && mMax.y > ray.loc.y) {
407      miny = -MAXFLOAT;
408      maxy = MAXFLOAT;
409    }
410    else
411      return 0;
412  }
413  else {
414    float t1 = (mMin.y - ray.loc.y) / ray.dir.y;
415    float t2 = (mMax.y - ray.loc.y) / ray.dir.y;
416    if (t1 < t2) {
417      miny = t1;
418      maxy = t2;
419      swapped[1] = 0;
420    }
421    else {
422      miny = t2;
423      maxy = t1;
424      swapped[1] = 1;
425    }
426    if (maxy < 0.0)
427      return 0;
428  }
429
430  if (fabs(ray.dir.z) < 0.001) {
431    if (mMin.z < ray.loc.z && mMax.z > ray.loc.z) {
432      minz = -MAXFLOAT;
433      maxz = MAXFLOAT;
434    }
435    else
436      return 0;
437  }
438  else {
439    float t1 = (mMin.z - ray.loc.z) / ray.dir.z;
440    float t2 = (mMax.z - ray.loc.z) / ray.dir.z;
441    if (t1 < t2) {
442      minz = t1;
443      maxz = t2;
444      swapped[2] = 0;
445    }
446    else {
447      minz = t2;
448      maxz = t1;
449      swapped[2] = 1;
450    }
451    if (maxz < 0.0)
452      return 0;
453  }
454
455  *tmin = minx;
456  entryFace = ID_Back;
457  if (miny > *tmin) {
458    *tmin = miny;
459    entryFace = ID_Left;
460  }
461  if (minz > *tmin) {
462    *tmin = minz;
463    entryFace = ID_Bottom;
464  }
465 
466  *tmax = maxx;
467  exitFace = ID_Back;
468  if (maxy < *tmax) {
469    *tmax = maxy;
470    exitFace = ID_Left;
471  }
472  if (maxz < *tmax) {
473    *tmax = maxz;
474    exitFace = ID_Bottom;
475  }
476
477  if (swapped[entryFace])
478    entryFace = (EFaces)(entryFace + 3);
479 
480  if (!swapped[exitFace])
481    exitFace = (EFaces)(exitFace + 3);
482 
483  return 1; // yes, intersection was found
484}
485
486void
487AxisAlignedBox3::Describe(ostream &app, int ind) const
488{
489  indent(app, ind);
490  app << "AxisAlignedBox3: min at(" << mMin << "), max at(" << mMax << ")\n";
491}
492
493// computes the passing through parameters for case tmin<tmax and tmax>0
494int
495AxisAlignedBox3::GetMinMaxT(const Ray &ray, float *tmin, float *tmax) const
496{
497  if (!ComputeMinMaxT(ray, tmin, tmax))
498    return 0;
499  if ( *tmax < *tmin)
500    return 0; // the ray passes outside the box
501
502  if ( *tmax < 0.0)
503    return 0; // the intersection is not on the positive halfline
504
505  return 1; // ray hits the box .. origin can be outside or inside the box
506}
507
508// computes the signed distances for case tmin<tmax and tmax>0
509int
510AxisAlignedBox3::GetMinMaxT(const Ray &ray, float *tmin, float *tmax,
511                            EFaces &entryFace, EFaces &exitFace) const
512{
513  if (!ComputeMinMaxT(ray, tmin, tmax, entryFace, exitFace))
514    return 0;
515  if ( *tmax < *tmin)
516    return 0; // the ray passes outside the box
517 
518  if ( *tmax < 0.0)
519    return 0; // the intersection is not on the positive halfline
520 
521  return 1; // ray hits the box .. origin can be outside or inside the box
522}
523
524#if 0
525int
526AxisAlignedBox3::IsInside(const Vector3 &point) const
527{
528  return (point.x >= mMin.x) && (point.x <= mMax.x) &&
529         (point.y >= mMin.y) && (point.y <= mMax.y) &&
530         (point.z >= mMin.z) && (point.z <= mMax.z);
531}
532#else
533int
534AxisAlignedBox3::IsInside(const Vector3 &v) const
535{
536  return ! (v.x < mMin.x ||
537            v.x > mMax.x ||
538            v.y < mMin.y ||
539            v.y > mMax.y ||
540            v.z < mMin.z ||
541            v.z > mMax.z);
542}
543#endif
544
545bool
546AxisAlignedBox3::Includes(const AxisAlignedBox3 &b) const
547{
548  return (b.mMin.x >= mMin.x &&
549      b.mMin.y >= mMin.y &&
550      b.mMin.z >= mMin.z &&
551      b.mMax.x <= mMax.x &&
552      b.mMax.y <= mMax.y &&
553      b.mMax.z <= mMax.z);
554
555}
556
557
558// compute the coordinates of one vertex of the box
559Vector3
560AxisAlignedBox3::GetVertex(int xAxis, int yAxis, int zAxis) const
561{
562  Vector3 p;
563  if (xAxis)
564    p.x = mMax.x;
565  else
566    p.x = mMin.x;
567
568  if (yAxis)
569    p.y = mMax.y;
570  else
571    p.y = mMin.y;
572
573  if (zAxis)
574    p.z = mMax.z;
575  else
576    p.z = mMin.z;
577  return p;
578}
579
580// compute the vertex for number N = <0..7>, N = 4.x + 2.y + z, where
581// x,y,z are either 0 or 1; (0 .. min coordinate, 1 .. max coordinate)
582void
583AxisAlignedBox3::GetVertex(const int N, Vector3 &vertex) const
584{
585  switch (N) {
586    case 0: vertex = mMin; break;
587    case 1: vertex.SetValue(mMin.x, mMin.y, mMax.z); break;
588    case 2: vertex.SetValue(mMin.x, mMax.y, mMin.z); break;
589    case 3: vertex.SetValue(mMin.x, mMax.y, mMax.z); break;
590    case 4: vertex.SetValue(mMax.x, mMin.y, mMin.z); break;
591    case 5: vertex.SetValue(mMax.x, mMin.y, mMax.z); break;
592    case 6: vertex.SetValue(mMax.x, mMax.y, mMin.z); break;
593    case 7: vertex = mMax; break;
594    default: {
595      FATAL << "ERROR in AxisAlignedBox3::GetVertex N=" << N <<  "\n";
596      FATAL_ABORT;
597    }
598  }
599}
600
601// Returns region 0 .. 26 ; R = 9*x + 3*y + z ; (x,y,z) \in {0,1,2}
602int
603AxisAlignedBox3::GetRegionID(const Vector3 &point) const
604{
605  int ID = 0;
606
607  if (point.z >= mMin.z) {
608    if (point.z <= mMax.z)
609      ID += 1; // inside the two boundary planes
610    else
611      ID += 2; // outside
612  }
613
614  if (point.y >= mMin.y) {
615    if (point.y <= mMax.y)
616      ID += 3; // inside the two boundary planes
617    else
618      ID += 6; // outside
619  }
620
621  if (point.x >= mMin.x) {
622    if (point.x <= mMax.x)
623      ID += 9; // inside the two boundary planes
624    else
625      ID += 18; // outside
626  }
627  return ID;
628}
629
630
631
632// computes if a given box (smaller) lies at least in one
633// projection whole in the box (larger) = this encompasses given
634// ;-----;
635// | ;-; |
636// | '-' |
637// '-----'
638int
639AxisAlignedBox3::IsPiercedByBox(const AxisAlignedBox3 &box, int &axis) const
640{
641  // test on x-axis
642  if ( (mMax.x < box.mMin.x) ||
643       (mMin.x > box.mMax.x) )
644    return 0; // the boxes do not overlap at all at x-axis
645  if ( (box.mMin.y > mMin.y) &&
646       (box.mMax.y < mMax.y) &&
647       (box.mMin.z > mMin.z) &&
648       (box.mMax.z < mMax.z) ) {
649    axis = 0;
650    return 1; // the boxes overlap in x-axis
651  }
652  // test on y-axis
653  if ( (mMax.y < box.mMin.y) ||
654       (mMin.y > box.mMax.y) )
655    return 0; // the boxes do not overlap at all at y-axis
656  if ( (box.mMin.x > mMin.x) &&
657       (box.mMax.x < mMax.x) &&
658       (box.mMin.z > mMin.z) &&
659       (box.mMax.z < mMax.z) ) {
660    axis = 1;
661    return 1; // the boxes overlap in y-axis
662  }
663  // test on z-axis
664  if ( (mMax.z < box.mMin.z) ||
665       (mMin.z > box.mMax.z) )
666    return 0; // the boxes do not overlap at all at y-axis
667  if ( (box.mMin.x > mMin.x) &&
668       (box.mMax.x < mMax.x) &&
669       (box.mMin.y > mMin.y) &&
670       (box.mMax.y < mMax.y) ) {
671    axis = 2;
672    return 1; // the boxes overlap in z-axis
673  }
674  return 0;
675}
676
677float
678AxisAlignedBox3::SurfaceArea() const
679{
680  Vector3 ext = mMax - mMin;
681 
682  return 2.0f * (ext.x * ext.y +
683                ext.x * ext.z +
684                ext.y * ext.z);
685}
686
687const int AxisAlignedBox3::bvertices[27][9] =
688{                   // region number.. position
689  {5,1,3,2,6,4,-1,-1,-1},      // 0 .. x=0 y=0 z=0
690  {4,5,1,3,2,0,-1,-1,-1},      // 1 .. x=0 y=0 z=1
691  {4,5,7,3,2,0,-1,-1,-1},      // 2 .. x=0 y=0 z=2
692
693  {0,1,3,2,6,4,-1,-1,-1},      // 3 .. x=0 y=1 z=0
694  {0,1,3,2,-1,-1,-1,-1,-1},    // 4 .. x=0 y=1 z=1
695  {1,5,7,3,2,0,-1,-1,-1},      // 5 .. x=0 y=1 z=2
696
697  {0,1,3,7,6,4,-1,-1,-1},      // 6 .. x=0 y=2 z=0
698  {0,1,3,7,6,2,-1,-1,-1},      // 7 .. x=0 y=2 z=1
699  {1,5,7,6,2,0,-1,-1,-1},      // 8 .. x=0 y=2 z=2
700
701  // the regions number <9,17>
702  {5,1,0,2,6,4,-1,-1,-1},      // 9  .. x=1 y=0 z=0
703  {5,1,0,4,-1,-1,-1,-1,-1},    // 10 .. x=1 y=0 z=1
704  {7,3,1,0,4,5,-1,-1,-1},      // 11 .. x=1 y=0 z=2
705
706  {4,0,2,6,-1,-1,-1,-1,-1},    // 12 .. x=1 y=1 z=0
707  {0,2,3,1,5,4,6,7,-1},        // 13 .. x=1 y=1 z=1 .. inside the box
708  {1,5,7,3,-1,-1,-1,-1,-1},    // 14 .. x=1 y=1 z=2
709
710  {4,0,2,3,7,6,-1,-1,-1},      // 15 .. x=1 y=2 z=0
711  {6,2,3,7,-1,-1,-1,-1,-1},    // 16 .. x=1 y=2 z=1
712  {1,5,7,6,2,3,-1,-1,-1},      // 17 .. x=1 y=2 z=2
713
714  // the regions number <18,26>
715  {1,0,2,6,7,5,-1,-1,-1},      // 18 .. x=2 y=0 z=0
716  {1,0,4,6,7,5,-1,-1,-1},      // 19 .. x=2 y=0 z=1
717  {0,4,6,7,3,1,-1,-1,-1},      // 20 .. x=2 y=0 z=2
718
719  {4,0,2,6,7,5,-1,-1,-1},      // 21 .. x=2 y=1 z=0
720  {5,4,6,7,-1,-1,-1,-1,-1},    // 22 .. x=2 y=1 z=1
721  {5,4,6,7,3,1,-1,-1,-1},      // 23 .. x=2 y=1 z=2
722
723  {4,0,2,3,7,5,-1,-1,-1},      // 24 .. x=2 y=2 z=0
724  {5,4,6,2,3,7,-1,-1,-1},      // 25 .. x=2 y=2 z=1
725  {5,4,6,2,3,1,-1,-1,-1},      // 26 .. x=2 y=2 z=2
726};
727
728// the visibility of boundary faces from a given region
729// one to three triples: (axis, min_vertex, max_vertex), axis==-1(terminator)
730const int AxisAlignedBox3::bfaces[27][10] =
731{                              // region number .. position
732  {0,0,3,1,0,5,2,0,6,-1},      // 0 .. x=0 y=0 z=0
733  {0,0,3,1,0,5,-1,-1,-1,-1},   // 1 .. x=0 y=0 z=1
734  {0,0,3,1,0,5,2,1,7,-1},      // 2 .. x=0 y=0 z=2
735
736  {0,0,3,2,0,6,-1,-1,-1,-1},   // 3 .. x=0 y=1 z=0
737  {0,0,3,-1,-1,-1,-1,-1,-1,-1},// 4 .. x=0 y=1 z=1
738  {0,0,3,2,1,7,-1,-1,-1,-1},   // 5 .. x=0 y=1 z=2
739
740  {0,0,3,1,2,7,2,0,6,-1},      // 6 .. x=0 y=2 z=0
741  {0,0,3,1,2,7,-1,-1,-1,-1},   // 7 .. x=0 y=2 z=1
742  {0,0,3,1,2,7,2,1,7,-1},      // 8 .. x=0 y=2 z=2
743
744  // the regions number <9,17>
745  {1,0,5,2,0,6,-1,-1,-1,-1},   // 9  .. x=1 y=0 z=0
746  {1,0,5,-1,-1,-1,-1,-1,-1,-1},// 10 .. x=1 y=0 z=1
747  {1,0,5,2,1,7,-1,-1,-1,-1},   // 11 .. x=1 y=0 z=2
748
749  {2,0,6,-1,-1,-1,-1,-1,-1,-1},// 12 .. x=1 y=1 z=0
750  {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},// 13 .. x=1 y=1 z=1 .. inside the box
751  {2,1,7,-1,-1,-1,-1,-1,-1,-1},// 14 .. x=1 y=1 z=2
752
753  {1,2,7,2,0,6,-1,-1,-1,-1},   // 15 .. x=1 y=2 z=0
754  {1,2,7,-1,-1,-1,-1,-1,-1,-1},// 16 .. x=1 y=2 z=1
755  {1,2,7,2,1,7,-1,-1,-1,-1},   // 17 .. x=1 y=2 z=2
756
757  // the region number <18,26>
758  {0,4,7,1,0,5,2,0,6,-1},      // 18 .. x=2 y=0 z=0
759  {0,4,7,1,0,5,-1,-1,-1,-1},   // 19 .. x=2 y=0 z=1
760  {0,4,7,1,0,5,2,1,7,-1},      // 20 .. x=2 y=0 z=2
761
762  {0,4,7,2,0,6,-1,-1,-1,-1},   // 21 .. x=2 y=1 z=0
763  {0,4,7,-1,-1,-1,-1,-1,-1,-1},// 22 .. x=2 y=1 z=1
764  {0,4,7,2,1,7,-1,-1,-1,-1},   // 23 .. x=2 y=1 z=2
765
766  {0,4,7,1,2,7,2,0,6,-1},      // 24 .. x=2 y=2 z=0
767  {0,4,7,1,2,7,-1,-1,-1,-1},   // 25 .. x=2 y=2 z=1
768  {0,4,7,1,2,7,2,1,7,-1},      // 26 .. x=2 y=2 z=2
769};
770
771// the correct corners indexing from entry face to exit face
772// first index determines entry face, second index exit face, and
773// the two numbers (indx, inc) determines: ind = the index on the exit
774// face, when starting from the vertex 0 on entry face, 'inc' is
775// the increment when we go on entry face in order 0,1,2,3 to create
776// convex shaft with the rectangle on exit face. That is, inc = -1 or 1.
777const int AxisAlignedBox3::pairFaceRects[6][6][2] = {
778  { // entry face = 0
779    {-1,0}, // exit face 0 .. no meaning
780    {0,-1}, // 1
781    {0,-1}, // 2
782    {0,1}, // 3 .. opposite face
783    {3,1}, // 4
784    {1,1} // 5
785  },
786  { // entry face = 1
787    {0,-1}, // exit face 0
788    {-1,0}, // 1 .. no meaning
789    {0,-1}, // 2
790    {1,1}, // 3
791    {0,1}, // 4 .. opposite face
792    {3,1} // 5
793  },
794  { // entry face = 2
795    {0,-1}, // 0
796    {0,-1}, // 1
797    {-1,0}, // 2 .. no meaning
798    {3,1}, // 3
799    {1,1}, // 4
800    {0,1} // 5 .. opposite face
801  },
802  { // entry face = 3
803    {0,1}, // 0 .. opposite face
804    {3,-1}, // 1
805    {1,1}, // 2
806    {-1,0}, // 3  .. no meaning
807    {0,-1}, // 4
808    {0,-1} // 5
809  },
810  { // entry face = 4
811    {1,1}, // 0
812    {0,1}, // 1 .. opposite face
813    {3,1}, // 2
814    {0,-1}, // 3
815    {-1,0}, // 4 .. no meaning
816    {0,-1} // 5
817  },
818  { // entry face = 5
819    {3,-1}, // 0
820    {1,1}, // 1
821    {0,1}, // 2  .. opposite face
822    {0,-1}, // 3
823    {0,-1}, // 4
824    {-1,0} // 5 .. no meaning
825  }
826};
827
828
829// ------------------------------------------------------------
830// The vertices that form CLOSEST points with respect to the region
831// for all the regions possible, number of regions is 3^3 = 27,
832// since two parallel sides of bbox forms three disjoint spaces.
833// The vertices are given in anti-clockwise order, stopped by value 15,
834// at most 8 points, at least 1 point.
835// The table includes the closest 1/2/4/8 points, followed possibly
836// by the set of coordinates that should be used for testing for
837// the proximity queries. The coordinates to be tested are described by
838// the pair (a,b), when a=0, we want to test min vector of the box,
839//                 when a=1, we want to test max vector of the box
840//                 b=0,1,2 corresponds to the axis (0=x,1=y,2=z)
841// The sequence is ended by 15, number -1 is used as the separator
842// between the vertices and coordinates.
843const int
844AxisAlignedBox3::cvertices[27][9] =
845{                   // region number.. position
846  {0,15,15,15,15,15,15,15,15}, // 0 .. x=0 y=0 z=0 D one vertex
847  {0,1,-1,0,0,0,1,15,15},      // 1 .. x=0 y=0 z=1 D two vertices foll. by 2
848  {1,15,15,15,15,15,15,15,15}, // 2 .. x=0 y=0 z=2 D one vertex
849
850  {0,2,-1,0,0,0,2,15,15},      // 3 .. x=0 y=1 z=0 D
851  {0,1,3,2,-1,0,0,15,15},      // 4 .. x=0 y=1 z=1 D
852  {1,3,-1,0,0,1,2,15,15},      // 5 .. x=0 y=1 z=2 D
853
854  {2,15,15,15,15,15,15,15,15}, // 6 .. x=0 y=2 z=0 D
855  {2,3,-1,0,0,1,1,15,15},      // 7 .. x=0 y=2 z=1 D
856  {3,15,15,15,15,15,15,15,15}, // 8 .. x=0 y=2 z=2 D
857
858  // the regions number <9,17>
859  {0,4,-1,0,1,0,2,15,15},      // 9  .. x=1 y=0 z=0 D
860  {5,1,0,4,-1,0,1,15,15},      // 10 .. x=1 y=0 z=1 D
861  {1,5,-1,0,1,1,2,15,15},      // 11 .. x=1 y=0 z=2 D
862
863  {4,0,2,6,-1,0,2,15,15},      // 12 .. x=1 y=1 z=0 D
864  {0,2,3,1,5,4,6,7,15},        // 13 .. x=1 y=1 z=1 .. inside the box
865  {1,5,7,3,-1,1,2,15,15},      // 14 .. x=1 y=1 z=2 D
866
867  {6,2,-1,0,2,1,1,15,15},      // 15 .. x=1 y=2 z=0 D
868  {6,2,3,7,-1,1,1,15,15},      // 16 .. x=1 y=2 z=1 D
869  {3,7,-1,1,1,1,2,15,15},      // 17 .. x=1 y=2 z=2 D
870
871  // the regions number <18,26>
872  {4,15,15,15,15,15,15,15,15}, // 18 .. x=2 y=0 z=0 D
873  {4,5,-1,0,1,1,0,15,15},      // 19 .. x=2 y=0 z=1 D
874  {5,15,15,15,15,15,15,15,15}, // 20 .. x=2 y=0 z=2 D
875
876  {4,6,-1,0,2,1,0,15,15},      // 21 .. x=2 y=1 z=0 D
877  {5,4,6,7,-1,1,0,15,15},      // 22 .. x=2 y=1 z=1 D
878  {7,5,-1,1,0,1,2,15,15},      // 23 .. x=2 y=1 z=2 D
879
880  {6,15,15,15,15,15,15,15,15}, // 24 .. x=2 y=2 z=0 D
881  {6,7,-1,1,0,1,1,15,15},      // 25 .. x=2 y=2 z=1 D
882  {7,15,15,15,15,15,15,15,15}, // 26 .. x=2 y=2 z=2 D
883};
884
885// Table for Sphere-AABB intersection based on the region knowledge
886// Similar array to previous cvertices, but we omit the surfaces
887// which are not necessary for testing. First are vertices,
888// they are finished with -1. Second, there are indexes in
889// the pair (a,b), when a=0, we want to test min vector of the box,
890//                 when a=1, we want to test max vector of the box
891//                 b=0,1,2 corresponds to the axis (0=x,1=y,2=z)
892//
893// So either we check the vertices or only the distance in specified
894// dimensions. There are at all four possible cases:
895//
896//   1) we check one vertex - then sequence start with non-negative index
897//      and is finished with 15
898//   2) we check two coordinates of min/max vector describe by the pair
899//         (a,b) .. a=min/max(0/1) b=x/y/z (0/1/2), sequence starts with 8
900//      and finishes with 15
901//   3) we check only one coordinate of min/max, as for 2), sequence start
902//      with 9 and ends with 15
903//   4) Position 13 - sphere is inside the box, intersection always exist
904//        the sequence start with 15 .. no further testing is necessary
905//        in this case
906const int
907AxisAlignedBox3::csvertices[27][6] =
908{                   // region number.. position
909  {0,15,15,15,15,15},  // 0 .. x=0 y=0 z=0 D vertex only
910  {8,0,0,0,1,15},      // 1 .. x=0 y=0 z=1 D two coords.
911  {1,15,15,15,15,15},  // 2 .. x=0 y=0 z=2 D vertex only
912
913  {8,0,0,0,2,15},      // 3 .. x=0 y=1 z=0 D two coords
914  {9,0,0,15,15,15},    // 4 .. x=0 y=1 z=1 D one coord
915  {8,0,0,1,2,15},      // 5 .. x=0 y=1 z=2 D two coords.
916
917  {2,15,15,15,15,15},  // 6 .. x=0 y=2 z=0 D one vertex
918  {8,0,0,1,1,15},      // 7 .. x=0 y=2 z=1 D two coords
919  {3,15,15,15,15,15},  // 8 .. x=0 y=2 z=2 D one vertex
920
921  // the regions number <9,17>
922  {8,0,1,0,2,15},      // 9  .. x=1 y=0 z=0 D two coords
923  {9,0,1,15,15,15},    // 10 .. x=1 y=0 z=1 D one coord
924  {8,0,1,1,2,15},      // 11 .. x=1 y=0 z=2 D two coords
925
926  {9,0,2,15,15,15},    // 12 .. x=1 y=1 z=0 D one coord
927  {15,15,15,15,15,15}, // 13 .. x=1 y=1 z=1 inside the box, special case/value
928  {9,1,2,15,15,15},    // 14 .. x=1 y=1 z=2 D one corrd
929
930  {8,0,2,1,1,15},      // 15 .. x=1 y=2 z=0 D two coords
931  {9,1,1,15,15},       // 16 .. x=1 y=2 z=1 D one coord
932  {8,1,1,1,2,15},      // 17 .. x=1 y=2 z=2 D two coords
933
934  // the regions number <18,26>
935  {4,15,15,15,15,15},  // 18 .. x=2 y=0 z=0 D one vertex
936  {8,0,1,1,0,15},      // 19 .. x=2 y=0 z=1 D two coords
937  {5,15,15,15,15,15},  // 20 .. x=2 y=0 z=2 D one vertex
938
939  {8,0,2,1,0,15},      // 21 .. x=2 y=1 z=0 D two coords
940  {9,1,0,15,15,15},    // 22 .. x=2 y=1 z=1 D one coord
941  {8,1,0,1,2,15},      // 23 .. x=2 y=1 z=2 D two coords
942
943  {6,15,15,15,15,15},  // 24 .. x=2 y=2 z=0 D one vertex
944  {8,1,0,1,1,15},      // 25 .. x=2 y=2 z=1 D two coords
945  {7,15,15,15,15,15},  // 26 .. x=2 y=2 z=2 D one vertex
946};
947
948
949// The vertices that form all FARTHEST points with respect to the region
950// for all the regions possible, number of regions is 3^3 = 27,
951// since two parallel sides of bbox forms three disjoint spaces.
952// The vertices are given in anti-clockwise order, stopped by value 15,
953// at most 8 points, at least 1 point.
954// For testing, if the AABB is whole in the sphere, it is enough
955// to test only vertices, either 1,2,4, or 8.
956const int
957AxisAlignedBox3::fvertices[27][9] =
958{                   // region number.. position
959  {7,15,15,15,15,15,15,15,15}, // 0 .. x=0 y=0 z=0 D
960  {6,7,15,15,15,15,15,15,15},  // 1 .. x=0 y=0 z=1 D
961  {6,15,15,15,15,15,15,15,15}, // 2 .. x=0 y=0 z=2 D
962
963  {5,7,15,15,15,15,15,15,15},  // 3 .. x=0 y=1 z=0 D
964  {4,5,7,6,15,15,15,15,15},    // 4 .. x=0 y=1 z=1 D
965  {4,6,15,15,15,15,15,15,15},  // 5 .. x=0 y=1 z=2 D
966
967  {5,15,15,15,15,15,15,15,15}, // 6 .. x=0 y=2 z=0 D
968  {4,5,15,15,15,15,15,15,15},  // 7 .. x=0 y=2 z=1 D
969  {4,15,15,15,15,15,15,15,15}, // 8 .. x=0 y=2 z=2 D
970
971  // the regions number <9,17>
972  {3,7,15,15,15,15,15,15,15},  // 9  .. x=1 y=0 z=0 D
973  {7,3,2,6,15,15,15,15,15},    // 10 .. x=1 y=0 z=1 D
974  {2,6,15,15,15,15,15,15,15},  // 11 .. x=1 y=0 z=2 D
975
976  {5,1,3,7,15,15,15,15,15},    // 12 .. x=1 y=1 z=0 D
977  {0,7,1,6,3,4,5,2,15},        // 13 .. x=1 y=1 z=1 .. inside the box
978  {0,4,6,2,15,15,15,15,15},    // 14 .. x=1 y=1 z=2 D
979
980  {5,1,15,15,15,15,15,15,15},  // 15 .. x=1 y=2 z=0 D
981  {4,0,1,5,15,15,15,15,15},    // 16 .. x=1 y=2 z=1 D
982  {4,0,15,15,15,15,15,15,15},  // 17 .. x=1 y=2 z=2 D
983
984  // the regions number <18,26>
985  {3,15,15,15,15,15,15,15,15}, // 18 .. x=2 y=0 z=0 D
986  {2,3,15,15,15,15,15,15,15},  // 19 .. x=2 y=0 z=1 D
987  {2,15,15,15,15,15,15,15,15}, // 20 .. x=2 y=0 z=2 D
988
989  {1,3,15,15,15,15,15,15,15},  // 21 .. x=2 y=1 z=0 D
990  {1,0,2,3,15,15,15,15,15},    // 22 .. x=2 y=1 z=1 D
991  {2,0,15,15,15,15,15,15,15},  // 23 .. x=2 y=1 z=2 D
992
993  {1,15,15,15,15,15,15,15,15}, // 24 .. x=2 y=2 z=0 D
994  {0,1,15,15,15,15,15,15,15},  // 25 .. x=2 y=2 z=1 D
995  {0,15,15,15,15,15,15,15,15}, // 26 .. x=2 y=2 z=2 D
996};
997
998// Similar table as above, farthest points, but only the ones
999// necessary for testing the intersection problem. If we do
1000// not consider the case 13, center of the sphere is inside the
1001// box, then we can always test at most 2 box vertices to say whether
1002// the whole box is inside the sphere.
1003// The number of vertices is minimized using some assumptions
1004// about the ortogonality of vertices and sphere properties.
1005const int
1006AxisAlignedBox3::fsvertices[27][9] =
1007{                   // region number.. position
1008  {7,15,15,15,15,15,15,15,15}, // 0 .. x=0 y=0 z=0 D 1 vertex
1009  {6,7,15,15,15,15,15,15,15},  // 1 .. x=0 y=0 z=1 D 2 vertices
1010  {6,15,15,15,15,15,15,15,15}, // 2 .. x=0 y=0 z=2 D 1 vertex
1011
1012  {5,7,15,15,15,15,15,15,15},  // 3 .. x=0 y=1 z=0 D 2 vertices
1013  {4,7,15,5,6,15,15,15,15},    // 4 .. x=0 y=1 z=1 D 4/2 vertices
1014  {4,6,15,15,15,15,15,15,15},  // 5 .. x=0 y=1 z=2 D 2 vertices
1015
1016  {5,15,15,15,15,15,15,15,15}, // 6 .. x=0 y=2 z=0 D 1 vertex
1017  {4,5,15,15,15,15,15,15,15},  // 7 .. x=0 y=2 z=1 D 2 vertices
1018  {4,15,15,15,15,15,15,15,15}, // 8 .. x=0 y=2 z=2 D 1 vertex
1019
1020  // the regions number <9,17>
1021  {3,7,15,15,15,15,15,15,15},  // 9  .. x=1 y=0 z=0 D 2 vertices
1022  {7,2,15,3,6,15,15,15,15},    // 10 .. x=1 y=0 z=1 D 4/2 vertices
1023  {2,6,15,15,15,15,15,15,15},  // 11 .. x=1 y=0 z=2 D 2 vertices
1024
1025  {5,3,15,1,7,15,15,15,15},    // 12 .. x=1 y=1 z=0 D 4/2 vertices
1026  {0,7,1,6,3,4,5,2,15},        // 13 .. x=1 y=1 z=1 .. inside the box
1027  {0,6,15,4,2,15,15,15,15},    // 14 .. x=1 y=1 z=2 D 4/2 vertices
1028
1029  {5,1,15,15,15,15,15,15,15},  // 15 .. x=1 y=2 z=0 D 2 vertices
1030  {4,1,15,0,5,15,15,15,15},    // 16 .. x=1 y=2 z=1 D 4/2 vertices
1031  {4,0,15,15,15,15,15,15,15},  // 17 .. x=1 y=2 z=2 D 2 vertices
1032
1033  // the regions number <18,26>
1034  {3,15,15,15,15,15,15,15,15}, // 18 .. x=2 y=0 z=0 D 1 vertex
1035  {2,3,15,15,15,15,15,15,15},  // 19 .. x=2 y=0 z=1 D 2 vertices
1036  {2,15,15,15,15,15,15,15,15}, // 20 .. x=2 y=0 z=2 D 1 vertex
1037
1038  {1,3,15,15,15,15,15,15,15},  // 21 .. x=2 y=1 z=0 D 2 vertices
1039  {1,2,15,0,3,15,15,15,15},    // 22 .. x=2 y=1 z=1 D 4/2 vertices
1040  {2,0,15,15,15,15,15,15,15},  // 23 .. x=2 y=1 z=2 D 2 vertices
1041
1042  {1,15,15,15,15,15,15,15,15}, // 24 .. x=2 y=2 z=0 D 1 vertex
1043  {0,1,15,15,15,15,15,15,15},  // 25 .. x=2 y=2 z=1 D 2 vertices
1044  {0,15,15,15,15,15,15,15,15}, // 26 .. x=2 y=2 z=2 D 1 vertex
1045};
1046
1047
1048// The fast computation of arctangent .. the maximal error is less
1049// than 4.1 degrees, according to Graphics GEMSII, 1991, pages 389--391
1050// Ron Capelli: "Fast approximation to the arctangent"
1051float
1052atan22(const float& y)
1053{
1054  const float x = 1.0;
1055  const float c = (float)(M_PI * 0.25);
1056 
1057  if (y < 0.0) {
1058    if (y < -1.0)
1059      return c * (-2.0f + x / y); // for angle in <-PI/2, -PI/4)
1060    else
1061      return c * (y / x); // for angle in <-PI/4 , 0>
1062  }
1063  else {
1064    if (y > 1.0)
1065      return c * (2.0f - x / y); // for angle in <PI/4, PI/2>
1066    else
1067      return c * (y / x); // for angle in <0, PI/2>
1068  }
1069}
1070
1071
1072float
1073AxisAlignedBox3::ProjectToSphereSA(const Vector3 &viewpoint, int *tcase) const
1074{
1075  int id = GetRegionID(viewpoint);
1076  *tcase = id;
1077
1078  // spherical projection .. SA represents solid angle
1079  if (id == 13) // .. inside the box
1080    return (float)(4.0*M_PI); // the whole sphere
1081  float SA = 0.0; // inital value
1082   
1083  int i = 0; // the pointer in the array of vertices
1084  while (bfaces[id][i] >= 0) {
1085    int axisO = bfaces[id][i++];
1086    int minvIdx = bfaces[id][i++];
1087    int maxvIdx = bfaces[id][i++];
1088    Vector3 vmin, vmax;
1089    GetVertex(minvIdx, vmin);
1090    GetVertex(maxvIdx, vmax);
1091    float h = fabs(vmin[axisO] - viewpoint[axisO]);
1092    int axis = (axisO + 1) % 3; // next axis
1093    float a = (vmin[axis] - viewpoint[axis]) / h; // minimum for v-range
1094    float b = (vmax[axis] - viewpoint[axis]) / h; // maximum for v-range
1095    //if (a > b) {
1096    //  FATAL << "ProjectToSphereSA::Error a > b\n";
1097    //  FATAL_ABORT;
1098    //}
1099    //if (vmin[axisO] != vmax[axisO]) {
1100    //  FATAL << "ProjectToSphereSA::Error a-axis != b-axis\n";
1101    //  FATAL_ABORT;     
1102    //}
1103    axis = (axisO + 2) % 3; // next second axis       
1104    float c = (vmin[axis] - viewpoint[axis]) / h; // minimum for u-range
1105    float d = (vmax[axis] - viewpoint[axis]) / h; // maximum for u-range
1106    //if (c > d) {
1107    //  FATAL << "ProjectToSphereSA::Error c > d\n";
1108    //  FATAL_ABORT;
1109    //}
1110    SA +=atan22(d*b/sqrt(b*b + d*d + 1.0f)) - atan22(b*c/sqrt(b*b + c*c + 1.0f))
1111      - atan22(d*a/sqrt(a*a + d*d + 1.0f)) + atan22(a*c/sqrt(a*a + c*c + 1.0f));
1112  }
1113
1114#if 0
1115  if ((SA > 2.0*M_PI) ||
1116      (SA < 0.0)) {
1117    FATAL << "The solid angle has strange value: ";
1118    FATAL << "SA = "<< SA << endl;
1119    FATAL_ABORT;
1120  }
1121#endif
1122 
1123  return SA;
1124}
1125
1126// Projects the box to a plane given a normal vector only and
1127// computes the surface area of the projected silhouette
1128// no clipping of the box is performed.
1129float
1130AxisAlignedBox3::ProjectToPlaneSA(const Vector3 &normal) const
1131{
1132  Vector3 size = Size();
1133
1134  // the surface area of the box to a yz-plane - perpendicular to x-axis
1135  float sax = size.y * size.z;
1136
1137  // the surface area of the box to a zx-plane - perpendicular to y-axis
1138  float say = size.z * size.x;
1139
1140  // the surface area of the box to a xy-plane - perpendicular to z-axis
1141  float saz = size.x * size.y;
1142 
1143  return sax * fabs(normal.x) + say * fabs(normal.y) + saz * fabs(normal.z);
1144}
1145
1146
1147
1148// This definition allows to be a point when answering true
1149bool
1150AxisAlignedBox3::IsCorrectAndNotPoint() const
1151{
1152  if ( (mMin.x > mMax.x) ||
1153       (mMin.y > mMax.y) ||
1154       (mMin.z > mMax.z) )
1155    return false; // box is not formed
1156
1157  if ( (mMin.x == mMax.x) &&
1158       (mMin.y == mMax.y) &&
1159       (mMin.z == mMax.z) )
1160    return false; // degenerates to a point
1161 
1162  return true;
1163}
1164
1165// This definition allows to be a point when answering true
1166bool
1167AxisAlignedBox3::IsPoint() const
1168{
1169  if ( (mMin.x == mMax.x) &&
1170       (mMin.y == mMax.y) &&
1171       (mMin.z == mMax.z) )
1172    return true; // degenerates to a point
1173 
1174  return false;
1175}
1176
1177// This definition requires shape of non-zero volume
1178bool
1179AxisAlignedBox3::IsSingularOrIncorrect() const
1180{
1181  if ( (mMin.x >= mMax.x) ||
1182       (mMin.y >= mMax.y) ||
1183       (mMin.z >= mMax.z) )
1184    return true; // box is not formed
1185
1186  return false; // has non-zero volume
1187}
1188
1189// returns true, when the sphere specified by the origin and radius
1190// fully contains the box
1191bool
1192AxisAlignedBox3::IsFullyContainedInSphere(const Vector3 &center, float rad) const
1193{
1194  int region = GetRegionID(center);
1195  float rad2 = rad*rad;
1196
1197  // vertex of the box
1198  Vector3 vertex;
1199
1200  int i = 0;
1201  for (i = 0 ; ; i++) {
1202    int a = fsvertices[region][i];
1203    if (a == 15)
1204      return true; // if was not false untill now, it must be contained
1205
1206    assert( (a>=0) && (a<8) );
1207   
1208    // normal vertex
1209    GetVertex(a, vertex);
1210
1211    if (SqrMagnitude(vertex - center) > rad2)
1212      return false;   
1213  } // for
1214 
1215}
1216
1217// returns true, when the volume of the sphere and volume of the
1218// axis aligned box has no intersection
1219bool
1220AxisAlignedBox3::HasNoIntersectionWithSphere(const Vector3 &center, float rad) const
1221{
1222  int region = GetRegionID(center);
1223  float rad2 = rad*rad;
1224
1225  // vertex of the box
1226  Vector3 vertex;
1227
1228  switch (csvertices[region][0]) {
1229  case 8: {
1230    // test two coordinates described within the field
1231    int face = 3*csvertices[region][1] + csvertices[region][2];
1232    float dist = GetExtent(face) - center[csvertices[region][2]];
1233    dist *= dist;
1234    face = 3 * (csvertices[region][3]) + csvertices[region][4];
1235    float dist2 = GetExtent(face) - center[csvertices[region][4]];
1236    dist += (dist2 * dist2);
1237    if (dist > rad2)
1238      return true; // no intersection is possible
1239  }
1240  case 9: {
1241    // test one coordinate described within the field
1242    int face = 3*csvertices[region][1] + csvertices[region][2];
1243    float dist = fabs(GetExtent(face) - center[csvertices[region][2]]);
1244    if (dist > rad)
1245      return true; // no intersection is possible
1246  }
1247  case 15:
1248    return false; // box and sphere surely has intersection
1249  default: {
1250    // test using normal vertices
1251    assert( (csvertices[region][0]>=0) && (csvertices[region][0]<8) );
1252
1253    // normal vertex
1254    GetVertex(csvertices[region][0], vertex);
1255
1256    if (SqrMagnitude(vertex - center) > rad2)
1257      return true; // no intersectino is possible   
1258    }
1259  } // switch
1260
1261  return false; // partial or full containtment
1262}
1263
1264#if 0
1265// Given the sphere, determine the mutual position between the
1266// sphere and box
1267
1268// SOME BUG IS INSIDE !!!! V.H. 25/4/2001
1269int
1270AxisAlignedBox3::MutualPositionWithSphere(const Vector3 &center, float rad) const
1271{
1272  int region = GetRegionID(center);
1273  float rad2 = rad*rad;
1274
1275  // vertex of the box
1276  Vector3 vertex;
1277
1278  // first testing for  full containtment - whether sphere fully
1279  // contains the box
1280  int countInside = 0; // how many points were found inside
1281 
1282  int i = 0;
1283  for (i = 0 ; ; i++) {
1284    int a = fsvertices[region][i];
1285    if (a == 15)
1286      return 1; // the sphere fully contain the box
1287
1288    assert( (a>=0) && (a<8) );
1289   
1290    // normal vertex
1291    GetVertex(a, vertex);
1292
1293    if (SqrMagnitude(vertex - center) <= rad2)
1294      countInside++; // the number of vertices inside the sphere
1295    else {
1296      if (countInside)
1297        return 0; // partiall overlap has been found
1298      // the sphere does not fully contain the box .. only way to break
1299      // this loop and go for other testing
1300      break;
1301    }
1302  } // for
1303
1304  // now only box and sphere can partially overlap or no intersection
1305  switch (csvertices[region][0]) {
1306  case 8: {
1307    // test two coordinates described within the field
1308    int face = 3*csvertices[region][1] + csvertices[region][2];
1309    float dist = GetExtent(face) - center[csvertices[region][2]];
1310    dist *= dist;
1311    face = 3 * (csvertices[region][3]) + csvertices[region][4];
1312    float dist2 = GetExtent(face) - center[csvertices[region][4]];
1313    dist += (dist2 * dist2);
1314    if (dist > rad2 )
1315      return -1; // no intersection is possible
1316  }
1317  case 9: {
1318    // test one coordinate described within the field
1319    int face = 3*csvertices[region][1] + csvertices[region][2];
1320    float dist = fabs(GetExtent(face) - center[csvertices[region][2]]);
1321    if (dist > rad)
1322      return -1; // no intersection is possible
1323  }
1324  case 15:
1325    return 0 ; // partial overlap is now guaranteed
1326  default: {
1327    // test using normal vertices
1328    assert( (csvertices[region][0]>=0) && (csvertices[region][0]<8) );
1329   
1330    // normal vertex
1331    GetVertex(csvertices[region][0], vertex);
1332
1333    if (SqrMagnitude(vertex - center) > rad2)
1334      return -1; // no intersection is possible   
1335    }
1336  } // switch
1337
1338  return 0; // partial intersection is guaranteed
1339}
1340#else
1341
1342// Some maybe smarter version, extendible easily to d-dimensional
1343// space!
1344// Given a sphere described by the center and radius,
1345// the fullowing function returns:
1346//   -1 ... the sphere and the box are completely separate
1347//    0 ... the sphere and the box only partially overlap
1348//    1 ... the sphere contains fully the box
1349//  Note: the case when box fully contains the sphere is not reported
1350//        since it was not required.
1351int
1352AxisAlignedBox3::MutualPositionWithSphere(const Vector3 &center, float rad) const
1353{
1354//#define SPEED_UP
1355
1356#ifndef SPEED_UP
1357  // slow version, instructively written 
1358#if 0
1359  // does it make sense to test
1360  // checking the sides of the box for possible non-intersection
1361  if ( ((center.x + rad) < mMin.x) ||
1362       ((center.x - rad) > mMax.x) ||
1363       ((center.y + rad) < mMin.y) ||
1364       ((center.y - rad) > mMax.y) ||
1365       ((center.z + rad) < mMin.z) ||
1366       ((center.z - rad) > mMax.z) ) {
1367    // cout << "r ";
1368    return -1;  // no overlap is possible
1369  }
1370#endif
1371 
1372  // someoverlap is possible, check the distance of vertices
1373  rad = rad*rad;
1374  float sumMin = 0;
1375  // Try to minimize the function of a distance
1376  // from the sphere center
1377
1378  // for x-axis
1379  float minSqrX = sqr(mMin.x - center.x);
1380  float maxSqrX = sqr(mMax.x - center.x);
1381  if (center.x < mMin.x)
1382    sumMin = minSqrX;
1383  else
1384    if (center.x > mMax.x)
1385      sumMin = maxSqrX;
1386
1387  // for y-axis
1388  float minSqrY = sqr(mMin.y - center.y);
1389  float maxSqrY = sqr(mMax.y - center.y);
1390  if (center.y < mMin.y)
1391    sumMin += minSqrY;
1392  else
1393    if (center.y > mMax.y)
1394      sumMin += maxSqrY;
1395
1396  // for z-axis
1397  float minSqrZ = sqr(mMin.z - center.z);
1398  float maxSqrZ = sqr(mMax.z - center.z);
1399  if (center.z < mMin.z)
1400    sumMin += minSqrZ;
1401  else
1402    if (center.z > mMax.z)
1403      sumMin += maxSqrZ;
1404
1405  if (sumMin > rad)
1406    return -1; // no intersection between sphere and box
1407
1408  // try to find out the maximum distance between the
1409  // sphere center and vertices
1410  float sumMax = 0;
1411 
1412  if (minSqrX > maxSqrX)
1413    sumMax = minSqrX;
1414  else
1415    sumMax = maxSqrX;
1416 
1417  if (minSqrY > maxSqrY)
1418    sumMax += minSqrY;
1419  else
1420    sumMax += maxSqrY;
1421 
1422  if (minSqrZ > maxSqrZ)
1423    sumMax += minSqrZ;
1424  else
1425    sumMax += maxSqrZ;
1426 
1427  // sumMin < rad
1428  if (sumMax < rad)
1429    return 1; // the sphere contains the box completely
1430
1431  // partial intersection, part of the box is outside the sphere
1432  return 0;
1433#else
1434
1435  // Optimized version of the test
1436 
1437#ifndef __VECTOR_HACK
1438#error "__VECTOR_HACK for Vector3 was not defined"
1439#endif
1440
1441  // some overlap is possible, check the distance of vertices
1442  rad = rad*rad;
1443  float sumMin = 0;
1444  float sumMax = 0;
1445  // Try to minimize the function of a distance
1446  // from the sphere center
1447
1448  const float *minp = &(min[0]);
1449  const float *maxp = &(max[0]);
1450  const float *pcenter = &(center[0]);
1451 
1452  // for x-axis
1453  for (int i = 0; i < 3; i++, minp++, maxp++, pcenter++) {
1454    float minsqr = sqr(*minp - *pcenter);
1455    float maxsqr = sqr(*maxp - *pcenter);
1456    if (*pcenter < *minp)
1457      sumMin += minsqr;
1458    else
1459      if (*pcenter > *maxp)
1460        sumMin += maxsqr;
1461    sumMax += (minsqr > maxsqr) ? minsqr : maxsqr;
1462  }
1463
1464  if (sumMin > rad)
1465    return -1; // no intersection between sphere and box
1466
1467  // sumMin < rad
1468  if (sumMax < rad)
1469    return 1; // the sphere contains the box completely
1470
1471  // partial intersection, part of the box is outside the sphere
1472  return 0;
1473#endif
1474}
1475#endif
1476
1477// Given the cube describe by the center and the half-sie,
1478// determine the mutual position between the cube and the box
1479int
1480AxisAlignedBox3::MutualPositionWithCube(const Vector3 &center, float radius) const
1481{
1482  // the cube is described by the center and the distance to the any face
1483  // along the axes
1484
1485  // Note on efficiency!
1486  // Can be quite optimized using tables, but I do not have time
1487  // V.H. 18/11/2001
1488
1489  AxisAlignedBox3 a =
1490    AxisAlignedBox3(Vector3(center.x - radius, center.y - radius, center.z - radius),
1491           Vector3(center.x + radius, center.y + radius, center.z + radius));
1492
1493  if (a.Includes(*this))
1494    return 1; // cube contains the box
1495
1496  if (OverlapS(a,*this))
1497    return 0; // cube partially overlap the box
1498
1499  return -1; // completely separate 
1500}
1501
1502void
1503AxisAlignedBox3::GetSqrDistances(const Vector3 &point,
1504                                 float &minDistance,
1505                                 float &maxDistance
1506                                 ) const
1507{
1508
1509 
1510#ifndef __VECTOR_HACK
1511#error "__VECTOR_HACK for Vector3 was not defined"
1512#endif
1513
1514  // some overlap is possible, check the distance of vertices
1515  float sumMin = 0;
1516  float sumMax = 0;
1517
1518  // Try to minimize the function of a distance
1519  // from the sphere center
1520
1521  const float *minp = &(mMin[0]);
1522  const float *maxp = &(mMax[0]);
1523  const float *pcenter = &(point[0]);
1524 
1525  // for x-axis
1526  for (int i = 0; i < 3; i++, minp++, maxp++, pcenter++) {
1527    float minsqr = sqr(*minp - *pcenter);
1528    float maxsqr = sqr(*maxp - *pcenter);
1529    if (*pcenter < *minp)
1530      sumMin += minsqr;
1531    else
1532      if (*pcenter > *maxp)
1533        sumMin += maxsqr;
1534    sumMax += (minsqr > maxsqr) ? minsqr : maxsqr;
1535  }
1536
1537  minDistance = sumMin;
1538  maxDistance = sumMax;
1539}
1540
1541
1542int
1543AxisAlignedBox3::Side(const Plane3 &plane) const
1544{
1545  Vector3 v;
1546  int i, m=3, M=-3, s;
1547 
1548  for (i=0;i<8;i++) {
1549    GetVertex(i, v);
1550    if((s = plane.Side(v)) < m)
1551      m=s;
1552    if(s > M)
1553      M=s;
1554    if (m && m==-M)
1555      return 0;
1556  }
1557 
1558  return (m == M) ? m : m + M;
1559}
1560
1561int
1562AxisAlignedBox3::GetFaceVisibilityMask(const Rectangle3 &rectangle) const
1563{
1564  int mask = 0;
1565  for (int i=0; i < 4; i++)
1566    mask |= GetFaceVisibilityMask(rectangle.mVertices[i]);
1567  return mask;
1568}
1569
1570int
1571AxisAlignedBox3::GetFaceVisibilityMask(const Vector3 &position) const {
1572 
1573  // assume that we are not inside the box
1574  int c=0;
1575 
1576  if (position.x<(mMin.x-Limits::Small))
1577    c|=1;
1578  else
1579    if (position.x>(mMax.x+Limits::Small))
1580      c|=2;
1581 
1582  if (position.y<(mMin.y-Limits::Small))
1583    c|=4;
1584  else
1585    if (position.y>(mMax.y+Limits::Small))
1586      c|=8;
1587 
1588  if (position.z<(mMin.z-Limits::Small))
1589    c|=16;
1590  else
1591    if (position.z>(mMax.z+Limits::Small))
1592      c|=32;
1593 
1594  return c;
1595}
1596
1597
1598Rectangle3
1599AxisAlignedBox3::GetFace(const int face) const
1600{
1601  Vector3 v[4];
1602  switch (face) {
1603   
1604  case 0:
1605    v[3].SetValue(mMin.x,mMin.y,mMin.z);
1606    v[2].SetValue(mMin.x,mMax.y,mMin.z);
1607    v[1].SetValue(mMin.x,mMax.y,mMax.z);
1608    v[0].SetValue(mMin.x,mMin.y,mMax.z);
1609    break;
1610   
1611  case 1:
1612    v[0].SetValue(mMax.x,mMin.y,mMin.z);
1613    v[1].SetValue(mMax.x,mMax.y,mMin.z);
1614    v[2].SetValue(mMax.x,mMax.y,mMax.z);
1615    v[3].SetValue(mMax.x,mMin.y,mMax.z);
1616    break;
1617   
1618  case 2:
1619    v[3].SetValue(mMin.x,mMin.y,mMin.z);
1620    v[2].SetValue(mMin.x,mMin.y,mMax.z);
1621    v[1].SetValue(mMax.x,mMin.y,mMax.z);
1622    v[0].SetValue(mMax.x,mMin.y,mMin.z);
1623    break;
1624 
1625  case 3:
1626    v[0].SetValue(mMin.x,mMax.y,mMin.z);
1627    v[1].SetValue(mMin.x,mMax.y,mMax.z);
1628    v[2].SetValue(mMax.x,mMax.y,mMax.z);
1629    v[3].SetValue(mMax.x,mMax.y,mMin.z);
1630    break;
1631
1632  case 4:
1633    v[3].SetValue(mMin.x,mMin.y,mMin.z);
1634    v[2].SetValue(mMax.x,mMin.y,mMin.z);
1635    v[1].SetValue(mMax.x,mMax.y,mMin.z);
1636    v[0].SetValue(mMin.x,mMax.y,mMin.z);
1637    break;
1638 
1639  case 5:
1640    v[0].SetValue(mMin.x,mMin.y,mMax.z);
1641    v[1].SetValue(mMax.x,mMin.y,mMax.z);
1642    v[2].SetValue(mMax.x,mMax.y,mMax.z);
1643    v[3].SetValue(mMin.x,mMax.y,mMax.z);
1644    break;
1645  }
1646 
1647  return Rectangle3(v[0], v[1], v[2], v[3]);
1648}
1649
1650struct VertexData
1651{
1652        Vector3 mVertex;
1653        float mAngle;
1654       
1655        VertexData(Vector3 vtx, float angle): mVertex(vtx), mAngle(angle)
1656        {}
1657
1658        bool operator<(const VertexData &b) const
1659        {
1660                return mAngle > b.mAngle;
1661        }
1662};
1663
1664// TODO: use a table to avoid normal and distance computations
1665Polygon3 *AxisAlignedBox3::CrossSection(const Plane3 &plane) const
1666{
1667        Polygon3 *planePoly = new Polygon3();
1668       
1669        int side[8];
1670        bool onFrontSide = false, onBackSide = false;
1671       
1672        Vector3 vtx;
1673        //-- compute classification of vertices
1674        for (int i = 0; i < 8; ++i)
1675        {
1676                GetVertex(i, vtx);
1677                side[i] = plane.Side(vtx);
1678                if (side[i] > 0)
1679                        onFrontSide = true;
1680                else if (side[i] < 0)
1681                        onBackSide = true;
1682                else // vertex coincident => push_back
1683                        planePoly->mVertices.push_back(vtx);
1684        }
1685
1686        //-- find intersections
1687        if (onFrontSide && onBackSide)
1688        {
1689                Vector3 ptA, ptB;
1690                for (int i = 0; i < 12; ++ i)
1691                {
1692                        int aIdx, bIdx;
1693                        GetEdge(i, aIdx, bIdx);
1694
1695                        ptA = GetVertex(aIdx);
1696                        ptB = GetVertex(bIdx);
1697
1698                        int sideA = side[aIdx];
1699                        int sideB = side[bIdx];
1700
1701                        if (((sideA > 0) && (sideB < 0)) || (sideA < 0) && (sideB > 0))
1702                                planePoly->mVertices.push_back(plane.FindIntersection(ptA, ptB));       
1703                }
1704        }
1705
1706        // order intersectioins
1707        if (planePoly->mVertices.size() > 3)
1708        {
1709                Vector3 centerOfMass(0);
1710                int i;
1711                // compute center of mass
1712                for (i = 0; i < (int)planePoly->mVertices.size(); ++ i)
1713                        centerOfMass += planePoly->mVertices[i];
1714               
1715                centerOfMass /= (float)planePoly->mVertices.size();
1716
1717                vector<VertexData> vertexData;
1718               
1719                Vector3 refVec = Normalize(centerOfMass - planePoly->mVertices[0]);
1720
1721                // compute angle to reference point
1722                for (i = 1; i < (int)planePoly->mVertices.size(); ++ i)
1723                  {
1724                    float angle =
1725                      Angle(refVec, centerOfMass - planePoly->mVertices[i], plane.mNormal);
1726                   
1727                    vertexData.push_back(VertexData(planePoly->mVertices[i], angle));
1728                  }
1729               
1730                std::stable_sort(vertexData.begin(), vertexData.end());
1731
1732                // update vertices
1733                for (i = 1; i < (int)planePoly->mVertices.size(); ++ i)
1734                        planePoly->mVertices[i] = vertexData[i - 1].mVertex;
1735        }
1736        else if (planePoly->mVertices.size() == 3)
1737        {
1738                // fix orientation if needed
1739                if (DotProd(planePoly->GetNormal(), plane.mNormal) < 0)
1740                {
1741                        Vector3 v = planePoly->mVertices[1];
1742                        planePoly->mVertices[1] = planePoly->mVertices[2];
1743                        planePoly->mVertices[2] = v;
1744                }
1745        }
1746       
1747        return planePoly;
1748}
1749
1750bool AxisAlignedBox3::GetRaySegment(const Ray &ray,
1751                                                                        float &minT,
1752                                                                        float &maxT) const
1753{
1754        maxT = 1e6;
1755        minT = 0;
1756       
1757        // test with  bounding box
1758        if (!GetMinMaxT(ray, &minT, &maxT))
1759                return false;
1760
1761        if (minT < 0) // start ray from origin
1762                minT = 0;
1763
1764        // bound ray or line segment
1765        if (//(ray.GetType() == Ray::LOCAL_RAY) &&
1766            !ray.intersections.empty() &&
1767                (ray.intersections[0].mT <= maxT))
1768        {
1769                maxT = ray.intersections[0].mT;
1770        }
1771
1772        return true;
1773}
1774
1775
1776  // Compute tmin and tmax for a ray, whenever required .. need not pierce box
1777int
1778AxisAlignedBox3::ComputeMinMaxT(const Vector3 &origin,
1779                                                                const Vector3 &direction,
1780                                                                float *tmin,
1781                                                                float *tmax) const
1782{
1783
1784  register float minx, maxx;
1785
1786 
1787  Vector3 invDirection;
1788  const float eps = 1e-6;
1789  const float invEps = 1e6;
1790 
1791  // it does change the ray direction very slightly,
1792  // but the size direction vector is not practically changed
1793 
1794  if (fabs(direction.x) < eps) {
1795    if (direction.x < 0.0)
1796      invDirection.x = -invEps;
1797    else
1798      invDirection.x = invEps;
1799  }
1800  else
1801    invDirection.x = 1.0 / direction.x;
1802 
1803  if (fabs(direction.y) < eps) {
1804    if (direction.y < 0.0)
1805      invDirection.y = -invEps;
1806    else
1807      invDirection.y = invEps;
1808  }
1809  else
1810    invDirection.y = 1.0 / direction.y;
1811 
1812  if (fabs(direction.z) < eps) {
1813    if (direction.z < 0.0)
1814      invDirection.z = -invEps;
1815    else
1816      invDirection.z = invEps;
1817  }
1818  else
1819    invDirection.z = 1.0 / direction.z;
1820
1821
1822 
1823  if (fabs(direction.x) < 0.001) {
1824    if (mMin.x < origin.x && mMax.x > origin.x) {
1825      minx = -MAXFLOAT;
1826      maxx = MAXFLOAT;
1827    }
1828    else
1829      return 0;
1830  }
1831  else {
1832    float t1 = (mMin.x - origin.x) * invDirection.x;
1833    float t2 = (mMax.x - origin.x) * invDirection.x;
1834    if (t1 < t2) {
1835      minx = t1;
1836      maxx = t2;
1837    }
1838    else {
1839      minx = t2;
1840      maxx = t1;
1841    }
1842        //    if (maxx < 0.0)
1843        //      return 0;
1844  }
1845
1846  *tmin = minx;
1847  *tmax = maxx;
1848 
1849  if (fabs(direction.y) < 0.001) {
1850    if (mMin.y < origin.y && mMax.y > origin.y) {
1851      minx = -MAXFLOAT;
1852      maxx = MAXFLOAT;
1853    }
1854    else
1855      return 0;
1856  }
1857  else {
1858    float t1 = (mMin.y - origin.y) * invDirection.y;
1859    float t2 = (mMax.y - origin.y) * invDirection.y;
1860    if (t1 < t2) {
1861      minx = t1;
1862      maxx = t2;
1863    }
1864    else {
1865      minx = t2;
1866      maxx = t1;
1867    }
1868        //    if (maxx < 0.0)
1869        //      return 0;
1870  }
1871
1872  if (minx > *tmin)
1873    *tmin = minx;
1874  if (maxx < *tmax)
1875    *tmax = maxx;
1876 
1877  if (fabs(direction.z) < 0.001) {
1878    if (mMin.z < origin.z && mMax.z > origin.z) {
1879      minx = -MAXFLOAT;
1880      maxx = MAXFLOAT;
1881    }
1882    else
1883      return 0;
1884  }
1885  else {
1886    float t1 = (mMin.z - origin.z) * invDirection.z;
1887    float t2 = (mMax.z - origin.z) * invDirection.z;
1888    if (t1 < t2) {
1889      minx = t1;
1890      maxx = t2;
1891    }
1892    else {
1893      minx = t2;
1894      maxx = t1;
1895    }
1896        //    if (maxx < 0.0)
1897        //      return 0;
1898  }
1899
1900  if (minx > *tmin)
1901    *tmin = minx;
1902  if (maxx < *tmax)
1903    *tmax = maxx;
1904
1905  return 1; // yes, intersection was found
1906}
1907
1908
1909bool AxisAlignedBox3::GetIntersectionFace(Rectangle3 &face,
1910                                                                                  const AxisAlignedBox3 &neighbour) const
1911                                                                                   
1912{
1913        if (EpsilonEqual(mMin[0], neighbour.Max(0)))
1914        {
1915                float maxy = min(mMax.y, neighbour.mMax.y);
1916                float maxz = min(mMax.z, neighbour.mMax.z);
1917                float miny = max(mMin.y, neighbour.mMin.y);
1918                float minz = max(mMin.z, neighbour.mMin.z);
1919
1920                face.mVertices[3].SetValue(mMin.x, miny, minz);
1921                face.mVertices[2].SetValue(mMin.x, maxy, minz);
1922                face.mVertices[1].SetValue(mMin.x, maxy, maxz);
1923                face.mVertices[0].SetValue(mMin.x, miny, maxz);
1924
1925        return true;
1926        }
1927    if (EpsilonEqual(mMax[0], neighbour.Min(0)))
1928        {
1929                float maxy = min(mMax.y, neighbour.mMax.y);
1930                float maxz = min(mMax.z, neighbour.mMax.z);
1931                float miny = max(mMin.y, neighbour.mMin.y);
1932                float minz = max(mMin.z, neighbour.mMin.z);
1933
1934                face.mVertices[0].SetValue(mMax.x, miny, minz);
1935                face.mVertices[1].SetValue(mMax.x, maxy, minz);
1936                face.mVertices[2].SetValue(mMax.x, maxy, maxz);
1937                face.mVertices[3].SetValue(mMax.x, miny, maxz);
1938
1939                return true;
1940        }
1941    if (EpsilonEqual(mMin[1], neighbour.Max(1)))
1942        {
1943                float maxx = min(mMax.x, neighbour.mMax.x);
1944                float maxz = min(mMax.z, neighbour.mMax.z);
1945                float minx = max(mMin.x, neighbour.mMin.x);
1946                float minz = max(mMin.z, neighbour.mMin.z);
1947
1948                face.mVertices[3].SetValue(minx, mMin.y, minz);
1949                face.mVertices[2].SetValue(minx, mMin.y, maxz);
1950                face.mVertices[1].SetValue(maxx, mMin.y, maxz);
1951                face.mVertices[0].SetValue(maxx, mMin.y, minz);
1952               
1953                return true;
1954        }
1955        if (EpsilonEqual(mMax[1], neighbour.Min(1)))
1956        {               
1957                float maxx = min(mMax.x, neighbour.mMax.x);
1958                float maxz = min(mMax.z, neighbour.mMax.z);
1959                float minx = max(mMin.x, neighbour.mMin.x);
1960                float minz = max(mMin.z, neighbour.mMin.z);
1961
1962                face.mVertices[0].SetValue(minx, mMax.y, minz);
1963                face.mVertices[1].SetValue(minx, mMax.y, maxz);
1964                face.mVertices[2].SetValue(maxx, mMax.y, maxz);
1965                face.mVertices[3].SetValue(maxx, mMax.y, minz);
1966
1967                return true;
1968        }
1969        if (EpsilonEqual(mMin[2], neighbour.Max(2)))
1970        {
1971                float maxx = min(mMax.x, neighbour.mMax.x);
1972                float maxy = min(mMax.y, neighbour.mMax.y);
1973                float minx = max(mMin.x, neighbour.mMin.x);
1974                float miny = max(mMin.y, neighbour.mMin.y);
1975
1976                face.mVertices[3].SetValue(minx, miny, mMin.z);
1977                face.mVertices[2].SetValue(maxx, miny, mMin.z);
1978                face.mVertices[1].SetValue(maxx, maxy, mMin.z);
1979                face.mVertices[0].SetValue(minx, maxy, mMin.z);
1980       
1981                return true;
1982        }
1983        if (EpsilonEqual(mMax[2], neighbour.Min(2)))
1984        {
1985                float maxx = min(mMax.x, neighbour.mMax.x);
1986                float maxy = min(mMax.y, neighbour.mMax.y);
1987                float minx = max(mMin.x, neighbour.mMin.x);
1988                float miny = max(mMin.y, neighbour.mMin.y);
1989
1990                face.mVertices[0].SetValue(minx, miny, mMax.z);
1991                face.mVertices[1].SetValue(maxx, miny, mMax.z);
1992                face.mVertices[2].SetValue(maxx, maxy, mMax.z);
1993                face.mVertices[3].SetValue(minx, maxy, mMax.z);
1994
1995                return true;
1996        }
1997
1998        return false;
1999}
2000
2001
2002void AxisAlignedBox3::AddBoxToMesh(Mesh *mesh) const
2003{
2004        // add 6 vertices of the box
2005        int index = (int)mesh->mVertices.size();
2006       
2007        for (int i=0; i < 8; i++)
2008        {
2009                Vector3 v;
2010                GetVertex(i, v);
2011                mesh->mVertices.push_back(v);
2012        }
2013       
2014        mesh->AddFace(new Face(index + 0, index + 1, index + 3, index + 2) );
2015        mesh->AddFace(new Face(index + 0, index + 2, index + 6, index + 4) );
2016        mesh->AddFace(new Face(index + 4, index + 6, index + 7, index + 5) );
2017       
2018        mesh->AddFace(new Face(index + 3, index + 1, index + 5, index + 7) );
2019        mesh->AddFace(new Face(index + 0, index + 4, index + 5, index + 1) );
2020        mesh->AddFace(new Face(index + 2, index + 3, index + 7, index + 6) );
2021
2022}
Note: See TracBrowser for help on using the repository browser.