29. Representations of Geometry for Computer Graphics

Full Day / Advanced

The latest research on the most important computational representations of geometry used in computer graphics. The emphasis is on their strengths and weaknesses and how to build a coherent system that supports multiple representations.

Who Should Attend
Industrial software engineers engaged in the implementation of computer-graphics, geometric-modeling, or visualization-based systems, and anyone who is conducting research in these "geometric computation" areas.

Bruce Naylor
Spatial Visions

Chandrajit Bajaj
Purdue University

Herbert Edelsbrunner
University of Illinois

Arie Kaufman
State University of New York at Stony Brook

Jarek Rossignac IBM Corporation


8:30 am: Introduction - Naylor

Course objectives and taxonomy of representations.

8:45 am: Discrete-Space Volume Representations - Kaufman

Volume graphics is an emerging subfield of computer graphics concerned with the synthesis, manipulation, and rendering of volumetric modeled objects, stored as a volume buffer of voxels. Unlike volume visualization which focuses primarily on sampled and computed data sets, volume graphics is concerned primarily with modeled geometric scenes and particularly with those that are represented in a regular volume buffer. Volume graphics has advantages over surface graphics by being viewpoint independent, insensitive to scene and object complexity, and suitable for the representation of sampled and simulated data sets and mixtures thereof with geometric objects. It supports the visualization of internal structures, and lends itself to the realization of block operations, CSG modeling, and hierarchical multi-resolution representations. The problems associated with the volume buffer representation, such as discreteness, memory size, processing time, and loss of geometric representation, echo problems encountered when raster graphics emerged as an alternative technology to vector graphics and can be alleviated in similar ways.

10:00 am: Break

10:15 am: Boundary/Topological Representations - Rossignac

We will discuss boundary/topological representations for characterizing the topological coverages of CAD system, for comparing the data structures they maintain, and for reliably computing boundary models from constructive representations. Creating multi-resolution representation will be addressed.

11:15 am: Shapes, Complexes, and Surfaces - Edelsbrunner

The main theme of this talk is the idea of using cell decompositions (complexes) to model geometric shapes. The complex is what is often called a grid or mesh. This approach to modeling allows the instantaneous analysis of the created shape. The following specific questions and issues will be addressed.
- What are complexes? (definitions and examples)
- How can the geometric integrity of a complex be guaranteed?
- How can complexes be used to model shape?
- How can complexes be manipulated and maintained?

12:00 noon: Break

1:30 pm: Non-linear Surface-Patch Representations - Bajaj

Algebraic curves and surfaces can be represented in an implicit form, and sometimes also in a parametric form. We will compare the implicit and parametric representations of algebraic surfaces by considering the the parametric form either as a mapping or alternatively, an algebraic variety. In this course, I shall consider specific geometric operations: scattered data fitting and surface display and compare the implicit and parametric forms for their superiority (or lack thereof) in optimizing algorithms for these operations.

3:00 pm: Break

3:15 pm: Binary Space Partitioning Trees - Naylor

Partitioning Trees, a multi-dimensional generalization of binary search trees, provide a computational representation of geometry via recursive subdivision with hyperplanes defined by linear equations. Linearity and recursive subdivision lead to simple algorithms for visibility (hidden surface removal, transparency, shadows) as well as intersections (set operations, collision detection, clipping, ray-tracing). We will present a review of these capabilities as well as present new results on building multi-resolution trees, representing volumetric data, and integrating parametric surfaces into Partitioning Trees to permit local non-linear deformations.

4:15 pm: Building a Whole Geometry System - All

Having presented each of the representational schemes, we will now be in a position to focus exclusively on the relation between the various representations and how one can build a single coherent geometry system that exploits the strengths of each and avoids their weaknesses. We will be able to draw upon the experience of several of the speakers who have built such integrated systems.

Course Notes

Voxels as a Computational Representation of Geometry, by Arie E. Kaufman, is missing from the printed notes. A PDF version can be downloaded here (Adobe Acrobat PDF, 431KB).

Courses Main Page ACM SIGGRAPH Contact us about:
Courses | This Web Site

Final SIGGRAPH 96 Web site update: 25 October 1996.
For complete information on the next conference and exhibition, see: http/