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.
13 * (Note that the current bitcount function is 32 bit only!)
15 * The overlap tests uses the following offsets (which may be negative):
25 * For optimal collision detection performance combine these functions
26 * with some kind of pre-sorting to avoid comparing objects far from
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.
34 * Performance of the various functions goes something like:
35 * (relative timings, smaller is better)
37 * bitmask_overlap() 1.0
38 * bitmask_overlap_pos() 1.3
39 * bitmask_overlap_area() 1.6
41 * For maximum performance on my machine I use gcc with
42 * -O2 -fomit-frame-pointer -funroll-loops
45 * If you can make these functions faster or have found any bugs please
46 * email Ulf Ekstrom, ulfek@ifm.liu.se
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.
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.
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.
64 #ifndef SUPERTUX_BITMASK_H
65 #define SUPERTUX_BITMASK_H
69 /* Define INLINE for different compilers. */
72 # define INLINE __inline__
75 # define INLINE __inline
82 #define BITW unsigned long int
85 #define BITN(n) ((BITW)1 << (n))
93 /* Creates a bitmask of width w and height h.
94 * The mask is automatically cleared when created.
96 bitmask *bitmask_create(int w, int h);
97 void bitmask_free(bitmask *m);
99 /* Returns nonzero if the bit at (x,y) is set.
100 * Coordinates start at (0,0)
102 static INLINE int bitmask_getbit(const bitmask *m,int x,int y)
104 return m->bits[x/BITW_LEN*m->h + y] & BITN(x & BITW_MASK);
108 /* Sets the bit at (x,y) */
109 static INLINE void bitmask_setbit(bitmask *m,int x,int y)
111 m->bits[x/BITW_LEN*m->h + y] |= BITN(x & BITW_MASK);
115 /* Clears the bit at (x,y) */
116 static INLINE void bitmask_clearbit(bitmask *m,int x,int y)
118 m->bits[x/BITW_LEN*m->h + y] &= ~BITN(x & BITW_MASK);
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);
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
129 int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffset, int *x, int *y);
131 /* Returns the number of overlapping 'pixels' */
132 int bitmask_overlap_area(const bitmask *a,const bitmask *b,int xoffset, int yoffset);
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.
138 void bitmask_draw(bitmask *a,bitmask *b,int xoffset, int yoffset);
140 /* Create a bitmask from a SDL_Surface */
141 bitmask* bitmask_create_SDL(SDL_Surface* surf);
143 #endif /*SUPERTUX_BITMASK_H*/