source: GTP/trunk/App/Demos/Vis/FriendlyCulling/src/AxisAlignedBox3.cpp @ 3070

Revision 3070, 39.1 KB checked in by mattausch, 16 years ago (diff)
Line 
1#include "AxisAlignedBox3.h"
2#include "Plane3.h"
3#include "Polygon3.h"
4#include "Polyhedron.h"
5#include "Triangle3.h"
6
7#include <cassert>
8#include <iostream>
9
10#ifdef _CRT_SET
11        #define _CRTDBG_MAP_ALLOC
12        #include <stdlib.h>
13        #include <crtdbg.h>
14
15        // redefine new operator
16        #define DEBUG_NEW new(_NORMAL_BLOCK, __FILE__, __LINE__)
17        #define new DEBUG_NEW
18#endif
19
20
21using namespace std;
22
23
24namespace CHCDemoEngine
25{
26
27// Overload << operator for C++-style output
28ostream& operator<< (ostream &s, const AxisAlignedBox3 &A)
29{
30        return s << '[' << A.mMin.x << ", " << A.mMin.y << ", " << A.mMin.z << "]["
31                << A.mMax.x << ", " << A.mMax.y << ", " << A.mMax.z << ']';
32}
33
34
35// Overload >> operator for C++-style input
36istream& operator>> (istream &s, AxisAlignedBox3 &A)
37{
38        char a;
39        // read "[min.x, min.y, min.z][mMax.x, mMax.y, mMax.z]"
40        return s >> a >> A.mMin.x >> a >> A.mMin.y >> a >> A.mMin.z >> a >> a
41                >> A.mMax.x >> a >> A.mMax.y >> a >> A.mMax.z >> a;
42}
43
44
45AxisAlignedBox3::AxisAlignedBox3()
46{ }
47
48
49AxisAlignedBox3::AxisAlignedBox3(const Vector3 &nMin, const Vector3 &nMax)
50: mMin(nMin), mMax(nMax)
51{}
52
53
54
55bool AxisAlignedBox3::Unbounded() const
56{
57        return (mMin == Vector3(-MAXFLOAT)) ||
58                   (mMax == Vector3(-MAXFLOAT));
59}
60
61
62void AxisAlignedBox3::Include(const Vector3 &newpt)
63{
64        Minimize(mMin, newpt);
65        Maximize(mMax, newpt);
66}
67
68
69void AxisAlignedBox3::Include(const Polygon3 &newpoly)
70{
71        VertexArray::const_iterator it, it_end = newpoly.mVertices.end();
72
73        for (it = newpoly.mVertices.begin(); it != it_end; ++ it)
74                Include(*it);
75}
76
77
78void AxisAlignedBox3::Include(const PolygonContainer &polys)
79{
80        PolygonContainer::const_iterator it, it_end = polys.end();
81
82        for (it = polys.begin(); it != it_end; ++ it)
83                Include(*(*it));
84}
85
86
87void AxisAlignedBox3::Include(const AxisAlignedBox3 &bbox)
88{
89        Minimize(mMin, bbox.mMin);
90        Maximize(mMax, bbox.mMax);
91}
92
93
94bool AxisAlignedBox3::IsCorrect()
95{
96        if ( (mMin.x > mMax.x) ||
97                (mMin.y > mMax.y) ||
98                (mMin.z > mMax.z) )
99                return false; // box is not formed
100        return true;
101}
102
103
104void AxisAlignedBox3::GetEdge(const int edge, Vector3 *a, Vector3 *b) const
105{
106        switch(edge) {
107  case 0:
108          a->SetValue(mMin.x, mMin.y, mMin.z);
109          b->SetValue(mMin.x, mMin.y, mMax.z);
110          break;
111  case 1:
112          a->SetValue(mMin.x, mMin.y, mMin.z);
113          b->SetValue(mMin.x, mMax.y, mMin.z);
114          break;
115  case 2:
116          a->SetValue(mMin.x, mMin.y, mMin.z);
117          b->SetValue(mMax.x, mMin.y, mMin.z);
118          break;
119  case 3:
120          a->SetValue(mMax.x, mMax.y, mMax.z);
121          b->SetValue(mMax.x, mMax.y, mMin.z);
122          break;
123  case 4:
124          a->SetValue(mMax.x, mMax.y, mMax.z);
125          b->SetValue(mMax.x, mMin.y, mMax.z);
126          break;
127  case 5:
128          a->SetValue(mMax.x, mMax.y, mMax.z);
129          b->SetValue(mMin.x, mMax.y, mMax.z);
130          break;
131
132  case 6:
133          a->SetValue(mMin.x, mMin.y, mMax.z);
134          b->SetValue(mMin.x, mMax.y, mMax.z);
135          break;
136  case 7:
137          a->SetValue(mMin.x, mMin.y, mMax.z);
138          b->SetValue(mMax.x, mMin.y, mMax.z);
139          break;
140  case 8:
141          a->SetValue(mMin.x, mMax.y, mMin.z);
142          b->SetValue(mMin.x, mMax.y, mMax.z);
143          break;
144  case 9:
145          a->SetValue(mMin.x, mMax.y, mMin.z);
146          b->SetValue(mMax.x, mMax.y, mMin.z);
147          break;
148  case 10:
149          a->SetValue(mMax.x, mMin.y, mMin.z);
150          b->SetValue(mMax.x, mMax.y, mMin.z);
151          break;
152  case 11:
153          a->SetValue(mMax.x, mMin.y, mMin.z);
154          b->SetValue(mMax.x, mMin.y, mMax.z);
155          break;
156        }
157}
158
159// returns the vertex indices in the range <0..7>, v = 4.x + 2.y + z, where
160// x,y,z are either 0 or 1; (0 .. min coordinate, 1 .. max coordinate)
161void
162AxisAlignedBox3::GetEdge(const int edge, int  &aIdx, int &bIdx) const
163{
164        switch(edge) {
165  case 0: aIdx = 0; bIdx = 1; break;
166  case 1: aIdx = 0; bIdx = 2; break;
167  case 2: aIdx = 0; bIdx = 4; break;
168  case 3: aIdx = 7; bIdx = 6; break;
169  case 4: aIdx = 7; bIdx = 5; break;
170  case 5: aIdx = 7; bIdx = 3; break;
171  case 6: aIdx = 1; bIdx = 3; break;
172  case 7: aIdx = 1; bIdx = 5; break;
173  case 8: aIdx = 2; bIdx = 3; break;
174  case 9: aIdx = 2; bIdx = 6; break;
175  case 10: aIdx = 4; bIdx = 6; break;
176  case 11: aIdx = 4; bIdx = 5; break;
177        }
178}
179
180void
181AxisAlignedBox3::Include(const int &axis, const float &newBound)
182{
183        switch (axis) {
184        case 0: { // x-axis
185                if (mMin.x > newBound)
186                        mMin.x = newBound;
187                if (mMax.x < newBound)
188                        mMax.x = newBound;
189                break;
190                        }
191        case 1: { // y-axis
192                if (mMin.y > newBound)
193                        mMin.y = newBound;
194                if (mMax.y < newBound)
195                        mMax.y = newBound;
196                break;
197                        }
198        case 2: { // z-axis
199                if (mMin.z > newBound)
200                        mMin.z = newBound;
201                if (mMax.z < newBound)
202                        mMax.z = newBound;
203                break;
204                        }
205        }
206}
207
208
209void AxisAlignedBox3::Describe(ostream &app, int ind) const
210{
211        indent(app, ind);
212        app << "AxisAlignedBox3: min at(" << mMin << "), max at(" << mMax << ")\n";
213}
214
215int
216AxisAlignedBox3::IsInside(const Vector3 &v) const
217{
218        return !((v.x < mMin.x) ||
219                    (v.x > mMax.x) ||
220                        (v.y < mMin.y) ||
221                        (v.y > mMax.y) ||
222                        (v.z < mMin.z) ||
223                        (v.z > mMax.z));
224}
225
226
227bool AxisAlignedBox3::Includes(const AxisAlignedBox3 &b) const
228{
229        return (b.mMin.x >= mMin.x &&
230                b.mMin.y >= mMin.y &&
231                b.mMin.z >= mMin.z &&
232                b.mMax.x <= mMax.x &&
233                b.mMax.y <= mMax.y &&
234                b.mMax.z <= mMax.z);
235}
236
237
238// compute the coordinates of one vertex of the box
239Vector3 AxisAlignedBox3::GetVertex(int xAxis, int yAxis, int zAxis) const
240{
241        Vector3 p;
242        if (xAxis)
243                p.x = mMax.x;
244        else
245                p.x = mMin.x;
246
247        if (yAxis)
248                p.y = mMax.y;
249        else
250                p.y = mMin.y;
251
252        if (zAxis)
253                p.z = mMax.z;
254        else
255                p.z = mMin.z;
256        return p;
257}
258
259
260// compute the vertex for number N = <0..7>, N = 4.x + 2.y + z, where
261// x,y,z are either 0 or 1; (0 .. min coordinate, 1 .. max coordinate)
262void AxisAlignedBox3::GetVertex(const int N, Vector3 &vertex) const
263{
264        switch (N)
265        {
266        case 0: vertex = mMin; break;
267        case 1: vertex.SetValue(mMin.x, mMin.y, mMax.z); break;
268        case 2: vertex.SetValue(mMin.x, mMax.y, mMin.z); break;
269        case 3: vertex.SetValue(mMin.x, mMax.y, mMax.z); break;
270        case 4: vertex.SetValue(mMax.x, mMin.y, mMin.z); break;
271        case 5: vertex.SetValue(mMax.x, mMin.y, mMax.z); break;
272        case 6: vertex.SetValue(mMax.x, mMax.y, mMin.z); break;
273        case 7: vertex = mMax; break;
274        default:
275                {
276                        cerr << "ERROR in AxisAlignedBox3::GetVertex N=" << N <<  "\n";
277                }
278        }
279}
280
281
282float AxisAlignedBox3::SurfaceArea() const
283{
284        Vector3 ext = mMax - mMin;
285
286        return 2.0f * (ext.x * ext.y +
287                ext.x * ext.z +
288                ext.y * ext.z);
289}
290
291
292float AxisAlignedBox3::GetVolume() const
293{
294        return (mMax.x - mMin.x) * (mMax.y - mMin.y) * (mMax.z - mMin.z);
295}
296
297
298const int AxisAlignedBox3::bvertices[27][9] =
299{                   // region number.. position
300        {5,1,3,2,6,4,-1,-1,-1},      // 0 .. x=0 y=0 z=0
301        {4,5,1,3,2,0,-1,-1,-1},      // 1 .. x=0 y=0 z=1
302        {4,5,7,3,2,0,-1,-1,-1},      // 2 .. x=0 y=0 z=2
303
304        {0,1,3,2,6,4,-1,-1,-1},      // 3 .. x=0 y=1 z=0
305        {0,1,3,2,-1,-1,-1,-1,-1},    // 4 .. x=0 y=1 z=1
306        {1,5,7,3,2,0,-1,-1,-1},      // 5 .. x=0 y=1 z=2
307
308        {0,1,3,7,6,4,-1,-1,-1},      // 6 .. x=0 y=2 z=0
309        {0,1,3,7,6,2,-1,-1,-1},      // 7 .. x=0 y=2 z=1
310        {1,5,7,6,2,0,-1,-1,-1},      // 8 .. x=0 y=2 z=2
311
312        // the regions number <9,17>
313        {5,1,0,2,6,4,-1,-1,-1},      // 9  .. x=1 y=0 z=0
314        {5,1,0,4,-1,-1,-1,-1,-1},    // 10 .. x=1 y=0 z=1
315        {7,3,1,0,4,5,-1,-1,-1},      // 11 .. x=1 y=0 z=2
316
317        {4,0,2,6,-1,-1,-1,-1,-1},    // 12 .. x=1 y=1 z=0
318        {0,2,3,1,5,4,6,7,-1},        // 13 .. x=1 y=1 z=1 .. inside the box
319        {1,5,7,3,-1,-1,-1,-1,-1},    // 14 .. x=1 y=1 z=2
320
321        {4,0,2,3,7,6,-1,-1,-1},      // 15 .. x=1 y=2 z=0
322        {6,2,3,7,-1,-1,-1,-1,-1},    // 16 .. x=1 y=2 z=1
323        {1,5,7,6,2,3,-1,-1,-1},      // 17 .. x=1 y=2 z=2
324
325        // the regions number <18,26>
326        {1,0,2,6,7,5,-1,-1,-1},      // 18 .. x=2 y=0 z=0
327        {1,0,4,6,7,5,-1,-1,-1},      // 19 .. x=2 y=0 z=1
328        {0,4,6,7,3,1,-1,-1,-1},      // 20 .. x=2 y=0 z=2
329
330        {4,0,2,6,7,5,-1,-1,-1},      // 21 .. x=2 y=1 z=0
331        {5,4,6,7,-1,-1,-1,-1,-1},    // 22 .. x=2 y=1 z=1
332        {5,4,6,7,3,1,-1,-1,-1},      // 23 .. x=2 y=1 z=2
333
334        {4,0,2,3,7,5,-1,-1,-1},      // 24 .. x=2 y=2 z=0
335        {5,4,6,2,3,7,-1,-1,-1},      // 25 .. x=2 y=2 z=1
336        {5,4,6,2,3,1,-1,-1,-1},      // 26 .. x=2 y=2 z=2
337};
338
339// the visibility of boundary faces from a given region
340// one to three triples: (axis, min_vertex, max_vertex), axis==-1(terminator)
341const int AxisAlignedBox3::bfaces[27][10] =
342{                              // region number .. position
343        {0,0,3,1,0,5,2,0,6,-1},      // 0 .. x=0 y=0 z=0
344        {0,0,3,1,0,5,-1,-1,-1,-1},   // 1 .. x=0 y=0 z=1
345        {0,0,3,1,0,5,2,1,7,-1},      // 2 .. x=0 y=0 z=2
346
347        {0,0,3,2,0,6,-1,-1,-1,-1},   // 3 .. x=0 y=1 z=0
348        {0,0,3,-1,-1,-1,-1,-1,-1,-1},// 4 .. x=0 y=1 z=1
349        {0,0,3,2,1,7,-1,-1,-1,-1},   // 5 .. x=0 y=1 z=2
350
351        {0,0,3,1,2,7,2,0,6,-1},      // 6 .. x=0 y=2 z=0
352        {0,0,3,1,2,7,-1,-1,-1,-1},   // 7 .. x=0 y=2 z=1
353        {0,0,3,1,2,7,2,1,7,-1},      // 8 .. x=0 y=2 z=2
354
355        // the regions number <9,17>
356        {1,0,5,2,0,6,-1,-1,-1,-1},   // 9  .. x=1 y=0 z=0
357        {1,0,5,-1,-1,-1,-1,-1,-1,-1},// 10 .. x=1 y=0 z=1
358        {1,0,5,2,1,7,-1,-1,-1,-1},   // 11 .. x=1 y=0 z=2
359
360        {2,0,6,-1,-1,-1,-1,-1,-1,-1},// 12 .. x=1 y=1 z=0
361        {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1},// 13 .. x=1 y=1 z=1 .. inside the box
362        {2,1,7,-1,-1,-1,-1,-1,-1,-1},// 14 .. x=1 y=1 z=2
363
364        {1,2,7,2,0,6,-1,-1,-1,-1},   // 15 .. x=1 y=2 z=0
365        {1,2,7,-1,-1,-1,-1,-1,-1,-1},// 16 .. x=1 y=2 z=1
366        {1,2,7,2,1,7,-1,-1,-1,-1},   // 17 .. x=1 y=2 z=2
367
368        // the region number <18,26>
369        {0,4,7,1,0,5,2,0,6,-1},      // 18 .. x=2 y=0 z=0
370        {0,4,7,1,0,5,-1,-1,-1,-1},   // 19 .. x=2 y=0 z=1
371        {0,4,7,1,0,5,2,1,7,-1},      // 20 .. x=2 y=0 z=2
372
373        {0,4,7,2,0,6,-1,-1,-1,-1},   // 21 .. x=2 y=1 z=0
374        {0,4,7,-1,-1,-1,-1,-1,-1,-1},// 22 .. x=2 y=1 z=1
375        {0,4,7,2,1,7,-1,-1,-1,-1},   // 23 .. x=2 y=1 z=2
376
377        {0,4,7,1,2,7,2,0,6,-1},      // 24 .. x=2 y=2 z=0
378        {0,4,7,1,2,7,-1,-1,-1,-1},   // 25 .. x=2 y=2 z=1
379        {0,4,7,1,2,7,2,1,7,-1},      // 26 .. x=2 y=2 z=2
380};
381
382// the correct corners indexing from entry face to exit face
383// first index determines entry face, second index exit face, and
384// the two numbers (indx, inc) determines: ind = the index on the exit
385// face, when starting from the vertex 0 on entry face, 'inc' is
386// the increment when we go on entry face in order 0,1,2,3 to create
387// convex shaft with the rectangle on exit face. That is, inc = -1 or 1.
388const int AxisAlignedBox3::pairFaceRects[6][6][2] = {
389        { // entry face = 0
390                {-1,0}, // exit face 0 .. no meaning
391                {0,-1}, // 1
392                {0,-1}, // 2
393                {0,1}, // 3 .. opposite face
394                {3,1}, // 4
395                {1,1} // 5
396        },
397        { // entry face = 1
398                {0,-1}, // exit face 0
399                {-1,0}, // 1 .. no meaning
400                {0,-1}, // 2
401                {1,1}, // 3
402                {0,1}, // 4 .. opposite face
403                {3,1} // 5
404        },
405        { // entry face = 2
406                {0,-1}, // 0
407                {0,-1}, // 1
408                {-1,0}, // 2 .. no meaning
409                {3,1}, // 3
410                {1,1}, // 4
411                {0,1} // 5 .. opposite face
412        },
413        { // entry face = 3
414                {0,1}, // 0 .. opposite face
415                {3,-1}, // 1
416                {1,1}, // 2
417                {-1,0}, // 3  .. no meaning
418                {0,-1}, // 4
419                {0,-1} // 5
420        },
421        { // entry face = 4
422                {1,1}, // 0
423                {0,1}, // 1 .. opposite face
424                {3,1}, // 2
425                {0,-1}, // 3
426                {-1,0}, // 4 .. no meaning
427                {0,-1} // 5
428        },
429        { // entry face = 5
430                {3,-1}, // 0
431                {1,1}, // 1
432                {0,1}, // 2  .. opposite face
433                {0,-1}, // 3
434                {0,-1}, // 4
435                {-1,0} // 5 .. no meaning
436        }
437};
438
439
440// ------------------------------------------------------------
441// The vertices that form CLOSEST points with respect to the region
442// for all the regions possible, number of regions is 3^3 = 27,
443// since two parallel sides of bbox forms three disjoint spaces.
444// The vertices are given in anti-clockwise order, stopped by value 15,
445// at most 8 points, at least 1 point.
446// The table includes the closest 1/2/4/8 points, followed possibly
447// by the set of coordinates that should be used for testing for
448// the proximity queries. The coordinates to be tested are described by
449// the pair (a,b), when a=0, we want to test min vector of the box,
450//                 when a=1, we want to test max vector of the box
451//                 b=0,1,2 corresponds to the axis (0=x,1=y,2=z)
452// The sequence is ended by 15, number -1 is used as the separator
453// between the vertices and coordinates.
454const int
455AxisAlignedBox3::cvertices[27][9] =
456{                   // region number.. position
457        {0,15,15,15,15,15,15,15,15}, // 0 .. x=0 y=0 z=0 D one vertex
458        {0,1,-1,0,0,0,1,15,15},      // 1 .. x=0 y=0 z=1 D two vertices foll. by 2
459        {1,15,15,15,15,15,15,15,15}, // 2 .. x=0 y=0 z=2 D one vertex
460
461        {0,2,-1,0,0,0,2,15,15},      // 3 .. x=0 y=1 z=0 D
462        {0,1,3,2,-1,0,0,15,15},      // 4 .. x=0 y=1 z=1 D
463        {1,3,-1,0,0,1,2,15,15},      // 5 .. x=0 y=1 z=2 D
464
465        {2,15,15,15,15,15,15,15,15}, // 6 .. x=0 y=2 z=0 D
466        {2,3,-1,0,0,1,1,15,15},      // 7 .. x=0 y=2 z=1 D
467        {3,15,15,15,15,15,15,15,15}, // 8 .. x=0 y=2 z=2 D
468
469        // the regions number <9,17>
470        {0,4,-1,0,1,0,2,15,15},      // 9  .. x=1 y=0 z=0 D
471        {5,1,0,4,-1,0,1,15,15},      // 10 .. x=1 y=0 z=1 D
472        {1,5,-1,0,1,1,2,15,15},      // 11 .. x=1 y=0 z=2 D
473
474        {4,0,2,6,-1,0,2,15,15},      // 12 .. x=1 y=1 z=0 D
475        {0,2,3,1,5,4,6,7,15},        // 13 .. x=1 y=1 z=1 .. inside the box
476        {1,5,7,3,-1,1,2,15,15},      // 14 .. x=1 y=1 z=2 D
477
478        {6,2,-1,0,2,1,1,15,15},      // 15 .. x=1 y=2 z=0 D
479        {6,2,3,7,-1,1,1,15,15},      // 16 .. x=1 y=2 z=1 D
480        {3,7,-1,1,1,1,2,15,15},      // 17 .. x=1 y=2 z=2 D
481
482        // the regions number <18,26>
483        {4,15,15,15,15,15,15,15,15}, // 18 .. x=2 y=0 z=0 D
484        {4,5,-1,0,1,1,0,15,15},      // 19 .. x=2 y=0 z=1 D
485        {5,15,15,15,15,15,15,15,15}, // 20 .. x=2 y=0 z=2 D
486
487        {4,6,-1,0,2,1,0,15,15},      // 21 .. x=2 y=1 z=0 D
488        {5,4,6,7,-1,1,0,15,15},      // 22 .. x=2 y=1 z=1 D
489        {7,5,-1,1,0,1,2,15,15},      // 23 .. x=2 y=1 z=2 D
490
491        {6,15,15,15,15,15,15,15,15}, // 24 .. x=2 y=2 z=0 D
492        {6,7,-1,1,0,1,1,15,15},      // 25 .. x=2 y=2 z=1 D
493        {7,15,15,15,15,15,15,15,15}, // 26 .. x=2 y=2 z=2 D
494};
495
496// Table for Sphere-AABB intersection based on the region knowledge
497// Similar array to previous cvertices, but we omit the surfaces
498// which are not necessary for testing. First are vertices,
499// they are finished with -1. Second, there are indexes in
500// the pair (a,b), when a=0, we want to test min vector of the box,
501//                 when a=1, we want to test max vector of the box
502//                 b=0,1,2 corresponds to the axis (0=x,1=y,2=z)
503//
504// So either we check the vertices or only the distance in specified
505// dimensions. There are at all four possible cases:
506//
507//   1) we check one vertex - then sequence start with non-negative index
508//      and is finished with 15
509//   2) we check two coordinates of min/max vector describe by the pair
510//         (a,b) .. a=min/max(0/1) b=x/y/z (0/1/2), sequence starts with 8
511//      and finishes with 15
512//   3) we check only one coordinate of min/max, as for 2), sequence start
513//      with 9 and ends with 15
514//   4) Position 13 - sphere is inside the box, intersection always exist
515//        the sequence start with 15 .. no further testing is necessary
516//        in this case
517const int
518AxisAlignedBox3::csvertices[27][6] =
519{                   // region number.. position
520        {0,15,15,15,15,15},  // 0 .. x=0 y=0 z=0 D vertex only
521        {8,0,0,0,1,15},      // 1 .. x=0 y=0 z=1 D two coords.
522        {1,15,15,15,15,15},  // 2 .. x=0 y=0 z=2 D vertex only
523
524        {8,0,0,0,2,15},      // 3 .. x=0 y=1 z=0 D two coords
525        {9,0,0,15,15,15},    // 4 .. x=0 y=1 z=1 D one coord
526        {8,0,0,1,2,15},      // 5 .. x=0 y=1 z=2 D two coords.
527
528        {2,15,15,15,15,15},  // 6 .. x=0 y=2 z=0 D one vertex
529        {8,0,0,1,1,15},      // 7 .. x=0 y=2 z=1 D two coords
530        {3,15,15,15,15,15},  // 8 .. x=0 y=2 z=2 D one vertex
531
532        // the regions number <9,17>
533        {8,0,1,0,2,15},      // 9  .. x=1 y=0 z=0 D two coords
534        {9,0,1,15,15,15},    // 10 .. x=1 y=0 z=1 D one coord
535        {8,0,1,1,2,15},      // 11 .. x=1 y=0 z=2 D two coords
536
537        {9,0,2,15,15,15},    // 12 .. x=1 y=1 z=0 D one coord
538        {15,15,15,15,15,15}, // 13 .. x=1 y=1 z=1 inside the box, special case/value
539        {9,1,2,15,15,15},    // 14 .. x=1 y=1 z=2 D one corrd
540
541        {8,0,2,1,1,15},      // 15 .. x=1 y=2 z=0 D two coords
542        {9,1,1,15,15},       // 16 .. x=1 y=2 z=1 D one coord
543        {8,1,1,1,2,15},      // 17 .. x=1 y=2 z=2 D two coords
544
545        // the regions number <18,26>
546        {4,15,15,15,15,15},  // 18 .. x=2 y=0 z=0 D one vertex
547        {8,0,1,1,0,15},      // 19 .. x=2 y=0 z=1 D two coords
548        {5,15,15,15,15,15},  // 20 .. x=2 y=0 z=2 D one vertex
549
550        {8,0,2,1,0,15},      // 21 .. x=2 y=1 z=0 D two coords
551        {9,1,0,15,15,15},    // 22 .. x=2 y=1 z=1 D one coord
552        {8,1,0,1,2,15},      // 23 .. x=2 y=1 z=2 D two coords
553
554        {6,15,15,15,15,15},  // 24 .. x=2 y=2 z=0 D one vertex
555        {8,1,0,1,1,15},      // 25 .. x=2 y=2 z=1 D two coords
556        {7,15,15,15,15,15},  // 26 .. x=2 y=2 z=2 D one vertex
557};
558
559
560// The vertices that form all FARTHEST points with respect to the region
561// for all the regions possible, number of regions is 3^3 = 27,
562// since two parallel sides of bbox forms three disjoint spaces.
563// The vertices are given in anti-clockwise order, stopped by value 15,
564// at most 8 points, at least 1 point.
565// For testing, if the AABB is whole in the sphere, it is enough
566// to test only vertices, either 1,2,4, or 8.
567const int
568AxisAlignedBox3::fvertices[27][9] =
569{                   // region number.. position
570        {7,15,15,15,15,15,15,15,15}, // 0 .. x=0 y=0 z=0 D
571        {6,7,15,15,15,15,15,15,15},  // 1 .. x=0 y=0 z=1 D
572        {6,15,15,15,15,15,15,15,15}, // 2 .. x=0 y=0 z=2 D
573
574        {5,7,15,15,15,15,15,15,15},  // 3 .. x=0 y=1 z=0 D
575        {4,5,7,6,15,15,15,15,15},    // 4 .. x=0 y=1 z=1 D
576        {4,6,15,15,15,15,15,15,15},  // 5 .. x=0 y=1 z=2 D
577
578        {5,15,15,15,15,15,15,15,15}, // 6 .. x=0 y=2 z=0 D
579        {4,5,15,15,15,15,15,15,15},  // 7 .. x=0 y=2 z=1 D
580        {4,15,15,15,15,15,15,15,15}, // 8 .. x=0 y=2 z=2 D
581
582        // the regions number <9,17>
583        {3,7,15,15,15,15,15,15,15},  // 9  .. x=1 y=0 z=0 D
584        {7,3,2,6,15,15,15,15,15},    // 10 .. x=1 y=0 z=1 D
585        {2,6,15,15,15,15,15,15,15},  // 11 .. x=1 y=0 z=2 D
586
587        {5,1,3,7,15,15,15,15,15},    // 12 .. x=1 y=1 z=0 D
588        {0,7,1,6,3,4,5,2,15},        // 13 .. x=1 y=1 z=1 .. inside the box
589        {0,4,6,2,15,15,15,15,15},    // 14 .. x=1 y=1 z=2 D
590
591        {5,1,15,15,15,15,15,15,15},  // 15 .. x=1 y=2 z=0 D
592        {4,0,1,5,15,15,15,15,15},    // 16 .. x=1 y=2 z=1 D
593        {4,0,15,15,15,15,15,15,15},  // 17 .. x=1 y=2 z=2 D
594
595        // the regions number <18,26>
596        {3,15,15,15,15,15,15,15,15}, // 18 .. x=2 y=0 z=0 D
597        {2,3,15,15,15,15,15,15,15},  // 19 .. x=2 y=0 z=1 D
598        {2,15,15,15,15,15,15,15,15}, // 20 .. x=2 y=0 z=2 D
599
600        {1,3,15,15,15,15,15,15,15},  // 21 .. x=2 y=1 z=0 D
601        {1,0,2,3,15,15,15,15,15},    // 22 .. x=2 y=1 z=1 D
602        {2,0,15,15,15,15,15,15,15},  // 23 .. x=2 y=1 z=2 D
603
604        {1,15,15,15,15,15,15,15,15}, // 24 .. x=2 y=2 z=0 D
605        {0,1,15,15,15,15,15,15,15},  // 25 .. x=2 y=2 z=1 D
606        {0,15,15,15,15,15,15,15,15}, // 26 .. x=2 y=2 z=2 D
607};
608
609// Similar table as above, farthest points, but only the ones
610// necessary for testing the intersection problem. If we do
611// not consider the case 13, center of the sphere is inside the
612// box, then we can always test at most 2 box vertices to say whether
613// the whole box is inside the sphere.
614// The number of vertices is minimized using some assumptions
615// about the ortogonality of vertices and sphere properties.
616const int
617AxisAlignedBox3::fsvertices[27][9] =
618{                   // region number.. position
619        {7,15,15,15,15,15,15,15,15}, // 0 .. x=0 y=0 z=0 D 1 vertex
620        {6,7,15,15,15,15,15,15,15},  // 1 .. x=0 y=0 z=1 D 2 vertices
621        {6,15,15,15,15,15,15,15,15}, // 2 .. x=0 y=0 z=2 D 1 vertex
622
623        {5,7,15,15,15,15,15,15,15},  // 3 .. x=0 y=1 z=0 D 2 vertices
624        {4,7,15,5,6,15,15,15,15},    // 4 .. x=0 y=1 z=1 D 4/2 vertices
625        {4,6,15,15,15,15,15,15,15},  // 5 .. x=0 y=1 z=2 D 2 vertices
626
627        {5,15,15,15,15,15,15,15,15}, // 6 .. x=0 y=2 z=0 D 1 vertex
628        {4,5,15,15,15,15,15,15,15},  // 7 .. x=0 y=2 z=1 D 2 vertices
629        {4,15,15,15,15,15,15,15,15}, // 8 .. x=0 y=2 z=2 D 1 vertex
630
631        // the regions number <9,17>
632        {3,7,15,15,15,15,15,15,15},  // 9  .. x=1 y=0 z=0 D 2 vertices
633        {7,2,15,3,6,15,15,15,15},    // 10 .. x=1 y=0 z=1 D 4/2 vertices
634        {2,6,15,15,15,15,15,15,15},  // 11 .. x=1 y=0 z=2 D 2 vertices
635
636        {5,3,15,1,7,15,15,15,15},    // 12 .. x=1 y=1 z=0 D 4/2 vertices
637        {0,7,1,6,3,4,5,2,15},        // 13 .. x=1 y=1 z=1 .. inside the box
638        {0,6,15,4,2,15,15,15,15},    // 14 .. x=1 y=1 z=2 D 4/2 vertices
639
640        {5,1,15,15,15,15,15,15,15},  // 15 .. x=1 y=2 z=0 D 2 vertices
641        {4,1,15,0,5,15,15,15,15},    // 16 .. x=1 y=2 z=1 D 4/2 vertices
642        {4,0,15,15,15,15,15,15,15},  // 17 .. x=1 y=2 z=2 D 2 vertices
643
644        // the regions number <18,26>
645        {3,15,15,15,15,15,15,15,15}, // 18 .. x=2 y=0 z=0 D 1 vertex
646        {2,3,15,15,15,15,15,15,15},  // 19 .. x=2 y=0 z=1 D 2 vertices
647        {2,15,15,15,15,15,15,15,15}, // 20 .. x=2 y=0 z=2 D 1 vertex
648
649        {1,3,15,15,15,15,15,15,15},  // 21 .. x=2 y=1 z=0 D 2 vertices
650        {1,2,15,0,3,15,15,15,15},    // 22 .. x=2 y=1 z=1 D 4/2 vertices
651        {2,0,15,15,15,15,15,15,15},  // 23 .. x=2 y=1 z=2 D 2 vertices
652
653        {1,15,15,15,15,15,15,15,15}, // 24 .. x=2 y=2 z=0 D 1 vertex
654        {0,1,15,15,15,15,15,15,15},  // 25 .. x=2 y=2 z=1 D 2 vertices
655        {0,15,15,15,15,15,15,15,15}, // 26 .. x=2 y=2 z=2 D 1 vertex
656};
657
658
659// The fast computation of arctangent .. the maximal error is less
660// than 4.1 degrees, according to Graphics GEMSII, 1991, pages 389--391
661// Ron Capelli: "Fast approximation to the arctangent"
662float atan22(const float& y)
663{
664        const float x = 1.0;
665        const float c = (float)(M_PI * 0.25);
666
667        if (y < 0.0) {
668                if (y < -1.0)
669                        return c * (-2.0f + x / y); // for angle in <-PI/2, -PI/4)
670                else
671                        return c * (y / x); // for angle in <-PI/4 , 0>
672        }
673        else {
674                if (y > 1.0)
675                        return c * (2.0f - x / y); // for angle in <PI/4, PI/2>
676                else
677                        return c * (y / x); // for angle in <0, PI/2>
678        }
679}
680
681
682// This definition allows to be a point when answering true
683bool
684AxisAlignedBox3::IsCorrectAndNotPoint() const
685{
686        if ( (mMin.x > mMax.x) ||
687                (mMin.y > mMax.y) ||
688                (mMin.z > mMax.z) )
689                return false; // box is not formed
690
691        if ( (mMin.x == mMax.x) &&
692                (mMin.y == mMax.y) &&
693                (mMin.z == mMax.z) )
694                return false; // degenerates to a point
695
696        return true;
697}
698
699// This definition allows to be a point when answering true
700bool AxisAlignedBox3::IsPoint() const
701{
702        if ( (mMin.x == mMax.x) &&
703                (mMin.y == mMax.y) &&
704                (mMin.z == mMax.z) )
705                return true; // degenerates to a point
706
707        return false;
708}
709
710// This definition requires shape of non-zero volume
711bool AxisAlignedBox3::IsSingularOrIncorrect() const
712{
713        if ( (mMin.x >= mMax.x) ||
714                (mMin.y >= mMax.y) ||
715                (mMin.z >= mMax.z) )
716                return true; // box is not formed
717
718        return false; // has non-zero volume
719}
720
721
722void AxisAlignedBox3::GetSqrDistances(const Vector3 &point,
723                                                                          float &minDistance,
724                                                                          float &maxDistance) const
725{
726        // some overlap is possible, check the distance of vertices
727        float sumMin = 0;
728        float sumMax = 0;
729
730        // Try to minimize the function of a distance
731        // from the sphere center
732
733        const float *minp = &(mMin.x);
734        const float *maxp = &(mMax.x);
735        const float *pcenter = &(point.x);
736
737        // for x-axis
738        for (int i = 0; i < 3; i++, minp++, maxp++, pcenter++) {
739                float minsqr = sqr(*minp - *pcenter);
740                float maxsqr = sqr(*maxp - *pcenter);
741                if (*pcenter < *minp)
742                        sumMin += minsqr;
743                else
744                        if (*pcenter > *maxp)
745                                sumMin += maxsqr;
746                sumMax += (minsqr > maxsqr) ? minsqr : maxsqr;
747        }
748
749        minDistance = sumMin;
750        maxDistance = sumMax;
751}
752
753
754void AxisAlignedBox3::Scale(const float scale)
755{
756        Vector3 newSize = Size()*(scale*0.5f);
757        Vector3 center = Center();
758        mMin = center - newSize;
759        mMax = center + newSize;
760}
761
762
763void AxisAlignedBox3::Scale(const Vector3 &scale)
764{
765        Vector3 newSize = Size()*(scale*0.5f);
766        Vector3 center = Center();
767        mMin = center - newSize;
768        mMax = center + newSize;
769}
770
771
772void AxisAlignedBox3::Translate(const Vector3 &shift)
773{
774        mMin += shift;
775        mMax += shift;
776}
777
778
779void AxisAlignedBox3::Initialize()
780{
781        mMin = Vector3(MAXFLOAT);
782        mMax = Vector3(-MAXFLOAT);
783}
784
785
786Vector3 AxisAlignedBox3::Center() const
787{
788        return 0.5 * (mMin + mMax);
789}
790
791
792Vector3 AxisAlignedBox3::Diagonal() const
793{
794        return (mMax - mMin);
795}
796
797
798float AxisAlignedBox3::Center(const int axis) const
799{
800        return  0.5f * (mMin[axis] + mMax[axis]);
801}
802
803
804float AxisAlignedBox3::Min(const int axis) const
805{
806        return mMin[axis];
807}
808
809
810float AxisAlignedBox3::Max(const int axis) const
811{
812        return  mMax[axis];
813}
814
815
816float AxisAlignedBox3::Size(const int axis) const
817{
818        return  Max(axis) - Min(axis);
819}
820
821// Read-only const access tomMin and max vectors using references
822const Vector3& AxisAlignedBox3::Min() const
823{
824        return mMin;
825}
826
827
828const Vector3& AxisAlignedBox3::Max() const
829{
830        return mMax;
831}
832
833
834void AxisAlignedBox3::Enlarge (const Vector3 &v)
835{
836        mMax += v;
837        mMin -= v;
838}
839
840
841void AxisAlignedBox3::EnlargeToMinSize()
842{
843        const float epsMin = 1e-7f;
844        const float epsAdd = 1e-6f;
845        const float epsMul = 1.000005f;
846        float dir = mMax.x - mMin.x;
847
848        assert(dir >= 0.f);
849
850        if (dir < epsMin)
851        {
852                if (mMax.x > 0)
853                {
854                        mMax.x *= epsMul;
855                        mMax.x += epsAdd;
856                }
857                else
858                {
859                        mMin.x *= epsMul;
860                        mMin.x -= epsAdd;
861                }
862               
863                assert(mMin.x < mMax.x);
864        }
865
866        dir = mMax.y - mMin.y;
867        assert(dir >= 0.f);
868       
869        if (dir < epsMin)
870        {
871                if (mMax.y > 0)
872                {
873                        mMax.y *= epsMul;
874                        mMax.y += epsAdd;
875                }
876                else
877                {
878                        mMin.y *= epsMul;
879                        mMin.y -= epsAdd;
880                }
881                assert(mMin.y < mMax.y);
882        }
883       
884        dir = mMax.z - mMin.z;
885        assert(dir >= 0.f);
886       
887        if (dir < epsMin)
888        {
889                if (mMax.z > 0)
890                {
891                        mMax.z *= epsMul;
892                        mMax.z += epsAdd;
893                }
894                else
895                {
896                        mMin.z *= epsMul;
897                        mMin.z -= epsAdd;
898                }
899               
900                assert(mMin.z < mMax.z);
901        }
902}
903
904
905void AxisAlignedBox3::SetMin(const Vector3 &v)
906{
907        mMin = v;
908}
909
910
911void AxisAlignedBox3::SetMax(const Vector3 &v)
912{
913        mMax = v;
914}
915
916
917void AxisAlignedBox3::SetMin(int axis, const float value)
918{
919        mMin[axis] = value;
920}
921
922
923void AxisAlignedBox3::SetMax(int axis, const float value)
924{
925        mMax[axis] = value;
926}
927
928
929// Decrease box by given splitting plane
930void AxisAlignedBox3::Reduce(int axis, int right, float value)
931{
932        if ((value >=mMin[axis]) && (value <= mMax[axis]))
933        {
934                if (right)
935                        mMin[axis] = value;
936                else
937                        mMax[axis] = value;
938        }
939}
940
941
942Vector3 AxisAlignedBox3::Size() const
943{
944        return mMax - mMin;
945}
946
947
948Vector3 AxisAlignedBox3::GetRandomPoint() const
949{
950        Vector3 size = Size();
951
952        return mMin + Vector3(RandomValue(0.0f, 1.0f),
953                                  RandomValue(0.0f, 1.0f),
954                                                  RandomValue(0.0f, 1.0f)) * Size();
955}
956
957
958bool AxisAlignedBox3::Intersects(const Vector3 &lStart,
959                                                                 const Vector3 &lEnd) const
960{
961        float st, et, fst = 0, fet = 1;
962        float const *bmin = &mMin.x;
963        float const *bmax = &mMax.x;
964        float const *si = &lStart.x;
965        float const *ei = &lEnd.x;
966
967        for (int i = 0; i < 3; ++ i)
968        {
969                if (*si < *ei)
970                {
971                        if (*si > *bmax || *ei < *bmin)
972                                return false;
973
974                        const float di = *ei - *si;
975
976                        st = (*si < *bmin)? (*bmin - *si) / di : 0;
977                        et = (*ei > *bmax)? (*bmax - *si) / di : 1;
978                }
979                else
980                {
981                        if (*ei > *bmax || *si < *bmin)
982                                return false;
983
984                        const float di = *ei - *si;
985
986                        st = (*si > *bmax)? (*bmax - *si) / di : 0;
987                        et = (*ei < *bmin)? (*bmin - *si) / di : 1;
988                }
989
990                if (st > fst) fst = st;
991                if (et < fet) fet = et;
992                if (fet < fst)
993                        return false;
994
995                ++ bmin; ++ bmax;
996                ++ si; ++ ei;
997        }
998
999        //*time = fst;
1000        return true;
1001}
1002
1003
1004Vector3 AxisAlignedBox3::GetVertex(const int N) const
1005{
1006        Vector3 v;
1007        GetVertex(N, v);
1008
1009        return v;
1010}
1011
1012
1013float AxisAlignedBox3::GetExtent(int face) const
1014{
1015        if (face < 3)
1016                return mMin[face];
1017        else
1018                return mMax[face - 3];
1019}
1020
1021
1022int AxisAlignedBox3::GetIndexNearestVertex(const Vector3 &vecPlaneNormal)
1023{
1024        int x, y, z;
1025
1026        x = (vecPlaneNormal.x > 0.0f) ? 0 : 1;
1027        y = (vecPlaneNormal.y > 0.0f) ? 0 : 1;
1028        z = (vecPlaneNormal.z > 0.0f) ? 0 : 1;
1029       
1030        return 4 * x + 2 * y + z;
1031}
1032
1033
1034int AxisAlignedBox3::GetIndexFarthestVertex(const Vector3 &vecPlaneNormal)
1035{
1036        int x, y, z;
1037
1038        x = (vecPlaneNormal.x <= 0.0f) ? 0 : 1;
1039        y = (vecPlaneNormal.y <= 0.0f) ? 0 : 1;
1040        z = (vecPlaneNormal.z <= 0.0f) ? 0 : 1;
1041       
1042        return 4 * x + 2 * y + z;
1043}
1044
1045
1046float AxisAlignedBox3::GetDistance(int index, const Plane3 &plane) const
1047{
1048        return plane.Distance(GetVertex(index));
1049}
1050
1051
1052float AxisAlignedBox3::GetMinDistance(const Plane3 &near) const
1053{
1054        return  near.mNormal.x * ((near.mNormal.x > 0.0f) ? mMin.x : mMax.x) +
1055                        near.mNormal.y * ((near.mNormal.y > 0.0f) ? mMin.y : mMax.y) +
1056                        near.mNormal.z * ((near.mNormal.z > 0.0f) ? mMin.z : mMax.z) +
1057                        near.mD;
1058}
1059
1060
1061float AxisAlignedBox3::GetMaxDistance(const Plane3 &near) const
1062{
1063        return  near.mNormal.x * ((near.mNormal.x <= 0.0f) ? mMin.x : mMax.x) +
1064                        near.mNormal.y * ((near.mNormal.y <= 0.0f) ? mMin.y : mMax.y) +
1065                        near.mNormal.z * ((near.mNormal.z <= 0.0f) ? mMin.z : mMax.z) +
1066                        near.mD;
1067}
1068
1069
1070struct VertexData
1071{
1072        Vector3 mVertex;
1073        float mAngle;
1074       
1075        VertexData(Vector3 vtx, float angle): mVertex(vtx), mAngle(angle)
1076        {}
1077
1078        bool operator<(const VertexData &b) const
1079        {
1080                return mAngle > b.mAngle;
1081        }
1082};
1083
1084// TODO: use a table to avoid normal and distance computations
1085Polygon3 *AxisAlignedBox3::CrossSection(const Plane3 &plane) const
1086{
1087        Polygon3 *planePoly = new Polygon3();
1088       
1089        int side[8];
1090        bool onFrontSide = false, onBackSide = false;
1091       
1092        Vector3 vtx;
1093       
1094        //////////////
1095        //-- compute classification of vertices
1096
1097        for (int i = 0; i < 8; ++i)
1098        {
1099                GetVertex(i, vtx);
1100                side[i] = plane.Side(vtx);
1101                if (side[i] > 0)
1102                        onFrontSide = true;
1103                else if (side[i] < 0)
1104                        onBackSide = true;
1105                else // vertex coincident => push_back
1106                        planePoly->mVertices.push_back(vtx);
1107        }
1108
1109        ///////////
1110        //-- find intersections
1111
1112        if (onFrontSide && onBackSide)
1113        {
1114                Vector3 ptA, ptB;
1115                for (int i = 0; i < 12; ++ i)
1116                {
1117                        int aIdx, bIdx;
1118                        GetEdge(i, aIdx, bIdx);
1119
1120                        ptA = GetVertex(aIdx);
1121                        ptB = GetVertex(bIdx);
1122
1123                        int sideA = side[aIdx];
1124                        int sideB = side[bIdx];
1125
1126                        if (((sideA > 0) && (sideB < 0)) || (sideA < 0) && (sideB > 0))
1127                                planePoly->mVertices.push_back(plane.FindIntersection(ptA, ptB));       
1128                }
1129        }
1130
1131        // order intersections 
1132        if (planePoly->mVertices.size() > 3)
1133        {
1134                Vector3 centerOfMass(0);
1135
1136                int i;
1137                // compute center of mass
1138                for (i = 0; i < (int)planePoly->mVertices.size(); ++ i)
1139                        centerOfMass += planePoly->mVertices[i];
1140               
1141                centerOfMass /= (float)planePoly->mVertices.size();
1142
1143                vector<VertexData> vertexData;
1144                Vector3 refVec = Normalize(centerOfMass - planePoly->mVertices[0]);
1145
1146                // compute angle to reference point
1147                for (i = 1; i < (int)planePoly->mVertices.size(); ++ i)
1148                {
1149                    float angle =
1150                      Angle(refVec, centerOfMass - planePoly->mVertices[i], plane.mNormal);
1151                   
1152                    vertexData.push_back(VertexData(planePoly->mVertices[i], angle));
1153                }
1154               
1155                std::stable_sort(vertexData.begin(), vertexData.end());
1156
1157                // update vertices
1158                for (i = 1; i < (int)planePoly->mVertices.size(); ++ i)
1159                        planePoly->mVertices[i] = vertexData[i - 1].mVertex;
1160        }
1161        else if (planePoly->mVertices.size() == 3)
1162        {
1163                // fix orientation if needed
1164                if (DotProd(planePoly->GetNormal(), plane.mNormal) < 0)
1165                {
1166                        Vector3 v = planePoly->mVertices[1];
1167                        planePoly->mVertices[1] = planePoly->mVertices[2];
1168                        planePoly->mVertices[2] = v;
1169                }
1170        }
1171       
1172        return planePoly;
1173}
1174
1175
1176Plane3 AxisAlignedBox3::GetPlane(int face) const
1177{
1178        switch (face)
1179        {
1180        case 0:
1181                return Plane3(Vector3(0, -1, 0), mMin);
1182        case 1:
1183                return Plane3(Vector3(0, 1, 0), mMax);
1184        case 2:
1185                return Plane3(Vector3(-1, 0, 0), mMin);
1186        case 3:
1187                return Plane3(Vector3(1, 0, 0), mMax);
1188        case 4:
1189                return Plane3(Vector3(0, 0, -1), mMin);
1190        case 5:
1191                return Plane3(Vector3(0, 0, 1), mMax);
1192        }
1193
1194        // should not come here
1195        return Plane3();
1196}
1197
1198
1199/*int AxisAlignedBox3::Side(const Plane3 &plane) const
1200{
1201        Vector3 v;
1202        int i, m=3, M=-3, s;
1203
1204        for (i=0;i<8;i++)
1205        {
1206                GetVertex(i, v);
1207       
1208                if((s = plane.Side(v)) < m) m=s;
1209                if(s > M) M=s;
1210                if (m && m==-M) return 0;
1211        }
1212
1213        return (m == M) ? m : m + M;
1214}
1215*/
1216
1217int AxisAlignedBox3::Side(const Plane3 &plane) const
1218{
1219        int s = 0;
1220        // if exactly one of the vertices lies on the plane
1221        // and the others are on the same side, the plane is tangent
1222        // to the box on either side and not intersecting
1223        for (int i = 0; i < 8; ++ i)
1224        {
1225                Vector3 pt;
1226                GetVertex(i, pt);
1227
1228                int side = plane.Side(pt);
1229
1230                if (side != 0)
1231                {
1232                        if (side == -s)
1233                                return 0; // sign changed => intersects
1234
1235                        s = side;
1236                }
1237        }
1238
1239        return s;
1240}
1241
1242
1243Polyhedron *AxisAlignedBox3::CalcIntersection(const Polyhedron &polyhedron) const
1244{
1245        Polyhedron *oldPolyhedron = new Polyhedron(polyhedron);
1246        Polyhedron *newPolyhedron = NULL;
1247
1248        for (int i = 0; i < 6; ++ i)
1249        {
1250                newPolyhedron = oldPolyhedron->CalcIntersection(GetPlane(i));
1251
1252                if (!newPolyhedron || !newPolyhedron->Valid())
1253                {
1254                        DEL_PTR(newPolyhedron);
1255                        //cerr << "polyhedron not valid or NULL!" << endl;
1256                        return NULL;   
1257                }
1258
1259                DEL_PTR(oldPolyhedron);
1260                oldPolyhedron = newPolyhedron;
1261        }
1262
1263        return newPolyhedron;
1264}
1265
1266
1267
1268bool AxisAlignedBox3::Intersects(const SimpleRay &ray, float &tnear, float &tfar) const
1269{
1270        tnear = -1e20f;
1271        tfar = 1e20f;
1272
1273        const Vector3 origin = ray.mOrigin;
1274        const Vector3 dir = ray.mDirection;
1275
1276        float t1, t2;
1277
1278        // ray is parallel to the planes
1279        if (dir.x == 0)
1280        {
1281                if ((origin.x < mMin.x) || (origin.x > mMax.x))
1282                        return false; // origin not between planes
1283        }
1284        else
1285        {
1286                // time at which ray intersects minimum X plane
1287                t1 = (mMin.x - origin.x) / dir.x;
1288                // time at which ray intersects maximum X plane
1289                t2 = (mMax.x - origin.x) / dir.x;
1290               
1291                if (t1 > t2)
1292                        swap(t1, t2);
1293               
1294                if (t1 > tnear)
1295                        tnear = t1;
1296               
1297                if (t2 < tfar)
1298                        tfar = t2;
1299               
1300                if (tnear > tfar)
1301                        return false;
1302               
1303                if (tfar < 0)
1304                        return false;
1305        }
1306
1307        if (dir.y == 0) // ray is parallel to the planes
1308        {
1309                if ((origin.y < mMin.y) || (origin.y > mMax.y))
1310                        return false; // origin not between planes)
1311        }
1312        else
1313        {
1314                t1 = (mMin.y - origin.y) / dir.y;
1315                t2 = (mMax.y - origin.y) / dir.y;
1316               
1317                if (t1 > t2)
1318                        swap(t1, t2);
1319               
1320                if (t1 > tnear)
1321                        tnear = t1;
1322               
1323                if (t2 < tfar)
1324                        tfar = t2;
1325               
1326                if (tnear > tfar)
1327                        return false;
1328               
1329                if (tfar < 0)
1330                        return false;
1331        }
1332
1333        if (dir.z == 0) // ray is parallel to the planes
1334        {
1335                if ((origin.z < mMin.z) || (origin.z > mMax.z))
1336                        return false; // origin not between planes)
1337        }
1338        else
1339        {
1340                t1 = (mMin.z - origin.z) / dir.z;
1341                t2 = (mMax.z - origin.z) / dir.z;
1342               
1343                if (t1 > t2)
1344                        swap(t1, t2);
1345               
1346                if (t1 > tnear)
1347                        tnear = t1;
1348               
1349                if (t2 < tfar)
1350                        tfar = t2;
1351               
1352                if (tnear > tfar)
1353                        return false;
1354               
1355                if (tfar < 0)
1356                        return false;
1357        }
1358
1359        return true;
1360}
1361
1362
1363void AxisAlignedBox3::ExtractPolygons(PolygonContainer &polys) const
1364{
1365        Polygon3 *face1 = new Polygon3();
1366        polys.push_back(face1);   
1367
1368    face1->mVertices.push_back(Vector3(mMin.x, mMin.y, mMax.z));
1369        face1->mVertices.push_back(Vector3(mMin.x, mMax.y, mMax.z));
1370        face1->mVertices.push_back(Vector3(mMin.x, mMax.y ,mMin.z));
1371        face1->mVertices.push_back(Vector3(mMin.x, mMin.y, mMin.z));
1372
1373        Polygon3 *face2 = new Polygon3(); 
1374        polys.push_back(face2);
1375   
1376    face2->mVertices.push_back(Vector3(mMax.x, mMin.y, mMin.z));
1377    face2->mVertices.push_back(Vector3(mMax.x, mMax.y, mMin.z));
1378    face2->mVertices.push_back(Vector3(mMax.x, mMax.y, mMax.z));
1379    face2->mVertices.push_back(Vector3(mMax.x, mMin.y, mMax.z));
1380 
1381        Polygon3 *face3 = new Polygon3(); 
1382        polys.push_back(face3);
1383
1384    face3->mVertices.push_back(Vector3(mMax.x, mMin.y ,mMin.z));
1385        face3->mVertices.push_back(Vector3(mMax.x, mMin.y, mMax.z));
1386        face3->mVertices.push_back(Vector3(mMin.x, mMin.y, mMax.z));
1387        face3->mVertices.push_back(Vector3(mMin.x, mMin.y, mMin.z));
1388
1389        Polygon3 *face4 = new Polygon3(); 
1390        polys.push_back(face4);
1391
1392        face4->mVertices.push_back(Vector3(mMin.x, mMax.y, mMin.z));
1393        face4->mVertices.push_back(Vector3(mMin.x, mMax.y, mMax.z));
1394        face4->mVertices.push_back(Vector3(mMax.x, mMax.y, mMax.z));
1395        face4->mVertices.push_back(Vector3(mMax.x, mMax.y, mMin.z));
1396   
1397        Polygon3 *face5 = new Polygon3(); 
1398        polys.push_back(face5);
1399
1400        face5->mVertices.push_back(Vector3(mMin.x, mMax.y, mMin.z));
1401    face5->mVertices.push_back(Vector3(mMax.x, mMax.y, mMin.z));
1402    face5->mVertices.push_back(Vector3(mMax.x, mMin.y, mMin.z));
1403        face5->mVertices.push_back(Vector3(mMin.x, mMin.y, mMin.z));
1404
1405        Polygon3 *face6 = new Polygon3(); 
1406        polys.push_back(face6); 
1407 
1408    face6->mVertices.push_back(Vector3(mMin.x, mMin.y, mMax.z));
1409    face6->mVertices.push_back(Vector3(mMax.x, mMin.y, mMax.z));
1410    face6->mVertices.push_back(Vector3(mMax.x, mMax.y, mMax.z));
1411    face6->mVertices.push_back(Vector3(mMin.x, mMax.y, mMax.z));
1412}
1413
1414
1415void AxisAlignedBox3::Triangulate(std::vector<Triangle3> &triangles) const
1416{
1417        Triangle3 tri;
1418
1419        tri.mVertices[0] = Vector3(mMin.x, mMax.y ,mMin.z);
1420        tri.mVertices[1] = Vector3(mMin.x, mMax.y, mMax.z);
1421        tri.mVertices[2] = Vector3(mMin.x, mMin.y, mMax.z);
1422
1423        triangles.push_back(tri);
1424
1425    tri.mVertices[0] = Vector3(mMin.x, mMin.y, mMax.z);
1426        tri.mVertices[1] = Vector3(mMin.x, mMin.y, mMin.z);
1427        tri.mVertices[2] = Vector3(mMin.x, mMax.y ,mMin.z);
1428
1429        triangles.push_back(tri);
1430
1431        //////////////////////////////////////
1432
1433    tri.mVertices[0] = Vector3(mMax.x, mMax.y, mMax.z);
1434    tri.mVertices[1] = Vector3(mMax.x, mMax.y, mMin.z);
1435        tri.mVertices[2] = Vector3(mMax.x, mMin.y, mMin.z);
1436
1437        triangles.push_back(tri);
1438
1439        tri.mVertices[0] = Vector3(mMax.x, mMin.y, mMin.z);
1440        tri.mVertices[1] = Vector3(mMax.x, mMin.y, mMax.z);
1441    tri.mVertices[2] = Vector3(mMax.x, mMax.y, mMax.z);
1442
1443        triangles.push_back(tri);
1444
1445
1446        //////////////////////////////////////
1447
1448        tri.mVertices[0] = Vector3(mMin.x, mMin.y, mMax.z);
1449        tri.mVertices[1] = Vector3(mMax.x, mMin.y, mMax.z);
1450    tri.mVertices[2] = Vector3(mMax.x, mMin.y ,mMin.z);
1451
1452        triangles.push_back(tri);
1453
1454    tri.mVertices[0] = Vector3(mMax.x, mMin.y ,mMin.z);
1455        tri.mVertices[1] = Vector3(mMin.x, mMin.y, mMin.z);
1456        tri.mVertices[2] = Vector3(mMin.x, mMin.y, mMax.z);     
1457
1458        triangles.push_back(tri);
1459
1460
1461        //////////////////////////////////////
1462
1463        tri.mVertices[0] = Vector3(mMax.x, mMax.y, mMax.z);
1464        tri.mVertices[1] = Vector3(mMin.x, mMax.y, mMax.z);
1465        tri.mVertices[2] = Vector3(mMin.x, mMax.y, mMin.z);
1466
1467        triangles.push_back(tri);
1468
1469        tri.mVertices[0] = Vector3(mMin.x, mMax.y, mMin.z);
1470        tri.mVertices[1] = Vector3(mMax.x, mMax.y, mMin.z);
1471        tri.mVertices[2] = Vector3(mMax.x, mMax.y, mMax.z);
1472   
1473        triangles.push_back(tri);
1474
1475
1476        //////////////////////////////////////
1477
1478    tri.mVertices[0] = Vector3(mMax.x, mMin.y, mMin.z);
1479        tri.mVertices[1] = Vector3(mMax.x, mMax.y, mMin.z);
1480        tri.mVertices[2] = Vector3(mMin.x, mMax.y, mMin.z);
1481           
1482        triangles.push_back(tri);
1483
1484        tri.mVertices[0] = Vector3(mMin.x, mMax.y, mMin.z);
1485        tri.mVertices[1] = Vector3(mMin.x, mMin.y, mMin.z);
1486    tri.mVertices[2] = Vector3(mMax.x, mMin.y, mMin.z);
1487           
1488        triangles.push_back(tri);
1489
1490
1491        //////////////////////////////////////
1492
1493    tri.mVertices[0] = Vector3(mMax.x, mMax.y, mMax.z);
1494        tri.mVertices[1] = Vector3(mMax.x, mMin.y, mMax.z);
1495    tri.mVertices[2] = Vector3(mMin.x, mMin.y, mMax.z);
1496
1497        triangles.push_back(tri);
1498
1499    tri.mVertices[0] = Vector3(mMin.x, mMin.y, mMax.z);
1500    tri.mVertices[1] = Vector3(mMin.x, mMax.y, mMax.z);
1501    tri.mVertices[2] = Vector3(mMax.x, mMax.y, mMax.z);
1502           
1503        triangles.push_back(tri);
1504}
1505
1506
1507int AxisAlignedBox3::MajorAxis() const
1508{
1509        const Vector3 sizeVec = mMax - mMin;
1510
1511        int axis;
1512
1513        if (sizeVec.x > sizeVec.y) axis = (sizeVec.x > sizeVec.z) ? 0 : 2;
1514        else axis = (sizeVec.y > sizeVec.z) ? 1 : 2;
1515
1516        return axis;
1517}
1518
1519
1520}
1521
Note: See TracBrowser for help on using the repository browser.