Public API Reference

csgeom/tcovbuf.h

Go to the documentation of this file.

/*
    Copyright (C) 2002-2005 by Jorrit Tyberghein

    This library is free software; you can redistribute it and/or
    modify it under the terms of the GNU Library General Public
    License as published by the Free Software Foundation; either
    version 2 of the License, or (at your option) any later version.

    This library is distributed in the hope that it will be useful,
    but WITHOUT ANY WARRANTY; without even the implied warranty of
    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    Library General Public License for more details.

    You should have received a copy of the GNU Library General Public
    License along with this library; if not, write to the Free
    Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

#ifndef __CS_CSGEOM_TCOVBUF_H__
#define __CS_CSGEOM_TCOVBUF_H__

#include "csextern.h"

#include "csutil/scf_implementation.h"
#include "iutil/dbghelp.h"
#include "csutil/ref.h"

struct iGraphics2D;
struct iGraphics3D;
struct iBugPlug;

class csBox2;
class csReversibleTransform;
class csString;
class csVector2;
class csVector3;


class csTiledCoverageBuffer;


enum
{
  SHIFT_TILECOL = 6,
  SHIFT_TILEROW = 5,

  NUM_TILECOL = (1<<SHIFT_TILECOL),
  NUM_TILEROW = (1<<SHIFT_TILEROW),
  NUM_DEPTHROW = (NUM_TILEROW/8),
  NUM_DEPTHCOL = (NUM_TILECOL/8),
  NUM_DEPTH = (NUM_DEPTHROW * NUM_DEPTHCOL),

  TILECOL_EMPTY = 0,
  TILECOL_FULL = ((uint32)~0),

  TEST_OCCLUDER_QUALITY = 1,
  TB_DUMMY = -1 //to force it to signed
};

typedef uint32 csTileCol;

class csBox2Int
{
public:
  int minx, miny;
  int maxx, maxy;
  csBox2Int& operator+= (const csBox2Int& box)
  {
    if (box.minx < minx) minx = box.minx;
    if (box.miny < miny) miny = box.miny;
    if (box.maxx > maxx) maxx = box.maxx;
    if (box.maxy > maxy) maxy = box.maxy;
    return *this;
  }
};

struct csTestRectData
{
  csBox2Int bbox;
  int startrow, endrow;
  int startcol, endcol;
  int start_x, end_x;
};


// Line operations in a tile.
enum
{
  OP_LINE = 1,  // General line.
  OP_VLINE = 2, // Vertical line.
  OP_FULLVLINE = 3      // Full vertical line (from 0 to 63).
};

// A definition for a line operation.
struct csLineOperation
{
  uint8 op;             // One of OP_...
  // All coordinates are with 0,0 relative to top-left of tile.
  // x coordinates are also shifted 16 to the left.
  int x1;               // Start of line.
  int y1;               // Start of line. Not used with OP_FULLVLINE.
  int x2;               // End of line. Only used with OP_LINE.
  int y2;               // End of line. Not used with OP_FULLVLINE.
  int dx;               // Slope to add to x1 (shifted 16 to left).
};

class CS_CRYSTALSPACE_EXPORT csCoverageTile
{
  friend class csTiledCoverageBuffer;

private:
  // If true entire tile is full.
  bool tile_full;
  // If true tile is queued as empty but 'coverage' and other
  // data structures may not yet reflect this.
  bool queue_tile_empty;

  // The coverage bits.
  csTileCol coverage[NUM_TILECOL];

  // The cache on which we will write lines before or-ing that to the
  // real coverage bits.
  static csTileCol coverage_cache[NUM_TILECOL];

  // This is an array of precalculated bit-sets for vertical line
  // segments that start at 'n' and go to 63.
  static csTileCol precalc_end_lines[NUM_TILEROW];
  // This is an array of precalculated bit-sets for vertical line
  // segments that start at 0 and go to 'n'.
  static csTileCol precalc_start_lines[NUM_TILEROW];
  // If true the two arrays above are initialized.
  static bool precalc_init;

  // For every block a depth value (4 blocks on every row, ordered
  // by rows).
  float depth[NUM_DEPTH];
  // Minimum depth of all blocks.
  float tile_min_depth;
  // Maximum depth of all blocks.
  float tile_max_depth;

  // Line Operations that are waiting to be executed.
  int num_operations;
  int max_operations;
  csLineOperation* operations;

  // A temporary values that are used to test if the objects in the write
  // queue can actually help cull the object.
  bool covered;
  bool fully_covered;

  // Add an operation.
  csLineOperation& AddOperation ();

  // Check if the precalc tables are precalculated. If not
  // precalculate them.
  static void MakePrecalcTables ();

  // Count how many objects were occluded away that covered this tile.
  int objects_culled;

public:
  csCoverageTile () :
        tile_full (false),
        queue_tile_empty (true),
        num_operations (0),
        max_operations (16),
        covered (false)
  {
    operations = new csLineOperation [16];
    MakePrecalcTables ();
    MakeEmpty ();
  }

  ~csCoverageTile ()
  {
    delete[] operations;
  }

  inline void MarkEmpty ()
  {
    queue_tile_empty = true;
    tile_full = false;
    objects_culled = 0;
  }

#define INIT_MIN_DEPTH     999999999.0f
#define INIT_MIN_DEPTH_CMP 999900000.0f

  inline void MakeEmpty ()
  {
    tile_full = false; queue_tile_empty = false;
    memset (coverage, 0, sizeof (csTileCol)*NUM_TILECOL);
    memset (depth, 0, sizeof (float)*NUM_DEPTH);
    tile_min_depth = INIT_MIN_DEPTH;
    tile_max_depth = 0;
    objects_culled = 0;
  }

  inline void MakeEmptyQuick ()
  {
    queue_tile_empty = false;
    memset (depth, 0, sizeof (float)*NUM_DEPTH);
    tile_min_depth = INIT_MIN_DEPTH;
    tile_max_depth = 0;
    objects_culled = 0;
  }

  inline void ClearOperations ()
  {
    num_operations = 0;
  }

  inline bool IsFull () const { return tile_full; }

  inline bool IsEmpty () const { return queue_tile_empty; }

  void PushLine (int x1, int y1, int x2, int y2, int dx);

  void PushVLine (int x, int y1, int y2);

  void PushFullVLine (int x);

  void PerformOperations ();

  void FlushOperations ();

  void PerformOperationsOnlyFValue (csTileCol& fvalue);

  void FlushOperationsOnlyFValue (csTileCol& fvalue);

  //-----------------------------------------------------------------

  bool Flush (csTileCol& fvalue, float maxdepth);

  bool FlushIgnoreDepth (csTileCol& fvalue);

  bool FlushForEmpty (csTileCol& fvalue, float maxdepth);

  bool FlushForEmptyNoDepth (csTileCol& fvalue);

  bool FlushForFull (csTileCol& fvalue, float maxdepth);

  bool FlushNoDepth (csTileCol& fvalue);

  bool FlushGeneral (csTileCol& fvalue, float maxdepth);

  void FlushForEmptyConstFValue (csTileCol& fvalue, float maxdepth);

  void FlushForFullConstFValue (csTileCol& fvalue, float maxdepth);

  bool FlushNoDepthConstFValue (csTileCol& fvalue, float maxdepth);

  bool FlushGeneralConstFValue (csTileCol& fvalue, float maxdepth);

  //-----------------------------------------------------------------

  bool TestCoverageFlush (csTileCol& fvalue, float mindepth,
        bool& do_depth_test);

  bool TestCoverageFlushForFull (csTileCol& fvalue, float mindepth,
        bool& do_depth_test);

  bool TestCoverageFlushGeneral (csTileCol& fvalue, float maxdepth,
        bool& do_depth_test);

  //-----------------------------------------------------------------

  bool TestDepthFlush (csTileCol& fvalue, float mindepth);

  bool TestDepthFlushGeneral (csTileCol& fvalue, float maxdepth);

  //-----------------------------------------------------------------

  bool TestFullRect (float testdepth);

  bool TestDepthRect (int start, int end, float testdepth);

  bool TestDepthRect (const csTileCol& vermask, int start, int end,
        float testdepth);

  bool TestCoverageRect (int start, int end, float testdepth,
        bool& do_depth_test);

  bool TestCoverageRect (const csTileCol& vermask, int start, int end,
        float testdepth, bool& do_depth_test);

  //-----------------------------------------------------------------
  bool TestPoint (int x, int y, float testdepth);

  csPtr<iString> Debug_Dump ();

  csPtr<iString> Debug_Dump_Cache ();
};

class CS_CRYSTALSPACE_EXPORT csTiledCoverageBuffer :
  public scfImplementation1<csTiledCoverageBuffer,iDebugHelper>
{
public:
  iBugPlug* bugplug;    // For debugging...

private:
  int width, height;
  int width_po2;        // Width after correcting for power of two.
  int height_64;        // Height after making it a multiple of 64.
  int w_shift;          // Horizontal shift for width_po2 for tile multiples.
  int num_tile_rows;

  // All tiles representing the screen (ordered by rows).
  int num_tiles;
  csCoverageTile* tiles;

  // For every row the following arrays contain the left-most and
  // right-most horizontal tile number that was affected by the polygon/outline.
  // DrawLine() will update these values.
  int* dirty_left;
  int* dirty_right;

  void DrawLine (int x1, int y1, int x2, int y2, int yfurther = 0);

  bool DrawPolygon (csVector2* verts, size_t num_verts, csBox2Int& bbox);

  bool DrawOutline (const csReversibleTransform& trans,
        float fov, float sx, float sy, csVector3* verts, size_t num_verts,
        bool* used_verts,
        int* edges, size_t num_edges, csBox2Int& bbox,
        float& max_depth, bool splat_outline);

  inline csCoverageTile* GetTile (int tx, int ty)
  {
    CS_ASSERT (tx >= 0);
    CS_ASSERT (ty >= 0 && ty < num_tile_rows);
    return &tiles[(ty<<w_shift) + tx];
  }

  inline void MarkTileDirty (int tx, int ty)
  {
    CS_ASSERT (ty >= 0 && ty < num_tile_rows);
    if (tx < dirty_left[ty]) dirty_left[ty] = tx;
    if (tx > dirty_right[ty]) dirty_right[ty] = tx;
  }

public:
  csTiledCoverageBuffer (int w, int h);
  virtual ~csTiledCoverageBuffer ();

  void Setup (int w, int h);

  void Initialize ();

  bool TestPolygon (csVector2* verts, size_t num_verts, float min_depth);

  void InsertPolygonInverted (csVector2* verts, size_t num_verts,
        float max_depth);

  void InsertPolygonInvertedNoDepth (csVector2* verts, size_t num_verts);

  int InsertPolygon (csVector2* verts, size_t num_verts, float max_depth,
        csBox2Int& modified_bbox);

  int InsertPolygonNoDepth (csVector2* verts, size_t num_verts);

  int InsertOutline (const csReversibleTransform& trans,
        float fov, float sx, float sy, csVector3* verts, size_t num_verts,
        bool* used_verts,
        int* edges, size_t num_edges, bool splat_outline,
        csBox2Int& modified_bbox);

  bool PrepareTestRectangle (const csBox2& rect, csTestRectData& data);

  bool TestRectangle (const csTestRectData& data, float min_depth);

  bool QuickTestRectangle (const csTestRectData& data, float min_depth);

  void MarkCulledObject (const csTestRectData& data);

  int CountNotCulledObjects (const csBox2Int& bbox);

  int PrepareWriteQueueTest (const csTestRectData& data, float min_depth);

  int AddWriteQueueTest (const csTestRectData& maindata,
        const csTestRectData& data, bool& relevant);

  bool TestPoint (const csVector2& point, float min_depth);

  int StatusNoDepth ();

  // Debugging functions.
  csPtr<iString> Debug_UnitTest ();
  csTicks Debug_Benchmark (int num_iterations);
  void Debug_Dump (iGraphics3D* g3d, int zoom = 1);
  csPtr<iString> Debug_Dump ();

  virtual int GetSupportedTests () const
  {
    return CS_DBGHELP_UNITTEST |
           CS_DBGHELP_BENCHMARK |
           CS_DBGHELP_GFXDUMP |
           CS_DBGHELP_TXTDUMP;
  }
  virtual csPtr<iString> UnitTest ()
  {
    return Debug_UnitTest ();
  }
  virtual csPtr<iString> StateTest ()
  {
    return 0;
  }
  virtual csTicks Benchmark (int num_iterations)
  {
    return Debug_Benchmark (num_iterations);
  }
  virtual csPtr<iString> Dump ()
  {
    return Debug_Dump ();
  }
  virtual void Dump (iGraphics3D* g3d)
  {
    Debug_Dump (g3d, 1);
  }
  virtual bool DebugCommand (const char*)
  {
    return false;
  }
};

#endif // __CS_CSGEOM_TCOVBUF_H__

---