4 * Simple and efficient bitmask collision detection routines
5 * Copyright (C) 2002 Ulf Ekstrom except for the bitcount function.
7 * > See the header file for more info. <
9 * Please email bugs and comments to Ulf Ekstrom, ulfek@ifm.liu.se
11 * This program is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU General Public License
13 * as published by the Free Software Foundation; either version 2
14 * of the License, or (at your option) any later version.
16 * This program is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 * GNU General Public License for more details.
21 * You should have received a copy of the GNU General Public License
22 * along with this program; if not, write to the Free Software
23 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
29 #define MIN(a,b) ((a) < (b) ? (a) : (b))
31 bitmask *bitmask_create(int w, int h)
33 bitmask *temp = (bitmask*) malloc(sizeof(bitmask));
38 temp->bits = (long unsigned int*) calloc(h*((w - 1)/BITW_LEN + 1),sizeof(BITW));
48 bitmask *bitmask_create_SDL(SDL_Surface* surf)
54 bitmask *temp = (bitmask*) malloc(sizeof(bitmask));
59 temp->bits = (long unsigned int*) calloc(surf->h*((surf->w - 1)/BITW_LEN + 1),sizeof(BITW));
68 bpp = surf->format->BytesPerPixel;
69 for(h = 0; h <= surf->h; ++h)
71 for(w = 0; w <= surf->h; ++w)
74 p = (Uint8 *)surf->pixels + h*surf->pitch + w*bpp;
76 bitmask_setbit(temp,w,h);
82 void bitmask_free(bitmask *m)
88 int bitmask_overlap(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
93 int shift,rshift,i,astripes,bstripes;
95 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
102 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
103 a_end = a_entry + MIN(b->h,a->h - yoffset);
108 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
109 a_end = a_entry + MIN(b->h + yoffset,a->h);
110 b_entry = b->bits - yoffset;
112 shift = xoffset & BITW_MASK;
115 rshift = BITW_LEN - shift;
116 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
117 bstripes = (b->w - 1)/BITW_LEN + 1;
118 if (bstripes > astripes) /* zig-zag .. zig*/
120 for (i=0;i<astripes;i++)
122 for (ap = a_entry,bp = b_entry;ap < a_end;) /* Join these two to one loop */
123 if ((*ap++ >> shift) & *bp++)
127 for (ap = a_entry,bp = b_entry;ap < a_end;)
128 if ((*ap++ << rshift) & *bp++)
132 for (ap = a_entry,bp = b_entry;ap < a_end;)
133 if ((*ap++ >> shift) & *bp++)
139 for (i=0;i<bstripes;i++)
141 for (ap = a_entry,bp = b_entry;ap < a_end;)
142 if ((*ap++ >> shift) & *bp++)
146 for (ap = a_entry,bp = b_entry;ap < a_end;)
147 if ((*ap++ << rshift) & *bp++)
154 else /* xoffset is a multiple of the stripe width, and the above routines wont work */
156 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
157 for (i=0;i<astripes;i++)
159 for (ap = a_entry,bp = b_entry;ap < a_end;)
170 return bitmask_overlap(b,a,-xoffset,-yoffset);
173 /* Will hang if there are no bits set in w! */
174 static INLINE int firstsetbit(BITW w)
185 /* x and y are given in the coordinates of mask a, and are untouched if the is no overlap */
186 int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffset, int *x, int *y)
188 BITW *a_entry,*a_end;
191 int shift,rshift,i,astripes,bstripes;
193 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
200 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
201 a_end = a_entry + MIN(b->h,a->h - yoffset);
206 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
207 a_end = a_entry + MIN(b->h + yoffset,a->h);
208 b_entry = b->bits - yoffset;
210 shift = xoffset & BITW_MASK;
213 rshift = BITW_LEN - shift;
214 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
215 bstripes = (b->w - 1)/BITW_LEN + 1;
216 if (bstripes > astripes) /* zig-zag .. zig*/
218 for (i=0;i<astripes;i++)
220 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
221 if (*ap & (*bp << shift))
223 *y = (ap - a->bits) % a->h;
224 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
229 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
230 if (*ap & (*bp >> rshift))
232 *y = (ap - a->bits) % a->h;
233 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
238 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
239 if (*ap & (*bp << shift))
241 *y = (ap - a->bits) % a->h;
242 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
249 for (i=0;i<bstripes;i++)
251 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
252 if (*ap & (*bp << shift))
254 *y = (ap - a->bits) % a->h;
255 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
260 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
261 if (*ap & (*bp >> rshift))
263 *y = (ap - a->bits) % a->h;
264 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
272 else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
274 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
275 for (i=0;i<astripes;i++)
277 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
281 *y = (ap - a->bits) % a->h;
282 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & *bp);
295 if (bitmask_overlap_pos(b,a,-xoffset,-yoffset,x,y))
308 /* (C) Donald W. Gillies, 1992. All rights reserved. You may reuse
309 this bitcount() function anywhere you please as long as you retain
310 this Copyright Notice. */
311 static INLINE int bitcount(unsigned long n)
313 register unsigned long tmp;
314 return (tmp = (n) - (((n) >> 1) & 033333333333) - (((n) >> 2) & 011111111111),\
315 tmp = ((tmp + (tmp >> 3)) & 030707070707), \
316 tmp = (tmp + (tmp >> 6)), \
317 tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077);
319 /* End of Donald W. Gillies bitcount code */
322 int bitmask_overlap_area(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
324 BITW *a_entry,*a_end;
327 int shift,rshift,i,astripes,bstripes;
330 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
337 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
338 a_end = a_entry + MIN(b->h,a->h - yoffset);
343 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
344 a_end = a_entry + MIN(b->h + yoffset,a->h);
345 b_entry = b->bits - yoffset;
347 shift = xoffset & BITW_MASK;
350 rshift = BITW_LEN - shift;
351 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
352 bstripes = (b->w - 1)/BITW_LEN + 1;
353 if (bstripes > astripes) /* zig-zag .. zig*/
355 for (i=0;i<astripes;i++)
357 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
358 count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
363 for (ap = a_entry,bp = b_entry;ap < a_end;)
364 count += bitcount((*ap++ >> shift) & *bp++);
369 for (i=0;i<bstripes;i++)
371 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
372 count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
380 else /* xoffset is a multiple of the stripe width, and the above routines wont work */
382 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
383 for (i=0;i<astripes;i++)
385 for (ap = a_entry,bp = b_entry;ap < a_end;)
386 count += bitcount(*ap++ & *bp++);
396 return bitmask_overlap_area(b,a,-xoffset,-yoffset);
400 /* Draws mask b onto mask a (bitwise OR) */
401 void bitmask_draw(bitmask *a,bitmask *b,int xoffset, int yoffset)
403 BITW *a_entry,*a_end;
407 int shift,rshift,i,astripes,bstripes;
409 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
416 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
417 a_end = a_entry + MIN(b->h,a->h - yoffset);
422 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
423 a_end = a_entry + MIN(b->h + yoffset,a->h);
424 b_entry = b->bits - yoffset;
426 shift = xoffset & BITW_MASK;
429 rshift = BITW_LEN - shift;
430 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
431 bstripes = (b->w - 1)/BITW_LEN + 1;
432 if (bstripes > astripes) /* zig-zag .. zig*/
434 for (i=0;i<astripes;i++)
436 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
437 *ap |= (*bp << shift);
440 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
441 *ap |= (*bp >> rshift);
444 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
445 *ap |= (*bp << shift);
450 for (i=0;i<bstripes;i++)
452 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
453 *ap |= (*bp << shift);
456 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
457 *ap |= (*bp >> rshift);
463 else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
465 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
466 for (i=0;i<astripes;i++)
468 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
481 /* 'Swapping' arguments to be able to almost reuse the code above */
490 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
491 a_end = a_entry + MIN(b->h,a->h - yoffset);
496 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
497 a_end = a_entry + MIN(b->h + yoffset,a->h);
498 b_entry = b->bits - yoffset;
500 shift = xoffset & BITW_MASK;
503 rshift = BITW_LEN - shift;
504 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
505 bstripes = (b->w - 1)/BITW_LEN + 1;
506 if (bstripes > astripes) /* zig-zag .. zig*/
508 for (i=0;i<astripes;i++)
510 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
511 *bp |= (*ap >> shift);
514 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
515 *bp |= (*ap <<rshift);
518 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
519 *bp |= (*ap >> shift);
524 for (i=0;i<bstripes;i++)
526 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
527 *bp |= (*ap >> shift);
530 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
531 *bp |= (*ap << rshift);
537 else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
539 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
540 for (i=0;i<astripes;i++)
542 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)