Implement Continuous Collision Detection (CCD)

[controllerface]

I have put this on the back burner for a while now, but I think it is time to start tackling CCD in the physics simulation. This is one of the big things that will be needed to push the physics code up into "game ready" territory. As such, it's likely going to be one of the more challenging things I've done. Op top of it being difficult to get right, I will probably need to come up with a novel, or at least, unconventional approach to this in order for it to work in my simulation.

Most literature on this topic talks about sweeping a volume between two states of an entity, and this make a lot of sense when you're dealing with objects and not their constituent points. In my case though, I am dealing with points so any approach that assumes operation on entire entities isn't going to translate exactly.

I have been thinking about this for a while though, and I think I have an idea that may work. Fundamental to the CCD process is essentially finding the "first time of collision" and essentially "rewinding " the entity to that time, and then allowing the normal collision process to take place. This is sensible, and I will try to implement something that has this effect, but rather than "brute force" it with a binary search, I am hoping I can instead leverage the existing collision code, but have it give me a different type of output than what I have now, which are the reaction buffers.

I do need to track reactions, but not in the same way as the existing collision, which adds all the logic for friction, restitution, etc. Instead, my hope is to take all the points in an entity, and draw lines between their current and previous position, then consider that line a physics body and run collision on it. Then instead of having the collisions reacted to directly, I want to find the earliest DT value where a collision occurs, perhaps using a parallel minimum scan, and then adjust all of the points in the entity back to that time.

This rewind process will have to move the current and previous values back to that point in order to preserve momentum, and crucially, I need to make sure that when there is a collision detected this way, the position after adjustment ensures the body is still colliding, so that the normal collision process takes effect.

[controllerface]

OK, so the first thing is going to be figuring out how to tag an entity to it gets processed for CCD. To start, I will simply always grab the player entity, but I should allow for a velocity check at some point.

Generally, I want to assume that not every point will require CCD, so I don't want to just add AABB boxes to every point. Instead, I need to come up with some kind of per-frame map that tracks where the AABBs for the points for an entity are stored, and have this filled in every frame.

Though thinking about that for a second, it would require a GPU read in order to ensure buffer capacity. That could tank performance too much, and so it may make sense to simply have a buffer for this that is sized for all points. If that is the case, then it may actually make sense to just give every point and AABB and only use it when that point is moving fast enough. I will need to balance memory usage over speed, and I am going to be very speed sensitive in doing this, as it can be computationally expensive.

[controllerface]

I think my first order of business should be to do some cleanup on the physics class, and move it tot he buffer group style used in the other classes. This will help me determine how much space is used for each object so I can make informed decisions about space.

[controllerface]

moved the physics class over to using proper buffers and wired up a very basic test line mesh, just to make sure it would interact with the physics system, which it does. It's a little wonky in terms of reactions because single lines were never something I added support for, but it is enough to know they will interaction with the collision code as-is, I don't actually want them to react anyway, just collide and provide contact point information.

[controllerface]

Already found one thing that I need to adjust before this work can move forward. Right now, the AABB calculation process is coupled to the integration process. However, once CCD is in place, any hulls that get moved will need to have their AABB recalculated. Since it would be wasteful to do that process twice, it makes more sense to break it out to a separate kernel and call it after integration. Then once CCD is in place, I can just further delay it until after CCD is performed.

[controllerface]

well, not only was splitting up the logic for AAB calculation easy, but it also came with a decent FPS boost in the debugger. I am definitely going to be eyeballing any complex kernels and trying to break them down. Event looping all the points twice, which is what happens now that the AABB calc is done after integration, it's just more performant because there's less work done in each kernel.

[controllerface]

Got a little excited, there was a very modest FPS increase but IU forgot I had tweaked the world gen before testing in a way that made fewer objects generate. I set the values back to what it was prior and with the separate kernels it does still look like there's a minor FPS boost, but it's not as big as I thought at first. Still, something is better than nothing.

Started writing out TODOs for the CCD stuff, and immediately have a thought about how to change this a bit from my original idea. Instead of simply running the full AABB and SAT kernels as they are now, I want to see if I can make a CCD kernel that does the AABB logic, but then jumps right into an SAT collision check, rather than split them up. I will need a different collision function anyway, and this way I won't need to add special logic to the existing SAT or AABB kernels.

