Commits

illume  committed 953eedb

Adding the bitmask code from Ulf Ekstrom.

This is a python wrapper around his bitmask library.

  • Participants
  • Parent commits 3b0f4cc

Comments (0)

Files changed (7)

 image src/image.c $(SDL) $(DEBUG)
 overlay src/overlay.c $(SDL) $(DEBUG)
 transform src/transform.c src/rotozoom.c src/scale2x.c $(SDL) $(DEBUG)
-
+mask src/mask.c src/bitmask.c $(SDL) $(DEBUG)
 
 #the following are placeholders. setup.py can use them to help
 #auto-copy needed DLLs into the pygame installation folder.
 # CVS tag names are placed before the date
 # BREAK = change breaks existing code
 # BUG	= fixed a bug that was (or could have been) crashing
+#
+#
+May 9, 2007
+    Windows bitmap copy/paste is working for scrap.
 
 May 2, 2007
     [BUG] fromstring,tostring work for alpha. Thanks Brian Fisher.

File examples/mask.py

+import profile
+import sys, bitmask, random
+import pygame, pygame.image, pygame.surface, pygame.time, pygame.display
+
+def maskFromSurface(surface, threshold = 127):
+    mask = bitmask.Mask(surface.get_size())
+    key = surface.get_colorkey()
+    if key:
+        for y in range(surface.get_height()):
+            for x in range(surface.get_width()):
+                if surface.get_at((x+0.1,y+0.1)) != key:
+                    mask.set_at((x,y),1)
+    else:
+        for y in range(surface.get_height()):
+            for x in range (surface.get_width()):
+                if surface.get_at((x,y))[3] > threshold:
+                    mask.set_at((x,y),1)
+    return mask
+
+def vadd(x,y):
+    return [x[0]+y[0],x[1]+y[1]]
+
+def vsub(x,y):
+    return [x[0]-y[0],x[1]-y[1]]
+
+def vdot(x,y):
+    return x[0]*y[0]+x[1]*y[1]
+
+class Sprite:
+    def __init__(self, surface, mask = None):
+        self.surface = surface
+        if mask:
+            self.mask = mask
+        else:
+            self.mask = maskFromSurface(self.surface)
+        self.setPos([0,0])
+        self.setVelocity([0,0])
+        
+    def setPos(self,pos):
+        self.pos = [pos[0],pos[1]]
+    def setVelocity(self,vel):
+        self.vel = [vel[0],vel[1]]
+    def move(self,dr):
+        self.pos = vadd(self.pos,dr)
+    def kick(self,impulse):
+        self.vel[0] += impulse[0]
+        self.vel[1] += impulse[1]
+
+    def collide(self,s):
+        """Test if the sprites are colliding and
+        resolve the collision in this case."""
+        offset = map(int,vsub(s.pos,self.pos))
+        overlap = self.mask.overlap_area(s.mask,offset)
+        if overlap == 0:
+            return
+        """Calculate collision normal"""
+        nx = (self.mask.overlap_area(s.mask,(offset[0]+1,offset[1])) -
+              self.mask.overlap_area(s.mask,(offset[0]-1,offset[1])))
+        ny = (self.mask.overlap_area(s.mask,(offset[0],offset[1]+1)) -
+              self.mask.overlap_area(s.mask,(offset[0],offset[1]-1)))
+        if nx == 0 and ny == 0:
+            """One sprite is inside another"""
+            return
+        n = [nx,ny]
+        dv = vsub(s.vel,self.vel)
+        J = vdot(dv,n)/(2*vdot(n,n))
+        if J > 0:
+            """Can scale up to 2*J here to get bouncy collisions"""
+            J *= 1.9
+            self.kick([nx*J,ny*J])
+            s.kick([-J*nx,-J*ny])
+        return
+        """Separate the sprites"""
+        c1 = -overlap/vdot(n,n)
+        c2 = -c1/2
+        self.move([c2*nx,c2*ny])
+        s.move([(c1+c2)*nx,(c1+c2)*ny])
+        
+    def update(self,dt):
+        self.pos[0] += dt*self.vel[0]
+        self.pos[1] += dt*self.vel[1]
+
+
+def main(argv):
+    if len(argv) < 2:
+        print 'Usage: pygame_example IMAGE'
+        print 'Let many copies of IMAGE bounce against each other'
+        print 'Press any key to quit'
+        return
+    print 'Press any key to quit'
+    screen = pygame.display.set_mode((640,480))
+    images = []
+    masks = []
+    for impath in argv[1:]:
+        images.append(pygame.image.load(impath).convert_alpha())
+        masks.append(maskFromSurface(images[-1]))
+    sprites = []
+    for i in range(20):
+        j = i % len(images)
+        s = Sprite(images[j],masks[j])
+        s.setPos((random.uniform(0,screen.get_width()),
+                  random.uniform(0,screen.get_height())))
+        s.setVelocity((random.uniform(-5,5),random.uniform(-5,5)))
+        sprites.append(s)
+    pygame.time.set_timer(pygame.USEREVENT,33)
+    while 1:
+        event = pygame.event.wait()
+        if event.type == pygame.QUIT:
+            return
+        elif event.type == pygame.USEREVENT:
+            """Do both mechanics and screen update"""
+            screen.fill((240,220,100))
+            for i in range(len(sprites)):
+                for j in range(i+1,len(sprites)):
+                    sprites[i].collide(sprites[j])
+            for s in sprites:
+                s.update(1)
+                if s.pos[0] < -s.surface.get_width()-3:
+                    s.pos[0] = screen.get_width()
+                elif s.pos[0] > screen.get_width()+3:
+                    s.pos[0] = -s.surface.get_width()
+                if s.pos[1] < -s.surface.get_height()-3:
+                    s.pos[1] = screen.get_height()
+                elif s.pos[1] > screen.get_height()+3:
+                    s.pos[1] = -s.surface.get_height()
+                screen.blit(s.surface,s.pos)
+            pygame.display.update()
+        elif event.type == pygame.KEYDOWN:
+            return
+
+main(sys.argv)
+
+
+
+        

