Position Based Dynamics: Patent

[Eternl Knight]

raigan2,

I, for one, would be grateful to hear how/if this is resolved. Software patents are an anomaly in the patent system. The fact they are allowed to exist at all comes from case law (as there is nothing in the Patent Statutes on them right now).

Funnily enough one of the latest patent cases before the US Supreme Court (SCOTUS) had a judge remark that they haven't actually had the question of "software patent" legality before them (i.e. it is possible should someone push the issue that software patents will be declared illegal by the SCOTUS.

The European Union, while still "granting" software patents through their patent offices, have said they are explicitly not allowed. In other words, while alot of corporations own software patents in Europe, they cannot use them in court for fear of losing ALL of them. Hence the huge business push last year to change the EU patent law to allow them (which luckily failed).

I would be very interested in seeing how Ageia handles this because I have a feeling that they (i.e. their legals) were caught by suprise that someone picked up on the fact that the patent could be invalidated quite so easily. The fact it is a generalisation of Jakobsen's method brings it into the "obviousness test" arena, and the latest decision by SCOTUS makes this very dangerous territory for them.

--EK

[Oscar Civit Flores]

I'm just wondering if Jakobsen is aware of his algorithm being patented by others. Maybe someone could contact him... I mean, come on! The guy develops a super simple and fast algorithm, publishes it in gamasutra/GDC, and someone else comes and literally steals what he gave for free to everybody. So in practice they're not just robbing Jakobsen, they're robbing ALL of us who had the opportunity to use his ideas and now we don't.

I was not suggesting boycott as an action but as a reaction, so, if they don't troll you, fine, but if they did, that reaction to their action would be justified and, according to Newton, necessary.

In any case, there is no need to cite the posbaseddyn paper at all. Almowst every single important idea is available in some previous work, most of them in Jakobsen's, but also in Provot's, and, going a bit further, in Lagrange's

Oscar

[raigan2]

To be fair, the paper does develop the generalization of Jakobsen's method, which is something I tried to figure out myself over a couple years while I was in school -- with no results.

[Oscar Civit Flores]

I can't agree...
Understand me, I don't say the paper's bad or wrong, in fact, it's very clear and gives all information required to implement it, so in a tutorial sense, it's a very good paper, but the ideas are not new.

Anyhow, good luck with all this and keep us informed (just in case somebody else in the forums has, by chance, implemented a similar method NOT based on the posbaseddyn paper )

Oscar

[raigan2]

That was meant in reply to your "comes and literally steals" comment -- Muller provided a lot of important details and work that was absent in Jakobsen. I agree it shouldn't be patentable, but it's not like the PBD paper is without merit -- it's awesome!

Anyway, it seems like the patenting was just an automatic part of the business pipeline which Muller has nothing to do with. I'll write more soon..

[Oscar Civit Flores]

For me patenting something which was, in fact, free knowledge, is stealing in a strict sense. So my stealing accusation is on the patent, not the paper, of course.

So let's blame the lawyers, they're used to it

Oscar

[KenB]

Well, I think Jacobsen's way of presenting "his" method is sound since he doesn't quite claim alot of credit for it. "His" method is very well known as the lowest order approximation to a set of methods used in molecular dynamics (for rigid body molecules) since the early 80's (and those papers also refer to things done already in the 70's).
The "computer graphics way" of claiming right to "novel invented algorithms" is not sound at all, and often totally lacks respect for previous work in the literature.

I'm just wondering if Jakobsen is aware of his algorithm being patented by others. Maybe someone could contact him... I mean, come on! The guy develops a super simple and fast algorithm, publishes it in gamasutra/GDC, and someone else comes and literally steals what he gave for free to everybody. So in practice they're not just robbing Jakobsen, they're robbing ALL of us who had the opportunity to use his ideas and now we don't.

I was not suggesting boycott as an action but as a reaction, so, if they don't troll you, fine, but if they did, that reaction to their action would be justified and, according to Newton, necessary.

In any case, there is no need to cite the posbaseddyn paper at all. Almowst every single important idea is available in some previous work, most of them in Jakobsen's, but also in Provot's, and, going a bit further, in Lagrange's

Oscar

[pinballwizard]

Well, I think Jacobsen's way of presenting "his" method is sound since he doesn't quite claim alot of credit for it. "His" method is very well known as the lowest order approximation to a set of methods used in molecular dynamics (for rigid body molecules) since the early 80's (and those papers also refer to things done already in the 70's).

While I'm aware of Barth and Leimkuhler's earlier work on particulated rigid bodies, constraints, and Verlet integration, I am not aware of earlier work that uses Jakobsen's scheme of an "embedded tetrahedron" in collision geometry, and using Barycentric coordinates to express and resolve the point of deepest penetration. Do you know any references before Jakobsen that use Jakobsen's scheme for collision handling? For instance, if I recall correctly, Barth and Leimkuhler don't deal with rigid body collision at all.

[KenB]

No, but in my experience Jacobsen's scheme isn't so efficient for rigid bodies anyway. It is certainly useful for simple cloth models and often for ragdolls, but due to the extreme damping, this is really where the usefulness ends.

