[Author Prev][Author Next][Thread Prev][Thread Next][Author Index][Thread Index]

Re: [pygame] extending pygame masks



Attached. It's not integrated w/ python yet, but the tricky part is mostly done.

--Mike

Nirav Patel wrote:
Mike

Ah, very interesting. Can I see the source on that?  I would love to
see that included in the Mask module.

Nirav

On Tue, Oct 14, 2008 at 10:44 AM, Michael George
<mdgeorge@xxxxxxxxxxxxxx> wrote:
Thanks,

what I need is different - I need to compute overlap_mask for each possible
offset, so that I can search for an optimal placement.  Of course I could
write a loop and call overlap_mask for each offset, but I think that would
be prohibitively slow - I'm computing it all in one pass.

To move the #defines into pygame.h you wouldn't need to include the PyObject
stuff in bitmask.h.  If anything, pygame.h would have to include bitmask.h,
not the other way around (although you could just add a forward declaration
of bitmask_t).  In the mean time, I guess I'll just copy the defs into my
source.

--Mike

Nirav Patel wrote:
Mike,

I'm not sure if this is what you mean, but the Mask module has a
function in SVN called Mask.overlap_mask, which returns a mask of the
overlapping pixels between two masks by an offset.

The internals of most of the bitmask stuff is exposed in bitmask.h.
It could be useful to move the defines and typedef from mask.c to
there.  I think the reason it wasn't is that what's in bitmask.h
currently is purely C, while the typedef has a PyObject_HEAD in it.
Alternately, if you're making an external module, you could just
import bitmask.h and copy the typedef and defines into your file.

Nirav

On Tue, Oct 14, 2008 at 9:11 AM, Michael George <mdgeorge@xxxxxxxxxxxxxx>
wrote:

hello,

I've been working on some code that generates what I've been calling a
"hitmask", namely a mask with the (x,y) bit set if placing one mask on
another offset by (x,y) would cause a collision.  It's part of a slick
algorithm I'm working on for drag-and-drop collision response.  I've
implemented it in C against the bitmask api.  I have n questions:

1. Is there any interest in putting this in pygame?  I suspect no,
because
it's only useful for situations where you may freely drag oddly-shaped
objects around but need to avoid collisions between them.  It would be
good
for things like map editors.  However if there is interest, I'd be happy
to
contribute it.

2. If not, I'd like to avoid shipping a modified pygame with my game.  Is
it
possible for me to build and ship extensions that link against pygame
internals (really just the bitmask stuff, and maybe rects at some point)?
 I
haven't dug into the python/C boundary too much, although glancing over
the
pygame source it doesn't seem too bad.  Can someone point me in the right
direction?

3. If I do build my code separately, it currently looks impossible to
actually get at the internals of a PyMaskObject without doing something
hacky.  In particular, the data structure and the PyMask_AsBitmap macro
are
only defined in mask.c, rather than in a separate header file.  Is it
reasonable for you to move that into pygame.h, or is it hidden for a
reason?


...where n = 3.

Thanks!

--Mike



#include <stdio.h>
#include "bitmask.h"

/*
** Convolution *****************************************************************
*/

/* or aw bits from a into o + offset bits  */
static void shift_or(BITMASK_W * a, int aw, int offset, BITMASK_W * o)
{
	int woff = offset / BITMASK_W_LEN;
	int boff = offset & BITMASK_W_MASK;
	int mask_len;

	BITMASK_W residue = 0;
	BITMASK_W current;

	int i = 0;
	for (i = 0; (i+1) * BITMASK_W_LEN < aw + boff; i++)
	{
		current = residue | (a[i] << boff);
		residue = a[i] >> (BITMASK_W_LEN - boff);

		o[woff + i] |= current;
	}

	mask_len = BITMASK_W_LEN - (offset + aw) & BITMASK_W_MASK;
	current  = residue | (a[i] << boff);
	current  = current << mask_len >> mask_len;

	o[woff + i] |= current;
}

/* create "hitmask": a mask with the [x,y] bit set if the corresponding offset
 * would cause an intersection between a and b.  Assumes that b is
 * right-aligned */
