Jumpin Donuts

Here's another test of the softbody solver I'm currently filling my spare time writing. This example has roughly 23000 vertices and runs at approx. 1-2 mins per frame. Pardon the ugly OpenGL representation -  geometry output to a proper renderer is on the backburner as I'm still optimizing a few things in the collision loop.

Another softbody solver test

Here's another Maya playblast of the softbody solver I'm working on in my spare time. The main limitation visible here is the fact that the level set collision algorithm, which I'm using for all static objects in this simulation, only handles particles, not edges or triangles. This means the softbodies will snag  wherever the static objects get thin enough to enter the spaces between the particles. The immediate workaround, which in the past I've successfully employed with the hair solver which this is a generalization of, is to enable mesh-based collisions for thin non-deforming objects. However, this means losing the very advantageous efficiency and robustness of level set based collisions. More results to come...

Softbody solver: first test

This is an early test render from my slow-moving pet project, a softbody dynamics solver for Maya. It's based on the core technology from the hair solver I wrote for "Tron Legacy", with added support for conversion of arbitrary poly surfaces into tet meshes using TetGen.

I'm still working on extracting the resulting surface so that I can plug it into a proper renderer. Meanwhile, please enjoy the OpenGL framegrab above. It shows a tetrahedralized poly sphere which is affected by gravity and a couple of kinematic poly meshes which are represented as level sets internally (for faster and more robust collision lookups).

Due to the large amount of proprietary Digital Domain libraries involved in the solver, this is strictly an in-house project which will most likely never see the outside of DD's facilities. Hopefully I'll be able to use this to generate some interesting animation down the road though, even if it's just to satisfy my own curiousness.

The following credits are due:

• R. Bridson, R. Fedkiw and J. Anderson, for  "Robust treatment of collisions, contact and friction for cloth animation" [pdf]
• A. Selle, J. Su, G. Irving, and R. Fedkiw, for "Robust High-Resolution Cloth Using Parallelism, History-Based Collisions and Accurate Friction" [pdf]
• H. Si,  for TetGen
• K. Museth, for DBGrid (a dynamic blocked grid for sparse high-resolution volumes and level sets)
• D. Roble and rest of Digital Domain's software department, for DDMath and other proprietary libraries.

Maya 2012 idle event issue

This might be old news to some but I just discovered another baffling "feature" of Maya 2012. Try this in the Python editor of a Maya session you can do without:

import maya.utils
def foo():
  print 'here'
  maya.utils.processIdleEvents()
maya.utils.executeDeferred( 'foo()' )

Boom! Infinite recursion, stack blows up, segfault, good night.

So what's going on here? Well, it seems that somehow processIdleEvents() doesn't actually pop the event queue until after it's processed an event. Call me old fashioned but isn't that kinda backwards? Wouldn't you pop the queue right after you acquire the event, just to prevent issues like this?

The reason I came across this in the first place is we had a case of someone launching a Python script from MEL using evalDeferred, in order to avoid these massive UI deadlocks that would regularly happen due to some unfortunate combination of Maya 2009, Linux, pyQt and context menus. Now, deep down in one of our Python modules someone else had added a call to processIdleEvents() in order to guarantee that a loadPlugin() call has completed before proceeding - most probably due to some other synchronization issue in the Maya Python engine. You can guess what happened next, to everyone's stunned amazement: the script simply restarted, without any clue whatsoever why that might be.

The way I was able to catch this was by using 'traceback' to print out the call stack at a certain place in a module that I happened to have control over, realizing where the jump was happening. The solution? I'm not quite sure yet but it seems as though the UI deadlocks that gave rise to the use of evalDeferred in the first place have been mitigated post Maya 2009, so hopefully by just using a straight-up python() call instead we can put this behind us. However, this somewhat unorthodox treatment of idle events seems as something that should at least be mentioned in the API docs, if not fixed, period.

Or did I get any or all of this backwards? Please leave a comment if you have any thoughts on the matter!

Python list comprehension

I've written about Python list magic in the past and here's another tip:

Say you wanna create a list based on some other list, possibly filtering out certain entries and/or modifying the ones you choose to include.

Rather than this:

result = []
for item in mylist:
  if item > 5:
    result.append( '%05d'%item )

