00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019 #ifndef __CS_CSGEOM_TCOVBUF_H__
00020 #define __CS_CSGEOM_TCOVBUF_H__
00021
00022 #include "csextern.h"
00023
00024 #include "csutil/scf_implementation.h"
00025 #include "iutil/dbghelp.h"
00026 #include "csutil/ref.h"
00027
00034 struct iGraphics2D;
00035 struct iGraphics3D;
00036 struct iBugPlug;
00037
00038 class csBox2;
00039 class csReversibleTransform;
00040 class csString;
00041 class csVector2;
00042 class csVector3;
00043
00044
00045 class csTiledCoverageBuffer;
00046
00047
00048 enum
00049 {
00050 SHIFT_TILECOL = 6,
00051 SHIFT_TILEROW = 5,
00052
00053 NUM_TILECOL = (1<<SHIFT_TILECOL),
00054 NUM_TILEROW = (1<<SHIFT_TILEROW),
00055 NUM_DEPTHROW = (NUM_TILEROW/8),
00056 NUM_DEPTHCOL = (NUM_TILECOL/8),
00057 NUM_DEPTH = (NUM_DEPTHROW * NUM_DEPTHCOL),
00058
00059 TILECOL_EMPTY = 0,
00060 TILECOL_FULL = ((uint32)~0),
00061
00062 TEST_OCCLUDER_QUALITY = 1,
00063 TB_DUMMY = -1
00064 };
00065
00066 typedef uint32 csTileCol;
00067
00071 class csBox2Int
00072 {
00073 public:
00074 int minx, miny;
00075 int maxx, maxy;
00076 csBox2Int& operator+= (const csBox2Int& box)
00077 {
00078 if (box.minx < minx) minx = box.minx;
00079 if (box.miny < miny) miny = box.miny;
00080 if (box.maxx > maxx) maxx = box.maxx;
00081 if (box.maxy > maxy) maxy = box.maxy;
00082 return *this;
00083 }
00084 };
00085
00090 struct csTestRectData
00091 {
00092 csBox2Int bbox;
00093 int startrow, endrow;
00094 int startcol, endcol;
00095 int start_x, end_x;
00096 };
00097
00098
00099
00100 enum
00101 {
00102 OP_LINE = 1,
00103 OP_VLINE = 2,
00104 OP_FULLVLINE = 3
00105 };
00106
00107
00108 struct csLineOperation
00109 {
00110 uint8 op;
00111
00112
00113 int x1;
00114 int y1;
00115 int x2;
00116 int y2;
00117 int dx;
00118 };
00119
00125 class CS_CRYSTALSPACE_EXPORT csCoverageTile
00126 {
00127 friend class csTiledCoverageBuffer;
00128
00129 private:
00130
00131 bool tile_full;
00132
00133
00134 bool queue_tile_empty;
00135
00136
00137 csTileCol coverage[NUM_TILECOL];
00138
00139
00140
00141 static csTileCol coverage_cache[NUM_TILECOL];
00142
00143
00144
00145 static csTileCol precalc_end_lines[NUM_TILEROW];
00146
00147
00148 static csTileCol precalc_start_lines[NUM_TILEROW];
00149
00150 static bool precalc_init;
00151
00152
00153
00154 float depth[NUM_DEPTH];
00155
00156 float tile_min_depth;
00157
00158 float tile_max_depth;
00159
00160
00161 int num_operations;
00162 int max_operations;
00163 csLineOperation* operations;
00164
00165
00166
00167 bool covered;
00168 bool fully_covered;
00169
00170
00171 csLineOperation& AddOperation ();
00172
00173
00174
00175 static void MakePrecalcTables ();
00176
00177
00178 int objects_culled;
00179
00180 public:
00181 csCoverageTile () :
00182 tile_full (false),
00183 queue_tile_empty (true),
00184 num_operations (0),
00185 max_operations (16),
00186 covered (false)
00187 {
00188 operations = new csLineOperation [16];
00189 MakePrecalcTables ();
00190 MakeEmpty ();
00191 }
00192
00193 ~csCoverageTile ()
00194 {
00195 delete[] operations;
00196 }
00197
00202 inline void MarkEmpty ()
00203 {
00204 queue_tile_empty = true;
00205 tile_full = false;
00206 objects_culled = 0;
00207 }
00208
00209 #define INIT_MIN_DEPTH 999999999.0f
00210 #define INIT_MIN_DEPTH_CMP 999900000.0f
00211
00216 inline void MakeEmpty ()
00217 {
00218 tile_full = false; queue_tile_empty = false;
00219 memset (coverage, 0, sizeof (csTileCol)*NUM_TILECOL);
00220 memset (depth, 0, sizeof (float)*NUM_DEPTH);
00221 tile_min_depth = INIT_MIN_DEPTH;
00222 tile_max_depth = 0;
00223 objects_culled = 0;
00224 }
00225
00231 inline void MakeEmptyQuick ()
00232 {
00233 queue_tile_empty = false;
00234 memset (depth, 0, sizeof (float)*NUM_DEPTH);
00235 tile_min_depth = INIT_MIN_DEPTH;
00236 tile_max_depth = 0;
00237 objects_culled = 0;
00238 }
00239
00243 inline void ClearOperations ()
00244 {
00245 num_operations = 0;
00246 }
00247
00251 inline bool IsFull () const { return tile_full; }
00252
00258 inline bool IsEmpty () const { return queue_tile_empty; }
00259
00263 void PushLine (int x1, int y1, int x2, int y2, int dx);
00264
00268 void PushVLine (int x, int y1, int y2);
00269
00273 void PushFullVLine (int x);
00274
00278 void PerformOperations ();
00279
00285 void FlushOperations ();
00286
00291 void PerformOperationsOnlyFValue (csTileCol& fvalue);
00292
00299 void FlushOperationsOnlyFValue (csTileCol& fvalue);
00300
00301
00302
00312 bool Flush (csTileCol& fvalue, float maxdepth);
00313
00317 bool FlushIgnoreDepth (csTileCol& fvalue);
00318
00323 bool FlushForEmpty (csTileCol& fvalue, float maxdepth);
00324
00329 bool FlushForEmptyNoDepth (csTileCol& fvalue);
00330
00335 bool FlushForFull (csTileCol& fvalue, float maxdepth);
00336
00341 bool FlushNoDepth (csTileCol& fvalue);
00342
00347 bool FlushGeneral (csTileCol& fvalue, float maxdepth);
00348
00353 void FlushForEmptyConstFValue (csTileCol& fvalue, float maxdepth);
00354
00359 void FlushForFullConstFValue (csTileCol& fvalue, float maxdepth);
00360
00366 bool FlushNoDepthConstFValue (csTileCol& fvalue, float maxdepth);
00367
00373 bool FlushGeneralConstFValue (csTileCol& fvalue, float maxdepth);
00374
00375
00376
00381 bool TestCoverageFlush (csTileCol& fvalue, float mindepth,
00382 bool& do_depth_test);
00383
00387 bool TestCoverageFlushForFull (csTileCol& fvalue, float mindepth,
00388 bool& do_depth_test);
00389
00393 bool TestCoverageFlushGeneral (csTileCol& fvalue, float maxdepth,
00394 bool& do_depth_test);
00395
00396
00397
00402 bool TestDepthFlush (csTileCol& fvalue, float mindepth);
00403
00407 bool TestDepthFlushGeneral (csTileCol& fvalue, float maxdepth);
00408
00409
00410
00419 bool TestFullRect (float testdepth);
00420
00425 bool TestDepthRect (int start, int end, float testdepth);
00426
00432 bool TestDepthRect (const csTileCol& vermask, int start, int end,
00433 float testdepth);
00434
00439 bool TestCoverageRect (int start, int end, float testdepth,
00440 bool& do_depth_test);
00441
00447 bool TestCoverageRect (const csTileCol& vermask, int start, int end,
00448 float testdepth, bool& do_depth_test);
00449
00450
00455 bool TestPoint (int x, int y, float testdepth);
00456
00460 csPtr<iString> Debug_Dump ();
00461
00465 csPtr<iString> Debug_Dump_Cache ();
00466 };
00467
00476 class CS_CRYSTALSPACE_EXPORT csTiledCoverageBuffer :
00477 public scfImplementation1<csTiledCoverageBuffer,iDebugHelper>
00478 {
00479 public:
00480 iBugPlug* bugplug;
00481
00482 private:
00483 int width, height;
00484 int width_po2;
00485 int height_64;
00486 int w_shift;
00487 int num_tile_rows;
00488
00489
00490 int num_tiles;
00491 csCoverageTile* tiles;
00492
00493
00494
00495
00496 int* dirty_left;
00497 int* dirty_right;
00498
00505 void DrawLine (int x1, int y1, int x2, int y2, int yfurther = 0);
00506
00515 bool DrawPolygon (const csVector2* verts, size_t num_verts, csBox2Int& bbox);
00516
00518
00524 bool DrawOutline (const csReversibleTransform& trans,
00525 float fov, float sx, float sy, csVector3* verts, size_t num_verts,
00526 bool* used_verts,
00527 int* edges, size_t num_edges, csBox2Int& bbox,
00528 float& max_depth, bool splat_outline);
00529 bool DrawOutline (const csReversibleTransform& trans,
00530 const CS::Math::Matrix4& projection,
00531 csVector3* verts, size_t num_verts, bool* used_verts,
00532 int* edges, size_t num_edges, csBox2Int& bbox,
00533 float& max_depth, bool splat_outline);
00535
00539 inline csCoverageTile* GetTile (int tx, int ty)
00540 {
00541 CS_ASSERT (tx >= 0);
00542 CS_ASSERT (ty >= 0 && ty < num_tile_rows);
00543 return &tiles[(ty<<w_shift) + tx];
00544 }
00545
00549 inline void MarkTileDirty (int tx, int ty)
00550 {
00551 CS_ASSERT (ty >= 0 && ty < num_tile_rows);
00552 if (tx < dirty_left[ty]) dirty_left[ty] = tx;
00553 if (tx > dirty_right[ty]) dirty_right[ty] = tx;
00554 }
00555
00556 public:
00558 csTiledCoverageBuffer (int w, int h);
00560 virtual ~csTiledCoverageBuffer ();
00561
00563 void Setup (int w, int h);
00564
00565 void SetSize (int w, int h)
00566 {
00567 if ((w > width_po2) || (h > height_64)) Setup (w, h);
00568 width = w;
00569 height = h;
00570 }
00571
00573 void Initialize ();
00574
00584 bool TestPolygon (csVector2* verts, size_t num_verts, float min_depth);
00585
00589 void InsertPolygonInverted (const csVector2* verts, size_t num_verts,
00590 float max_depth);
00591
00598 void InsertPolygonInvertedNoDepth (const csVector2* verts, size_t num_verts);
00599
00610 int InsertPolygon (const csVector2* verts, size_t num_verts, float max_depth,
00611 csBox2Int& modified_bbox);
00612
00624 int InsertPolygonNoDepth (const csVector2* verts, size_t num_verts);
00625
00627
00640 int InsertOutline (const csReversibleTransform& trans,
00641 float fov, float sx, float sy, csVector3* verts, size_t num_verts,
00642 bool* used_verts,
00643 int* edges, size_t num_edges, bool splat_outline,
00644 csBox2Int& modified_bbox);
00645 int InsertOutline (const csReversibleTransform& trans,
00646 const CS::Math::Matrix4& projection,
00647 csVector3* verts, size_t num_verts, bool* used_verts,
00648 int* edges, size_t num_edges, bool splat_outline,
00649 csBox2Int& modified_bbox);
00651
00657 bool PrepareTestRectangle (const csBox2& rect, csTestRectData& data);
00658
00665 bool TestRectangle (const csTestRectData& data, float min_depth);
00666
00674 bool QuickTestRectangle (const csTestRectData& data, float min_depth);
00675
00680 void MarkCulledObject (const csTestRectData& data);
00681
00686 int CountNotCulledObjects (const csBox2Int& bbox);
00687
00693 int PrepareWriteQueueTest (const csTestRectData& data, float min_depth);
00694
00702 int AddWriteQueueTest (const csTestRectData& maindata,
00703 const csTestRectData& data, bool& relevant);
00704
00710 bool TestPoint (const csVector2& point, float min_depth);
00711
00717 int StatusNoDepth ();
00718
00719
00720 csTicks Debug_Benchmark (int num_iterations);
00721 void Debug_Dump (iGraphics3D* g3d, int zoom = 1);
00722 csPtr<iString> Debug_Dump ();
00723
00724 virtual int GetSupportedTests () const
00725 {
00726 return CS_DBGHELP_BENCHMARK |
00727 CS_DBGHELP_GFXDUMP |
00728 CS_DBGHELP_TXTDUMP;
00729 }
00730 virtual csPtr<iString> StateTest ()
00731 {
00732 return 0;
00733 }
00734 virtual csTicks Benchmark (int num_iterations)
00735 {
00736 return Debug_Benchmark (num_iterations);
00737 }
00738 virtual csPtr<iString> Dump ()
00739 {
00740 return Debug_Dump ();
00741 }
00742 virtual void Dump (iGraphics3D* g3d)
00743 {
00744 Debug_Dump (g3d, 1);
00745 }
00746 virtual bool DebugCommand (const char*)
00747 {
00748 return false;
00749 }
00750 };
00751
00754 #endif // __CS_CSGEOM_TCOVBUF_H__
00755