4 * Simple and efficient bitmask collision detection routines
5 * Copyright (C) 2002 Ulf Ekstrom except for the bitcount function.
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.
14 * The overlap tests uses the following offsets (which may be negative):
24 * For optimal collision detection performance combine these functions
25 * with some kind of pre-sorting to avoid comparing objects far from
28 * Performance of the various functions goes something like:
29 * (relative timings, smaller is better)
31 * bitmask_overlap() 1.0
32 * bitmask_overlap_pos() 1.3
33 * bitmask_overlap_area() 1.6
35 * For maximum performance on my machine I use gcc with
36 * -O2 -fomit-frame-pointer -funroll-loops
39 * If you can make these functions faster or have found any bugs please
40 * email Ulf Ekstrom, ulfek@ifm.liu.se
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.
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.
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.
58 #ifndef SUPERTUX_BITMASK_H
59 #define SUPERTUX_BITMASK_H
64 /* Define INLINE for different compilers. */
67 # define INLINE inline
70 # define INLINE __inline
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))
88 /* Creates a bitmask of width w and height h.
89 * The mask is automatically cleared when created.
91 bitmask *bitmask_create(int w, int h);
92 void bitmask_free(bitmask *m);
94 void bitmask_clear(bitmask *m);
95 void bitmask_fill(bitmask *m);
97 /* Returns nonzero if the bit at (x,y) is set.
98 * Coordinates start at (0,0)
100 static INLINE int bitmask_getbit(const bitmask *m,int x,int y)
102 return m->bits[x/BITW_LEN*m->h + y] & BITN(x & BITW_MASK);
106 /* Sets the bit at (x,y) */
107 static INLINE void bitmask_setbit(bitmask *m,int x,int y)
109 m->bits[x/BITW_LEN*m->h + y] |= BITN(x & BITW_MASK);
113 /* Clears the bit at (x,y) */
114 static INLINE void bitmask_clearbit(bitmask *m,int x,int y)
116 m->bits[x/BITW_LEN*m->h + y] &= ~BITN(x & BITW_MASK);
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);
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
127 int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffset, int *x, int *y);
129 /* Returns the number of overlapping 'pixels' */
130 int bitmask_overlap_area(const bitmask *a,const bitmask *b,int xoffset, int yoffset);
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.
136 void bitmask_draw(bitmask *a,bitmask *b,int xoffset, int yoffset);
138 /* Create a bitmask from a SDL_Surface */
139 bitmask* bitmask_create_SDL(SDL_Surface* surf);
141 #endif /*SUPERTUX_BITMASK_H*/