give this a go next time:

result = [ '%05d'%item for item in mylist if item>5 ]

Pretty neat, huh? Obviously this works on all valid sources of list data:

print 'Modules with \'site\' in the name:\n%s'%'\n'.join( \
      ['%s : %s'%(name,module) for name,module in \
        sys.modules.iteritems() if  'site' in name] )

Once we know this pattern it's fairly straightforward to create nested versions thereof, like this one straight out of a Maya script:

for attr in \
    [ '%s%s'%(attr,dim) for attr in ['t','r','s'] \ 
                         for dim in ['x','y','z'] ]:
  maya.cmds.connectAttr('%s.%s'%(sourceNode,attr), \
                        '%s.%s'%(targetNode,attr), f=True)

which combines two lists into one sequence of Maya attributes ['tx','ty','tz','rx','ry'... ] to connect between two nodes.

Expressive and neat, just the way I like it.

Google Test

As usual Google gets the behind-the-scenes stuff just right with their "C++ Testing Framework":

http://code.google.com/p/googletest/

For the simplest possible usage example, just include gtest/gtest.h and add this to your application entry point:

::testing::InitGoogleTest(&argc, argv);
int ret = RUN_ALL_TESTS();

Now, each test you wanna add is declared like so:

TEST(TestCase,TestName)
{
   // test goes here
}

The framework provides a bunch of macros for value tests and assertions, a very simple example being:

ASSERT_EQ( 1, someValue );

where the test fails and spits out an instructive error message in case someValue != 1.

I've found this framework to be extremely simple to learn, but once you scratch the surface you'll find it also has quite a few advanced features such as listeners, reflection, type-parametrized testing etc. to keep you busy for quite some time.

Eigen - versatile, fast, reliable linear algebra library for C++

