Graphics
This area is quite closely connected with computational geometry; for
instance ACM TOG often publishes computational geometry papers.
Geometric research topics in graphics include data structures for ray
tracing, clipping, and radiosity; hidden surface
elimination algorithms; automatic simplification for distant objects;
morphing; clustering for color quantization; converting triangulated
surfaces to strips of triangles (some graphics engines
take inputs in this form to save bandwidth); and construction of
low-discrepancy point sets (for oversampling to eliminate Moire effects
in ray tracing). Specialized applications of graphics
in which other geometric ideas are needed include
architecture,
virtual reality, and
video game programming.
This area is also related to mesh generation
in several ways: both fields use triangulation algorithms to partition
complex surfaces into simpler pieces, and radiosity calculations in
graphics are essentially a special case of the finite element method.
- ACM Special Interest Group on
Graphics (SIGGRAPH).
- ACM Transactions on Graphics.
- Annotated bibliography on object representation schemes for 3d graphics, H.-G. Park, Air Force Inst. Tech.
- Bibliographies on Computer Graphics, Alf-Christian Achilles, U. Karlsruhe.
- Computational Topology.
Survey paper by Dey, Edelsbrunner, and Guha, presented at the conference
"Computational Geometry -- Ten Years After". Includes descriptions of
applications in image processing, cartography, graphics, solid modeling,
mesh generation, and molecular modeling.
- Computer Graphics
directory, Perceptual Science Lab, UC Santa Cruz.
- Converting
sets of triangles with shared edges into triangle strips,
Brad Grantham.
- Displaying a Voxel-Based Object Via Linear Octrees, Gargantini et al., Proc.
SPIE 1986.
- Dynamic
Scene Radiosity.
Robert Grzeszczuk, U. Chicago, maintains a triangulated mesh
dynamically, keeping track of the topological changes in
the pattern of shadow crossings in an image.
- Floating
Points. Deussen, Hiller, van Overveld, and Strothotte use Voronoi
diagrams to place stipple points for
non-photorealistic rendering.
- From
computational geometry to computational physics, M. Pellegrini,
ERCIM News, Apr. 1996.
Marco describes his recent work on algorithms for form
factors, radiosity, and electrostatics, using integral geometry and
Monte Carlo methods in place
of the traditional finite element meshing approach.
- Geometry for computer graphics. Teaching materials from the ITTI Gravigs
Project.
- Mosaic / stained glass graphic effect. One gets interesting
visual effects by taking a random sample of pixels from a bitmap image,
computing the Voronoi diagram of the sample, and filling each cell
with the corresponding sample's color. This appears to be what
Photoshop does in its "Pixelate->Crystalize" filter;
it can be thought of as a form of piecewise constant function interpolation.
- MosaicExpress and Mosaïque 2000 PC software for designing and building tile mosaics, based
on square, hexagonal, triangular, and other tilings of the plane.
- Jeffry
Nimeroff works with both the Computer and Information
Science and Architecture depts. at U. Penn., on illumination
algorithms for architectural computer graphics.
- Programmer's
Heaven computer graphics programming links.
- PUERTRA, software for modeling Islamic geometric art.
- Seth Teller
of MIT is constructing a database
of buildings in Cambridge Mass. Related algorithmic questions
include methods for combining image data from different
sources into a single 3d model, and data structures for fast rendering
of the resulting graphics.
- SIGRAPI 2001,
14th Brazilian Symposium on Computer Graphics and Image Processing,
Santa Catarina, 15-18 October 2001.
Lists computational geometry as one of the possible submission topics.
- Stripe
tool for converting polygonal models into triangle strips, for fast
output to graphics hardware.
- 3d
Geometric Morphing, R. Rohrer, George Washington U.
- US
Patent 3602702 covers the quadtree subdivision of a viewing plane to perform hidden surface removal in computer graphics.
Patent 4694404 covers the use of octrees to implement a nearer-object-first
painting order.
Patent 5123084 describes a similar nearest-first octree graphics method.
Patent
5222201 also concerns octree graphics methods, and describes
a heuristic for speeding up the conversion of objects into octree
representations.
- US
Patent 3889107 covers the use of binary space partitions for hidden
surface removal, shadow calculation, and collision detection.
- US
Patent 5129051 covers a slab method of performing trapezoidal
decomposition and its application to scan-line conversion in computer graphics
(Patent
4791582).
Patent 5276783 is also on slab-based trapezoidalization.
Patent
5020002 is harder to
decode; it seems to be describing an ear-cutting trapezoidalization method.
- US Patent 5268998 seems to cover graphical display of objects in non-Euclidean or higher dimensional geometries.
- US Patents
5317681 and
5428717 cover methods for finding convex hulls of
polyhedra based on flipping reflex edges, along with an animated version
of this procedure that creates a smooth morph of the polyhedron to its hull.
- US
Patent 5574835 describes a method of performing visibility checking
of polygons by intersecting bounding boxes.
Part of
Geometry in Action,
a collection of applications of computational geometry.
David Eppstein,
Theory Group,
ICS,
UC Irvine.
Semi-automatically
filtered
from a common source file.
