00001 /* 00002 File: RT_Grid.h 00003 00004 Function: Interface for hierarchical grid raytracer 00005 00006 Author(s): Andrew Willmott, 1996-2000 00007 00008 Copyright: (c) 1997-2000, Andrew Willmott 00009 */ 00010 00011 #ifndef __RT_Grid__ 00012 #define __RT_Grid__ 00013 00014 #include "RT_Defs.h" 00015 #include "RT_Prim.h" 00016 #include "RT_RayStats.h" 00017 #include "gcl/VecUtil.h" 00018 00019 class Renderer; 00020 00021 // --- RT_Grid support classes ------------------------------------------------ 00022 00023 00024 // Private data structures 00025 00026 struct PrimEntry; 00027 struct PrimListEntry; 00028 struct ObjEntry; 00029 class GridStore; 00030 00031 #ifdef RT_MEM_DEFRAG 00032 const Int PAGE_BITS = 12; // 2 ^ PAGE_BITS = size of a memory page. 00033 const Int PAGE_PTR_BITS = PAGE_BITS - 2; 00034 const Int PAGE_PTR_SIZE = 1 << PAGE_PTR_BITS; 00035 const Int PAGE_PTR_MASK = (1 << PAGE_PTR_BITS) - 1; 00036 #else 00037 const Int PAGE_BITS = 16; // 2 ^ PAGE_BITS = size of a memory page. 00038 const Int PAGE_PTR_BITS = PAGE_BITS - 2; 00039 const Int PAGE_PTR_SIZE = 1 << PAGE_PTR_BITS; 00040 const Int PAGE_PTR_MASK = (1 << PAGE_PTR_BITS) - 1; 00041 #endif 00042 00043 class GridStore 00046 { 00047 00048 public: 00049 Void Init(Int size); 00050 Void Free(); 00051 Int NumPages() 00052 { return numPages; }; 00053 GCLReal MemoryUsage() 00054 { return(mem / 1024.0); }; 00055 00056 PrimEntry*& operator [](Int i) 00057 { return(pages[i >> PAGE_PTR_BITS][i & PAGE_PTR_MASK]); }; 00058 00059 protected: 00060 PrimEntry*** pages; // Array of pointers to page data 00061 Int numPages; // How many page pointers we have 00062 Int mem; 00063 }; 00064 00065 00066 // --- RT_Grid Class ---------------------------------------------------------- 00067 00068 00069 class RT_Grid 00070 { 00071 public: 00072 // --- Public interface ------------------------------------------------------- 00073 00074 Void MasterInit(); 00075 Void Init(); 00076 Void Free(); 00077 00078 Void AddObject(RT_Object *object); 00079 Void RemoveObject(RT_Object *object); 00080 Void PrepareGrid(); 00081 00082 Bool IntersectionExists( 00083 const Point& start, 00084 const Point& end, 00085 RT_Prim* origPrim = 0, 00086 RayStats* stats = 0 00087 ); 00088 00089 RT_Prim* ClosestIntersection( 00090 const Point& start, 00091 const Vector& direction, 00092 RT_Prim* origPrim = 0, 00093 RayStats* stats = 0 00094 ); 00095 00096 // Misc 00097 Void HierPrint(ostream& s, Int index); 00098 static Void SetTag(Int tag) 00099 { sTag = tag; }; 00100 Void Draw(Renderer &r, Int level); 00101 00102 // Memory management 00103 Void DumpMemoryUsage(); 00104 GCLReal GridMemoryUsage(); 00105 GCLReal MemoryUsage(); 00106 static Void SetMemLimit(Int maxKbs); 00107 00108 // Low-level 00109 Void SetBounds(Point &bmin, Point &bmax) 00110 { min = bmin; max = bmax; }; 00111 Void SetupGrid(); 00112 Void AddTriangle(RT_Tri *tri); 00113 Void AddGeneric(RT_Gen *gen); 00114 GCLReal GetScale() 00115 { return(MaxElt(max - min)); }; 00116 00117 // Caching 00118 RT_Prim* hitPrim; 00119 GCLReal hitT; 00120 00121 Point min, max; 00122 00123 // --- Private! --------------------------------------------------------------- 00124 protected: 00125 ObjEntry* addedObjs; 00126 ObjEntry* addObjs; 00127 00128 GridStore grid; 00129 PrimListEntry* addPrims; 00130 RT_Grid* subGrids; 00131 RT_Grid* next; 00132 00133 GCLReal cellSize; 00134 GCLReal areaLimit; 00135 Int numCells[3]; 00136 Int xSpan, ySpan; 00137 Int totalCells, totalPrims; 00138 00139 // Class globals 00140 00141 public: 00142 static GCLReal sEpsilon; 00143 static Int sMem; 00144 static Int sMemLimit; 00145 static Int sTriMem; 00146 static Int sGenMem; 00147 static Int sPointMem; 00148 00149 static Int sMaxCells; 00150 static Int sMaxCellPrims; 00151 static GCLReal sPushSizeLimit; 00152 static GCLReal sMaxCellRatio; 00153 static GCLReal sMinDensity; 00154 static GCLReal sMaxExpand; 00155 00156 // Grid maintenance 00157 00158 protected: 00159 Int dirty; 00160 Int level; 00161 RT_Grid* parent; 00162 00163 Int stamp; 00164 static Int sStamp; 00165 static Int sTag; 00166 00167 // Methods 00168 00169 static Void IncTime() 00170 { sStamp++; }; 00171 Void Stamp() 00172 { stamp = sStamp; }; 00173 Bool IsStamped() 00174 { return(stamp == sStamp); }; 00175 00176 Void UpdateBounds(Point& cellMin, Point& cellMax); 00177 Void UpdateBounds(RT_Object *object); 00178 00179 Void CreateNestedGrids(); 00180 Void CullSubGrids(); 00181 Void PushPrimitives(); 00182 Int CountPolys(PrimEntry *entry); 00183 00184 Bool FindGridStart( 00185 const Point& start, 00186 const Vector& direction, 00187 Int cell[3], 00188 Int increment[3], 00189 Int limit[3], 00190 GCLReal& tRay, 00191 Vector& tDelta, 00192 Vector& tMax 00193 ); 00194 00195 Void RayClampEntryPoint(Int index, Bool backEntry[3], 00196 Vector& fujiPoint, Int cell[3]); 00197 }; 00198 00199 struct ObjEntry 00200 { 00201 RT_Object* object; 00202 ObjEntry* next; 00203 }; 00204 00205 #endif