After years of trudging along with all manners of legacy libraries for vector math, both homegrown and 3rd party, I finally got turned on to Eigen by a coworker. Unfortunately I can't provide any first impressions of it yet - I've been too giddy over all the cool features (vectorization! loop unrolling! lazy evaluation! elegance! it's free!) to actually be able to sit down and try it out. Instead, I present you with the product overview verbatim from their website:

• Eigen is versatile.
  • It supports all matrix sizes, from small fixed-size matrices to arbitrarily large dense matrices, and even sparse matrices.
  • It supports all standard numeric types, including std::complex, integers, and is easily extensible to custom numeric types.
  • It supports various matrix decompositions and geometry features.
  • Its ecosystem of unsupported modules provides many specialized features such as non-linear optimization, matrix functions, a polynomial solver, FFT, and much more.
• Eigen is fast.
  • Expression templates allow to intelligently remove temporaries and enable lazy evaluation, when that is appropriate.
  • Explicit vectorization is performed for SSE 2/3/4, ARM NEON, and AltiVec instruction sets, with graceful fallback to non-vectorized code.
  • Fixed-size matrices are fully optimized: dynamic memory allocation is avoided, and the loops are unrolled when that makes sense.
  • For large matrices, special attention is paid to cache-friendliness.
• Eigen is reliable.
  • Algorithms are carefully selected for reliability. Reliability trade-offs are clearly documented and extremely safe decompositions are available.
  • Eigen is thoroughly tested through its own test suite (over 500 executables), the standard BLAS test suite, and parts of the LAPACK test suite.
• Eigen is elegant.
  • The API is extremely clean and expressive while feeling natural to C++ programmers, thanks to expression templates.
  • Implementing an algorithm on top of Eigen feels like just copying pseudocode.
• Eigen has good compiler support as we run our test suite against many compilers to guarantee reliability and work around any compiler bugs. Eigen also is standard C++98 and maintains very reasonable compilation times.

Off-screen OpenGL drawing without a graphics card using Mesa 7.6.1 on CentOS 5

So let's say you wanna rasterize a couple of polygons using OpenGL, but don't have access to a graphics card. Maybe yours broke - or maybe you're on a 6000 node render farm without a single GPU in sight. Either way you're just plain out of luck when it comes using regular OpenGL.

The Mesa 3D Graphics Library could save your day! It's been around since the dawn of time, was started by this guy named Brian Paul and as the website states:

"Mesa is an open-source implementation of the OpenGL specification - a system for rendering interactive 3D graphics.

A variety of device drivers allows Mesa to be used in many different environments ranging from software emulation to complete hardware acceleration for modern GPUs.

Mesa ties into several other open-source projects: the Direct Rendering Infrastructure and X.org to provide OpenGL support to users of X on Linux, FreeBSD and other operating systems."

Ok, but of what use is it to you? It turns out that among many other nifty things Mesa includes an off-screen rendering engine which allows you to render into any buffer, rather than the framebuffer on your non-existent graphics card. It's in other words a software version of OpenGL so not nearly as fast as your average graphics board, but hey, it's exactly that kind of hardware independence that we're after in the first place, right?


Installation

Being on CentOS, we're as usual at a rather tiresome disadvantage due to the pletora of ancient - albeit very stable - drivers in the distro, many of which you may not want (or more likely, be allowed) to fully replace, so throughout this installation guide I'll make frequent of use of the --prefix argument to "configure" in order to redirect my installations and builds to some local directory rather than the restricted /usr area.

Let's get started! First of all, CentOS 5 ships with a rather old x-org server which means the latest Mesa versions don't seem to want to build with it. Instead we'll settle for version 7.6.1, which seemingly has all the off-screen capabilities we'd like, while still working with CentOS 5. (as always, don't take my word for it though - try for yourself!). Grab it here:

ftp://ftp.freedesktop.org/pub/mesa/7.6.1/MesaLib-7.6.1.tar.bz2 (md5: 7db4617e9e10ad3aca1b64339fd71b7d)

However, before we can build Mesa we need a couple of prerequisites:

libpthread-stubs

According to Linux From Scratch,

The libpthread-stubs package provides weak aliases for pthread functions not provided in libc or otherwise available by default. This is useful for libraries that rely on pthread stubs to use pthreads optionally. On Linux, all necessary pthread functions are available, so this package is simply a placeholder.

Just download, untar, and:

> ./configure --prefix=/home/username/local

> ./make 

> ./make install

Make sure to change "/home/username/local" to wherever you want to install your Mesa setup, or ignore the prefix switch altogether AT YOUR OWN PERIL, as this will permanently change your machine configuration and likely affect other users as well.

libdrm

Again according to Linux From Scratch,

"libdrm provides core library routines for the X Window System to directly interface with video hardware using the Linux kernel's Direct Rendering Modules."

Unfortunately we can't just grab the latest version from http://www.linuxfromscratch.org/blfs/view/cvs/general/libdrm.html due to a conflict with the Nouveau driver (http://bugs.gentoo.org/324539), so instead let's grab 2.4.20 from here:

http://dri.freedesktop.org/libdrm/libdrm-2.4.20.tar.bz2 (md5: 3c56e03172b236e14905ef9a68ba2f97)

Again, download and untar, but this time:

> env PKG_CONFIG_PATH=/home/username/local/lib/pkconfig./configure --prefix=/home/username/local

> ./make 

> ./make install

Same thing again with the prefix path, but with the addition of PKG_CONFIG_PATH in order to tell autoconf where our new, custom package config resides.

Now repeat this with dri2proto-2.1 and glproto-1.4.11 as well:

http://xorg.freedesktop.org/archive/individual/proto/dri2proto-2.1.tar.bz2 (md5 5cb7987d29db068153bdc8f23c767c43)

http://xorg.freedesktop.org/archive/individual/proto/glproto-1.4.11.tar.bz2 (md5  78e7c4dc7dcb74b1869fee7897e00f59)

That should do it! Now let's build and install Mesa. However, the autoconfigure options aren't super clear and may not give us all the options we need, so instead let's do an old-school build:

> make realclean

> make linux-x86-64

This is for my specific 64-bit Intel rig - go ahead and try other options which may suit you better. You can get a listing of available ones by simply typing 'make'.

After the build has succeeded, but before we can install Mesa, we'll need to tweak the install path manually as we're not using autoconf. Open configs/default and set INSTALL_DIR to match the path used above:

INSTALL_DIR = /home/username/local

Save and close, and now you can:

> make install

Alright, that should do it! Let's try it out...


Usage

If you pull down the "Mesa Demos" tarball from:

ftp://ftp.freedesktop.org/pub/mesa/7.6.1/MesaDemos-7.6.1.tar.bz2 (md5 a4226f06732a02556fcf6be290b86dff)

you'll find a very simple and instructive demo program in progs/osdemos. To try it out, simply:

> env LD_LIBRARY_PATH=/home/username/local/lib64:{LD_LIBRARY_PATH} make

> env LD_LIBRARY_PATH=/home/username/local/lib64:{LD_LIBRARY_PATH} ./osdemo test.tga

There are obviously many other ways to infuse the newly installed directory into your LD library path. Eventually you'll also want to point your compiler at the new include path at /home/username/local/include.

Once you've successfully run the demo program, load up "test.tga" in your image viewer of choice and behold a couple of really awesome colorful primitives:

100% rendered in software (this particular one is from an 8-core Intel Xeon blade server located somewhere in the American midwest).

New website, new blog template, same old Mattias

Three posts in a day, and that's no joke! Anyway, while I have my typing gloves on I thought I'd plug my new website:

http://www.mattiasbergbom.com

and also take a moment to join the blogosphere in spontaneous cheering over the new css theme that I found in Blogspot's crypts. I figured since I didn't check since late 2007 there just had to be something new there, and blimey if I wasn't right.

In the process of transmogrifying my blog I realized I've collected a handful of comments over the years which I never saw and thus never responded to, but I'm full of faith that the posters didn't take my silence as some kind of gesture of hubris (now that I have a job and all), but rather a sign of increasing age and deteriorating cognitive ability. Sorry guys!

I'll leave you with that. Now go hike my visitor count please.

ps uT and other Linux memory goodness

The nerdery continues...

Ever wondered how much resident memory this one app consumes that you just launched from your shell?

> ps uT

and check the 'RSS' column.

Ever wondered how much physical memory you *actually* have access to?

> free -m

Ever wondered how much disk space you have available?

> df

TGIF.

Python slice notation

Addressing subsets of a list is easy a hell in Python. Dig this:

Assuming we have a list a=[some items],

a[:]
gives you the entire list. Ok, the benefit of that one maybe wasn't too obvious. Bear with me though!

a[x:y]
gives you items x to y (excluding 'y')

a[x:]
gives you items from x to the end of the list

a[:y]
gives you items from the beginning of the list to (but again excluding) y

So far so good. Let's step it up a notch:

a[x:y:z]
gives you items x to y, hitting only every z item (this is called 'stride')

a[x::z]
gives you items x to the end, with stride z

a[:y:z]
you guessed it: this gives you items from the beginning to y, with stride z

Ok. That about covers it, right? Not quite...

a[-x]
gives you x:th to last item, e.g. a[-1] gives you the last item, a[-2] the second to last and so on.

a[-x:-y]
gives you x:th to last to y:th to last items, so e.g. a[-5:-2] gives you the fifth item to the end to the second item to the end.

Now you probably go: what about a[-2:-5]? That just returns []! That's because not providing a stride means you're implicitly using a stride of +1, which in this case is equal to saying "take two steps back, then walk straight forward one step at a time until you're five steps behind where you started". Now, assuming you walk *straight* forward and don't follow the curvature of the earth, that's one hopeless journey, one which Python fortunately saves you from by just returning [].

Instead try this:

a[-x:-y:-z] 

which much as you'd expect returns the elements a[-x] to a[-y] in reverse order with stride z.

This obviously also means that a[::-1]  gives you the entire list, reversed.

Much like a[::2]  gives you every other item in the list, and a[::-2] gives you every other item in the list, in reverse order.

I may be preaching to the choir here but the ability to leverage Matlab-like short-hand like this inside a modern, object oriented, modular language is one of the things that make Python such an invaluable tool during prototyping and rapid application development, especially in a such a crazy environment as a Hollywood movie production.

Finally, if you agree that the above seems pretty friggin convenient, consider this: 3**9

Getting CUDA up and running on RedHat EE (CentOS)

Let's get right into it! Start by grabbing the latest CUDA toolkit (3.2.16 at the time of writing) from:


http://developer.nvidia.com/object/cuda_3_2_downloads.html#Linux

under "CUDA Toolkit for RedHat Enterprise Linux 5.5" (make sure to pick the architecture that matches your machine!)

Also grab the latest SDK, labeled "GPU Computing SDK code samples".

Now, open a shell and cd into your Downloads directory, and run the CUDA toolkit installation like so:

> chmod u+x cudatoolkit_3.2.16_linux_64_rhel5.5.run

> ./cudatoolkit_3.2.16_linux_64_rhel5.5.run

Make sure to specify an installation directory that makes sense, either the default or e.g. "~/local" if you're doing a test install.

Same goes for the SDK:

> chmod u+x gpucomputingsdk_3.2.16_linux.run

> ./gpucomputingsdk_3.2.16_linux.run

Again, specify where to put the SDK stuff. I thought ~/local/cuda/sdk was nice but it may have its drawbacks as you update your CUDA toolkit but want to keep your SDK the same.  Also make sure to point the SDK installer to the directory just specified for the CUDA toolkit installation (e.g. /usr/local/cuda or ~/local/cuda) when prompted.

Now, the first thing you want to build is "deviceQuery", which will tell you if your device driver matches your toolkit. It's really important that these two match, as most of the simple "hello world" stuff will otherwise just quietly not execute any of the code on the device, only the host code! So, starting from your SDK root installation directory, e.g. ~/local/cuda/sdk

> cd shared

> make

This builds a shared library needed by most of the SDK tools. Next,

> cd ../C/src/deviceQuery

> make

Now deviceQuery should be ready to use.

> cd ../../bin/linux/release

> ./deviceQuery

If your driver is up to date this should output something like:

CUDA Device Query (Runtime API) version (CUDART static linking)

There is 1 device supporting CUDA

Device 0: "Quadro FX 3800"
  CUDA Driver Version:                           3.20
  CUDA Runtime Version:                          3.20
  CUDA Capability Major/Minor version number:    1.3
  Total amount of global memory:                 1073020928 bytes
  Multiprocessors x Cores/MP = Cores:            24 (MP) x 8 (Cores/MP) = 192 (Cores)
  Total amount of constant memory:               65536 bytes
  Total amount of shared memory per block:       16384 bytes
  Total number of registers available per block: 16384
  Warp size:                                     32
  Maximum number of threads per block:           512
  Maximum sizes of each dimension of a block:    512 x 512 x 64
  Maximum sizes of each dimension of a grid:     65535 x 65535 x 1
  Maximum memory pitch:                          2147483647 bytes
  Texture alignment:                             256 bytes
  Clock rate:                                    1.20 GHz
  Concurrent copy and execution:                 Yes
  Run time limit on kernels:                     Yes
  Integrated:                                    No
  Support host page-locked memory mapping:       Yes
  Compute mode:                                  Default (multiple host threads can use this device simultaneously)
  Concurrent kernel execution:                   No
  Device has ECC support enabled:                No
  Device is using TCC driver mode:               No

deviceQuery, CUDA Driver = CUDART, CUDA Driver Version = 3.20, CUDA Runtime Version = 3.20, NumDevs = 1, Device = Quadro FX 3800


PASSED

Press to Quit...
-----------------------------------------------------------

Otherwise you may have to install an updated device driver. These can be found at:

http://www.nvidia.com/Download/index.aspx

NB! You need root permissions to install updated drivers, and if you're not comfortable dealing with things that may potentially break your X graphics settings you may want to consult a systems expert.

That being said, the installer asks very few questions and generally seems very good-behaved. You will however need to kill your X windows first of all, which will obviously close this browser window along with every other piece of X interface!


Closing X can be done in a myriad ways,  one of which is:

> init 3

Once you're in the shell, cd to your Downloads directory and (as usual):

> chmod u+x NVIDIA-Linux-x86_64-260.19.44.run

> sudo ./NVIDIA-Linux-x86_64-260.19.44.run

Once your device upgrade has finished, start x again:

> startx

and you should now be able to build and run CUDA SDK samples as well as tutorials such as these:

http://llpanorama.wordpress.com/2008/05/21/my-first-cuda-program/
http://llpanorama.wordpress.com/2008/06/11/threads-and-blocks-and-grids-oh-my/

(note that the latter requires you to build 'cutil' which can be found in sdk/C/common)

Good luck!