Kinetic Sweep & Prune

[ED209]

Im having some problems to understand how kinetic sweep and prune works. After reading http://graphics.idav.ucdavis.edu/~dcomi ... phys05.pdf and http://www.dtecta.com/papers/gdc2006_va ... cs_Tut.pps i still don't understand the general idea of the algorithm.

This is what i think i do understand: each axis (x,y,z) contains a list of endpoints and a priority que. Each frame and for each axis i go thrue the endpointlist and for each adjicent endpoint pair i compute a posible swap by predicting new positions for those endpoints and compute time of the swap. Each of those swaps i place in a priority que where the smallest time of the swap is treated as a priority.

But what does this priority que represent and how should i process the swaped pair?

How do i work together with the other two axises when it comes to check if the intervals are overlaping in all axises like in original axis sweep?

The endpoint lists still need to be sorted, but when i move endpoints and resort the endpointlist im back at the original sweep and prune so what is the point on looking at relative movement of the endpoints?

In Don's paper he talks about to not update the endpoints as long as you can compute the position based on a position(time) function, but how would you manage to do that in a physical simulation where you have to integrate new positions because you can't construct a function that describes the movement of objects in the system (or can you?). I prefer to implement the kinetic sweep based on Gino's idea so i guess i don't have to concider that problem yet.

Its hard to even make a prototype of the algorithm without even understanding the basic idea and especialy what makes the kinetic aproach faster then the original axis sweep.

If someone understand those papers better than me or even implemented those techniques it would be very nice if you could provide a better explanation.

[dcoming]

Im having some problems to understand how kinetic sweep and prune works. After reading http://graphics.idav.ucdavis.edu/~dcomi ... phys05.pdf and http://www.dtecta.com/papers/gdc2006_va ... cs_Tut.pps i still don't understand the general idea of the algorithm.

You may find better luck with this preprint of the journal version of my above-mentioned paper. I was personally happier with the presentation and level of detail permitted in the extended format:
http://graphics.idav.ucdavis.edu/~dcomi ... inetic.pdf

This is what i think i do understand: each axis (x,y,z) contains a list of endpoints and a priority que. Each frame and for each axis i go thrue the endpointlist and for each adjicent endpoint pair i compute a posible swap by predicting new positions for those endpoints and compute time of the swap.

I think you have a few details mixed between Gino's method and my own.
(Gino, feel free to correct any details I botch)
Gino's method uses one priority queue for swaps on all lists, but I use Basch's kinetic sorted lists (each of which you can think of as a sorted list and a priority queue for swaps). With my method: after the first frame, there is never a need to traverse the endpoint lists. Updates are only made as necessary. Last I knew, Gino's method traverses like you said, building predictions for each frame. We had a lengthy discussion on the differences here:
http://continuousphysics.com/Bullet/php ... .php?t=178

Each of those swaps i place in a priority que where the smallest time of the swap is treated as a priority.

But what does this priority que represent and how should i process the swaped pair?

The priority queue represents the schedule of swaps to be performed. It just orders the swaps by time. The swap that matters first is the one with the earliest time. Perform that swap as in the original method (i.e., a swap has the usual meaning re: interval/AABB overlaps); then there is some scheduling due to changes in adjacencies (more detailed in the journal version).

How do i work together with the other two axises when it comes to check if the intervals are overlaping in all axises like in original axis sweep?

This should be the same.

The endpoint lists still need to be sorted, but when i move endpoints and resort the endpointlist im back at the original sweep and prune so what is the point on looking at relative movement of the endpoints?

Both Gino's approach and my own keep the lists sorted by performing the swaps in the order provided by the priority queue(s). You should not require any further sorting operations for continuously moving objects. If an object has a discontinuous jump, then you can sort it into its new place without scheduling each swap along the way (they all happen atomically).

In Dan's paper he talks about to not update the endpoints as long as you can compute the position based on a position(time) function, but how would you manage to do that in a physical simulation where you have to integrate new positions because you can't construct a function that describes the movement of objects in the system (or can you?).

