This is to a large extent a branch of graphics, with the focus on generation of
real-time three-dimensional views of dynamic scenes. This is similar
to video game programming but with a greater
emphasis on accurate rendering and physical modeling. Problems of
interest here include simplification of objects (to save time by
avoiding the rendering of sub-pixel details) and collision detection.
There are also connections with graph drawing
for construction of 3d virtual environments that represent combinatorial
- Applications of computational geometry: virtual reality, 3d graphics, and route planning. Abstract for a talk in which Joe Mitchell describes his ongoing work.
- Central path
algorithm. Y.R. Ge and D. Stelts use medial axes to find paths
along the central line of the intestinal system as part of a
virtual endoscopy system
for non-invasive medical diagnosis.
detection research at UNC.
research in simulation and virtual environments, B. Mirtich, Berkeley.
- Detail removal.
The Queen's U. finite element group uses medial axes to simplify parts
to be simulated while maintaining as little error as possible,
as part of their
Presumably similar ideas would also apply to model simplification
for virtual reality.
Int. Eurographics Worksh. Computer Animation and Simulation, 1996,
proceedings contents, abstracts, and demos.
update of the visibility map as seen by a moving viewpoint in two
dimensions, S. Ghali and A. J. Stewart, Toronto.
- Interactive Walkthrough of Large Geometric Databases,
full day course, SIGGRAPH, August 1996, New Orleans.
Jiang's research in collision detection.
- Levels of
detail bibliography and links, M. Krus, CNRS.
level-of-detail generator for VRML.
simplification. Work at UNC on automatic
methods to produce visually accurate multi-resolution polygonal
simplifications of 3-D datasets. See also the UNC
Envelopes project and source code.
- 3d Engines
for real-time graphics.
collision detection. Philip Hubbard uses medial axes to find
multi-resolution approximations of a shape by unions of spheres,
and uses these approximations for fast collision detection.
Patent 3889107 covers the use of binary space partitions for hidden
surface removal, shadow calculation, and collision detection.
- The V-Clip
collision detection library for exact collision detection between
non-convex polyhedra (intended for use after bounding boxes or other
methods have been used to reduce the set of possible collisions).
Visualizing the structure of the WWW in hyperbolic space,
T. Munzner and P. Burchard. Hyperbolic graph drawings and
Geometry in Action,
a collection of applications of computational geometry.
from a common source file.