Vector Calculus and Constraint Functions

Please don't post Bullet support questions here, use the above forums instead.
bone
Posts: 231
Joined: Tue Feb 20, 2007 4:56 pm

Post by bone »

raigan2 wrote:So, has anyone implemented a bend constraint using the "Position Based Dynamics" paper?
As of today, yes and no. It's not quite working. Up through eqn (27), everything looks great (the calculated q's are the correct gradient directions). But something's amiss with the scaling term - applying it usually overshoots badly unless there's an error in my code. I'm still confused with the divisor in eqn (28) - is that the sum of squared values, or square of summed values? I'd prefer parentheses. Either way, though, it doesn't work.

Has anyone implemented this successfully?
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

One typical mistake is not to move your points to the origin as the paper states. So let x1, x2, x3, x4 be your particle positions.

p1 = (0,0,0)
p2 = x2 - x1
p3 = x3 - x1
p4 = x4 - x1

Then compute displacements as described in the appendix and update the original positions.

x1 += dp1
x2 += dp2
x3 += dp3
x4 += dp4


HTH,
-Dirk
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Post by raigan2 »

bone wrote:
raigan2 wrote:So, has anyone implemented a bend constraint using the "Position Based Dynamics" paper?
As of today, yes and no. It's not quite working. Up through eqn (27), everything looks great (the calculated q's are the correct gradient directions). But something's amiss with the scaling term - applying it usually overshoots badly unless there's an error in my code. I'm still confused with the divisor in eqn (28) - is that the sum of squared values, or square of summed values? I'd prefer parentheses. Either way, though, it doesn't work.

Has anyone implemented this successfully?
oh good, i'm not the only one -- i had overshooting quite badly. and i agree with the ambiguity of the sum.

i discovered a "solution", i'm not sure why it works, but it works quite well.
i'm almost positive the denominator is meant to be a sum-of-squared-lengths, not a sum-of-lengths squared.

anyway, the paper does:
-calculate sum-of-squared-lengths of gradient (call it denom)
-correction on particle i: -C/denom * scale_i * gradient_i
where scale_i = cardinality * invmass_i / invmass_total

instead, i found that this works much better:
-calculate scaled gradients (scale_i * gradient_i)
-calculate sum-of-squared-lengths of _scaled_ gradients
-correction on particle i: -C/denom * (scale_i * gradient_i)

I'd really, really like to know why this works. On a related note, I'd like to know where the "cardinality" term comes from, it's not explained in the paper very well and I don't understand why it's used.. but it seems necessary.
bone
Posts: 231
Joined: Tue Feb 20, 2007 4:56 pm

Post by bone »

Dirk Gregorius wrote:One typical mistake is not to move your points to the origin as the paper states. So let x1, x2, x3, x4 be your particle positions.
I did indeed make that mistake early on, but fixed it before encountering my other issue.

raigan2 - OK, thanks, I'll try implementing your suggestion. My memory of calculus is probably on par with yours, however, so I don't know if I'll be able to explain it any better.

EDIT: I don't think this is going to change my results. I believe scale_i would always be 1.0 with equally-weighted point-masses. For example, say all your masses are 0.1kg. Then all the w values are 10.0. So 4*10/(10+10+10+10) = 1.0. Perhaps this is where my misinterpretation is coming from?

EDIT #2: OK, my issue is definitely coding. Seems inexplicable, but I managed to miscalculate the term: arccos(d) - origAngle.

So now that I know it works, but isn't really that fast, has anybody thought of another bending constraint function that is a) faster, and b) mostly independent of other constraints?
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

I made the same experience with the bending constraint. It is slow and there is no gain in visual quality that justifies this. Even in Novodex this is an optional feature. The visual quality really depends on the density of the mesh (this is the number one factor IMO) - a dense cloth mesh gives you better looking cloth. So I went brute force with pure distance constraints, one for each edge and one for each bending element across the shared edge and tried to make this as fast as possible. For the bending (distant) constraint I use quite a low stiffness since this way it seems to recover (at least for me) better from degenerate cases (e.g. penetrations). You can of course make the bending unilateral, that is only apply the constraint to push apart...


HTH,
-Dirk
bone
Posts: 231
Joined: Tue Feb 20, 2007 4:56 pm

Post by bone »

raigan2 wrote:On a related note, I'd like to know where the "cardinality" term comes from, it's not explained in the paper very well and I don't understand why it's used.. but it seems necessary.
Actually I think this can be explained if you look between equations ( 7 ) and ( 8 ) in the paper. The cardinality is simply the number of particles that the constraint affects. In equation ( 8 ), n is the number of particles (what I believe you are calling the cardinality), and the constraint is expressed as C(p-sub-1, ..., p-sub-n).

Like I said in my previous post, I think your scale_i should be 1.0 if you have equally weighted particles. What they call the "final correction" in the paper seems to be simply adjusting the movements according to weight. Note that I haven't tested with differently-weighted particles, so I haven't verified that that works yet. So perhaps that's where you are running into the overshooting problem, whereas mine was simply a coding mistake.
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

You should think of the weighting as a separat thing. You can do two things

scale = m_i / Sum( masses )

or

scale = w_i / Sum( inverse masses )

