Projected Gauss Seidel patent and other physics patents

Please don't post Bullet support questions here, use the above forums instead.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Projected Gauss Seidel patent and other physics patents

Post by Erwin Coumans »

Did you know about this Ageia patent that describes Projected Gauss Seidel used to solve rigidbody dynamics lcp's?
It's here:
http://appft1.uspto.gov/netacgi/nph-Par ... a&RS=ageia

The patent pre-dates the ODE quickstep (projected Gauss Seidel) development but it describes the same algorithm and optimizations.

Here are some more patents related to physics simulation:
http://www.continuousphysics.com/Bullet ... .php?t=245
Last edited by Erwin Coumans on Sun Feb 19, 2006 6:05 pm, edited 6 times in total.
Etherton
Posts: 34
Joined: Thu Aug 18, 2005 6:27 pm

Post by Etherton »

Wow this is outrageous and disgusting.
Projected Guass Seidel is been used by mostly all real-time physics engines since they became a software commodity.
I used to work with Math Engine before it when under and the last incarnation implemented the same method and it was called the Arthur Solver, recommended for consoles like PS2 and Game cube.

The version implement in ODE was borrowed from the Croesia Team (Serious Sam) which was using ODE long before Novodex and Agia where even founded. Havok also uses the method for over 6 years and the method is probably used by all of the free physics engines.

To get a Patent all it is needed is a lawyer and 2000 us dollars. But come on do these people have any sense of ethics and honesty?

It seems these people want to re-write the history :shock:
Last edited by Etherton on Wed Jan 04, 2006 12:56 am, edited 1 time in total.
Erin Catto
Posts: 316
Joined: Fri Jul 01, 2005 5:29 am
Location: Irvine
Contact:

Post by Erin Catto »

It looks like right now it is just an application. Let's hope it gets rejected.

Isn't Richard Tonge from MathEngine? Doesn't Criterion own the MathEngine IP?
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Post by Erwin Coumans »

Wow this is outrageous and disgusting.
Projected Guass Seidel is been used by mostly all real-time physics engines since they became a software commodity.
I used to work with Math Engine before it when under and the last incarnation implemented the same method and it was called the Arthur Solver, recommended for consoles like PS2 and Game cube.
Havok's iterative solver and Arthur are impressive solvers, but they are not projected gauss seidel. I can't tell more, just trust me ;-)
The version implement in ODE was borrowed from the Croesia Team (Serious Sam) which was using ODE long before Novodex and Agia where even founded.
I hope there is prior art too, but I don't know of any.

Erin Catto wrote: It looks like right now it is just an application. Let's hope it gets rejected.

Isn't Richard Tonge from MathEngine? Doesn't Criterion own the MathEngine IP?
Richard is ex-Mathengine, and now Ageia. As far as I know, the Projected Gauss Seidel is not Mathengine IP. The Arthur solver was different.
Antonio Martini
Posts: 126
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Post by Antonio Martini »

as far as i can remember the mathengine patent is not about direct methods in general but it's about _a_ direct boxed LCP solver which i haven't not seen in any books before. Dantzig modified for the boxed case in short. But my knowledge may be limited.

ragarding patenting the PGS it's like patenting a standard text book algorithm(Cottle and Pang, pages 395-396). Let's say LU decomposiotion applied to A, where A is an arbitrary application. Being optimistic i guess that the patent is more related to the specific PGS Richard developed, which involves some clever optimisations we now know well about. However i have not read the patent in full, it's just my feeling about what could be fair to patent or not in the given context.
User avatar
Erwin Coumans
Site Admin
Posts: 4221
Joined: Sun Jun 26, 2005 6:43 pm
Location: California, USA
Contact:

Post by Erwin Coumans »

Being optimistic i guess that the patent is more related to the specific PGS Richard developed, which involves some clever optimisations we now know well about.
Well, the patent describes exactly the implementation and optimizations used in the fast iterative quickstep solver in ODE, as well as the PGS descriptions in Erin Catto's GDC paper (http://www.gphysics.com/files/IterativeDynamics.pdf) and Kenny Erleben's PhD (around Chapter 6.1.6 in http://www.diku.dk/~kenny/thesis.pdf)

1) use of projected gauss Seidel to iteratively solve the lcp
2) optimization of the innerloop (avoid looping over the entire row)
3) fixed number of iterations as ending criterium
4) storage of jacobian J as s*12 instead of s*6n because each row has at most two nonzero blocks of length 6