While I'm aware of Barth and Leimkuhler's earlier work on particulated rigid bodies, constraints, and Verlet integration, I am not aware of earlier work that uses Jakobsen's scheme of an "embedded tetrahedron" in collision geometry, and using Barycentric coordinates to express and resolve the point of deepest penetration. Do you know any references before Jakobsen that use Jakobsen's scheme for collision handling? For instance, if I recall correctly, Barth and Leimkuhler don't deal with rigid body collision at all.

[raigan2]

We're using it for 2D rigid bodies -- if you use a stick (2 particles) instead of a triangle for the dynamics model, things are much simpler. You need to use Muller's generalized version though.

The main benefit of this approach, for me, is that it replaces the usual math with geometry/vector calculus, which I find a lot simpler to deal with. It also lends itself to automatic-differentiation and other tools to handle the tricky bits automatically

Orientation/angular constraints are easy, as are more esoteric constraints -- we just finished a proof-of-concept "soft-skinned" solver, where collision models aren't rigid but instead are made of verts which are bound/blended between multiple bodies -- the solver figures out how to distribute "force" between the bodies appropriately to solve any constraints associated with a point on the surface of the collision model.

It's also quite easy to couple arbitrary DOFs (point on bodyA bound to orientation of bodyB), and motorizing things is equally straightforward. We also have a rope solver, which solves N distance constraints simultaneously.. it's actually pretty trivial to do a lot of weird stuff. Possibly the same things are easily accomplished using more traditional methods though, I don't have much experience with them.

Sadly we don't have any demos yet, this has taken a back seat for the past month or two; hopefully soon we'll have things together. Frankly the "physics" is trivial compared to the software engineering problems -- designing a system where you can describe DOFs generically and easily plug them together is somewhat beyond our experience


Finally, concerning the patent, over email they seem to have conceded that (being a generalization of an existing method) it's not defensible -- however I realize that wouldn't help me in court. They suggested that we obtain a free license to their SDK, so that we would be able to legally use their technology (though we'd be using our own implementation rather than theirs); we felt that this could be seen as an admission that they rightfully own the technology in question (certainly they own their PhysX SDK and hardware, but not the math behind them!) so we've just left things in limbo.

thanks,
raigan

[pinballwizard]

No, but in my experience Jacobsen's scheme isn't so efficient for rigid bodies anyway. It is certainly useful for simple cloth models and often for ragdolls, but due to the extreme damping, this is really where the usefulness ends.

While I'm aware of Barth and Leimkuhler's earlier work on particulated rigid bodies, constraints, and Verlet integration, I am not aware of earlier work that uses Jakobsen's scheme of an "embedded tetrahedron" in collision geometry, and using Barycentric coordinates to express and resolve the point of deepest penetration. Do you know any references before Jakobsen that use Jakobsen's scheme for collision handling? For instance, if I recall correctly, Barth and Leimkuhler don't deal with rigid body collision at all.

Regarding my original question, I'm starting to think that the expression of the penetration point in barycentric coordinates and the pushing of all particles (in weighted fashion based on particle mass) in the reverse direction of the penetration vector is related to collision detection concepts in general, stuff like Minkowski sums and simplexes that I don't understand. However I saw something about using a "simplex" for determination of penetration depth, and since Jakobsen's RB scheme does use simplexes (tetrahedrons in 3D, triangles in 2D), this might be how the collision resolution strategy was developed.

Regarding your comments, KenB, John Schultz at http://www.brightland.com/physics has posted interesting ideas (also discussed on this forum) about preserving kinetic energy, thus eliminating energy loss due to damping (rigid bodies without friction will bounce around forever, he says). I haven't implemented it myself but the idea sounds straightforward.

Still, I'm interested in the original thinking about Jakobsen's collision resolution scheme - where does the idea (Barycentric coordinates for penetration point, push all particles in weighted fashion against the penetration vector, let the tetrahedron stick constraints induce the needed torque on the body) come from?

[raigan2]

I don't think these papers by Barenbrug/Overveld have been mentioned yet; they presents a particle-only approach where rotational effects "emerge" (although I believe they use a force-based constraint model):
http://www.win.tue.nl/dynamo/publications/mtfbwy.zip
http://www.win.tue.nl/dynamo/publications/aynif.pdf


My (limited) understanding is that the ideas of:
(1) embedding geometry in a space that's rigidly bound to a dynamics model
(2) transforming any constraints/forces/etc. described in terms of the geometry into equivalent constraints/forces/etc. described in terms of the dynamics model
are found in all rigid body simulators -- more traditional methods just happen to use a different dynamics model for (1), which requires different math for (2).

[Oscar Civit Flores]

It seems that they've also invented asynchronous programming (tm)

http://www.freepatentsonline.com/20070038424.html

If you look at the example function calls you'll see some familiar Nx prefixes

Oscar "Sue, me first!" Civit

[KenB]

It seems that they've also invented asynchronous programming (tm)

http://www.freepatentsonline.com/20070038424.html

If you look at the example function calls you'll see some familiar Nx prefixes

Oscar "Sue, me first!" Civit

I have a real hard time understanding this "invention", even though I've read it twice now. The patent covers an asynchronous SPH API??? Is this a joke?

Am I missing something? Where is the invention???

[Oscar Civit Flores]

For some reason it's usually impossible to read patent claims without falling asleep... I'm sure they do it on purpose. Anyhow, I understood the same you did (before falling asleep): An SPH API with asynchronous execution... what's new in that?

It's so sad...

Oscar