The Soda Hall Walkthrough
by David Pescovitz
 Printer-friendly
version
Soda Hall
|
In the late 1980s, the Berkeley campus was gearing up to build a much-needed building
for the computer science division. Carlo Séquin, the computer science professor
heading the building committee, had already
caught many flaws in the two-dimensional
architectural floor plans. But, he thought, he
could do his job much better if he could take
a virtual walk through a three-dimensional
model of the building.
At the time, that was a tall order. A detailed
computer model of the new building, Soda
Hall, would contain millions of polygons.
State-of-the-art walk-through programs could
handle only on the order of tens of thousands
of polygons in real time-any more and the
succession of images would become jerky
and intermittent.
However, Seth Teller, a Ph.D. student working
with Séquin, realized that only a tiny fraction
of the polygons in the Soda Hall model are visible
from a given vantage point. So at any
moment in a walk-through, the rendering program
may need only about one percent of the model's
polygons. "If you can find a way
to avoid sending the other 99 percent through the
graphics pipeline, you can make models that
run 100 times faster or are 100 times more
detailed than before," he says.
To figure out what is visible from any vantage
point, Teller broke down the building's design
into cells, the rooms and corridors, and portals,
the windows, doors, and other openings
through which parts of the building can be
seen. Drawing on his background in theoretical
computer science and computational geometry,
Teller, now a professor at M.I.T., came up with an efficient algorithm to
calculate which objects are visible at any
moment in the walk-through. Previously, Teller
says, graphics algorithms decided what was
visible one polygon or even one point at a
time. "The idea here was to make decisions
about visibility on a chunk-by-chunk basis," he says.
Another challenge remained: to get the polygons
to the rendering program quickly enough
to refresh the scene 30 times every second,
which creates a fluid, realistic animation. The
Soda Hall model was too large for a computer's
memory, so the team was storing it on the
RAID disk system created by Randy Katz and
David Patterson's architecture group. But data
had to be fetched from the disk each time it
was needed. To avoid slowdowns, Tom
Funkhouser, another of Séquin's Ph.D. students,
came up with an algorithm that predicts
where a user is likely to move next, and brings
the relevant portions of the building into memory
before they become visible. Funkhouser
sped the Walkthru further by creating models
of the furniture at multiple levels of detail, and
developing an algorithm to determine the
appropriate level of detail for each item in a
frame in real time.
The final program could render detailed animations
of Soda Hall, complete with rooms,
staircases and furniture, in real time. "Seth
and Tom created a system that demonstrated
to the world how this could be done efficiently
and robustly, and this general approach has
now been widely adopted," Séquin says.
(Reprinted with permission from the Computer Science 30th Anniversary Brochure .)
Lab Notes is
published online by the Public Affairs Office of the UC Berkeley
College of Engineering. The Lab Notes mission is to illuminate groundbreaking
research underway today at the College of Engineering that will
dramatically change our lives tomorrow.
Media contact: Teresa
Moore, Lab Notes editor, Director of Public Affairs
Writer, Researcher: David
Pescovitz
Web Manager: Michele
Foley
Subscribe or send comments to the Engineering Public Affairs
Office: lab-notes@coe.berkeley.edu.
© 2004 UC Regents.
Updated 7/27/04.
|