File lib/locals.py

 from pygame.rect import Rect
 import pygame.color as color
 Color = color.Color
+import pygame.mask
+Mask = pygame.mask.Mask
 

File src/bitmask.c

+/*
+    Bitmask Collision Detection Library 1.5
+    Copyright (C) 2002-2005 Ulf Ekstrom except for the bitcount function which
+    is copyright (C) Donald W. Gillies, 1992, and the other bitcount function
+    which was taken from Jorg Arndt's excellent "Algorithms for Programmers"
+    text.
+  
+    This library is free software; you can redistribute it and/or
+    modify it under the terms of the GNU Library General Public
+    License as published by the Free Software Foundation; either
+    version 2 of the License, or (at your option) any later version.
+ 
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Library General Public License for more details.
+ 
+    You should have received a copy of the GNU Library General Public
+    License along with this library; if not, write to the Free
+    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+
+#include <stdlib.h>
+#include <stddef.h>
+#include <string.h>
+#include "bitmask.h"
+
+#ifndef INLINE
+#warning No INLINE definition in bitmask.h, performance may suffer.
+#endif
+
+#define MIN(a,b) ((a) <= (b) ? (a) : (b))
+#define MAX(a,b) ((a) >= (b) ? (a) : (b))
+
+bitmask_t *bitmask_create(int w, int h)
+{
+  bitmask_t *temp;
+  temp = malloc(offsetof(bitmask_t,bits) + h*((w - 1)/BITMASK_W_LEN + 1)*sizeof(BITMASK_W));  
+  if (!temp) 
+    return 0;
+  temp->w = w;
+  temp->h = h;
+  bitmask_clear(temp);
+  return temp;
+}
+
+void bitmask_free(bitmask_t *m)
+{
+  free(m);
+}
+
+void bitmask_clear(bitmask_t *m)
+{
+  memset(m->bits,0,m->h*((m->w - 1)/BITMASK_W_LEN + 1)*sizeof(BITMASK_W));
+}
+
+void bitmask_fill(bitmask_t *m)
+{
+  int x,y;
+  for (y = 0; y < m->h; y++)
+    for (x = 0; x < m->w; x++)
+      bitmask_setbit(m, x, y);
+}
+
+int bitmask_overlap(const bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset)
+{
+  const BITMASK_W *a_entry,*a_end;
+  const BITMASK_W *b_entry;
+  const BITMASK_W *ap,*app,*bp;
+  unsigned int shift,rshift,i,astripes,bstripes;
+  
+  if ((xoffset >= a->w) || (yoffset >= a->h) || (b->h + yoffset <= 0) || (b->w + xoffset <= 0)) 
+      return 0;
+
+  if (xoffset >= 0) 
+    {
+    swapentry:
+      if (yoffset >= 0)
+	{
+	  a_entry = a->bits + a->h*((unsigned int)xoffset/BITMASK_W_LEN) + yoffset;
+	  a_end = a_entry + MIN(b->h,a->h - yoffset);
+	  b_entry = b->bits;
+	}
+      else
+	{
+	  a_entry = a->bits + a->h*((unsigned int)xoffset/BITMASK_W_LEN);
+	  a_end = a_entry + MIN(b->h + yoffset,a->h);
+	  b_entry = b->bits - yoffset;
+	}
+      shift = xoffset & BITMASK_W_MASK;
+      if (shift)
+	{
+	  rshift = BITMASK_W_LEN - shift;
+	  astripes = ((unsigned int)(a->w - 1))/BITMASK_W_LEN - (unsigned int)xoffset/BITMASK_W_LEN;
+	  bstripes = ((unsigned int)(b->w - 1))/BITMASK_W_LEN + 1;
+	  if (bstripes > astripes) /* zig-zag .. zig*/
+	    {
+	      for (i=0;i<astripes;i++)
+		{
+		  for (ap = a_entry, app = ap + a->h, bp = b_entry;ap < a_end;) 
+		    if ((*ap++ >> shift) & *bp || (*app++ << rshift) & *bp++) return 1;
+		  a_entry += a->h;
+		  a_end += a->h;
+		  b_entry += b->h;
+		}
+	      for (ap = a_entry,bp = b_entry;ap < a_end;)
+		  if ((*ap++ >> shift) & *bp++) return 1;
+	      return 0;
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (ap = a_entry, app = ap + a->h, bp = b_entry;ap < a_end;) 
+		    if ((*ap++ >> shift) & *bp || (*app++ << rshift) & *bp++) return 1;
+		  a_entry += a->h;
+		  a_end += a->h;
+		  b_entry += b->h;
+		}
+	      return 0;
+	    }
+	}
+      else /* xoffset is a multiple of the stripe width, and the above routines wont work */
+	{
+	  astripes = (MIN(b->w,a->w - xoffset) - 1)/BITMASK_W_LEN + 1;
+	  for (i=0;i<astripes;i++)
+	    {
+	      for (ap = a_entry,bp = b_entry;ap < a_end;)
+		if (*ap++ & *bp++) return 1;
+	      a_entry += a->h;
+	      a_end += a->h;
+	      b_entry += b->h;
+	    }
+	  return 0;
+	}
+    }
+  else  
+    {
+      const bitmask_t *c = a;
+      a = b;
+      b = c;
+      xoffset *= -1;
+      yoffset *= -1;
+      goto swapentry;
+    }
+}
+
+/* Will hang if there are no bits set in w! */
+static INLINE int firstsetbit(BITMASK_W w)
+{
+  int i = 0;
+  while ((w & 1) == 0) 
+    {
+      i++;
+      w/=2;
+    }
+  return i;
+}
+
+/* x and y are given in the coordinates of mask a, and are untouched if there is no overlap */
+int bitmask_overlap_pos(const bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset, int *x, int *y)
+{
+  const BITMASK_W *a_entry,*a_end, *b_entry, *ap, *bp;
+  unsigned int shift,rshift,i,astripes,bstripes,xbase;
+  
+  if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h)) 
+      return 0;
+  
+  if (xoffset >= 0) 
+    {
+      xbase = xoffset/BITMASK_W_LEN; /* first stripe from mask a */
+      if (yoffset >= 0)
+	{
+	  a_entry = a->bits + a->h*xbase + yoffset;
+	  a_end = a_entry + MIN(b->h,a->h - yoffset);
+	  b_entry = b->bits;
+	}
+      else
+	{
+	  a_entry = a->bits + a->h*xbase;
+	  a_end = a_entry + MIN(b->h + yoffset,a->h);
+	  b_entry = b->bits - yoffset;
+	  yoffset = 0; /* relied on below */
+	}
+      shift = xoffset & BITMASK_W_MASK;
+      if (shift)
+	{
+	  rshift = BITMASK_W_LEN - shift;
+	  astripes = (a->w - 1)/BITMASK_W_LEN - xoffset/BITMASK_W_LEN;
+	  bstripes = (b->w - 1)/BITMASK_W_LEN + 1;
+	  if (bstripes > astripes) /* zig-zag .. zig*/
+	    {
+	      for (i=0;i<astripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		      if (*ap & (*bp << shift)) 
+			{
+			  *y = ap - a_entry + yoffset;
+			  *x = (xbase + i)*BITMASK_W_LEN + firstsetbit(*ap & (*bp << shift));
+			  return 1;
+			}
+		  a_entry += a->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		      if (*ap & (*bp >> rshift)) 
+			{
+			  *y = ap - a_entry + yoffset;
+			  *x = (xbase + i + 1)*BITMASK_W_LEN + firstsetbit(*ap & (*bp >> rshift));
+			  return 1;
+			}
+		  b_entry += b->h;
+		}
+	      for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		if (*ap & (*bp << shift)) 
+		  {
+		    *y = ap - a_entry + yoffset;
+		    *x = (xbase + astripes)*BITMASK_W_LEN + firstsetbit(*ap & (*bp << shift));
+		    return 1;
+		  }
+	      return 0;
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		      if (*ap & (*bp << shift)) 
+			{
+			  *y = ap - a_entry + yoffset;
+			  *x = (xbase + i)*BITMASK_W_LEN + firstsetbit(*ap & (*bp << shift));
+			  return 1;
+			}
+		  a_entry += a->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		      if (*ap & (*bp >> rshift)) 
+			{
+			  *y = ap - a_entry + yoffset;
+			  *x = (xbase + i + 1)*BITMASK_W_LEN + firstsetbit(*ap & (*bp >> rshift));
+			  return 1;
+			}
+		  b_entry += b->h;
+		}
+	      return 0;
+	    }
+	}
+      else 
+/* xoffset is a multiple of the stripe width, and the above routines
+   won't work. This way is also slightly faster. */
+	{
+	  astripes = (MIN(b->w,a->w - xoffset) - 1)/BITMASK_W_LEN + 1;
+	  for (i=0;i<astripes;i++)
+	    {
+	      for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		{
+		  if (*ap & *bp)
+		    {
+		      *y = ap - a_entry + yoffset;
+		      *x = (xbase + i)*BITMASK_W_LEN + firstsetbit(*ap & *bp); 
+		      return 1;
+		    }
+		}
+	      a_entry += a->h;
+	      a_end += a->h;
+	      b_entry += b->h;
+	    }
+	  return 0;
+	}
+    }
+  else  
+    {
+      if (bitmask_overlap_pos(b,a,-xoffset,-yoffset,x,y))
+	{
+	  *x += xoffset;
+	  *y += yoffset;
+	  return 1;
+	}
+      else
+	return 0;
+    }
+}
+
+/* The code by Gillies is slightly (1-3%) faster than the more
+   readable code below */
+#define GILLIES
+
+static INLINE unsigned int bitcount(BITMASK_W n)
+{
+  if (BITMASK_W_LEN == 32)
+    {
+#ifdef GILLIES
+/* (C) Donald W. Gillies, 1992.  All rights reserved.  You may reuse
+   this bitcount() function anywhere you please as long as you retain
+   this Copyright Notice. */
+      register unsigned long tmp;
+      return (tmp = (n) - (((n) >> 1) & 033333333333) - 
+	      (((n) >> 2) & 011111111111),
+	      tmp = ((tmp + (tmp >> 3)) & 030707070707),
+	      tmp =  (tmp + (tmp >> 6)),
+	      tmp = (tmp + (tmp >> 12) + (tmp >> 24)) & 077);
+/* End of Donald W. Gillies bitcount code */
+#else
+   /* This piece taken from Jorg Arndt's "Algorithms for Programmers" */
+    n  = ((n>>1) & 0x55555555) + (n & 0x55555555);  // 0-2 in 2 bits
+    n  = ((n>>2) & 0x33333333) + (n & 0x33333333);  // 0-4 in 4 bits
+    n  = ((n>>4) + n) & 0x0f0f0f0f;                 // 0-8 in 4 bits
+    n +=  n>> 8;                                    // 0-16 in 8 bits
+    n +=  n>>16;                                    // 0-32 in 8 bits
+    return  n & 0xff;
+#endif
+    }
+  else if (BITMASK_W_LEN == 64)
+    {
+      n  = ((n>>1) & 0x5555555555555555) + (n & 0x5555555555555555);
+      n  = ((n>>2) & 0x3333333333333333) + (n & 0x3333333333333333);
+      n  = ((n>>4) + n) & 0x0f0f0f0f0f0f0f0f;
+      n +=  n>> 8;                                    
+      n +=  n>>16;                                    
+      n +=  n>>32;
+      return  n & 0xff;
+    }
+  else
+    {
+      /* Handle non-32 or 64 bit case the slow way */
+      unsigned int nbits = 0;
+      while (n)
+	{
+	  if (n & 1)
+	    nbits++;
+	  n = n >> 1;
+	}
+      return nbits;
+    }
+}
+
+int bitmask_overlap_area(const bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset)
+{
+  const BITMASK_W *a_entry,*a_end, *b_entry, *ap,*bp;
+  unsigned int shift,rshift,i,astripes,bstripes;
+  unsigned int count = 0;
+
+  if ((xoffset >= a->w) || (yoffset >= a->h) || (b->h + yoffset <= 0) || (b->w + xoffset <= 0)) 
+      return 0;
+  
+  if (xoffset >= 0) 
+    {
+    swapentry:
+      if (yoffset >= 0)
+	{
+	  a_entry = a->bits + a->h*(xoffset/BITMASK_W_LEN) + yoffset;
+	  a_end = a_entry + MIN(b->h,a->h - yoffset);
+	  b_entry = b->bits;
+	}
+      else
+	{
+	  a_entry = a->bits + a->h*(xoffset/BITMASK_W_LEN);
+	  a_end = a_entry + MIN(b->h + yoffset,a->h);
+	  b_entry = b->bits - yoffset;
+	}
+      shift = xoffset & BITMASK_W_MASK;
+      if (shift)
+	{
+	  rshift = BITMASK_W_LEN - shift;
+	  astripes = (a->w - 1)/BITMASK_W_LEN - xoffset/BITMASK_W_LEN;
+	  bstripes = (b->w - 1)/BITMASK_W_LEN + 1;
+	  if (bstripes > astripes) /* zig-zag .. zig*/
+	    {
+	      for (i=0;i<astripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
+		  a_entry += a->h;
+		  a_end += a->h;
+		  b_entry += b->h;
+		}
+	      for (ap = a_entry,bp = b_entry;ap < a_end;)
+		count += bitcount((*ap++ >> shift) & *bp++);
+	      return count;
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    count += bitcount(((*ap >> shift) | (*(ap + a->h) << rshift)) & *bp);
+		  a_entry += a->h;
+		  a_end += a->h;
+		  b_entry += b->h;
+		}
+	      return count;
+	    }
+	}
+      else /* xoffset is a multiple of the stripe width, and the above routines wont work */
+	{
+	  astripes = (MIN(b->w,a->w - xoffset) - 1)/BITMASK_W_LEN + 1;
+	  for (i=0;i<astripes;i++)
+	    {
+	      for (ap = a_entry,bp = b_entry;ap < a_end;)
+		count += bitcount(*ap++ & *bp++);
+
+	      a_entry += a->h;
+	      a_end += a->h;
+	      b_entry += b->h;
+	    }
+	  return count;
+	}
+    }
+  else  
+    {
+      const bitmask_t *c = a;
+      a = b;
+      b = c;
+      xoffset *= -1;
+      yoffset *= -1;
+      goto swapentry;
+    }
+}
+
+/* Draws mask b onto mask a (bitwise OR) */
+void bitmask_draw(bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset)
+{
+  BITMASK_W *a_entry,*a_end, *ap;
+  const BITMASK_W *b_entry, *b_end, *bp;
+  int shift,rshift,i,astripes,bstripes;
+  
+  if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h)) 
+      return;
+  
+  if (xoffset >= 0) 
+    {
+      if (yoffset >= 0)
+	{
+	  a_entry = a->bits + a->h*(xoffset/BITMASK_W_LEN) + yoffset;
+	  a_end = a_entry + MIN(b->h,a->h - yoffset);
+	  b_entry = b->bits;
+	}
+      else
+	{
+	  a_entry = a->bits + a->h*(xoffset/BITMASK_W_LEN);
+	  a_end = a_entry + MIN(b->h + yoffset,a->h);
+	  b_entry = b->bits - yoffset;
+	}
+      shift = xoffset & BITMASK_W_MASK;
+      if (shift)
+	{
+	  rshift = BITMASK_W_LEN - shift;
+	  astripes = (a->w - 1)/BITMASK_W_LEN - xoffset/BITMASK_W_LEN;
+	  bstripes = (b->w - 1)/BITMASK_W_LEN + 1;
+	  if (bstripes > astripes) /* zig-zag .. zig*/
+	    {
+	      for (i=0;i<astripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *ap |= (*bp << shift);
+		  a_entry += a->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *ap |= (*bp >> rshift);
+		  b_entry += b->h;
+		}
+	      for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		*ap |= (*bp << shift);
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *ap |= (*bp << shift);
+		  a_entry += a->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *ap |= (*bp >> rshift);
+		  b_entry += b->h;
+		}
+	    }
+	}
+      else /* xoffset is a multiple of the stripe width, 
+	      and the above routines won't work. */
+	{
+	  astripes = (MIN(b->w,a->w - xoffset) - 1)/BITMASK_W_LEN + 1;
+	  for (i=0;i<astripes;i++)
+	    {
+	      for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		{
+		  *ap |= *bp;
+		}
+	      a_entry += a->h;
+	      a_end += a->h;
+	      b_entry += b->h;
+	    }
+	}
+    }
+  else  
+    {
+      xoffset *= -1;
+      yoffset *= -1;
+
+      if (yoffset >= 0)
+	{
+	  b_entry = b->bits + b->h*(xoffset/BITMASK_W_LEN) + yoffset;
+	  b_end = b_entry + MIN(a->h,b->h - yoffset);
+	  a_entry = a->bits;
+	}
+      else
+	{
+	  b_entry = b->bits + b->h*(xoffset/BITMASK_W_LEN);
+	  b_end = b_entry + MIN(a->h + yoffset,b->h);
+	  a_entry = a->bits - yoffset;
+	}
+      shift = xoffset & BITMASK_W_MASK;
+      if (shift)
+	{
+	  rshift = BITMASK_W_LEN - shift;
+	  astripes = (b->w - 1)/BITMASK_W_LEN - xoffset/BITMASK_W_LEN;
+	  bstripes = (a->w - 1)/BITMASK_W_LEN + 1;
+	  if (bstripes > astripes) /* zig-zag .. zig*/
+	    {
+	      for (i=0;i<astripes;i++)
+		{
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap |= (*bp >> shift);
+		  b_entry += b->h;
+		  b_end += b->h;
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap |= (*bp <<rshift); 
+		  a_entry += a->h;
+		}
+	      for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		*ap |= (*bp >> shift);
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap |= (*bp >> shift);
+		  b_entry += b->h;
+		  b_end += b->h;
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap |= (*bp << rshift);
+		  a_entry += a->h;
+		}
+	    }
+	}
+      else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
+	{
+	  astripes = (MIN(a->w,b->w - xoffset) - 1)/BITMASK_W_LEN + 1;
+	  for (i=0;i<astripes;i++)
+	    {
+	      for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		{
+		  *ap |= *bp;
+		}
+	      b_entry += b->h;
+	      b_end += b->h;
+	      a_entry += a->h;
+	    }
+	}
+      xoffset *= -1;
+      yoffset *= -1;
+    }	
+  /* Zero out bits outside the mask rectangle (to the right), if there
+   is a chance we were drawing there. */
+  if (xoffset + b->w > a->w)
+    {
+      BITMASK_W edgemask;
+      int n = a->w/BITMASK_W_LEN;
+      shift = (n + 1)*BITMASK_W_LEN - a->w;
+      edgemask = (~(BITMASK_W)0) >> shift;
+      a_end = a->bits + n*a->h + MIN(a->h,b->h + yoffset);
+      for (ap = a->bits + n*a->h + MAX(yoffset,0);ap<a_end;ap++)
+	*ap &= edgemask;
+    }
+}
+
+/* Erases mask b from mask a (a &= ~b) */
+void bitmask_erase(bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset)
+{
+  BITMASK_W *a_entry,*a_end, *ap;
+  const BITMASK_W *b_entry, *b_end, *bp;
+  int shift,rshift,i,astripes,bstripes;
+  
+  if ((xoffset >= a->w) || (yoffset >= a->h) || (yoffset <= - b->h)) 
+      return;
+  
+  if (xoffset >= 0) 
+    {
+      if (yoffset >= 0)
+	{
+	  a_entry = a->bits + a->h*(xoffset/BITMASK_W_LEN) + yoffset;
+	  a_end = a_entry + MIN(b->h,a->h - yoffset);
+	  b_entry = b->bits;
+	}
+      else
+	{
+	  a_entry = a->bits + a->h*(xoffset/BITMASK_W_LEN);
+	  a_end = a_entry + MIN(b->h + yoffset,a->h);
+	  b_entry = b->bits - yoffset;
+	}
+      shift = xoffset & BITMASK_W_MASK;
+      if (shift)
+	{
+	  rshift = BITMASK_W_LEN - shift;
+	  astripes = (a->w - 1)/BITMASK_W_LEN - xoffset/BITMASK_W_LEN;
+	  bstripes = (b->w - 1)/BITMASK_W_LEN + 1;
+	  if (bstripes > astripes) /* zig-zag .. zig*/
+	    {
+	      for (i=0;i<astripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *ap &= ~(*bp << shift);
+		  a_entry += a->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *ap &= ~(*bp >> rshift);
+		  b_entry += b->h;
+		}
+	      for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		*ap &= ~(*bp << shift);
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *ap &= ~(*bp << shift);
+		  a_entry += a->h;
+		  a_end += a->h;
+		  for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		    *ap &= ~(*bp >> rshift);
+		  b_entry += b->h;
+		}
+	    }
+	}
+      else /* xoffset is a multiple of the stripe width, 
+	      and the above routines won't work. */
+	{
+	  astripes = (MIN(b->w,a->w - xoffset) - 1)/BITMASK_W_LEN + 1;
+	  for (i=0;i<astripes;i++)
+	    {
+	      for (ap = a_entry,bp = b_entry;ap < a_end;ap++,bp++)
+		{
+		  *ap &= ~*bp;
+		}
+	      a_entry += a->h;
+	      a_end += a->h;
+	      b_entry += b->h;
+	    }
+	}
+    }
+  else  
+    {
+      xoffset *= -1;
+      yoffset *= -1;
+
+      if (yoffset >= 0)
+	{
+	  b_entry = b->bits + b->h*(xoffset/BITMASK_W_LEN) + yoffset;
+	  b_end = b_entry + MIN(a->h,b->h - yoffset);
+	  a_entry = a->bits;
+	}
+      else
+	{
+	  b_entry = b->bits + b->h*(xoffset/BITMASK_W_LEN);
+	  b_end = b_entry + MIN(a->h + yoffset,b->h);
+	  a_entry = a->bits - yoffset;
+	}
+      shift = xoffset & BITMASK_W_MASK;
+      if (shift)
+	{
+	  rshift = BITMASK_W_LEN - shift;
+	  astripes = (b->w - 1)/BITMASK_W_LEN - xoffset/BITMASK_W_LEN;
+	  bstripes = (a->w - 1)/BITMASK_W_LEN + 1;
+	  if (bstripes > astripes) /* zig-zag .. zig*/
+	    {
+	      for (i=0;i<astripes;i++)
+		{
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap &= ~(*bp >> shift);
+		  b_entry += b->h;
+		  b_end += b->h;
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap &= ~(*bp <<rshift); 
+		  a_entry += a->h;
+		}
+	      for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		*ap |= (*bp >> shift);
+	    }
+	  else /* zig-zag */
+	    {
+	      for (i=0;i<bstripes;i++)
+		{
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap &= ~(*bp >> shift);
+		  b_entry += b->h;
+		  b_end += b->h;
+		  for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		    *ap &= ~(*bp << rshift);
+		  a_entry += a->h;
+		}
+	    }
+	}
+      else /* xoffset is a multiple of the stripe width, and the above routines won't work. */
+	{
+	  astripes = (MIN(a->w,b->w - xoffset) - 1)/BITMASK_W_LEN + 1;
+	  for (i=0;i<astripes;i++)
+	    {
+	      for (bp = b_entry,ap = a_entry;bp < b_end;bp++,ap++)
+		*ap &= ~*bp;
+	      b_entry += b->h;
+	      b_end += b->h;
+	      a_entry += a->h;
+	    }
+	}
+    }	
+}
+
+
+
+bitmask_t *bitmask_scale(const bitmask_t *m, int w, int h)
+{
+  bitmask_t *nm;
+  int x,y,nx,ny,dx,dy,dnx,dny;
+
+  if (w < 1 || h < 1)
+    {
+      nm = bitmask_create(1,1);
+      return nm;
+    }
+
+  nm = bitmask_create(w,h);
+  if (!nm)
+    return NULL;
+  ny = dny = 0;
+  for (y=0,dy=h; y<m->h; y++,dy+=h)
+    {      
+      while (dny < dy)
+	{
+	  nx = dnx = 0;
+	  for (x=0,dx=w; x < m->w; x++, dx+=w)
+	    {
+	      if (bitmask_getbit(m,x,y))
+		{
+		  while (dnx < dx)
+		    {
+		      bitmask_setbit(nm,nx,ny);
+		      nx++;
+		      dnx += m->w;
+		    }
+		}
+	      else
+		{
+		  while (dnx < dx)
+		    {
+		      nx++;
+		      dnx += m->w;
+		    }
+		}
+	    }
+	  ny++;
+	  dny+=m->h;
+	}
+    }
+  return nm;
+}
+

