3
\$\begingroup\$

Erin Catto mentioned in a talk that solving constraints precisely requires cubic time and quadratic space. What algorithm is he talking about when he mentions cubic time?

pdf of slides with following quote:

We can model and program our constraints perfectly. Good enough to drive a robot arm on an assembly line or launch a satellite into space. Unfortunately for games, we do not have enough cycles to solve constraints accurately. Solving constraints precisely requires cubic time and quadratic space. For games we make due with linear time and space, so we are constantly wrestling with our solvers. The better you understand constraint solvers, the better chance you’ll have of creating robust simulations in your game.

\$\endgroup\$
  • \$\begingroup\$ Did you consider emailing Erin Catto to ask him? You might get a response! \$\endgroup\$ – Engineer Feb 21 at 9:12
0
+100
\$\begingroup\$

He tells you later in the slides

However, computing the global solution requires building and factoring a matrix. If there are a hundreds constraint, you will have to build and factor a 100x100 matrix. This will likely be too slow for most games.

From page 18. The method he is talking about is solving the matrix he gives a toy example of on the same page, except for a much larger number of constraints. He doesn't specify the exact algorithm used to solve the matrix, but matrix solving algorithms are relatively easy to find and have similar properties. This method requires quadratic space because for N constraints you must construct an N x N matrix but if you look into matrix solving methods you will rapidly discover that many algorithms exist with performance better than O(N^3) - the best has O (N^2.375) - however these algorithms only reach these levels of efficiency for excessively large N so for the purpose of physics models in game O(N^3) is probably a realistic estimate.

|improve this answer|||||
\$\endgroup\$
  • 1
    \$\begingroup\$ That's why games don't go for "perfect" simulation, but a "good enough" one. Box2D uses iterative solver of constraints, and if you played Garry's Mod (or probably some other Half-Life 2 based game) you might recognize the "physics iterations" slider in server settings. \$\endgroup\$ – crueltear Feb 21 at 11:36
  • \$\begingroup\$ @crueltear: Indeed, but that's all discussed in the slides linked in the Question. \$\endgroup\$ – Jack Aidley Feb 21 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.