what does "sweep" and "prune" mean ?

[uchickenbutt]

as the topic.. thanks

[colinvella]

I've seen this algorithm also termed as "sort and sweep" which would imply that "sort" is being used as an alias for "prune". So off the top of my head I'd say that "prune" refers to the sorting of the projection ranges along one or more axes, while "sweep" is the process of identifying bodies overlapping with the current open coordinate along the current axis.

[Erwin Coumans]

See also this posting with a SAP document by Pierre Terdiman:

http://www.bulletphysics.com/Bullet/php ... f=6&t=1497

[Pierre]

I'm french so my understanding of the two terms might be wrong. But to me:
- to sweep is to cover the full extent of an object via some process. So in this context it would be going through the sorted list of boxes, one by one.
- to prune = to cull. To remove unused stuff. So, in this context, it's to remove non-overlapping pairs and keep the others.

The "box pruning" I wrote in the document Erwin references is, for me, the perfect "sweep and prune" application: we "sweep" the sorted list of boxes and "prune" them on the way. The sort is actually a pre-requisite of the SAP, and it's done in a separate, initial pass.

The "real" SAP does local "sweeps" when moving each boxes in the arrays. This is the same as the sorting.

I think it was Christer Ericson who said the algorithm should really be called "sort and sweep" instead of "sweep and prune". To me it looks more like "sort and prune"

Anyway, as I said, I'm just french so what do I know?

[Christer Ericson]

I think it was Christer Ericson who said the algorithm should really be called "sort and sweep" instead of "sweep and prune". To me it looks more like "sort and prune"

I have said that, and the reason I've said that is because Baraff was the first one to describe this approach and he called it "sort and sweep." In a (much) later paper by others, the very same method was rechristened "sweep and prune." As with all things in science, we give credit to the first inventor, therefore it should be called "sort and sweep." It's as simple as that!

Anyway, as I said, I'm just french so what do I know?

I'll tell Fabrice and Cedric that you said that!

[Erwin Coumans]

Well, I prefer sweep and prune for the incremental version, because the sort is done by incremental sweeps. Christer describes those two very different 'sort and sweep' or 'sweep and prune' methods in his book:

• 3D incremental SAP method, usually for 3D axis, and incrementally adds and removes pairs. The arrays stay sorted by incremental swaps/sweeps. Christer mentions linked lists, but arrays seem to perform better even for the incremental method.
• 1D non-incremental 'array based sort', or 'box pruning'. This performs a full sort on one axis (with the best variance) and computes all pairs from scratch each time.

The incremental version exploits coherence and has generally excellent performance, but the non-incremental method is easier to parallelize for multi-core and SPUs and therefore has a better worst case behaviour.
Hope this helps,
Erwin