Hopefully, I can also cut out a bit of GPU->CPU back and forth by doing this all in one shot. Basically I should just need to make a modified copy of the AABB kernel that avoids using the match buffer, and instead just does the SAT check right there. Instead of a modification to the point position, it will store the computed "contact rewind" value in a buffer aligned with the point, and then a final kernel can run that finds the earliest rewind and applies it to the entity.

[controllerface]

Ok, already realized a flaw here, I need to have the normal AABBs built first, otherwise, the point-line AABBs won't have anything to match against. Now, I guess I could walk this back a bit, and say only do CCD with static objects, and in that case, only generate the static AABBs and then the point-line AABBs and collide that way... but I want to think on this. May just say screw it and try to integrate these AABB's into the normal process as I originally thought, but just make that process run in two stages, with an AABB re-calculate step in between. Looking at the debug data, calculating the hull AABBs is cheap, only 3 ms, so i think i can get away with doing it that way. Perhaps even combine the re-calculate step with the rewind step, since they will need to operate on the points in a loop in both cases.

[controllerface]

More experimentation has led me back to where I was before, with a completely separate step up front, but not one that relies on the hull AABBs. Instead, what i actually need is the point AABBs, and Edge AABBs. I need to do the checks against those first, resolve any adjustments, and then do the normal collision, without touching it at all. This is the only way I can see to make this work correctly.

Doing some initial work to get the point AABBs generated, which was successful I quickly came across the issue that the key banks rely too much on hull offsets. I can't easily integrate the points and for that matter, the edges, into that bank. I need completely separate banks. And now, I need to figure out how to allow collisions between two banks. In this case, I need to check the point-line banks only against the edge banks. Neither the point nor edge banks need to be checked against themselves.

This means I need to add more buffers, but I am OK with it. The points are pretty numerous and don't really add too much to the run-time memory usage, so I don't expect edges will add that much more either. I will need to add another debug renderer for these bounding boxes as well, so i can make sure everything is generated correctly.

[controllerface]

Well, that's not going to work. Calculating everything for the points and edges proved too computationally expensive. But i did figure out a possible way to allow to keymaps to work together, so i can go back to trying to work the point-lines into the normal AABB process again.

[controllerface]

Sleeping on this, I'm coming back to possibly a separate point-line/edge check once again. After trying again to integrate the point-lines into the normal process, I realized it was doomed from the start, because all of the logic there expects hulls. I kept overlooking that. I have reverted to a state where I am generating the bounds for point-lines and edges again, and will see if I can incrementally add more logic slowly until I have something that could be a bit more workable.

I will need some type of filtering in place for sure though, I do plan on at least trying to implement this so that it's "always on" just to kind of prove it out, with the expectation that it won't be very fast, but I am hopeful it will at least run in that state, so I can then add filtering afterward.

[controllerface]

Well I have it "working" but it doesn't seem to do what I had hoped. I tried a few different things to see if it had something to do with the boundaries being too small, and in fact that may be the issue, but in any case the collisions between the point-lines and the edges just don't happen when I expect.

So back to the drawing board I guess. I think I will try a different approach where I grab hulls, and make bounding boxes around their entire forms, including the previous positions of their points, and try doing collision on both the normal and "CCD" bounding boxes, with the CCD one occurring first. It may make things a bit easier since they will be aligned with hulls already.

Alternatively, I could do this at the entity level as well, which could make things a little slower up front, due to the nested loops, but would reduce the number of checks needed for the actual CCD portion. Will consider both...

[controllerface]

Alright, I think I have another idea. Trying to mix different types like points/edges/hulls, etc. is just asking for trouble. But I think I can refactor my concept in terms of just edges, and see about replicating the existing hull AABB check, but with edges.

