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 (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   // Debugging functions.  
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 

Generated for Crystal Space 2.0 by doxygen 1.7.6.1