Un-transformed Rectangle Collisions
BlitzMax Forums/BlitzMax Beginners Area/Un-transformed Rectangle Collisions
| ||
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! |
| ||
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. |
| ||
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? |
| ||
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! |