Antonio, can you find any optimizations described in the patent that are not in quickstep, or the other way around? You can start reading the last few pages of the patent to avoid falling asleep ;-)
Julio Jerez
Posts: 26
Joined: Sat Jul 23, 2005 12:56 am
Location: LA

Post by Julio Jerez »

AntonioMartini wrote: ragarding patenting the PGS it's like patenting a standard text book algorithm(Cottle and Pang, pages 395-396). Let's say LU decomposiotion applied to A, where A is an arbitrary application. Being optimistic i guess that the patent is more related to the specific PGS Richard developed, which involves some clever optimisations we now know well about. However i have not read the patent in full, it's just my feeling about what could be fair to patent or not in the given context.
If everybody knows the optimizations that means it is public domain knowledge and not one can claim invention for it.

I read the Patent application and there is nothing there that can be considered an invention, a new implementation, not even an algebraic arrangement for better exploitation of specific hardware. Let?s face it this is not a ?Cooley Tucky FFT? formulation of an LCP. As far as I concern they are trying to patent public domain knowledge.

This is not the first time these kinds of blunders happens a few year back a big game producer had the brilliant idea of trying to patent a spline subdivision as a new geometry compression technology and he was scorned by everybody, let us see how this one goes.

It is okay when people re-write the algorithm for a dissertation or a paper because the just want to get their degree after few year of studies but this is more serious.
Here is my question. Say these people get the patent, does this mean they can go after every institution using a Gauss Seidel LCP aproximation for anything at all.
This must have to be and april (came ealy this yera) fool joke or urban legend Joke.

About the second Math Engine Patent I also have reservations. I do not understand what is different on that patent and David Baraff algorithm for solving an LCP program.
They are both the same Danzig method line by line. Baraff paper and the Patent match line by line, except that Baraff paper is predate the patent by 6 years.
No disrespect but they both look very much identical.
Antonio Martini
Posts: 126
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Post by Antonio Martini »

Erwin Coumans wrote: 1) use of projected gauss Seidel to iteratively solve the lcp
2) optimization of the innerloop (avoid looping over the entire row)
3) fixed number of iterations as ending criterium
4) storage of jacobian J as s*12 instead of s*6n because each row has at most two nonzero blocks of length 6

Antonio, can you find any optimizations described in the patent that they are not in quickstep, or the other way around? You can start reading the last few pages of the patent to avoid falling asleep ;-)
regarding points 1 and 3(PGS and related ending criterium) i think we all agree that are standard numerical procedures. So at least to me it seems obvious that they are not "patentable".

2 and 4 i think are more for the lawyers:) I dont know exactly what the requirements for a patent application are in order to be valid. For example one of the requirements could be that even if a person believes he/she has invented something it should not be already documented/available elsewhere at the moment of the application. However as im not an expert in such matters there is no much more i can say;)
Last edited by Antonio Martini on Wed Jan 04, 2006 7:20 pm, edited 3 times in total.
Antonio Martini
Posts: 126
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Post by Antonio Martini »

Julio Jerez wrote:About the second Math Engine Patent I also have reservations. I do not understand what is different on that patent and David Baraff algorithm for solving an LCP program.
They are both the same Danzig method line by line. Baraff paper and the Patent match line by line, except that Baraff paper is predate the patent by 6 years.
No disrespect but they both look very much identical.
they are not the same line by line, the Baraff algorithm doesn't allow for low and hi force limits. Motors and Friction require such force limits in the karma solver(or ODE's direct solver).

regarding the Richard's patent, the optimisations exploit the structure of the problem and so they are specific to rigid body dynamics. They allow
to reduce the memory footprint and speedup the algorithm compared to a standard PGS implementation. I think we can all appreciate the algorithm, the main point is if it can be legally considered an invention and if we morally agree on the overall patenting approach.

to be more specific the PGS patent has been filed on March 8, 2004.
was quickstep already in ODE at that time? were those optimisations already available in some form elsewhere?

http://cvs.sourceforge.net/viewcvs.py/o ... 8&view=log

the first version of quickstep is dated:
Tue May 18 18:12:30 2004 UTC (19 months, 2 weeks ago) by russ_smith
Julio Jerez
Posts: 26
Joined: Sat Jul 23, 2005 12:56 am
Location: LA

Post by Julio Jerez »

