OPCODE/Ice/IceAABB.cpp

   1 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
   2 /**
   3  *      Contains AABB-related code.
   4  *      \file           IceAABB.cpp
   5  *      \author         Pierre Terdiman
   6  *      \date           January, 29, 2000
   7  */
   8 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
   9
  10 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  11 /**
  12  *      AABB class.
  13  *      \class          AABB
  14  *      \author         Pierre Terdiman
  15  *      \version        1.0
  16  */
  17 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  18
  19 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  20 // Precompiled Header
  21 #include "Stdafx.h"
  22
  23 using namespace IceMaths;
  24
  25 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  26 /**
  27  *      Computes the sum of two AABBs.
  28  *      \param          aabb    [in] the other AABB
  29  *      \return         Self-Reference
  30  */
  31 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  32 AABB& AABB::Add(const AABB& aabb)
  33 {
  34         // Compute new min & max values
  35         Point Min;      GetMin(Min);
  36         Point Tmp;      aabb.GetMin(Tmp);
  37         Min.Min(Tmp);
  38
  39         Point Max;      GetMax(Max);
  40         aabb.GetMax(Tmp);
  41         Max.Max(Tmp);
  42
  43         // Update this
  44         SetMinMax(Min, Max);
  45         return *this;
  46 }
  47
  48 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  49 /**
  50  *      Makes a cube from the AABB.
  51  *      \param          cube    [out] the cube AABB
  52  *      \return         cube edge length
  53  */
  54 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  55 float AABB::MakeCube(AABB& cube) const
  56 {
  57         Point Ext;      GetExtents(Ext);
  58         float Max = Ext.Max();
  59
  60         Point Cnt;      GetCenter(Cnt);
  61         cube.SetCenterExtents(Cnt, Point(Max, Max, Max));
  62         return Max;
  63 }
  64
  65 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  66 /**
  67  *      Makes a sphere from the AABB.
  68  *      \param          sphere  [out] sphere containing the AABB
  69  */
  70 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  71 void AABB::MakeSphere(Sphere& sphere) const
  72 {
  73         GetExtents(sphere.mCenter);
  74         sphere.mRadius = sphere.mCenter.Magnitude() * 1.00001f; // To make sure sphere::Contains(*this) succeeds
  75         GetCenter(sphere.mCenter);
  76 }
  77
  78 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  79 /**
  80  *      Checks a box is inside another box.
  81  *      \param          box             [in] the other AABB
  82  *      \return         true if current box is inside input box
  83  */
  84 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  85 bool AABB::IsInside(const AABB& box) const
  86 {
  87         if(box.GetMin(0)>GetMin(0))     return false;
  88         if(box.GetMin(1)>GetMin(1))     return false;
  89         if(box.GetMin(2)>GetMin(2))     return false;
  90         if(box.GetMax(0)<GetMax(0))     return false;
  91         if(box.GetMax(1)<GetMax(1))     return false;
  92         if(box.GetMax(2)<GetMax(2))     return false;
  93         return true;
  94 }
  95
  96 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
  97 /**
  98  *      Computes the AABB planes.
  99  *      \param          planes  [out] 6 planes surrounding the box
 100  *      \return         true if success
 101  */
 102 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 103 bool AABB::ComputePlanes(Plane* planes) const
 104 {
 105         // Checkings
 106         if(!planes)     return false;
 107
 108         Point Center, Extents;
 109         GetCenter(Center);
 110         GetExtents(Extents);
 111
 112         // Writes normals
 113         planes[0].n = Point(1.0f, 0.0f, 0.0f);
 114         planes[1].n = Point(-1.0f, 0.0f, 0.0f);
 115         planes[2].n = Point(0.0f, 1.0f, 0.0f);
 116         planes[3].n = Point(0.0f, -1.0f, 0.0f);
 117         planes[4].n = Point(0.0f, 0.0f, 1.0f);
 118         planes[5].n = Point(0.0f, 0.0f, -1.0f);
 119
 120         // Compute a point on each plane
 121         Point p0 = Point(Center.x+Extents.x, Center.y, Center.z);
 122         Point p1 = Point(Center.x-Extents.x, Center.y, Center.z);
 123         Point p2 = Point(Center.x, Center.y+Extents.y, Center.z);
 124         Point p3 = Point(Center.x, Center.y-Extents.y, Center.z);
 125         Point p4 = Point(Center.x, Center.y, Center.z+Extents.z);
 126         Point p5 = Point(Center.x, Center.y, Center.z-Extents.z);
 127
 128         // Compute d
 129         planes[0].d = -(planes[0].n|p0);
 130         planes[1].d = -(planes[1].n|p1);
 131         planes[2].d = -(planes[2].n|p2);
 132         planes[3].d = -(planes[3].n|p3);
 133         planes[4].d = -(planes[4].n|p4);
 134         planes[5].d = -(planes[5].n|p5);
 135
 136         return true;
 137 }
 138
 139 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 140 /**
 141  *      Computes the aabb points.
 142  *      \param          pts     [out] 8 box points
 143  *      \return         true if success
 144  */
 145 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 146 bool AABB::ComputePoints(Point* pts)    const
 147 {
 148         // Checkings
 149         if(!pts)        return false;
 150
 151         // Get box corners
 152         Point min;      GetMin(min);
 153         Point max;      GetMax(max);
 154
 155         //     7+------+6                       0 = ---
 156         //     /|     /|                        1 = +--
 157         //    / |    / |                        2 = ++-
 158         //   / 4+---/--+5                       3 = -+-
 159         // 3+------+2 /    y   z        4 = --+
 160         //  | /    | /     |  /         5 = +-+
 161         //  |/     |/      |/           6 = +++
 162         // 0+------+1      *---x        7 = -++
 163
 164         // Generate 8 corners of the bbox
 165         pts[0] = Point(min.x, min.y, min.z);
 166         pts[1] = Point(max.x, min.y, min.z);
 167         pts[2] = Point(max.x, max.y, min.z);
 168         pts[3] = Point(min.x, max.y, min.z);
 169         pts[4] = Point(min.x, min.y, max.z);
 170         pts[5] = Point(max.x, min.y, max.z);
 171         pts[6] = Point(max.x, max.y, max.z);
 172         pts[7] = Point(min.x, max.y, max.z);
 173
 174         return true;
 175 }
 176
 177 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 178 /**
 179  *      Gets vertex normals.
 180  *      \param          pts     [out] 8 box points
 181  *      \return         true if success
 182  */
 183 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 184 const Point* AABB::GetVertexNormals()   const
 185 {
 186         static const float VertexNormals[] =
 187         {
 188                 -INVSQRT3,      -INVSQRT3,      -INVSQRT3,
 189                 INVSQRT3,       -INVSQRT3,      -INVSQRT3,
 190                 INVSQRT3,       INVSQRT3,       -INVSQRT3,
 191                 -INVSQRT3,      INVSQRT3,       -INVSQRT3,
 192                 -INVSQRT3,      -INVSQRT3,      INVSQRT3,
 193                 INVSQRT3,       -INVSQRT3,      INVSQRT3,
 194                 INVSQRT3,       INVSQRT3,       INVSQRT3,
 195                 -INVSQRT3,      INVSQRT3,       INVSQRT3
 196         };
 197         return (const Point*)VertexNormals;
 198 }
 199
 200 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 201 /**
 202  *      Returns edges.
 203  *      \return         24 indices (12 edges) indexing the list returned by ComputePoints()
 204  */
 205 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 206 const udword* AABB::GetEdges() const
 207 {
 208         static const udword Indices[] = {
 209         0, 1,   1, 2,   2, 3,   3, 0,
 210         7, 6,   6, 5,   5, 4,   4, 7,
 211         1, 5,   6, 2,
 212         3, 7,   4, 0
 213         };
 214         return Indices;
 215 }
 216
 217 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 218 /**
 219  *      Returns edge normals.
 220  *      \return         edge normals in local space
 221  */
 222 ///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
 223 const Point* AABB::GetEdgeNormals() const
 224 {
 225         static const float EdgeNormals[] =
 226         {
 227                 0,                      -INVSQRT2,      -INVSQRT2,      // 0-1
 228                 INVSQRT2,       0,                      -INVSQRT2,      // 1-2
 229                 0,                      INVSQRT2,       -INVSQRT2,      // 2-3
 230                 -INVSQRT2,      0,                      -INVSQRT2,      // 3-0
 231
 232                 0,                      INVSQRT2,       INVSQRT2,       // 7-6
 233                 INVSQRT2,       0,                      INVSQRT2,       // 6-5
 234                 0,                      -INVSQRT2,      INVSQRT2,       // 5-4
 235                 -INVSQRT2,      0,                      INVSQRT2,       // 4-7
 236
 237                 INVSQRT2,       -INVSQRT2,      0,                      // 1-5
 238                 INVSQRT2,       INVSQRT2,       0,                      // 6-2
 239                 -INVSQRT2,      INVSQRT2,       0,                      // 3-7
 240                 -INVSQRT2,      -INVSQRT2,      0                       // 4-0
 241         };
 242         return (const Point*)EdgeNormals;
 243 }
 244
 245 // ===========================================================================
 246 //  (C) 1996-98 Vienna University of Technology
 247 // ===========================================================================
 248 //  NAME:       bboxarea
 249 //  TYPE:       c++ code
 250 //  PROJECT:    Bounding Box Area
 251 //  CONTENT:    Computes area of 2D projection of 3D oriented bounding box
 252 //  VERSION:    1.0
 253 // ===========================================================================
 254 //  AUTHORS:    ds      Dieter Schmalstieg
 255 //              ep      Erik Pojar
 256 // ===========================================================================
 257 //  HISTORY:
 258 //
 259 //  19-sep-99 15:23:03  ds      last modification
 260 //  01-dec-98 15:23:03  ep      created
 261 // ===========================================================================
 262
 263 //----------------------------------------------------------------------------
 264 // SAMPLE CODE STARTS HERE
 265 //----------------------------------------------------------------------------
 266
 267 // NOTE: This sample program requires OPEN INVENTOR!
 268
 269 //indexlist: this table stores the 64 possible cases of classification of
 270 //the eyepoint with respect to the 6 defining planes of the bbox (2^6=64)
 271 //only 26 (3^3-1, where 1 is "inside" cube) of these cases are valid.
 272 //the first 6 numbers in each row are the indices of the bbox vertices that
 273 //form the outline of which we want to compute the area (counterclockwise
 274 //ordering), the 7th entry means the number of vertices in the outline.
 275 //there are 6 cases with a single face and and a 4-vertex outline, and
 276 //20 cases with 2 or 3 faces and a 6-vertex outline. a value of 0 indicates
 277 //an invalid case.
 278
 279
 280 // Original list was made of 7 items, I added an 8th element:
 281 // - to padd on a cache line
 282 // - to repeat the first entry to avoid modulos
 283 //
 284 // I also replaced original ints with sbytes.
 285
 286 static const sbyte gIndexList[64][8] =
 287 {
 288     {-1,-1,-1,-1,-1,-1,-1,   0}, // 0 inside
 289     { 0, 4, 7, 3, 0,-1,-1,   4}, // 1 left
 290     { 1, 2, 6, 5, 1,-1,-1,   4}, // 2 right
 291     {-1,-1,-1,-1,-1,-1,-1,   0}, // 3 -
 292     { 0, 1, 5, 4, 0,-1,-1,   4}, // 4 bottom
 293     { 0, 1, 5, 4, 7, 3, 0,   6}, // 5 bottom, left
 294     { 0, 1, 2, 6, 5, 4, 0,   6}, // 6 bottom, right
 295     {-1,-1,-1,-1,-1,-1,-1,   0}, // 7 -
 296     { 2, 3, 7, 6, 2,-1,-1,   4}, // 8 top
 297     { 0, 4, 7, 6, 2, 3, 0,   6}, // 9 top, left
 298     { 1, 2, 3, 7, 6, 5, 1,   6}, //10 top, right
 299     {-1,-1,-1,-1,-1,-1,-1,   0}, //11 -
 300     {-1,-1,-1,-1,-1,-1,-1,   0}, //12 -
 301     {-1,-1,-1,-1,-1,-1,-1,   0}, //13 -
 302     {-1,-1,-1,-1,-1,-1,-1,   0}, //14 -
 303     {-1,-1,-1,-1,-1,-1,-1,   0}, //15 -
 304     { 0, 3, 2, 1, 0,-1,-1,   4}, //16 front
 305     { 0, 4, 7, 3, 2, 1, 0,   6}, //17 front, left
 306     { 0, 3, 2, 6, 5, 1, 0,   6}, //18 front, right
 307     {-1,-1,-1,-1,-1,-1,-1,   0}, //19 -
 308     { 0, 3, 2, 1, 5, 4, 0,   6}, //20 front, bottom
 309     { 1, 5, 4, 7, 3, 2, 1,   6}, //21 front, bottom, left
 310     { 0, 3, 2, 6, 5, 4, 0,   6}, //22 front, bottom, right
 311     {-1,-1,-1,-1,-1,-1,-1,   0}, //23 -
 312     { 0, 3, 7, 6, 2, 1, 0,   6}, //24 front, top
 313     { 0, 4, 7, 6, 2, 1, 0,   6}, //25 front, top, left
 314     { 0, 3, 7, 6, 5, 1, 0,   6}, //26 front, top, right
 315     {-1,-1,-1,-1,-1,-1,-1,   0}, //27 -
 316     {-1,-1,-1,-1,-1,-1,-1,   0}, //28 -
 317     {-1,-1,-1,-1,-1,-1,-1,   0}, //29 -
 318     {-1,-1,-1,-1,-1,-1,-1,   0}, //30 -
 319     {-1,-1,-1,-1,-1,-1,-1,   0}, //31 -
 320     { 4, 5, 6, 7, 4,-1,-1,   4}, //32 back
 321     { 0, 4, 5, 6, 7, 3, 0,   6}, //33 back, left
 322     { 1, 2, 6, 7, 4, 5, 1,   6}, //34 back, right
 323     {-1,-1,-1,-1,-1,-1,-1,   0}, //35 -
 324     { 0, 1, 5, 6, 7, 4, 0,   6}, //36 back, bottom
 325     { 0, 1, 5, 6, 7, 3, 0,   6}, //37 back, bottom, left
 326     { 0, 1, 2, 6, 7, 4, 0,   6}, //38 back, bottom, right
 327     {-1,-1,-1,-1,-1,-1,-1,   0}, //39 -
 328     { 2, 3, 7, 4, 5, 6, 2,   6}, //40 back, top
 329     { 0, 4, 5, 6, 2, 3, 0,   6}, //41 back, top, left
 330     { 1, 2, 3, 7, 4, 5, 1,   6}, //42 back, top, right
 331     {-1,-1,-1,-1,-1,-1,-1,   0}, //43 invalid
 332     {-1,-1,-1,-1,-1,-1,-1,   0}, //44 invalid
 333     {-1,-1,-1,-1,-1,-1,-1,   0}, //45 invalid
 334     {-1,-1,-1,-1,-1,-1,-1,   0}, //46 invalid
 335     {-1,-1,-1,-1,-1,-1,-1,   0}, //47 invalid
 336     {-1,-1,-1,-1,-1,-1,-1,   0}, //48 invalid
 337     {-1,-1,-1,-1,-1,-1,-1,   0}, //49 invalid
 338     {-1,-1,-1,-1,-1,-1,-1,   0}, //50 invalid
 339     {-1,-1,-1,-1,-1,-1,-1,   0}, //51 invalid
 340     {-1,-1,-1,-1,-1,-1,-1,   0}, //52 invalid
 341     {-1,-1,-1,-1,-1,-1,-1,   0}, //53 invalid
 342     {-1,-1,-1,-1,-1,-1,-1,   0}, //54 invalid
 343     {-1,-1,-1,-1,-1,-1,-1,   0}, //55 invalid
 344     {-1,-1,-1,-1,-1,-1,-1,   0}, //56 invalid
 345     {-1,-1,-1,-1,-1,-1,-1,   0}, //57 invalid
 346     {-1,-1,-1,-1,-1,-1,-1,   0}, //58 invalid
 347     {-1,-1,-1,-1,-1,-1,-1,   0}, //59 invalid
 348     {-1,-1,-1,-1,-1,-1,-1,   0}, //60 invalid
 349     {-1,-1,-1,-1,-1,-1,-1,   0}, //61 invalid
 350     {-1,-1,-1,-1,-1,-1,-1,   0}, //62 invalid
 351     {-1,-1,-1,-1,-1,-1,-1,   0}  //63 invalid
 352 };
 353
 354 const sbyte* AABB::ComputeOutline(const Point& local_eye, sdword& num)  const
 355 {
 356         // Get box corners
 357         Point min;      GetMin(min);
 358         Point max;      GetMax(max);
 359
 360         // Compute 6-bit code to classify eye with respect to the 6 defining planes of the bbox
 361         int pos = ((local_eye.x < min.x) ?  1 : 0)      // 1 = left
 362                         + ((local_eye.x > max.x) ?  2 : 0)      // 2 = right
 363                         + ((local_eye.y < min.y) ?  4 : 0)      // 4 = bottom
 364                         + ((local_eye.y > max.y) ?  8 : 0)      // 8 = top
 365                         + ((local_eye.z < min.z) ? 16 : 0)      // 16 = front
 366                         + ((local_eye.z > max.z) ? 32 : 0);     // 32 = back
 367
 368         // Look up number of vertices in outline
 369         num = (sdword)gIndexList[pos][7];
 370         // Zero indicates invalid case
 371         if(!num) return null;
 372
 373         return &gIndexList[pos][0];
 374 }
 375
 376 // calculateBoxArea: computes the screen-projected 2D area of an oriented 3D bounding box
 377
 378 //const Point&          eye,            //eye point (in bbox object coordinates)
 379 //const AABB&                   box,            //3d bbox
 380 //const Matrix4x4&      mat,            //free transformation for bbox
 381 //float width, float height, int& num)
 382 float AABB::ComputeBoxArea(const Point& eye, const Matrix4x4& mat, float width, float height, sdword& num)      const
 383 {
 384         const sbyte* Outline = ComputeOutline(eye, num);
 385         if(!Outline)    return -1.0f;
 386
 387         // Compute box vertices
 388         Point vertexBox[8], dst[8];
 389         ComputePoints(vertexBox);
 390
 391         // Transform all outline corners into 2D screen space
 392         for(sdword i=0;i<num;i++)
 393         {
 394                 HPoint Projected;
 395                 vertexBox[Outline[i]].ProjectToScreen(width, height, mat, Projected);
 396                 dst[i] = Projected;
 397         }
 398
 399         float Sum = (dst[num-1][0] - dst[0][0]) * (dst[num-1][1] + dst[0][1]);
 400
 401         for(int i=0; i<num-1; i++)
 402                 Sum += (dst[i][0] - dst[i+1][0]) * (dst[i][1] + dst[i+1][1]);
 403
 404         return Sum * 0.5f;      //return computed value corrected by 0.5
 405 }