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!

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

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?

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.

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.

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.

If you are just linearly sweeping AABB you can think of it as a sphere cast per axis. 

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?

If the underlying OBB is rotating you cannot lerp vertices linearly.

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.