AntonioMartini wrote:they are not the same line by line, the Baraff algorithm doesn't allow for low and hi force limits. Motors and Friction require such force limits in the karma solver(or ODE's direct solver).
With all due respect I do not think you completely understand what you are talking about. Motors and limits has nothing to do with teh underline matehematical algorithm.
Danzig and Lenkel methods both allowed for up and downs limits.
David Baraff was derived to handle specifically contacts, in that case the lower limit is zero and you do not need the code. In his paper he explain how to extend it to handle bilateral constraint. So adding the complement part to check the lower limit is not an invention.
It is okay because no one really takes that seriously as the method is a 0(n4) time complexity.
AntonioMartini wrote: regarding the Richard's patent, the optimisations exploit the structure of the problem and so they are specific to rigid body dynamics. They allow
to reduce the memory footprint and speedup the algorithm compared to a standard PGS implementation. I think we can all appreciate the algorithm, the main point is if it can be legally considered an invention and if we morally agree on the overall patenting approach.

to be more specific the PGS patent has been filed on March 8, 2004.
was quickstep already in ODE at that time? were those optimisations already available in some form elsewhere?

http://cvs.sourceforge.net/viewcvs.py/o ... 8&view=log

the first version of quickstep is dated:
Tue May 18 18:12:30 2004 UTC (19 months, 2 weeks ago) by russ_smith
About Richard Tongue he is claiming the invention of storing J and JM into and indexed flat array. This is not an invention I had been using that as early as 1999. And I am not claiming an invention. I do not think anybody is.

Did you know that long before ODE realizes this could be done that way there were other engines doing the same publicly. I did it in Newton.
Or you also think that My solve is a copy of ODE like the stablishment hint in many circles.

In a nut shell this is what he is claimimg in three lines of symbolic math:

J A? J? * X = b can be executed by using a temp variable
Y = J? X
J * A? * Y = b
And that by the particular properties of Gauss Siddel the J * Y and J * A? Y can be done
with a recurrent formulations, by keeping Y as intermediate variable.

Let me tell you a secret lots of people are doing that for so many years.

Further more I discussed this same topic with Richard Tonge, Manju Edge and Mike Skololone (all from from AGIA) in May 2004 when they invited me to a meeting to discussed the possibility of using Newton with theirs vector coprocessor. In reality what they wanted was to fighure out what do I do to get my solver stable.
In the meeting I quickly realized the situation and I quickly exposed the exact about equations. He was in oh that I knew that.

It is not that I am and expert but I can hold my own with Math and Physics and this letlte twist may fool and untrained eye belief me it does nto fool me.
Following that reasoning I thing I can have 5 or 6 patents with Newton.

BTW in the meeting at AGIA I said I pass, I was not going to surrender Newton for then to dissect for free.

And truth me Newton is 100% correct LCP solver (with is the limitation of round off numerical precision and condition number below 10000 in single presistion numbers)
Julio Jerez
Posts: 26
Joined: Sat Jul 23, 2005 12:56 am
Location: LA

Post by Julio Jerez »

sorry double post
Last edited by Julio Jerez on Wed Jan 04, 2006 8:00 pm, edited 1 time in total.
Antonio Martini
Posts: 126
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Post by Antonio Martini »

Julio Jerez wrote:
In his paper he explain how to extend it to handle bilateral constraint. So adding the complement part to check the lower limit is not an invention.
It is okay because no one really takes that seriously as the method is a 0(n4) time complexity.
I have implemented the baraff's algorithm many years ago with all the due respect for your language. In a bilateral constraint the forces are in the range -+ infinite.Contact allows for forces in the range 0,+infinite. the boxed LCP for low-high,limits. What you are basically saying is that something which is very simple is not an invention. To me that's not necessarily the case, given that slight modification allows to solve a wider range of problems. The baraff algorithm is O(n^3).
I agree that each single algorithm we are talking about could have been
"invented" by anybody working in the field at the same time o many year before. But inventions are more about who did it first i guess, or better about who did first and made it public, this considered that around there are many simple great original ideas and they still count as invention dont they?:)
Julio Jerez wrote:
About Richard Tongue he is claiming the invention of storing J and JM into and indexed flat array. This is not an invention I had been using that as early as 1999. And I am not claiming an invention. I do not think anybody is.
Did you know that long before ODE realizes this could be done that way there were other engines doing the same publicly. I did it in Newton.
Or you also think that My solve is a copy of ODE like the stablishment hint in many circles.
In a nut shell this is what he is claim this in three lines of symbolic math:
if in Newton you did the same or similar but nobody know about it that's not public domain knowledge i guess. It looks like that you have misunderstood what im trying to say and im going to try to be clearer here. Im _not_ in favour of patents, however there is a law, if somebody applies for a patent that laws applies if we like it or not. So what im interested in it's not if many other people did the same or bettter in their secret room given that i have no doubts about it. But im more interested to see if it possible to show that at the moment of the application there was sufficient available information (papers/code) in order t invalidate the "invention"
Last edited by Antonio Martini on Wed Jan 04, 2006 9:05 pm, edited 2 times in total.
Antonio Martini
Posts: 126
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Post by Antonio Martini »

