Jacobsen & Verlet - embedding simplex in polytopes

Please don't post Bullet support questions here, use the above forums instead.
Post Reply
pellepl
Posts: 4
Joined: Thu Jul 23, 2015 7:29 pm

Jacobsen & Verlet - embedding simplex in polytopes

Post by pellepl »

Hi there,

Like loads of other people, I've been tinkering away with Jacobsen's verlet approach (http://web.archive.org/web/201001110352 ... dc2001.htm) for a little game for my kids.

I have working tetrahedrons bouncing around and interacting on a heightmap, so far so good. However, what confuses me is Jacobsen's description of embedding tetrahedrons in more complex rigid bodies.

As far I understood, the collision detector is supposed to detect collisions on the wrapping rigid body. OK, not a problem. Then, and here I'm lost, one is supposed to use the collision response (penetration distance and normal) on the embedded tetrahedron. What of the collision point? The point cannot be described by barycentric coordinates of the tetrahedron as it is on the outside, thus I cannot use the Lagrangian multiplier to update the tetrahedron particles. Am I supposed to project the collision point onto the tetrahedrons surface or something?

Anyone worked this out? I've been googling around like crazy last week but fail to find anything. I even bought the book Game Physics Pearls, but Jacobsen's article here was much the same as the link above (Otherwise, a very good book).

Thanks / Peter
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Re: Jacobsen & Verlet - embedding simplex in polytopes

Post by raigan2 »

I've done this a couple different ways in 2d, I'm unfortunately really busy at work but I'll try to explain what I know and hopefully it gives you some ideas. (also it's been about 5 years..)

In general you have some collision geometry which is embedded in a frame, so the geometry is a function of the frame.

Now, given some delta that you want to apply to the collision geometry (i.e you want point p to move by displacement vector v), and you have to determine the corresponding delta to apply to the frame such that p_new = p + v.

It's been a while since I worked it out, but this is a vector calculus problem: you need to figure out the partial derivatives of p wrt the frame and use that to calculate the required delta to apply to the frame. (e.g "if the frame moves +1 then p will move +2; I want p to move +10, so I should move the frame by +5")

One other thing is: the embedding that Jacobsen proposes isn't necessarily the best, at least in my tests his barycentric weighting (in the 2d case he describes) is only approximate, there are other approaches which are more exact.

I've only done this in 2d, but AFAICT any type of frame/embedding you can construct is valid, you just need to be able to calculate partial derivatives (matlab can help a lot here!).

In 2d Jacobsen makes a triangle out of 3 particles and embeds the collision geometry in this frame, but I've found that a single stick is sufficient (and converges more quickly): if the two particles making up the stick are a and b, then the frame is defined as e.g:
origin = a
local x axis = (b-a)
local y axis = perp(b-a)

I've also tried e.g:
origin = 0.5*(a+b)
local x axis = (b-a)/||b-a||
local y axis = perp(b-a)/||b-a||