void bitmask_convolve(bitmask_t * a, bitmask_t * b, bitmask_t * o, int xoff, int yoff)
{
	/* widths in words */
	int aw = a->w / BITMASK_W_LEN + (a->w % BITMASK_W_LEN != 0),
	    ow = o->w / BITMASK_W_LEN + (o->w % BITMASK_W_LEN != 0);

	/* loop variables; positions in a and b */
	int ax, bx, ay, by;
	
	for (ay = 0; ay < a->h; ay++)
		for (by = 0; by < b->h; by++)
			for (bx = 0; bx < b->w; bx++)
				if (bitmask_getbit(b, b->w - bx - 1, by))
				{
					/* oy is the row of the output */
					int oy = ay - by + yoff + b->h - 1;

					/* or a->w bits from ay'th row to oy'th row, offset by xoff + bx bits */
					shift_or(&(a->bits[ay*aw]), a->w, xoff + bx, &(o->bits[oy*ow]));
				}
}


/*
** Closest Point ***************************************************************
*/

#define SQ(x) ((x) * (x))

/* find the closest point to (*x,*y) with getbit(mask,x,y) cleared.  Set (*x, *y)
 * to the result.  The result may be just outside of the boundary. */
void bitmask_closest(bitmask_t * mask, int * x, int * y)
{
	/* TODO: incremental search */
	unsigned int best_d = -1;
	int best_x, best_y;
	int i = 0, j = 0;

	/* check boundary */
	if (SQ(*x + 1) < best_d)
	{
		/* left */
		best_x = -1;
		best_y = *y;
		best_d = SQ(*x + 1);
	}
	if (SQ(*y + 1) < best_d)
	{
		/* top */
		best_x = *x;
		best_y = -1;
		best_d = SQ(*y + 1);
	}
	if (SQ(mask->w - *x) < best_d)
	{
		/* right */
		best_x = mask->w;
		best_y = *y;
		best_d = SQ(mask->w - *x);
	}
	if (SQ(mask->h - *y) < best_d)
	{
		/* bottom */
		best_x = *x;
		best_y = mask->h;
		best_d = SQ(mask->h - *y);
	}

	/* check interior */
	for (i = 0; i < mask->w; i++)
		for (j = 0; j < mask->h; j++)
			if (bitmask_getbit(mask, i, j))
			{
				unsigned int d = SQ(i - *x) + SQ(j - *y);
				if (d < best_d)
				{
					best_d = d;
					best_x = i;
					best_y = j;
				}
			}
	*x = best_x;
	*y = best_y;
}

/*
** Testing *********************************************************************
*/

static void print(bitmask_t * data)
{
	int x, y;

	for (y = 0; y < data->h; y++)
	{
		for (x = 0; x < data->w; x++)
			printf ("%c", bitmask_getbit(data,x,y) ? '+' : '-');
		printf("\n");
	}
}

int a_data[] = { 0, 1, 0, 0, 0, 1,
                 0, 1, 1, 1, 1, 1,
                 0, 1, 0, 1, 0, 0};

int b_data[] = { 0, 1, 0,
                 0, 1, 1,
			     0, 1, 0,
			     1, 1, 0};

void bitmask_test(bitmask_t * bm, int vals[], int w, int h)
{
	int i, j;
	for (i = 0; i < w; i++)
		for (j = 0; j < h; j++)
			if (vals[j*w + i])
				bitmask_setbit(bm, i, j);
}

int main(int argc, char** argv)
{
	bitmask_t *a, *b, *o, *p;
	int i, j;

	a = bitmask_create(6, 3);
	b = bitmask_create(3, 4);
	p = bitmask_create(1, 1);
	o = bitmask_create(8, 6);

	bitmask_setbit(p, 0, 0);
	bitmask_test(a, a_data, 6, 3);
	bitmask_test(b, b_data, 3, 4);
	bitmask_convolve(a, p, o, 2, 2);

	printf("A:\n");
	print(a);
	printf("\n\n");

	printf("B: \n");
	print(b);
	printf("\n\n");

	printf("O: \n");
	print(o);
	printf("\n\n");

	return 0;
}

/*
** vim: ts=4 sw=4 cindent cino=\:0
*/