Academic Facets: News and Views from Spatial's University Community

[#1]

One aspect of academic life that is both a blessing and a curse is the endless stream of requests to review papers for journals and conferences. It’s a curse because they are frequently on less than riveting topics and can take days to read (or decode)! However the upside is that often you learn something new and sometime you get a sense of emerging trends when three, or four, papers pass by (from quite different sources) all with a common theme.

So something I have noticed recently is the increasing use of General Purpose GPU (GPGPU) programming in Geometric Reasoning applications. In fact some of the results of using Graphics Hardware to compute geometric properties are so impressive I’m being to wonder if its going to be a “disruptive technology” for computational geometry, by making “brute-force” fashionable!

Wikipedia’s page on the GPGPU sums-up the general approach (in a very few words):

“Most operations on the GPU operate in a vectorized fashion: a single operation can be performed on up to four values at once. For instance, if one color <R1, G1, B1> is to be modulated by another color <R2, G2, B2>, the GPU can produce the resulting color <R1*R2, G1*G2, B1*B2> in a single operation. This functionality is useful in graphics because almost every basic data type is a vector (either 2, 3, or 4 dimensional).”

So by doing things like pretending colors values are (x,y,z) coordinates and rendering to multiple off-screen images researchers have devised cunning schemes for applications like “geometric pattern matching”, “Interactive Collision Detection Between Complex Models” through to “Fast 3D Distance Field Computation” (see www.gpgpu.org). All these are hard problems when crunched with traditional hardware, but by cunningly redesigning the algorithms (so they can exploit the GPU hardware) real time solutions become possible.

Although this sort of thing has been going on for a few years now, the level of academic take-up appears to be increasing. Perhaps a combination of the increasing flexibility of each new generation of GPU APIs and people’s skill at exploiting them has passed some sort of tipping point?

In the last few weeks I have seen impressive real time “tool access” calculations and collision detection between complex shapes. So I would guess that innovative approaches to problems of programming, say, multi-axes machine tools and 5-axis CMM inspection heads will soon exploit this cheap hardware.

While I don’t think this sort of technology will replace the need for the precise calculations that ACIS and other B-reps can produce (the results are only as good and fast as the number of pixels employed), I think that one day GPU hardware will be used to speed-up many modelling tasks. So operations like Booleans might use a GPGPU routine to quickly calculate the approximate locations of intersection curves as a precursor to the “standard” analytical computation.

In the big picture I think there is the exciting prospect that, in the next few years, researchers will be revisiting many of the "classic" geometric reasoning problems armed with GPGPUs and a new mindset!

I am always impressed when people are able to solve problems with technology design for something else. And I especially enjoy it when the economies of scale that allow amazingly sophisticated hardware developed for games (and sold at consumer prices) allow unforeseen applications.

The GPU is one example and another great (but only slightly geometric) example of this to have crossed my screen recently is the cult of Wii hacking, where lateral thinking has allowed the creation of applications like interactive white boards and head tracking for a fraction of the normal price. By using the infrared camera in the Wii remote and putting the sensor bar (two IR LEDs) on your head a researcher (at CMU I think) has been able to accurately track the location of a viewer and render view dependent images on the screen. The result a very strong 3D effect for a fraction of the normal VR costs, see:

http://www.youtube.com/watch?v=Jd3-eiid-Uw
http://www.youtube.com/watch?v=0awjPUkBXOU
http://www.youtube.com/watch?v=5s5EvhHy7eQ