File src/bitmask.h

+/*
+    Bitmask 1.7 - A pixel-perfect collision detection library.
+
+    Copyright (C) 2002-2005 Ulf Ekstrom except for the bitcount
+    function which is copyright (C) Donald W. Gillies, 1992.
+  
+    This library is free software; you can redistribute it and/or
+    modify it under the terms of the GNU Library General Public
+    License as published by the Free Software Foundation; either
+    version 2 of the License, or (at your option) any later version.
+ 
+    This library is distributed in the hope that it will be useful,
+    but WITHOUT ANY WARRANTY; without even the implied warranty of
+    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+    Library General Public License for more details.
+ 
+    You should have received a copy of the GNU Library General Public
+    License along with this library; if not, write to the Free
+    Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
+ */
+#ifndef BITMASK_H
+#define BITMASK_H
+
+#ifdef __cplusplus
+extern "C" {
+#endif
+
+#include <limits.h>
+/* Define INLINE for different compilers.  If your compiler does not
+   support inlining then there might be a performance hit in
+   bitmask_overlap_area().
+*/
+#ifndef INLINE
+# ifdef __GNUC__
+#  define INLINE inline
+# else
+#  ifdef _MSC_VER
+#   define INLINE __inline
+#  else
+#   define INLINE
+#  endif
+# endif
+#endif
+
+#define BITMASK_W unsigned long int
+#define BITMASK_W_LEN (sizeof(BITMASK_W)*CHAR_BIT)
+#define BITMASK_W_MASK (BITMASK_W_LEN - 1)
+#define BITMASK_N(n) ((BITMASK_W)1 << (n))
+
+typedef struct bitmask
+{
+  int w,h;
+  BITMASK_W bits[1];
+} bitmask_t;
+
+/* Creates a bitmask of width w and height h, where
+   w and h must both be greater than 0.
+   The mask is automatically cleared when created.
+ */
+bitmask_t *bitmask_create(int w, int h);
+
+/* Frees all the memory allocated by bitmask_create for m. */
+void bitmask_free(bitmask_t *m);
+
+/* Clears all bits in the mask */
+void bitmask_clear(bitmask_t *m);
+
+/* Sets all bits in the mask */
+void bitmask_fill(bitmask_t *m);
+
+/* Returns nonzero if the bit at (x,y) is set.  Coordinates start at
+   (0,0) */
+static INLINE int bitmask_getbit(const bitmask_t *m, int x, int y) 
+{ 
+  return (m->bits[x/BITMASK_W_LEN*m->h + y] & BITMASK_N(x & BITMASK_W_MASK)) != 0;
+}
+
+/* Sets the bit at (x,y) */
+static INLINE void bitmask_setbit(bitmask_t *m, int x, int y)
+{ 
+  m->bits[x/BITMASK_W_LEN*m->h + y] |= BITMASK_N(x & BITMASK_W_MASK); 
+}
+
+/* Clears the bit at (x,y) */
+static INLINE void bitmask_clearbit(bitmask_t *m, int x, int y)
+{ 
+  m->bits[x/BITMASK_W_LEN*m->h + y] &= ~BITMASK_N(x & BITMASK_W_MASK); 
+}
+
+/* Returns nonzero if the masks overlap with the given offset. 
+   The overlap tests uses the following offsets (which may be negative):
+
+   +----+----------..
+   |A   | yoffset   
+   |  +-+----------..
+   +--|B        
+   |xoffset      
+   |  |
+   :  :  
+*/
+int bitmask_overlap(const bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset);
+
+/* Like bitmask_overlap(), but will also give a point of intersection.
+   x and y are given in the coordinates of mask a, and are untouched
+   if there is no overlap. */
+int bitmask_overlap_pos(const bitmask_t *a, const bitmask_t *b,
+			int xoffset, int yoffset, int *x, int *y);
+
+/* Returns the number of overlapping 'pixels' */
+int bitmask_overlap_area(const bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset);
+
+
+
+/* Draws mask b onto mask a (bitwise OR). Can be used to compose large
+   (game background?) mask from several submasks, which may speed up
+   the testing. */
+
+void bitmask_draw(bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset);
+
+void bitmask_erase(bitmask_t *a, const bitmask_t *b, int xoffset, int yoffset);
+
+/* Return a new scaled bitmask, with dimensions w*h. The quality of the
+   scaling may not be perfect for all circumstances, but it should
+   be reasonable. If either w or h is 0 a clear 1x1 mask is returned. */
+bitmask_t *bitmask_scale(const bitmask_t *m, int w, int h);
+
+#ifdef __cplusplus
+} /* End of extern "C" { */
+#endif
+
+#endif
+/*
+  This wrapper code was originally written by Danny van Bruggen(?) for
+  the SCAM library, it was then converted by Ulf Ekstrom to wrap the
+  bitmask library, a spinoff from SCAM.
+
+  This file is released under the LGPL licence, see COPYING for 
+  details.
+*/
+
+#include <Python.h>
+#include "bitmask.h"
+
+typedef struct {
+  PyObject_HEAD
+  bitmask_t *mask;
+} PyMaskObject;
+
+staticforward PyTypeObject PyMask_Type;
+#define PyMask_Check(x) ((x)->ob_type == &PyMask_Type)
+#define PyMask_AsBitmap(x) (((PyMaskObject*)x)->mask)
+
+
+#define PyType_Init(x)                                          \
+{                                                               \
+    x.ob_type = &PyType_Type;                                   \
+}
+
+
+/* mask object methods */
+
+static char doc_mask_get_size[] = "Mask.get_size() -> width,height";
+static PyObject* mask_get_size(PyObject* self, PyObject* args)
+{
+	bitmask_t *mask = PyMask_AsBitmap(self);
+
+	if(!PyArg_ParseTuple(args, ""))
+		return NULL;
+
+	return Py_BuildValue("(ii)", mask->w, mask->h);
+}
+
+static char doc_mask_get_at[] = "Mask.get_at((x,y)) -> int";
+static PyObject* mask_get_at(PyObject* self, PyObject* args)
+{
+	bitmask_t *mask = PyMask_AsBitmap(self);
+        int x, y, val;
+
+	if(!PyArg_ParseTuple(args, "(ii)", &x, &y))
+		return NULL;
+	if (x >= 0 && x < mask->w && y >= 0 && y < mask->h)
+	  val = bitmask_getbit(mask, x, y);
+	else
+	  return NULL;
+
+        return PyInt_FromLong(val);
+}
+
+static char doc_mask_set_at[] = "Mask.set_at((x,y),value)";
+static PyObject* mask_set_at(PyObject* self, PyObject* args)
+{
+	bitmask_t *mask = PyMask_AsBitmap(self);
+        int x, y, value = 1;
+
+	if(!PyArg_ParseTuple(args, "(ii)|i", &x, &y, &value))
+		return NULL;
+	if (x >= 0 && x < mask->w && y >= 0 && y < mask->h)
+	  {
+	    if (value)
+	      bitmask_setbit(mask, x, y);
+	    else
+	      bitmask_clearbit(mask, x, y);
+	  }
+	else
+	  {
+	    return NULL;
+	  }
+	Py_INCREF(Py_None);
+        return Py_None;
+}
+
+static char doc_mask_overlap[] = "Mask.overlap(othermask, offset) -> x,y";
+static PyObject* mask_overlap(PyObject* self, PyObject* args)
+{
+	bitmask_t *mask = PyMask_AsBitmap(self);
+        bitmask_t *othermask;
+        PyObject *maskobj;
+        int x, y, val;
+	int xp,yp;
+
+	if(!PyArg_ParseTuple(args, "O!(ii)", &PyMask_Type, &maskobj, &x, &y))
+		return NULL;
+	othermask = PyMask_AsBitmap(maskobj);
+
+	val = bitmask_overlap_pos(mask, othermask, x, y, &xp, &yp);
+	if (val)
+	  return Py_BuildValue("(ii)", xp,yp);
+	else
+	  {
+	    Py_INCREF(Py_None);
+	    return Py_None;	  
+	  }
+}
+
+
+static char doc_mask_overlap_area[] = "Mask.overlap_area(othermask, offset) -> numpixels";
+static PyObject* mask_overlap_area(PyObject* self, PyObject* args)
+{
+	bitmask_t *mask = PyMask_AsBitmap(self);
+        bitmask_t *othermask;
+        PyObject *maskobj;
+        int x, y, val;
+
+	if(!PyArg_ParseTuple(args, "O!(ii)", &PyMask_Type, &maskobj, &x, &y))
+		return NULL;
+	othermask = PyMask_AsBitmap(maskobj);
+
+	val = bitmask_overlap_area(mask, othermask, x, y);
+        return PyInt_FromLong(val);
+}
+
+static PyMethodDef maskobj_builtins[] =
+{
+	{ "get_size", mask_get_size, METH_VARARGS, doc_mask_get_size },
+	{ "get_at", mask_get_at, METH_VARARGS, doc_mask_get_at },
+	{ "set_at", mask_set_at, METH_VARARGS, doc_mask_set_at },
+	{ "overlap", mask_overlap, METH_VARARGS, doc_mask_overlap },
+	{ "overlap_area", mask_overlap_area, METH_VARARGS, doc_mask_overlap_area },
+
+	{ NULL, NULL }
+};
+
+
+
+/*mask object internals*/
+
+static void mask_dealloc(PyObject* self)
+{
+	bitmask_t *mask = PyMask_AsBitmap(self);
+	bitmask_free(mask);
+	PyObject_DEL(self);
+}
+
+
+static PyObject* mask_getattr(PyObject* self, char* attrname)
+{
+	return Py_FindMethod(maskobj_builtins, self, attrname);
+}
+
+
+static char doc_mask_object[] = "2d bitmask";
+static PyTypeObject PyMask_Type = 
+{
+	PyObject_HEAD_INIT(NULL)
+	0,
+	"Mask",
+	sizeof(PyMaskObject),
+	0,
+	mask_dealloc,	
+	0,
+	mask_getattr,
+	0,
+	0,
+	0,
+	0,
+	NULL,
+	0, 
+	(hashfunc)NULL,
+	(ternaryfunc)NULL,
+	(reprfunc)NULL,
+	0L,0L,0L,0L,
+	doc_mask_object /* Documentation string */
+};
+
+
+
+/*mask module methods*/
+
+static char doc_Mask[] = "mask.Mask((width, height)) -> Mask";
+static PyObject* Mask(PyObject* self, PyObject* args)
+{
+	bitmask_t *mask;
+	int w,h;
+        PyMaskObject *maskobj;
+	if(!PyArg_ParseTuple(args, "(ii)", &w, &h))
+		return NULL;
+        mask = bitmask_create(w,h);
+
+	if(!mask)
+	  return NULL; /*RAISE(PyExc_Error, "cannot create bitmask");*/
+        
+        /*create the new python object from mask*/        
+	maskobj = PyObject_NEW(PyMaskObject, &PyMask_Type);
+        if(maskobj)
+        	maskobj->mask = mask;
+	return (PyObject*)maskobj;
+}
+
+
+
+static PyMethodDef mask_builtins[] =
+{
+	{ "Mask", Mask, 1, doc_Mask },
+
+	{ NULL, NULL }
+};
+
+
+
+
+static char doc_mask_module[] = "wrapper for the bitmask pixel collision library";
+
+void initmask(void)
+{
+  PyObject *module, *dict;
+  PyType_Init(PyMask_Type);
+  
+  /* create the module */
+  module = Py_InitModule3("mask", mask_builtins, doc_mask_module);
+  dict = PyModule_GetDict(module);
+  PyDict_SetItemString(dict, "MaskType", (PyObject *)&PyMask_Type);
+}
+