Interval Arithmetic

Via LtU, I became interested in interval arithmetic once again. I had first looked at this alternative method while struggling with errors in numeric computations in my Virtual Taj demo. If you have never heard of interval arithmetic, I recommend reading Brian Hayes's article "A Lucid Interval" (PDF, 84KB) first published in American Scientist and an interview with Bill Walster of Sun Microsystems. Essentially, interval arithmetic lets you keep track of the margins of error in your data and provides you an estimate of the probability of the correctness of the results of your computations with this data.

The main problem is not only that interval arithmetic is at least twice as slow as ordinary computer arithmetic, but also that the margins of error keep increasing over successive computations. Of course, this margin of error is anyway there in your computations whether you use interval arithmetic or not - at least now you have your "known unknowns" - but we humans normally do not like to face it. There are other problems too, including the difficulty of division when an interval contains the number 0, the non-distributive nature of computations, the necessity to anyway deal with floating-point precision and rounding errors when the endpoints of intervals are expressed as floating-point numbers, etc.


Despite all these problems, interval arithmetic might still be our best bet in attempting to perform meaningful computations on computers. Interestingly, Knuth also expresses a similar view in TAOCP Volume II ("Seminumerical Algorithms"), but sadly does not expand much on this topic.


If you're intrigued by such things, you might also want to check out affine arithmetic and arbitrary-precision arithmetic.


(Originally posted on Advogato.)

Visual Effects in "The Chronicles of Narnia: The Lion, The Witch and The Wardrobe"

Thanks to Anirban Deb, I attended a presentation yesterday that was given by some of the guys from Rhythm and Hues India where they demonstrated how they created some of the visual effects in the recent movie "The Chronicles of Narnia: The Lion, The Witch and The Wardrobe". It was organised by ASIFA India and supported by CG Tantra, Animation 'Xpress and Women In Animation. The auditorium was full of interested people - students from the various animation training institutes in Bangalore, professionals from the animation and visual effects industry and "outsiders" (like yours truly) who were just curious about such things.

The presentation was enlightening in several ways. Some interesting tidbits included:

• The lion Aslan was entirely CG! There were around 5 million strands of hair on this model and around 15 different types of hair. The model comprised the skeleton of the lion, the key muscles on its body, the skin and the fur. Its expressions were modelled on Gregory Peck's role as Atticus Finch in the movie "To Kill a Mockingbird", since they did not know who would provide the voice for Aslan till quite some time into the production. Fortunately for them, Liam Neeson's voice was not too far off the mark for the rendered expressions.
  


• They used around 65 different types of characters in the final battle scene. They used the MASSIVE software to simulate a realistic battle scene comprising almost entirely of tens of thousands of animated characters. They used Level of Detail (LoD) to reduce the load on their render farm.
  


• Their render farm for this project comprised around 2000 machines (I do not remember if they were dual-CPU Pentium 4s or Opterons). They also have a daemon on each employee's workstation that uses the idle time on that workstation to help with the rendering jobs. They use a custom Red Hat and SuSE distribution and all their employees use Linux on their desktop. All their assets are stored on centrally available file servers that virtualise access using a custom asset locator instead of ordinary file paths (this lets them easily move around stuff when discs get full for example). All the tools in their pipeline have been created in-house. All of this allows them to add capacity to their render farm as needed without wasting a tonne of money in software licenses or being at the mercy of a vendor to implement a feature they need immediately. It also insulates them from vendor bankruptcies which is apparently common in this industry.
  


• Since rendering each frame in a shot was computationally very expensive, they used several aggressive techniques to reduce re-renders. For example, while using something like Phong shading, instead of rendering the whole frame in one go, they would separately keep the contributions of ambient, diffuse and specular (from each of the lights in the frame) and then combine these in a computationally trivial step to create the final image. This allowed their artists to tweak the colour, intensity, etc. of each light source to get the perfect look without having to submit a new job to the render farm.
  


• Blend shapes are simple to use, but inaccurate, means to show character movement and expressions. Muscle deformations are more complex to use but volumetrically accurate. These guys created a tool that interpreted blend shapes to derive the corresponding muscle deformations to get the best of both worlds.
  