Julio Jerez wrote: Danzig and Lenkel methods both allowed for up and downs limits.
David Baraff was derived to handle specifically contacts, in that case the lower limit is zero and you do not need the code. In his paper he explain how to extend it to handle bilateral constraint. So adding the complement part to check the lower limit is not an invention.
i was referring to what you wrote:

"Baraff paper and the Patent match line by line, except that Baraff paper is predate the patent by 6 years."

and it seems clear in what i replied:

"they are not the same line by line, the Baraff algorithm doesn't allow for low and hi force limits. Motors and Friction require such force limits in the karma solver(or ODE's direct solver). "

but now you seem to agree that they don't match line by line anymore. So problem solved;) The Baraff's algorithm with equality constraints added is not the same as the low-high force limits case but is the special case of when low=-inf and high=+inf. both friction and motors in the model employd by ODE and Karma required finite force limits.
Julio Jerez
Posts: 26
Joined: Sat Jul 23, 2005 12:56 am
Location: LA

Post by Julio Jerez »

AntonioMartini wrote: I have implemented the baraff's algorithm many years ago with all the due respect for your language. In a bilateral constraint the forces are in the range -+ infinite.Contact allows for forces in the range 0,+infinite. the boxed LCP for low-high,limits. What you are basically saying is that something which is very simple is not an invention.
Well maybe that was your intepretation, I had been working with simplex Convex quadratic programming long before Baraff paper. When I Saw his formulation I implemented and I never used the 0 and infinity limit as matter of fact that infinity mombo-jumpo has hampered ODE for many years into making gratuitous explosion for nto particular reason (so there you go)
AntonioMartini wrote:The baraff algorithm is O(n^3).
For the record that goes to show you are reading the paper and relating what you read with very little critical analysis.
Here is the proff the LCP is O(n4)
Baraff did not lie but he mislead the people into thinking the method is and O(n3) and he say that is a worse case np complete. Whicj is a way of saying that is can only be expressed as a polynioming of O (n + n2 + ?n^n) it is truth but it is measleading.
In fact the method is presiselly O(n^4) average case and best case O(n3)

Proof:
The inner loop of the method solves n x n a linear system by either LU or Colesky factorization.

The outer loop solve either a n x n or (n+ 1 * n+1) linear system
So the time complexity is a geometric progression of the form

O = k * 1^3 + K * 2^3 + ?. .k * N ^ 3

The general turn of that regrasion is (goolgel for it if you like)

S = K1 * O(N^3) + K2 * O(N * 4)

The average come for the fact that the clamped variable are solve at last
So the lower composed of the regression are zero they are insignificant compare to the largers systems .

For example say you have a stack with 100 rows, and only 4 at the bottom are contacts
That is 4 of those rows are to be clamped.

The total time is assuming k is const

96^ 3 + 97^3 + 98^3 +100^3 =
if all o fteh point are contacts then the added values is totally marginal

since the larger part of the row are contacts yes the method is and average o(n4)
Antonio Martini
Posts: 126
Joined: Wed Jul 27, 2005 10:28 am
Location: SCEE London

Post by Antonio Martini »

Julio Jerez wrote: For the record that goes to show you are reading the paper and relating what you read with very little critical analysis.
given that you seems so good at it i would advice you to do also some critical analysis of your writing style;)
Julio Jerez wrote: The inner loop of the method solves n x n a linear system by either LU or Colesky factorization.
wasn't in an incremental LU/cholesky factorization done in O(n^2)?

no time to read the rest and to be honest im not that interested given that it's a long time that i dont work on that stuff anymore.Among the other things it's offtopic in repect to this thread which is more about patents rather than computational complexity.
Post Reply