🔒 Locked

Position Based Dynamics collision

Started by BRabbit27 Oct 9, 2014 at 6:40 PM 3 replies 6.1k views

Original Post

Oct 9, 2014 at 6:40 PM

I have read about Position-Based dynamics from this paper but I got a little bit confused on how can I use it to implement collision detection and response. I could follow the math for the case of a distance constrain but it got a bit confusing when trying to apply the same principle to collision.

They mention 2 types of collision detection: continuous and static. The former is when at time t the particle is in the valid zone and in time t+1 is not. The latter is just when at both times the position is invalid and thus the continuous collision detection failed.

To check whether a collision existed I can compute the distance from the particle's position p_i to the plane. This is achieved with the following equation (p_o-p_i) . n = d where p_o is a point in the plane and "n" is the normal of the plane. So far so good.

If I got it correctly I can add a constraint of type unilateral as follows C(p_i) = (p_o-p_i) . n >= 0. However, it mentions two conditions.

- If particle p_i comes from a valid to an invalid position, compute q_c and add an unilateral constraint C(p) = (p-q_c) . n_c >= 0

- If particle p_i has been in an invalid position, compute q_s(closest point to p_i) and add an unilateral constraint C(p) = (p-q_s) . n_s >= 0

So, my questions are

1) In the previous constraints what is P ? Is this the point in the plane or the particle's position? Since I know I have to have a point in the plane to be able to compute the distance from the particle to the plane I would say it is a point in the plane, nevertheless, the constraints are applied to the positions of the particles, so my previous statement makes no sense.

2) If I have to compute q_c (or q_s) then the constrain is solved right? why would I need to create a constraint when I already have the valid point?

3) For any constrain I want my system to be subject to, is the method described like a recipe? What I mean, I just take the constraint, compute the gradient, compute lambda, and then solve iteratively?

BRabbit27

Oct 13, 2014 at 12:06 PM

After some reading and thinking I figure out the idea behind those lines (I hope).

Since we have a particle at position x_iand after updating velocity and predicted the new position p_i we want to know whether there is a collision and if so move the particle back to the collision point q_c and then using position-based dynamics compute a new valid position for the particle.

To check whether the particle when moving from x_ito p_i collides, we check if there is an intersection of the ray given by r = x_i+ t(p_i-x_i) and the plane P = (p-p₀) dot n where t will tell us if there is a collision (0 <= t <= 1) or not.

Once we get the collision point q_c we can create an inequality constrain C(p) = (p-q_c) dot n_cwhere n_cis the same as the normal of the plane. With this constrain I can get the correction position DeltaP. Now the only question remaining is

- If I have two different constraints, each will give a DeltaP then, how to mix them in order to have the final correction position?

matejd

Oct 13, 2014 at 6:57 PM

First time posting here, but I've been reading position-based dynamics recently as well.

If I understand your last question about constraint mixing correctly, the answer is that this is what the repeated constraint projection is for (solverIterations times going through the

list of constraints and projecting them). Solving one constraint might mean that another one needs to be solved again, but after several iterations, all should be satisfied (at least

approximately).

Also, this lecture might be useful:

BRabbit27

Oct 13, 2014 at 8:47 PM

After some more thinking and reading your answer, so basically, for a single particle I will do something like

While iter < solverIteration do
Take constraint C₁compute DeltaP
Update particle's tmpPosition
Take constraint C₂compute DeltaP
Update particle's tmpPosition
End while

and, as you said, after a certain number of iterations, the system will have the best approximation of tmpPosition that satisfies both constraints, right?

BTW, thanks for the video, I'll watch it right away !

matejd

Oct 13, 2014 at 9:13 PM

Yes, updated position is immediately visible to other constraints - the authors call it a Gauss-Seidel-type iteration in section 3.2 (vs Jacobi-type). These slides have more on this iteration.

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.