Kinetic Sweep and Prune

[dcoming]

In conclusion, continuous collision detection in terms of interpolation methods already exist in the world of dynamics, all though the n-body problem is awkward.
/Kenny

We extended the popular sweep and prune method to be useful for continuous collision detection (without swept bounding volumes). Hopefully we have removed or at least reduced the awkwardness of the n-body problem for continuous collision detection with our Kinetic Sweep and Prune method.
http://graphics.idav.ucdavis.edu/resear ... weep_prune

[Erwin Coumans]

Thanks for the paper.

We did some related work, and also Gino van den Bergen described temporal use of the Sweep and Prune (SAP) space:

For a single continuous queries you can add the Ray Cast and AABB Cast to the Sweep and Prune space like here:
http://groups.google.com/group/comp.gra ... a738a90bf2

For multi-body continuous motion Gino presented the 4D SAP Broadphase, please read page 47 and onwards in this presentation:
https://www.cmpevents.com/Sessions/GD/C ... ction1.ppt

- How does the Kinetic Sweep and Prune compare to this 4D SAP Broadphase?

Erwin

[dcoming]

For a single continuous queries you can add the Ray Cast and AABB Cast to the Sweep and Prune space like here:
http://groups.google.com/group/comp.gra ... a738a90bf2

I'll look into this more.

For multi-body continuous motion Gino presented the 4D SAP Broadphase, please read page 47 and onwards in this presentation:
https://www.cmpevents.com/Sessions/GD/C ... ction1.ppt

- How does the Kinetic Sweep and Prune compare to this 4D SAP Broadphase?

At first glance they seem similar, when considering only the translational motion of AABB's. Indeed, Gino has described a good start at using sweep and prune for continuous collision detection. Our solution, however is more general than this and employs somewhat different structures for performing the swaps (for sweep and prune) in time-sequential order. Without going into the full detail of the flow of the method, the results would be similar in that the swaps for sweep and prune occur in order and some scheduling is used. There, the similarities end.

I am curious. Did Gino ever publish this work and/or results using it? If so, I am interested in reading the details as much is left out of the GDC talk.

Now lets define "motion" as a continuous function of time. For continuous collision detection, objects have such motion defined. We take this motion and separate it into projected components for each axis of Sweep and Prune (could be more than 3 technically, using k-DOPs). Note for a rotating or deforming object, the endpoints of the interval need not share the same motion so the box can continuously expand or contract as needed.

We place these continuously moving interval endpoints in something called a Kinetic Sorted List (KSL) [1]. There is one such KSL replacing each list and the necessary sorting in the sweep and prune method. The purpose of a KSL is to maintain the sorted order of a list of moving 1D points.

For performance consideration, we advise using approximations (conservative so as not to miss collisions) for the motion components used in the broad phase. It is easier to solve for intersection of two piecewise-linear functions than to use numerical solvers for a function like f(t) = t + sin(t).

There are more specifics in our paper such as handling when objects change their motion (e.g., due to collision response).

[1] BASCH J., GUIBAS L. J., HERSHBERGER J.:
Data structures for mobile data. Journal of Algorithms
31, 1 (April 1999), 1?28.

Again, our paper can be reached through:
http://graphics.idav.ucdavis.edu/resear ... weep_prune

[gino]

For multi-body continuous motion Gino presented the 4D SAP Broadphase, please read page 47 and onwards in this presentation:
https://www.cmpevents.com/Sessions/GD/C ... ction1.ppt

- How does the Kinetic Sweep and Prune compare to this 4D SAP Broadphase?

At first glance they seem similar, when considering only the translational motion of AABB's. Indeed, Gino has described a good start at using sweep and prune for continuous collision detection. Our solution, however is more general than this and employs somewhat different structures for performing the swaps (for sweep and prune) in time-sequential order. Without going into the full detail of the flow of the method, the results would be similar in that the swaps for sweep and prune occur in order and some scheduling is used. There, the similarities end.

I didn't went down to the nitty gritty of the paper, but it seems to discuss the same algorithm. The Kinetic Sweep and Prune paper discusses ordering the endpoint according to their ETA by applying a priority queue for storing the endpoint-swap events. After a swap event potentially two new swap-events (with neighboring endpoints) are scheduled. All these elements were also discussed in my GDC '05 presentation. The kinetic sweep and prune method, however, seems to maintain a consistent motion description, whereas in the 4D broad phase from my presentation the new target positions are set for each moving object in each time step.

I am curious. Did Gino ever publish this work and/or results using it? If so, I am interested in reading the details as much is left out of the GDC talk.

