Tool blazes virtual trails
By
Kimberly Patch,
Technology Research NewsImprovements 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 design process.
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, said Salomon.
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 added.
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, he said.
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.
Timeline: Now
Funding: Corporate, Government
TRN Categories: Human-Computer Interaction; Data Representation and Simulation
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
Advertisements:
August 13/20, 2003
Page One
Skulls gain virtual faces
Viewer explodes virtual buildings
Tool blazes virtual trails
Quantum computer keeps it simple
News briefs:
Video keys off human heat
Interference boosts biochip
Device simulates food
Motion sensor nears quantum limit
Molecule makes ring rotor
Carbon wires expand nano toolkit
News:
Research News Roundup
Research Watch blog
Features:
View from the High Ground Q&A
How It Works
RSS Feeds:
News
| Blog
| Books 
Ad links:
Buy an ad link
| Advertisements:
|
 |
Ad links: Clear History
Buy an ad link
|
TRN
Newswire and Headline Feeds for Web sites
|
© Copyright Technology Research News, LLC 2000-2006. All rights reserved.
