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