me | department | university | teaching | research | disclaimer

Roofs, Terrains, Chamfers and Fillets Based on Skeletal Structures

We study the generation of complex roofs, terrains, chamfers and fillets. The underlying mathematical concept that drives our work is given by the theory of skeletal structures, such as medial axis and its straight-line relative, the straight skeletons. In a nutshell, these skeletal structures partition the plane into regions such that all points of one region are closer to one input entity than to all other input entities. The precise meaning of ``closer'' and ``input entity'' depends on the specific skeletal structure. For an input polygon P in the plane, both structures can be constructed by wavefront propagation, where an offsetting process causes P to shrink while obeying certain rules. During the offsetting process, an offset structure traces out the interior of P, arriving at each locus with coordinates (x,y) at a specific point in time t(x,y).

By interpreting time t as z-coordinate one gets points in 3D with coordinates (x, y, t). The set of all these points forms a three dimensional structure which is commonly called the roof of P. We extend this standard roof interpretation by a conceptually simple yet powerful method which allows to model various styles of roofs or sinks. Basically, we lift the area bounded by P into 3D such that a roof-like surface is formed whose intersection with the plane is given by P.

Combining this concept with Voronoi diagrams or additively-weighted and multiplicatively-weighted straight skeletons allows to generate complex "roofs" and "terrains". Portions of such a surface can be seen as a complex chamfers and fillets. We can handle arbitrary polygonal areas with and without holes, and one method also allows to deal with boundary curves that consist of both straight-line segments and circular arcs. Please note that some of these structures cannot be generated by conventional straight skeletons, even if multiplicative weights are used.

The following roofs were generated by a commercial user of our work. More sample images of roofs of buildings and terrains and of chamfers and fillets are available.

[SK-based roof] [SK-based roof]

This research was supported by the Austrian Science Fund (FWF): Grants P25816-N15 and ORD 53-VO. Joint work with Günther Eder and Peter Palfrader.

Related publications:

M. Held, P. Palfrader (2019):
"Skeletal Structures for Modeling Generalized Chamfers and Fillets in the Presence of Complex Miters".
Computer-Aided Design and Applications, 16(4):620--627, 2019.

G. Eder, M. Held, P. Palfrader (2018):
"Min-/Max-Volume Roofs Induced by Bisector Graphs of Polygonal Footprints of Buildings".
Int. Journal of Computational Geometry & Applications, 28(4):309--340, 2019

P. Palfrader, M. Held (2017):
"Straight Skeletons with Additive and Multiplicative Weights and Their Application to the Algorithmic Generation of Roofs and Terrains".
Computer-Aided Design, 92(1):33-41, Nov 2017.

[Image of CS Logo]
file last modified: Monday, 30-Mar-2020 20:52:18 CEST
Copyright © 2024 Martin Held. All rights reserved.
[Image of CS Logo]