Path: chuka.playstation.co.uk!news
From: yaroze@theburrow.co.uk (Barry & Robert Swan)
Newsgroups: scee.yaroze.beginners
Subject: Re: Collision Detection!.....(Joy)
Date: Sun, 20 Jun 1999 18:40:31 GMT
Organization: PlayStation Net Yaroze (SCEE)
Lines: 191
Message-ID: <376d3500.12938268@www.netyaroze-europe.com>
References: <7kdntq$4fj13@chuka.playstation.co.uk>
NNTP-Posting-Host: pEBs11a01.client.global.net.uk
X-Newsreader: Forte Free Agent 1.11/32.235

Right this time Ill answer it properly. Basically, I had got halfway
thru answering this last night in my half drunk state, and then my
B***Y modem crashed the computer, so it was all wasted. So
unfortunately I have less patience this time and maybe wont write
everything down. Just have to see how annoyed I get, really.

also, none of this is tested, im very likely to get some of my x's and
y's the wrong way around, but then I always do :)


On Fri, 18 Jun 1999 16:15:41 +0100, "Scott Ward"
<scott.ward6@virgin.net> wrote:

>I've been looking for different ways of achieving quality collision
>detection and I saw a method on the Sony FAQ page which copies images into
>main memory and then uses bitwise 'and' to test for collision. Although this
>method is supposedly very slow it is pixel perfect when it comes to accuracy
>so I really wouldn't mind giving it a whirl.
>
>I got in touch with James Russell at Sony who provided me with some more
>information but I'm still unsure of how to do it. Here's a snippet of what
>he sent me:
>
>>Firstly you do trivial rejection - if the horizontal and vertical
>boundaries of
>>the two sprites don't cross in any way, then there is no detection. If they
>do
>>cross, then you clear a buffer that is the same size as the screen
>(although it
>>only has to have a 2 bit resolution). Then you copy the first mask into
>that
>>buffer, shifting the bits as necessary so that the mask is in the same
>position
>>it's in on the screen. Then you do the same for the second mask, except
>instead
>>of copying the mask into the buffer, you and it with the buffer and test
>the
>>result. If any bit is one, then there was a collision.
>
>Right, I'm still pretty new to this games coding business so whilst this
>message may seem reasonably straight forward to you lot it has me a little
>baffled.
>
>I'd get back in touch with James but I feel this may take some time to sort
>out so instead of me hounding the good people at Sony I'd rather someone
>offered their time to help me out. To save space on the newsgroup I'll try
>to ask as many questions on this one note. Here goes:
>
>1) Although I understand the concept of creating a mask of a sprite how do
>you make one? At first I thought that you probably just create an identical
>sprite with lower resolution but then, as far I know, 4-bit sprites are the
>lowest resolution you can load into the frame buffer. How do you make a
>2-bit mask?

ok, lets assume that the texture from which you create the texture has
a width that is a multiple of 2 (which it has to if its a 4 bit tim
anyway. or summat like that... cant remember (as usual)) This will
also muck up if you specify a sprite x or y of zero, but you would be
a FOOL to do such a thing. There is a much simpler way of creating
your masks, and that is to use an art package. Load up your texture,
and then mess around until all your non black colours are all white
(either through changing the palette values or floodfil or whatever)
and hen reduce it down to 2 colours. This can then be loaded into your
program as any other data file (tim or tmd).

// am only creating the mask locally. you might want to do it 
// globally or whatever...
// imageData is a pointer to the LoadImaged'd texture

void	CreateMaskFromTextureData(int sizex, int sizey, u_char
*imageData)
{
	// create an array that will hold all the mask info
	u_char	maskData[((sizex&0xf8)+1) * sizey];
	u_char	*maskPointer, *tp;
	
	int i,j;

	// try to use pointer arithmetic as per usual rubbish
	maskPointer = maskData;

	// work from top to bottom
	for (i=0; i<sizey; i++)
	{
		// work from left to right, a byte at a time
		for (j=0; j<(sizex&f8)+1); j++)
		{
			maskData = 0;		
			maskBit	= 0;
			
			// work on a maskData char at a time
			for (k=0; k<(sizex&0x07); k+=2)
			{
				maskPointer |= !!(imageData & 0x0f) << maskBit;
				maskPointer |= !!(imageData & 0xf0) << (maskBit+1);
				maskBit+=2;
				imageData++;
			}
		maskPointer++;
		}	
	}
}

what you end up with is a mask whose width is a multiple of 8 pixels.
Ie, if your texture was 6 pixels wide, the mask is 8 pixels wide with
the extra bits set to zero so as not to interfere with the anding
later on.

>2)When James refers to a buffer, does this mean in the frame buffer or a
>buffer in memory? If it means create a buffer in memory then I definately
>need help. :o\

see above with regards creating buffer in memory. It could be globabl
or local.

>3)Copying the first mask into the buffer. What form does the mask take? Is
>it an image in the frame buffer or is it stored in memory as a series of
>bytes?

well, what it is is irrelevant. Its the interpretation of memory that
defines what its use is, so an image in frame buffer or in memory as a
series of bytes are analogous. except one is in vram, the other isnt.

>4)If all this done in the frame buffer then I have no bother moving stuff
>about but if it's done in memory how would you go about 'shifting the bits'
>and how would you know where to shift them to?

ah, thje fun part. This next function is going to assume some nasty
things - that both the objects you want to check have masks of 16x16
pixels (ie, 16x16/8 bytes = 32 chars). 

int	HasCollided(int x1, int y1, int x2, int y2, u_char*mask1, u_char
mask2)
{
	int			shift1, shift2;
	int			numy;
	u_long		m1, m2;
	u_char		*line1, *line2;
	int			i;

	// do trivial boundy box reject first
	// do these stacked IFs give quicker execution than
	// one huge IF statement? havent checked so hypothetical
	if (x1 > (x2+16)) 	return (0);
	if (x1 <= (x2-16)) 	return (0);
	if (y1 > (y2+16)) 	return (0);
	if (y1 <= (y2-16)) 	return (0);

	// ok so bound boxes overlap... now some annoying stuff...
	// find offset from 16 pixel boundaries for the masks
	shift1 = x1 & 0x0f;
	shift2 = x2 & 0x0f;
	if (y1 > y2)
	{
		numy = y2 - y1 + 16;
		line1 = mask1;
		line2 = mask2 + (16-numy);
	}
	else
	{
		numy = y1 - y2 + 16;
		line1 = mask1 + (16-numy);;
		line2 = mask2;
	}	

	// now do the actual checking loop
	for (i=0; i<numy; i++)
	{
		t1 = (*line1 >> shift2)  >> 16;
		t2 = (*line2 >> shift1) >> 16;
		if (t1&t2)	return (1);
		line1++;
		line2++;
	}	

	return (0);
}

>I know this question(s) must seem a bit daunting but even if you can only
>answer one of the questions or you think you have a rough idea then I'd be
>grateful if you'd get in touch.
>
>Cheers,
>
>Scott  "stuck again.....what a surprise"  Ward.

Of course, you could email James Shaugnessy who did this collision
detection method for his cool game, gravitation, from which I won a
lovely joystick :)

Rob