newton model ?

[JernejL]

vor example ARM mobile phones

There's already a iphone & ipod touch build of library availible, and i'm sure julio is capable of building a library for android phones too

[Carli]

I don't see why everyone always wants to make everything open source. "Too many cooks spoil the broth".

That's right. my current project is opensource (GPL) but i do only allow changes that are in my sense. (it's easy to do so with mercurial/hg)

[Stucuk]

That's right. my current project is opensource (GPL) but i do only allow changes that are in my sense. (it's easy to do so with mercurial/hg)

The problem with that is then you have a good chance of someone (Assuming people like what your making) making a split off version, which has its own features and bugs. Which splits your community up into different camps.

With smaller projects (Like a Open Source GUI, Open Source Filesystem, etc) its alright. But large projects can easily become bloated and slow (Take Quake Army Knife for example. While it can support lots of different map formats, its compleatly bloated (Source code is a nightmare to try and understand) and its VERY slow at rendering maps) or have people splitting off like i said above.

Open Source-ing large projects scares me as it can make it a worse "Product". If people could "contribute" to the actual code, then you would proberly find Newton becoming less stable and optimised (Its far easier to debug your own code and make it optimised than code written by 50 other people).

[tiresius]

Julio is making an API. As long as we have documentation on this API there's no need to look at how he does things inside. Hopefully documentation will be coming soon for 2.0. Some people have the idea that Open Source makes better software, that's not always true. And Stucuk hit the nail on the head with branching problems and splitting communities. Julio decided long ago to have closed source for Newton, it is his project, his vision, and he's not obliged to share that with anyone. I just thank my lucky stars that something like Newton is free.

I started this thread because I would like a little more description of the solver (in English not Math), and perhaps a blow-by-blow representation of exactly what happens inside NewtonUpdate. But most of this is just curiosity's sake, the lack of this knowledge doesn't hinder me in using Newton.

[JernejL]

perhaps a blow-by-blow representation of exactly what happens inside NewtonUpdate. But most of this is just curiosity's sake, the lack of this knowledge doesn't hinder me in using Newton.

http://newtondynamics.com/wiki/index.ph ... ks_Diagram

The "3 material contact callbacks" section on bottom is outdated since that was written for a newton2 beta before the material callback was changed to 2 callbacks + material contact iterator, but the general order of things that happen during newtonupdate is same.

[_fleischman_]

I agree that open source in most cases doesn't result in better software. The reason I made my post was that if I remember correctly Julio repeatedly made statements that Newton is just a hobby and sometimes quite a burden for him. I can see some advantages of going open source because of that.

I agree with Carli that the LGPL could make sense for Newton. It's fine for development on PCs. Consoles don't allow the LGPL so he could sell Newton for consoles under a different license and this way make some money from it. The LGPL would also prevent that the current competitors (which all use incompatible more liberal licenses) rip off Newton code.

There wouldn't be too many cooks who spoil the broth since Julio could still be the only one who works on the core. There could be forks which also are licensed under the LGPL but they wouldn't be allowed to use the name Newton. (But the details of going open source would have to be checked by an expert about it.)

However, I don't want to insult or upset anyone so this will be my last post. I just find it worth thinking about.

[thedmd]

In my opinnion it is Julio choice to keep Netwon closed source and not without a reason. As he had said it is a hobby. Becouse of that we cannot expect that he will publish whole work. Personally I did not wish to see how his worrkshop looks like. I wish to final painting instead of looking at painter hands while he is working.

[doodaddy]

I'm two years late to this party, but I had the same question as tiresius! As a newb to physics engines, I was hoping for some clarification of the home page description: "Our engine implements a deterministic solver, which is not based on traditional LCP or iterative methods, but possesses the stability and speed of both respectively."

After reading this thread, it seems this IS an iterative solver with its own sauce!? The thread seemed to be about how many engines cheat with various impulse "laws of physics" to gain speed at the cost of accuracy. The others aren't "traditional."

So my questions are:

1) did I summarize the thread correctly so far?
2) Does an "iterative solver" mean that it works in time slices? (Or maybe it means how it solves within one time slice?)
3) If version 1 was not an iterative solver, what was it before?

I ask because time slices appears to leading to "tunneling" in my game prototype (not using Newton but Torque Game Builder). Tunneling appears to be the terminology for fast objects passing each other in a time slice and not colliding (because one object may move, say 50 units in one time slice and "pass by" a target of 10 units thick that was only 20 units away). I'm trying to avoid simple tunneling for a simple game. If Newton used to (or currently does) avoid this type of "iterative" problem, I'd like to understand.

Thanks!

[JernejL]

Newton possesses anti-tunneling mechanism called continous collision, which i think is based on convex-casting but only Julio can say more about that and how it really works.

[Julio Jerez]

1) did I summarize the thread correctly so far?
2) Does an "iterative solver" mean that it works in time slices? (Or maybe it means how it solves within one time slice?)
3) If version 1 was not an iterative solver, what was it before?

I ask because time slices appears to leading to "tunneling" in my game prototype (not using Newton but Torque Game Builder). Tunneling appears to be the terminology for fast objects passing each other in a time slice and not colliding (because one object may move, say 50 units in one time slice and "pass by" a target of 10 units thick that was only 20 units away). I'm trying to avoid simple tunneling for a simple game. If Newton used to (or currently does) avoid this type of "iterative" problem, I'd like to understand.Thanks!

