bsp2d.h Source File

00001 /*
00002     Copyright (C) 2000 by Jorrit Tyberghein
00003 
00004     This library is free software; you can redistribute it and/or
00005     modify it under the terms of the GNU Library General Public
00006     License as published by the Free Software Foundation; either
00007     version 2 of the License, or (at your option) any later version.
00008 
00009     This library is distributed in the hope that it will be useful,
00010     but WITHOUT ANY WARRANTY; without even the implied warranty of
00011     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00012     Library General Public License for more details.
00013 
00014     You should have received a copy of the GNU Library General Public
00015     License along with this library; if not, write to the Free
00016     Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
00017 */
00018 
00019 #ifndef __CS_BSP2D_H__
00020 #define __CS_BSP2D_H__
00021 
00022 #include "csgeom/math2d.h"
00023 #include "csgeom/segment.h"
00024 #include "csengine/arrays.h"
00025 #include "csengine/bsp.h"
00026 #include "csutil/csvector.h"
00027 
00028 class csBspTree2D;
00029 
00033 class csSegmentArray : public csVector
00034 {
00035 public:
00037   csSegmentArray (int iLimit, int iDelta) : csVector (iLimit, iDelta)
00038   { }
00039 
00041   virtual ~csSegmentArray ();
00042 
00044   virtual bool FreeItem (csSome Item)
00045   {
00046     delete (csSegment2*)Item;
00047     return true;
00048   }
00049 
00051   csSegment2* Get (int iIndex) const
00052   {
00053     return (csSegment2*)csVector::Get (iIndex);
00054   }
00055 
00057   csSegment2** GetArray () { return (csSegment2**)root; }
00058 };
00059 
00060 
00064 class csBspNode2D
00065 {
00066   friend class csBspTree2D;
00067 private:
00074   csSegmentArray segments;
00075 
00077   csPlane2 splitter;
00078 
00080   csBspNode2D* front;
00082   csBspNode2D* back;
00083 
00084 private:
00086   csBspNode2D ();
00087 
00089   virtual ~csBspNode2D ();
00090 
00094   void AddSegment (csSegment2* seg);
00095 };
00096 
00097 typedef void* (csTree2DVisitFunc)(csSegment2**, int num, void*);
00098 
00105 class csBspTree2D
00106 {
00107 private:
00109   csBspNode2D* root;
00110 
00114   void Add (csBspNode2D* node, csSegment2* segment);
00115 
00117   void* Back2Front (csBspNode2D* node, const csVector2& pos,
00118         csTree2DVisitFunc* func, void* data);
00120   void* Front2Back (csBspNode2D* node, const csVector2& pos,
00121         csTree2DVisitFunc* func, void* data);
00122 
00123 public:
00127   csBspTree2D ();
00128 
00132   virtual ~csBspTree2D ();
00133 
00139   void Add (csSegment2* segment);
00140 
00142   void* Back2Front (const csVector2& pos, csTree2DVisitFunc* func, void* data);
00144   void* Front2Back (const csVector2& pos, csTree2DVisitFunc* func, void* data);
00145 };
00146 
00147 #endif // __CS_BSP2D_H__
00148