You don't have to be too exact with the motion function for the endpoints; they need only be conservative, that they always contain the object. With this relaxation, its simple enough to make a prediction and correct once it loses that conservative property. For practical application of such prediction/correction for motion-tracking situations, see the siggraph 2001 coursenotes on Kalman filters. Synthetic scenes are usually nicer, since you define the laws of motion. Also keep in mind that your endpoint motion does not have to be valid for the infinite future, at least for kinetic sorted lists (see BASCH J., GUIBAS L. J., HERSHBERGER J.:
Data structures for mobile data. Journal of Algorithms
31, 1 (April 1999), 1?28.).

Its hard to even make a prototype of the algorithm without even understanding the basic idea and especialy what makes the kinetic aproach faster then the original axis sweep.

The savings are two-fold. First, both Gino's approach and mine make the overall continuous collision detection pipeline faster, by improving the pruning quality versus a static AABB that encloses a swept object.
Second, as previously mentioned, my method can reduce broad phase update costs to negligible amounts (these results were presented more clearly in the journal version).

Best wishes with either implementation.

[ED209]

Thanks alot for the answer, I think I got some more meat on my legs now. But I still look like question mark (you should se me).

One thing that i sudennly stuck on is how you should handle insertions and removals of objects. In a game enviroment there is alot of situations where you modify position and orientation (orientation is not a problem tho) by for example take an object and place it somwhare else. Its verry hard to understand how that case should be treated (how you should update the priority que).

For example: you predicted a new position based on time for an object, that may have resulted in some swaps witch was placed in the priority que. But in the next frame someone took that object and placed it in a totaly new position. So now you have a swap in the priority que that was supose to hapen if the object was not manualy placed to another position. That swap must have been invalidated. I think there is some big point i have missed.

I don't think you will be able to utilize the idea behind Dan's aproach where you only update when there is a collision or a change in the movement function in a dynamic game enviroment where basicaly you have state changes in each frame not including some koherence that might be present. How do you even predict how big the time interval you have to use to build the swap events (espesialy at simulation start).

Maybe im just not smart enougth to understand it so i think i will wait untill someone implements an example or some pseudocode.

[Erwin Coumans]

But in the next frame someone took that object and placed it in a totaly new position.

This sounds like a totally in-coherent motion. You probably don't want to catch any collision between old and new positions at all.

So the choice is to handle this 'reset' of positions by either the coherent 'kinetic' sweep and prune, or by just adding and removing it (as a 'new' broadphase entry), isn't it?
Just curious, what causes this 'new' position?

[dcoming]

Maybe it would help if I cast Gino's 4D sweep and prune into my kinetic sweep and prune, if you're following that one better. Your setting is that you know starting and ending positions of an object and linearly interpolate positions between them over time. The motions of list elements are, likewise, linearly interpolated between the two times.
The 'predictions' are not so much predictions in this setting, since they are all for times between the past frame and current. They are just swap times to help you order the swaps. If a collision were to happen mid-step, then a few of these scheduled swap times will change, among those not yet performed. Now just calculate each prediction at each time step (with an upper bound as the end of the time step), queue them up, and process them in time-sequential order until the queue is empty. That is a case of my method performing Gino's. Begin the differences:

Now, consider why you had to generate/update each prediction at each time step: the upper bound on the predictions. This upper bound meant that the queue was emptied by the end of each time step and had to be re-created at the beginning of each time step. If the path an object would travel in the next time step was completely random and independent of its path in the previous/current time steps, then that's the best you can do. If there is some motion coherence, then you can lift the upper bound on predictions as high as keeps you comfortable, and now they truly are 'predictions' into future frames. Note that in this linear case, there is no extra work in calculating predictions when the upper bound is lifted to infinity. The swaps still won't happen until future frames, but this lifts the need to re-evaluate many predictions that didn't change (e.g., stationary objects, groups moving together, pretty much between any two objects that weren't abruptly redirected as in collisions).

In this framework, linear motion could be rather limited, as it would require re-evaluation of predictions every time that gravity was applied. Thus its beneficial to consider higher order motions, at least quadratic for gravity's sake, so that predictions are worth keeping into the next frame.

Also, remember that the only swap predictions you keep track of are for adjacent list elements. This includes any operation that changes the list order (swap, insert, remove, splice). Anytime a pair of elements are no longer adjacent, remove the prediction for their swap. Likewise, if a pair of elements become adjacent in a list, schedule a prediction for their swap.

how you should handle insertions and removals of objects.

