Thread: [Pen-commits] SF.net SVN: pen:[104] pygame
Brought to you by:
mdgeorge
Menu
▾
▴
pen-commits
|
From: <mdg...@us...> - 2008-12-03 00:45:12
|
Revision: 104
http://pen.svn.sourceforge.net/pen/?rev=104&view=rev
Author: mdgeorge
Date: 2008-12-03 00:45:07 +0000 (Wed, 03 Dec 2008)
Log Message:
-----------
Replacing symlinks.
Removed Paths:
-------------
pygame/src/bitmask.c
pygame/src/bitmask.h
pygame/src/mask.c
pygame/src/mask.doc
pygame/src/pygamedocs.h
pygame/test/mask_test.py
Deleted: pygame/src/bitmask.c
===================================================================
--- pygame/src/bitmask.c 2008-12-01 18:26:50 UTC (rev 103)
+++ pygame/src/bitmask.c 2008-12-03 00:45:07 UTC (rev 104)
@@ -1 +0,0 @@
-link /home/mike/src/pygame/src/bitmask.c
\ No newline at end of file
Deleted: pygame/src/bitmask.h
===================================================================
--- pygame/src/bitmask.h 2008-12-01 18:26:50 UTC (rev 103)
+++ pygame/src/bitmask.h 2008-12-03 00:45:07 UTC (rev 104)
@@ -1 +0,0 @@
-link /home/mike/src/pygame/src/bitmask.h
\ No newline at end of file
Deleted: pygame/src/mask.c
===================================================================
--- pygame/src/mask.c 2008-12-01 18:26:50 UTC (rev 103)
+++ pygame/src/mask.c 2008-12-03 00:45:07 UTC (rev 104)
@@ -1 +0,0 @@
-link /home/mike/src/pygame/src/mask.c
\ No newline at end of file
Deleted: pygame/src/mask.doc
===================================================================
--- pygame/src/mask.doc 2008-12-01 18:26:50 UTC (rev 103)
+++ pygame/src/mask.doc 2008-12-03 00:45:07 UTC (rev 104)
@@ -1 +0,0 @@
-link /home/mike/src/pygame/src/mask.doc
\ No newline at end of file
Deleted: pygame/src/pygamedocs.h
===================================================================
--- pygame/src/pygamedocs.h 2008-12-01 18:26:50 UTC (rev 103)
+++ pygame/src/pygamedocs.h 2008-12-03 00:45:07 UTC (rev 104)
@@ -1 +0,0 @@
-link /home/mike/src/pygame/src/pygamedocs.h
\ No newline at end of file
Deleted: pygame/test/mask_test.py
===================================================================
--- pygame/test/mask_test.py 2008-12-01 18:26:50 UTC (rev 103)
+++ pygame/test/mask_test.py 2008-12-03 00:45:07 UTC (rev 104)
@@ -1 +0,0 @@
-link /home/mike/src/pygame/test/mask_test.py
\ No newline at end of file
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|
|
From: <mdg...@us...> - 2008-12-03 00:46:11
|
Revision: 105
http://pen.svn.sourceforge.net/pen/?rev=105&view=rev
Author: mdgeorge
Date: 2008-12-03 00:46:08 +0000 (Wed, 03 Dec 2008)
Log Message:
-----------
Replacing symlinks with copies.
Added Paths:
-----------
pygame/src/bitmask.c
pygame/src/bitmask.h
pygame/src/mask.c
pygame/src/mask.doc
pygame/src/pygamedocs.h
pygame/test/mask_test.py
Added: pygame/src/bitmask.c
===================================================================
--- pygame/src/bitmask.c (rev 0)
+++ pygame/src/bitmask.c 2008-12-03 00:46:08 UTC (rev 105)
@@ -0,0 +1,1038 @@
+/*
+ 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))
+
+/* 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;
+ }
+}
+
+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 len, shift;
+ BITMASK_W *pixels, cmask, full;
+
+ len = m->h*((m->w - 1)/BITMASK_W_LEN);
+ shift = BITMASK_W_LEN - (m->w % BITMASK_W_LEN);
+ full = ~(BITMASK_W)0;
+ cmask = (~(BITMASK_W)0) >> shift;
+ /* fill all the pixels that aren't in the rightmost BITMASK_Ws */
+ for (pixels = m->bits; pixels < (m->bits + len); pixels++) {
+ *pixels = full;
+ }
+ /* for the rightmost BITMASK_Ws, use cmask to ensure we aren't setting
+ bits that are outside of the mask */
+ for (pixels = m->bits + len; pixels < (m->bits + len + m->h); pixels++) {
+ *pixels = cmask;
+ }
+}
+
+void bitmask_invert(bitmask_t *m)
+{
+ int len, shift;
+ BITMASK_W *pixels, cmask;
+
+ len = m->h*((m->w - 1)/BITMASK_W_LEN);
+ shift = BITMASK_W_LEN - (m->w % BITMASK_W_LEN);
+ cmask = (~(BITMASK_W)0) >> shift;
+ /* flip all the pixels that aren't in the rightmost BITMASK_Ws */
+ for (pixels = m->bits; pixels < (m->bits + len); pixels++) {
+ *pixels = ~(*pixels);
+ }
+ /* for the rightmost BITMASK_Ws, & with cmask to ensure we aren't setting
+ bits that are outside of the mask */
+ for (pixels = m->bits + len; pixels < (m->bits + len + m->h); pixels++) {
+ *pixels = cmask & ~(*pixels);
+ }
+}
+
+unsigned int bitmask_count(bitmask_t *m)
+{
+ BITMASK_W *pixels;
+ unsigned int tot = 0;
+
+ for (pixels=m->bits; pixels<(m->bits+m->h*((m->w-1)/BITMASK_W_LEN + 1)); pixels++) {
+ tot += bitcount(*pixels);
+ }
+
+ return tot;
+}
+
+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;
+ }
+}
+
+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;
+ }
+}
+
+/* Makes a mask of the overlap of two other masks */
+void bitmask_overlap_mask(const bitmask_t *a, const bitmask_t *b, bitmask_t *c, int xoffset, int yoffset)
+{
+ const BITMASK_W *a_entry,*a_end, *ap;
+ const BITMASK_W *b_entry, *b_end, *bp;
+ BITMASK_W *c_entry, *c_end, *cp;
+ 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;
+ c_entry = c->bits + c->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);
+ c_entry = c->bits + c->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,cp = c_entry;ap < a_end;ap++,bp++,cp++)
+ *cp = *ap & (*bp << shift);
+ a_entry += a->h;
+ c_entry += c->h;
+ a_end += a->h;
+ for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
+ *cp = *ap & (*bp >> rshift);
+ b_entry += b->h;
+ }
+ for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
+ *cp = *ap & (*bp << shift);
+ }
+ else /* zig-zag */
+ {
+ for (i=0;i<bstripes;i++)
+ {
+ for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
+ *cp = *ap & (*bp << shift);
+ a_entry += a->h;
+ c_entry += c->h;
+ a_end += a->h;
+ for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
+ *cp = *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,cp = c_entry;ap < a_end;ap++,bp++,cp++)
+ {
+ *cp = *ap & *bp;
+ }
+ a_entry += a->h;
+ c_entry += c->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;
+ c_entry = c->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;
+ c_entry = c->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,cp = c_entry;bp < b_end;bp++,ap++,cp++)
+ *cp = *ap & (*bp >> shift);
+ b_entry += b->h;
+ b_end += b->h;
+ for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
+ *cp = *ap & (*bp <<rshift);
+ a_entry += a->h;
+ c_entry += c->h;
+ }
+ for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
+ *cp = *ap & (*bp >> shift);
+ }
+ else /* zig-zag */
+ {
+ for (i=0;i<bstripes;i++)
+ {
+ for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
+ *cp = *ap & (*bp >> shift);
+ b_entry += b->h;
+ b_end += b->h;
+ for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
+ *cp = *ap & (*bp << rshift);
+ a_entry += a->h;
+ c_entry += c->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,cp = c_entry;bp < b_end;bp++,ap++,cp++)
+ {
+ *cp = *ap & *bp;
+ }
+ b_entry += b->h;
+ b_end += b->h;
+ a_entry += a->h;
+ c_entry += c->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 > c->w)
+ {
+ BITMASK_W edgemask;
+ int n = c->w/BITMASK_W_LEN;
+ shift = (n + 1)*BITMASK_W_LEN - c->w;
+ edgemask = (~(BITMASK_W)0) >> shift;
+ c_end = c->bits + n*c->h + MIN(c->h,b->h + yoffset);
+ for (cp = c->bits + n*c->h + MAX(yoffset,0);cp<c_end;cp++)
+ *cp &= edgemask;
+ }
+}
+
+/* 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;
+}
+
+void bitmask_convolve(const bitmask_t *a, const bitmask_t *b, bitmask_t *o, int xoffset, int yoffset)
+{
+ int x, y;
+
+ xoffset += b->w - 1;
+ yoffset += b->h - 1;
+ for (y = 0; y < b->h; y++)
+ for (x = 0; x < b->w; x++)
+ if (bitmask_getbit(b, x, y))
+ bitmask_draw(o, a, xoffset - x, yoffset - y);
+}
+
+static inline int valid(const bitmask_t *mask, int x, int y)
+{
+ return x < 0 || y < 0 ||
+ x >= mask->w || y >= mask->h ||
+ !bitmask_getbit(mask,x,y);
+}
+
+void bitmask_find_closest(const bitmask_t *mask, int *x, int *y)
+{
+#define SQ(x) (x)*(x)
+
+ /* this method is either very elegant or very ugly. */
+ int best_d = SQ(*x + 1), best_x = -1, best_y = *y;
+ int covered;
+
+#define check_point(dist,x,y) \
+ if(dist < best_d) { \
+ best_d = dist; \
+ best_x = x; \
+ best_y = y; \
+ }
+
+ if (valid(mask, *x, *y))
+ check_point(0, *x, *y);
+
+ /* loop invariant: I've at least looked at everything of distance less than less than covered */
+ for (covered = 1; SQ(covered) <= best_d; covered++)
+ {
+ int sx, sy, i;
+
+#define check_row(xi, yi) \
+ sx = *x - (xi)*covered + (yi)*covered; \
+ sy = *y - (yi)*covered - (xi)*covered; \
+ for (i = 0; i < 2*covered; i++, sx += xi, sy += yi) \
+ if (valid(mask, sx, sy)) \
+ check_point(SQ(*x-sx) + SQ(*y-sy), sx, sy);
+
+ check_row(1,0);
+ check_row(-1,0);
+ check_row(0,1);
+ check_row(0,-1);
+ }
+
+ *x = best_x; *y = best_y;
+}
+
+
Added: pygame/src/bitmask.h
===================================================================
--- pygame/src/bitmask.h (rev 0)
+++ pygame/src/bitmask.h 2008-12-03 00:46:08 UTC (rev 105)
@@ -0,0 +1,149 @@
+/*
+ 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);
+
+/* Flips all bits in the mask */
+void bitmask_invert(bitmask_t *m);
+
+/* Counts the bits in the mask */
+unsigned int bitmask_count(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);
+
+/* Fills a mask with the overlap of two other masks. A bitwise AND. */
+void bitmask_overlap_mask (const bitmask_t *a, const bitmask_t *b, bitmask_t *c, 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);
+
+/* Convolve b into a, drawing the output into o, shifted by offset. If offset
+ * is 0, then the (x,y) bit will be set if and only if
+ * bitmask_overlap(a, b, x - b->w - 1, y - b->h - 1) returns true.
+ *
+ * Modifies bits o[xoffset ... xoffset + a->w + b->w - 1)
+ * [yoffset ... yoffset + a->h + b->h - 1). */
+void bitmask_convolve(const bitmask_t *a, const bitmask_t *b, bitmask_t *o, int xoffset, int yoffset);
+
+/* Find the closest point to (x,y) with mask[x,y] not set */
+void bitmask_find_closest(const bitmask_t *mask, int * x, int * y);
+
+#ifdef __cplusplus
+} /* End of extern "C" { */
+#endif
+
+#endif
Added: pygame/src/mask.c
===================================================================
--- pygame/src/mask.c (rev 0)
+++ pygame/src/mask.c 2008-12-03 00:46:08 UTC (rev 105)
@@ -0,0 +1,1432 @@
+/*
+ Copyright (C) 2002-2007 Ulf Ekstrom except for the bitcount function.
+ 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 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
+
+*/
+
+/* a couple of print debugging helpers */
+/*
+#define CALLLOG2(x,y) fprintf(stderr, (x), (y));
+#define CALLLOG(x) fprintf(stderr, (x));
+*/
+
+#include "pygame.h"
+#include "pygamedocs.h"
+#include "structmember.h"
+#include "bitmask.h"
+#include <math.h>
+
+#ifndef M_PI
+#define M_PI 3.14159265358979323846
+#endif
+
+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)
+
+
+/* mask object methods */
+
+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 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 {
+ PyErr_Format(PyExc_IndexError, "%d, %d is out of bounds", x, y);
+ return NULL;
+ }
+
+ return PyInt_FromLong(val);
+}
+
+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 {
+ PyErr_Format(PyExc_IndexError, "%d, %d is out of bounds", x, y);
+ return NULL;
+ }
+ Py_INCREF(Py_None);
+ return Py_None;
+}
+
+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 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 PyObject* mask_overlap_mask(PyObject* self, PyObject* args)
+{
+ int x, y;
+ bitmask_t *mask = PyMask_AsBitmap(self);
+ bitmask_t *output = bitmask_create(mask->w, mask->h);
+ bitmask_t *othermask;
+ PyObject *maskobj;
+ PyMaskObject *maskobj2 = PyObject_New(PyMaskObject, &PyMask_Type);
+
+ if(!PyArg_ParseTuple(args, "O!(ii)", &PyMask_Type, &maskobj, &x, &y)) {
+ return NULL;
+ }
+ othermask = PyMask_AsBitmap(maskobj);
+
+ bitmask_overlap_mask(mask, othermask, output, x, y);
+
+ if(maskobj2)
+ maskobj2->mask = output;
+
+ return (PyObject*)maskobj2;
+}
+
+static PyObject* mask_fill(PyObject* self, PyObject* args)
+{
+ bitmask_t *mask = PyMask_AsBitmap(self);
+
+ bitmask_fill(mask);
+
+ Py_RETURN_NONE;
+}
+
+static PyObject* mask_clear(PyObject* self, PyObject* args)
+{
+ bitmask_t *mask = PyMask_AsBitmap(self);
+
+ bitmask_clear(mask);
+
+ Py_RETURN_NONE;
+}
+
+static PyObject* mask_invert(PyObject* self, PyObject* args)
+{
+ bitmask_t *mask = PyMask_AsBitmap(self);
+
+ bitmask_invert(mask);
+
+ Py_RETURN_NONE;
+}
+
+static PyObject* mask_scale(PyObject* self, PyObject* args)
+{
+ int x, y;
+ bitmask_t *input = PyMask_AsBitmap(self);
+ bitmask_t *output;
+ PyMaskObject *maskobj = PyObject_New(PyMaskObject, &PyMask_Type);
+
+ if(!PyArg_ParseTuple(args, "(ii)", &x, &y)) {
+ return NULL;
+ }
+
+ output = bitmask_scale(input, x, y);
+
+ if(maskobj)
+ maskobj->mask = output;
+
+ return (PyObject*)maskobj;
+}
+
+static PyObject* mask_draw(PyObject* self, PyObject* args)
+{
+ bitmask_t *mask = PyMask_AsBitmap(self);
+ bitmask_t *othermask;
+ PyObject *maskobj;
+ int x, y;
+
+ if(!PyArg_ParseTuple(args, "O!(ii)", &PyMask_Type, &maskobj, &x, &y)) {
+ return NULL;
+ }
+ othermask = PyMask_AsBitmap(maskobj);
+
+ bitmask_draw(mask, othermask, x, y);
+
+ Py_RETURN_NONE;
+}
+
+static PyObject* mask_erase(PyObject* self, PyObject* args)
+{
+ bitmask_t *mask = PyMask_AsBitmap(self);
+ bitmask_t *othermask;
+ PyObject *maskobj;
+ int x, y;
+
+ if(!PyArg_ParseTuple(args, "O!(ii)", &PyMask_Type, &maskobj, &x, &y)) {
+ return NULL;
+ }
+ othermask = PyMask_AsBitmap(maskobj);
+
+ bitmask_erase(mask, othermask, x, y);
+
+ Py_RETURN_NONE;
+}
+
+static PyObject* mask_count(PyObject* self, PyObject* args)
+{
+ bitmask_t *m = PyMask_AsBitmap(self);
+
+ return PyInt_FromLong(bitmask_count(m));
+}
+
+static PyObject* mask_centroid(PyObject* self, PyObject* args)
+{
+ bitmask_t *mask = PyMask_AsBitmap(self);
+ int x, y;
+ long int m10, m01, m00;
+ PyObject *xobj, *yobj;
+
+ m10 = m01 = m00 = 0;
+
+ for (x = 0; x < mask->w; x++) {
+ for (y = 0; y < mask->h; y++) {
+ if (bitmask_getbit(mask, x, y)) {
+ m10 += x;
+ m01 += y;
+ m00++;
+ }
+ }
+ }
+
+ if (m00) {
+ xobj = PyInt_FromLong(m10/m00);
+ yobj = PyInt_FromLong(m01/m00);
+ } else {
+ xobj = PyInt_FromLong(0);
+ yobj = PyInt_FromLong(0);
+ }
+
+ return Py_BuildValue("(NN)", xobj, yobj);
+}
+
+static PyObject* mask_angle(PyObject* self, PyObject* args)
+{
+ bitmask_t *mask = PyMask_AsBitmap(self);
+ int x, y, xc, yc;
+ long int m10, m01, m00, m20, m02, m11;
+ double theta;
+
+ m10 = m01 = m00 = m20 = m02 = m11 = 0;
+
+ for (x = 0; x < mask->w; x++) {
+ for (y = 0; y < mask->h; y++) {
+ if (bitmask_getbit(mask, x, y)) {
+ m10 += x;
+ m20 += x*x;
+ m11 += x*y;
+ m02 += y*y;
+ m01 += y;
+ m00++;
+ }
+ }
+ }
+
+ if (m00) {
+ xc = m10/m00;
+ yc = m01/m00;
+ theta = -90.0*atan2(2*(m11/m00 - xc*yc),(m20/m00 - xc*xc)-(m02/m00 - yc*yc))/M_PI;
+ return PyFloat_FromDouble(theta);
+ } else {
+ return PyFloat_FromDouble(0);
+ }
+}
+
+static PyObject* mask_outline(PyObject* self, PyObject* args)
+{
+ bitmask_t* c = PyMask_AsBitmap(self);
+ bitmask_t* m = bitmask_create(c->w + 2, c->h + 2);
+ PyObject *plist, *value;
+ int x, y, every, e, firstx, firsty, secx, secy, currx, curry, nextx, nexty, n;
+ int a[14], b[14];
+ a[0] = a[1] = a[7] = a[8] = a[9] = b[1] = b[2] = b[3] = b[9] = b[10] = b[11]= 1;
+ a[2] = a[6] = a[10] = b[4] = b[0] = b[12] = b[8] = 0;
+ a[3] = a[4] = a[5] = a[11] = a[12] = a[13] = b[5] = b[6] = b[7] = b[13] = -1;
+
+ plist = NULL;
+ plist = PyList_New (0);
+ if (!plist)
+ return NULL;
+
+ every = 1;
+ n = firstx = firsty = secx = x = 0;
+
+ if(!PyArg_ParseTuple(args, "|i", &every)) {
+ return NULL;
+ }
+
+ /* by copying to a new, larger mask, we avoid having to check if we are at
+ a border pixel every time. */
+ bitmask_draw(m, c, 1, 1);
+
+ e = every;
+
+ /* find the first set pixel in the mask */
+ for (y = 1; y < m->h-1; y++) {
+ for (x = 1; x < m->w-1; x++) {
+ if (bitmask_getbit(m, x, y)) {
+ firstx = x;
+ firsty = y;
+ value = Py_BuildValue("(ii)", x-1, y-1);
+ PyList_Append(plist, value);
+ Py_DECREF(value);
+ break;
+ }
+ }
+ if (bitmask_getbit(m, x, y))
+ break;
+ }
+
+
+
+ /* covers the mask having zero pixels or only the final pixel */
+ if ((x == m->w-1) && (y == m->h-1)) {
+ bitmask_free(m);
+ return plist;
+ }
+
+ /* check just the first pixel for neighbors */
+ for (n = 0;n < 8;n++) {
+ if (bitmask_getbit(m, x+a[n], y+b[n])) {
+ currx = secx = x+a[n];
+ curry = secy = y+b[n];
+ e--;
+ if (!e) {
+ e = every;
+ value = Py_BuildValue("(ii)", secx-1, secy-1);
+ PyList_Append(plist, value);
+ Py_DECREF(value);
+ }
+ break;
+ }
+ }
+
+ /* if there are no neighbors, return */
+ if (!secx) {
+ bitmask_free(m);
+ return plist;
+ }
+
+ /* the outline tracing loop */
+ for (;;) {
+ /* look around the pixel, it has to have a neighbor */
+ for (n = (n + 6) & 7;;n++) {
+ if (bitmask_getbit(m, currx+a[n], curry+b[n])) {
+ nextx = currx+a[n];
+ nexty = curry+b[n];
+ e--;
+ if (!e) {
+ e = every;
+ if ((curry == firsty && currx == firstx) && (secx == nextx && secy == nexty)) {
+ break;
+ }
+ value = Py_BuildValue("(ii)", nextx-1, nexty-1);
+ PyList_Append(plist, value);
+ Py_DECREF(value);
+ }
+ break;
+ }
+ }
+ /* if we are back at the first pixel, and the next one will be the
+ second one we visited, we are done */
+ if ((curry == firsty && currx == firstx) && (secx == nextx && secy == nexty)) {
+ break;
+ }
+
+ curry = nexty;
+ currx = nextx;
+ }
+
+ bitmask_free(m);
+
+ return plist;
+}
+
+static PyObject* mask_convolve(PyObject* aobj, PyObject* args)
+{
+ PyObject *bobj, *oobj = Py_None;
+ bitmask_t *a, *b, *o;
+ int xoffset = 0, yoffset = 0;
+
+ if (!PyArg_ParseTuple (args, "O!|O(ii)", &PyMask_Type, &bobj, &oobj, &xoffset, &yoffset))
+ return NULL;
+
+ a = PyMask_AsBitmap(aobj);
+ b = PyMask_AsBitmap(bobj);
+
+ if (oobj == Py_None) {
+ PyMaskObject *result = PyObject_New(PyMaskObject, &PyMask_Type);
+
+ result->mask = bitmask_create(a->w + b->w - 1, a->h + b->h - 1);
+ oobj = (PyObject*) result;
+ }
+ else
+ Py_INCREF(oobj);
+
+ o = PyMask_AsBitmap(oobj);
+
+ bitmask_convolve(a, b, o, xoffset, yoffset);
+ return oobj;
+}
+
+static PyObject * mask_find_closest(PyObject* self, PyObject* args)
+{
+ bitmask_t * mask = PyMask_AsBitmap(self);
+ int x, y;
+
+ if (!PyArg_ParseTuple(args, "(ii)", &x, &y))
+ return NULL;
+
+ bitmask_find_closest(mask, &x, &y);
+
+ return Py_BuildValue("(ii)", x, y);
+}
+
+static PyObject* mask_from_surface(PyObject* self, PyObject* args)
+{
+ bitmask_t *mask;
+ SDL_Surface* surf;
+
+ PyObject* surfobj;
+ PyMaskObject *maskobj;
+
+ int x, y, threshold, ashift, aloss, usethresh;
+ Uint8 *pixels;
+
+ SDL_PixelFormat *format;
+ Uint32 color, amask;
+ Uint8 *pix;
+ Uint8 a;
+
+ /* set threshold as 127 default argument. */
+ threshold = 127;
+
+ /* get the surface from the passed in arguments.
+ * surface, threshold
+ */
+
+ if (!PyArg_ParseTuple (args, "O!|i", &PySurface_Type, &surfobj, &threshold)) {
+ return NULL;
+ }
+
+ surf = PySurface_AsSurface(surfobj);
+
+ /* lock the surface, release the GIL. */
+ PySurface_Lock (surfobj);
+
+ Py_BEGIN_ALLOW_THREADS;
+
+ /* get the size from the surface, and create the mask. */
+ mask = bitmask_create(surf->w, surf->h);
+
+
+ if(!mask) {
+ /* Py_END_ALLOW_THREADS;
+ */
+ return NULL; /*RAISE(PyExc_Error, "cannot create bitmask");*/
+ }
+
+ pixels = (Uint8 *) surf->pixels;
+ format = surf->format;
+ amask = format->Amask;
+ ashift = format->Ashift;
+ aloss = format->Aloss;
+ usethresh = !(surf->flags & SDL_SRCCOLORKEY);
+
+ for(y=0; y < surf->h; y++) {
+ pixels = (Uint8 *) surf->pixels + y*surf->pitch;
+ for(x=0; x < surf->w; x++) {
+ /* Get the color. TODO: should use an inline helper
+ * function for this common function. */
+ switch (format->BytesPerPixel)
+ {
+ case 1:
+ color = (Uint32)*((Uint8 *) pixels);
+ pixels++;
+ break;
+ case 2:
+ color = (Uint32)*((Uint16 *) pixels);
+ pixels += 2;
+ break;
+ case 3:
+ pix = ((Uint8 *) pixels);
+ pixels += 3;
+ #if SDL_BYTEORDER == SDL_LIL_ENDIAN
+ color = (pix[0]) + (pix[1] << 8) + (pix[2] << 16);
+ #else
+ color = (pix[2]) + (pix[1] << 8) + (pix[0] << 16);
+ #endif
+ break;
+ default: /* case 4: */
+ color = *((Uint32 *) pixels);
+ pixels += 4;
+ break;
+ }
+
+
+ if (usethresh) {
+ a = ((color & amask) >> ashift) << aloss;
+ /* no colorkey, so we check the threshold of the alpha */
+ if (a > threshold) {
+ bitmask_setbit(mask, x, y);
+ }
+ } else {
+ /* test against the colour key. */
+ if (format->colorkey != color) {
+ bitmask_setbit(mask, x, y);
+ }
+ }
+ }
+ }
+
+ Py_END_ALLOW_THREADS;
+
+ /* unlock the surface, release the GIL.
+ */
+ PySurface_Unlock (surfobj);
+
+ /*create the new python object from mask*/
+ maskobj = PyObject_New(PyMaskObject, &PyMask_Type);
+ if(maskobj)
+ maskobj->mask = mask;
+
+
+ return (PyObject*)maskobj;
+}
+
+void bitmask_threshold (bitmask_t *m, SDL_Surface *surf, SDL_Surface *surf2,
+ Uint32 color, Uint32 threshold)
+{
+ int x, y, rshift, gshift, bshift, rshift2, gshift2, bshift2;
+ int rloss, gloss, bloss, rloss2, gloss2, bloss2;
+ Uint8 *pixels, *pixels2;
+ SDL_PixelFormat *format, *format2;
+ Uint32 the_color, the_color2, rmask, gmask, bmask, rmask2, gmask2, bmask2;
+ Uint8 *pix;
+ Uint8 r, g, b, a;
+ Uint8 tr, tg, tb, ta;
+
+ pixels = (Uint8 *) surf->pixels;
+ format = surf->format;
+ rmask = format->Rmask;
+ gmask = format->Gmask;
+ bmask = format->Bmask;
+ rshift = format->Rshift;
+ gshift = format->Gshift;
+ bshift = format->Bshift;
+ rloss = format->Rloss;
+ gloss = format->Gloss;
+ bloss = format->Bloss;
+
+ if(surf2) {
+ format2 = surf2->format;
+ rmask2 = format2->Rmask;
+ gmask2 = format2->Gmask;
+ bmask2 = format2->Bmask;
+ rshift2 = format2->Rshift;
+ gshift2 = format2->Gshift;
+ bshift2 = format2->Bshift;
+ rloss2 = format2->Rloss;
+ gloss2 = format2->Gloss;
+ bloss2 = format2->Bloss;
+ pixels2 = (Uint8 *) surf2->pixels;
+ } else { /* make gcc stop complaining */
+ rmask2 = gmask2 = bmask2 = 0;
+ rshift2 = gshift2 = bshift2 = 0;
+ rloss2 = gloss2 = bloss2 = 0;
+ format2 = NULL;
+ pixels2 = NULL;
+ }
+
+ SDL_GetRGBA (color, format, &r, &g, &b, &a);
+ SDL_GetRGBA (threshold, format, &tr, &tg, &tb, &ta);
+
+ for(y=0; y < surf->h; y++) {
+ pixels = (Uint8 *) surf->pixels + y*surf->pitch;
+ if (surf2) {
+ pixels2 = (Uint8 *) surf2->pixels + y*surf2->pitch;
+ }
+ for(x=0; x < surf->w; x++) {
+ /* the_color = surf->get_at(x,y) */
+ switch (format->BytesPerPixel)
+ {
+ case 1:
+ the_color = (Uint32)*((Uint8 *) pixels);
+ pixels++;
+ break;
+ case 2:
+ the_color = (Uint32)*((Uint16 *) pixels);
+ pixels += 2;
+ break;
+ case 3:
+ pix = ((Uint8 *) pixels);
+ pixels += 3;
+#if SDL_BYTEORDER == SDL_LIL_ENDIAN
+ the_color = (pix[0]) + (pix[1] << 8) + (pix[2] << 16);
+#else
+ the_color = (pix[2]) + (pix[1] << 8) + (pix[0] << 16);
+#endif
+ break;
+ default: /* case 4: */
+ the_color = *((Uint32 *) pixels);
+ pixels += 4;
+ break;
+ }
+
+ if (surf2) {
+ switch (format2->BytesPerPixel) {
+ case 1:
+ the_color2 = (Uint32)*((Uint8 *) pixels2);
+ pixels2++;
+ break;
+ case 2:
+ the_color2 = (Uint32)*((Uint16 *) pixels2);
+ pixels2 += 2;
+ break;
+ case 3:
+ pix = ((Uint8 *) pixels2);
+ pixels2 += 3;
+#if SDL_BYTEORDER == SDL_LIL_ENDIAN
+ the_color2 = (pix[0]) + (pix[1] << 8) + (pix[2] << 16);
+#else
+ the_color2 = (pix[2]) + (pix[1] << 8) + (pix[0] << 16);
+#endif
+ break;
+ default: /* case 4: */
+ the_color2 = *((Uint32 *) pixels2);
+ pixels2 += 4;
+ break;
+ }
+ if ((abs((((the_color2 & rmask2) >> rshift2) << rloss2) - (((the_color & rmask) >> rshift) << rloss)) < tr) &
+ (abs((((the_color2 & gmask2) >> gshift2) << gloss2) - (((the_color & gmask) >> gshift) << gloss)) < tg) &
+ (abs((((the_color2 & bmask2) >> bshift2) << bloss2) - (((the_color & bmask) >> bshift) << bloss)) < tb)) {
+ /* this pixel is within the threshold of othersurface. */
+ bitmask_setbit(m, x, y);
+ }
+ } else if ((abs((((the_color & rmask) >> rshift) << rloss) - r) < tr) &
+ (abs((((the_color & gmask) >> gshift) << gloss) - g) < tg) &
+ (abs((((the_color & bmask) >> bshift) << bloss) - b) < tb)) {
+ /* this pixel is within the threshold of the color. */
+ bitmask_setbit(m, x, y);
+ }
+ }
+ }
+}
+
+static PyObject* mask_from_threshold(PyObject* self, PyObject* args)
+{
+ PyObject *surfobj, *surfobj2;
+ PyMaskObject *maskobj;
+ bitmask_t* m;
+ SDL_Surface* surf, *surf2;
+ int bpp;
+ PyObject *rgba_obj_color, *rgba_obj_threshold;
+ Uint8 rgba_color[4];
+ Uint8 rgba_threshold[4];
+ Uint32 color;
+ Uint32 color_threshold;
+
+ surf2 = surf = NULL;
+ surfobj2 = NULL;
+ rgba_obj_threshold = NULL;
+ rgba_threshold[0] = 0; rgba_threshold[1] = 0; rgba_threshold[2] = 0; rgba_threshold[4] = 255;
+
+ if (!PyArg_ParseTuple (args, "O!O|OO!", &PySurface_Type, &surfobj,
+ &rgba_obj_color, &rgba_obj_threshold,
+ &PySurface_Type, &surfobj2))
+ return NULL;
+
+ surf = PySurface_AsSurface (surfobj);
+ if(surfobj2) {
+ surf2 = PySurface_AsSurface (surfobj2);
+ }
+
+ if (PyInt_Check (rgba_obj_color)) {
+ color = (Uint32) PyInt_AsLong (rgba_obj_color);
+ } else if (PyLong_Check (rgba_obj_color)) {
+ color = (Uint32) PyLong_AsUnsignedLong (rgba_obj_color);
+ } else if (RGBAFromColorObj (rgba_obj_color, rgba_color)) {
+ color = SDL_MapRGBA (surf->format, rgba_color[0], rgba_color[1],
+ rgba_color[2], rgba_color[3]);
+ } else {
+ return RAISE (PyExc_TypeError, "invalid color argument");
+ }
+
+ if(rgba_obj_threshold) {
+ if (PyInt_Check (rgba_obj_threshold))
+ color_threshold = (Uint32) PyInt_AsLong (rgba_obj_threshold);
+ else if (PyLong_Check (rgba_obj_threshold))
+ color_threshold = (Uint32) PyLong_AsUnsignedLong
+ (rgba_obj_threshold);
+ else if (RGBAFromColorObj (rgba_obj_threshold, rgba_threshold))
+ color_threshold = SDL_MapRGBA (surf->format, rgba_threshold[0], rgba_threshold[1], rgba_threshold[2], rgba_threshold[3]);
+ else
+ return RAISE (PyExc_TypeError, "invalid threshold argument");
+ } else {
+ color_threshold = SDL_MapRGBA (surf->format, rgba_threshold[0], rgba_threshold[1], rgba_threshold[2], rgba_threshold[3]);
+ }
+
+ bpp = surf->format->BytesPerPixel;
+ m = bitmask_create(surf->w, surf->h);
+
+ PySurface_Lock(surfobj);
+ if(surfobj2) {
+ PySurface_Lock(surfobj2);
+ }
+
+ Py_BEGIN_ALLOW_THREADS;
+ bitmask_threshold (m, surf, surf2, color, color_threshold);
+ Py_END_ALLOW_THREADS;
+
+ PySurface_Unlock(surfobj);
+ if(surfobj2) {
+ PySurface_Unlock(surfobj2);
+ }
+
+ maskobj = PyObject_New(PyMaskObject, &PyMask_Type);
+ if(maskobj)
+ maskobj->mask = m;
+
+ return (PyObject*)maskobj;
+}
+
+
+
+
+/* the initial labelling phase of the connected components algorithm
+
+Returns: The highest label in the labelled image
+
+input - The input Mask
+image - An array to store labelled pixels
+ufind - The union-find label equivalence array
+largest - An array to store the number of pixels for each label
+
+*/
+unsigned int cc_label(bitmask_t *input, unsigned int* image, unsigned int* ufind, unsigned int* largest) {
+ unsigned int *buf;
+ unsigned int x, y, w, h, root, aroot, croot, temp, label;
+
+ label = 0;
+ w = input->w;
+ h = input->h;
+
+ ufind[0] = 0;
+ buf = image;
+
+ /* special case for first pixel */
+ if(bitmask_getbit(input, 0, 0)) { /* process for a new connected comp: */
+ label++; /* create a new label */
+ *buf = label; /* give the pixel the label */
+ ufind[label] = label; /* put the label in the equivalence array */
+ largest[label] = 1; /* the label has 1 pixel associated with it */
+ } else {
+ *buf = 0;
+ }
+ buf++;
+
+
+
+ /* special case for first row.
+ Go over the first row except the first pixel.
+ */
+ for(x = 1; x < w; x++) {
+ if (bitmask_getbit(input, x, 0)) {
+ if (*(buf-1)) { /* d label */
+ *buf = *(buf-1);
+ } else { /* create label */
+ label++;
+ *buf = label;
+ ufind[label] = label;
+ largest[label] = 0;
+ }
+ largest[*buf]++;
+ } else {
+ *buf = 0;
+ }
+ buf++;
+ }
+
+
+
+ /* the rest of the image */
+ for(y = 1; y < h; y++) {
+ /* first pixel of the row */
+ if (bitmask_getbit(input, 0, y)) {
+ if (*(buf-w)) { /* b label */
+ *buf = *(buf-w);
+ } else if (*(buf-w+1)) { /* c label */
+ *buf = *(buf-w+1);
+ } else { /* create label */
+ label++;
+ *buf = label;
+ ufind[label] = label;
+ largest[label] = 0;
+ }
+ largest[*buf]++;
+ } else {
+ *buf = 0;
+ }
+ buf++;
+ /* middle pixels of the row */
+ for(x = 1; x < (w-1); x++) {
+ if (bitmask_getbit(input, x, y)) {
+ if (*(buf-w)) { /* b label */
+ *buf = *(buf-w);
+ } else if (*(buf-w+1)) { /* c branch of tree */
+ if (*(buf-w-1)) { /* union(c, a) */
+ croot = root = *(buf-w+1);
+ while (ufind[root] < root) { /* find root */
+ root = ufind[root];
+ }
+ if (croot != *(buf-w-1)) {
+ temp = aroot = *(buf-w-1);
+ while (ufind[aroot] < aroot) { /* find root */
+ aroot = ufind[aroot];
+ ...
[truncated message content] |
|
From: <mdg...@us...> - 2008-12-03 03:09:52
|
Revision: 110
http://pen.svn.sourceforge.net/pen/?rev=110&view=rev
Author: mdgeorge
Date: 2008-12-03 03:09:49 +0000 (Wed, 03 Dec 2008)
Log Message:
-----------
Replaced my old pygame patch (which add custom functionality that has been
moved into maskutils in src/) with my new pygame patch (which adds a C API
object to the mask module).
Modified Paths:
--------------
pygame/src/mask.c
Added Paths:
-----------
pygame/src/mask.h
Removed Paths:
-------------
pygame/src/bitmask.c
pygame/src/bitmask.h
pygame/src/mask.doc
pygame/src/pygamedocs.h
pygame/test/
Deleted: pygame/src/bitmask.c
===================================================================
--- pygame/src/bitmask.c 2008-12-03 03:00:27 UTC (rev 109)
+++ pygame/src/bitmask.c 2008-12-03 03:09:49 UTC (rev 110)
@@ -1,1038 +0,0 @@
-/*
- 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))
-
-/* 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;
- }
-}
-
-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 len, shift;
- BITMASK_W *pixels, cmask, full;
-
- len = m->h*((m->w - 1)/BITMASK_W_LEN);
- shift = BITMASK_W_LEN - (m->w % BITMASK_W_LEN);
- full = ~(BITMASK_W)0;
- cmask = (~(BITMASK_W)0) >> shift;
- /* fill all the pixels that aren't in the rightmost BITMASK_Ws */
- for (pixels = m->bits; pixels < (m->bits + len); pixels++) {
- *pixels = full;
- }
- /* for the rightmost BITMASK_Ws, use cmask to ensure we aren't setting
- bits that are outside of the mask */
- for (pixels = m->bits + len; pixels < (m->bits + len + m->h); pixels++) {
- *pixels = cmask;
- }
-}
-
-void bitmask_invert(bitmask_t *m)
-{
- int len, shift;
- BITMASK_W *pixels, cmask;
-
- len = m->h*((m->w - 1)/BITMASK_W_LEN);
- shift = BITMASK_W_LEN - (m->w % BITMASK_W_LEN);
- cmask = (~(BITMASK_W)0) >> shift;
- /* flip all the pixels that aren't in the rightmost BITMASK_Ws */
- for (pixels = m->bits; pixels < (m->bits + len); pixels++) {
- *pixels = ~(*pixels);
- }
- /* for the rightmost BITMASK_Ws, & with cmask to ensure we aren't setting
- bits that are outside of the mask */
- for (pixels = m->bits + len; pixels < (m->bits + len + m->h); pixels++) {
- *pixels = cmask & ~(*pixels);
- }
-}
-
-unsigned int bitmask_count(bitmask_t *m)
-{
- BITMASK_W *pixels;
- unsigned int tot = 0;
-
- for (pixels=m->bits; pixels<(m->bits+m->h*((m->w-1)/BITMASK_W_LEN + 1)); pixels++) {
- tot += bitcount(*pixels);
- }
-
- return tot;
-}
-
-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;
- }
-}
-
-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;
- }
-}
-
-/* Makes a mask of the overlap of two other masks */
-void bitmask_overlap_mask(const bitmask_t *a, const bitmask_t *b, bitmask_t *c, int xoffset, int yoffset)
-{
- const BITMASK_W *a_entry,*a_end, *ap;
- const BITMASK_W *b_entry, *b_end, *bp;
- BITMASK_W *c_entry, *c_end, *cp;
- 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;
- c_entry = c->bits + c->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);
- c_entry = c->bits + c->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,cp = c_entry;ap < a_end;ap++,bp++,cp++)
- *cp = *ap & (*bp << shift);
- a_entry += a->h;
- c_entry += c->h;
- a_end += a->h;
- for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
- *cp = *ap & (*bp >> rshift);
- b_entry += b->h;
- }
- for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
- *cp = *ap & (*bp << shift);
- }
- else /* zig-zag */
- {
- for (i=0;i<bstripes;i++)
- {
- for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
- *cp = *ap & (*bp << shift);
- a_entry += a->h;
- c_entry += c->h;
- a_end += a->h;
- for (ap = a_entry,bp = b_entry,cp = c_entry;ap < a_end;ap++,bp++,cp++)
- *cp = *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,cp = c_entry;ap < a_end;ap++,bp++,cp++)
- {
- *cp = *ap & *bp;
- }
- a_entry += a->h;
- c_entry += c->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;
- c_entry = c->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;
- c_entry = c->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,cp = c_entry;bp < b_end;bp++,ap++,cp++)
- *cp = *ap & (*bp >> shift);
- b_entry += b->h;
- b_end += b->h;
- for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
- *cp = *ap & (*bp <<rshift);
- a_entry += a->h;
- c_entry += c->h;
- }
- for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
- *cp = *ap & (*bp >> shift);
- }
- else /* zig-zag */
- {
- for (i=0;i<bstripes;i++)
- {
- for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
- *cp = *ap & (*bp >> shift);
- b_entry += b->h;
- b_end += b->h;
- for (bp = b_entry,ap = a_entry,cp = c_entry;bp < b_end;bp++,ap++,cp++)
- *cp = *ap & (*bp << rshift);
- a_entry += a->h;
- c_entry += c->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,cp = c_entry;bp < b_end;bp++,ap++,cp++)
- {
- *cp = *ap & *bp;
- }
- b_entry += b->h;
- b_end += b->h;
- a_entry += a->h;
- c_entry += c->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 > c->w)
- {
- BITMASK_W edgemask;
- int n = c->w/BITMASK_W_LEN;
- shift = (n + 1)*BITMASK_W_LEN - c->w;
- edgemask = (~(BITMASK_W)0) >> shift;
- c_end = c->bits + n*c->h + MIN(c->h,b->h + yoffset);
- for (cp = c->bits + n*c->h + MAX(yoffset,0);cp<c_end;cp++)
- *cp &= edgemask;
- }
-}
-
-/* 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;
-}
-
-void bitmask_convolve(const bitmask_t *a, const bitmask_t *b, bitmask_t *o, int xoffset, int yoffset)
-{
- int x, y;
-
- xoffset += b->w - 1;
- yoffset += b->h - 1;
- for (y = 0; y < b->h; y++)
- for (x = 0; x < b->w; x++)
- if (bitmask_getbit(b, x, y))
- bitmask_draw(o, a, xoffset - x, yoffset - y);
-}
-
-static inline int valid(const bitmask_t *mask, int x, int y)
-{
- return x < 0 || y < 0 ||
- x >= mask->w || y >= mask->h ||
- !bitmask_getbit(mask,x,y);
-}
-
-void bitmask_find_closest(const bitmask_t *mask, int *x, int *y)
-{
-#define SQ(x) (x)*(x)
-
- /* this method is either very elegant or very ugly. */
- int best_d = SQ(*x + 1), best_x = -1, best_y = *y;
- int covered;
-
-#define check_point(dist,x,y) \
- if(dist < best_d) { \
- best_d = dist; \
- best_x = x; \
- best_y = y; \
- }
-
- if (valid(mask, *x, *y))
- check_point(0, *x, *y);
-
- /* loop invariant: I've at least looked at everything of distance less than less than covered */
- for (covered = 1; SQ(covered) <= best_d; covered++)
- {
- int sx, sy, i;
-
-#define check_row(xi, yi) \
- sx = *x - (xi)*covered + (yi)*covered; \
- sy = *y - (yi)*covered - (xi)*covered; \
- for (i = 0; i < 2*covered; i++, sx += xi, sy += yi) \
- if (valid(mask, sx, sy)) \
- check_point(SQ(*x-sx) + SQ(*y-sy), sx, sy);
-
- check_row(1,0);
- check_row(-1,0);
- check_row(0,1);
- check_row(0,-1);
- }
-
- *x = best_x; *y = best_y;
-}
-
-
Deleted: pygame/src/bitmask.h
===================================================================
--- pygame/src/bitmask.h 2008-12-03 03:00:27 UTC (rev 109)
+++ pygame/src/bitmask.h 2008-12-03 03:09:49 UTC (rev 110)
@@ -1,149 +0,0 @@
-/*
- 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);
-
-/* Flips all bits in the mask */
-void bitmask_invert(bitmask_t *m);
-
-/* Counts the bits in the mask */
-unsigned int bitmask_count(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);
-
-/* Fills a mask with the overlap of two other masks. A bitwise AND. */
-void bitmask_overlap_mask (const bitmask_t *a, const bitmask_t *b, bitmask_t *c, 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);
-
-/* Convolve b into a, drawing the output into o, shifted by offset. If offset
- * is 0, then the (x,y) bit will be set if and only if
- * bitmask_overlap(a, b, x - b->w - 1, y - b->h - 1) returns true.
- *
- * Modifies bits o[xoffset ... xoffset + a->w + b->w - 1)
- * [yoffset ... yoffset + a->h + b->h - 1). */
-void bitmask_convolve(const bitmask_t *a, const bitmask_t *b, bitmask_t *o, int xoffset, int yoffset);
-
-/* Find the closest point to (x,y) with mask[x,y] not set */
-void bitmask_find_closest(const bitmask_t *mask, int * x, int * y);
-
-#ifdef __cplusplus
-} /* End of extern "C" { */
-#endif
-
-#endif
Modified: pygame/src/mask.c
===================================================================
--- pygame/src/mask.c 2008-12-03 03:00:27 UTC (rev 109)
+++ pygame/src/mask.c 2008-12-03 03:09:49 UTC (rev 110)
@@ -26,6 +26,8 @@
#define CALLLOG(x) fprintf(stderr, (x));
*/
+#define PYGAMEAPI_MASK_INTERNAL 1
+#include "mask.h"
#include "pygame.h"
#include "pygamedocs.h"
#include "structmember.h"
@@ -36,16 +38,8 @@
#define M_PI 3.14159265358979323846
#endif
-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)
-
/* mask object methods */
static PyObject* mask_get_size(PyObject* self, PyObject* args)
@@ -379,7 +373,7 @@
bitmask_free(m);
return plist;
}
-
+
/* the outline tracing loop */
for (;;) {
/* look around the pixel, it has to have a neighbor */
@@ -395,11 +389,11 @@
}
value = Py_BuildValue("(ii)", nextx-1, nexty-1);
PyList_Append(plist, value);
- Py_DECREF(value);
+ Py_DECREF(value);
}
break;
}
- }
+ }
/* if we are back at the first pixel, and the next one will be the
second one we visited, we are done */
if ((curry == firsty && currx == firstx) && (secx == nextx && secy == nexty)) {
@@ -409,52 +403,12 @@
curry = nexty;
currx = nextx;
}
-
+
bitmask_free(m);
-
+
return plist;
}
-static PyObject* mask_convolve(PyObject* aobj, PyObject* args)
-{
- PyObject *bobj, *oobj = Py_None;
- bitmask_t *a, *b, *o;
- int xoffset = 0, yoffset = 0;
-
- if (!PyArg_ParseTuple (args, "O!|O(ii)", &PyMask_Type, &bobj, &oobj, &xoffset, &yoffset))
- return NULL;
-
- a = PyMask_AsBitmap(aobj);
- b = PyMask_AsBitmap(bobj);
-
- if (oobj == Py_None) {
- PyMaskObject *result = PyObject_New(PyMaskObject, &PyMask_Type);
-
- result->mask = bitmask_create(a->w + b->w - 1, a->h + b->h - 1);
- oobj = (PyObject*) result;
- }
- else
- Py_INCREF(oobj);
-
- o = PyMask_AsBitmap(oobj);
-
- bitmask_convolve(a, b, o, xoffset, yoffset);
- return oobj;
-}
-
-static PyObject * mask_find_closest(PyObject* self, PyObject* args)
-{
- bitmask_t * mask = PyMask_AsBitmap(self);
- int x, y;
-
- if (!PyArg_ParseTuple(args, "(ii)", &x, &y))
- return NULL;
-
- bitmask_find_closest(mask, &x, &y);
-
- return Py_BuildValue("(ii)", x, y);
-}
-
static PyObject* mask_from_surface(PyObject* self, PyObject* args)
{
bitmask_t *mask;
@@ -558,7 +512,7 @@
*/
PySurface_Unlock (surfobj);
- /*create the new python object from mask*/
+ /*create the new python object from mask*/
maskobj = PyObject_New(PyMaskObject, &PyMask_Type);
if(maskobj)
maskobj->mask = mask;
@@ -567,7 +521,7 @@
return (PyObject*)maskobj;
}
-void bitmask_threshold (bitmask_t *m, SDL_Surface *surf, SDL_Surface *surf2,
+void bitmask_threshold (bitmask_t *m, SDL_Surface *surf, SDL_Surface *surf2,
Uint32 color, Uint32 threshold)
{
int x, y, rshift, gshift, bshift, rshift2, gshift2, bshift2;
@@ -578,7 +532,9 @@
Uint8 *pix;
Uint8 r, g, b, a;
Uint8 tr, tg, tb, ta;
+ int bpp1, bpp2;
+
pixels = (Uint8 *) surf->pixels;
format = surf->format;
rmask = format->Rmask;
@@ -590,6 +546,7 @@
rloss = format->Rloss;
gloss = format->Gloss;
bloss = format->Bloss;
+ bpp1 = surf->format->BytesPerPixel;
if(surf2) {
format2 = surf2->format;
@@ -603,14 +560,17 @@
gloss2 = format2->Gloss;
bloss2 = format2->Bloss;
pixels2 = (Uint8 *) surf2->pixels;
+ bpp2 = surf->format->BytesPerPixel;
} else { /* make gcc stop complaining */
rmask2 = gmask2 = bmask2 = 0;
rshift2 = gshift2 = bshift2 = 0;
rloss2 = gloss2 = bloss2 = 0;
format2 = NULL;
pixels2 = NULL;
+ bpp2 = 0;
}
+
SDL_GetRGBA (color, format, &r, &g, &b, &a);
SDL_GetRGBA (threshold, format, &tr, &tg, &tb, &ta);
@@ -621,7 +581,7 @@
}
for(x=0; x < surf->w; x++) {
/* the_color = surf->get_at(x,y) */
- switch (format->BytesPerPixel)
+ switch (bpp1)
{
case 1:
the_color = (Uint32)*((Uint8 *) pixels);
@@ -647,7 +607,7 @@
}
if (surf2) {
- switch (format2->BytesPerPixel) {
+ switch (bpp2) {
case 1:
the_color2 = (Uint32)*((Uint8 *) pixels2);
pixels2++;
@@ -669,15 +629,15 @@
the_color2 = *((Uint32 *) pixels2);
pixels2 += 4;
break;
- }
- if ((abs((((the_color2 & rmask2) >> rshift2) << rloss2) - (((the_color & rmask) >> rshift) << rloss)) < tr) &
- (abs((((the_color2 & gmask2) >> gshift2) << gloss2) - (((the_color & gmask) >> gshift) << gloss)) < tg) &
+ }
+ if ((abs((((the_color2 & rmask2) >> rshift2) << rloss2) - (((the_color & rmask) >> rshift) << rloss)) < tr) &
+ (abs((((the_color2 & gmask2) >> gshift2) << gloss2) - (((the_color & gmask) >> gshift) << gloss)) < tg) &
(abs((((the_color2 & bmask2) >> bshift2) << bloss2) - (((the_color & bmask) >> bshift) << bloss)) < tb)) {
/* this pixel is within the threshold of othersurface. */
bitmask_setbit(m, x, y);
}
- } else if ((abs((((the_color & rmask) >> rshift) << rloss) - r) < tr) &
- (abs((((the_color & gmask) >> gshift) << gloss) - g) < tg) &
+ } else if ((abs((((the_color & rmask) >> rshift) << rloss) - r) < tr) &
+ (abs((((the_color & gmask) >> gshift) << gloss) - g) < tg) &
(abs((((the_color & bmask) >> bshift) << bloss) - b) < tb)) {
/* this pixel is within the threshold of the color. */
bitmask_setbit(m, x, y);
@@ -741,12 +701,12 @@
bpp = surf->format->BytesPerPixel;
m = bitmask_create(surf->w, surf->h);
-
+
PySurface_Lock(surfobj);
if(surfobj2) {
PySurface_Lock(surfobj2);
}
-
+
Py_BEGIN_ALLOW_THREADS;
bitmask_threshold (m, surf, surf2, color, color_threshold);
Py_END_ALLOW_THREADS;
@@ -766,7 +726,7 @@
-/* the initial labelling phase of the connected components algorithm
+/* the initial labelling phase of the connected components algorithm
Returns: The highest label in the labelled image
@@ -779,7 +739,7 @@
unsigned int cc_label(bitmask_t *input, unsigned int* image, unsigned int* ufind, unsigned int* largest) {
unsigned int *buf;
unsigned int x, y, w, h, root, aroot, croot, temp, label;
-
+
label = 0;
w = input->w;
h = input->h;
@@ -800,9 +760,9 @@
- /* special case for first row.
- Go over the first row except the first pixel.
- */
+ /* special case for first row.
+ Go over the first row except the first pixel.
+ */
for(x = 1; x < w; x++) {
if (bitmask_getbit(input, x, 0)) {
if (*(buf-1)) { /* d label */
@@ -938,7 +898,7 @@
buf++;
}
}
-
+
return label;
}
@@ -952,7 +912,7 @@
checked. It stores equivalence information in an array based union-find.
This implementation also has a final step of finding bounding boxes. */
-/*
+/*
returns -2 on memory allocation error, otherwise 0 on success.
input - the input mask.
@@ -983,8 +943,8 @@
largest = (unsigned int *) malloc(sizeof(int)*(w/2 + 1)*(h/2 + 1));
if(!largest) { return -2; }
-
-
+
+
/* do the initial labelling */
label = cc_label(input, image, ufind, largest);
@@ -996,7 +956,7 @@
if (ufind[x] < x) { /* is it a union find root? */
ufind[x] = ufind[ufind[x]]; /* relabel it to its root */
} else { /* its a root */
- relabel++;
+ relabel++;
ufind[x] = relabel; /* assign the lowest label available */
}
}
@@ -1015,7 +975,7 @@
/* the bounding rects, need enough space for the number of labels */
rects = (GAME_Rect *) malloc(sizeof(GAME_Rect) * (relabel +1));
if(!rects) { return -2; }
-
+
for (temp = 0; temp <= relabel; temp++) {
rects[temp].h = 0; /* so we know if its a new rect or not */
}
@@ -1040,8 +1000,8 @@
}
buf++;
}
- }
-
+ }
+
free(image);
free(ufind);
free(largest);
@@ -1057,8 +1017,8 @@
int num_bounding_boxes, i, r;
PyObject* ret;
PyObject* rect;
-
+
bitmask_t *mask = PyMask_AsBitmap(self);
ret = NULL;
@@ -1118,10 +1078,10 @@
largest = (unsigned int *) malloc(sizeof(int)*(w/2 + 1)*(h/2 + 1));
if(!largest) { return -2; }
-
+
/* do the initial labelling */
label = cc_label(mask, image, ufind, largest);
-
+
for (x = 1; x <= label; x++) {
if (ufind[x] < x) {
largest[ufind[x]] += largest[x];
@@ -1137,7 +1097,7 @@
ufind[x] = ufind[ufind[x]]; /* relabel it to its root */
} else { /* its a root */
if (largest[x] >= min) {
- relabel++;
+ relabel++;
ufind[x] = relabel; /* assign the lowest label available */
} else {
ufind[x] = 0;
@@ -1156,7 +1116,7 @@
/* allocate space for the mask array */
comps = (bitmask_t **) malloc(sizeof(bitmask_t *) * (relabel +1));
if(!comps) { return -2; }
-
+
/* create the empty masks */
for (x = 1; x <= relabel; x++) {
comps[x] = bitmask_create(w, h);
@@ -1172,7 +1132,7 @@
buf++;
}
}
-
+
free(image);
free(ufind);
free(largest);
@@ -1180,7 +1140,7 @@
*components = comps;
return relabel;
-}
+}
static PyObject* mask_connected_components(PyObject* self, PyObject* args)
{
@@ -1189,25 +1149,25 @@
bitmask_t **components;
bitmask_t *mask = PyMask_AsBitmap(self);
int i, num_components, min;
-
+
min = 0;
components = NULL;
-
+
if(!PyArg_ParseTuple(args, "|i", &min)) {
return NULL;
}
-
+
Py_BEGIN_ALLOW_THREADS;
num_components = get_connected_components(mask, &components, min);
Py_END_ALLOW_THREADS;
-
+
if (num_components == -2)
return RAISE (PyExc_MemoryError, "Not enough memory to get components. \n");
-
+
ret = PyList_New(0);
if (!ret)
- return NULL;
-
+ return NULL;
+
for (i=1; i <= num_components; i++) {
maskobj = PyObject_New(PyMaskObject, &PyMask_Type);
if(maskobj) {
@@ -1216,7 +1176,7 @@
Py_DECREF((PyObject *) maskobj);
}
}
-
+
free(components);
return ret;
}
@@ -1227,14 +1187,14 @@
summary, it is a very efficient two pass method for 8-connected components.
It uses a decision tree to minimize the number of neighbors that need to be
checked. It stores equivalence information in an array based union-find.
- This implementation also tracks the number of pixels in each label, finding
- the biggest one while flattening the union-find equivalence array. It then
+ This implementation also tracks the number of pixels in each label, finding
+ the biggest one while flattening the union-find equivalence array. It then
writes an output mask containing only the largest connected component. */
static int largest_connected_comp(bitmask_t* input, bitmask_t* output, int ccx, int ccy)
{
unsigned int *image, *ufind, *largest, *buf;
unsigned int max, x, y, w, h, label;
-
+
w = input->w;
h = input->h;
@@ -1244,11 +1204,18 @@
/* allocate enough space for the maximum possible connected components */
/* the union-find array. see wikipedia for info on union find */
ufind = (unsigned int *) malloc(sizeof(int)*(w/2 + 1)*(h/2 + 1));
- if(!ufind) { return -2; }
+ if(!ufind) {
+ free(image);
+ return -2;
+ }
/* an array to track the number of pixels associated with each label */
largest = (unsigned int *) malloc(sizeof(int)*(w/2 + 1)*(h/2 + 1));
- if(!largest) { return -2; }
-
+ if(!largest) {
+ free(image);
+ free(ufind);
+ return -2;
+ }
+
/* do the initial labelling */
label = cc_label(input, image, ufind, largest);
@@ -1263,7 +1230,7 @@
max = ufind[x];
}
}
-
+
/* write out the final image */
buf = image;
if (ccx >= 0)
@@ -1276,11 +1243,11 @@
buf++;
}
}
-
+
free(image);
free(ufind);
free(largest);
-
+
return 0;
}
@@ -1288,28 +1255,29 @@
{
bitmask_t *input = PyMask_AsBitmap(self);
bitmask_t *output = bitmask_create(input->w, input->h);
- PyMaskObject *maskobj = PyObject_New(PyMaskObject, &PyMask_Type);
+ PyMaskObject *maskobj = PyObject_New(PyMaskObject, &PyMask_Type);
int x, y;
-
+
x = -1;
if(!PyArg_ParseTuple(args, "|(ii)", &x, &y)) {
return NULL;
}
-
+
/* if a coordinate is specified, make the pixel there is actually set */
if (x == -1 || bitmask_getbit(input, x, y)) {
if (largest_connected_comp(input, output, x, y) == -2) {
return RAISE (PyExc_MemoryError, "Not enough memory to get bounding rects. \n");
}
}
-
+
if(maskobj)
maskobj->mask = output;
return (PyObject*)maskobj;
}
+
static PyMethodDef maskobj_builtins[] =
{
{ "get_size", mask_get_size, METH_VARARGS, DOC_MASKGETSIZE},
@@ -1328,8 +1296,6 @@
{ "centroid", mask_centroid, METH_NOARGS, DOC_MASKCENTROID },
{ "angle", mask_angle, METH_NOARGS, DOC_MASKANGLE },
{ "outline", mask_outline, METH_VARARGS, DOC_MASKOUTLINE },
- { "convolve", mask_convolve, METH_VARARGS, DOC_MASKCONVOLVE },
- { "find_closest", mask_find_closest, METH_VARARGS, DOC_MASKFINDCLOSEST },
{ "connected_component", mask_connected_component, METH_VARARGS,
DOC_MASKCONNECTEDCOMPONENT },
{ "connected_components", mask_connected_components, METH_VARARGS,
@@ -1358,7 +1324,7 @@
}
-static PyTypeObject PyMask_Type =
+static PyTypeObject PyMask_Type =
{
PyObject_HEAD_INIT(NULL)
0,
@@ -1373,7 +1339,7 @@
0,
0,
NULL,
- 0,
+ 0,
(hashfunc)NULL,
(ternaryfunc)NULL,
(reprfunc)NULL,
@@ -1395,8 +1361,8 @@
if(!mask)
return NULL; /*RAISE(PyExc_Error, "cannot create bitmask");*/
-
- /*create the new python object from mask*/
+
+ /*create the new python object from mask*/
maskobj = PyObject_New(PyMaskObject, &PyMask_Type);
if(maskobj)
maskobj->mask = mask;
@@ -1419,7 +1385,7 @@
{
PyObject *module, *dict;
PyType_Init(PyMask_Type);
-
+
/* create the module */
module = Py_InitModule3("mask", mask_builtins, DOC_PYGAMEMASK);
dict = PyModule_GetDict(module);
Deleted: pygame/src/mask.doc
===================================================================
--- pygame/src/mask.doc 2008-12-03 03:00:27 UTC (rev 109)
+++ pygame/src/mask.doc 2008-12-03 03:09:49 UTC (rev 110)
@@ -1,212 +0,0 @@
-pygame.mask
-pygame module for image masks.
-
-Useful for fast pixel perfect collision detection. A Mask uses 1bit per
-pixel to store which parts collide.
-
-New in pygame 1.8.
-<SECTION>
-
-from_surface
-Returns a Mask from the given surface.
-pygame.mask.from_surface(Surface, threshold = 127) -> Mask
-
-Makes the transparent parts of the Surface not set, and the opaque parts set.
-
-The alpha of each pixel is checked to see if it is greater than the
-given threshold.
-
-If the Surface is color keyed, then threshold is not used.
-<END>
-
-from_threshold
-Creates a mask by thresholding Surfaces
-pygame.mask.from_surface(Surface, color, threshold = (0,0,0,255), othersurface = None) -> Mask
-
-This is a more featureful method of getting a Mask from a Surface. If supplied
-with only one Surface, all pixels within the threshold of the supplied color are
-set in the Mask. If given the optional othersurface, all pixels in Surface that
-are within the threshold of the corresponding pixel in othersurface are set in
-the Mask.
-<END>
-
-Mask
-pygame object for representing 2d bitmasks
-pygame.Mask((width, height)): return Mask
-<SECTION>
-
-get_size
-Returns the size of the mask.
-Mask.get_size() -> width,height
-<END>
-
-get_at
-Returns nonzero if the bit at (x,y) is set.
-Mask.get_at((x,y)) -> int
-
-Coordinates start at (0,0) is top left - just like Surfaces.
-<END>
-
-set_at
-Sets the position in the mask given by x and y.
-Mask.set_at((x,y),value)
-<END>
-
-overlap
-Returns the point of intersection if the masks overlap with the given offset - or None if it does not overlap.
-Mask.overlap(othermask, offset) -> x,y
-
-The overlap tests uses the following offsets (which may be negative):
-
- +----+----------..
- |A | yoffset
- | +-+----------..
- +--|B
- |xoffset
- | |
- : :
-<END>
-
-overlap_area
-Returns the number of overlapping 'pixels'.
-Mask.overlap_area(othermask, offset) -> numpixels
-
-You can see how many pixels overlap with the other mask given. This can
-be used to see in which direction things collide, or to see how much the
-two masks collide. An approximate collision normal can be found by calculating
-the gradient of the overlap area through the finite difference.
-
- dx = Mask.overlap_area(othermask,(x+1,y)) - Mask.overlap_area(othermask,(x-1,y))
- dy = Mask.overlap_area(othermask,(x,y+1)) - Mask.overlap_area(othermask,(x,y-1))
-<END>
-
-overlap_mask
-Returns a mask of the overlapping pixels
-Mask.overlap_mask(othermask, offset) -> Mask
-
-Returns a Mask the size of the original Mask containing only the overlapping
-pixels between Mask and othermask.
-<END>
-
-fill
-Sets all bits to 1
-Mask.fill()
-
-Sets all bits in a Mask to 1.
-<END>
-
-clear
-Sets all bits to 0
-Mask.clear()
-
-Sets all bits in a Mask to 0.
-<END>
-
-invert
-Flips the bits in a Mask
-Mask.invert()
-
-Flips all of the bits in a Mask, so that the set pixels turn to unset pixels and
-the unset pixels turn to set pixels.
-<END>
-
-scale
-Resizes a mask
-Mask.scale((x, y)) -> Mask
-
-Returns a new Mask of the Mask scaled to the requested size.
-<END>
-
-draw
-Draws a mask onto another
-Mask.draw(othermask, offset)
-
-Performs a bitwise OR, drawing othermask onto Mask.
-<END>
-
-erase
-Erases a mask from another
-Mask.erase(othermask, offset)
-
-Erases all pixels set in othermask from Mask.
-<END>
-
-count
-Returns the number of set pixels
-Mask.count() -> pixels
-
-Returns the number of set pixels in the Mask.
-<END>
-
-centroid
-Returns the centroid of the pixels in a Mask
-Mask.centroid() -> (x, y)
-
-Finds the centroid, the center of pixel mass, of a Mask. Returns a coordinate
-tuple for the centroid of the Mask. In the event the Mask is empty, it will
-return (0,0).
-<END>
-
-angle
-Returns the orientation of the pixels
-Mask.angle() -> theta
-
-Finds the approximate orientation of the pixels in the image from -90 to 90
-degrees. This works best if performed on one connected component of pixels. It
-will return 0.0 on an empty Mask.
-<END>
-
-outline
-list of points outlining an object
-Mask.outline(every = 1) -> [(x,y), (x,y) ...]
-
-Returns a list of points of the outline of the first object it comes across in a
-Mask. For this to be useful, there should probably only be one connected
-component of pixels in the Mask. The every option allows you to skip pixels in
-the outline. For example, setting it to 10 would return a list of every 10th
-pixel in the outline.
-<END>
-
-connected_component
-Returns a mask of a connected region of pixels.
-Mask.connected_component((x,y) = None) -> Mask
-
-This uses the SAUF algorithm to find a connected component in the
-Mask. It checks 8 point connectivity. By default, it will return the largest
-connected component in the image. Optionally, a coordinate pair of a pixel can
-be specified, and the connected component containing it will be returned. In
-the event the pixel at that location is not set, the returned Mask will be
-empty. The Mask returned is the same size as the original Mask.
-<END>
-
-connected_components
-Returns a list of masks of connected regions of pixels.
-Mask.connected_components(min = 0) -> [Masks]
-
-Returns a list of masks of connected regions of pixels. An optional minimum
-number of pixels per connected region can be specified to filter out noise.
-<END>
-
-get_bounding_rects
-Returns a list of bounding rects of regions of set pixels.
-Mask.get_bounding_rects() -> Rects
-
-This gets a bounding rect of connected regions of set pixels. A
-bounding rect is one for which each of the connected pixels is inside
-the rect.
-<END>
-
-convolve
-Return the convolution of self with another mask.
-Mask.convolve(othermask, outputmask = None, offset = (0,0)): return Mask
-Returns a mask with the (i-offset[0],j-offset[1]) bit set if shifting othermask
-so that it's lower right corner pixel is at (i,j) would cause it to overlap
-with self.
-
-If outputmask is not None, then the output is drawn onto outputmask and
-outputmask is returned. Otherwise a mask of size self.size() +
-othermask.getsize() - (1,1) is created.
-<END>
-
-
-<END>
Added: pygame/src/mask.h
===================================================================
--- pygame/src/mask.h (rev 0)
+++ pygame/src/mask.h 2008-12-03 03:09:49 UTC (rev 110)
@@ -0,0 +1,23 @@
+#include <Python.h>
+#include "bitmask.h"
+
+#define PYGAMEAPI_MASK_NUMSLOTS
+
+typedef struct {
+ PyObject_HEAD
+ bitmask_t *mask;
+} PyMaskObject;
+
+#define PyMask_AsBitmap(x) (((PyMaskObject*)x)->mask)
+
+#ifndef PYGAMEAPI_MASK_INTERNAL
+
+#define PyMask_Type (*(PyTypeObject*)PyMASK_C_API[0])
+#define PyMask_Check(x) ((x)->ob_type == &PyMask_Type)
+
+
+
+#endif /* !defined(PYGAMEAPI_MASK_INTERNAL) */
+
+static void* PyMASK_C_API[PYGAMEAPI_MASK_NUMSLOTS] = {NULL};
+
Deleted: pygame/src/pygamedocs.h
===================================================================
--- pygame/src/pygamedocs.h 2008-12-03 03:00:27 UTC (rev 109)
+++ pygame/src/pygamedocs.h 2008-12-03 03:09:49 UTC (rev 110)
@@ -1,915 +0,0 @@
-/* Auto generated file: with makeref.py . Docs go in src/ *.doc . */
-#define DOC_PYGAME "the top level pygame package"
-
-#define DOC_PYGAMEINIT "pygame.init(): return (numpass, numfail)\ninitialize all imported pygame modules"
-
-#define DOC_PYGAMEQUIT "pygame.quit(): return None\nuninitialize all pygame modules"
-
-#define DOC_PYGAMEERROR "raise pygame.error, message\nstandard pygame exception"
-
-#define DOC_PYGAMEGETERROR "pygame.get_error(): return errorstr\nget the current error message"
-
-#define DOC_PYGAMEGETSDLVERSION "pygame.get_sdl_version(): return major, minor, patch\nget the version number of SDL"
-
-#define DOC_PYGAMEGETSDLBYTEORDER "pygame.get_sdl_byteorder(): return int\nget the byte order of SDL"
-
-#define DOC_PYGAMEREGISTERQUIT "register_quit(callable): return None\nregister a function to be called when pygame quits"
-
-#define DOC_PYGAMEVERSION "module pygame.version\nsmall module containing version information"
-
-#define DOC_PYGAMEVERSIONVER "pygame.version.ver = '1.2'\nversion number as a string"
-
-#define DOC_PYGAMEVERSIONVERNUM "pygame.version.vernum = (1, 5, 3)\ntupled integers of the version"
-
-#define DOC_PYGAMECAMERA "pygame module for camera use"
-
-#define DOC_PYGAMECAMERACOLORSPACE "pygame.camera.colorspace(Surface, format, DestSurface = None): return Surface\nSurface colorspace conversion"
-
-#define DOC_PYGAMECAMERALISTCAMERAS "pygame.camera.list_cameras(): return [cameras]\nreturns a list of available cameras"
-
-#define DOC_PYGAMECAMERACAMERA "pygame.camera.Camera(device, (width, height), format): return Camera\nload a camera"
-
-#define DOC_CAMERASTART "Camera.start(): return None\nopens, initializes, and starts capturing"
-
-#define DOC_CAMERASTOP "Camera.stop(): return None\nstops, uninitializes, and closes the camera"
-
-#define DOC_CAMERAGETCONTROLS "Camera.get_controls(): return (hflip = bool, vflip = bool)\ngets current values of user controls"
-
-#define DOC_CAMERASETCONTROLS "Camera.set_controls(hflip = bool, vflip = bool): return (hflip = bool, vflip = bool)\nchanges camera settings if supported by the camera"
-
-#define DOC_CAMERAGETSIZE "Camera.get_size(): return (width, height)\nreturns the dimensions of the images being recorded"
-
-#define DOC_CAMERAQUERYIMAGE "Camera.query_image(): return bool\nchecks if a frame is ready"
-
-#define DOC_CAMERAGETIMAGE "Camera.get_image(Surface = None): return Surface\ncaptures an image as a Surface"
-
-#define DOC_CAMERAGETRAW "Camera.get_raw(): return string\nreturns an unmodified image as a string"
-
-#define DOC_PYGAMECDROM "pygame module for audio cdrom control"
-
-#define DOC_PYGAMECDROMINIT "pygame.cdrom.init(): return None\ninitialize the cdrom module"
-
-#define DOC_PYGAMECDROMQUIT "pygame.cdrom.quit(): return None\nuninitialize the cdrom module"
-
-#define DOC_PYGAMECDROMGETINIT "pygame.cdrom.get_init(): return bool\ntrue if the cdrom module is initialized"
-
-#define DOC_PYGAMECDROMGETCOUNT "pygame.cdrom.get_count(): return count\nnu...
[truncated message content] |
Thanks for helping keep SourceForge clean.
X