I'm afraid, the ppt presentation and the voice recording of the GDC '05 lecture is all there is. The meat of the lecture dealt with a continuous collision test for arbitrary convexes. The 4D broad phase was a nice addition but turned out a little condensed. (I hope the basic idea still survived.) I would love to get all this down to paper but writing books and papers does not earn me a living, so I have to prioritise.

[dcoming]

I didn't went down to the nitty gritty of the paper, but it seems to discuss the same algorithm. The Kinetic Sweep and Prune paper discusses ordering the endpoint according to their ETA by applying a priority queue for storing the endpoint-swap events.

Certainly the scheduling of swaps is the next logical extension of sweep and prune for a continuous broad phase, but I think this is more of the goal or problem, rather than solution. It is interesting to consider the varied approaches to this issue. For example Basch presented a list structure that scheduled swaps back in 1998, whereas perhaps you use one priority queue among all three axes.

After a swap event potentially two new swap-events (with neighboring endpoints) are scheduled.

Certainly! This is inevitable, though an unfortunate overhead we both face. I think we can agree that this is often preferrable to the alternative of an unmoving bounding volume that encloses a swept bounding volume.

The kinetic sweep and prune method, however, seems to maintain a consistent motion description, whereas in the 4D broad phase from my presentation the new target positions are set for each moving object in each time step.

That's interesting... we don't need/use time steps, though we permit them if desired by a user. The use of time steps is a construction only necessary for non-continuous collision detection, and/or rendering. Why add an arbitrary update step that is unnecessary? We just take motion updates wherever the user deems them necessary. This could be at regular intervals or at any point in time. Our goals were flexibility and generality.

I'm afraid, the ppt presentation and the voice recording of the GDC '05 lecture is all there is. The meat of the lecture dealt with a continuous collision test for arbitrary convexes. The 4D broad phase was a nice addition but turned out a little condensed. (I hope the basic idea still survived.) I would love to get all this down to paper but writing books and papers does not earn me a living, so I have to prioritise.

That's too bad. I was interested in going to GDC this year just for your talk, but an industry conference would have been too rough on a grad student budget

[gino]

The kinetic sweep and prune method, however, seems to maintain a consistent motion description, whereas in the 4D broad phase from my presentation the new target positions are set for each moving object in each time step.

That's interesting... we don't need/use time steps, though we permit them if desired by a user. The use of time steps is a construction only necessary for non-continuous collision detection, and/or rendering. Why add an arbitrary update step that is unnecessary? We just take motion updates wherever the user deems them necessary. This could be at regular intervals or at any point in time. Our goals were flexibility and generality.

That's a nice generalization. Have you used the Kinetic sweep for anything other than linear motions that were updated at regular intervals? It seems that the time step of a motion integrator makes a natural time step for updating the collision objects. Having anything other than linear motion may overly complicate the event processing , so it is hard for me to imagine the use of any higher order motions. Also, you usually want the response callbacks to be executed on the client's demand. So this would suggest that the client sets an interval over which responses need to be generated. So, from a client's perspective the time step is not that arbitrary.

[dcoming]

That's interesting... we don't need/use time steps, though we permit them if desired by a user. The use of time steps is a construction only necessary for non-continuous collision detection, and/or rendering. Why add an arbitrary update step that is unnecessary? We just take motion updates wherever the user deems them necessary. This could be at regular intervals or at any point in time. Our goals were flexibility and generality.

That's a nice generalization. Have you used the Kinetic sweep for anything other than linear motions that were updated at regular intervals? It seems that the time step of a motion integrator makes a natural time step for updating the collision objects. Having anything other than linear motion may overly complicate the event processing , so it is hard for me to imagine the use of any higher order motions.

Thanks. It is understandable that for some user-controlled objects, linear motion with frequent updates would be a suitable approximation for what is typically unpredictable behavior. As for higher order motions, quadratic functions would be convenient for a scene with gravity. Linear motions would have to be updated at regular intervals, to approximate gravity. This would introduce some O(n) updates which would each involve scheduling overhead of O(lg n) for a total O(n lg n) update cost for each time step. Because of this, we certainly do not perform updates at regular intervals. You can see this in Figure 7 in the paper, where KSP updates are almost 0. The "updates" to motion are always the result of either user interactions, collisions, or other arbitrary times at which the scene could decide to change the path of an object. The time step in that consideration is merely the granularity at which the simulation asks the collision detection engine to report collisions. The same figure (7) shows scalability with the granularity of time steps (i.e., sample rate) and ours is almost constant w.r.t. sample rate. This would not be achievable with updates at regular intervals.

Also, you usually want the response callbacks to be executed on the client's demand. So this would suggest that the client sets an interval over which responses need to be generated. So, from a client's perspective the time step is not that arbitrary.

