Jump to content
  • Advertisement
Sign in to follow this  
Black-Panther

Antagonism in David Eberly's "Game Physics"

This topic is 3815 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all! First I've to apologize for my bad English, but I hope you'll understand want I intend to say ;) I read "Game Phyisics" and now I'm currently trying to implement such a physics engine (surely there are some differences to the implementation of the book once! But the main concept is the same). Unconstraint motion works fine, but now I'm about to implement the collision detection and response-system. The response is based on a non-penetration-collision-detection-system with collision prediction! Method: separeting axis. Yet only convex bodies are supported! Ok, now in the book there is used a function called Minimize to solve for all contactpoints simultanously (not resting-contact). The target is, to minimize a quadratic function: "The minimize function is solving for |Af + b|^2, under the constraints f >= 0, Af + b >= 0, and Af + b <= c. Vector b has ith component b = 0 if dneg >= 0 and b = 2*dneg if dneg < 0. Vector c has ith component c = |dneg|" On one page (chapter 5) there is written, that this problem can be solved using the Lemke-Howson algorithm, thus transforming it into a LCP! But in chapter 7, treating LCPs (and MP in general), there is written, that this problem CAN'T be transformed to an LCP, because the resulting matrix isn't symetric and positive semidefinite, and because there would be no complementary condition. Now I'm quite confused about that. Without this function "Minimize" the collision-response won't work. I hope someone can help me! Thanks! Black-Panther

Share this post


Link to post
Share on other sites
Advertisement
The LCP solver on the acceleration level like e.g. described by Eberly and Baraff suffers from a lot of problems. Especially the direct solvers like Dantzig or Lemke have problems with the over-constrained system typically found in games.

Do yourself a favor and implement an iterative solver like Projected Gauss-Seidel (PGS) or Sequential Impulses (SI). If you understand the stuff described in Dave's book you clearly shouldn't have any problems understanding the iterative approach on the velocity level.

We just created a reference sticky post in this forum where you might look for reference material. Personally my favorite is Box2D by Erin Catto. If you understand every aspect of this engine you will not have any problems with physic or at least have enough solutions to work around potential problems. Another wonderful example is JigLib by Danny Chapman (MrRowl). This is a very clean and well structured physic library that also implements the SI solver of Erin Catto.

Share this post


Link to post
Share on other sites
First, visit my web site for corrections to "Game Physics". The statements you mention are indeed contradictory, and I mention this at my site (with a correction).

Second, the biggest mistake I made with "Game Physics" was to decide to present the Lemke-Howson algorithm as a way of solving the LCP. I chose this because I thought that its similarity to linear system solving and linear programming would make it easier for readers to understand the concepts. However, this algorithm is not what folks use in commercial software. The L-H algorithm does not save any state information. Better to use iterative (and faster) algorithms that start from the last state of the system.

Once I finish my current game project, I'll be working on the second edition of the book and include practical algorithms rather than trying to be pedagogic and academic...

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!