• Normally PCs use 8-bits of intensity levels per Red, Green and Blue component to illuminate a pixel. Apparently this is not sufficient and produces banding effects due to loss of precision over several calculations. They were therefore using a 16-bit logarithmic intensity level per component for all intermediate calculations.
  


• If one is to believe the presenters, apparently the visual effects guys are pretty low in the pecking order in a movie production. Something as simple as telling the director to not use bright green as the key colour when the background itself is green sunlit grass was beyond them.
  


• I didn't understand it fully, but they apparently made a monetary loss on this project. It is also apparently a very low margin, high effort business requiring extremely talented artists.
  

It is also heartening to know that Blender 3D is getting better and better, especially for character animation, and we can actually do some of this stuff at home. Synfig, a 2D vector animation tool, also became Free recently though I do not know how good it is.

(Originally posted on Advogato.)

What Was Your First Computer?

Seen on Slashdot: "What Was Your First Computer?"

The first computer I worked on was the SCL Unicorn which was a clone of the BBC Micro Model B. This was a microcomputer based on the 6502 microprocessor and came with the OS and an interpreter for BASIC on ROM and 32KB of RAM.

(Originally posted on Advogato.)

IITs All About

Someone has uploaded CBS's "60 Minutes" feature on the IITs to Google Video (thanks to Arpana for pointing me to this). There is a lot of truth accompanied by the usual hyperbole in this video with unfortunately some of the interviewed students also playing along. For instance, not everyone likes to stay up all night preparing for examinations, that too accompanied by a doting tea-making mother. Certainly not everyone has their entire family dropping them off at the examination centre and has them hanging around for the entire duration of the examination. "Puh-sycho!" It is also too much of a stretch to put the IITs above MIT, Princeton, CMU, etc. - they are each good and bad in their own ways.


For the IIT Kanpur junta, someone else has also uploaded the musical production targetted at nostalgic alumni "Din Bhar" to Google Video. You must see this at least once.


(Originally posted on Advogato.)

C99

In a personal project, I have been using some of the niftier and simpler C99 features like //-style comments, mixed variable declarations and statements, the bool type with its true and false pre-defined values and the uint16_t, int32_t, etc. integral types from stdint.h. They resolve some of the minor irritants I used to face when I am forced to code in C89. I plan to use these features from C99 in all my personal projects written in C.

Unfortunately, compiler vendors do not seem too eager to support all the features in C99 even after a better part of a decade after the standard was released! Microsoft is surely not in a hurry to support C99 and GCC and glibc are still not completely there yet. A sad state of affairs. Either the standards committee was eager to get new features into C without a buy-in from the compiler vendors or the C coders have been a little underwhelmed with these features and hence have not been pushing for support for them in their compilers.

(Originally posted on Advogato.)

QEMU on steroids

First there was QEMU that provided a fairly fast emulation of x86 hardware using a technique called "dynamic translation". Then came kqemu (or QEMU Accelerator Module) that allowed user code (ring 3) to run directly on the actual hardware providing speedups of around 3-5 times. Now comes the -kernel-kqemu option that allows even some of kernel code (ring 0) to run directly on the actual hardware providing impressive speedups over the old kqemu. Of course, these speedups come at the cost of affecting the stability of the host OS because of bugs in kqemu. kqemu is also not Free software, though it is free (gratis) for non-commercial uses.

In other news, GCC's SVN repository is also available for read-only access via HTTP for those who are stuck behind corporate firewalls and want access to the latest sources without having to download weekly snapshots. Of course, this is slower than the SVN protocol and might also be pulled off if it contributes too much to the load on the server.


(Originally posted on Advogato.)

"A look at GCJ 4.1"

Mark Wielaard has written another article for LWN.net titled "A look at GCJ 4.1" (where he also looks at GCJ 4.2 and beyond). It is subscribers-only for the moment (for a week), but if you are interested in Linux in any way, you should seriously consider subscribing to LWN. It's quite good.

(Originally posted on Advogato.)