CrystalSpace

Public API Reference

Main Page   Modules   Class Hierarchy   Alphabetical List   Compound List   File List   Compound Members   File Members   Related Pages  

csgeom/box.h

Go to the documentation of this file.
00001 /*
00002     Copyright (C) 1998-2002 by Jorrit Tyberghein
00003     Largely rewritten by Ivan Avramovic <ivan@avramovic.com>
00004 
00005     This library is free software; you can redistribute it and/or
00006     modify it under the terms of the GNU Library General Public
00007     License as published by the Free Software Foundation; either
00008     version 2 of the License, or (at your option) any later version.
00009 
00010     This library is distributed in the hope that it will be useful,
00011     but WITHOUT ANY WARRANTY; without even the implied warranty of
00012     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00013     Library General Public License for more details.
00014 
00015     You should have received a copy of the GNU Library General Public
00016     License along with this library; if not, write to the Free
00017     Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00018 */
00019 
00020 #ifndef __CS_BOX_H__
00021 #define __CS_BOX_H__
00022 
00030 #include "cstypes.h"    // for bool
00031 #include "vector2.h"
00032 #include "vector3.h"
00033 #include "segment.h"
00034 
00035 class csPlane3;
00036 class csTransform;
00037 class csPoly2D;
00038 
00043 #define CS_BOUNDINGBOX_MAXVALUE 1000000000.
00044 
00048 
00049 #define CS_BOX_CORNER_xy 0
00050 
00051 #define CS_BOX_CORNER_xY 1
00052 
00053 #define CS_BOX_CORNER_Xy 2
00054 
00055 #define CS_BOX_CORNER_XY 3
00056 
00057 #define CS_BOX_CENTER2 4
00058 
00064 
00065 #define CS_BOX_EDGE_xy_Xy 0
00066 
00067 #define CS_BOX_EDGE_Xy_xy 1
00068 
00069 #define CS_BOX_EDGE_Xy_XY 2
00070 
00071 #define CS_BOX_EDGE_XY_Xy 3
00072 
00073 #define CS_BOX_EDGE_XY_xY 4
00074 
00075 #define CS_BOX_EDGE_xY_XY 5
00076 
00077 #define CS_BOX_EDGE_xY_xy 6
00078 
00079 #define CS_BOX_EDGE_xy_xY 7
00080 
00089 class csBox2
00090 {
00091 private:
00092   struct bEdge
00093   {
00094     uint8 v1, v2;       // Indices of vertex in bounding box (CS_BOX_CORNER_...)
00095   };
00096   // Index by edge number. Edge e and e+1 with e even are opposite edges.
00097   // (CS_BOX_EDGE_...)
00098   static bEdge edges[8];
00099 
00100 protected:
00102   csVector2 minbox;
00104   csVector2 maxbox;
00105 
00106 public:
00108   float MinX () const { return minbox.x; }
00110   float MinY () const { return minbox.y; }
00112   float MaxX () const { return maxbox.x; }
00114   float MaxY () const { return maxbox.y; }
00116   float Min (int idx) const { return idx ? minbox.y : minbox.x; }
00118   float Max (int idx) const { return idx ? maxbox.y : maxbox.x; }
00120   const csVector2& Min () const { return minbox; }
00122   const csVector2& Max () const { return maxbox; }
00123 
00132   csVector2 GetCorner (int corner) const;
00133 
00137   csVector2 GetCenter () const { return (minbox+maxbox)/2; }
00138 
00143   void SetCenter (const csVector2& c);
00144 
00148   void SetSize (const csVector2& s);
00149 
00154   void GetEdgeInfo (int edge, int& v1, int& v2) const
00155   {
00156     v1 = edges[edge].v1;
00157     v2 = edges[edge].v2;
00158   }
00159 
00164   csSegment2 GetEdge (int edge) const
00165   {
00166     return csSegment2 (GetCorner (edges[edge].v1), GetCorner (edges[edge].v2));
00167   }
00168 
00173   void GetEdge (int edge, csSegment2& e) const
00174   {
00175     e.SetStart (GetCorner (edges[edge].v1));
00176     e.SetEnd (GetCorner (edges[edge].v2));
00177   }
00178 
00185   static bool Intersect (float minx, float miny, float maxx, float maxy,
00186     csVector2* poly, int num_poly);
00187 
00194   static bool Intersect (const csVector2& minbox, const csVector2& maxbox,
00195     csVector2* poly, int num_poly)
00196   {
00197     return Intersect (minbox.x, minbox.y, maxbox.x, maxbox.y, poly, num_poly);
00198   }
00199 
00206   bool Intersect (csVector2* poly, int num_poly) const
00207   {
00208     return Intersect (minbox, maxbox, poly, num_poly);
00209   }
00210 
00212   bool In (float x, float y) const
00213   {
00214     if (x < minbox.x || x > maxbox.x) return false;
00215     if (y < minbox.y || y > maxbox.y) return false;
00216     return true;
00217   }
00218 
00220   bool In (const csVector2& v) const
00221   {
00222     return In (v.x, v.y);
00223   }
00224 
00226   bool Overlap (const csBox2& box) const
00227   {
00228     if (maxbox.x < box.minbox.x || minbox.x > box.maxbox.x) return false;
00229     if (maxbox.y < box.minbox.y || minbox.y > box.maxbox.y) return false;
00230     return true;
00231   }
00232 
00234   bool Contains (const csBox2& box) const
00235   {
00236     return (box.minbox.x >= minbox.x && box.maxbox.x <= maxbox.x) &&
00237            (box.minbox.y >= minbox.y && box.maxbox.y <= maxbox.y);
00238   }
00239 
00241   bool Empty () const
00242   {
00243     if (minbox.x > maxbox.x) return true;
00244     if (minbox.y > maxbox.y) return true;
00245     return false;
00246   }
00247 
00252   float SquaredOriginDist () const;
00253 
00259   float SquaredOriginMaxDist () const;
00260 
00262   void StartBoundingBox ()
00263   {
00264     minbox.x =  CS_BOUNDINGBOX_MAXVALUE;  minbox.y =  CS_BOUNDINGBOX_MAXVALUE;
00265     maxbox.x = -CS_BOUNDINGBOX_MAXVALUE;  maxbox.y = -CS_BOUNDINGBOX_MAXVALUE;
00266   }
00267 
00269   void StartBoundingBox (const csVector2& v)
00270   {
00271     minbox = v;
00272     maxbox = v;
00273   }
00274 
00276   void StartBoundingBox (float x, float y)
00277   {
00278     minbox.x = maxbox.x = x;
00279     minbox.y = maxbox.y = y;
00280   }
00281 
00283   void AddBoundingVertex (float x, float y)
00284   {
00285     if (x < minbox.x) minbox.x = x;  if (x > maxbox.x) maxbox.x = x;
00286     if (y < minbox.y) minbox.y = y;  if (y > maxbox.y) maxbox.y = y;
00287   }
00288 
00290   void AddBoundingVertex (const csVector2& v)
00291   {
00292     AddBoundingVertex (v.x, v.y);
00293   }
00294 
00300   void AddBoundingVertexSmart (float x, float y)
00301   {
00302     if (x < minbox.x) minbox.x = x; else if (x > maxbox.x) maxbox.x = x;
00303     if (y < minbox.y) minbox.y = y; else if (y > maxbox.y) maxbox.y = y;
00304   }
00305 
00311   void AddBoundingVertexSmart (const csVector2& v)
00312   {
00313     AddBoundingVertexSmart (v.x, v.y);
00314   }
00315 
00316   //-----
00317   // Maintenance Note: The csBox2 constructors and Set() appear at this point
00318   // in the file, rather than earlier, in order to appease the OpenStep 4.2
00319   // compiler.  Specifically, the problem is that the compiler botches code
00320   // generation if an unseen method (which is later declared inline) is
00321   // called from within another inline method.  For instance, if the
00322   // constructors were listed at the top of the file, rather than here, the
00323   // compiler would see calls to Empty() and StartBoundingBox() before seeing
00324   // declarations for them.  In such a situation, the buggy compiler
00325   // generates a broken object file.  The simple work-around of textually
00326   // reorganizing the file ensures that the declarations for Empty() and
00327   // StartBoundingBox() are seen before they are called.
00328   //-----
00329 
00331   csBox2 () : minbox (CS_BOUNDINGBOX_MAXVALUE, CS_BOUNDINGBOX_MAXVALUE),
00332              maxbox (-CS_BOUNDINGBOX_MAXVALUE, -CS_BOUNDINGBOX_MAXVALUE) {}
00333 
00335   csBox2 (const csVector2& v) : minbox (v.x, v.y), maxbox (v.x, v.y) {}
00336 
00338   csBox2 (float x1, float y1, float x2, float y2) :
00339     minbox (x1, y1), maxbox (x2, y2)
00340   { if (Empty ()) StartBoundingBox (); }
00341 
00343   void Set (const csVector2& bmin, const csVector2& bmax)
00344   {
00345     minbox = bmin;
00346     maxbox = bmax;
00347   }
00348 
00350   void Set (float x1, float y1, float x2, float y2)
00351   {
00352     if (x1>x2 || y1>y2) StartBoundingBox();
00353     else { minbox.x = x1;  minbox.y = y1;  maxbox.x = x2;  maxbox.y = y2; }
00354   }
00355 
00357   void SetMin (int idx, float val)
00358   {
00359     if (idx == 1) minbox.y = val;
00360     else minbox.x = val;
00361   }
00362 
00364   void SetMax (int idx, float val)
00365   {
00366     if (idx == 1) maxbox.y = val;
00367     else maxbox.x = val;
00368   }
00369 
00371   csBox2& operator+= (const csBox2& box);
00373   csBox2& operator+= (const csVector2& point);
00375   csBox2& operator*= (const csBox2& box);
00377   bool TestIntersect (const csBox2& box) const;
00378 
00380   friend csBox2 operator+ (const csBox2& box1, const csBox2& box2);
00382   friend csBox2 operator+ (const csBox2& box, const csVector2& point);
00384   friend csBox2 operator* (const csBox2& box1, const csBox2& box2);
00385 
00387   friend bool operator== (const csBox2& box1, const csBox2& box2);
00389   friend bool operator!= (const csBox2& box1, const csBox2& box2);
00391   friend bool operator< (const csBox2& box1, const csBox2& box2);
00393   friend bool operator> (const csBox2& box1, const csBox2& box2);
00395   friend bool operator< (const csVector2& point, const csBox2& box);
00396 };
00397 
00402 
00403 #define CS_BOX_CORNER_xyz 0
00404 
00405 #define CS_BOX_CORNER_xyZ 1
00406 
00407 #define CS_BOX_CORNER_xYz 2
00408 
00409 #define CS_BOX_CORNER_xYZ 3
00410 
00411 #define CS_BOX_CORNER_Xyz 4
00412 
00413 #define CS_BOX_CORNER_XyZ 5
00414 
00415 #define CS_BOX_CORNER_XYz 6
00416 
00417 #define CS_BOX_CORNER_XYZ 7
00418 
00419 #define CS_BOX_CENTER3 8
00420 
00426 
00427 #define CS_BOX_SIDE_x 0
00428 
00429 #define CS_BOX_SIDE_X 1
00430 
00431 #define CS_BOX_SIDE_y 2
00432 
00433 #define CS_BOX_SIDE_Y 3
00434 
00435 #define CS_BOX_SIDE_z 4
00436 
00437 #define CS_BOX_SIDE_Z 5
00438 
00439 #define CS_BOX_INSIDE 6
00440 
00446 
00447 #define CS_BOX_EDGE_Xyz_xyz 0
00448 
00449 #define CS_BOX_EDGE_xyz_Xyz 1
00450 
00451 #define CS_BOX_EDGE_xyz_xYz 2
00452 
00453 #define CS_BOX_EDGE_xYz_xyz 3
00454 
00455 #define CS_BOX_EDGE_xYz_XYz 4
00456 
00457 #define CS_BOX_EDGE_XYz_xYz 5
00458 
00459 #define CS_BOX_EDGE_XYz_Xyz 6
00460 
00461 #define CS_BOX_EDGE_Xyz_XYz 7
00462 
00463 #define CS_BOX_EDGE_Xyz_XyZ 8
00464 
00465 #define CS_BOX_EDGE_XyZ_Xyz 9
00466 
00467 #define CS_BOX_EDGE_XyZ_XYZ 10
00468 
00469 #define CS_BOX_EDGE_XYZ_XyZ 11
00470 
00471 #define CS_BOX_EDGE_XYZ_XYz 12
00472 
00473 #define CS_BOX_EDGE_XYz_XYZ 13
00474 
00475 #define CS_BOX_EDGE_XYZ_xYZ 14
00476 
00477 #define CS_BOX_EDGE_xYZ_XYZ 15
00478 
00479 #define CS_BOX_EDGE_xYZ_xYz 16
00480 
00481 #define CS_BOX_EDGE_xYz_xYZ 17
00482 
00483 #define CS_BOX_EDGE_xYZ_xyZ 18
00484 
00485 #define CS_BOX_EDGE_xyZ_xYZ 19
00486 
00487 #define CS_BOX_EDGE_xyZ_xyz 20
00488 
00489 #define CS_BOX_EDGE_xyz_xyZ 21
00490 
00491 #define CS_BOX_EDGE_xyZ_XyZ 22
00492 
00493 #define CS_BOX_EDGE_XyZ_xyZ 23
00494 
00503 class csBox3
00504 {
00505 protected:
00507   csVector3 minbox;
00509   csVector3 maxbox;
00511   struct bEdge
00512   {
00513     uint8 v1, v2; // Indices of vertex in bounding box (CS_BOX_CORNER_...)
00514     uint8 fl, fr; // Indices of left/right faces sharing edge (CS_BOX_SIDE_...)
00515   };
00517   typedef uint8 bFace[4];       
00522   static bEdge edges[24];
00524   static bFace faces[6];
00525 public:
00527   float MinX () const { return minbox.x; }
00529   float MinY () const { return minbox.y; }
00531   float MinZ () const { return minbox.z; }
00533   float MaxX () const { return maxbox.x; }
00535   float MaxY () const { return maxbox.y; }
00537   float MaxZ () const { return maxbox.z; }
00539   float Min (int idx) const
00540   { return idx == 1 ? minbox.y : idx == 0 ? minbox.x : minbox.z; }
00542   float Max (int idx) const
00543   { return idx == 1 ? maxbox.y : idx == 0 ? maxbox.x : maxbox.z; }
00545   const csVector3& Min () const { return minbox; }
00547   const csVector3& Max () const { return maxbox; }
00548 
00558   csVector3 GetCorner (int corner) const;
00559 
00564   void GetEdgeInfo (int edge, int& v1, int& v2, int& fleft, int& fright) const
00565   {
00566     v1 = edges[edge].v1;
00567     v2 = edges[edge].v2;
00568     fleft = edges[edge].fl;
00569     fright = edges[edge].fr;
00570   }
00571 
00576   uint8* GetFaceEdges (int face) const
00577   {
00578     return faces[face];
00579   }
00580 
00584   csVector3 GetCenter () const { return (minbox+maxbox)/2; }
00585 
00590   void SetCenter (const csVector3& c);
00591 
00595   void SetSize (const csVector3& s);
00596 
00601   csBox2 GetSide (int side) const;
00602 
00609   int GetVisibleSides (const csVector3& pos, int* visible_sides) const;
00610 
00615   static int OtherSide (int side)
00616   {
00617     return side ^ 1;
00618   }
00619 
00625   csSegment3 GetEdge (int edge) const
00626   {
00627     return csSegment3 (GetCorner (edges[edge].v1), GetCorner (edges[edge].v2));
00628   }
00629 
00635   void GetEdge (int edge, csSegment3& e) const
00636   {
00637     e.SetStart (GetCorner (edges[edge].v1));
00638     e.SetEnd (GetCorner (edges[edge].v2));
00639   }
00640 
00642   bool In (float x, float y, float z) const
00643   {
00644     if (x < minbox.x || x > maxbox.x) return false;
00645     if (y < minbox.y || y > maxbox.y) return false;
00646     if (z < minbox.z || z > maxbox.z) return false;
00647     return true;
00648   }
00649 
00651   bool In (const csVector3& v) const
00652   {
00653     return In (v.x, v.y, v.z);
00654   }
00655 
00657   bool Overlap (const csBox3& box) const
00658   {
00659     if (maxbox.x < box.minbox.x || minbox.x > box.maxbox.x) return false;
00660     if (maxbox.y < box.minbox.y || minbox.y > box.maxbox.y) return false;
00661     if (maxbox.z < box.minbox.z || minbox.z > box.maxbox.z) return false;
00662     return true;
00663   }
00664 
00666   bool Contains (const csBox3& box) const
00667   {
00668     return (box.minbox.x >= minbox.x && box.maxbox.x <= maxbox.x) &&
00669            (box.minbox.y >= minbox.y && box.maxbox.y <= maxbox.y) &&
00670            (box.minbox.z >= minbox.z && box.maxbox.z <= maxbox.z);
00671   }
00672 
00674   bool Empty () const
00675   {
00676     if (minbox.x > maxbox.x) return true;
00677     if (minbox.y > maxbox.y) return true;
00678     if (minbox.z > maxbox.z) return true;
00679     return false;
00680   }
00681 
00683   void StartBoundingBox ()
00684   {
00685     minbox.x =  CS_BOUNDINGBOX_MAXVALUE;
00686     minbox.y =  CS_BOUNDINGBOX_MAXVALUE;
00687     minbox.z =  CS_BOUNDINGBOX_MAXVALUE;
00688     maxbox.x = -CS_BOUNDINGBOX_MAXVALUE;
00689     maxbox.y = -CS_BOUNDINGBOX_MAXVALUE;
00690     maxbox.z = -CS_BOUNDINGBOX_MAXVALUE;
00691   }
00692 
00694   void StartBoundingBox (const csVector3& v)
00695   {
00696     minbox = v; maxbox = v;
00697   }
00698 
00700   void AddBoundingVertex (float x, float y, float z)
00701   {
00702     if (x < minbox.x) minbox.x = x; if (x > maxbox.x) maxbox.x = x;
00703     if (y < minbox.y) minbox.y = y; if (y > maxbox.y) maxbox.y = y;
00704     if (z < minbox.z) minbox.z = z; if (z > maxbox.z) maxbox.z = z;
00705   }
00706 
00708   void AddBoundingVertex (const csVector3& v)
00709   {
00710     AddBoundingVertex (v.x, v.y, v.z);
00711   }
00712 
00718   void AddBoundingVertexSmart (float x, float y, float z)
00719   {
00720     if (x < minbox.x) minbox.x = x; else if (x > maxbox.x) maxbox.x = x;
00721     if (y < minbox.y) minbox.y = y; else if (y > maxbox.y) maxbox.y = y;
00722     if (z < minbox.z) minbox.z = z; else if (z > maxbox.z) maxbox.z = z;
00723   }
00724 
00730   void AddBoundingVertexSmart (const csVector3& v)
00731   {
00732     AddBoundingVertexSmart (v.x, v.y, v.z);
00733   }
00734 
00735   //-----
00736   // Maintenance Note: The csBox3 constructors and Set() appear at this point
00737   // in the file, rather than earlier, in order to appease the OpenStep 4.2
00738   // compiler.  Specifically, the problem is that the compiler botches code
00739   // generation if an unseen method (which is later declared inline) is
00740   // called from within another inline method.  For instance, if the
00741   // constructors were listed at the top of the file, rather than here, the
00742   // compiler would see calls to Empty() and StartBoundingBox() before seeing
00743   // declarations for them.  In such a situation, the buggy compiler
00744   // generated a broken object file.  The simple work-around of textually
00745   // reorganizing the file ensures that the declarations for Empty() and
00746   // StartBoundingBox() are seen before they are called.
00747   //-----
00748 
00750   csBox3 () :
00751     minbox ( CS_BOUNDINGBOX_MAXVALUE,
00752              CS_BOUNDINGBOX_MAXVALUE,
00753              CS_BOUNDINGBOX_MAXVALUE),
00754     maxbox (-CS_BOUNDINGBOX_MAXVALUE,
00755             -CS_BOUNDINGBOX_MAXVALUE,
00756             -CS_BOUNDINGBOX_MAXVALUE) {}
00757 
00759   csBox3 (const csVector3& v) : minbox (v), maxbox (v) { }
00760 
00762   csBox3 (const csVector3& v1, const csVector3& v2) :
00763         minbox (v1), maxbox (v2)
00764   { if (Empty ()) StartBoundingBox (); }
00765 
00767   csBox3 (float x1, float y1, float z1, float x2, float y2, float z2) :
00768     minbox (x1, y1, z1), maxbox (x2, y2, z2)
00769   { if (Empty ()) StartBoundingBox (); }
00770 
00772   void Set (const csVector3& bmin, const csVector3& bmax)
00773   {
00774     minbox = bmin;
00775     maxbox = bmax;
00776   }
00777 
00779   void Set (float x1, float y1, float z1, float x2, float y2, float z2)
00780   {
00781     if (x1>x2 || y1>y2 || z1>z2) StartBoundingBox();
00782     else
00783     {
00784       minbox.x = x1; minbox.y = y1; minbox.z = z1;
00785       maxbox.x = x2; maxbox.y = y2; maxbox.z = z2;
00786     }
00787   }
00788 
00790   void SetMin (int idx, float val)
00791   {
00792     if (idx == 1) minbox.y = val;
00793     else if (idx == 0) minbox.x = val;
00794     else minbox.z = val;
00795   }
00796 
00798   void SetMax (int idx, float val)
00799   {
00800     if (idx == 1) maxbox.y = val;
00801     else if (idx == 0) maxbox.x = val;
00802     else maxbox.z = val;
00803   }
00804 
00808   bool AdjacentX (const csBox3& other) const;
00809 
00813   bool AdjacentY (const csBox3& other) const;
00814 
00818   bool AdjacentZ (const csBox3& other) const;
00819 
00826   int Adjacent (const csBox3& other) const;
00827 
00834   int CalculatePointSegment (const csVector3& pos) const;
00835 
00844   void GetConvexOutline (const csVector3& pos,
00845         csVector3* array, int& num_array, bool bVisible=false) const;
00846 
00850   bool Between (const csBox3& box1, const csBox3& box2) const;
00851 
00856   void ManhattanDistance (const csBox3& other, csVector3& dist) const;
00857 
00862   float SquaredOriginDist () const;
00863 
00869   float SquaredOriginMaxDist () const;
00870 
00882   bool ProjectBox (const csTransform& trans, float fov, float sx, float sy,
00883         csBox2& sbox, float& min_z, float& max_z) const;
00884 
00894   bool ProjectOutline (const csTransform& trans, float fov, float sx, float sy,
00895         csPoly2D& poly, float& min_z, float& max_z) const;
00896 
00909   bool ProjectBoxAndOutline (const csTransform& trans, float fov,
00910         float sx, float sy, csBox2& sbox, csPoly2D& poly,
00911         float& min_z, float& max_z) const;
00912 
00914   csBox3& operator+= (const csBox3& box);
00916   csBox3& operator+= (const csVector3& point);
00918   csBox3& operator*= (const csBox3& box);
00920   bool TestIntersect (const csBox3& box) const;
00921 
00923   friend csBox3 operator+ (const csBox3& box1, const csBox3& box2);
00925   friend csBox3 operator+ (const csBox3& box, const csVector3& point);
00927   friend csBox3 operator* (const csBox3& box1, const csBox3& box2);
00928 
00930   friend bool operator== (const csBox3& box1, const csBox3& box2);
00932   friend bool operator!= (const csBox3& box1, const csBox3& box2);
00934   friend bool operator< (const csBox3& box1, const csBox3& box2);
00936   friend bool operator> (const csBox3& box1, const csBox3& box2);
00938   friend bool operator< (const csVector3& point, const csBox3& box);
00939 };
00940 
00943 #endif // __CS_BOX_H__

Generated for Crystal Space by doxygen 1.2.18