Many-Worlds Browsing Code

I am making the many-worlds browsing source code publically available. The license is BSD, feel free to use it however you like, and please let me know if you find it useful. A few general caveats:

This code is broken into two parts:

Modified LCP solver for ODE

During the course of this project, I played around with a number of different rigid simulators. In those days, bullet was in its infancy and had less-than-perfect joint support, and Novodex seemed to have problems generating realistic collisions (which would have made the paper a tough sell, since it was predicated on the fact that people are relatively insensitive to small errors during collision handling). I ended up settling on ODE, which was at that point already quite mature and stable (and was being used in at least one commercial product, Softimage). However, I found that ODE's native pivoting LCP solver produced very good results but was terrifically slow, and the alternative solver (based on projected Gauss-Seidel) didn't seem to converge quickly enough.

To help improve the speed of sampling, therefore, I decided to put some effort into speeding up ODE's pivoting solver. A big part of the cost is due to the fact that ODE refactors the system matrix every time it adds or removes a row. Since factoring a matrix is O(n3) and this has to happen n times for n constraints, the total cost is actually O(n4)!

Traditionally, when you implement a pivoting LP solver, this is ameliorated somewhat by using incremental updates to the factorization: each time you add a row, you perform some operation that takes at most O(n2) time to generate the new factorization. Then the total cost is only O(n3) (roughly, of course; the simplex method technically has worst case exponential performance). Baraff took advantage of these fast matrix updates because he had access to a copy of LUSOL, which now appears to be publically available but (at least as far as I could tell) wasn't at the time of submission of the original MWB work.

Updating LU factorizations is notoriously difficult due to pivoting (even very well-conditioned matrices cannot be factorized using LU without pivoting). To get this up and running quickly, I needed to build something stable out of existing tools. I therefore chose to use and update a QR factorization. Updates to QR decompositions are much simpler than updates to LU decompositions; you get a "spike" below the diagonal and just need to eliminate it. See my thesis for details.

An updated version of ODE's LCP solver that uses QR updates can be found here.

Required libraries

Since the project was frozen in 2008, a lot of these library dependencies are pretty ancient. If you get it working with more modern versions of everything, let me know and I'll put the updated version here, or maybe just move the whole mess into github.

Stuff in libtwigg

Some of libtwigg is just code poached from elsewhere (all of it either BSD-licensed or public domain, I hope; if not let me know and I'll remove it).. Some of it might be useful to other people. Here's a partial list:

License

Copyright 2002-2008 Christopher D. Twigg. All rights reserved.

Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:

  1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
  2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following disclaimer in the documentation and/or other materials provided with the distribution.

THIS SOFTWARE IS PROVIDED BY CHRISTOPHER D. TWIGG "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL CHRISTOPHER D. TWIGG OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

The views and conclusions contained in the software and documentation are those of the authors and should not be interpreted as representing official policies, either expressed or implied, of Carnegie Mellon University or Cornell University.