Tool blazes virtual trails
Technology Research News
Improvements in computer graphics hardware
and computer aided design (CAD) software over the past few years have
made it possible to render complicated models of buildings, ships and
aircraft relatively quickly.
But navigating through these models has been challenging. In most
cases users wander around like disoriented ghosts, drifting through walls
and having trouble keeping their bearings.
Researchers at the University of North Carolina have found a way
to keep users' feet on the floor. "Now that we can interact with complex
models at a high frame rate, we want to make it easier for a user to navigate
through those models," said Brian Salomon, a researcher at the University
of North Carolina. "Our goal is to allow a user sitting at a desktop PC
to navigate through a virtual environment such as a power plant as though
he or she was walking through [it]," he said.
The key to the system is an algorithm that computes a global road
map of the environment. When a user wants to navigate from one place to
another, the algorithm plots out a collision-free path.
The software can be integrated with CAD and visualization systems
to allow users to more easily navigate and explore structures during the
The researchers' software has two components -- a local navigation
mode and a global mode that computes paths through the environment. The
researchers have demonstrated the system on CAD drawings of a pair of
large environments -- a power plant and a factory room.
The approach makes no assumptions about a particular model, said
Salomon. "We didn't want to require that someone [specify] where floors,
stair cases et cetera are located," he said. "We are assuming the model
of the environment is presented to us simply as an unstructured list of
polygons." At the lowest level, graphics programs define structures as
groups of polygons.
The local component keeps track of the surface that an avatar,
or representation of the user within the model, is standing on, said Salomon.
"As the avatar moves, the local component follows a series of rules to
keep the avatar out of collision with obstacles and to transition between
walkable surfaces," he said.
To do so, the algorithm looks at the polygons that make up the
environment that the avatar comes into contact with, said Salomon. "Consider
walking up to a flight of stairs. The avatar moves until it collides with
the staircase," he said.
When the collision occurs, the program analyzes the polygons of
the environment within the neighborhood of the avatar's feet and determines
that the polygons representing the top of the first stair are a valid
floor surface, then it determines whether moving the avatar to this surface
will cause any other collisions, said Salomon.
At the same time, the global mode makes navigation easier by planning
out paths ahead of time. The system builds a graph that captures the connected
space a user can walk through -- a road map, Salomon said.
The graph contains nodes that represent places the avatar can
stand. And edges, or lines, connecting nodes represent a walkable path
between those positions. When a user requests a route between locations,
the software finds graph nodes near the start and end positions and determines
a sequence of edges that connect the two.
The graph is built in a preprocessing step that randomly finds
positions the avatar can occupy, then connects those positions. In order
to generate a graph that captures complex paths but avoids redundancy,
the algorithm determines whether each position adds valuable connectivity
information to the graph before adding it, Salomon said.
The challenges in building the system were dealing with the complexity
and scale of environments that often contain complicated structures, and
are made up of tens of millions of polygons, said Salomon.
In putting together the system the researchers developed algorithms
for fast collision detection and motion planning. They modified an existing
algorithm in order to produce non-redundant graphs. And they came up with
a set of rules for determining how the user can move through the environment,
The researchers were able to capture 88 percent of the structure
of a power plant model that contains 12 million triangles using a graph
that contained fewer than than 6,000 nodes, said Salomon. The researchers
were initially surprised by how compactly they could capture the structure
of such a complex environment, he said. It was also surprising how much
more difficult the job became to achieve coverage above 88 percent, he
The scheme requires very little model-specific information, it
can be used with very large models, the graph requires very little storage,
finding a path from one point to another is very fast, and it is easy
to approximate the coverage of the road map as it is being built and stop
sampling when the coverage is adequate, said Salomon.
Movement along a path, however is still fairly awkward. And the
preprocess step that generates the graph can take a long time. For instance,
it took more than 12 hours to process the 12-million triangle power plant
model, he said. "This... means we cannot adapt the graph quickly enough
to allow for dynamically changing environments.
The researchers are working on rendering larger and more complex
models, and on reducing the time required to process the models in order
to decrease the turnaround time between model generation and visualization,
Their ultimate aim is to make virtual prototyping easier for designers,
said Salomon. "We are working with Boeing, Newport News Shipbuilding,
and designers of large structures like the power plant," he said.
The method can be incorporated into existing visualization products
now, said Salomon.
Salomon's research colleagues were Maxim Garber, Ming C. Lin and
Dinesh Manocha. The work was presented at the Association of Computing
Machinery's Symposium on Interactive 3D Graphics (ACM ID3'03), April 27-30,
2003 in Monterey, California. The research was funded by the Army Research
Office (ARO), the National Science Foundation (NSF), the Office of Naval
Research (ONR) and Intel Corporation.
Funding: Corporate, Government
TRN Categories: Human-Computer Interaction; Data Representation
Story Type: News
Related Elements: Technical paper, "Interactive Navigation
in Complex Environments Using Path Planning," presented at the Association
of Computing Machinery's Symposium on Interactive 3D Graphics (ACM ID3'03)
and posted at www.cs.unc.edu/gamma/Navigation including video clip
August 13/20, 2003
Skulls gain virtual faces
Tool blazes virtual trails
keeps it simple
Video keys off human
Device simulates food
nears quantum limit
Molecule makes ring
expand nano toolkit
Research News Roundup
Research Watch blog
View from the High Ground Q&A
How It Works
News | Blog
Buy an ad link