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.
30 #define MIN(a,b) ((a) < (b) ? (a) : (b))
32 bitmask *bitmask_create(int w, int h)
34 bitmask *temp = (bitmask*) malloc(sizeof(bitmask));
39 temp->bits = (long unsigned int*) calloc(h*((w - 1)/BITW_LEN + 1),sizeof(BITW));
49 bitmask *bitmask_create_SDL(SDL_Surface* surf)
55 bitmask *temp = (bitmask*) malloc(sizeof(bitmask));
60 temp->bits = (long unsigned int*) calloc(surf->h*((surf->w - 1)/BITW_LEN + 1),sizeof(BITW));
69 bpp = surf->format->BytesPerPixel;
70 for(h = 0; h <= surf->h; ++h)
72 for(w = 0; w <= surf->h; ++w)
75 p = (Uint8 *)surf->pixels + h*surf->pitch + w*bpp;
77 bitmask_setbit(temp,w,h);
83 void bitmask_free(bitmask *m)
89 int bitmask_overlap(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
94 int shift,rshift,i,astripes,bstripes;
96 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
103 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
104 a_end = a_entry + MIN(b->h,a->h - yoffset);
109 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
110 a_end = a_entry + MIN(b->h + yoffset,a->h);
111 b_entry = b->bits - yoffset;
113 shift = xoffset & BITW_MASK;
116 rshift = BITW_LEN - shift;
117 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
118 bstripes = (b->w - 1)/BITW_LEN + 1;
119 if (bstripes > astripes) /* zig-zag .. zig*/
121 for (i=0;i<astripes;i++)
123 for (ap = a_entry,bp = b_entry;ap < a_end;) /* Join these two to one loop */
124 if ((*ap++ >> shift) & *bp++)
128 for (ap = a_entry,bp = b_entry;ap < a_end;)
129 if ((*ap++ << rshift) & *bp++)
133 for (ap = a_entry,bp = b_entry;ap < a_end;)
134 if ((*ap++ >> shift) & *bp++)
140 for (i=0;i<bstripes;i++)
142 for (ap = a_entry,bp = b_entry;ap < a_end;)
143 if ((*ap++ >> shift) & *bp++)
147 for (ap = a_entry,bp = b_entry;ap < a_end;)
148 if ((*ap++ << rshift) & *bp++)
155 else /* xoffset is a multiple of the stripe width, and the above routines wont work */
157 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
158 for (i=0;i<astripes;i++)
160 for (ap = a_entry,bp = b_entry;ap < a_end;)
171 return bitmask_overlap(b,a,-xoffset,-yoffset);
174 /* Will hang if there are no bits set in w! */
175 static INLINE int firstsetbit(BITW w)
186 /* x and y are given in the coordinates of mask a, and are untouched if the is no overlap */
187 int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffset, int *x, int *y)
189 BITW *a_entry,*a_end;
192 int shift,rshift,i,astripes,bstripes;
194 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
201 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
202 a_end = a_entry + MIN(b->h,a->h - yoffset);
207 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
208 a_end = a_entry + MIN(b->h + yoffset,a->h);
209 b_entry = b->bits - yoffset;
211 shift = xoffset & BITW_MASK;
214 rshift = BITW_LEN - shift;
215 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
216 bstripes = (b->w - 1)/BITW_LEN + 1;
217 if (bstripes > astripes) /* zig-zag .. zig*/
219 for (i=0;i<astripes;i++)
221 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
222 if (*ap & (*bp << shift))
224 *y = (ap - a->bits) % a->h;
225 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
230 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
231 if (*ap & (*bp >> rshift))
233 *y = (ap - a->bits) % a->h;
234 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
239 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
240 if (*ap & (*bp << shift))
242 *y = (ap - a->bits) % a->h;
243 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
250 for (i=0;i<bstripes;i++)
252 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
253 if (*ap & (*bp << shift))
255 *y = (ap - a->bits) % a->h;
256 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
261 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
262 if (*ap & (*bp >> rshift))
264 *y = (ap - a->bits) % a->h;
265 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
273 else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
275 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
276 for (i=0;i<astripes;i++)
278 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
282 *y = (ap - a->bits) % a->h;
283 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & *bp);
296 if (bitmask_overlap_pos(b,a,-xoffset,-yoffset,x,y))
309 /* (C) Donald W. Gillies, 1992. All rights reserved. You may reuse
310 this bitcount() function anywhere you please as long as you retain
311 this Copyright Notice. */
312 static INLINE int bitcount(unsigned long n)
314 register unsigned long tmp;
315 return (tmp = (n) - (((n) >> 1) & 033333333333) - (((n) >> 2) & 011111111111),\
316 tmp = ((tmp + (tmp >> 3)) & 030707070707), \
317 tmp = (tmp + (tmp >> 6)), \
318 tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077);
320 /* End of Donald W. Gillies bitcount code */
323 int bitmask_overlap_area(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
325 BITW *a_entry,*a_end;
328 int shift,rshift,i,astripes,bstripes;
331 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
338 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
339 a_end = a_entry + MIN(b->h,a->h - yoffset);
344 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
345 a_end = a_entry + MIN(b->h + yoffset,a->h);
346 b_entry = b->bits - yoffset;
348 shift = xoffset & BITW_MASK;
351 rshift = BITW_LEN - shift;
352 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
353 bstripes = (b->w - 1)/BITW_LEN + 1;
354 if (bstripes > astripes) /* zig-zag .. zig*/
356 for (i=0;i<astripes;i++)
358 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
359 count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
364 for (ap = a_entry,bp = b_entry;ap < a_end;)
365 count += bitcount((*ap++ >> shift) & *bp++);
370 for (i=0;i<bstripes;i++)
372 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
373 count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
381 else /* xoffset is a multiple of the stripe width, and the above routines wont work */
383 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
384 for (i=0;i<astripes;i++)
386 for (ap = a_entry,bp = b_entry;ap < a_end;)
387 count += bitcount(*ap++ & *bp++);
397 return bitmask_overlap_area(b,a,-xoffset,-yoffset);
401 /* Draws mask b onto mask a (bitwise OR) */
402 void bitmask_draw(bitmask *a,bitmask *b,int xoffset, int yoffset)
404 BITW *a_entry,*a_end;
408 int shift,rshift,i,astripes,bstripes;
410 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
417 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
418 a_end = a_entry + MIN(b->h,a->h - yoffset);
423 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
424 a_end = a_entry + MIN(b->h + yoffset,a->h);
425 b_entry = b->bits - yoffset;
427 shift = xoffset & BITW_MASK;
430 rshift = BITW_LEN - shift;
431 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
432 bstripes = (b->w - 1)/BITW_LEN + 1;
433 if (bstripes > astripes) /* zig-zag .. zig*/
435 for (i=0;i<astripes;i++)
437 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
438 *ap |= (*bp << shift);
441 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
442 *ap |= (*bp >> rshift);
445 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
446 *ap |= (*bp << shift);
451 for (i=0;i<bstripes;i++)
453 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
454 *ap |= (*bp << shift);
457 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
458 *ap |= (*bp >> rshift);
464 else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
466 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
467 for (i=0;i<astripes;i++)
469 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
482 /* 'Swapping' arguments to be able to almost reuse the code above */
491 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
492 a_end = a_entry + MIN(b->h,a->h - yoffset);
497 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
498 a_end = a_entry + MIN(b->h + yoffset,a->h);
499 b_entry = b->bits - yoffset;
501 shift = xoffset & BITW_MASK;
504 rshift = BITW_LEN - shift;
505 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
506 bstripes = (b->w - 1)/BITW_LEN + 1;
507 if (bstripes > astripes) /* zig-zag .. zig*/
509 for (i=0;i<astripes;i++)
511 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
512 *bp |= (*ap >> shift);
515 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
516 *bp |= (*ap <<rshift);
519 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
520 *bp |= (*ap >> shift);
525 for (i=0;i<bstripes;i++)
527 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
528 *bp |= (*ap >> shift);
531 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
532 *bp |= (*ap << rshift);
538 else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
540 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
541 for (i=0;i<astripes;i++)
543 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)