Orion Lawlor's PhD Thesis: Impostors for Parallel Interactive Computer Graphics

This page describes my parallel programming and computer graphics work on impostors, which are 2D texture standins for real 3D geometry. Impostors provide a substantial amount of latency tolerance and rendering speedup, which can be used to render huge and detailed models--like a model of the entire UIUC campus--with quality antialiased rendering techniques, including soft shadows.

The best places to learn more about these techniques are:

• My thesis defense slides give a good overall tour: PPT PDF 6-up PDF (6MB, 94 slides, Updated 11/29)
• The broad benefits can be seen in the Example Movies.
• The nitty gritty details are in my PhD Dissertation (6.5MB PDF, Updated 12/23)

I gave my final defense on 2:00PM Monday, November 29, 2004 in 4407 Siebel. Defense Version of Dissertation (5.5MB, Updated 11/23)

Committee:

• Sanjay Kale: Parallel Prioritization, Load Balancing
• Mike Heath: Parallel Algorithms, Numerical Analysis
• John Hart: Procedural Computer Graphics, Graphics Hardware
• Mike Garland: Model Simplification, Texture Synthesis

Selected Self Citations

• Kale et al 1993 Prioritization Describes problems with and results in prioritized parallel computations.
• Lawlor and Kale 2002 Arrays Parallel migratable object array manager.
• Lawlor and Hart 2003 IFS Bounding My only computer graphics paper, on bounding iterated function systems like trees.
• Jyothi and Lawlor 2004 Parallel Debugger Contains a good description of and motivation for PUP and CCS.

Selected Prior Work

• Chen 1993 Viewpoint Interpolation. Nice exploration of the ways to morph and blend textures to interpolate between two viewpoints. Sadly, viewpoint interpolation is difficult to perform quickly, and hole-filling turns out to be a significant problem with this approach. See Mark 1999 warping thesis for more modern work on the same reconstruction problem.
• Maciel 1995 Imposters First paper to name "imposters"; idea is to replace geometry by images. Their usage of imposters was quite simple--they pasted fixed images onto the object bounding box.
• Shade 1996 Heirarchical Walkthrough. Replace a subtree of the scene graph with an imposter, for quickly rendering outdoor scenes.
• Schaufler 1996 Image Caching. Replace individual objects with imposters.
• Ward 1999 Ray Cache. Trace a random set of high-quality rays on a parallel machine, and reconstruct an image from the current subset of rays. Not imposters, but parallel, realtime, and prioritized; the only downside is that reconstructing an image from random rays is difficult, and the results are speckly.
• Pasman 2001 Low-latency. Remote rendering system which makes the explicit argument of imposters for latency tolerance.
• Harris 2002 Realtime Clouds. Imposter-based lovely cloud rendering.
• Humpreys 2002 Chromium (WireGL). Parallel rendering system based on OpenGL pipeline (Documentation).

Prelim Report

Prelim Report, final revision (PDF 7.3MB).

Prelim Presentation (PowerPoint, 5.4MB) (PDF 3.4MB) (4-up PDF 1.0MB)

The prelim was held 4:00pm Monday, April 12, 2004.

ChangeLog

(Updated Wednesday, December 21 2005: Finally added movies.)

(... many updates in preparation for defense...)

(Updated 4pm Sunday, November 7: Added final defense schedule.)

(Updated 4pm Sunday, April 11: Final version of slides.)

(Updated 3am Sunday, April 11: Added slides.)

(Updated 6pm Thursday, April 1: Final version.)

(Updated 11pm Wednesday, March 31: Incorporate suggestions from Kale and Sayantan.)

(Updated 2am Wednesday, March 31: Example images from penumbra limit maps, upload self-citation papers.)

(Updated 4pm Saturday, March 27: More graphics references.)

(Updated 2am Saturday, March 27: Incorporate Kale e-mail edits, a few final additions.)

(Updated 2am Thursday, March 25: Incorporate Kale edits, rework most sections.)

(Updated 2pm Wednesday, March 24: Better fundamentals section, more rendering details.)