Yes this is correct. Considering that swaps are events (now that they have a scheduled time), we can also consider collision responses as events that need to occur at exactly the first time of impact. Swaps and response callbacks are in fact interleaved so that the motion change resulting from the collision response can be immediately applied to the broad phase, before the next event is performed. The simulation or "client" if you prefer, can call our collision detection engine in two different ways. The first is to provide an interval, as you state. In this case, the collision detection engine works as you'd expect, providing response callbacks in order of when collisions occur. Since we don't have a per-time-step update overhead, these intervals can be arbitrarily large, small, or flexible within the same application.

The other method is event-by-event. The client can provide a time (representing the time the simulation wishes to advance to) and call the collision detection engine to perform the next event if it is before that time. This is particularly useful if you have an environment with motion trackers and/or Haptic feedback that update at different frequencies than rendering.

[kenny]

I read the paper, nice work:-) I do have a few questions/remarks:

Using an event driven scheme, would the usage of sequential collision response (I got the impression when reading the paper, that this is what you use) cause problems when configurations with infinite sequences are encountered?

Have you done any testing with dense structured stacks or random piles? All your test configuration appears to be very dynamic (everything is moving around). I am especially thinking of simulation errors in handling static contacts. For instance iteartive complementarity problem solvers are quite popular for the moment. However, they are not very accurate, thus even for static contacts you can expect errors in both position and velocities. In the paper you did mention something about bounds to handle ``noise'', I think this is similar, perhaps you could elaborate a bit about this?

If you did not use the spherical-AABB approximation, but used tight AABBs taking the rotational motion into account, how would you then determine the velocities of the extrema?

Also in a multiplayer setting I would imagine that every object in the configuration would constantly change acceleration/velocities, requiring updates of the kinetic sorted lists, I was wondering what kind of impact this has on performance?

I have used priority queus to in the past for making an event-driven approach, what I found to be the downside was the constant heapify operations that need to be performed. These were way to expensive (for my usage:-). Do you have some magical workaround for this issue?

You do mention that you need O(n^2) storage for keeping track of axis overlaps (close counters). I am curious about what data structure you decided to use for this?

As a side-note I would like to mention that I gave up on the ordinary sweep and prune years ago. It was too slow! I usually have 1000 primitive objects, which means the pair-testing is cheap and broad-phase is the bottleneck. Today I use optimized spatial hashing with a few tweaks of my own. Although this is a ``pseudo-dynamic'' approach I have very low constants compared to sweep and prune, and I do not need the O(n^2) storage for close counters. In my case a query with 1000 objects in dense configuration usually takes less than 0.01 seconds using optimized spatial hashing. It is a bit unclear to me if kinetic sweep and prune would be more expensive or more efficient for my usage?

[dcoming]

I read the paper, nice work:-) I do have a few questions/remarks:

Using an event driven scheme, would the usage of sequential collision response (I got the impression when reading the paper, that this is what you use) cause problems when configurations with infinite sequences are encountered?

Well, our broad phase allows interleaving sequential collision response with broad phase events. The result is that configurations with such infinite sequences wouldn't hurt Kinetic Sweep and Prune per se. I think the bottleneck in these situations is in the pair-wise testing and response. I'll make no claims that our method for collision response is great; our focus was on the broad phase.

Have you done any testing with dense structured stacks or random piles? All your test configuration appears to be very dynamic (everything is moving around).

Yeah it seems to be a popular description for scenes to test broad phases. I am interested in hearing of other possibly better scenes which push the bounds of broad phase methods. By definition this requires many objects to be moving on their own paths. A scene with mostly static objects is simple to prune after initial steps, as it probably won't incur worst-case behavior in any scheme.

In the paper you did mention something about bounds to handle ``noise'', I think this is similar, perhaps you could elaborate a bit about this?

Certainly. Lets imagine an object infinitely bouncing between two other very close objects, quickly enough that it occurs over 1000 times/second. At least from the broad phase's perspective, this object's motion can be bounded pretty well. For resolving all of the intersection tests and responses I'm afraid all I can suggest is to search through the other literature on it. For the broad phase, however, consider first a case with the other two objects immobile (e.g., walls). The motion of the object in between has a hard bound. If one wall ends at 3.0 and the other starts at 3.5, and the object is a ball with radius 0.4, it only has room to move back and forth by 0.1. In such a tight case it'd be wise to set the bounds of the motion to 3.0 and 3.5. If these walls were moving along instead of static, again keeping the ball bouncing infinitely between them, then on average, the ball's velocity would share the walls' velocities. To hopefully wrap up this long-winded response, the traditional way for sweep and prune to absorb noise is to just expand bounding volumes. The approach more suited to KSP is that when a pair of values in the lists keep swapping too frequently, then a compromise needs to be made: a shared motion that reduces the frequency of the swapping, acknowledging that a particular pair of boxes will frequently start and stop overlapping so just let them stay overlapped. In essence this is maintaining a contact. These are suggestions for handling noise, but perhaps the subject for further study.