which is more or less the same -- it behaves a bit better when there are large deformations (the axes don't grow if the stick is stretched), but it's also a bit more costly to compute the partial derivatives (IIRC).

In 3D you should be able to do something similar, using a triangle as the dynamic model (i.e the triangle defines a plane, if you take the cross product of two of the triangle edges, that plus the plane gives you 3 orthogonal axes). This way you can avoid barycentric coordinates altogether.

(note: I haven't really thought this through in 3d, possibly it won't work because the triangle model won't let you control the moment of inertia in certain directions..)
pellepl
Posts: 4
Joined: Thu Jul 23, 2015 7:29 pm

Re: Jacobsen & Verlet - embedding simplex in polytopes

Post by pellepl »

Millions of thanks for the explanation! You saved me some serious head scratching.

It is not fully clear to me how to find the correct vectors using partial derivatives, but I'll google around and experiment a bit. I guess the hard part is coming up with the actual geometry function regarding the frame.
raigan2 wrote:One other thing is: the embedding that Jacobsen proposes isn't necessarily the best, at least in my tests his barycentric weighting (in the 2d case he describes) is only approximate, there are other approaches which are more exact.
That's very interesting. You wouldn't happen to remember any of those approaches..? :wink:
raigan2 wrote:In 2d Jacobsen makes a triangle out of 3 particles and embeds the collision geometry in this frame, but I've found that a single stick is sufficient (and converges more quickly)
Again, very interesting. I think I'll switch to 2D while experimenting to get a feel of it. Everything goes so much smoother when losing a dimension.

And yet again, thanks for getting me back on the path.
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Re: Jacobsen & Verlet - embedding simplex in polytopes

Post by raigan2 »

pellepl wrote:That's very interesting. You wouldn't happen to remember any of those approaches..?
Just the stick-based one I described (and, we have a few other weird IK-based embeddings, where the collision geometry is a function of the length between two particles connected via min/max distance constraint).

As far as I can tell the embedding is sort of arbitrary, you could play around with it (eg if you have a triangle of particles a,b,c, and distance constraints ab = x, ac = x, bc = sqrt2 * x (i.e a right triangle), you can define the origin as a linear combination of abc, and the basis vectors are ab, ac, and cross(ab, ac)).

For the partial derivatives, you have to describe the embedded vertex e as a function of the particles f(a,b,c,r) (where r is the local coordinates of e wrt the frame made from abc) and then pass this function to matlab and ask for the partial derivaties. (I think these partial derivatives are called the jacobian)

(note: you might find it easier to pass matlab a function of scalars, eg f(ax,ay,az,bx,by,bz,cx,cy,cz,rx,ry,rz) since IIRC getting it to parse functions of vectors was difficult.. for me anyway)

OR: as a debugging tool, you can also approximate the partial derivatives via finite difference, i.e calculate e0 = f(a,b,c,r) e1 = f(a+(h,0,0),b,c,r); the rate of change of e as r.x changes is approximately e1 - e0 / h; (you have to pick h at an appropriate scale though)

These partial derivatives are what you use to transform a desired displacement to the embedded geometry into the corresponding displacement of the dynamic particle model (in which the geometry is embedded).

One author you might want to check out is Matthias Muller, he generalized/expanded on Jacobsen's approach in Position Based Dynamics http://matthias-mueller-fischer.ch/publ ... sedDyn.pdf and this is a good recent survey of position-based methods: http://matthias-mueller-fischer.ch/publ ... 015PBD.pdf

Specifically, his paper formulates things in terms of partial derivatives, so this should help explain how you use them. Honestly I only figured it out after posting a lot here and some very patient people helping me work through it :)
pellepl
Posts: 4
Joined: Thu Jul 23, 2015 7:29 pm

Re: Jacobsen & Verlet - embedding simplex in polytopes

Post by pellepl »

Ok, I think I had some heureka-moments (perhaps :wink: ).

First of all, Jacobsen's paper speaks of embedding a particle simplex within a larger collision geometry. As you describe it, it is the other way round. One possibility is I've either misunderstood Jacobsen, or you, or both. Either way, it should not make any difference - as a matter of fact, Jacobsen's paper makes more sense if the particles instead wraps the collision geometry as you describe it.

Just to sum up your wisdoms: if describing the collision geometry as a function of the particles, and using the gradients (or Jacobian, I think you're right) for finding how to move particles as response to a collision on the geometry, it really should not matter what is embedded.

EDIT: Below is so wrong.
Quick question, only if you have the time - want to check if I'm on the right track:
For simplicity, assume 2D. Let's say I have particles A and B, and some collision geometry vertex E described by A and B. As this is in 2D, I would have:

Ex = fx(A,B)
Ey = fy(A,B)

The partial derivatives I seek then would be:

dEx/dx = fx(A,B)/dx
dEy/dx = fy(A,B)/dx
dEx/dy = fx(A,B)/dy
dEy/dy = fy(A,B)/dy

right?

I think I just got some deja vu from the past millennium from a university exam with regard to some weird question on electrical fields. Too bad they never taught us it actually could be useful. :D
raigan2 wrote:One author you might want to check out is Matthias Muller...
Funny, found those pdfs a while ago but forgot about them. There's really a wealth of info on Müllers site. Guess I'll have to try to rewrite my hack according to Müllers approach, seems way more effective.
You're the hero of the day. Thanks for taking the time!

EDIT
Well, fake heurekas.

What I actually need to derive should be:
dEx/dAx, dEx/dAy, dEx/dBx, dEx/dBy
dEy/dAx, dEy/dAy, dEy/dBx, dEy/dBy

and, apparently, wrt the mysterious r:
dEx/dRx, dEx/dRy
dEy/dRx, dEy/dRy

I need to ponder over this a bit more it seems. Trying out a simple 2d stick variant of A and B, where my collision point E is described as
fE = (A+B)*0.5 + perp(B-A)
placing E over the AB midpoint, with distance to AB midpoint being ||B-A||.

So R in this case would be (0.5,1). I guess. Giving:
fEx = (Ax + Bx)*0.5 + Ay - By + 0.5Rx
fEy = (Ay + By)*0.5 + Bx - Ax + Ry

giving gradients (wrt dAx, dAy, dBx, dBy, dRx, dRy)
grad(fEx) = [0.5, 1, 0.5, -1, 0.5, 0]
grad(fEy) = [-1, 0.5, 1, 0.5, 0, 1]

What I need to sort out is
1) should the geometry (E in my case) be described locally to the frame or in world coordinates (as above)
2) how to use my gradients for finding displacement of A and B when I have a MDV and penetration on E
3) why R is needed. Intuitively it should be there. Could be it is the answer of 2...

