DrDeath3191

Continuous Collision Detection of Scaling AABBs

Recommended Posts

Hello,

I have been doing some research on continuous collision solutions, because I intend to have fast-moving bullets. However, the AABBs of these bullets may change in scale, either by scaling directly or rotation of the underlying object. From what I've seen in my searches, continuous collision solutions such as Minkowski Difference and Separating Axis Theorem take the scale of the shape to be constant (if I am wrong about that, please let me know). So I'm at a bit of a loss as to what the correct solution is. I do have a couple of thoughts, but I'm not a fan of them;

 

The easiest solution would be to create another AABB that encompasses the previous frame's and the current frame's AABB. This would not be the most accurate (though I don't really need it to be I suppose), but the bigger issue is how to determine the time of intersection, which I need to sort the collisions.

 

My next thought is to create line segments for each vertex in both AABBs from their positions in the previous frame to the current frame, then check these line segments for intersections. This would make getting the time of intersection simple (I think), but it strikes me as monstrously inefficient.

 

The other thought I had was creating a swept shape of the AABBs, and then using the Separating Axis Theorem to find collisions with the swept shapes. This is accurate, and highly used from what I understand, but I don't know how I would get the time of intersection, seeing as the scale of the AABB could easily change between frames.

 

I don't plan on making a super-complex physics simulation; I don't need the minimum translation vector, the contact normal, or any of that. I just need to see that there was a collision, and when in the time-step it happened. If I am overthinking any of this, I sure would like to know. I've been wracking my brain on this for the last few days, and been feeling like a complete moron.

 

Thanks in advance for any help!

Share this post


Link to post
Share on other sites

There are two things to consider to solve this. The first is that you build the swept AABB and then do continuous sweep against all potentially overlapping objects. If the other objects are moving as well you need to test against their swept AABB too. Note that there is a limit of 90 degrees rotation per tick for the swept AABB. After that it can shrink again. That is why you find limits on the allowed rotation per tick in most physics engines.

Erin Catto gave a presentation about CCD. His algorithm should be able to handle at least uniform scale. I thought about this in the context of camera occlusion query, but then decided it was not worth the hassle. Still it should work.

http://box2d.org/files/GDC2013/ErinCatto_GDC2013.zip

Share this post


Link to post
Share on other sites
22 hours ago, DonDickieD said:

There are two things to consider to solve this. The first is that you build the swept AABB and then do continuous sweep against all potentially overlapping objects. If the other objects are moving as well you need to test against their swept AABB too. Note that there is a limit of 90 degrees rotation per tick for the swept AABB. After that it can shrink again. That is why you find limits on the allowed rotation per tick in most physics engines.

Yes, I figured that much out at least. The issue is, how do I get the time of intersection in this case?

 

22 hours ago, DonDickieD said:

Erin Catto gave a presentation about CCD. His algorithm should be able to handle at least uniform scale. I thought about this in the context of camera occlusion query, but then decided it was not worth the hassle. Still it should work.

http://box2d.org/files/GDC2013/ErinCatto_GDC2013.zip

Please pardon me if I am not quite understanding, but do you believe this algorithm would not handle non-uniform scaling well? Because recalculating an AABB after rotation could very easily result in non-uniform scaling.

 

I may have to read that paper a few times more to make sure I understand it, but it seems like overkill for what I need. I'm not well versed in this stuff, so I may be completely wrong, but I would imagine that the AABB case would have been a little simpler. Perhaps some false hope on my part?

Share this post


Link to post
Share on other sites
Quote

The issue is, how do I get the time of intersection in this case?

I don't think you can get the intersection time this way.

Quote

Please pardon me if I am not quite understanding, but do you believe this algorithm would not handle non-uniform scaling well?

I think it would, but I haven't tried it.

Quote

 Perhaps some false hope on my part?

Sorry, but I think so. The TOI between two rotating AABB (which makes them essentially OBB) which are potentially also scaling has no simple solution (at least I am not aware of it). The only algorithm I know from the back of my head would be conservative advancement. If you had two AABB which were purely translating this would be indeed much simpler. Once you have also rotations it becomes a very tough problem.

Edited by DonDickieD

Share this post


Link to post
Share on other sites
6 hours ago, DonDickieD said:

Sorry, but I think so. The TOI between two rotating AABB (which makes them essentially OBB) which are potentially also scaling has no simple solution (at least I am not aware of it). The only algorithm I know from the back of my head would be conservative advancement. If you had two AABB which were purely translating this would be indeed much simpler. Once you have also rotations it becomes a very tough problem.

Well, that sucks. However, I still hold onto at least a slight thread of hope, because I think you misunderstood what I meant when I mentioned rotation earlier. If I was using the rotated AABB as a bounding box, I would have agreed immediately that I'm pretty much screwed. However, what I was talking about was building a new AABB based on the rotation; meaning that for all intents and purposes no rotation takes place at all for the collision check. Like I said, I'm not trying to make the world's most accurate physics simulation; I can be a little generous. So hopefully that leaves me marginally less screwed.

 

If that hope is misplaced, I may have to reconsider the fast moving projectiles for now, at least until I feel more comfortable with collision detection logic.

 

Thanks for all your help.

Share this post


Link to post
Share on other sites

It all depends on the scaling involved. If the scaling happens at a constant rate, then you can write down a closed-form solution. If the scaling is undulating in a non-linear fashion, a more exhaustive search would be necessary, which could require a more complicated algorithm.

The problem with an OBB rotating and wrapped in a new AABB is that the new AABB can still grow and shrink in an unpredictable and non-linear fashion. The edge of an AABB can be approaching a collision, and then move away slightly, and then swing back and cause a collision. This is not something a simple closed-form sweep can solve.

Share this post


Link to post
Share on other sites

So I've thought about it some more, and I struck up upon an idea. Maybe good, maybe bad, not sure.

The problem I had with my second plan was that I would have to perform 16 checks, one for each vertex on each box (the box is in 3D, sorry I didn't mention that). However, I think I really only need to check 2; the closest vertices on each box. So if I perform an interpolation of the nearest two vertices' paths in the frame, I can find a time where the line segments would intersect.

The only case that I can currently think of that would break this is rotation, because the nearest points might not be the first ones that generate a collision. But I am specifically using AABBs, so there is no rotation to consider.

Does that sound reasonable?

Share this post


Link to post
Share on other sites

I've been off the net for the past few days, which is why its taken me a while to post again. I understand the paper a bit more, and it seems compelling. However, I wonder if perhaps just doing a binary search would be better in the case of AABBs.

 

I would do something akin to the paper; I could start with two variables, t0 = 0, t1 = 1. Take the midpoint of t0 and t1, and calculate the state of the AABBs of interest at that point. Then, create an encompassing AABB which covers the t0 and midpoint rectangles of each collider. If they collide set t1 to the midpoint, otherwise set t0 to the midpoint. Repeat until the bracket is sufficiently small, and return t0.

 

It seems to me that just doing a bunch of AABB collision checks would be faster than having to recalculate the closest features multiple times. Am I wrong?

 

Of course, there is always the option of just having slower moving projectiles. I've been spinning in my analysis paralysis for a while, as you can probably tell.

Share this post


Link to post
Share on other sites

I haven't implemented this myself, but I think you can just compute the TOI along each axis. Then sort in descending order (lower TOIs first). Advance the AABB to each TOI and check if the box is also overlapping along the other axes at that time. If they do you have found the TOI.

As mentioned I never tested this, but it should work something along those lines. Also, you can just buy Christer's book 'Real-Time Collision Detection' which has a solution for moving AABB.

Edited by DonDickieD

Share this post


Link to post
Share on other sites
17 hours ago, Randy Gaul said:

Dirk mentioned "conservative advancement" and it sounds like you have yet to look it up.

You are correct, it seems I missed that. Apologies to Dirk. So the idea is that I calculate the minimum distance vector between the colliders shapes, and find when in the timestep a vertex moves more than that amount projected on that vector, am I understanding that correctly?

 

16 hours ago, DonDickieD said:

I haven't implemented this myself, but I think you can just compute the TOI along each axis. Then sort in descending order (lower TOIs first). Advance the AABB to each TOI and check if the box is also overlapping along the other axes at that time. If they do you have found the TOI.

As mentioned I never tested this, but it should work something along those lines.

This seems simple enough for me to get my head around. But why would you bother checking anything other than the maximum TOI? Doesn't the fact that one axis has a higher TOI imply that the lower ones couldn't possibly be correct?

 

16 hours ago, DonDickieD said:

Also, you can just buy Christer's book 'Real-Time Collision Detection' which has a solution for moving AABB.

Placing an order as we speak.

Share this post


Link to post
Share on other sites

Because you need to also overlap along the other axes. Here is an example. You first hit the vertical line (which is the lowest TOI), but you are not actually touching yet. 

image.png.f8e78ace3dd5bcfc56da2eb7f13c6d4a.png

As an exercise also try to imagine the case where you first hit the vertical line, then the horizontal line, but actually never hit the other AABB.

Share this post


Link to post
Share on other sites
19 hours ago, DonDickieD said:

Because you need to also overlap along the other axes. Here is an example. You first hit the vertical line (which is the lowest TOI), but you are not actually touching yet. 

As an exercise also try to imagine the case where you first hit the vertical line, then the horizontal line, but actually never hit the other AABB.

Yes, but you hit the horizontal line second, so why even test the vertical? Even in the case where you cross both axes and miss, you only need to test the last one to determine the intersection never happened.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now