|
box.h00001 /* 00002 Copyright (C) 1998,1999,2000 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 00023 #include "cstypes.h" // for bool 00024 #include "vector2.h" 00025 #include "vector3.h" 00026 #include "segment.h" 00027 00028 class csPlane3; 00029 00034 #define CS_BOUNDINGBOX_MAXVALUE 1000000000. 00035 00037 #define CS_BOX_CORNER_xy 0 00038 #define CS_BOX_CORNER_xY 1 00039 #define CS_BOX_CORNER_Xy 2 00040 #define CS_BOX_CORNER_XY 3 00041 00046 #define CS_BOX_EDGE_xy_Xy 0 00047 #define CS_BOX_EDGE_Xy_xy 1 00048 #define CS_BOX_EDGE_Xy_XY 2 00049 #define CS_BOX_EDGE_XY_Xy 3 00050 #define CS_BOX_EDGE_XY_xY 4 00051 #define CS_BOX_EDGE_xY_XY 5 00052 #define CS_BOX_EDGE_xY_xy 6 00053 #define CS_BOX_EDGE_xy_xY 7 00054 00062 class csBox2 00063 { 00064 private: 00065 struct bEdge 00066 { 00067 uint8 v1, v2; // Indices of vertex in bounding box (CS_BOX_CORNER_...) 00068 }; 00069 // Index by edge number. Edge e and e+1 with e even are opposite edges. 00070 // (CS_BOX_EDGE_...) 00071 static bEdge edges[8]; 00072 00073 protected: 00075 csVector2 minbox; 00077 csVector2 maxbox; 00078 00079 public: 00081 float MinX () const { return minbox.x; } 00083 float MinY () const { return minbox.y; } 00085 float MaxX () const { return maxbox.x; } 00087 float MaxY () const { return maxbox.y; } 00089 float Min (int idx) const { return idx ? minbox.y : minbox.x; } 00091 float Max (int idx) const { return idx ? maxbox.y : maxbox.x; } 00093 const csVector2& Min () const { return minbox; } 00095 const csVector2& Max () const { return maxbox; } 00096 00104 csVector2 GetCorner (int corner) const; 00105 00109 csVector2 GetCenter () const { return (minbox+maxbox)/2; } 00110 00115 void SetCenter (const csVector2& c); 00116 00120 void SetSize (const csVector2& s); 00121 00126 void GetEdgeInfo (int edge, int& v1, int& v2) const 00127 { 00128 v1 = edges[edge].v1; 00129 v2 = edges[edge].v2; 00130 } 00131 00136 csSegment2 GetEdge (int edge) const 00137 { 00138 return csSegment2 (GetCorner (edges[edge].v1), GetCorner (edges[edge].v2)); 00139 } 00140 00145 void GetEdge (int edge, csSegment2& e) const 00146 { 00147 e.SetStart (GetCorner (edges[edge].v1)); 00148 e.SetEnd (GetCorner (edges[edge].v2)); 00149 } 00150 00157 static bool Intersect (float minx, float miny, float maxx, float maxy, 00158 csVector2* poly, int num_poly); 00159 00166 static bool Intersect (const csVector2& minbox, const csVector2& maxbox, 00167 csVector2* poly, int num_poly) 00168 { 00169 return Intersect (minbox.x, minbox.y, maxbox.x, maxbox.y, poly, num_poly); 00170 } 00171 00178 bool Intersect (csVector2* poly, int num_poly) const 00179 { 00180 return Intersect (minbox, maxbox, poly, num_poly); 00181 } 00182 00184 bool In (float x, float y) const 00185 { 00186 if (x < minbox.x || x > maxbox.x) return false; 00187 if (y < minbox.y || y > maxbox.y) return false; 00188 return true; 00189 } 00190 00192 bool In (const csVector2& v) const 00193 { 00194 return In (v.x, v.y); 00195 } 00196 00198 bool Overlap (const csBox2& box) const 00199 { 00200 if (maxbox.x < box.minbox.x || minbox.x > box.maxbox.x) return false; 00201 if (maxbox.y < box.minbox.y || minbox.y > box.maxbox.y) return false; 00202 return true; 00203 } 00204 00206 bool Contains (const csBox2& box) const 00207 { 00208 return (box.minbox.x >= minbox.x && box.maxbox.x <= maxbox.x) && 00209 (box.minbox.y >= minbox.y && box.maxbox.y <= maxbox.y); 00210 } 00211 00213 bool Empty () const 00214 { 00215 if (minbox.x > maxbox.x) return true; 00216 if (minbox.y > maxbox.y) return true; 00217 return false; 00218 } 00219 00224 float SquaredOriginDist () const; 00225 00231 float SquaredOriginMaxDist () const; 00232 00234 void StartBoundingBox () 00235 { 00236 minbox.x = CS_BOUNDINGBOX_MAXVALUE; minbox.y = CS_BOUNDINGBOX_MAXVALUE; 00237 maxbox.x = -CS_BOUNDINGBOX_MAXVALUE; maxbox.y = -CS_BOUNDINGBOX_MAXVALUE; 00238 } 00239 00241 void StartBoundingBox (const csVector2& v) 00242 { 00243 minbox = v; 00244 maxbox = v; 00245 } 00246 00248 void StartBoundingBox (float x, float y) 00249 { 00250 minbox.x = maxbox.x = x; 00251 minbox.y = maxbox.y = y; 00252 } 00253 00255 void AddBoundingVertex (float x, float y) 00256 { 00257 if (x < minbox.x) minbox.x = x; if (x > maxbox.x) maxbox.x = x; 00258 if (y < minbox.y) minbox.y = y; if (y > maxbox.y) maxbox.y = y; 00259 } 00260 00262 void AddBoundingVertex (const csVector2& v) 00263 { 00264 AddBoundingVertex (v.x, v.y); 00265 } 00266 00272 void AddBoundingVertexSmart (float x, float y) 00273 { 00274 if (x < minbox.x) minbox.x = x; else if (x > maxbox.x) maxbox.x = x; 00275 if (y < minbox.y) minbox.y = y; else if (y > maxbox.y) maxbox.y = y; 00276 } 00277 00283 void AddBoundingVertexSmart (const csVector2& v) 00284 { 00285 AddBoundingVertexSmart (v.x, v.y); 00286 } 00287 00288 //----- 00289 // Maintenance Note: The csBox2 constructors and Set() appear at this point 00290 // in the file, rather than earlier, in order to appease the OpenStep 4.2 00291 // compiler. Specifically, the problem is that the compiler botches code 00292 // generation if an unseen method (which is later declared inline) is 00293 // called from within another inline method. For instance, if the 00294 // constructors were listed at the top of the file, rather than here, the 00295 // compiler would see calls to Empty() and StartBoundingBox() before seeing 00296 // declarations for them. In such a situation, the buggy compiler 00297 // generates a broken object file. The simple work-around of textually 00298 // reorganizing the file ensures that the declarations for Empty() and 00299 // StartBoundingBox() are seen before they are called. 00300 //----- 00301 00303 csBox2 () : minbox (CS_BOUNDINGBOX_MAXVALUE, CS_BOUNDINGBOX_MAXVALUE), 00304 maxbox (-CS_BOUNDINGBOX_MAXVALUE, -CS_BOUNDINGBOX_MAXVALUE) {} 00305 00307 csBox2 (const csVector2& v) : minbox (v.x, v.y), maxbox (v.x, v.y) {} 00308 00310 csBox2 (float x1, float y1, float x2, float y2) : 00311 minbox (x1, y1), maxbox (x2, y2) 00312 { if (Empty ()) StartBoundingBox (); } 00313 00315 void Set (const csVector2& bmin, const csVector2& bmax) 00316 { 00317 minbox = bmin; 00318 maxbox = bmax; 00319 } 00320 00322 void Set (float x1, float y1, float x2, float y2) 00323 { 00324 if (x1>x2 || y1>y2) StartBoundingBox(); 00325 else { minbox.x = x1; minbox.y = y1; maxbox.x = x2; maxbox.y = y2; } 00326 } 00327 00329 csBox2& operator+= (const csBox2& box); 00331 csBox2& operator+= (const csVector2& point); 00333 csBox2& operator*= (const csBox2& box); 00334 00336 friend csBox2 operator+ (const csBox2& box1, const csBox2& box2); 00338 friend csBox2 operator+ (const csBox2& box, const csVector2& point); 00340 friend csBox2 operator* (const csBox2& box1, const csBox2& box2); 00341 00343 friend bool operator== (const csBox2& box1, const csBox2& box2); 00345 friend bool operator!= (const csBox2& box1, const csBox2& box2); 00347 friend bool operator< (const csBox2& box1, const csBox2& box2); 00349 friend bool operator> (const csBox2& box1, const csBox2& box2); 00351 friend bool operator< (const csVector2& point, const csBox2& box); 00352 }; 00353 00358 #define CS_BOX_CORNER_xyz 0 00359 #define CS_BOX_CORNER_xyZ 1 00360 #define CS_BOX_CORNER_xYz 2 00361 #define CS_BOX_CORNER_xYZ 3 00362 #define CS_BOX_CORNER_Xyz 4 00363 #define CS_BOX_CORNER_XyZ 5 00364 #define CS_BOX_CORNER_XYz 6 00365 #define CS_BOX_CORNER_XYZ 7 00366 00371 #define CS_BOX_SIDE_x 0 00372 #define CS_BOX_SIDE_X 1 00373 #define CS_BOX_SIDE_y 2 00374 #define CS_BOX_SIDE_Y 3 00375 #define CS_BOX_SIDE_z 4 00376 #define CS_BOX_SIDE_Z 5 00377 #define CS_BOX_INSIDE 6 00378 00383 #define CS_BOX_EDGE_Xyz_xyz 0 00384 #define CS_BOX_EDGE_xyz_Xyz 1 00385 #define CS_BOX_EDGE_xyz_xYz 2 00386 #define CS_BOX_EDGE_xYz_xyz 3 00387 #define CS_BOX_EDGE_xYz_XYz 4 00388 #define CS_BOX_EDGE_XYz_xYz 5 00389 #define CS_BOX_EDGE_XYz_Xyz 6 00390 #define CS_BOX_EDGE_Xyz_XYz 7 00391 #define CS_BOX_EDGE_Xyz_XyZ 8 00392 #define CS_BOX_EDGE_XyZ_Xyz 9 00393 #define CS_BOX_EDGE_XyZ_XYZ 10 00394 #define CS_BOX_EDGE_XYZ_XyZ 11 00395 #define CS_BOX_EDGE_XYZ_XYz 12 00396 #define CS_BOX_EDGE_XYz_XYZ 13 00397 #define CS_BOX_EDGE_XYZ_xYZ 14 00398 #define CS_BOX_EDGE_xYZ_XYZ 15 00399 #define CS_BOX_EDGE_xYZ_xYz 16 00400 #define CS_BOX_EDGE_xYz_xYZ 17 00401 #define CS_BOX_EDGE_xYZ_xyZ 18 00402 #define CS_BOX_EDGE_xyZ_xYZ 19 00403 #define CS_BOX_EDGE_xyZ_xyz 20 00404 #define CS_BOX_EDGE_xyz_xyZ 21 00405 #define CS_BOX_EDGE_xyZ_XyZ 22 00406 #define CS_BOX_EDGE_XyZ_xyZ 23 00407 00415 class csBox3 00416 { 00417 protected: 00419 csVector3 minbox; 00421 csVector3 maxbox; 00422 00423 struct bEdge 00424 { 00425 uint8 v1, v2; // Indices of vertex in bounding box (CS_BOX_CORNER_...) 00426 uint8 fl, fr; // Indices of left/right faces sharing edge (CS_BOX_SIDE_...) 00427 }; 00428 typedef uint8 bFace[4]; // Indices of four clock-wise edges (0..23) 00429 // Index by edge number. Edge e and e+1 with e even are opposite edges. 00430 // (CS_BOX_EDGE_...) 00431 static bEdge edges[24]; 00432 // Index by CS_BOX_SIDE_? number. 00433 static bFace faces[6]; 00434 public: 00436 float MinX () const { return minbox.x; } 00438 float MinY () const { return minbox.y; } 00440 float MinZ () const { return minbox.z; } 00442 float MaxX () const { return maxbox.x; } 00444 float MaxY () const { return maxbox.y; } 00446 float MaxZ () const { return maxbox.z; } 00448 float Min (int idx) const 00449 { return idx == 1 ? minbox.y : idx == 0 ? minbox.x : minbox.z; } 00451 float Max (int idx) const 00452 { return idx == 1 ? maxbox.y : idx == 0 ? maxbox.x : maxbox.z; } 00454 const csVector3& Min () const { return minbox; } 00456 const csVector3& Max () const { return maxbox; } 00457 00466 csVector3 GetCorner (int corner) const; 00467 00472 void GetEdgeInfo (int edge, int& v1, int& v2, int& fleft, int& fright) const 00473 { 00474 v1 = edges[edge].v1; 00475 v2 = edges[edge].v2; 00476 fleft = edges[edge].fl; 00477 fright = edges[edge].fr; 00478 } 00479 00484 uint8* GetFaceEdges (int face) const 00485 { 00486 return faces[face]; 00487 } 00488 00492 csVector3 GetCenter () const { return (minbox+maxbox)/2; } 00493 00498 void SetCenter (const csVector3& c); 00499 00503 void SetSize (const csVector3& s); 00504 00509 csBox2 GetSide (int side) const; 00510 00517 int GetVisibleSides (const csVector3& pos, int* visible_sides) const; 00518 00523 static int OtherSide (int side) 00524 { 00525 return side ^ 1; 00526 } 00527 00533 csSegment3 GetEdge (int edge) const 00534 { 00535 return csSegment3 (GetCorner (edges[edge].v1), GetCorner (edges[edge].v2)); 00536 } 00537 00543 void GetEdge (int edge, csSegment3& e) const 00544 { 00545 e.SetStart (GetCorner (edges[edge].v1)); 00546 e.SetEnd (GetCorner (edges[edge].v2)); 00547 } 00548 00550 bool In (float x, float y, float z) const 00551 { 00552 if (x < minbox.x || x > maxbox.x) return false; 00553 if (y < minbox.y || y > maxbox.y) return false; 00554 if (z < minbox.z || z > maxbox.z) return false; 00555 return true; 00556 } 00557 00559 bool In (const csVector3& v) const 00560 { 00561 return In (v.x, v.y, v.z); 00562 } 00563 00565 bool Overlap (const csBox3& box) const 00566 { 00567 if (maxbox.x < box.minbox.x || minbox.x > box.maxbox.x) return false; 00568 if (maxbox.y < box.minbox.y || minbox.y > box.maxbox.y) return false; 00569 if (maxbox.z < box.minbox.z || minbox.z > box.maxbox.z) return false; 00570 return true; 00571 } 00572 00574 bool Contains (const csBox3& box) const 00575 { 00576 return (box.minbox.x >= minbox.x && box.maxbox.x <= maxbox.x) && 00577 (box.minbox.y >= minbox.y && box.maxbox.y <= maxbox.y) && 00578 (box.minbox.z >= minbox.z && box.maxbox.z <= maxbox.z); 00579 } 00580 00582 bool Empty () const 00583 { 00584 if (minbox.x > maxbox.x) return true; 00585 if (minbox.y > maxbox.y) return true; 00586 if (minbox.z > maxbox.z) return true; 00587 return false; 00588 } 00589 00591 void StartBoundingBox () 00592 { 00593 minbox.x = CS_BOUNDINGBOX_MAXVALUE; 00594 minbox.y = CS_BOUNDINGBOX_MAXVALUE; 00595 minbox.z = CS_BOUNDINGBOX_MAXVALUE; 00596 maxbox.x = -CS_BOUNDINGBOX_MAXVALUE; 00597 maxbox.y = -CS_BOUNDINGBOX_MAXVALUE; 00598 maxbox.z = -CS_BOUNDINGBOX_MAXVALUE; 00599 } 00600 00602 void StartBoundingBox (const csVector3& v) 00603 { 00604 minbox = v; maxbox = v; 00605 } 00606 00608 void AddBoundingVertex (float x, float y, float z) 00609 { 00610 if (x < minbox.x) minbox.x = x; if (x > maxbox.x) maxbox.x = x; 00611 if (y < minbox.y) minbox.y = y; if (y > maxbox.y) maxbox.y = y; 00612 if (z < minbox.z) minbox.z = z; if (z > maxbox.z) maxbox.z = z; 00613 } 00614 00616 void AddBoundingVertex (const csVector3& v) 00617 { 00618 AddBoundingVertex (v.x, v.y, v.z); 00619 } 00620 00626 void AddBoundingVertexSmart (float x, float y, float z) 00627 { 00628 if (x < minbox.x) minbox.x = x; else if (x > maxbox.x) maxbox.x = x; 00629 if (y < minbox.y) minbox.y = y; else if (y > maxbox.y) maxbox.y = y; 00630 if (z < minbox.z) minbox.z = z; else if (z > maxbox.z) maxbox.z = z; 00631 } 00632 00638 void AddBoundingVertexSmart (const csVector3& v) 00639 { 00640 AddBoundingVertexSmart (v.x, v.y, v.z); 00641 } 00642 00643 //----- 00644 // Maintenance Note: The csBox3 constructors and Set() appear at this point 00645 // in the file, rather than earlier, in order to appease the OpenStep 4.2 00646 // compiler. Specifically, the problem is that the compiler botches code 00647 // generation if an unseen method (which is later declared inline) is 00648 // called from within another inline method. For instance, if the 00649 // constructors were listed at the top of the file, rather than here, the 00650 // compiler would see calls to Empty() and StartBoundingBox() before seeing 00651 // declarations for them. In such a situation, the buggy compiler 00652 // generated a broken object file. The simple work-around of textually 00653 // reorganizing the file ensures that the declarations for Empty() and 00654 // StartBoundingBox() are seen before they are called. 00655 //----- 00656 00658 csBox3 () : 00659 minbox ( CS_BOUNDINGBOX_MAXVALUE, 00660 CS_BOUNDINGBOX_MAXVALUE, 00661 CS_BOUNDINGBOX_MAXVALUE), 00662 maxbox (-CS_BOUNDINGBOX_MAXVALUE, 00663 -CS_BOUNDINGBOX_MAXVALUE, 00664 -CS_BOUNDINGBOX_MAXVALUE) {} 00665 00667 csBox3 (const csVector3& v) : minbox (v), maxbox (v) { } 00668 00670 csBox3 (const csVector3& v1, const csVector3& v2) : 00671 minbox (v1), maxbox (v2) 00672 { if (Empty ()) StartBoundingBox (); } 00673 00675 csBox3 (float x1, float y1, float z1, float x2, float y2, float z2) : 00676 minbox (x1, y1, z1), maxbox (x2, y2, z2) 00677 { if (Empty ()) StartBoundingBox (); } 00678 00680 void Set (const csVector3& bmin, const csVector3& bmax) 00681 { 00682 minbox = bmin; 00683 maxbox = bmax; 00684 } 00685 00687 void Set (float x1, float y1, float z1, float x2, float y2, float z2) 00688 { 00689 if (x1>x2 || y1>y2 || z1>z2) StartBoundingBox(); 00690 else 00691 { 00692 minbox.x = x1; minbox.y = y1; minbox.z = z1; 00693 maxbox.x = x2; maxbox.y = y2; maxbox.z = z2; 00694 } 00695 } 00696 00700 bool AdjacentX (const csBox3& other) const; 00701 00705 bool AdjacentY (const csBox3& other) const; 00706 00710 bool AdjacentZ (const csBox3& other) const; 00711 00718 int Adjacent (const csBox3& other) const; 00719 00728 void GetConvexOutline (const csVector3& pos, 00729 csVector3* array, int& num_array, bool bVisible=false) const; 00730 00734 bool Between (const csBox3& box1, const csBox3& box2) const; 00735 00740 void ManhattanDistance (const csBox3& other, csVector3& dist) const; 00741 00746 float SquaredOriginDist () const; 00747 00753 float SquaredOriginMaxDist () const; 00754 00756 csBox3& operator+= (const csBox3& box); 00758 csBox3& operator+= (const csVector3& point); 00760 csBox3& operator*= (const csBox3& box); 00761 00763 friend csBox3 operator+ (const csBox3& box1, const csBox3& box2); 00765 friend csBox3 operator+ (const csBox3& box, const csVector3& point); 00767 friend csBox3 operator* (const csBox3& box1, const csBox3& box2); 00768 00770 friend bool operator== (const csBox3& box1, const csBox3& box2); 00772 friend bool operator!= (const csBox3& box1, const csBox3& box2); 00774 friend bool operator< (const csBox3& box1, const csBox3& box2); 00776 friend bool operator> (const csBox3& box1, const csBox3& box2); 00778 friend bool operator< (const csVector3& point, const csBox3& box); 00779 }; 00780 00781 #endif // __CS_BOX_H__ Generated for Crystal Space by doxygen 1.2.5 written by Dimitri van Heesch, ©1997-2000 |