Un-transformed Rectangle Collisions

BlitzMax Forums/BlitzMax Beginners Area/Un-transformed Rectangle Collisions

lukehedman(Posted 2009) [#1]
My current project is a simple physics engine. So far I have sphere to sphere collision detection and response working. Before I expand to lines and polygons, I want to optimize the routines a bit.

My plan is to create a bounding box check. If it fails, no sphere checks need to be made, and thus I can avoid have to find the square root of anything or use sines.

What I would like to do is create two rectangles for each sphere in a collision check. The first would be for the sphere's current position, and the second would be its position the next logic step. Each would be the size of the sphere's diameter. I would then want to merge these two into a larger box. Finally the expanded boxes of each instance would be checked to see of they overlap.

Yes, I know it's kind of ironic. I can handle spherical collision physics, but I need help making a simple, unrotated box. The thing is, I have some ideas of how to hack one together, but they're very messy. If someone could guide me to a simple solution, it would be appreciated.

I already searched the forums and code archives, but didn't find what I was looking for. Pointing me to something I missed would be helpful as well.

Thanks!


Who was John Galt?(Posted 2009) [#2]
Hi,

For spheres, if you just check (distance^2)>(combined radius^2), i.e. compare squares of length rather than length, it should be pretty much as fast as a box check, I'm guessing. You may have to use r*r rather than r^2 for speed optimization.


ImaginaryHuman(Posted 2009) [#3]
In some circles, no pun intended, sphere collisions are thought to be more efficient to check than rectangles.

You can approximate (quite loosely) a circle collision by finding the difference between the two circle centers with a simple subtract operation like CenterX1-CenterX2, and CenterY1-CenterY2. If you add those together, ie Distance=(CenterX1-CenterX2)+(CenterY1-CenterY2) and then check if the result is less than a certain threshold (use Abs() too), it will activate the need to check accurately for a collision only when the circles are pretty close to each other. That's one option.

As to your rectangle thing, you have explained quite clearly the steps you need to take to build the bounding rectangle so I'm not sure what problem you're having turning it into code? It's quite simple. The total bounding rectangle will be:

TopLeftX=Min(CenterX1-Radius1,CenterX2-Radius2)
TopLeftY=Min(CenterY1-Radius1,CenterY2-Radius2)
BottomRightX=Max(CenterX1+Radius1,CenterX2+Radius2)
BottomRightY=Max(CenterY1+Radius1,CenterY2+Radius2)

These four variables then define the top left and bottom right corners of the rectangle. Is that what you wanted?


lukehedman(Posted 2009) [#4]
Thanks for the replies guys!

ImaginaryHuman: Your first example was what I was looking for. I didn't actually want to create a rectangle, but check for collisions in a rectangular area. I guess I should have been more clear. The bit of code you gave worked wonderfully, and I was able to build a quick test program.

Here it is. Just paste it into your compiler.


SuperStrict

SeedRnd(MilliSecs())

Global ScreenWidth:Int = 1024
Global ScreenHeight:Int = 768

Global RectList:TList = New TList

Type TRect

	Field X:Double
	Field Y:Double
	Field Radius:Double
	Field Colliding:Byte
	
	Method MStart()
	
		X = Rnd(0, ScreenWidth)
		Y = Rnd(0, ScreenHeight)
		Radius = Rnd(16, 64)
	
	End Method
	
	Method MUpdate()
	
		Colliding = 0
	
		For Local Rect:TRect = EachIn RectList
	
			If Rect <> Self
			
				Local RadiusAdd:Double = Radius + Rect.Radius
				Local XDiff:Double = Abs(X - Rect.X)
				Local YDiff:Double = Abs(Y - Rect.Y)
				
				If XDiff <= RadiusAdd
				
					If YDiff <= RadiusAdd
				
						Colliding = 1
				
					End If
				
				End If

			End If
			
		Next
	
	End Method
	
	Method MDraw()
	
		SetBlend(ALPHABLEND)
		
		If Colliding = 1
		
			SetAlpha(.5)
			
		Else
		
			SetAlpha(1)
			
		End If
		
		DrawRect(X - Radius, Y - Radius, Radius * 2, Radius * 2)
	
	End Method

End Type

Graphics(ScreenWidth, ScreenHeight)

Local Count:Int

Repeat

	Count :+ 1
	Local Rect:TRect = New TRect
	ListAddLast(RectList, Rect)
	Rect.MStart()

Until Count >= 20

While Not KeyDown(KEY_ESCAPE)

	Cls

	For Local Rect:TRect = EachIn RectList
	
		Rect.MUpdate()
		
		
		Rect.MDraw()
		
	Next
	
	Flip

Wend



A little messy I know, but it's just a quick prototype. And yes, I know one really doesn't use radius with a rectangle, but I was thinking of using the properties that the spheres would already have to make the calculations.

Thanks again for the quick replies!