src/bitmask.h

   1 /*
   2  *                         bitmask.c 1.0
   3  *                         -------------
   4  *    Simple and efficient bitmask collision detection routines
   5  *  Copyright (C) 2002 Ulf Ekstrom except for the bitcount function.
   6  *
   7  *  A bitmask is a simple array of bits, which can be used for
   8  *  2d collision detection. Set 'unoccupied' area to zero and
   9  *  occupies areas to one and use the bitmask_overlap*() functions
  10  *  to check for collisions.
  11  *  The current implementation uses 32 bit wide stripes to hold
  12  *  the masks, but should work just as well with 64 bit sizes.
  13  *
  14  *  The overlap tests uses the following offsets (which may be negative):
  15  *
  16  *   +----+----------..
  17  *   |A   | yoffset
  18  *   |  +-+----------..
  19  *   +--|B
  20  *   |xoffset
  21  *   |  |
  22  *   :  :
  23  *
  24  *  For optimal collision detection performance combine these functions
  25  *  with some kind of pre-sorting to avoid comparing objects far from
  26  *  each other.
  27  *
  28  *  Performance of the various functions goes something like:
  29  *  (relative timings, smaller is better)
  30  *
  31  *  bitmask_overlap()        1.0
  32  *  bitmask_overlap_pos()    1.3
  33  *  bitmask_overlap_area()   1.6
  34  *
  35  *  For maximum performance on my machine I use gcc with
  36  *  -O2 -fomit-frame-pointer -funroll-loops
  37  *
  38  *
  39  *  If you can make these functions faster or have found any bugs please
  40  *  email Ulf Ekstrom, ulfek@ifm.liu.se
  41  *
  42  *
  43  *
  44  * This program is free software; you can redistribute it and/or
  45  * modify it under the terms of the GNU General Public License
  46  * as published by the Free Software Foundation; either version 2
  47  * of the License, or (at your option) any later version.
  48  *
  49  * This program is distributed in the hope that it will be useful,
  50  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  51  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  52  * GNU General Public License for more details.
  53  *
  54  * You should have received a copy of the GNU General Public License
  55  * along with this program; if not, write to the Free Software
  56  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  57  */
  58 #ifndef SUPERTUX_BITMASK_H
  59 #define SUPERTUX_BITMASK_H
  60
  61 #include <SDL.h>
  62 #include <climits>
  63
  64 /* Define INLINE for different compilers. */
  65 #ifndef INLINE
  66 # ifdef __GNUC__
  67 #  define INLINE inline
  68 # else
  69 #  ifdef _MSC_VER
  70 #   define INLINE __inline
  71 #  else
  72 #   define INLINE
  73 #  endif
  74 # endif
  75 #endif
  76
  77 #define BITW unsigned long int
  78 #define BITW_LEN (sizeof(BITW)*CHAR_BIT)
  79 #define BITW_MASK (BITW_LEN - 1)
  80 #define BITN(n) ((BITW)1 << (n))
  81
  82 struct bitmask
  83 {
  84   int w,h;
  85   BITW *bits;
  86 };
  87
  88 /* Creates a bitmask of width w and height h.
  89  * The mask is automatically cleared when created.
  90  */
  91 bitmask *bitmask_create(int w, int h);
  92 void bitmask_free(bitmask *m);
  93
  94 void bitmask_clear(bitmask *m);
  95 void bitmask_fill(bitmask *m);
  96
  97 /* Returns nonzero if the bit at (x,y) is set.
  98  * Coordinates start at (0,0)
  99  */
 100 static INLINE int bitmask_getbit(const bitmask *m,int x,int y)
 101 {
 102   return m->bits[x/BITW_LEN*m->h + y] & BITN(x & BITW_MASK);
 103 }
 104
 105
 106 /* Sets the bit at (x,y) */
 107 static INLINE void bitmask_setbit(bitmask *m,int x,int y)
 108 {
 109   m->bits[x/BITW_LEN*m->h + y] |= BITN(x & BITW_MASK);
 110 }
 111
 112
 113 /* Clears the bit at (x,y) */
 114 static INLINE void bitmask_clearbit(bitmask *m,int x,int y)
 115 {
 116   m->bits[x/BITW_LEN*m->h + y] &= ~BITN(x & BITW_MASK);
 117 }
 118
 119
 120 /* Returns nonzero if the masks overlap with the given offset. */
 121 int bitmask_overlap(const bitmask *a,const bitmask *b,int xoffset, int yoffset);
 122
 123 /* Like bitmask_overlap(), but will also give a point of intersection.
 124  * x and y are given in the coordinates of mask a, and are untouched if there is
 125  * no overlap.
 126  */
 127 int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffset, int *x, int *y);
 128
 129 /* Returns the number of overlapping 'pixels' */
 130 int bitmask_overlap_area(const bitmask *a,const bitmask *b,int xoffset, int yoffset);
 131
 132 /* Draws mask b onto mask a (bitwise OR)
 133  * Can be used to compose large (game background?) mask from
 134  * several submasks, which may speed up the testing.
 135  */
 136 void bitmask_draw(bitmask *a,bitmask *b,int xoffset, int yoffset);
 137
 138 /* Create a bitmask from a SDL_Surface */
 139 bitmask* bitmask_create_SDL(SDL_Surface* surf);
 140
 141 #endif /*SUPERTUX_BITMASK_H*/