Position based dynamics and collision constraints

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
bartk
Posts: 1
Joined: Wed Aug 13, 2014 10:17 am

Position based dynamics and collision constraints

Post by bartk »

I was reading through "Position-based Method for the Simulation of Solid Objects" and noticed something about the algorithm outlined there. Collision constraints are generated for the ray/line from current positions to the initially predicted positions and this is only done once.

What seems "strange" though is that when modifying predicted positions over several iterations, I guess new collisions could occur and would go undetected if, say, we were to use a general triangle mesh as the collider.

So what is the assumption here?
- The chances of this happening are so small that it's of no use to be worried about them?
- The colliders are substantial enough (general spheres, cubes, capsules, large triangles) that it's still THE valid collider? i.e. no general triangle meshes with "small" triangles
- ...

Or am I off in my interpretation somewhere are would you re-generate constraints based on the modification of the predicted positions?
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Re: Position based dynamics and collision constraints

Post by raigan2 »

I think there are a few different ways to handle this.

An approach I've used with a position-based solver is "speculative collisions": at the start of the frame, generate all pairs of potentially colliding features, and solve them speculatively (i.e inside the solver you check if there's penetration, and if not you skip/ignore that constraint).

This type of approach is explained pretty well here: http://www.wildbunny.co.uk/blog/2011/03 ... ch-part-1/

Two problems with this approach are (1) the heuristic for "potentially colliding" isn't always correct (IIRC I swept objects from start to end, generated AABBs that covered the sweep, inflated them, and tested them for overlap; the inflation step is meant to deal with the case where the solver moves things quite a bit, but if it moves things by more than the inflation amount, collisions can be missed), (2) the number of constraints to solve is much higher (since you're generating lots of speculative pairs).

A different approach suggested in this (excellent) recent paper is to use a signed distance field: http://mmacklin.com/uppfrta_preprint.pdf i.e rather than trying to sweep and predict/avoid penetration, they use a signed distance field to recover from penetration.


IMO one problem with position-based solvers is that they seem to want collision detection to be moved into the solving loop, which can be a performance bottleneck. Finding novel ways to avoid this (or speed this up) seems necessary. Or maybe not -- it's been a few years since I worked on this, there may be better approaches I'm not aware of.
Post Reply