Sorry for thinking aloud, some moderator stop me if needed.

Oh and raigan2, I fully understand if you haven't got the time to hold my hand through this. You're still hero of the day though ;)
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Re: Jacobsen & Verlet - embedding simplex in polytopes

Post by raigan2 »

Cheers! This stuff was such a headache to figure out that I'm glad to help someone avoid that as much as possible :)

I still think that it's "geometry embedded in particles" (or really, "geometry embedded in frame derived from particle positions") and not the other way around, because the particles are the independent variables -- their coordinates are things you can directly change -- while the collision geometry is a dependent variable; in order to change the worldspace coordinates of the collision geometry, you have to change the particle positions.

Anyway I guess it's semantic, it looks like you're on the right track!

To answer your questions (as far as I know, note: I may be very wrong, since I'm definitely an amateur):

1) I find it less confusing to work in worldspace, I think it should be equivalent regardless of the space (I'm willing to trade a bit of inefficiency for being able to stay in worldspace as much as possible, it's simpler for me to understand)

2) if you read Muller's PBD paper, he provides a formula which is a generalization of Jacobsen's, and one of the terms is a gradient, so you can just follow that formula and plug in your gradient there to get the displacement/position deltas for the particles (IIRC there is also a weighting term that depends on the sum of the squared length of the jacobian)

3) if r is fixed (i.e static, it doesn't move in objectspace) then AFAIK you shouldn't need its partial derivatives. (the term r may still show up in the Jacobian of the particle positions, but you shouldn't need derivatives of r on its own if the geometry is rigid (i.e if r doesn't change over time))

Of course, it's interesting if you allow r to be a dynamic variable like particle positions, since you can assign it a mass and then have a soft-body model where the collision geometry is allowed to deform. ;)

Good luck!

p.s - yes, this was exactly my response to this stuff -- why didn't I know calculus was actually useful when I was forced to take it in uni?! Honestly I just bugged a couple better-at-math friends to help remind me how to use the chain rule ;)
p.p.s - now that we shipped N++ I have more free time, so no worries :) We hope to release some more tutorials about this embedding stuff at some point, because I think it's pretty useful and fascinating, and I'd love to see more people exploring the possibilities
pellepl
Posts: 4
Joined: Thu Jul 23, 2015 7:29 pm

Re: Jacobsen & Verlet - embedding simplex in polytopes

Post by pellepl »

raigan2 wrote:I still think that it's "geometry embedded in particles" (or really, "geometry embedded in frame derived from particle positions")
Yes, you're right. I was thinking "embedded" as in the picture from Jacobsens paper, i.e. graphical. But it is more of a mathematical meaning it seems.

