Theory and Application of Straight Skeletons in 2D and 3D

A straight skeleton is a geometric structure studied in the field of computational geometry which features a wide range of real-world applications in science and industry. The wide range of potential applications is contrasted by the fact that important questions related to straight skeletons have not been addressed yet. And this remark is particularly relevant for generalizations such as weighted straight skeletons in two dimensions and straight skeletons of three-dimensional polyhedra. Little is known on the geometry of weighted straight skeletons, and efficient algorithms for practical applications are missing. And almost nothing is known on the geometry of straight skeletons of polyhedra, and algorithms for their computation (and even trivial brute-force implementations) do not exist. In prior work we successfully generalized the so-called motorcycle graph in order to use it as a tool for the geometric characterization and efficient computation of straight skeletons of arbitrary planar straight-line graphs. Our investigation allowed us to design and implement Bone, which is the most efficient straight-skeleton code currently available. In this project we propose to extend the knowledge we have gained to (1) weighted straight skeletons in two dimensions and to (2) straight skeletons of three-dimensional polyhedra. Our goal is to achieve results for these two main work items that are comparable to our current results for ordinary straight skeletons. Our new work will again rely strongly on the efficient computation of motorcycle graphs. Hence, we also propose to work on more efficient algorithms for the practical computation of motorcycle graphs. These two main work items will be supplemented by work on other problems related to straight skeletons. First, we will extend Bone to make it compute linear axes. Second, we will investigate the handling of discontinuities of the straight skeleton in the presence of imprecise data, in an attempt to come up with a canonical representative skeleton. Third, we will use the characterization of straight skeletons as the lower envelope of linear functions to compute discrete skeletons by rendering on a graphics hardware. Besides working on a thorough mathematical and algorithmic foundation for straight skeletons in 2D and 3D, we will place our emphasis on converting our algorithms into software tools, in order to jump-start future work by providing colleagues and companies with ready-to-use libraries. These tools will be implemented as small modules of their own and, thus, will be widely applicable. Hence, while being motivated by genuine algorithmic problems of computational geometry, the tools that we propose to develop will be applicable to diverse fields, including, but not limited to, CAD/CAM, architecture and GIS, thereby broadening the practical impact of the work proposed.

Computational geometry is a field of (theoretical) computer science which is concerned with the efficient solution of problems that bear a geometric flavor. Straight skeletons form a key data structure of computational geometry; they provide the algorithmic basis for efficient solutions to a variety of geometric problems in diverse fields of application, ranging from tool-path planning in CAD/CAM to shape reconstruction in medical imaging, roof modeling in architecture, the computation of centerlines of roads and rivers in geographic information systems, and even to computing so-called crease patterns in mathematical origami. Roughly, the straight skeleton of a simple polygon is defined by a wavefront propagation process. That is, one considers a shrinking process by which each polygon edge moves inwards at unit speed and in a self-parallel fashion. This moving wavefront mimics the input polygon, but its shape changes over time: edges may vanish and the wavefront may be split into parts. The straight skeleton is defined as the set of loci traced out by the vertices of the wavefront. The same principle can also be applied to planar straight-line graphs, i.e., to a set of straight-line segments in the plane that do not intersect each other in the interior. In this project, a mathematical characterization of additive and multiplicatively weighted straight skeletons was developed. In particular, a procedure was designed to resolve ambiguities that may arise in the interaction of moving input segments. For special classes of input polygons convex and so-called monotone polygons algorithms could be designed whose runtime complexities clearly beat the best known results. In addition to the development of theoretical fundamentals including algorithms (such as Surfer) for the calculation of weighted straight skeletons, practical applications of these skeletal structures were investigated. For instance weighted straight skeletons are used for a fully automatic modeling of roof structures of buildings with polygonal foot- prints. The multiplicative and additive weights result in roof facets of different inclinations and different heights. In a similar way one can model generalized chamfers and fillets in the presence of complex miters. Like Surfer, all algorithms designed in the course of this project were implemented and tested carefully. In the meantime, our codes are used by colleagues in academia and the University of Salzburg has started to license the resulting software modules to companies for commercial use. Hence, the practical impact and technology transfer achieved by this project can certainly be regarded as a success story.