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