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

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

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