Euclidean Geometry. - 2D Computational Euclidean Geometry. - Geometric Predicates. - 3D Computational Euclidean Geometry. - Affine Transformations. - Affine Intersections. - Genericity in Geometric Computing. - Numerical Precision. - Non-Euclidean Geometries. - 1D Computational Spherical Geometry. - 2D Computational Spherical Geometry. - Rotations and Quaternions. - Projective Geometry. - Homogeneous Coordinates for Projective Geometry. - Barycentric Coordinates. - Oriented Projective Geometry. - Oriented Projective Intersections. - Coordinate-Free Geometry. - Homogeneous Coordinates for Euclidean Geometry. - Coordinate-Free Geometric Computing. - Introduction to CGAL. - Raster Graphics. - Segment Scan Conversion. - Polygon-Point Containment. - Illumination and Shading. - Raster-Based Visibility. - Ray Tracing. - Tree and Graph Drawing. - Tree Drawing. - Graph Drawing. - Geometric and Solid Modeling. - Boundary Representations. - The Halfedge Data Structure and Euler Operators. - BSP Trees in Euclidean and Spherical Geometries. - Geometry-Free Geometric Computing. - Constructive Solid Geometry. - Vector Visibility. - Visibility from Euclidean to Spherical Spaces. - Visibility in Space. - Appendices. - The PostScript Language. - OpenGL. - The GLOW Toolkit.
Table of contents:
pdf,
txt.
Code:
igc-code.zip,
igc-code.tgz.
Figures:
pdf —
1 figure/page; 348 figures (345 vector + 3 raster).
Errata:
pdf.
Any geometric algorithm can be dissected into combinatorial parts and geometric parts. The two parts intertwine both in the description of the algorithm and in its implementation. We consider the benefits of relaxing this tight coupling.
Coordinate freedom is widely considered the most important principle in designing and implementing geometric systems. By ensuring that client code not manipulate individual coordinates and by restricting such access to input and output components, a geometric algorithm can be implemented without knowing how the coordinates are represented. By developing two sets of core classes, one based on homogeneous and the other based on Cartesian coordinates, switching from one to the other can be easily performed after the system has been completed.
We take another step and show that geometry freedom is possible. By removing the geometric classes (along with their dependence on coordinates) from the implementation of a geometric algorithm, the algorithm becomes purely combinatorial. An arbitrary Euclidean or spherical geometry is then used as a parameter to the combinatorial algorithm to produce a geometric system in that geometry.
Geometric freedom is helpful, for instance, when a geographic input is no longer constrained to a small area of Earth and one wishes to use spherical instead of Euclidean geometry. We show examples for applying geometry freedom to three classical problems: convex hulls, Delaunay triangulations, and binary space partitioning. The algorithms become generic with respect to the geometry (for convex hulls and Delaunay triangulations) or with respect to both the geometry and the dimension (in the case of binary space partitioning).
pdf (0.56 MB)
Computer graphics is ostensibly based on projective geometry. The graphics pipeline—the sequence of functions applied to 3D geometric primitives to determine a 2D image—is described in the graphics literature as taking the primitives from Euclidean to projective space, and then back to Euclidean space.
This is a weak foundation for computer graphics. An instructor is at a loss: one day entering the classroom and invoking the established and venerable theory of projective geometry while asserting that projective spaces are not separable, and then entering the classroom the following week to tell the students that the standard graphics pipeline performs clipping not in Euclidean, but in projective space—precisely the operation (deciding sidedness, which depends on separability) that was deemed nonsensical.
But there is no need to present Blinn and Newell's algorithm—the crucial clipping step in the graphics pipeline and, perhaps, the most original knowledge a student learns in a fourth-year computer graphics class—as a clever trick that just works. Jorge Stolfi described in 1991 oriented projective geometry. By declaring the two vectors (x,y,z,w) and (-x,-y,-z,-w) distinct, Blinn and Newell were already unknowingly working in oriented projective space. This paper presents the graphics pipeline on this stronger foundation.
pdf (0.29 MB)
We introduce a novel representation for visibility in three dimensions and describe an efficient algorithm to construct it. The data structure is a spherical map that consists of a doubly connected edge list embedded on the surface of a sphere. Each face of the spherical map is labeled with the polygon visible in the corresponding cone. We demonstrate that the algorithm is efficient and robust by showing statistics of its time and space requirements for handling several classes of input.
Rendering interactive shadows using the stencil buffer makes it possible to generate precise shadow boundaries without the need to compute the location of these boundaries. And yet the shadow volumes used are computed individually for each solid in a scene. How can the set union of the shadow volumes be computed so that one can extract a water-tight description of the boundary of the volume?
pdf (0.56 MB)
One can compute boolean operations on bounded regular point sets in the plane using an algorithm described in 1987, but that algorithm can easily fail in the presence of numerical imprecision. A variation on geometric duality in addition to a robust version of Sutherland and Hodgman's classical clipping algorithm are what is needed for a robust implementation. Also, building this library component using Mehlhorn and Seel's infimaximal frames makes it possible to handle unbounded point sets as well, which in turn easily solves halfplane intersection, another problem that would only with much practical difficulty be solved via duality.
Is it possible to design a computer graphics API such that modeling primitives, computing visibility, and generating shadows from point, linear, and area light sources can be conveniently and concisely expressed?
We answer this question in the affirmative by describing a framework for geometric computing in computer graphics. The classes in the layered system constituting the framework are described using the UML notation and each algorithm presented is encapsulated in a member method of a class in the hierarchy.
Platform-neutral C++ GUI libraries: fltk, glGUI, plib, wxWidgets, GLUI, GLOW, AGAR, gtk, SDL, ClanLib, Qt
You must naturally be prepared to sacrifice simplicity to some extent if you wish to be interesting. –G. H. Hardy (1877-1947), What is Geometry?, Mathematical Gazette, 12(175):315, 1925.
It is much easier to choose the language on which to base a graphics system than to decide just how to add to it the necessary graphics features. –Newman & Sproull, Principles of Interactive Computer Graphics, p. 365.