For inserting/removing from lists and finding overlaps, handle them like you would with any other sweep and prune. With a few scheduling considerations:
An inserted element (except at the endpoints) goes between two adjacent elements, making them no longer adjacent; deschedule accordingly. Further, the inserted element is now adjacent to either one or two elements; schedule accordingly.
Removals are the compliment of insertions; the removed element should have its swaps descheduled, and unless it was at an endpoint, its former neighbors become adjacent to each other, so schedule a prediction for them.

For example: you predicted a new position based on time for an object, that may have resulted in some swaps witch was placed in the priority que. But in the next frame someone took that object and placed it in a totaly new position. So now you have a swap in the priority que that was supose to hapen if the object was not manualy placed to another position. That swap must have been invalidated. I think there is some big point i have missed.

Correct, swaps are invalidated by discontinuous re-placement of an object. You could treat it as a removal & insertion of the object (regarding the predictions), with many options for how to handle actually moving the elements to their new positions. For small jumps, I typically just atomically perform a splice, noting overlaps as you find the new position. A key tenet of either method is to maintain that the lists are always sorted, even at a simulation time between two discrete rendering/simulation time steps.

How do you even predict how big the time interval you have to use to build the swap events (espesialy at simulation start).

I think I covered this, but infinity works You're not committed to performing these swaps until simulation time catches up with the predictions. If your prediction needs to change in the meantime, its easy enough to change its key within certain priority queue.

Maybe im just not smart enougth to understand it so i think i will wait untill someone implements an example or some pseudocode.

No need to get down on yourself. I think you have a pretty good grasp of it now, but an implementation example would help indeed. I'd like to open source the whole thing when I get time to factor it out of some other parts that are not ready to be revealed.

[ED209]

Thanks again for the answer, i think i start to understand now, just needed some time to melt it down.

Erwin Coumans: Just curious, what causes this 'new' position?

Im not sure maybe it never hapens but maybe if for example when you edit objects in a game editor or by user interaction (as mentioned in Don's paper) or reset objects to some initial state.

Big credit to both Don and Gino presenting theese new ideas!

I think the broadphase is a very important optimization part of a collision system and theese new techniques looks very promasing.

[dcoming]

Thanks again for the answer, i think i start to understand now, just needed some time to melt it down.

I'm glad to hear it.

Just curious, what causes this 'new' position?

Im not sure maybe it never hapens but maybe if for example when you edit objects in a game editor or by user interaction (as mentioned in Don's paper) or reset objects to some initial state.

There is typically plenty of coherence in a user's actions in short time periods, at the 100ms scale even, because of either the laws of physics governing the user's body movements (e.g., 3D position tracking or even a mouse movement) or because of interaction constraints you provide them (movement buttons, etc). What is important here is that a user moved (self or something else) from a previous location, to a new location, through some real path. You may treat it as a discontinuous jump, but if you want to detect collisions that may have happened along the path, then you should just have the object move along that path (via a motion change), through kinetic sweep and prune. How you describe the path is up to you, but piece-wise linear or piece-wise quadratic should suffice.

[Erwin Coumans]

What is important here is that a user moved (self or something else) from a previous location, to a new location, through some real path.

If you restart your game/level, you don't want to deal with such path, or any inbetween motion. In that case you instantaneouly move objects from current position to the starting position.
Do you consider such case? Or do you just remove and reinsert objects at new location?

[dcoming]

What is important here is that a user moved (self or something else) from a previous location, to a new location, through some real path.

If you restart your game/level, you don't want to deal with such path, or any inbetween motion. In that case you instantaneouly move objects from current position to the starting position.
Do you consider such case? Or do you just remove and reinsert objects at new location?

Good point. I considered it a degenerate case to ever have a discontinuous position jump without an in-between path. If my system actually receives such a jump, it's easily identified, because the element is actually out of order in the list. It is the only time an element gets out of order, and is dealt with immediately. This ensures the nice feature that the lists are always in order, even in the middle of a 'time-step'. Usually, I just do the usual SAP update/local-sort if that happens. There's no need to schedule swaps in-between when they will all be performed atomically.

If you wanted to reset objects that have moved far from their starting positions, it may be faster to remove and reinsert them, if you have a constant-time or logarithmic-time insertion.