I actually think I cracked it, at least in the 2d case (and not with r). I need to do some more coding, but this is .. really promising, to say the least. For now I'm deriving the geometry from two particles with a stick constraint, just as you suggested. I use
F(A,B) = x_geom*(B-A) + A + y_geom*perp(B-A)
to describe my geometry vertices. In world space also, much easier.

For other readers, the formula above describes one geometry vertex using particles A and B. A and B forms a frame, hence x axis is B-A and y axis is perp(B-A). Expanding for world axes yields:

Fx(A,B) = x_geom*(Bx - Ax) + Ax + y_geom*(Ay-By)
Fy(A,B) = x_geom*(By - Ay) + Ay + y_geom*(Bx-Ax)

Expanding and shuffling around gives the gradients (wrt dAx,dAy,dBx,dBy):

gradFx = [1-x_geom, y_geom, x_geom, -y_geom]
gradFy = [-y_geom, 1-x_geom, y_geom, x_geom]

(Interesting that gradFy is gradFx with all elements shifted right.)

So, would I want to move my geometric vertex by (dx, dy), I simply apply

Ax += dx * (1-x_geom) + dy * -y_geom
Ay += dx * y_geom + dy * (1-x_geom)
Bx += dx * x_geom + dy * y_geom
By += dx * -y_geom + dy * x_geom

Which, I gladly can say now, makes fully sense regarding to what the gradient describe.

One interesting property, at least when doing it with a stick this way, is that the center of mass is always in the middle of the stick - regardless what your geometrical shape is. Symmetrical shapes around the stick behaves fully as expected. Others, well, are interesting.

Also, having a vertex where |x_geom|>1 or |y_geom|>1 will makes it very "sensitive", or bouncy. Which also mathematically makes sense I guess.

In 3d, I suspect a triangle would make e.g. a cube have its mass center somewhat dislocated, being in the triangle's center instead. Or to quote raigan2:
raigan2 wrote:(note: I haven't really thought this through in 3d, possibly it won't work because the triangle model won't let you control the moment of inertia in certain directions..)
Guess a particle-quadrilateral should work, or being very precise when describing the cube from the triangle.

Anyhow, I will play around further. Probably will post a github link here soon with some examples. Need to go figuring on that mysterious r also.. ;)

And, I said it before and I say it again: thanks raigan2!
raigan2 wrote:We hope to release some more tutorials about this embedding stuff at some point, because I think it's pretty useful and fascinating, and I'd love to see more people exploring the possibilities
I totally agree. This is actually quite awesome! I tossed up quite an interesting rigid body system with weird shapes using just some particles in no time using this way. Oh, and sorry my ignorance here (being a physics-noob), but who are "we"?

Cheers!
raigan2
Posts: 197
Joined: Sat Aug 19, 2006 11:52 pm

Re: Jacobsen & Verlet - embedding simplex in polytopes

Post by raigan2 »

You're welcome! (We're Metanet Software http://www.metanetsoftware.com/blog/)

We made a couple crappy vids using this solver, but then kind of got burnt out. I'm hoping to revisit it sometime though, it had a lot of potential IMO!
https://www.youtube.com/watch?v=YHVyg2rDBy4
https://www.youtube.com/watch?v=AmHZdOuRlvQ

Jacobsen developed his method with the help of Jeroen Wagenaar, who wrote a more extensive PHD on the subject (sadly it's not online; I wrote and got a hard copy once but that was a decade ago, alas); one of the things he did was derive, given a rigid body, how to construct a particle model with the same center-of-gravity and moment-of-inertia.

(in 2d it's pretty easy unless I've completely messed something up, COG is midpoint of stick and MOI is adjusted by scaling the stick length; I've found this helps the sensitive/bouncy problem (i.e increasing rotational inertia stabilizes things); in 3d, well, the math was over my head ;) )

(note: one year at GDC David Wu gave a presentation where he remarked that humans can predict a rigid body incredibly well (and instinctively see when its motion is wrong), but are terrible at predicting articulated bodies and thus you can cheat a lot)

Anyway, good luck! :)
Post Reply