#ifndef TriageMask_h #define TriageMask_h #include "iostream.h" #include "algebra3.h" typedef enum {FULL,EMPTY} FillType; #define NUMSUB 513 #define MASKSIZE 8 /**************************************************************** Class: Bitmask Purpose: 8x8 bitmask representing a polygon's coverage of a particular square screenspace region. The square region is divided into an 8x8 grid of subregions. Each bit in the mask represents a sample position at the centre of the corresponding subregion. The perimeter of the square region is discretized into 512 intervals, numbered from 0 at the bottom left, and proceeding counterclockwise to 512 (again at the bottom left). To compute the coverage of a particular polygon, you first compute the coverage masks for each edge of the polygon, then composite them together. To compute the mask for an edge, simply call the constructor, specifying the entry and exit points of the edge along the perimeter of the region. It is assumed that edge vertices are specified in counterclockwise order, so that the "inside" of an edge corresponds to the inside of the polygon to which that edge belongs. Edge masks are composited using one of the AND operators to construct the poly coverage mask. The initialize() method will precompute bitmasks for all possible edges. *****************************************************************/ class Bitmask { public: // Constructors Bitmask(); // empty bitmask Bitmask( Bitmask& b ); // copy constructor Bitmask( int in, int out ); // initialize from precomputed mask for edge // (in,out) Bitmask( FillType fill ); // initialize to empty or full // Boolean operations - in-place and external // AND operations friend Bitmask operator& ( Bitmask& left, Bitmask& right ); Bitmask& operator&= ( Bitmask& opnd ); // OR operations friend Bitmask operator| ( Bitmask& left, Bitmask& right ); Bitmask& operator|= ( Bitmask& opnd ); // complement operations friend Bitmask operator~ ( Bitmask& b ); Bitmask& complement(); // bitwise test/set methods int testBit( int x, int y ); // tests a single bit void setBit( int x, int y ); // sets a single bit void clearBit( int x, int y ); // clears a single bit void setBits( int x1, int y1, int x2, int y2 ); // sets a block of bits void clear(void); // clears the entire mask bool empty(void); // tests to see if the mask is empty void fill(void); // sets the entire mask bool full(void); // tests to see if the mask is full int numBits(); // counts the number of bits set in the mask // // Static methods for initializing precomputed tables // // initializes the tables static void initialize(); // tests for initialization static bool isInit() { return initialized; }; const static int maskSize; // determines the resolution of the mask, ie how many // subregions the mask divides a square into const static int subIntervals; // for each subregion, how many subdivisions are used // along its perimeter for identifying edge crossings // analytically computes the coverage mask for a particular edge, to be stored in the // lookup table static Bitmask computeMask( int in, int out ); // output operator friend ostream& operator << ( ostream& os, Bitmask& b ); private: // b1 and b2 together form a 64-bit square bitmask unsigned int b1; unsigned int b2; // are the precomputed tables initialized? static bool initialized; // precomputed edge bitmasks, indexed by entry and exit positions static Bitmask pre[NUMSUB][NUMSUB]; // precomputed rectangular bitmasks. preSumAbove[x][y] has all // bits set in the rectangular region whose lower left corner is (x,y), // and preSumBelow[x][y] has all bits set in the rectangular region whose // upper right corner is (x,y). These tables are used for the setBits() // operation for setting rectangular regions of bits. static Bitmask preSumAbove[MASKSIZE][MASKSIZE]; static Bitmask preSumBelow[MASKSIZE][MASKSIZE]; // precomputed bit counts for every 8-bit integer. Used by the // numBits() function. static unsigned char preBitcounts[256]; // converts an index along the perimeter of a region to a 2d position // in normalized [0..8][0..8] space. static vec2 indexToPos( int index ); }; /******************************************************************* Class: TriageMask Purpose: Triage coverage mask, as described in Greene '96. Whereas the Bitmask class represents visibility sampled on a regular 8x8 grid, triage masks represent area-sampled visibility. As with bitmasks, a triage mask subdivides a given region into a regular 8x8 grid. The triage mask consists of 3 8x8 bitmasks: The 'C' mask - denotes subregions that are completely covered by a polygon The 'V' mask - denotes subregions that are completely disjoint from a polygon The 'A' mask - denotes subregions that are partially covered by a polygon. The A mask is simply ~(C|V), so we only actually store the C and V masks. The computation of a polygon's triage mask is similar to the computation of a bitmask (described above). First, triage masks for the edges are constructed (we use the same 512-interval perimeter discretization as the Bitmask class), then the edge masks are combined, this time using the + or += operators. ********************************************************************/ class TriageMask { public: // Constructors TriageMask(); // empty mask TriageMask( TriageMask& t ); // copy constructor TriageMask( Bitmask& C, Bitmask& V ); // specify C, V masks up-front TriageMask( Bitmask& C ); // specify C only, assumes V = ~C TriageMask( int in, int out ); // construct edge mask by specifying // edge intersection indices with perimeter TriageMask( FillType which ); // construct empty or full triage mask // accessors for the C,V, and A masks Bitmask& C() { return c; }; Bitmask& V() { return v; }; Bitmask& A() { return ~(c|v); }; // set/test operators void fill() { c.fill(); v.clear(); }; // fills the mask bool full() { return c.full(); }; // checks for a full mask void clear() { c.clear(); v.fill(); }; // clears the mask bool empty() { return v.full(); }; // checks for an empty mask // operators for compositing edge masks together friend TriageMask operator+ ( TriageMask& l, TriageMask& r ); TriageMask& operator +=( TriageMask& t ); // // Static methods for initializing precomputed tables // // initializes the tables static void initialize(); // checks for initialization static bool isInit() { return initialized; }; const static int maskSize; // number of subregions each region is divided // into const static int subIntervals; // number of subintervals the perimeter of each // subregion is divided into // analytically computes the triage mask for a given edge, // used to initialize the precomputed table static TriageMask computeMask( int in, int out ); // output operator friend ostream& operator << ( ostream& os, TriageMask& t ); private: // stores the C and V bitmasks Bitmask c; Bitmask v; // whether or not the precomputed tables have been initialized static bool initialized; // precomputed triage masks static TriageMask pre[NUMSUB][NUMSUB]; // converts a perimeter index into a position static vec2 indexToPos( int index ); }; #endif