Software Design in Computational Geometry and Contour-Edge Based Polyhedron Visualization. Lutz Kettner. PhD Thesis, ETH Zürich, Institute of Theoretical Computer Science, 148 pages, September 1999.
[PostScript,
A4 size] 7 MB, 39 MB uncompressed
[PostScript,
letter size] 7 MB, 39 MB uncompressed
In computational geometry efficient algorithms and data structures are designed and analyzed for geometric problems. I address important software design questions to achieve flexible and efficient implementations. I present new design solutions particularly useful for geometric algorithms and data structures, among others a halfedge data structure for polyhedral surfaces. For three-dimensional polyhedral surfaces, visibility algorithms are an important class of algorithms. I present a new approach based on contour edges. The advantages are supported by my extensive experimental study. In particular, I describe a new object-space hidden-surface removal algorithm for three-dimensional polyhedral surfaces. The algorithms also serve as a case study for the software design solutions.
I have successfully applied the recent paradigm of generic programming to the domain of geometric algorithms and data structures. Examples are the implementation of my new visibility algorithms and my contributions in designing CGAL, the Computational Geometry Algorithms Library. CGAL, written in C++, is being developed by research groups in Europe and Israel. I give an introduction to generic programming and present our extensions, circulators and geometric traits classes, which solve specific problems in geometric algorithms.
In particular, I present a library design solution for combinatorial data structures such as polyhedral surfaces and planar maps. The design issues considered are flexibility, time and space efficiency, and ease-of-use. I focus on topological aspects of polyhedral surfaces and evaluate edge-based representations with respect to my design goals. A halfedge data structure has been realized. Connections to planar maps and face-based structures are clarified.
The new visibility algorithms for three-dimensional polyhedral surfaces are based on contour edges. Given a view point, an edge is a contour edge if it is incident to a front-facing facet and a back-facing facet. The algorithms exploit the fact that the number of contour edges is usually much smaller than the overall number of edges. I provide evidence for, and quantify, the claim that the number of contour edges is small in many situations. For example, an asymptotic analysis of polyhedral approximations of a sphere with Hausdorff distance shows that, while the required number of edges for such an approximation is , the number of contour edges in a random orthogonal projection is only .
Indeed, the number of contour edges is small for many objects, especially for polyhedral approximations of curved surfaces. These findings are based on an experimental study of polyhedral surfaces from several application areas. I analyze, for random orthogonal projections, the expected number of contour edges and the expected number of their intersections in the projection. The number of intersections is a quantity relevant for the runtime of sweep-line algorithms, which I use in my visibility algorithms. The small number of intersections support fast expected running times for this approach.
Concluding from the experimental study, the extraction of the contour edges from the total number of edges, , is likely to determine the runtime of this algorithms. Thus, a view-independent preprocessing is of interest. One can prepare a data structure of only nearly linear size so that one can answer a query for the contour edges for a particular viewing transformation in log for orthogonal projections or in for perspective projections, where denotes the number of contour edges reported. These results are based on a transformation of the contour-edge reporting problem to a segment stabbing problem.
I present three new visibility algorithms based on contour edges: the computation of the silhouette of a three-dimensional polyhedral surface, object-space hidden-surface removal for general three-dimensional polyhedral surfaces and a faster and easier specialization of the object-space hidden-surface removal for terrains. Let be number of contour edges, int the number of their intersections, and the size of the output. The silhouette can be computed in intlog time. The visibility map, the output of the object-space hidden-surface removal algorithm, can be computed for terrains in intloglog time. For general polyhedral surfaces, a geometric construction shows that the visibility map cannot be computed within a similar time bound by following this approach. This construction requires locating the visible facet within a hole. If we denote the total time needed for locating all these facets with then the visibility map for general polyhedral surfaces can be computed in intlogloglog time. The expected runtime of these algorithms for a particular object can be derived almost directly from the results of the experimental study.
The implementation of these visibility algorithms is based on the classical Bentley-Ottmann sweep-line algorithm for segment intersection. Degeneracies are successfully handled using symbolic perturbation of the viewing transformation. The geometric predicates in the algorithms are evaluated exactly by using exact and bounded integer arithmetic with efficient built-in number types. For each predicate, bounds on the required precision in the arithmetic are given. The new software design solutions proved to be very useful in these implementation.