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)
51 bitmask* pbitmask = bitmask_create(surf->w, surf->h);
57 if(surf->format->BytesPerPixel != 4) //This function only works for true-color surfaces with an alpha channel
61 for(h = 0; h <= surf->h; ++h)
63 for(w = 0; w <= surf->w; ++w)
66 pixel = *((Uint32*)((Uint8 *)surf->pixels + h * surf->pitch + w * 4));
67 /* Get Alpha component */
68 temp=pixel&fmt->Amask; /* Isolate alpha component */
69 temp=temp>>fmt->Ashift;/* Shift it down to 8-bit */
70 temp=temp<<fmt->Aloss; /* Expand to a full 8-bit number */
72 if (fmt->Amask == 0 || alpha != 0)
73 bitmask_setbit(pbitmask,w,h);
78 void bitmask_free(bitmask *m)
84 int bitmask_overlap(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
89 int shift,rshift,i,astripes,bstripes;
91 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
98 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
99 a_end = a_entry + MIN(b->h,a->h - yoffset);
104 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
105 a_end = a_entry + MIN(b->h + yoffset,a->h);
106 b_entry = b->bits - yoffset;
108 shift = xoffset & BITW_MASK;
111 rshift = BITW_LEN - shift;
112 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
113 bstripes = (b->w - 1)/BITW_LEN + 1;
114 if (bstripes > astripes) /* zig-zag .. zig*/
116 for (i=0;i<astripes;i++)
118 for (ap = a_entry,bp = b_entry;ap < a_end;) /* Join these two to one loop */
119 if ((*ap++ >> shift) & *bp++)
123 for (ap = a_entry,bp = b_entry;ap < a_end;)
124 if ((*ap++ << rshift) & *bp++)
128 for (ap = a_entry,bp = b_entry;ap < a_end;)
129 if ((*ap++ >> shift) & *bp++)
135 for (i=0;i<bstripes;i++)
137 for (ap = a_entry,bp = b_entry;ap < a_end;)
138 if ((*ap++ >> shift) & *bp++)
142 for (ap = a_entry,bp = b_entry;ap < a_end;)
143 if ((*ap++ << rshift) & *bp++)
150 else /* xoffset is a multiple of the stripe width, and the above routines wont work */
152 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
153 for (i=0;i<astripes;i++)
155 for (ap = a_entry,bp = b_entry;ap < a_end;)
166 return bitmask_overlap(b,a,-xoffset,-yoffset);
169 /* Will hang if there are no bits set in w! */
170 static INLINE int firstsetbit(BITW w)
181 /* x and y are given in the coordinates of mask a, and are untouched if the is no overlap */
182 int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffset, int *x, int *y)
184 BITW *a_entry,*a_end;
187 int shift,rshift,i,astripes,bstripes;
189 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
196 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
197 a_end = a_entry + MIN(b->h,a->h - yoffset);
202 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
203 a_end = a_entry + MIN(b->h + yoffset,a->h);
204 b_entry = b->bits - yoffset;
206 shift = xoffset & BITW_MASK;
209 rshift = BITW_LEN - shift;
210 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
211 bstripes = (b->w - 1)/BITW_LEN + 1;
212 if (bstripes > astripes) /* zig-zag .. zig*/
214 for (i=0;i<astripes;i++)
216 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
217 if (*ap & (*bp << shift))
219 *y = (ap - a->bits) % a->h;
220 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
225 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
226 if (*ap & (*bp >> rshift))
228 *y = (ap - a->bits) % a->h;
229 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
234 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
235 if (*ap & (*bp << shift))
237 *y = (ap - a->bits) % a->h;
238 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
245 for (i=0;i<bstripes;i++)
247 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
248 if (*ap & (*bp << shift))
250 *y = (ap - a->bits) % a->h;
251 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
256 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
257 if (*ap & (*bp >> rshift))
259 *y = (ap - a->bits) % a->h;
260 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
268 else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
270 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
271 for (i=0;i<astripes;i++)
273 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
277 *y = (ap - a->bits) % a->h;
278 *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & *bp);
291 if (bitmask_overlap_pos(b,a,-xoffset,-yoffset,x,y))
304 /* (C) Donald W. Gillies, 1992. All rights reserved. You may reuse
305 this bitcount() function anywhere you please as long as you retain
306 this Copyright Notice. */
307 static INLINE int bitcount(unsigned long n)
309 register unsigned long tmp;
310 return (tmp = (n) - (((n) >> 1) & 033333333333) - (((n) >> 2) & 011111111111),\
311 tmp = ((tmp + (tmp >> 3)) & 030707070707), \
312 tmp = (tmp + (tmp >> 6)), \
313 tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077);
315 /* End of Donald W. Gillies bitcount code */
318 int bitmask_overlap_area(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
320 BITW *a_entry,*a_end;
323 int shift,rshift,i,astripes,bstripes;
326 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
333 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
334 a_end = a_entry + MIN(b->h,a->h - yoffset);
339 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
340 a_end = a_entry + MIN(b->h + yoffset,a->h);
341 b_entry = b->bits - yoffset;
343 shift = xoffset & BITW_MASK;
346 rshift = BITW_LEN - shift;
347 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
348 bstripes = (b->w - 1)/BITW_LEN + 1;
349 if (bstripes > astripes) /* zig-zag .. zig*/
351 for (i=0;i<astripes;i++)
353 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
354 count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
359 for (ap = a_entry,bp = b_entry;ap < a_end;)
360 count += bitcount((*ap++ >> shift) & *bp++);
365 for (i=0;i<bstripes;i++)
367 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
368 count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
376 else /* xoffset is a multiple of the stripe width, and the above routines wont work */
378 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
379 for (i=0;i<astripes;i++)
381 for (ap = a_entry,bp = b_entry;ap < a_end;)
382 count += bitcount(*ap++ & *bp++);
392 return bitmask_overlap_area(b,a,-xoffset,-yoffset);
396 /* Draws mask b onto mask a (bitwise OR) */
397 void bitmask_draw(bitmask *a,bitmask *b,int xoffset, int yoffset)
399 BITW *a_entry,*a_end;
403 int shift,rshift,i,astripes,bstripes;
405 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
412 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
413 a_end = a_entry + MIN(b->h,a->h - yoffset);
418 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
419 a_end = a_entry + MIN(b->h + yoffset,a->h);
420 b_entry = b->bits - yoffset;
422 shift = xoffset & BITW_MASK;
425 rshift = BITW_LEN - shift;
426 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
427 bstripes = (b->w - 1)/BITW_LEN + 1;
428 if (bstripes > astripes) /* zig-zag .. zig*/
430 for (i=0;i<astripes;i++)
432 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
433 *ap |= (*bp << shift);
436 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
437 *ap |= (*bp >> rshift);
440 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
441 *ap |= (*bp << shift);
446 for (i=0;i<bstripes;i++)
448 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
449 *ap |= (*bp << shift);
452 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
453 *ap |= (*bp >> rshift);
459 else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
461 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
462 for (i=0;i<astripes;i++)
464 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
477 /* 'Swapping' arguments to be able to almost reuse the code above */
486 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
487 a_end = a_entry + MIN(b->h,a->h - yoffset);
492 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
493 a_end = a_entry + MIN(b->h + yoffset,a->h);
494 b_entry = b->bits - yoffset;
496 shift = xoffset & BITW_MASK;
499 rshift = BITW_LEN - shift;
500 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
501 bstripes = (b->w - 1)/BITW_LEN + 1;
502 if (bstripes > astripes) /* zig-zag .. zig*/
504 for (i=0;i<astripes;i++)
506 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
507 *bp |= (*ap >> shift);
510 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
511 *bp |= (*ap <<rshift);
514 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
515 *bp |= (*ap >> shift);
520 for (i=0;i<bstripes;i++)
522 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
523 *bp |= (*ap >> shift);
526 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
527 *bp |= (*ap << rshift);
533 else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
535 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
536 for (i=0;i<astripes;i++)
538 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)