CrystalSpace

Public API Reference

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 

Generated for Crystal Space 1.2.1 by doxygen 1.5.3