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.
33 #define MIN(a,b) ((a) < (b) ? (a) : (b))
35 bitmask *bitmask_create(int w, int h)
37 bitmask *temp = (bitmask*) malloc(sizeof(bitmask));
42 temp->bits = (long unsigned int*) calloc(h*((w - 1)/BITW_LEN + 1),sizeof(BITW));
52 /* (C) Tobias Glaesser <tobi.web@gmx.de>, 2004.
53 This function isn't available in the original bitmask library. */
54 bitmask *bitmask_create_SDL(SDL_Surface* surf)
56 bitmask* pbitmask = bitmask_create(surf->w, surf->h);
62 if(surf->format->BytesPerPixel != 4) //This function only works for true-color surfaces with an alpha channel
66 for(h = 0; h <= surf->h; ++h)
68 for(w = 0; w <= surf->w; ++w)
71 pixel = *((Uint32*)((Uint8 *)surf->pixels + h * surf->pitch + w * 4));
72 /* Get Alpha component */
73 temp=pixel&fmt->Amask; /* Isolate alpha component */
74 temp=temp>>fmt->Ashift;/* Shift it down to 8-bit */
75 temp=temp<<fmt->Aloss; /* Expand to a full 8-bit number */
77 if (fmt->Amask == 0 || alpha != 0)
78 bitmask_setbit(pbitmask,w,h);
83 void bitmask_free(bitmask *m)
89 void bitmask_clear(bitmask *m)
91 memset(m->bits,0,m->h*((m->w - 1)/BITW_LEN + 1)*sizeof(BITW));
94 void bitmask_fill(bitmask *m)
96 memset(m->bits,255,m->h*((m->w - 1)/BITW_LEN + 1)*sizeof(BITW));
99 int bitmask_overlap(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
101 BITW *a_entry,*a_end;
104 int shift,rshift,i,astripes,bstripes;
106 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
113 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
114 a_end = a_entry + MIN(b->h,a->h - yoffset);
119 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
120 a_end = a_entry + MIN(b->h + yoffset,a->h);
121 b_entry = b->bits - yoffset;
123 shift = xoffset & BITW_MASK;
126 rshift = BITW_LEN - shift;
127 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
128 bstripes = (b->w - 1)/BITW_LEN + 1;
129 if (bstripes > astripes) /* zig-zag .. zig*/
131 for (i=0;i<astripes;i++)
133 for (ap = a_entry,bp = b_entry;ap < a_end;) /* Join these two to one loop */
134 if ((*ap++ >> shift) & *bp++)
138 for (ap = a_entry,bp = b_entry;ap < a_end;)
139 if ((*ap++ << rshift) & *bp++)
143 for (ap = a_entry,bp = b_entry;ap < a_end;)
144 if ((*ap++ >> shift) & *bp++)
150 for (i=0;i<bstripes;i++)
152 for (ap = a_entry,bp = b_entry;ap < a_end;)
153 if ((*ap++ >> shift) & *bp++)
157 for (ap = a_entry,bp = b_entry;ap < a_end;)
158 if ((*ap++ << rshift) & *bp++)
165 else /* xoffset is a multiple of the stripe width, and the above routines wont work */
167 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
168 for (i=0;i<astripes;i++)
170 for (ap = a_entry,bp = b_entry;ap < a_end;)
181 return bitmask_overlap(b,a,-xoffset,-yoffset);
184 /* Will hang if there are no bits set in w! */
185 static INLINE int firstsetbit(BITW w)
196 /* x and y are given in the coordinates of mask a, and are untouched if the is no overlap */
197 int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffset, int *x, int *y)
199 BITW *a_entry,*a_end;
202 int shift,rshift,i,astripes,bstripes,xbase;
204 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
209 xbase = xoffset/BITW_LEN; /* first stripe from mask a */
212 a_entry = a->bits + a->h*xbase + yoffset;
213 a_end = a_entry + MIN(b->h,a->h - yoffset);
218 a_entry = a->bits + a->h*xbase;
219 a_end = a_entry + MIN(b->h + yoffset,a->h);
220 b_entry = b->bits - yoffset;
221 yoffset = 0; /* relied on below */
223 shift = xoffset & BITW_MASK;
226 rshift = BITW_LEN - shift;
227 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
228 bstripes = (b->w - 1)/BITW_LEN + 1;
229 if (bstripes > astripes) /* zig-zag .. zig*/
231 for (i=0;i<astripes;i++)
233 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
234 if (*ap & (*bp << shift))
236 *y = ap - a_entry + yoffset;
237 *x = (xbase + i)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
242 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
243 if (*ap & (*bp >> rshift))
245 *y = ap - a_entry + yoffset;
246 *x = (xbase + i + 1)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
251 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
252 if (*ap & (*bp << shift))
254 *y = ap - a_entry + yoffset;
255 *x = (xbase + astripes)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
262 for (i=0;i<bstripes;i++)
264 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
265 if (*ap & (*bp << shift))
267 *y = ap - a_entry + yoffset;
268 *x = (xbase + i)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
273 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
274 if (*ap & (*bp >> rshift))
276 *y = ap - a_entry + yoffset;
277 *x = (xbase + i + 1)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
285 else /* xoffset is a multiple of the stripe width, and the above routines
286 won't work. This way is also slightly faster. */
288 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
289 for (i=0;i<astripes;i++)
291 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
295 *y = ap - a_entry + yoffset;
296 *x = (xbase + i)*BITW_LEN + firstsetbit(*ap & *bp);
309 if (bitmask_overlap_pos(b,a,-xoffset,-yoffset,x,y))
320 static INLINE int bitcount(unsigned long n)
324 /* (C) Donald W. Gillies, 1992. All rights reserved. You may reuse
325 this bitcount() function anywhere you please as long as you retain
326 this Copyright Notice. */
327 register unsigned long tmp;
328 return (tmp = (n) - (((n) >> 1) & 033333333333) -
329 (((n) >> 2) & 011111111111),
330 tmp = ((tmp + (tmp >> 3)) & 030707070707),
331 tmp = (tmp + (tmp >> 6)),
332 tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077);
333 /* End of Donald W. Gillies bitcount code */
337 /* Handle non-32 bit case the slow way */
350 int bitmask_overlap_area(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
352 BITW *a_entry,*a_end;
355 int shift,rshift,i,astripes,bstripes;
358 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
365 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
366 a_end = a_entry + MIN(b->h,a->h - yoffset);
371 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
372 a_end = a_entry + MIN(b->h + yoffset,a->h);
373 b_entry = b->bits - yoffset;
375 shift = xoffset & BITW_MASK;
378 rshift = BITW_LEN - shift;
379 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
380 bstripes = (b->w - 1)/BITW_LEN + 1;
381 if (bstripes > astripes) /* zig-zag .. zig*/
383 for (i=0;i<astripes;i++)
385 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
386 count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
391 for (ap = a_entry,bp = b_entry;ap < a_end;)
392 count += bitcount((*ap++ >> shift) & *bp++);
397 for (i=0;i<bstripes;i++)
399 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
400 count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
408 else /* xoffset is a multiple of the stripe width, and the above routines wont work */
410 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
411 for (i=0;i<astripes;i++)
413 for (ap = a_entry,bp = b_entry;ap < a_end;)
414 count += bitcount(*ap++ & *bp++);
424 return bitmask_overlap_area(b,a,-xoffset,-yoffset);
428 /* Draws mask b onto mask a (bitwise OR) */
429 void bitmask_draw(bitmask *a,bitmask *b,int xoffset, int yoffset)
431 BITW *a_entry,*a_end;
435 int shift,rshift,i,astripes,bstripes;
437 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
444 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
445 a_end = a_entry + MIN(b->h,a->h - yoffset);
450 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
451 a_end = a_entry + MIN(b->h + yoffset,a->h);
452 b_entry = b->bits - yoffset;
454 shift = xoffset & BITW_MASK;
457 rshift = BITW_LEN - shift;
458 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
459 bstripes = (b->w - 1)/BITW_LEN + 1;
460 if (bstripes > astripes) /* zig-zag .. zig*/
462 for (i=0;i<astripes;i++)
464 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
465 *ap |= (*bp << shift);
468 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
469 *ap |= (*bp >> rshift);
472 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
473 *ap |= (*bp << shift);
478 for (i=0;i<bstripes;i++)
480 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
481 *ap |= (*bp << shift);
484 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
485 *ap |= (*bp >> rshift);
491 else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
493 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
494 for (i=0;i<astripes;i++)
496 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
509 /* 'Swapping' arguments to be able to almost reuse the code above,
510 should be taken care of by the compiler efficiently. */
519 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
520 a_end = a_entry + MIN(b->h,a->h - yoffset);
525 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
526 a_end = a_entry + MIN(b->h + yoffset,a->h);
527 b_entry = b->bits - yoffset;
529 shift = xoffset & BITW_MASK;
532 rshift = BITW_LEN - shift;
533 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
534 bstripes = (b->w - 1)/BITW_LEN + 1;
535 if (bstripes > astripes) /* zig-zag .. zig*/
537 for (i=0;i<astripes;i++)
539 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
540 *bp |= (*ap >> shift);
543 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
544 *bp |= (*ap <<rshift);
547 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
548 *bp |= (*ap >> shift);
553 for (i=0;i<bstripes;i++)
555 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
556 *bp |= (*ap >> shift);
559 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
560 *bp |= (*ap << rshift);
566 else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
568 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
569 for (i=0;i<astripes;i++)
571 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)