#StackBounty: #physics #physics-engine Time complexity of solving constraints in physics engine

Bounty: 100

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.


Get this bounty!!!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.