CrystalSpace

Public API Reference

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