Game Mechanics - Resources

This topic is yours ! Post your physic resources here so we can have a complete knowledge base

Physics

Baraff’s LCP algoritm, as used in ODE (and JOODE)
http://www.cs.cmu.edu/~baraff/papers/sig94.pdf
and why it doesn’t always work:
http://crl.nmsu.edu/users/sb/papers/thesis/node20.html
Good introductory material
http://www.d6.com/users/checker/dynamics.htm

Collision detection

BSP trees. Can be used to classify space quickly
http://www.faqs.org/faqs/graphics/bsptree-faq/

The OBB tree, provides a fast boolean result for trimesh collisions
http://citeseer.ist.psu.edu/gottschalk96obbtree.html

DEEP, Dual-space Expansion for Estimating Penetration Depth. http://www.cs.unc.edu/~geom/DEEP/icra02.pdf
See http://www.java-gaming.org/forums/index.php?topic=10976.195 for hints on deciphering this paper

Example of the sweep line algorithm, the fore father of initial planar subdivision algorithms (but a bit outdated now)
http://www.lupinho.de/gishur/html/Sweeps.html

Math:-

JAMA is comprised of six Java classes: Matrix, CholeskyDecomposition, LUDecomposition, QRDecomposition, SingularValueDecomposition and EigenvalueDecomposition.
http://math.nist.gov/javanumerics/jama/

Wikopedia’s writup of Cholesky is fairly easy to read. Cholesky decompositions are used to solve linear equations. They use alot of square roots though.

The Orbital library is a class library providing object-oriented representations and algorithms for logic, mathematics and artificial intelligence. It comprises theorem proving, computer algebra, search and planning, as well as machine learning algorithms.
http://www.functologic.com/orbital/

ECJ is a research Evolutionary Computing system written in Java. (Good for optimizations)
http://cs.gmu.edu/~eclab/projects/ecj/

i found these intresting video lectures if somebody intrested in the most basic topics of algebra etc:

http://ocw.mit.edu/OcwWeb/Mathematics/18-06Spring-2005/VideoLectures/index.htm

Do you have other resource links for:

  1. programming constraints - especialy how to code it and solve as lcp
  2. resting contacts - the same how to code it

Baraff papers (http://www.cs.cmu.edu/~baraff/papers/sig94.pdf) explain that. However I find them a bit hard (I’m actually looking for simpler documents that can drive me to understand Baraff’s work).

there are lots of academics papers which for programmers without excellent knowledge of mathematics and advanced physics are hard to understand. I saw Baraff work but it is not for me, j have not graduated physics studies… so i am looking for simpler papers just like you MagicSpark.org [ BlueSky ], so please post something if you find, thanx

http://softsurfer.com
is another nice site

thanks for sharing the resource about physical and math. But most of them seemed a little theoretical, if we can share the imformation about physical and math coding ,it will be nice.

The Game Programming Wiki contains some math and physics tutorials :

http://gpwiki.org/index.php/Tutorials_and_Source_Code#Physics_.2F_Math_.2F_Transformations

Here are some more resources from a forum on the Bullet engine:

http://continuousphysics.com/Bullet/phpBB2/viewtopic.php?p=1935#1935

In summary, a good collision detection paper:
http://www.continuousphysics.com/ftp/pub/test/index.php?dir=physics/papers/&file=gino_van_den_bergen_phd.pdf

and some theses on implementing a physics engine:
http://www.diku.dk/forskning/image/publications/erleben.html

Java applets focusing on physical forces + explanations:
www.myphysicslab.com

A list contains main Physic Engines available Internet.
http://www.digitalrune.com/KnowledgeBase/RigidBodyDynamics/PhysicsEnginesList/tabid/476/lang/en-US/default.aspx

I may be missing something, but isn’t that second link about LP rather than LCP? LCP doesn’t always work, it’s true, but for different reasons.

Barraff’s LCP is derived from Dantzig’s algorithm. Barraff’s LCP is virtually a linear program, and certainly is a simplex method. So those arguments are valid. However, I would treat most of the material I posted years ago with some caution as I hardly knew what I was talking about then :slight_smile:

It’s certainly closely related to LP, but doesn’t the different setup mean that looping is impossible? And whereas the first problem listed for LPs is finding an initial feasible solution, LCP terminates as soon as you find a feasible solution.

[quote]but doesn’t the different setup mean that looping is impossible?
[/quote]
Infinite looping is still possible with LCP. ODE permutes its parameters when it detects its having problems, and if it can’t solve the equations it returns an invalid solution.

[quote]LCP terminates as soon as you find a feasible solution.
[/quote]
Yeah, LCP is not maximizing a cost function.

[quote]And whereas the first problem listed for LPs is finding an initial feasible solution
[/quote]
well that is the key problem for LCP. As it is just returning a feasible solution, the LCP fails when it can’t find a feasible solution. Which can happen in real systems, but more often than not it also happens because of numerical issues.