AI_BBox.h

Go to the documentation of this file.
00001 #ifndef AI_BBOX_H
00002 #define AI_BBOX_H
00003 //------------------------------------------------------------------------------
00010 #include "AI_Vector.h"
00011 #include "AI_Matrix.h"
00012 #include "AI_Line.h"
00013 
00014 class AI_BBox 
00015 {
00016 public:
00018     enum 
00019     {
00020         ClipLeft   = (1<<0),
00021         ClipRight  = (1<<1),
00022         ClipBottom = (1<<2),
00023         ClipTop    = (1<<3),
00024         ClipNear   = (1<<4),
00025         ClipFar    = (1<<5),
00026     };
00028     enum ClipStatus 
00029     {
00030         Outside,
00031         Inside,
00032         Clipped,
00033     };
00034 
00035     enum {
00036         OUTSIDE     = 0,
00037         ISEQUAL     = (1<<0),
00038         ISCONTAINED = (1<<1),
00039         CONTAINS    = (1<<2),
00040         CLIPS       = (1<<3),
00041     };
00042 
00044     AI_BBox();
00046     AI_BBox(const AI_Vector3& center, const AI_Vector3& extents);
00048     AI_BBox(const AI_Matrix44& m);
00050     AI_Vector3 center() const;
00052     AI_Vector3 extents() const;
00054     AI_Vector3 size() const;
00056     float diagonal_size() const;
00058     void set(const AI_Matrix44& m);
00060     void set(const AI_Vector3& center, const AI_Vector3& extents);
00062     void begin_extend();
00064     void extend(const AI_Vector3& v);
00066     void extend(float x, float y, float z);
00068     void extend(const AI_BBox& box);
00070     void transform(const AI_Matrix44& m);
00072     bool intersects(const AI_BBox& box) const;
00074     bool contains(const AI_BBox& box) const;
00076     bool contains(const AI_Vector3& pos) const;
00078     ClipStatus clipstatus(const AI_BBox& other) const;
00080     ClipStatus clipstatus(const AI_Matrix44& viewProjection) const;  
00081 
00083     AI_Matrix44 to_matrix44() const;
00084 
00085     int line_test(float v0, float v1, float w0, float w1);
00086     int intersect(AI_BBox box);
00087 
00095     bool intersect(const AI_Line3& line, AI_Vector3& ipos) const;
00096 
00097     // get point of intersection of 3d line with planes
00098     // on const x,y,z
00099     bool isect_const_x(const float x, const AI_Line3& l, AI_Vector3& out) const
00100     {
00101         if (l.m.x != 0.0f)
00102         {
00103             float t = (x - l.b.x) / l.m.x;
00104             if ((t>=0.0f) && (t<=1.0f))
00105             {
00106                 // point of intersection...
00107                 out = l.ipol(t);
00108                 return true;
00109             }
00110         }
00111         return false;
00112     }
00113     bool isect_const_y(const float y, const AI_Line3& l, AI_Vector3& out) const
00114     {
00115         if (l.m.y != 0.0f)
00116         {
00117             float t = (y - l.b.y) / l.m.y;
00118             if ((t>=0.0f) && (t<=1.0f))
00119             {
00120                 // point of intersection...
00121                 out = l.ipol(t);
00122                 return true;
00123             }
00124         }
00125         return false;
00126     }
00127     bool isect_const_z(const float z, const AI_Line3& l, AI_Vector3& out) const
00128     {
00129         if (l.m.z != 0.0f)
00130         {
00131             float t = (z - l.b.z) / l.m.z;
00132             if ((t>=0.0f) && (t<=1.0f))
00133             {
00134                 // point of intersection...
00135                 out = l.ipol(t);
00136                 return true;
00137             }
00138         }
00139         return false;
00140     }
00141 
00142     // point in polygon check for sides with constant x,y and z
00143     bool pip_const_x(const AI_Vector3& p) const
00144     {
00145         if ((p.y>=vmin.y)&&(p.y<=vmax.y)&&(p.z>=vmin.z)&&(p.z<=vmax.z)) return true;
00146         else return false;
00147     }
00148     bool pip_const_y(const AI_Vector3& p) const
00149     {
00150         if ((p.x>=vmin.x)&&(p.x<=vmax.x)&&(p.z>=vmin.z)&&(p.z<=vmax.z)) return true;
00151         else return false;
00152     }
00153     bool pip_const_z(const AI_Vector3& p) const
00154     {
00155         if ((p.x>=vmin.x)&&(p.x<=vmax.x)&&(p.y>=vmin.y)&&(p.y<=vmax.y)) return true;
00156         else return false;
00157     }
00158 
00159     AI_Vector3 vmin;
00160     AI_Vector3 vmax;
00161 };
00162 
00163 //------------------------------------------------------------------------------
00166 inline
00167 AI_BBox::AI_BBox()
00168 {
00169     // empty
00170 }
00171 
00172 //------------------------------------------------------------------------------
00175 inline
00176 AI_BBox::AI_BBox(const AI_Vector3& center, const AI_Vector3& extents)
00177 {
00178     vmin = center - extents;
00179     vmax = center + extents;
00180 }
00181 
00182 //------------------------------------------------------------------------------
00188 inline
00189 void
00190 AI_BBox::set(const AI_Matrix44& m)
00191 {
00192     // get extents
00193     float xExtent = ai_max(ai_max(ai_abs(m.m[0][0]), ai_abs(m.m[1][0])), ai_abs(m.m[2][0]));
00194     float yExtent = ai_max(ai_max(ai_abs(m.m[0][1]), ai_abs(m.m[1][1])), ai_abs(m.m[2][1]));
00195     float zExtent = ai_max(ai_max(ai_abs(m.m[0][2]), ai_abs(m.m[1][2])), ai_abs(m.m[2][2]));
00196     AI_Vector3 extent(xExtent, yExtent, zExtent);
00197 
00198     AI_Vector3 center = m.pos_component();
00199     this->vmin = center - extent;
00200     this->vmax = center + extent;
00201 }
00202 //------------------------------------------------------------------------------
00205 inline
00206 AI_BBox::AI_BBox(const AI_Matrix44& m)
00207 {
00208     this->set(m);
00209 }
00210 
00211 //------------------------------------------------------------------------------
00214 inline
00215 AI_Vector3
00216 AI_BBox::center() const
00217 {
00218     return AI_Vector3((vmin + vmax) * 0.5f);
00219 }
00220 
00221 //------------------------------------------------------------------------------
00224 inline
00225 AI_Vector3
00226 AI_BBox::extents() const
00227 {
00228     return AI_Vector3((vmax - vmin) * 0.5f);
00229 }
00230 
00231 //------------------------------------------------------------------------------
00234 inline
00235 AI_Vector3
00236 AI_BBox::size() const
00237 {
00238     return AI_Vector3(vmax - vmin);
00239 }
00240 
00241 //------------------------------------------------------------------------------
00244 inline
00245 void
00246 AI_BBox::set(const AI_Vector3& center, const AI_Vector3& extents)
00247 {
00248     vmin = center - extents;
00249     vmax = center + extents;
00250 }
00251 
00252 //------------------------------------------------------------------------------
00255 inline
00256 void
00257 AI_BBox::begin_extend()
00258 {
00259     vmin.set(+1000000.0f,+1000000.0f,+1000000.0f);
00260     vmax.set(-1000000.0f,-1000000.0f,-1000000.0f);
00261 }
00262 
00263 //------------------------------------------------------------------------------
00266 inline
00267 void
00268 AI_BBox::extend(const AI_Vector3& v)
00269 {
00270     if (v.x < vmin.x) vmin.x = v.x;
00271     if (v.x > vmax.x) vmax.x = v.x;
00272     if (v.y < vmin.y) vmin.y = v.y;
00273     if (v.y > vmax.y) vmax.y = v.y;
00274     if (v.z < vmin.z) vmin.z = v.z;
00275     if (v.z > vmax.z) vmax.z = v.z;
00276 }
00277 
00278 //------------------------------------------------------------------------------
00281 inline
00282 void
00283 AI_BBox::extend(float x, float y, float z)
00284 {
00285     if (x < vmin.x) vmin.x = x;
00286     if (x > vmax.x) vmax.x = x;
00287     if (y < vmin.y) vmin.y = y;
00288     if (y > vmax.y) vmax.y = y;
00289     if (z < vmin.z) vmin.z = z;
00290     if (z > vmax.z) vmax.z = z;
00291 }
00292 
00293 //------------------------------------------------------------------------------
00296 inline
00297 void
00298 AI_BBox::extend(const AI_BBox& box)
00299 {
00300     if (box.vmin.x < vmin.x) vmin.x = box.vmin.x;
00301     if (box.vmin.y < vmin.y) vmin.y = box.vmin.y;
00302     if (box.vmin.z < vmin.z) vmin.z = box.vmin.z;
00303     if (box.vmax.x > vmax.x) vmax.x = box.vmax.x;
00304     if (box.vmax.y > vmax.y) vmax.y = box.vmax.y;
00305     if (box.vmax.z > vmax.z) vmax.z = box.vmax.z;
00306 }
00307 
00308 //------------------------------------------------------------------------------
00321 inline
00322 void
00323 AI_BBox::transform(const AI_Matrix44& m)
00324 {
00325     /*  ?? BUG ??
00326     // get own extents vector
00327     AI_Vector3 extents = this->extents();
00328     AI_Vector3 center  = this->center();
00329 
00330     // Extent the matrix' (x,y,z) components by our own extent
00331     // vector. 
00332     AI_Matrix44 extentMatrix(
00333         m.m[0][0] * extents.x, m.m[0][1] * extents.x, m.m[0][2] * extents.x, 0.0f,
00334         m.m[1][0] * extents.y, m.m[1][1] * extents.y, m.m[1][2] * extents.y, 0.0f,
00335         m.m[2][0] * extents.z, m.m[2][1] * extents.z, m.m[2][2] * extents.z, 0.0f,
00336         m.m[3][0] + center.x,  m.m[3][1] + center.y,  m.m[3][2] + center.z,  1.0f);
00337 
00338     this->set(extentMatrix);
00339     */
00340 
00341     AI_Vector3 temp, min, max, corners[8];
00342     bool first = true;
00343     int i;
00344         
00345     corners[0]   = this->vmin;
00346     corners[1].x = this->vmin.x; corners[1].y = this->vmax.y; corners[1].z = this->vmin.z;
00347     corners[2].x = this->vmax.x; corners[2].y = this->vmax.y; corners[2].z = this->vmin.z;
00348     corners[3].x = this->vmax.x; corners[3].y = this->vmin.y; corners[3].z = this->vmin.z;            
00349     corners[4]   = this->vmax;
00350     corners[5].x = this->vmin.x; corners[5].y = this->vmax.y; corners[5].z = this->vmax.z;
00351     corners[6].x = this->vmin.x; corners[6].y = this->vmin.y; corners[6].z = this->vmax.z;
00352     corners[7].x = this->vmax.x; corners[7].y = this->vmin.y; corners[7].z = this->vmax.z;
00353 
00354     for(i = 0; i < 8; ++i)
00355     {
00356         // Transform and check extents
00357         temp = m * corners[i];
00358         if( first || temp.x > max.x )   max.x = temp.x;
00359         if( first || temp.y > max.y )   max.y = temp.y;
00360         if( first || temp.z > max.z )   max.z = temp.z;
00361         if( first || temp.x < min.x )   min.x = temp.x;
00362         if( first || temp.y < min.y )   min.y = temp.y;
00363         if( first || temp.z < min.z )   min.z = temp.z;
00364         first = false;
00365 }
00366 
00367     this->vmin = min;
00368     this->vmax = max;
00369 }
00370 
00371 //------------------------------------------------------------------------------
00376 inline
00377 bool
00378 AI_BBox::intersects(const AI_BBox& box) const
00379 {
00380     if ((this->vmax.x < box.vmin.x) ||
00381         (this->vmin.x > box.vmax.x) ||
00382         (this->vmax.y < box.vmin.y) ||
00383         (this->vmin.y > box.vmax.y) ||
00384         (this->vmax.z < box.vmin.z) ||
00385         (this->vmin.z > box.vmax.z))
00386     {
00387         return false;
00388     }
00389     return true;
00390 }
00391 
00392 //------------------------------------------------------------------------------
00397 inline
00398 bool
00399 AI_BBox::contains(const AI_BBox& box) const
00400 {
00401     if ((this->vmin.x < box.vmin.x) && (this->vmax.x >= box.vmax.x) &&
00402         (this->vmin.y < box.vmin.y) && (this->vmax.y >= box.vmax.y) &&
00403         (this->vmin.z < box.vmin.z) && (this->vmax.z >= box.vmax.z))
00404     {
00405         return true;
00406     }
00407     return false;
00408 }
00409 
00410 //------------------------------------------------------------------------------
00414 inline
00415 bool
00416 AI_BBox::contains(const AI_Vector3& v) const
00417 {
00418     if ((this->vmin.x < v.x) && (this->vmax.x >= v.x) &&
00419         (this->vmin.y < v.y) && (this->vmax.y >= v.y) &&
00420         (this->vmin.z < v.z) && (this->vmax.z >= v.z))
00421     {
00422         return true;
00423     }
00424     return false;
00425 }
00426 
00427 //------------------------------------------------------------------------------
00431 inline
00432 AI_BBox::ClipStatus
00433 AI_BBox::clipstatus(const AI_BBox& other) const
00434 {
00435     if (this->contains(other))
00436     {
00437         return Inside;
00438     }
00439     else if (this->intersects(other))
00440     {
00441         return Clipped;
00442     }
00443     else 
00444     {
00445         return Outside;
00446     }
00447 }
00448 
00449 //------------------------------------------------------------------------------
00454 inline
00455 AI_BBox::ClipStatus
00456 AI_BBox::clipstatus(const AI_Matrix44& viewProjection) const
00457 {
00458     int andFlags = 0xffff;
00459     int orFlags  = 0;
00460     int i;
00461     static AI_Vector4 v0;
00462     static AI_Vector4 v1;
00463     for (i = 0; i < 8; i++)
00464     {
00465         int clip = 0;
00466         v0.w = 1.0f;
00467         if (i & 1) v0.x = this->vmin.x;
00468         else       v0.x = this->vmax.x;
00469         if (i & 2) v0.y = this->vmin.y;
00470         else       v0.y = this->vmax.y;
00471         if (i & 4) v0.z = this->vmin.z;
00472         else       v0.z = this->vmax.z;
00473 
00474         v1 = viewProjection * v0;
00475 
00476         if (v1.x < -v1.w)       clip |= ClipLeft;
00477         else if (v1.x > v1.w)   clip |= ClipRight;
00478         if (v1.y < -v1.w)       clip |= ClipBottom;
00479         else if (v1.y > v1.w)   clip |= ClipTop;
00480         if (v1.z < -v1.w)       clip |= ClipFar;
00481         else if (v1.z > v1.w)   clip |= ClipNear;
00482         andFlags &= clip;
00483         orFlags  |= clip;
00484     }
00485     if (0 == orFlags)       return Inside;
00486     else if (0 != andFlags) return Outside;
00487     else                    return Clipped;
00488 }
00489 
00490 //------------------------------------------------------------------------------
00495 inline
00496 AI_Matrix44
00497 AI_BBox::to_matrix44() const
00498 {
00499     AI_Matrix44 m;
00500     m.scale(this->size());
00501     m.translate(this->center());
00502     return m;
00503 }
00504 
00505 //------------------------------------------------------------------------------
00513 inline bool AI_BBox::intersect(const AI_Line3& line, AI_Vector3& ipos) const
00514 {
00515     // Handle special case for start point inside box
00516     if (line.b.x >= vmin.x && line.b.y >= vmin.y && line.b.z >= vmin.z &&
00517         line.b.x <= vmax.x && line.b.y <= vmax.y && line.b.z <= vmax.z)
00518     {
00519         ipos = line.b;
00520         return true;
00521     }
00522 
00523     // Order planes to check, closest three only
00524     int AI_Plane[3];
00525     if (line.m.x > 0) AI_Plane[0] = 0;
00526     else              AI_Plane[0] = 1;
00527     if (line.m.y > 0) AI_Plane[1] = 2;
00528     else              AI_Plane[1] = 3;
00529     if (line.m.z > 0) AI_Plane[2] = 4;
00530     else              AI_Plane[2] = 5;
00531 
00532     for (int i = 0; i < 3; ++i)
00533     {
00534         switch (AI_Plane[i])
00535         {
00536             case 0:
00537                 if (isect_const_x(vmin.x,line,ipos) && pip_const_x(ipos)) return true;
00538                 break;
00539             case 1:
00540                 if (isect_const_x(vmax.x,line,ipos) && pip_const_x(ipos)) return true;
00541                 break;
00542             case 2:
00543                 if (isect_const_y(vmin.y,line,ipos) && pip_const_y(ipos)) return true;
00544                 break;
00545             case 3:
00546                 if (isect_const_y(vmax.y,line,ipos) && pip_const_y(ipos)) return true;
00547                 break;
00548             case 4:
00549                 if (isect_const_z(vmin.z,line,ipos) && pip_const_z(ipos)) return true;
00550                 break;
00551             case 5:
00552                 if (isect_const_z(vmax.z,line,ipos) && pip_const_z(ipos)) return true;
00553                 break;
00554         }
00555     }
00556 
00557     return false;
00558 }
00559 
00560 //------------------------------------------------------------------------------
00566 inline
00567 int AI_BBox::line_test(float v0, float v1, float w0, float w1)
00568 {
00569     // quick rejection test
00570     if ((v1<w0) || (v0>w1)) return OUTSIDE;
00571     else if ((v0==w0) && (v1==w1)) return ISEQUAL;
00572     else if ((v0>=w0) && (v1<=w1)) return ISCONTAINED;
00573     else if ((v0<=w0) && (v1>=w1)) return CONTAINS;
00574     else return CLIPS;
00575 }
00576 
00577 inline
00578 int AI_BBox::intersect(AI_BBox box)
00579 {
00580     int and_code = 0xffff;
00581     int or_code  = 0;
00582     int cx,cy,cz;
00583     cx = line_test(vmin.x,vmax.x,box.vmin.x,box.vmax.x);
00584     and_code&=cx; or_code|=cx;
00585     cy = line_test(vmin.y,vmax.y,box.vmin.y,box.vmax.y);
00586     and_code&=cy; or_code|=cy;
00587     cz = line_test(vmin.z,vmax.z,box.vmin.z,box.vmax.z);
00588     and_code&=cz; or_code|=cz;
00589     if (or_code == 0) return OUTSIDE;
00590     else if (and_code != 0) {
00591         return and_code;
00592     } else {
00593         // only if all test produced a non-outside result,
00594         // an intersection has occured
00595         if (cx && cy && cz) return CLIPS;
00596         else                return OUTSIDE;
00597     }
00598 }
00599 
00602 inline
00603 float
00604 AI_BBox::diagonal_size() const
00605 {
00606     return AI_Vector3::distance(this->vmin, this->vmax);
00607 }
00608 
00609 
00610 //------------------------------------------------------------------------------
00611 #endif