2) In Newton 1.
There is one solver which is not iterative. This mean it does not run a few number of iteration and bail out.
Instead it run until the error is smaller than some small arbitrary value, for this it use uses a Line Search Conjugate Gradient Descent.
This solver can a find the exact solution of a linear system in a finite number of steps.
Because of that properties you can claimed it is Not iterative.
The adaptive model is the mode where the number of step is fixed, and it uses the solution of the previous frame a first Guess.

In Newton 2.0 the "iterative line search conjugate Gradient Descent" exhibits non linear behavior when used as iterative solver, so I replaced it with Gauss Seidel.
But This is not an ordinary Gauss Seidel as it has embedded a RK (Runge-Kutta) order 4 in the internals sub steps.
This solves rival the Conjugate Gradient when the condition number of the system is reasonable, in Newton 3.0 I will use for everything.

[ledahut]

What you wrote is really important for me. It take me one hour to correct you but it was worth it
I post it here in quotes for others looking for answer with search engine (or foreign peoples using translators).
Some students using NGD like me in theirs schools projects need to explain differences between solvers.

In Newton 1.
There is one solver which is not iterative. This mean it does not run a few number of iteration and bail out.
Instead it run until the error is smaller than some small arbitrary value, for this it use uses a line search conjugate Gradient Descent.
This solver can a find the exact solution number of a linear system in a finite number of steps.
Because of that properties you can claimed it is why it is Not iterative.
The adaptive model is the mode where the number of step is fixed, and it uses the solution of the previus frame a first Guess.

In Netwon 2.0 the "iterative line search conjugate Gradient Descent" exhibits non linear behavior when used as iterative solver, so I replaced it with Gauss Seidel.
But This is not an ordinary Gauss Seidel as it has embedded a RK (Runge-Kutta) order 4 in the internals sub steps.
This solves rival the Line serach Conjugate Gradient when the condition number of the system is reasonble, in Newton 3.0 I will use for everything.

[doodaddy]

Thanks to the three of you for the quick reply! I think I understand now.

I did some mathy grad work 15 years ago and have worked with a static scene iterating over the flow of light until the solution was close enough (radiosity), so I get what you are saying at a high level.

For the record, I think what confused me at first was that I was assuming too much about the home page text of a "non-iterative" solution. (In my time, I would have called all these solutions iterative, but...) The claim here is that it can solve "until close enough" within a time slice. I was confused though and thinking this engine may somehow render physics with no time slices! I guess such a beast does not exist. (But how cool would such a thing be?)

[Julio Jerez]

It appears some people (the self appointed Experts in some forum dedicated to plagiarize commercial libraries) are confused by that two,
and they uses that against me personally as if I had some nepheriuos motivation to confuse the users.
They attack me with comments on other forum but never came here to ask what I meant but that. Instead they make comments for the cheerleaders in places like Ogre and GameDev.net to attack me persona.
They take comment of mine and paste on other thread out of context to make me look incoherent and as if I did not know what I was saying.
Some had even accused me of taking the code from ODE, and I believe any one can see that Newton is very different than any other physic engines in all aspect. I do not think these people can claim the same about their products.
I had never being employee or associated with code from Math Engine, Havok or Phyx, therefore I do not have "Inspiration" to write stuff that look, feel and behave just like the stuff of any former employer.
For me is my math, and experimentation so that is why Newton look, feel and behave different.


On the Iterative vs direct methods for solve system of equation,

This is the Mathematical definition of Iterative process:
An numerical procedure that improves the state of a set of variables in a unknown number of steps. In each step the solution converge asymptotically to the solution but the number if step in unknown.
Guass Sidle, Jacobi, Newton Raphson, the Secant, and so, on are iterative method.

This is the definition of a Direct Method:
An numerical procedure that improves the state of a set of variables on in a finite number of steps.
Gauss Jordan Pivoting, Matrix Inversion, Matrix Factorization are all Directs Methods.

Conjugate Gradient Decent is also a Direct Method, because it can only improve the solution of N variables by finding to fine the N conjugate gradient direction,
so the number of steps is N x N at worse,
due to numerical rounding error the solution is no exact, but once you the contribution of each of the N conjugate direction, the solution does no improves.
So because of that this is classified as a direct Method.
However when you do not run the required N iteration, you have an approximation to the solution, so you can use it a Iterative in the sense that it produces an approximation to the solution, but that has nothing to do with the definition of an iterative method.

I use Line Search Precondition Gradient Decent which has faster converge rate when there are large condition number in the system matrix, so when the first Guess is close the system is almost linear.
However the assumption that a previous solution can be used as first Guess, does not always work well all the time, and this is why you see that Newton exhibit erratic behavior when an object come to contact,
It is because the initial Gauss does not do anything and it need to run almost N^2 iteration.
that led me to replace with a Gauss for the Game mode solver.
and leave the Gradient decent for the people how use for other purpose because want more accuracy.

In any case the Newton solve is still one order of magnitude faster that the Danzig with pivoting used by David Baraff in his 1992 paper.
That solver have a best case n^3 and worse case N^4 , with an n^2 storage.

where using Linear Search Precondition Gradient Decent has a best case N, average N^2 and worse case N^3, with Linear Storage.

The reason this is true is because of the same reason that makes Gauss Sidle fast, this is that you can multiply a sparse the system matrix is linear time (therefore elimination one order of magnitude in the problem) and you do not need to store the results,
were Danzig method requires the complete matrix in advance, and the operations to build the matrix required O(n^2) space plus all known operations to invert or factorize a matrix are O(N^3) complexity.
therefore you have an O(N^3) at the inner loop, but that loop have to be run from 1 to N time, so there is your O(N^4) iteration.