polytree.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_POLYTREE_H__
00020 #define __CS_POLYTREE_H__
00021 
00022 #include "csgeom/math3d.h"
00023 #include "csgeom/plane3.h"
00024 #include "csgeom/vector3.h"
00025 #include "csgeom/box.h"
00026 #include "csengine/arrays.h"
00027 
00028 class csThing;
00029 class csPolygonInt;
00030 class csPolygonTree;
00031 class csPolygonTreeNode;
00032 class csPolygonStub;
00033 class csPolyTreeBBox;
00034 struct iFile;
00035 
00036 
00037 #define NODE_OCTREE 1
00038 #define NODE_BSPTREE 2
00039 
00046 typedef void* (csTreeVisitFunc)(csThing*, csPolygonInt**,
00047         int num, bool same_plane, void*);
00048 
00054 typedef bool (csTreeCullFunc)(csPolygonTree* tree, csPolygonTreeNode* node,
00055         const csVector3& pos, void* data);
00056 
00060 class csPolygonTreeNode
00061 {
00062 protected:
00068   csPolygonStub* first_stub;
00069 
00074   csPolygonStub* todo_stubs;
00075 
00076 public:
00080   csPolygonTreeNode () : first_stub (NULL), todo_stubs (NULL) { }
00081 
00085   virtual ~csPolygonTreeNode ();
00086 
00088   virtual bool IsEmpty () = 0;
00089 
00091   virtual int Type () = 0;
00092 
00098   void UnlinkStub (csPolygonStub* ps);
00099 
00103   void LinkStubTodo (csPolygonStub* ps);
00104 
00108   void LinkStub (csPolygonStub* ps);
00109 
00114   void* TraverseObjects (csThing* thing, const csVector3& pos,
00115         csTreeVisitFunc* func, void* data);
00116 };
00117 
00123 class csPolygonTree
00124 {
00125 protected:
00127   csPolygonTreeNode* root;
00128 
00130   csThing* thing;
00131 
00133   void Clear () { delete root; }
00134 
00135   // Various routines to write to an iFile. Used by 'Cache'.
00136   void WriteString (iFile* cf, char* str, int len);
00137   void WriteBox3 (iFile* cf, const csBox3& box);
00138   void WriteVector3 (iFile* cf, const csVector3& v);
00139   void WritePlane3 (iFile* cf, const csPlane3& v);
00140   void WriteLong (iFile* cf, long l);
00141   void WriteUShort (iFile* cf, uint16 l);
00142   void WriteByte (iFile* cf, unsigned char b);
00143   void WriteBool (iFile* cf, bool b);
00144 
00145   // Various routines to write from an iFile. Used by 'ReadFromCache'.
00146   void ReadString (iFile* cf, char* str, int len);
00147   void ReadBox3 (iFile* cf, csBox3& box);
00148   void ReadVector3 (iFile* cf, csVector3& v);
00149   void ReadPlane3 (iFile* cf, csPlane3& v);
00150   long ReadLong (iFile* cf);
00151   uint16 ReadUShort (iFile* cf);
00152   unsigned char ReadByte (iFile* cf);
00153   bool ReadBool (iFile* cf);
00154 
00155 public:
00159   csPolygonTree (csThing* th) : root (NULL), thing (th) { }
00160 
00164   virtual ~csPolygonTree () { }
00165 
00167   csThing* GetThing () { return thing; }
00168 
00172   virtual void Build (csPolygonInt** polygons, int num) = 0;
00173 
00177   void Build (csPolygonArray& polygons)
00178   {
00179     Build (polygons.GetArray (), polygons.Length ());
00180   }
00181 
00185   void AddObject (csPolyTreeBBox* obj);
00186 
00190   void AddStubTodo (csPolygonStub* stub)
00191   {
00192     root->LinkStubTodo (stub);
00193   }
00194 
00199   bool Overlaps (csPolygonInt** polygons, int num);
00200 
00202   virtual void* Back2Front (const csVector3& pos, csTreeVisitFunc* func,
00203         void* data, csTreeCullFunc* cullfunc = NULL, void* culldata = NULL) = 0;
00205   virtual void* Front2Back (const csVector3& pos, csTreeVisitFunc* func,
00206         void* data, csTreeCullFunc* cullfunc = NULL, void* culldata = NULL) = 0;
00207 
00209   virtual void Statistics () = 0;
00210 };
00211 
00212 #endif // __CS_POLYTREE_H__