Skip to main content

Summer of Code - Physics Engine

7 replies [Last post]
timloff
Offline
Joined: 2006-05-06

I'm a student considering an application to Google's Summer of Code to work on your proposed 3D Physics Engine idea. I'm not sure what you want out of the engine, though. Is it meant to be a general-purpose physics engine, like the kind that a game could run on? Would it be composed of several widget-type effects, like maybe a turn-the-window-into-jello effect or a particles physics effect? I want some more detail about the specifications, or what you hope to use the engine for.

Reply viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.
paulby
Offline
Joined: 2003-06-13

There are already a couple of simple demos in lg3d that use Spring/Damper for some interesting effects (object layout and the cloth simulation). What we need is a centralized physics system that uses a robust solver such as rk4 and is extensible. Collision detection and reaction would also be interesting and a particle system would be a huge bonus.

tobiasevert
Offline
Joined: 2006-05-08

When implementing the solver, you might want to check into the verlet solvers too, from what I understand they can be as robust as rk4 on rigid body systems but work faster. Please correct med if I am wrong though.

rkd
Offline
Joined: 2005-02-16

I believe that's pretty-much correct.

The best paper I've seen on the subject is [1]. They've tested and compared different solvers in terms of balancing their accuracy (where RK4 wins and the Verlet methods are variably less good but still reasonable) and their performance (where RK4 bows to the Verlet winners).

I'd suggest the best algorithm would be a velocity-Verlet integrator since it's reasonably accurate, gives you velocity values (handy for those velocity-related damping systems) and is still pretty fast.

I'd see the goal being to write the code in such a way that different integrator implementations can be added later and applied to different targets that may prefer them (e.g. particle effects that know they don't need a velocity value or as much accuracy might programmatically (or even config-filely) opt for a different integrator.

1. "A Versatile and Robust Model
for Geometrically Complex Deformable Solids"
http://graphics.ethz.ch/~brunoh/download/DeformableSolids_CGI04.pdf

rkd
Offline
Joined: 2005-02-16

P.s. (some thoughts)

Perhaps we might want to separate the project into some sub-projects/stages:
a. Physics Engine implementation
b. LG API into PE (for both core and user apps)
c. Example LG apps using PE
d. LG core uses of PE
e. LG superfluous uses of PE

Suggested examples of each...
(c) reimplement the Pong demo using PE, rolling-dice demo, cloth example (if using deformable-body-capable algorithm), etc.
(d) include scene-manager uses such as seamless switching between present interpolator system, PE-based system and back again (e.g. by reading previous positions, use as initial values for integrator and continue ad infinitum - damping optional ;) )
(e) blowing-up, melting, etc windows (mwuh-hahaha ]:) )

For (b), perhaps any interested parties would care to start an new thread on API suggestions people think they'd want? That'd be a super input to the project!

Lastly, one /potentially impractical/ goal might be keeping it sufficiently loosely coupled to LG that it can be useful for other projects. There's currently a thread running on our sister group "Java3D-interest" regarding available "java game engin" (sic). The solution here /might/ be a façade patterned interposing layer for LG use, presenting a simplified API for general LG-use but allowing access to the lower-level for other projects and LG power-coders 8)

p.p.s. Yes, I've been 'working' in this area :D
Hmm... yup - reckon I'd like to formally volunteer any help I can give including mentoring if useful. (I've lurked too long.) HTH.

paulby
Offline
Joined: 2003-06-13

I agree, the scope of 'Physics Engine' is way to broad (unless you have a Havok license ;-)). We should definately break the project into a number of subprojects and ensure that we have a consistant API etc. That's sort of where I was heading with my comment about extensible and pluggable. I've only dabbled in physics so it's great to have someone on the team with a better domain space knowledge.

I'm not sure how many students have shown and interest in the physics work, I'll check with Krishna. Any help in mentoring students would be greatly appreciated.

As we did last year we plan to have all technical discussions with students on this forum/alias so everyone can chip in with ideas and/or learn from the discussion.

timloff
Offline
Joined: 2006-05-06

There's something I don't understand about RK4. Or lots of other integrators, for that matter.

Consider two objects gravitationally pulling each other. Both are free to move, and for the sake of simplicity, let's say they have the same mass. That means they will move toward each other at the same rate.

For RK4, we need to make four calls to our differential equation F, which tells us the gravitational force. In this case, F is simple: it's something like

F = k * (M ^ 2) / ((x1-x2) ^ 2)

where k is a constant, M is mass, x1 is the position of object 1 and x2 is the position of object 2. As we make our force calls for object 1, the only variable among these that will change is x1, as the object's position is recalculated. But doesn't the second object move too? Given the symmetry, x2 should change by exactly how much x1 does, but in the opposite direction. It seems that RK4 ignores this. It assumes the environment remains stationary while the single particle being considered moves.

The only way to fix this problem, that I can see, is to step all the objects through each of the four stages of RK4 without moving on to the next step. In other words, step the entire system ahead through each stage instead of sequentially stepping each object through all the stages.

Is that the norm? Is there a different way? Is this inaccuracy usually ignored? I have been unable to find the answer to this question, since all the RK4 examples I find on the internet involve a single object or a single spring. The idea of sequential vs. simultaneous never comes up. Thanks.

- Tim Loff

rkd
Offline
Joined: 2005-02-16

Hi Tim,
*DISCLAIMER*: All this is 'as I understand it' - apocrypha ensue ;) Anyone with better understandings - please post!
That said, I'm 95% confident this is correct -- unlike my "velocity Verlet" comment (earlier in this thread) where I'd forgotten the basic VV assumes a non-velocity affected force function. Doh!

> In other words, step the entire system ahead through each stage instead of sequentially stepping each object through all the stages.

The short answer is "yes".

But only for tightly coupled subjects. By this I mean groups of subjects whose forces change dependent upon each other.
The gravitic example you describe needs it. For modeling [b]*all*[/b] objects in the world affecting each other through gravity: yes - you'd step the whole world's state [i]/if you wanted the best accuracy possible/[/i]. Whether you need that accuracy's down to scenario. For LG, it be [i]/nice/[/i] to have it as an option - meaning first implementation should allow for a future version to implement.

That said, most simulations aren't entirely composed of every object affecting every other object. If you're dealing with N nodes with forces between (e.g. 1 set of springs, 1 cloth, 1 ragdoll, etc) optionally interacting with M static objects, you only need to step the N nodes together. For multiple tightly coupled systems to interact with each other, one needs to consider them as 1 system and, again, step together. Determining when that's happening is obviously a 'fun' part ;)
In summary, ideally, one codes the integrator in such a way that it will handle temporary sets of state data to integrate together and make compiling those sets a separate [possibly future] task.

Obviously, there exists a large set of physics problems that do not need this level of complexity.

Also, all of this assumed a Runga-Kutta integrator was our subject. There are other robust integrators that do not need hypothetical future states. Some of these use known past states - the multistep integrators! The Verlet integrators come under this category. These use [b]*previous*[/b] frame data and, depending upon which Verlet, [i]/may/[/i] only evaluate the force equations once. That said, annoyingly some Verlet methods do evaluate force equations more than once and some also calculate [admittedly intermediate] extra frames (but at most 2 as far as I've seen).

Hmm... perhaps a more complex answer than wanted but hopefully of some use. Btw, sorry for the delay while I paged some of this stuff back in from reference ;)
Looking forward to the next question :D