src/bitmask.cpp

   1 /*
   2  *                          bitmask.c 1.0
   3  *                          -------------
   4  *    Simple and efficient bitmask collision detection routines
   5  *  Copyright (C) 2002 Ulf Ekstrom except for the bitcount function.
   6  *
   7  *           >  See the header file for more info. <
   8  *
   9  *  Please email bugs and comments to Ulf Ekstrom, ulfek@ifm.liu.se
  10  *
  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.
  15  *
  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.
  20  *
  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.
  24  */
  25
  26 #include <stdlib.h>
  27 #include <stdio.h>
  28 #include "bitmask.h"
  29
  30 #define MIN(a,b) ((a) < (b) ? (a) : (b))
  31
  32 bitmask *bitmask_create(int w, int h)
  33 {
  34   bitmask *temp = (bitmask*) malloc(sizeof(bitmask));
  35   if (! temp)
  36     return 0;
  37   temp->w = w;
  38   temp->h = h;
  39   temp->bits = (long unsigned int*) calloc(h*((w - 1)/BITW_LEN + 1),sizeof(BITW));
  40   if (! temp->bits)
  41     {
  42       free(temp);
  43       return 0;
  44     }
  45   else
  46     return temp;
  47 }
  48
  49 bitmask *bitmask_create_SDL(SDL_Surface* surf)
  50 {
  51   bitmask* pbitmask = bitmask_create(surf->w, surf->h);
  52   int w,h;
  53   SDL_PixelFormat* fmt;
  54   Uint32 temp, pixel;
  55   Uint8 alpha;
  56
  57   if(surf->format->BytesPerPixel != 4) //This function only works for true-color surfaces with an alpha channel
  58     return 0;
  59
  60   fmt = surf->format;
  61   for(h = 0; h <= surf->h; ++h)
  62     {
  63       for(w = 0; w <= surf->w; ++w)
  64         {
  65
  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 */
  71           alpha=(Uint8)temp;
  72           if (fmt->Amask == 0 || alpha != 0)
  73             bitmask_setbit(pbitmask,w,h);
  74         }
  75     }
  76   return pbitmask;
  77 }
  78 void bitmask_free(bitmask *m)
  79 {
  80   free(m->bits);
  81   free(m);
  82 }
  83
  84 int bitmask_overlap(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
  85 {
  86   BITW *a_entry,*a_end;
  87   BITW *b_entry;
  88   BITW *ap,*bp;
  89   int shift,rshift,i,astripes,bstripes;
  90
  91   if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
  92     return 0;
  93
  94   if (xoffset >= 0)
  95     {
  96       if (yoffset >= 0)
  97         {
  98           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
  99           a_end = a_entry + MIN(b->h,a->h - yoffset);
 100           b_entry = b->bits;
 101         }
 102       else
 103         {
 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;
 107         }
 108       shift = xoffset & BITW_MASK;
 109       if (shift)
 110         {
 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*/
 115             {
 116               for (i=0;i<astripes;i++)
 117                 {
 118                   for (ap = a_entry,bp = b_entry;ap < a_end;) /* Join these two to one loop */
 119                     if ((*ap++ >> shift) & *bp++)
 120                       return 1;
 121                   a_entry += a->h;
 122                   a_end += a->h;
 123                   for (ap = a_entry,bp = b_entry;ap < a_end;)
 124                     if ((*ap++ << rshift) & *bp++)
 125                       return 1;
 126                   b_entry += b->h;
 127                 }
 128               for (ap = a_entry,bp = b_entry;ap < a_end;)
 129                 if ((*ap++ >> shift) & *bp++)
 130                   return 1;
 131               return 0;
 132             }
 133           else /* zig-zag */
 134             {
 135               for (i=0;i<bstripes;i++)
 136                 {
 137                   for (ap = a_entry,bp = b_entry;ap < a_end;)
 138                     if ((*ap++ >> shift) & *bp++)
 139                       return 1;
 140                   a_entry += a->h;
 141                   a_end += a->h;
 142                   for (ap = a_entry,bp = b_entry;ap < a_end;)
 143                     if ((*ap++  << rshift) & *bp++)
 144                       return 1;
 145                   b_entry += b->h;
 146                 }
 147               return 0;
 148             }
 149         }
 150       else /* xoffset is a multiple of the stripe width, and the above routines wont work */
 151         {
 152           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 153           for (i=0;i<astripes;i++)
 154             {
 155               for (ap = a_entry,bp = b_entry;ap < a_end;)
 156                 if (*ap++ & *bp++)
 157                   return 1;
 158               a_entry += a->h;
 159               a_end += a->h;
 160               b_entry += b->h;
 161             }
 162           return 0;
 163         }
 164     }
 165   else
 166     return bitmask_overlap(b,a,-xoffset,-yoffset);
 167 }
 168
 169 /* Will hang if there are no bits set in w! */
 170 static INLINE int firstsetbit(BITW w)
 171 {
 172   int i = 0;
 173   while ((w & 1) == 0)
 174     {
 175       i++;
 176       w/=2;
 177     }
 178   return i;
 179 }
 180
 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)
 183 {
 184   BITW *a_entry,*a_end;
 185   BITW *b_entry;
 186   BITW *ap,*bp;
 187   int shift,rshift,i,astripes,bstripes;
 188
 189   if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
 190     return 0;
 191
 192   if (xoffset >= 0)
 193     {
 194       if (yoffset >= 0)
 195         {
 196           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
 197           a_end = a_entry + MIN(b->h,a->h - yoffset);
 198           b_entry = b->bits;
 199         }
 200       else
 201         {
 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;
 205         }
 206       shift = xoffset & BITW_MASK;
 207       if (shift)
 208         {
 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*/
 213             {
 214               for (i=0;i<astripes;i++)
 215                 {
 216                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 217                     if (*ap & (*bp << shift))
 218                       {
 219                         *y = (ap - a->bits) % a->h;
 220                         *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
 221                         return 1;
 222                       }
 223                   a_entry += a->h;
 224                   a_end += a->h;
 225                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 226                     if (*ap & (*bp >> rshift))
 227                       {
 228                         *y = (ap - a->bits) % a->h;
 229                         *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
 230                         return 1;
 231                       }
 232                   b_entry += b->h;
 233                 }
 234               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 235                 if (*ap & (*bp << shift))
 236                   {
 237                     *y = (ap - a->bits) % a->h;
 238                     *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
 239                     return 1;
 240                   }
 241               return 0;
 242             }
 243           else /* zig-zag */
 244             {
 245               for (i=0;i<bstripes;i++)
 246                 {
 247                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 248                     if (*ap & (*bp << shift))
 249                       {
 250                         *y = (ap - a->bits) % a->h;
 251                         *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
 252                         return 1;
 253                       }
 254                   a_entry += a->h;
 255                   a_end += a->h;
 256                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 257                     if (*ap & (*bp >> rshift))
 258                       {
 259                         *y = (ap - a->bits) % a->h;
 260                         *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
 261                         return 1;
 262                       }
 263                   b_entry += b->h;
 264                 }
 265               return 0;
 266             }
 267         }
 268       else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
 269         {
 270           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 271           for (i=0;i<astripes;i++)
 272             {
 273               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 274                 {
 275                   if (*ap & *bp)
 276                     {
 277                       *y = (ap - a->bits) % a->h;
 278                       *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & *bp);
 279                       return 1;
 280                     }
 281                 }
 282               a_entry += a->h;
 283               a_end += a->h;
 284               b_entry += b->h;
 285             }
 286           return 0;
 287         }
 288     }
 289   else
 290     {
 291       if (bitmask_overlap_pos(b,a,-xoffset,-yoffset,x,y))
 292         {
 293           *x += xoffset;
 294           *y += yoffset;
 295           return 1;
 296         }
 297       else
 298         return 0;
 299     }
 300 }
 301
 302
 303
 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)
 308 {
 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);
 314 }
 315 /* End of Donald W. Gillies bitcount code */
 316
 317
 318 int bitmask_overlap_area(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
 319 {
 320   BITW *a_entry,*a_end;
 321   BITW *b_entry;
 322   BITW *ap,*bp;
 323   int shift,rshift,i,astripes,bstripes;
 324   int count = 0;
 325
 326   if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
 327     return 0;
 328
 329   if (xoffset >= 0)
 330     {
 331       if (yoffset >= 0)
 332         {
 333           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
 334           a_end = a_entry + MIN(b->h,a->h - yoffset);
 335           b_entry = b->bits;
 336         }
 337       else
 338         {
 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;
 342         }
 343       shift = xoffset & BITW_MASK;
 344       if (shift)
 345         {
 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*/
 350             {
 351               for (i=0;i<astripes;i++)
 352                 {
 353                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 354                     count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
 355                   a_entry += a->h;
 356                   a_end += a->h;
 357                   b_entry += b->h;
 358                 }
 359               for (ap = a_entry,bp = b_entry;ap < a_end;)
 360                 count += bitcount((*ap++ >> shift) & *bp++);
 361               return count;
 362             }
 363           else /* zig-zag */
 364             {
 365               for (i=0;i<bstripes;i++)
 366                 {
 367                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 368                     count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
 369                   a_entry += a->h;
 370                   a_end += a->h;
 371                   b_entry += b->h;
 372                 }
 373               return count;
 374             }
 375         }
 376       else /* xoffset is a multiple of the stripe width, and the above routines wont work */
 377         {
 378           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 379           for (i=0;i<astripes;i++)
 380             {
 381               for (ap = a_entry,bp = b_entry;ap < a_end;)
 382                 count += bitcount(*ap++ & *bp++);
 383
 384               a_entry += a->h;
 385               a_end += a->h;
 386               b_entry += b->h;
 387             }
 388           return count;
 389         }
 390     }
 391   else
 392     return bitmask_overlap_area(b,a,-xoffset,-yoffset);
 393 }
 394
 395
 396 /* Draws mask b onto mask a (bitwise OR) */
 397 void bitmask_draw(bitmask *a,bitmask *b,int xoffset, int yoffset)
 398 {
 399   BITW *a_entry,*a_end;
 400   BITW *b_entry;
 401   BITW *ap,*bp;
 402   bitmask *swap;
 403   int shift,rshift,i,astripes,bstripes;
 404
 405   if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
 406     return;
 407
 408   if (xoffset >= 0)
 409     {
 410       if (yoffset >= 0)
 411         {
 412           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
 413           a_end = a_entry + MIN(b->h,a->h - yoffset);
 414           b_entry = b->bits;
 415         }
 416       else
 417         {
 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;
 421         }
 422       shift = xoffset & BITW_MASK;
 423       if (shift)
 424         {
 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*/
 429             {
 430               for (i=0;i<astripes;i++)
 431                 {
 432                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 433                     *ap |= (*bp << shift);
 434                   a_entry += a->h;
 435                   a_end += a->h;
 436                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 437                     *ap |= (*bp >> rshift);
 438                   b_entry += b->h;
 439                 }
 440               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 441                 *ap |= (*bp << shift);
 442               return;
 443             }
 444           else /* zig-zag */
 445             {
 446               for (i=0;i<bstripes;i++)
 447                 {
 448                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 449                     *ap |= (*bp << shift);
 450                   a_entry += a->h;
 451                   a_end += a->h;
 452                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 453                     *ap |= (*bp >> rshift);
 454                   b_entry += b->h;
 455                 }
 456               return;
 457             }
 458         }
 459       else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
 460         {
 461           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 462           for (i=0;i<astripes;i++)
 463             {
 464               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 465                 {
 466                   *ap |= *bp;
 467                 }
 468               a_entry += a->h;
 469               a_end += a->h;
 470               b_entry += b->h;
 471             }
 472           return;
 473         }
 474     }
 475   else
 476     {
 477       /* 'Swapping' arguments to be able to almost reuse the code above */
 478       swap = a;
 479       a = b;
 480       b = swap;
 481       xoffset *= -1;
 482       yoffset *= -1;
 483
 484       if (yoffset >= 0)
 485         {
 486           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
 487           a_end = a_entry + MIN(b->h,a->h - yoffset);
 488           b_entry = b->bits;
 489         }
 490       else
 491         {
 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;
 495         }
 496       shift = xoffset & BITW_MASK;
 497       if (shift)
 498         {
 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*/
 503             {
 504               for (i=0;i<astripes;i++)
 505                 {
 506                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 507                     *bp |= (*ap >> shift);
 508                   a_entry += a->h;
 509                   a_end += a->h;
 510                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 511                     *bp |= (*ap <<rshift);
 512                   b_entry += b->h;
 513                 }
 514               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 515                 *bp |= (*ap >> shift);
 516               return;
 517             }
 518           else /* zig-zag */
 519             {
 520               for (i=0;i<bstripes;i++)
 521                 {
 522                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 523                     *bp |= (*ap >> shift);
 524                   a_entry += a->h;
 525                   a_end += a->h;
 526                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 527                     *bp |= (*ap << rshift);
 528                   b_entry += b->h;
 529                 }
 530               return;
 531             }
 532         }
 533       else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
 534         {
 535           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 536           for (i=0;i<astripes;i++)
 537             {
 538               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 539                 {
 540                   *bp |= *ap;
 541                 }
 542               a_entry += a->h;
 543               a_end += a->h;
 544               b_entry += b->h;
 545             }
 546           return;
 547         }
 548     }
 549 }