If you did not use the spherical-AABB approximation, but used tight AABBs taking the rotational motion into account, how would you then determine the velocities of the extrema?

Take a look at this image from wikipedia, noting the sine and triangle waveforms:

In 1D, rotations turn into functions of sine and/or cosine. With rotation and velocity, an extrema's 1D motion x(t) with rotation would be:
x(t) = x_0 + v_x * t + sin(theta(t)),
where theta(t) is the object's angle also as a function of time.
Frankly, there is no closed form solution to intersecting two such x(t) functions, so (relatively slow) numerical solvers are usually used. Instead, imagine if you will, placing the triangle wave above the sine wave so that it intersects tangentially only but always stays above the sine wave.
Replacing the sine wave, we get:
x(t) = x_0 + v_x * t + tri_wave(theta(t)),
Since the tri_wave is piece-wise linear, now we have a closed form solution that we can apply. The triangle wave is just one of many possible wave forms you could use to 'cap' the sine wave, each with its own trade-off in tightness vs cost of finding intersections.

Also in a multiplayer setting I would imagine that every object in the configuration would constantly change acceleration/velocities, requiring updates of the kinetic sorted lists, I was wondering what kind of impact this has on performance?

Each time an element's motion in a kinetic sorted list changes there can be O(log n) cost, depending on the data structure you use for scheduling. This cost is a trade-off. Instead of an O(n) update cost (updating all moving objects' positions every time-step), we have an O(log n) cost for each time an object changes its "motion". When would this theoretically be worse? Well, constant factors aside, if less than O(n / log n) objects changed their motion within a given time period, our method would be asymptotically faster. For example, a ballistic object, just following physics laws like gravity, the motion changes are infrequent. Once in air, its affected by a constant acceleration. Even though its velocity changes continuously, its "motion" can be described as a function of time. It is when this function is changed arbitrarily that we incur the motion change cost. However, users are less predictable, but in most cases more limited in quantity than predictable objects. Of course, if acceleration were to change continuously for the scene, say... gravity were in the process of reversing(?), then you could just use an even higher order of motion and account for the continuous change in acceleration.

I have used priority queues to in the past for making an event-driven approach, what I found to be the downside was the constant heapify operations that need to be performed. These were way to expensive (for my usage:-). Do you have some magical workaround for this issue?

Nothing magical about it, but the choice of data structure is Critical! We use auxiliary two-pass pairing heaps. They're a bit tricky, but very cheap and have great amortized costs.

You do mention that you need O(n^2) storage for keeping track of axis overlaps (close counters). I am curious about what data structure you decided to use for this?

I wouldn't say "need". Technically any sweep and prune method can get away without storing any axis overlaps, by testing for overlaps on other axes whenever a new overlap occurs on one axis. This is expensive so the trade-off of extra memory is worthwhile. We use a lower-triangular matrix M of integers, such that if M[i,j] = 0 then the bounding volumes of objects i and j overlap. M[i,j] = 1,2,3 means that 1,2,3 axes do not overlap, respectively. We use this method since it easily scales to more than 3 axes as would be nice for k-DOPs.

As a side-note I would like to mention that I gave up on the ordinary sweep and prune years ago. It was too slow! I usually have 1000 primitive objects, which means the pair-testing is cheap and broad-phase is the bottleneck.

The studies I've read comparing S&P to other broad phase methods have shown that S&P is relatively more expensive but performs superior in terms of pruning. Whether the broad-phase expense is justified depends on how complex the objects are and how expensive each pair-wise test is.

Today I use optimized spatial hashing with a few tweaks of my own. Although this is a ``pseudo-dynamic'' approach I have very low constants compared to sweep and prune, and I do not need the O(n^2) storage for close counters. In my case a query with 1000 objects in dense configuration usually takes less than 0.01 seconds using optimized spatial hashing. It is a bit unclear to me if kinetic sweep and prune would be more expensive or more efficient for my usage?

Again, it depends on your objects' complexities and how expensive pair-wise tests are. I will say that one problem with spatial hashing (I presume this is space partitioning into cells) is the issue of cell-sizes. Also, there are costs associated with entering and leaving cells in such a way that I find S&P usually handles scenes with fast-moving objects better, where spatial subdivision works great for scenes with slow-movers. I'm also aware that there are differences in terms of scene density (how spaced objects are). S&P seems to gracefully handle density changes too. I've only seen one adaptive spatial subdivision scheme that changed cell sizes, but it was an expensive operation.