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   int w,h;
  52   int bpp;
  53   Uint8* p;
  54
  55   bitmask *temp = (bitmask*) malloc(sizeof(bitmask));
  56   if (! temp)
  57     return 0;
  58   temp->w = surf->w;
  59   temp->h = surf->h;
  60   temp->bits = (long unsigned int*) calloc(surf->h*((surf->w - 1)/BITW_LEN + 1),sizeof(BITW));
  61   if (! temp->bits)
  62     {
  63       free(temp);
  64       return 0;
  65     }
  66   else
  67     return temp;
  68
  69   bpp = surf->format->BytesPerPixel;
  70   for(h = 0; h <= surf->h; ++h)
  71     {
  72       for(w = 0; w <= surf->h; ++w)
  73         {
  74
  75           p = (Uint8 *)surf->pixels + h*surf->pitch + w*bpp;
  76           if(*p == 255)
  77             bitmask_setbit(temp,w,h);
  78         }
  79     }
  80
  81 }
  82
  83 void bitmask_free(bitmask *m)
  84 {
  85   free(m->bits);
  86   free(m);
  87 }
  88
  89 int bitmask_overlap(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
  90 {
  91   BITW *a_entry,*a_end;
  92   BITW *b_entry;
  93   BITW *ap,*bp;
  94   int shift,rshift,i,astripes,bstripes;
  95
  96   if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
  97     return 0;
  98
  99   if (xoffset >= 0)
 100     {
 101       if (yoffset >= 0)
 102         {
 103           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
 104           a_end = a_entry + MIN(b->h,a->h - yoffset);
 105           b_entry = b->bits;
 106         }
 107       else
 108         {
 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;
 112         }
 113       shift = xoffset & BITW_MASK;
 114       if (shift)
 115         {
 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*/
 120             {
 121               for (i=0;i<astripes;i++)
 122                 {
 123                   for (ap = a_entry,bp = b_entry;ap < a_end;) /* Join these two to one loop */
 124                     if ((*ap++ >> shift) & *bp++)
 125                       return 1;
 126                   a_entry += a->h;
 127                   a_end += a->h;
 128                   for (ap = a_entry,bp = b_entry;ap < a_end;)
 129                     if ((*ap++ << rshift) & *bp++)
 130                       return 1;
 131                   b_entry += b->h;
 132                 }
 133               for (ap = a_entry,bp = b_entry;ap < a_end;)
 134                 if ((*ap++ >> shift) & *bp++)
 135                   return 1;
 136               return 0;
 137             }
 138           else /* zig-zag */
 139             {
 140               for (i=0;i<bstripes;i++)
 141                 {
 142                   for (ap = a_entry,bp = b_entry;ap < a_end;)
 143                     if ((*ap++ >> shift) & *bp++)
 144                       return 1;
 145                   a_entry += a->h;
 146                   a_end += a->h;
 147                   for (ap = a_entry,bp = b_entry;ap < a_end;)
 148                     if ((*ap++  << rshift) & *bp++)
 149                       return 1;
 150                   b_entry += b->h;
 151                 }
 152               return 0;
 153             }
 154         }
 155       else /* xoffset is a multiple of the stripe width, and the above routines wont work */
 156         {
 157           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 158           for (i=0;i<astripes;i++)
 159             {
 160               for (ap = a_entry,bp = b_entry;ap < a_end;)
 161                 if (*ap++ & *bp++)
 162                   return 1;
 163               a_entry += a->h;
 164               a_end += a->h;
 165               b_entry += b->h;
 166             }
 167           return 0;
 168         }
 169     }
 170   else
 171     return bitmask_overlap(b,a,-xoffset,-yoffset);
 172 }
 173
 174 /* Will hang if there are no bits set in w! */
 175 static INLINE int firstsetbit(BITW w)
 176 {
 177   int i = 0;
 178   while ((w & 1) == 0)
 179     {
 180       i++;
 181       w/=2;
 182     }
 183   return i;
 184 }
 185
 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)
 188 {
 189   BITW *a_entry,*a_end;
 190   BITW *b_entry;
 191   BITW *ap,*bp;
 192   int shift,rshift,i,astripes,bstripes;
 193
 194   if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
 195     return 0;
 196
 197   if (xoffset >= 0)
 198     {
 199       if (yoffset >= 0)
 200         {
 201           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
 202           a_end = a_entry + MIN(b->h,a->h - yoffset);
 203           b_entry = b->bits;
 204         }
 205       else
 206         {
 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;
 210         }
 211       shift = xoffset & BITW_MASK;
 212       if (shift)
 213         {
 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*/
 218             {
 219               for (i=0;i<astripes;i++)
 220                 {
 221                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 222                     if (*ap & (*bp << shift))
 223                       {
 224                         *y = (ap - a->bits) % a->h;
 225                         *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
 226                         return 1;
 227                       }
 228                   a_entry += a->h;
 229                   a_end += a->h;
 230                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 231                     if (*ap & (*bp >> rshift))
 232                       {
 233                         *y = (ap - a->bits) % a->h;
 234                         *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
 235                         return 1;
 236                       }
 237                   b_entry += b->h;
 238                 }
 239               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 240                 if (*ap & (*bp << shift))
 241                   {
 242                     *y = (ap - a->bits) % a->h;
 243                     *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
 244                     return 1;
 245                   }
 246               return 0;
 247             }
 248           else /* zig-zag */
 249             {
 250               for (i=0;i<bstripes;i++)
 251                 {
 252                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 253                     if (*ap & (*bp << shift))
 254                       {
 255                         *y = (ap - a->bits) % a->h;
 256                         *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp << shift));
 257                         return 1;
 258                       }
 259                   a_entry += a->h;
 260                   a_end += a->h;
 261                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 262                     if (*ap & (*bp >> rshift))
 263                       {
 264                         *y = (ap - a->bits) % a->h;
 265                         *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & (*bp >> rshift));
 266                         return 1;
 267                       }
 268                   b_entry += b->h;
 269                 }
 270               return 0;
 271             }
 272         }
 273       else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
 274         {
 275           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 276           for (i=0;i<astripes;i++)
 277             {
 278               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 279                 {
 280                   if (*ap & *bp)
 281                     {
 282                       *y = (ap - a->bits) % a->h;
 283                       *x = ((ap - a->bits) / a->h)*BITW_LEN + firstsetbit(*ap & *bp);
 284                       return 1;
 285                     }
 286                 }
 287               a_entry += a->h;
 288               a_end += a->h;
 289               b_entry += b->h;
 290             }
 291           return 0;
 292         }
 293     }
 294   else
 295     {
 296       if (bitmask_overlap_pos(b,a,-xoffset,-yoffset,x,y))
 297         {
 298           *x += xoffset;
 299           *y += yoffset;
 300           return 1;
 301         }
 302       else
 303         return 0;
 304     }
 305 }
 306
 307
 308
 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)
 313 {
 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);
 319 }
 320 /* End of Donald W. Gillies bitcount code */
 321
 322
 323 int bitmask_overlap_area(const bitmask *a,const bitmask *b,int xoffset, int yoffset)
 324 {
 325   BITW *a_entry,*a_end;
 326   BITW *b_entry;
 327   BITW *ap,*bp;
 328   int shift,rshift,i,astripes,bstripes;
 329   int count = 0;
 330
 331   if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
 332     return 0;
 333
 334   if (xoffset >= 0)
 335     {
 336       if (yoffset >= 0)
 337         {
 338           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
 339           a_end = a_entry + MIN(b->h,a->h - yoffset);
 340           b_entry = b->bits;
 341         }
 342       else
 343         {
 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;
 347         }
 348       shift = xoffset & BITW_MASK;
 349       if (shift)
 350         {
 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*/
 355             {
 356               for (i=0;i<astripes;i++)
 357                 {
 358                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 359                     count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
 360                   a_entry += a->h;
 361                   a_end += a->h;
 362                   b_entry += b->h;
 363                 }
 364               for (ap = a_entry,bp = b_entry;ap < a_end;)
 365                 count += bitcount((*ap++ >> shift) & *bp++);
 366               return count;
 367             }
 368           else /* zig-zag */
 369             {
 370               for (i=0;i<bstripes;i++)
 371                 {
 372                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 373                     count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
 374                   a_entry += a->h;
 375                   a_end += a->h;
 376                   b_entry += b->h;
 377                 }
 378               return count;
 379             }
 380         }
 381       else /* xoffset is a multiple of the stripe width, and the above routines wont work */
 382         {
 383           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 384           for (i=0;i<astripes;i++)
 385             {
 386               for (ap = a_entry,bp = b_entry;ap < a_end;)
 387                 count += bitcount(*ap++ & *bp++);
 388
 389               a_entry += a->h;
 390               a_end += a->h;
 391               b_entry += b->h;
 392             }
 393           return count;
 394         }
 395     }
 396   else
 397     return bitmask_overlap_area(b,a,-xoffset,-yoffset);
 398 }
 399
 400
 401 /* Draws mask b onto mask a (bitwise OR) */
 402 void bitmask_draw(bitmask *a,bitmask *b,int xoffset, int yoffset)
 403 {
 404   BITW *a_entry,*a_end;
 405   BITW *b_entry;
 406   BITW *ap,*bp;
 407   bitmask *swap;
 408   int shift,rshift,i,astripes,bstripes;
 409
 410   if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h))
 411     return;
 412
 413   if (xoffset >= 0)
 414     {
 415       if (yoffset >= 0)
 416         {
 417           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
 418           a_end = a_entry + MIN(b->h,a->h - yoffset);
 419           b_entry = b->bits;
 420         }
 421       else
 422         {
 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;
 426         }
 427       shift = xoffset & BITW_MASK;
 428       if (shift)
 429         {
 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*/
 434             {
 435               for (i=0;i<astripes;i++)
 436                 {
 437                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 438                     *ap |= (*bp << shift);
 439                   a_entry += a->h;
 440                   a_end += a->h;
 441                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 442                     *ap |= (*bp >> rshift);
 443                   b_entry += b->h;
 444                 }
 445               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 446                 *ap |= (*bp << shift);
 447               return;
 448             }
 449           else /* zig-zag */
 450             {
 451               for (i=0;i<bstripes;i++)
 452                 {
 453                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 454                     *ap |= (*bp << shift);
 455                   a_entry += a->h;
 456                   a_end += a->h;
 457                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 458                     *ap |= (*bp >> rshift);
 459                   b_entry += b->h;
 460                 }
 461               return;
 462             }
 463         }
 464       else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
 465         {
 466           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 467           for (i=0;i<astripes;i++)
 468             {
 469               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 470                 {
 471                   *ap |= *bp;
 472                 }
 473               a_entry += a->h;
 474               a_end += a->h;
 475               b_entry += b->h;
 476             }
 477           return;
 478         }
 479     }
 480   else
 481     {
 482       /* 'Swapping' arguments to be able to almost reuse the code above */
 483       swap = a;
 484       a = b;
 485       b = swap;
 486       xoffset *= -1;
 487       yoffset *= -1;
 488
 489       if (yoffset >= 0)
 490         {
 491           a_entry = a->bits + a->h*(xoffset/BITW_LEN) + yoffset;
 492           a_end = a_entry + MIN(b->h,a->h - yoffset);
 493           b_entry = b->bits;
 494         }
 495       else
 496         {
 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;
 500         }
 501       shift = xoffset & BITW_MASK;
 502       if (shift)
 503         {
 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*/
 508             {
 509               for (i=0;i<astripes;i++)
 510                 {
 511                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 512                     *bp |= (*ap >> shift);
 513                   a_entry += a->h;
 514                   a_end += a->h;
 515                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 516                     *bp |= (*ap <<rshift);
 517                   b_entry += b->h;
 518                 }
 519               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 520                 *bp |= (*ap >> shift);
 521               return;
 522             }
 523           else /* zig-zag */
 524             {
 525               for (i=0;i<bstripes;i++)
 526                 {
 527                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 528                     *bp |= (*ap >> shift);
 529                   a_entry += a->h;
 530                   a_end += a->h;
 531                   for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 532                     *bp |= (*ap << rshift);
 533                   b_entry += b->h;
 534                 }
 535               return;
 536             }
 537         }
 538       else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
 539         {
 540           astripes = (MIN(b->w,a->w - xoffset) - 1)/BITW_LEN + 1;
 541           for (i=0;i<astripes;i++)
 542             {
 543               for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
 544                 {
 545                   *bp |= *ap;
 546                 }
 547               a_entry += a->h;
 548               a_end += a->h;
 549               b_entry += b->h;
 550             }
 551           return;
 552         }
 553     }
 554 }