## Public API Reference

- Main Page
- Modules
- Namespaces
- Classes
- Files
- Related Pages

- File List
- File Members

# csgeom/tcovbuf.h

Go to the documentation of this file.

    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
    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 //to force it to signed
    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 // Line operations in a tile.
    00100 enum
    00101 {
    00102   OP_LINE = 1,  // General line.
    00103   OP_VLINE = 2, // Vertical line.
    00104   OP_FULLVLINE = 3      // Full vertical line (from 0 to 63).
    00105 };
    00106
    00107 // A definition for a line operation.
    00108 struct csLineOperation
    00109 {
    00110   uint8 op;             // One of OP_...
    00111   // All coordinates are with 0,0 relative to top-left of tile.
    00112   // x coordinates are also shifted 16 to the left.
    00113   int x1;               // Start of line.
    00114   int y1;               // Start of line. Not used with OP_FULLVLINE.
    00115   int x2;               // End of line. Only used with OP_LINE.
    00116   int y2;               // End of line. Not used with OP_FULLVLINE.
    00117   int dx;               // Slope to add to x1 (shifted 16 to left).
    00118 };
    00119
    00125 class CS_CRYSTALSPACE_EXPORT csCoverageTile
    00126 {
    00127   friend class csTiledCoverageBuffer;
    00128
    00129 private:
    00130   // If true entire tile is full.
    00131   bool tile_full;
    00132   // If true tile is queued as empty but 'coverage' and other
    00133   // data structures may not yet reflect this.
    00134   bool queue_tile_empty;
    00135
    00136   // The coverage bits.
    00137   csTileCol coverage[NUM_TILECOL];
    00138
    00139   // The cache on which we will write lines before or-ing that to the
    00140   // real coverage bits.
    00141   static csTileCol coverage_cache[NUM_TILECOL];
    00142
    00143   // This is an array of precalculated bit-sets for vertical line
    00144   // segments that start at 'n' and go to 63.
    00145   static csTileCol precalc_end_lines[NUM_TILEROW];
    00146   // This is an array of precalculated bit-sets for vertical line
    00147   // segments that start at 0 and go to 'n'.
    00148   static csTileCol precalc_start_lines[NUM_TILEROW];
    00149   // If true the two arrays above are initialized.
    00150   static bool precalc_init;
    00151
    00152   // For every block a depth value (4 blocks on every row, ordered
    00153   // by rows).
    00154   float depth[NUM_DEPTH];
    00155   // Minimum depth of all blocks.
    00156   float tile_min_depth;
    00157   // Maximum depth of all blocks.
    00158   float tile_max_depth;
    00159
    00160   // Line Operations that are waiting to be executed.
    00161   int num_operations;
    00162   int max_operations;
    00163   csLineOperation* operations;
    00164
    00165   // A temporary values that are used to test if the objects in the write
    00166   // queue can actually help cull the object.
    00167   bool covered;
    00168   bool fully_covered;
    00169
    00170   // Add an operation.
    00171   csLineOperation& AddOperation ();
    00172
    00173   // Check if the precalc tables are precalculated. If not
    00174   // precalculate them.
    00175   static void MakePrecalcTables ();
    00176
    00177   // Count how many objects were occluded away that covered this tile.
    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;    // For debugging...
    00481
    00482 private:
    00483   int width, height;
    00484   int width_po2;        // Width after correcting for power of two.
    00485   int height_64;        // Height after making it a multiple of 64.
    00486   int w_shift;          // Horizontal shift for width_po2 for tile multiples.
    00487   int num_tile_rows;
    00488
    00489   // All tiles representing the screen (ordered by rows).
    00490   int num_tiles;
    00491   csCoverageTile* tiles;
    00492
    00493   // For every row the following arrays contain the left-most and
    00494   // right-most horizontal tile number that was affected by the polygon/outline.
    00495   // DrawLine() will update these values.
    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 (csVector2* verts, size_t num_verts, csBox2Int& bbox);
    00516
    00523   bool DrawOutline (const csReversibleTransform& trans,
    00524         float fov, float sx, float sy, csVector3* verts, size_t num_verts,
    00525         bool* used_verts,
    00526         int* edges, size_t num_edges, csBox2Int& bbox,
    00527         float& max_depth, bool splat_outline);
    00528
    00532   inline csCoverageTile* GetTile (int tx, int ty)
    00533   {
    00534     CS_ASSERT (tx >= 0);
    00535     CS_ASSERT (ty >= 0 && ty < num_tile_rows);
    00536     return &tiles[(ty<<w_shift) + tx];
    00537   }
    00538
    00542   inline void MarkTileDirty (int tx, int ty)
    00543   {
    00544     CS_ASSERT (ty >= 0 && ty < num_tile_rows);
    00545     if (tx < dirty_left[ty]) dirty_left[ty] = tx;
    00546     if (tx > dirty_right[ty]) dirty_right[ty] = tx;
    00547   }
    00548
    00549 public:
    00551   csTiledCoverageBuffer (int w, int h);
    00553   virtual ~csTiledCoverageBuffer ();
    00554
    00556   void Setup (int w, int h);
    00557
    00559   void Initialize ();
    00560
    00570   bool TestPolygon (csVector2* verts, size_t num_verts, float min_depth);
    00571
    00575   void InsertPolygonInverted (csVector2* verts, size_t num_verts,
    00576         float max_depth);
    00577
    00584   void InsertPolygonInvertedNoDepth (csVector2* verts, size_t num_verts);
    00585
    00596   int InsertPolygon (csVector2* verts, size_t num_verts, float max_depth,
    00597         csBox2Int& modified_bbox);
    00598
    00610   int InsertPolygonNoDepth (csVector2* verts, size_t num_verts);
    00611
    00625   int InsertOutline (const csReversibleTransform& trans,
    00626         float fov, float sx, float sy, csVector3* verts, size_t num_verts,
    00627         bool* used_verts,
    00628         int* edges, size_t num_edges, bool splat_outline,
    00629         csBox2Int& modified_bbox);
    00630
    00636   bool PrepareTestRectangle (const csBox2& rect, csTestRectData& data);
    00637
    00644   bool TestRectangle (const csTestRectData& data, float min_depth);
    00645
    00653   bool QuickTestRectangle (const csTestRectData& data, float min_depth);
    00654
    00659   void MarkCulledObject (const csTestRectData& data);
    00660
    00665   int CountNotCulledObjects (const csBox2Int& bbox);
    00666
    00672   int PrepareWriteQueueTest (const csTestRectData& data, float min_depth);
    00673
    00681   int AddWriteQueueTest (const csTestRectData& maindata,
    00682         const csTestRectData& data, bool& relevant);
    00683
    00689   bool TestPoint (const csVector2& point, float min_depth);
    00690
    00696   int StatusNoDepth ();
    00697
    00698   // Debugging functions.
    00699   csPtr<iString> Debug_UnitTest ();
    00700   csTicks Debug_Benchmark (int num_iterations);
    00701   void Debug_Dump (iGraphics3D* g3d, int zoom = 1);
    00702   csPtr<iString> Debug_Dump ();
    00703
    00704   virtual int GetSupportedTests () const
    00705   {
    00706     return CS_DBGHELP_UNITTEST |
    00707            CS_DBGHELP_BENCHMARK |
    00708            CS_DBGHELP_GFXDUMP |
    00709            CS_DBGHELP_TXTDUMP;
    00710   }
    00711   virtual csPtr<iString> UnitTest ()
    00712   {
    00713     return Debug_UnitTest ();
    00714   }
    00715   virtual csPtr<iString> StateTest ()
    00716   {
    00717     return 0;
    00718   }
    00719   virtual csTicks Benchmark (int num_iterations)
    00720   {
    00721     return Debug_Benchmark (num_iterations);
    00722   }
    00723   virtual csPtr<iString> Dump ()
    00724   {
    00725     return Debug_Dump ();
    00726   }
    00727   virtual void Dump (iGraphics3D* g3d)
    00728   {
    00729     Debug_Dump (g3d, 1);
    00730   }
    00731   virtual bool DebugCommand (const char*)
    00732   {
    00733     return false;
    00734   }
    00735 };
    00736
    00739 #endif // __CS_CSGEOM_TCOVBUF_H__
    00740