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

Revision 3202, 39.9 KB checked in by mattausch, 16 years ago (diff)

finally found bvh tighter bounds bug

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