# 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 is the code as it was roughly around January 2008 when I was submitting the "Backwards Steps in Rigid Body Simulation" paper. It therefore has a number of bugfixes and improvements on top of the original binary MWB demo; however it doubtless has lots of new bugs and is (due to the backwards sampling support) no doubt more complicated than it needs to be.
- I will be happy to answer any questions about this software, but I warn you that my memory may be a bit fuzzy.
- I don't really have the time or energy to do any active development on this, so if anyone else is interested, have at it!
- The bulk of the code should build on multiple platforms (Mac, Windows, and Linux). In particular, the sampling engine usually ran on Linux while I was working on the paper. The main application, however, is currently Windows-only. The reason is that it relies on a number of Windows API calls related to multithreaded and network operations. These could probably be swapped out with a smallish amount of effort.

This code is broken into two parts:

- libtwigg.tar.gz. This is a collection of routines and classes that are generally useful and were shared among all the code I wrote as a grad student.
- mwb.tar.gz. This is the application that actually does the browsing.

## 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(*n ^{3}*) and this has to happen

*n*times for

*n*constraints, the total cost is actually O(

*n*)!

^{4}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(*n ^{2}*) time to generate the new
factorization. Then the total cost is only O(

*n*) (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.

^{3}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.

- Andrew Willmott's Vector library. This code uses a slight variant on the released version where I've gone through and namespaced everything; find it here.
- I used wxWidgets for all my UI code. The version I was using in 2008 was wxWidgets 2.8; it could probably be made to work on newer versions without too much effort.
- WildMagic. It looks like the version I was using was maybe version 4, but I can't remember for sure. My recollection is that this dependency is actually pretty thin (just a couple of utility functions) and so could probably be removed without too much effort; I'm pretty sure I was able to remove the dependency for the downloadable demo.
- OpenGL Extension Wrangler.
- Bullet Physics. As noted
on the webpage for the downloadable demo, this dependency is removable with
some
`#ifdef`

s (the only required physics library is ODE) - Novodex (no link). This is probably not rescuable; I did a lot of
development with an early developer's release of the library, but I don't think
NVIDIA is supporting that any
more.
`#ifdef`

it out. - OpenEXR. This dependency is removable; for some of the paper images I was dumping out super-high-res HDR images.
- CLP. I'm completely stumped why I list this as a dependency, which probably means it is removable.
- MKL. I was able to remove this for the released version using a little 3x3 symmetric Jacobi solve, so this depency is probably not really necessary any more.

## 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:

- 3x3 block sparse matrices
- axis-aligned bounding box tree
- extensions to vl
- .obj file support
- .mat file support (for exporting to Matlab)
- simplified wrappers for BLAS and LAPACK
- wrappers for the NAG libraries
- wrappers for functionality/data types in WildMagic

## 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:

- Redistributions of source code must retain the above copyright notice, this list of conditions and the following disclaimer.
- 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.