I can run a kernel hat generates an AABB for an edge, such that if the edge is static, it simply builds the box around the two points (plus maybe a very small amount padding to account for FP imprecision) and if the edge is non-static, it does the same, but builds the box around the points, and includes the previous location value of those points. Then, I should be able to copy the hull approach and just apply it to edges. This has the benefit of being able to apply some of the existing techniques to avoid duplicates, like smaller/greater indices, and being able to filter out edges on the same entity, as well as avoid static/static checks.

Once I have those collisions being done, I can modify the logic so instead of doing the SAT check, it does a new CCD check, which is designed specifically for line/line collision tests, which can be a lot quicker. I will arrange it so there is always only one static and one non-static edge, just for simplicity, and that will remove the need to deal with moving bodies. That does mean CCD will not happen between moving entities, but I am OK with that for now, and logic can be added later to handle that, much like the current SAT process which filters down to specific collision functions based on the bodies that are colliding.

When an edge is static, it will not be adjusted, and only serve as a collision barrier. The non-static edge will have two lines generated from it, one for each point, using it's current and previous value. These can then both be checked against the static edge. If one is found to be colliding, I will calculate the point between the previous and current position, and map that to a time delta. This will be the amount of "rewind" that needs to be applied to that point in order to put it at the time of collision.

Because edges share points, this does mean that the same point may be processed more than once, and one colliding edge may be closer to a point's previous location than a different edge that it's point-line would also collide with. Because of this, I think the best approach would be to align this "rewind buffer" with points, and use an atomic max check to set it. This will be a little tricky, since that means the value must be an integer, but simply treating the DT value as if it were a very small scale and rounding should suffice. I don't actually need exact precision, just close enough to avoid tunneling. There are also some tricks to get atomic float max working, so i can look into that as well.

[controllerface]

The edge based approach is already going better, I have a kernel that correctly does AABB detection on edges as I planned, and the very simple edge intersection test appears to be working. Crucially, when the player starts in the air, and there's no collisions, there's no collisions printed, then when hitting the floor, and while standing on the floor collisions are printed. Also, walking to the left to spawn in the shards that fall to the ground under the surface shows those colliding as expected. Now I can move on to the next step.

I need to add a new buffer aligned with points to store the re-wind value. I decided that just for quick and dirty testing, I'm not going to worry about it being atomic, and just let whatever value is there be set. I know this is a temporary solution but it has worked in the past just to try things out, and in this case the effect should be very subtle, so I don't expect it would cause crazy behavior. I should be able to validate at least that the core concept works before putting in the work to make it atomic.

So, I need to actually figure out what this time rewind will be. It will be a float, since that is what dt is, and my initial thought is to have it be a value that essentially says "rewind this much" so that a 0 value does nothing, and a 100 value would move the current point all the way to the previous point.

[controllerface]

Still haven't set up the point aligned buffer yet, but I have in place a working function to determine the intersection point between two lines. Running this code in my CCD check, and verifying the output against some online resources, it appears to be working correctly, and the numbers generally pass the sniff test.

I have a couple thoughts on how to go about this now. I can stick with the original idea of storing a "rewind amount" or I could possibly just store the exact point to which the current X,Y value needs to be set. Then when adjusting, I could simply find the diff between new and old and apply that to the previous position. Though... that may be harder to make atomic later...

I will sleep on it and pick this back up tomorrow.

[controllerface]

Well... I got it all working. Set up a test for running through a 1 pixel wide wall and... it doesn't really help much. You can still go through the wall. A/B testing with it on/off does look a little bit like is less likely to clip through, but it doesn't seem to really do much.

I will tinker with the values and see if I'm doing something wrong, but I am not certain this approach will work now. Might just have to abandon it and move on.

[controllerface]

so, thinking this through a bit, there's a chance that part of the issue is really the player's animation entity. I know that the way I add up all the movements and apply them to the entity point causes issues in other places, like with friction. So it is possible this would work if I used a bounding box for animated entities. Which is something I've considered for a while now, but haven't put too much time into as I was hoping this effort would help with that kind of thing. But i guess this points me toward possibly investigating that a bit more.

It is also possible that I could do something similar for entities where they get some reaction adjustment after the points do, but that also could get messy. I think for now, I'm going to leave the code in place, but just disable it. I will continues to think about how I might be able to use the logic for entities directly, that may be a better option.