The first will move the lightest mass the most and the second will move the heaviest mass the most. You could for example also move each particle equally which then becomes

scale = 1 / kardinality
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Post by raigan2 »

Actually I think this can be explained if you look between equations ( 7 ) and ( 8 ) in the paper. The cardinality is simply the number of particles that the constraint affects. In equation ( 8 ), n is the number of particles (what I believe you are calling the cardinality), and the constraint is expressed as C(p-sub-1, ..., p-sub-n).
I meant more: why do we need to use a cardinality term at all -- how did they arrive at it? Why can't we just scale things with weights which sum to 1? Just using (w_i/w_total) would be an example: why do we have to use n*(w_i/w_total)??

What's confusing to me is that a constraint function that takes 2 3D vectors (cardinality 2) could also be considered a constraint function that takes 6 scalars.. the gradients would be the same, and you could split the mass of each particle between its x,y,z coordinates so that the total mass remained constant, but in the second case you'd have a cardinality of 6, which would alter the results.

Shouldn't the results be identical in both cases, since it's simply a matter of changing C(p1,p2) to C(x1,y1,z1,x2,y2,z2) -- we've posed the same question in a different form, which shouldn't alter the solution. So it seems like scaling everything by the "cardinality" in addition to a weighting term is a bit arbitrary/ambiguous.. or at least I don't understand where it came from.


About the bending constraint, I found that arccos didn't behave all that well, arctan was much more well-behaved:
C = (atan2(n1) - atan2(n2)) - theta

Is no one else having fundamental problems with over-shooting? For the collision/normal constraint (section 4.3), there was definite overshooting when using particles with varied masses. I'm almost positive it wasn't due to a programming error as i derived the constraint in a few different ways, several times over a period of weeks. Plus my solver is generic so the other constraints would have shown weird behaviour if there was a bug -- only the constraint function and the gradients vary between constraints.

When all masses were the same, the behaviour of the original paper's method and my method was the same: they both behaved well.

However, if you took one of the particle's masses and doubled it, the paper's method over-corrects. In contrast, even at extreme mass ratios such as 1:50, the method I happened upon behaves perfectly well. I just wish I understood why!
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

Were you able to reproduce the overshoot for exactly on constraint (e.g. distance or bending)?
dank
Posts: 2
Joined: Wed Aug 15, 2007 5:49 pm

Post by dank »

Hello Guys, very new to this forum and this is my first post.

I've implemented the "HitMan" paper on position based dynamics and have read the Ageia paper. I've got the basic rod constraints working great and I implemented the angle/bend constraints in the simple way described in the "HitMan" paper (testing the distance of the endpoints of the angle.. if too close push apart).

The bend constraints work, but they aren't as strong as I'd like. In the Ageia paper they measure the angle and avoid the prob of the measuring distances which can fail when the edges are stretched.. this isolates the bend from the stretching constraints.

I've tried a variant of this which works in a simple case but as I apply it to more complex meshes they end up feeding back and overshooting so much that it grows unstable.

Here's my approach:

1) assign a constraint across 2 end points that share a common second endpoint. this second endpoint is like a joint.
2) find the vector between the joint and an endpoint and store the length somewhere, now normalize that vector and select a new end point which is 1 unit away from the joint but along the same vector. Do the same for the other endpoint.
3) now measure the distance between the two new end points.. if too close push them apart.
4) take the new vector between the angle joint and the adjusted end point.. project that end point away from the angle joint by the length stored before working

this is probably a very confusing explanation. Essentially I'm adjusting the endpoints to a fixed distance away from the angle joint to eliminate problems with edge stretching before doing dist checks.. then if I adjust them I move them away from the angle joint to the orig length along the new vector.

I've tested on very simple cases like a 3 point line.. I fix the center point and allow the outside points to fall.. my constraint works well in this simple case. Works well with 4 quads in a grid where I fix the center point and allow the outside to fall. If I have a heavier mesh.. say a 10x 10.. then when the constraints kick it they seem to cause a ripple effect and I get overshooting and increasing energy over time

I originally tried doing it like the paper measuring angles and I got the same sorts of feedback issues.. so I tried this other method.. now I still have the same result. I'm guessing the problem is in how I try and correct the small angle

any pointers would be appreciated

thnx

Daniel
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

Do you use the correction as suggested in the Ageia paper? If yes, do you use the lately published corrected version?

I use a distance constraint for each edge and another (softer) distance constraint for each triangle pair sharing an edge. This works great, so I assume there is maybe another issue...
dank
Posts: 2
Joined: Wed Aug 15, 2007 5:49 pm

Post by dank »

not sure if I have the lately published corrected version, can you send a link to that so I can check? I guess I'm not clear on the "correction", just looked over that paper section again and there's not a lot of info there.

One thing that's probably different about my version is I don't assume triangles, I also allow for quads. it could be causing more instability

I can provide a code snip if you think that would help (or if you're willing to help at that level)

thnx

d
Dirk Gregorius
Posts: 861
Joined: Sun Jul 03, 2005 4:06 pm
Location: Kirkland, WA

Post by Dirk Gregorius »

http://www.matthiasmueller.info/publica ... sedDyn.pdf

Yeah, post your code and I have a look, though I will not romise anything...
Post Reply