Pixel perfect collisions

[Paul]

HI!
I'm working on an image collision routine. Right now I'm checking all the pixels that overlap the collision rectangles(hope you understand what i mean ).
Right now it's about 50x slower than the built in one in blitz. Some ideas i have to speed it up are, at least one is to.
divide the image up into 4 smaller squares, repeatedly until i get down to the pixel level.
If it doesn't sound clear the attached image below probably wont help
Any other Ideas on how to make a faster image collision checker are welcome.


The code (in blitz, i start here but will rewrite it i c# when it's done).

Code: [Select]

Const gx=1024
Const gy=768
;Const debug_c=1


Graphics gx,gy,32,2
SetBuffer BackBuffer()


Local image1 = loadimage2("",-16777216);black
Local image2 = loadimage2("",-16777216);black


HidePointer()


Local mx
Local my
Local mz

While Not KeyHit(1)

mx=MouseX()
my=MouseY()
mz=MouseZ()

drawimage2(image1,20,20,Abs(mz) Mod 2)
drawimage2(image2,mx,my,Abs(mz) Mod 2)
If ImagesCollide2(image1,20,20,image2,mx,my) Then Text 0,0,"!!!!!!!!!!!!!"




Flip
Cls

Wend

Function drawimage2(image,x,y,debug=0)

If debug
Local i=0
LockBuffer BackBuffer()
Local iw=PeekShort(image,6)

For x1=0 To PeekShort(image,4)-1
For y1=0 To PeekShort(image,6)-1
i=x1*iw+y1
If Not y1+y=>gy Or y1+y<0 Or x1+x=>gx Or x1+x<0
If PeekByte(image,i/8+8) And (1 Shl (i Mod 8))
WritePixelFast(x+x1,y+Y1,255)
EndIf

EndIf
i=i+1
Next
Next
UnlockBuffer BackBuffer()
Else
DrawImage(PeekInt(image,0),x,y)
EndIf
End Function

Function loadimage2(Image_f$,Mask)
Local Image=LoadImage(Image_f$)
Local Iw=ImageWidth(Image)
Local Ih=ImageHeight(Image)

Local bank=CreateBank(((Ih*Iw) Shr 3)+9)
PokeInt(bank,0,Image)
PokeShort(bank,4,Iw)
PokeShort(bank,6,Ih)
;DebugLog Iw+","+Ih

Local i,x,y,byte=0
Local buffer=ImageBuffer(Image)
LockBuffer buffer
;Mask=ReadPixelFast(0,0,buffer)
For i=0 To (Iw*Ih)-1
y=i-(i/Ih)*Ih
x=i/Ih
If ReadPixelFast(x,y,buffer)<>Mask
byte=byte+(1 Shl (i Mod 8))
EndIf
If i Mod 8=7
PokeByte(bank,i/8+8,byte)
byte=0
EndIf
Next
UnlockBuffer buffer

Return bank
End Function

Function MaskImage2(image,mask)
iw=PeekShort(image,4)
ih=PeekShort(image,6)

Local buffer=ImageBuffer(PeekInt(image,0))
LockBuffer buffer
For i=0 To iw*ih-1
y=i-(i/Ih)*Ih
x=i/Ih
If ReadPixelFast(x,y,buffer)<>mask
byte=byte+(1 Shl (i Mod 8))
EndIf
If i Mod 8=7
PokeByte(image,i/8+8,byte)
byte=0
EndIf
Next
UnlockBuffer buffer

End Function

Function ImagesCollide2(image1,x1,y1,image2,x2,y2)
Local sx1=PeekShort(image1,4)
Local sy1=PeekShort(image1,6)

Local sx2=PeekShort(image2,4)
Local sy2=PeekShort(image2,6)

Local top
Local bottom
Local Left
Local Right


If x1>x2
Left=x1
Else
Left=x2
EndIf
If y1>y2
top=y1
Else
top=y2
EndIf

If y1+sy1<y2+sy2
bottom=y1+sy1
Else
bottom=y2+sy2
EndIf
If x1+sx1<x2+sx2
Right=x1+sx1
Else
Right=x2+sx2
EndIf


t1=top-y1
t2=top-y2

For x=Left To Right-1
i1=(x-x1)*sy1+t1
i2=(x-x2)*sy2+t2
f1=i1 Mod 8
f2=i2 Mod 8
For y=top To bottom-1
;n1%=PeekByte(image1,i1 Shr 3+8) And 1 Shl f1
;n2%=PeekByte(image2,i2 Shr 3+8) And 1 Shl f2
;If n1>0 And n2>0 Then Return 1
;If debug_c=0
;I know reading the byte for every pixel is lame, but I hopefully wont have that problem in c#
If (PeekByte(image1,i1 Shr 3+8) And 1 Shl f1)>0 And (PeekByte(image2,i2 Shr 3+8) And 1 Shl f2)>0 Then Return 1
;Else
; If (PeekByte(image1,i1 Shr 3+8) And 1 Shl f1)>0 And (PeekByte(image2,i2 Shr 3+8) And 1 Shl f2)>0 Then Plot x,y
;EndIf
i1=i1+1
i2=i2+1
f1=f1+1
f2=f2+1
If f1>7 Then f1=0
If f2>7 Then f2=0
Next
Next
Return 0
End Function





[code][/code]

[Jim]

Create a 1-bit per pixel mask graphic for each sprite, set it to 0 where there are no pixels and a 1 where there are coloured pixels.
Then you can check many pixels at once by just ANDing together the masks.

I like the recursive subdivision idea too

Jim

[va!n]

if you need to detect collisions between two circles i can post an easy and very good (pixel exactly) collision code

[Paul]

Thx for the whole byte idea Jim, but i don't really see how it would work?
I'm doing the i bit pixel mask, but still checking each pixel individually. could you try to explain further, please?

@ va!n it's supposed to work for any image, not just circles( it was easier to draw i circle in paint )

[Shockwave]

IF you have an image and look at one line for example.

Let's say that the 0's are blank pixels and the 1's have something drawn on them.

0001111000

That is how you create a mask.

Then you can overlay the masks of sprites and use the AND command to detect collisions.

for example, these masks;

0001111000 and 0011110000

0001111000
0011110000

Remember, AND only returns true if both bits are set so;

If (%0001111000 and %0011110000) = true then
  collision
else
  do nothing
end if

[Paul]

Thank you for the explanations shocky, va!n and Jim, but I cant get it to work.
The problem is that the bytes aren't always synced, one of the images has to read bit 4 and the other image needs to read bit 3, wouldn't they be one pixel off?
The answer is probably really simple, but i can't think of anything that works.

[Jim]

In those cases you need to shift one of the masks left or right before doing the AND.  It makes it a bit more complicated.

Jim

[rain_storm]

either shift the bits or only create the collision mask so that it starts alligned on both sides but where added zeros on the ends are allowed

[Paul]

The closest i can get is this:
white is where it found a collision outside the image and blue is the image I'm checking against.

Code: [Select]

Const gx=1024
Const gy=768
Const debug_c=0


Graphics gx,gy,32,2
SetBuffer BackBuffer()


Local image1 = loadimage2("",-16777216);black
Local image2 = loadimage2("",-16777216);black


HidePointer()


Local mx
Local my
Local mz

While Not KeyHit(1)

mx=MouseX()
my=MouseY()
mz=MouseZ()

drawimage2(image1,20,20,Abs(mz) Mod 2)
drawimage2(image2,mx,my,Abs(mz) Mod 2)
If ImagesCollide2(image1,20,20,image2,mx,my) Then Text 0,0,"!!!!!!!!!!!!!"
If ImagesCollide(PeekInt(image1,0),20,20,0,PeekInt(image2,0),mx,my,0) Then Text 0,20,"wWWWWWWWWWWWWWWWWWWWW"

;blur(image1,8,PeekShort(image1,4),PeekShort(image1,6))
;WaitKey()
Flip
Cls

Wend

Function drawimage2(image,x,y,debug=0)

If debug
Local i=0
LockBuffer BackBuffer()
Local iH=PeekShort(image,6)

For x1=0 To PeekShort(image,4)-1
For y1=0 To PeekShort(image,6)-1
i=x1*iH+y1
If Not y1+y=>gy Or y1+y<0 Or x1+x=>gx Or x1+x<0
If PeekByte(image,i/8+8) And (1 Shl (i Mod 8))
WritePixelFast(x+x1,y+Y1,255)
EndIf

EndIf
i=i+1
Next
Next
UnlockBuffer BackBuffer()
Else
DrawImage(PeekInt(image,0),x,y)
EndIf
End Function

Function loadimage2(Image_f$,Mask)
Local Image=LoadImage(Image_f$)
Local Iw=ImageWidth(Image)
Local Ih=ImageHeight(Image)

Local bank=CreateBank(((Ih*Iw) Shr 3)+9+8)
PokeInt(bank,0,Image)
PokeShort(bank,4,Iw)
PokeShort(bank,6,Ih)
;DebugLog Iw+","+Ih

Local i,x,y,byte=0
Local buffer=ImageBuffer(Image)
LockBuffer buffer
;Mask=ReadPixelFast(0,0,buffer)
For i=0 To (Iw*Ih)-1
y=i-(i/Ih)*Ih
x=i/Ih
If ReadPixelFast(x,y,buffer)<>Mask
byte=byte+(1 Shl (i Mod 8))
EndIf
If i Mod 8=7
PokeByte(bank,i/8+8,byte)
byte=0
EndIf
Next
UnlockBuffer buffer

Return bank
End Function

Function MaskImage2(image,mask)
iw=PeekShort(image,4)
ih=PeekShort(image,6)

Local buffer=ImageBuffer(PeekInt(image,0))
LockBuffer buffer
For i=0 To iw*ih-1
y=i-(i/Ih)*Ih
x=i/Ih
If ReadPixelFast(x,y,buffer)<>mask
byte=byte+(1 Shl (i Mod 8))
EndIf
If i Mod 8=7
PokeByte(image,i/8+8,byte)
byte=0
EndIf
Next
UnlockBuffer buffer

End Function

Function ImagesCollide2(image1,x1,y1,image2,x2,y2)
Local sx1=PeekShort(image1,4)
Local sy1=PeekShort(image1,6)

Local sx2=PeekShort(image2,4)
Local sy2=PeekShort(image2,6)

Local top
Local bottom
Local Left
Local Right


; If x1>x2
; Left=x1
; Else
; Left=x2
; EndIf
; If y1>y2
; top=y1
; Else
; top=y2
; EndIf
;
; If y1+sy1<y2+sy2
; bottom=y1+sy1
; Else
; bottom=y2+sy2
; EndIf
; If x1+sx1<x2+sx2
; Right=x1+sx1
; Else
; Right=x2+sx2
; EndIf

Right=min(x1+sx1,x2+sx2)
Left=max(x1,x2)
top=max(y1,y2)
bottom=min(y1+sy1,y2+sy2)



t1=(top-y1)
t2=(top-y2)

For x=Left To Right-1
i1#=((x-x1)*sy1+t1)/8
i2#=((x-x2)*sy2+t2)/8
f1=i1 Mod 8
f2=i2 Mod 8
If f1-f2<0
f1=Abs(f1-f2)
f2=0
Else
f2=Abs(f1-f2)
f1=0
EndIf
;i1=i1
For y=top To bottom-1 Step 8
;n1%=PeekByte(image1,i1 Shr 3+8) And 1 Shl f1
;n2%=PeekByte(image2,i2 Shr 3+8) And 1 Shl f2
;If n1>0 And n2>0 Then Return 1


;If debug_c=0
;If (PeekByte(image1,i1 Shr 3+8) And 1 Shl f1)>0 And (PeekByte(image2,i2 Shr 3+8) And 1 Shl f2)>0 Then Return 1
;Else
; If (PeekByte(image1,i1 Shr 3+8) And 1 Shl f1)>0 And (PeekByte(image2,i2 Shr 3+8) And 1 Shl f2)>0 Then Plot x,y
;EndIf


If (PeekByte(image1,i1+8) Shl f1) And (PeekByte(image2,i2+8) Shl f2)
; f1=i1 Mod 8
; f2=i2 Mod 8

;Plot x,y
                                return 1
;r=1
;If (PeekByte(image1,i1 Shr 3+8) And 1) Shl f1>0 And (PeekByte(image2,i2 Shr 3+8) And 1 Shl f2)>0 Then Return 1;Plot x,y
EndIf
i1=i1+1
i2=i2+1

;f1=f1+1
;f2=f2+1
;If f1>7 Then f1=0
;If f2>7 Then f2=0
Next
Next
Return 0;r
End Function


Function min(v1,v2)

If v2>v1 Then Return v1
Return v2

End Function

Function max(v1,v2)

If v1>v2 Then Return v1
Return v2

End Function


[va!n]

The closest i can get is this:
white is where it found a collision outside the image and blue is the image I'm checking against.

@paul:
i know this methode from the amiga where obj had a visible black outline for example to detect if there is any collision or not, like in 32k games by abyss on amiga.

This way would work if all objects are moving only 1pxl each frame. The problem is, if a object is moving for example +2 or +4 pxl one frame (to speed up ship moving)... the you jump over the outline and collision would return false.

possible something for you:
http://imrtechnology.ngemu.com/downloads/tutorial.pdf
http://nightschool.near-time.net/news/2007/8/6/continuous-swept-collision-in-2d

[Jim]

Paul, can you post your test images?
You will find it easier to write the code if you keep one mask unshifted and just shift the other mask relative to it before doing the AND.  It looks to me like you're trying to shift both at the same time.

Jim

[stormbringer]

Paul, instead of your recursive algorithm I was thinking to use a pyramid of masks (like mip-map, but for collision masks). Depending on the number of levels in your pyramids, you could start with a coarse detection at say a resolution of 1/16, this will give you the area where you need to test in the next, larger level of your pyramid, etc until you reach he 1:1 resolution collision mask. This will consume some extra memory (who cares??) and limit the search for the pixels to test. Also mip-maps can be easily generated with modern hardware...