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.
31 #define MIN(a,b) ((a) < (b) ? (a) : (b))
33 bitmask *bitmask_create(int w, int h)
35 bitmask *temp = (bitmask*) malloc(sizeof(bitmask));
40 temp->bits = (long unsigned int*) calloc(h*((w - 1)/BITW_LEN + 1),sizeof(BITW));
50 /* (C) Tobias Glaesser <tobi.web@gmx.de>, 2004.
51 This function isn't available in the original bitmask library. */
52 bitmask *bitmask_create_SDL(SDL_Surface* surf)
54 bitmask* pbitmask = bitmask_create(surf->w, surf->h);
60 if(surf->format->BytesPerPixel != 4) //This function only works for true-color surfaces with an alpha channel
64 for(h = 0; h <= surf->h; ++h)
66 for(w = 0; w <= surf->w; ++w)
69 pixel = *((Uint32*)((Uint8 *)surf->pixels + h * surf->pitch + w * 4));
70 /* Get Alpha component */
71 temp=pixel&fmt->Amask; /* Isolate alpha component */
72 temp=temp>>fmt->Ashift;/* Shift it down to 8-bit */
73 temp=temp<<fmt->Aloss; /* Expand to a full 8-bit number */
75 if (fmt->Amask == 0 || alpha != 0)
76 bitmask_setbit(pbitmask,w,h);
81 void bitmask_free(bitmask *m)
87 void bitmask_clear(bitmask *m)
89 memset(m->bits,0,m->h*((m->w - 1)/BITW_LEN + 1)*sizeof(BITW));
92 void bitmask_fill(bitmask *m)
94 memset(m->bits,255,m->h*((m->w - 1)/BITW_LEN + 1)*sizeof(BITW));
97 int bitmask_overlap(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
102 int shift,rshift,i,astripes,bstripes;
104 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
111 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
112 a_end = a_entry + MIN(b->h,a->h - yoffset);
117 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
118 a_end = a_entry + MIN(b->h + yoffset,a->h);
119 b_entry = b->bits - yoffset;
121 shift = xoffset & BITW_MASK;
124 rshift = BITW_LEN - shift;
125 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
126 bstripes = (b->w - 1)/BITW_LEN + 1;
127 if (bstripes > astripes) /* zig-zag .. zig*/
129 for (i=0;i<astripes;i++)
131 for (ap = a_entry,bp = b_entry;ap < a_end;) /* Join these two to one loop */
132 if ((*ap++ >> shift) & *bp++)
136 for (ap = a_entry,bp = b_entry;ap < a_end;)
137 if ((*ap++ << rshift) & *bp++)
141 for (ap = a_entry,bp = b_entry;ap < a_end;)
142 if ((*ap++ >> shift) & *bp++)
148 for (i=0;i<bstripes;i++)
150 for (ap = a_entry,bp = b_entry;ap < a_end;)
151 if ((*ap++ >> shift) & *bp++)
155 for (ap = a_entry,bp = b_entry;ap < a_end;)
156 if ((*ap++ << rshift) & *bp++)
163 else /* xoffset is a multiple of the stripe width, and the above routines wont work */
165 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
166 for (i=0;i<astripes;i++)
168 for (ap = a_entry,bp = b_entry;ap < a_end;)
179 return bitmask_overlap(b,a,-xoffset,-yoffset);
182 /* Will hang if there are no bits set in w! */
183 static INLINE int firstsetbit(BITW w)
194 /* x and y are given in the coordinates of mask a, and are untouched if the is no overlap */
195 int bitmask_overlap_pos(const bitmask *a,const bitmask *b,int xoffset, int yoffset, int *x, int *y)
197 BITW *a_entry,*a_end;
200 int shift,rshift,i,astripes,bstripes,xbase;
202 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
207 xbase = xoffset/BITW_LEN; /* first stripe from mask a */
210 a_entry = a->bits + a->h*xbase + yoffset;
211 a_end = a_entry + MIN(b->h,a->h - yoffset);
216 a_entry = a->bits + a->h*xbase;
217 a_end = a_entry + MIN(b->h + yoffset,a->h);
218 b_entry = b->bits - yoffset;
219 yoffset = 0; /* relied on below */
221 shift = xoffset & BITW_MASK;
224 rshift = BITW_LEN - shift;
225 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
226 bstripes = (b->w - 1)/BITW_LEN + 1;
227 if (bstripes > astripes) /* zig-zag .. zig*/
229 for (i=0;i<astripes;i++)
231 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
232 if (*ap & (*bp << shift))
234 *y = ap - a_entry + yoffset;
235 *x = (xbase + i)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
240 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
241 if (*ap & (*bp >> rshift))
243 *y = ap - a_entry + yoffset;
244 *x = (xbase + i + 1)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
249 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
250 if (*ap & (*bp << shift))
252 *y = ap - a_entry + yoffset;
253 *x = (xbase + astripes)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
260 for (i=0;i<bstripes;i++)
262 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
263 if (*ap & (*bp << shift))
265 *y = ap - a_entry + yoffset;
266 *x = (xbase + i)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
271 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
272 if (*ap & (*bp >> rshift))
274 *y = ap - a_entry + yoffset;
275 *x = (xbase + i + 1)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
283 else /* xoffset is a multiple of the stripe width, and the above routines
284 won't work. This way is also slightly faster. */
286 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
287 for (i=0;i<astripes;i++)
289 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
293 *y = ap - a_entry + yoffset;
294 *x = (xbase + i)*BITW_LEN + firstsetbit(*ap & *bp);
307 if (bitmask_overlap_pos(b,a,-xoffset,-yoffset,x,y))
318 static INLINE int bitcount(unsigned long n)
322 /* (C) Donald W. Gillies, 1992. All rights reserved. You may reuse
323 this bitcount() function anywhere you please as long as you retain
324 this Copyright Notice. */
325 register unsigned long tmp;
326 return (tmp = (n) - (((n) >> 1) & 033333333333) -
327 (((n) >> 2) & 011111111111),
328 tmp = ((tmp + (tmp >> 3)) & 030707070707),
329 tmp = (tmp + (tmp >> 6)),
330 tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077);
331 /* End of Donald W. Gillies bitcount code */
335 /* Handle non-32 bit case the slow way */
348 int bitmask_overlap_area(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
350 BITW *a_entry,*a_end;
353 int shift,rshift,i,astripes,bstripes;
356 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
363 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
364 a_end = a_entry + MIN(b->h,a->h - yoffset);
369 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
370 a_end = a_entry + MIN(b->h + yoffset,a->h);
371 b_entry = b->bits - yoffset;
373 shift = xoffset & BITW_MASK;
376 rshift = BITW_LEN - shift;
377 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
378 bstripes = (b->w - 1)/BITW_LEN + 1;
379 if (bstripes > astripes) /* zig-zag .. zig*/
381 for (i=0;i<astripes;i++)
383 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
384 count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
389 for (ap = a_entry,bp = b_entry;ap < a_end;)
390 count += bitcount((*ap++ >> shift) & *bp++);
395 for (i=0;i<bstripes;i++)
397 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
398 count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
406 else /* xoffset is a multiple of the stripe width, and the above routines wont work */
408 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
409 for (i=0;i<astripes;i++)
411 for (ap = a_entry,bp = b_entry;ap < a_end;)
412 count += bitcount(*ap++ & *bp++);
422 return bitmask_overlap_area(b,a,-xoffset,-yoffset);
426 /* Draws mask b onto mask a (bitwise OR) */
427 void bitmask_draw(bitmask *a,bitmask *b,int xoffset, int yoffset)
429 BITW *a_entry,*a_end;
433 int shift,rshift,i,astripes,bstripes;
435 if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
442 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
443 a_end = a_entry + MIN(b->h,a->h - yoffset);
448 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
449 a_end = a_entry + MIN(b->h + yoffset,a->h);
450 b_entry = b->bits - yoffset;
452 shift = xoffset & BITW_MASK;
455 rshift = BITW_LEN - shift;
456 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
457 bstripes = (b->w - 1)/BITW_LEN + 1;
458 if (bstripes > astripes) /* zig-zag .. zig*/
460 for (i=0;i<astripes;i++)
462 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
463 *ap |= (*bp << shift);
466 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
467 *ap |= (*bp >> rshift);
470 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
471 *ap |= (*bp << shift);
476 for (i=0;i<bstripes;i++)
478 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
479 *ap |= (*bp << shift);
482 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
483 *ap |= (*bp >> rshift);
489 else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
491 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
492 for (i=0;i<astripes;i++)
494 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
507 /* 'Swapping' arguments to be able to almost reuse the code above,
508 should be taken care of by the compiler efficiently. */
517 a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
518 a_end = a_entry + MIN(b->h,a->h - yoffset);
523 a_entry = a->bits + a->h*(xoffset/BITW_LEN);
524 a_end = a_entry + MIN(b->h + yoffset,a->h);
525 b_entry = b->bits - yoffset;
527 shift = xoffset & BITW_MASK;
530 rshift = BITW_LEN - shift;
531 astripes = (a->w - 1)/BITW_LEN - xoffset/BITW_LEN;
532 bstripes = (b->w - 1)/BITW_LEN + 1;
533 if (bstripes > astripes) /* zig-zag .. zig*/
535 for (i=0;i<astripes;i++)
537 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
538 *bp |= (*ap >> shift);
541 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
542 *bp |= (*ap <<rshift);
545 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
546 *bp |= (*ap >> shift);
551 for (i=0;i<bstripes;i++)
553 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
554 *bp |= (*ap >> shift);
557 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
558 *bp |= (*ap << rshift);
564 else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
566 astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
567 for (i=0;i<astripes;i++)
569 for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)