Main Page | Modules | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | File Members | Related Pages
tcovbuf.h
00001 /* 00002 Copyright (C) 2002-2005 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_CSGEOM_TCOVBUF_H__ 00020 #define __CS_CSGEOM_TCOVBUF_H__ 00021 00022 #include "csextern.h" 00023 #include "csgeom/vector2.h" 00024 #include "csgeom/math2d.h" 00025 #include "iutil/dbghelp.h" 00026 00027 //#define SHIFT_TILECOL 5 00028 //#define SHIFT_TILEROW 6 00029 00030 #define SHIFT_TILECOL 6 00031 #define SHIFT_TILEROW 5 00032 00033 #define NUM_TILECOL (1<<SHIFT_TILECOL) 00034 #define NUM_TILEROW (1<<SHIFT_TILEROW) 00035 #define NUM_DEPTHROW (NUM_TILEROW/8) 00036 #define NUM_DEPTHCOL (NUM_TILECOL/8) 00037 #define NUM_DEPTH (NUM_DEPTHROW * NUM_DEPTHCOL) 00038 00039 #define TILECOL_EMPTY 0 00040 #define TILECOL_FULL ((uint32)~0) 00041 00042 #define TEST_OCCLUDER_QUALITY 1 00043 00044 typedef uint32 csTileCol; 00045 00049 class csBox2Int 00050 { 00051 public: 00052 int minx, miny; 00053 int maxx, maxy; 00054 csBox2Int& operator+= (const csBox2Int& box) 00055 { 00056 if (box.minx < minx) minx = box.minx; 00057 if (box.miny < miny) miny = box.miny; 00058 if (box.maxx > maxx) maxx = box.maxx; 00059 if (box.maxy > maxy) maxy = box.maxy; 00060 return *this; 00061 } 00062 }; 00063 00068 struct csTestRectData 00069 { 00070 csBox2Int bbox; 00071 int startrow, endrow; 00072 int startcol, endcol; 00073 int start_x, end_x; 00074 }; 00075 00076 struct iGraphics2D; 00077 struct iGraphics3D; 00078 struct iBugPlug; 00079 class csString; 00080 class csBox2; 00081 class csTiledCoverageBuffer; 00082 00083 // Line operations in a tile. 00084 #define OP_LINE 1 // General line. 00085 #define OP_VLINE 2 // Vertical line. 00086 #define OP_FULLVLINE 3 // Full vertical line (from 0 to 63). 00087 00088 // A definition for a line operation. 00089 struct csLineOperation 00090 { 00091 uint8 op; // One of OP_... 00092 // All coordinates are with 0,0 relative to top-left of tile. 00093 // x coordinates are also shifted 16 to the left. 00094 int x1; // Start of line. 00095 int y1; // Start of line. Not used with OP_FULLVLINE. 00096 int x2; // End of line. Only used with OP_LINE. 00097 int y2; // End of line. Not used with OP_FULLVLINE. 00098 int dx; // Slope to add to x1 (shifted 16 to left). 00099 }; 00100 00106 class CS_CSGEOM_EXPORT csCoverageTile 00107 { 00108 friend class csTiledCoverageBuffer; 00109 00110 private: 00111 // If true entire tile is full. 00112 bool tile_full; 00113 // If true tile is queued as empty but 'coverage' and other 00114 // data structures may not yet reflect this. 00115 bool queue_tile_empty; 00116 00117 // The coverage bits. 00118 csTileCol coverage[NUM_TILECOL]; 00119 00120 // The cache on which we will write lines before or-ing that to the 00121 // real coverage bits. 00122 static csTileCol coverage_cache[NUM_TILECOL]; 00123 00124 // This is an array of precalculated bit-sets for vertical line 00125 // segments that start at 'n' and go to 63. 00126 static csTileCol precalc_end_lines[NUM_TILEROW]; 00127 // This is an array of precalculated bit-sets for vertical line 00128 // segments that start at 0 and go to 'n'. 00129 static csTileCol precalc_start_lines[NUM_TILEROW]; 00130 // If true the two arrays above are initialized. 00131 static bool precalc_init; 00132 00133 // For every block a depth value (4 blocks on every row, ordered 00134 // by rows). 00135 float depth[NUM_DEPTH]; 00136 // Minimum depth of all blocks. 00137 float tile_min_depth; 00138 // Maximum depth of all blocks. 00139 float tile_max_depth; 00140 00141 // Line Operations that are waiting to be executed. 00142 int num_operations; 00143 int max_operations; 00144 csLineOperation* operations; 00145 00146 // A temporary values that are used to test if the objects in the write 00147 // queue can actually help cull the object. 00148 bool covered; 00149 bool fully_covered; 00150 00151 // Add an operation. 00152 csLineOperation& AddOperation (); 00153 00154 // Check if the precalc tables are precalculated. If not 00155 // precalculate them. 00156 static void MakePrecalcTables (); 00157 00158 // Count how many objects were occluded away that covered this tile. 00159 int objects_culled; 00160 00161 public: 00162 csCoverageTile () : 00163 tile_full (false), 00164 queue_tile_empty (true), 00165 num_operations (0), 00166 max_operations (16), 00167 covered (false) 00168 { 00169 operations = new csLineOperation [16]; 00170 MakePrecalcTables (); 00171 MakeEmpty (); 00172 } 00173 00174 ~csCoverageTile () 00175 { 00176 delete[] operations; 00177 } 00178 00183 void MarkEmpty () 00184 { 00185 queue_tile_empty = true; 00186 tile_full = false; 00187 objects_culled = 0; 00188 } 00189 00190 #define INIT_MIN_DEPTH 999999999.0f 00191 #define INIT_MIN_DEPTH_CMP 999900000.0f 00192 00197 void MakeEmpty () 00198 { 00199 tile_full = false; queue_tile_empty = false; 00200 memset (coverage, 0, sizeof (csTileCol)*NUM_TILECOL); 00201 memset (depth, 0, sizeof (float)*NUM_DEPTH); 00202 tile_min_depth = INIT_MIN_DEPTH; 00203 tile_max_depth = 0; 00204 objects_culled = 0; 00205 } 00206 00212 void MakeEmptyQuick () 00213 { 00214 queue_tile_empty = false; 00215 memset (depth, 0, sizeof (float)*NUM_DEPTH); 00216 tile_min_depth = INIT_MIN_DEPTH; 00217 tile_max_depth = 0; 00218 objects_culled = 0; 00219 } 00220 00224 void ClearOperations () 00225 { 00226 num_operations = 0; 00227 } 00228 00232 bool IsFull () const { return tile_full; } 00233 00239 bool IsEmpty () const { return queue_tile_empty; } 00240 00244 void PushLine (int x1, int y1, int x2, int y2, int dx); 00245 00249 void PushVLine (int x, int y1, int y2); 00250 00254 void PushFullVLine (int x); 00255 00259 void PerformOperations (); 00260 00266 void FlushOperations (); 00267 00272 void PerformOperationsOnlyFValue (csTileCol& fvalue); 00273 00280 void FlushOperationsOnlyFValue (csTileCol& fvalue); 00281 00282 //----------------------------------------------------------------- 00283 00293 bool Flush (csTileCol& fvalue, float maxdepth); 00294 00298 bool FlushIgnoreDepth (csTileCol& fvalue); 00299 00304 bool FlushForEmpty (csTileCol& fvalue, float maxdepth); 00305 00310 bool FlushForEmptyNoDepth (csTileCol& fvalue); 00311 00316 bool FlushForFull (csTileCol& fvalue, float maxdepth); 00317 00322 bool FlushNoDepth (csTileCol& fvalue); 00323 00328 bool FlushGeneral (csTileCol& fvalue, float maxdepth); 00329 00334 void FlushForEmptyConstFValue (csTileCol& fvalue, float maxdepth); 00335 00340 void FlushForFullConstFValue (csTileCol& fvalue, float maxdepth); 00341 00347 bool FlushNoDepthConstFValue (csTileCol& fvalue, float maxdepth); 00348 00354 bool FlushGeneralConstFValue (csTileCol& fvalue, float maxdepth); 00355 00356 //----------------------------------------------------------------- 00357 00362 bool TestCoverageFlush (csTileCol& fvalue, float mindepth, 00363 bool& do_depth_test); 00364 00368 bool TestCoverageFlushForFull (csTileCol& fvalue, float mindepth, 00369 bool& do_depth_test); 00370 00374 bool TestCoverageFlushGeneral (csTileCol& fvalue, float maxdepth, 00375 bool& do_depth_test); 00376 00377 //----------------------------------------------------------------- 00378 00383 bool TestDepthFlush (csTileCol& fvalue, float mindepth); 00384 00388 bool TestDepthFlushGeneral (csTileCol& fvalue, float maxdepth); 00389 00390 //----------------------------------------------------------------- 00391 00400 bool TestFullRect (float testdepth); 00401 00406 bool TestDepthRect (int start, int end, float testdepth); 00407 00413 bool TestDepthRect (const csTileCol& vermask, int start, int end, 00414 float testdepth); 00415 00420 bool TestCoverageRect (int start, int end, float testdepth, 00421 bool& do_depth_test); 00422 00428 bool TestCoverageRect (const csTileCol& vermask, int start, int end, 00429 float testdepth, bool& do_depth_test); 00430 00431 //----------------------------------------------------------------- 00436 bool TestPoint (int x, int y, float testdepth); 00437 00441 csPtr<iString> Debug_Dump (); 00442 00446 csPtr<iString> Debug_Dump_Cache (); 00447 }; 00448 00457 class CS_CSGEOM_EXPORT csTiledCoverageBuffer : public iBase 00458 { 00459 public: 00460 iBugPlug* bugplug; // For debugging... 00461 00462 private: 00463 int width, height; 00464 int width_po2; // Width after correcting for power of two. 00465 int height_64; // Height after making it a multiple of 64. 00466 int w_shift; // Horizontal shift for width_po2 for tile multiples. 00467 int num_tile_rows; 00468 00469 // All tiles representing the screen (ordered by rows). 00470 int num_tiles; 00471 csCoverageTile* tiles; 00472 00473 // For every row the following arrays contain the left-most and 00474 // right-most horizontal tile number that was affected by the polygon/outline. 00475 // DrawLine() will update these values. 00476 int* dirty_left; 00477 int* dirty_right; 00478 00485 void DrawLine (int x1, int y1, int x2, int y2, int yfurther = 0); 00486 00495 bool DrawPolygon (csVector2* verts, int num_verts, csBox2Int& bbox); 00496 00503 bool DrawOutline (const csReversibleTransform& trans, 00504 float fov, float sx, float sy, csVector3* verts, int num_verts, 00505 bool* used_verts, 00506 int* edges, int num_edges, csBox2Int& bbox, 00507 float& max_depth, bool splat_outline); 00508 00512 csCoverageTile* GetTile (int tx, int ty) 00513 { 00514 CS_ASSERT (tx >= 0); 00515 CS_ASSERT (ty >= 0 && ty < num_tile_rows); 00516 return &tiles[(ty<<w_shift) + tx]; 00517 } 00518 00522 void MarkTileDirty (int tx, int ty) 00523 { 00524 CS_ASSERT (ty >= 0 && ty < num_tile_rows); 00525 if (tx < dirty_left[ty]) dirty_left[ty] = tx; 00526 if (tx > dirty_right[ty]) dirty_right[ty] = tx; 00527 } 00528 00529 public: 00531 csTiledCoverageBuffer (int w, int h); 00533 virtual ~csTiledCoverageBuffer (); 00534 00536 void Setup (int w, int h); 00537 00538 SCF_DECLARE_IBASE; 00539 00541 void Initialize (); 00542 00552 bool TestPolygon (csVector2* verts, int num_verts, float min_depth); 00553 00557 void InsertPolygonInverted (csVector2* verts, int num_verts, float max_depth); 00558 00565 void InsertPolygonInvertedNoDepth (csVector2* verts, int num_verts); 00566 00577 int InsertPolygon (csVector2* verts, int num_verts, float max_depth, 00578 csBox2Int& modified_bbox); 00579 00591 int InsertPolygonNoDepth (csVector2* verts, int num_verts); 00592 00606 int InsertOutline (const csReversibleTransform& trans, 00607 float fov, float sx, float sy, csVector3* verts, int num_verts, 00608 bool* used_verts, 00609 int* edges, int num_edges, bool splat_outline, 00610 csBox2Int& modified_bbox); 00611 00617 bool PrepareTestRectangle (const csBox2& rect, csTestRectData& data); 00618 00625 bool TestRectangle (const csTestRectData& data, float min_depth); 00626 00634 bool QuickTestRectangle (const csTestRectData& data, float min_depth); 00635 00640 void MarkCulledObject (const csTestRectData& data); 00641 00646 int CountNotCulledObjects (const csBox2Int& bbox); 00647 00653 int PrepareWriteQueueTest (const csTestRectData& data, float min_depth); 00654 00662 int AddWriteQueueTest (const csTestRectData& maindata, 00663 const csTestRectData& data, bool& relevant); 00664 00670 bool TestPoint (const csVector2& point, float min_depth); 00671 00677 int StatusNoDepth (); 00678 00679 // Debugging functions. 00680 csPtr<iString> Debug_UnitTest (); 00681 csTicks Debug_Benchmark (int num_iterations); 00682 void Debug_Dump (iGraphics3D* g3d, int zoom = 1); 00683 csPtr<iString> Debug_Dump (); 00684 00685 struct DebugHelper : public iDebugHelper 00686 { 00687 SCF_DECLARE_EMBEDDED_IBASE (csTiledCoverageBuffer); 00688 virtual int GetSupportedTests () const 00689 { 00690 return CS_DBGHELP_UNITTEST | 00691 CS_DBGHELP_BENCHMARK | 00692 CS_DBGHELP_GFXDUMP | 00693 CS_DBGHELP_TXTDUMP; 00694 } 00695 virtual csPtr<iString> UnitTest () 00696 { 00697 return scfParent->Debug_UnitTest (); 00698 } 00699 virtual csPtr<iString> StateTest () 00700 { 00701 return 0; 00702 } 00703 virtual csTicks Benchmark (int num_iterations) 00704 { 00705 return scfParent->Debug_Benchmark (num_iterations); 00706 } 00707 virtual csPtr<iString> Dump () 00708 { 00709 return scfParent->Debug_Dump (); 00710 } 00711 virtual void Dump (iGraphics3D* g3d) 00712 { 00713 scfParent->Debug_Dump (g3d, 1); 00714 } 00715 virtual bool DebugCommand (const char*) 00716 { 00717 return false; 00718 } 00719 } scfiDebugHelper; 00720 }; 00721 00722 #endif // __CS_CSGEOM_TCOVBUF_H__ 00723
Generated for Crystal Space by doxygen 1.3.9.1