Straight Skeleton Computation Optimized
for Automatic Generation of 3D Roof Model○ Kenichi Sugihara*1, Zhenjiang Shen*2*1 Professor, Faculty of Information Media, Gifu Kyoritsu University*2 Professor, Faculty of Geosciences and civil Engineering, Institute of Science and Engineering, Kanazawa University
Summary: 3D building models with roofs are important in several fields, such as urban planning and BIM (Building
Information Model). However, enormous time and labor are required to create these 3D models. In order to automate laborious
steps, a GIS and CG integrated system has been proposed for the automatic generation of 3D building models, based on building
polygons (building footprints) on digital maps. The generation is implemented through straight skeleton computation, in which
three events (‘Edge’ and ‘Split’, ‘Vertex’ events) were proposed. In the computation process, usually three edges propagate i nto anode. Often it causes an acute angle shape that is not appropriate for roof boards. To avoid the inappropriate shape, in this paper,
methodologies are proposed for adding ‘Line segment’ events besides the conventional events, and for monotone polygon nodes
sorting.
Keywords: straight skeleton, automatic generation, 3D building model, GIS, 3D CG, building footprint

1. Introduction
3D town models, as shown in Figure 1 right, are important inproposed by Aichholzer et al.4). In their proposal, two events

urban planning and architectural design, e.g., BIM. However,Besides two events, Eppstein et al. 5) suggested a ‘Vertex’ event

enormous time and labour has to be consumed to create these 3D

in which two or more reflex vertices reach the same point

models, using 3D modeling software such as 3ds Max orsimultaneously. A reflex vertex is a vertex whose internal angle

SketchUp. In order to automate the laborious steps, a GIS

is greater than 180 degrees. However, some roofs are not created(Geographic Information System) and CG integrated system hasby these three events proposed. In our paper 3), the methodology

been proposed for automatically generating 3D building models,

was proposed for constructing roof models by assuming ‘thebased on building polygons (building footprints) on a digital map

Third event’ in which a reflex vertex runs into the edge, but theshown in Figure 1 left 1)2)3). In the digital map, not all building

other split polygon is collapsed into a node (an Edge event

polygons are orthogonal. In either orthogonal or non-orthogonal

happens in the Split event at the same time).

polygons, methodologies were proposed for automaticallygenerating 3D building models with general shaped roofs by thestraight skeleton defined by a continuous shrinking process(‘Edge’ and ‘Split’ events) will occur during shrinking process.

Our contribution lies in a new methodology for adding a‘Line segment’ event by which the inappropriate roof board

GIS Application

GIS Module

CG Module(ArcGIS)*Building polygons on 2D
Digital Map*Attributes (left up) such as atexture map code and numberof stories linked to building
polygons(Python & Visual Basic)(MaxScript)*Acquire coordinates ofbuilding
polygons’
vertices & attributes by
Python including ArcPy(ArcGIS)*Generation of 3D roof models
by placing roof board primitives
to monotone polygons, and roof
ridges primitives to straightskeleton segments with Boolean
operation* Generation of walls, windows
and facade by placing wall andwindows board primitives along
the receded building polygons
by setback distance*Node formation byedge events and split
events by shrinking
building
polygons
through straight skeleton
computation*
Straight
skeletonformation from nodes* Monotone polygon
generation*Automatic texture mapping
onto primitives by classifying a
set of primitives according toattributes
Automatically generated 3D urban model*Automatic texture mapping
onto
by Modelsclassifying
Figure 1. Pipeline of Automatic Generation for
3Dtriangles
Building
byaStraight Skeleton Computation
set of triangles according to
日本建築学会情報システム技術委員会
features
第 42 回情報･システム･利用･技術シンポジウム論文集， 196-201 ， 2019 年 12 月，東京
Proceedings of the 42nd Symposium on Computer Technology of Information ，Systems and Applications ， AIJ ， 196-201 ， Dec. ， 2019 ， Tokyo－ 196 －

shape can be avoided. In the straight skeleton computation, thedesign and BIM, 3D building models should be made up of

shrinking process continues if split polygons have non-zero area.

solid geometries primitives which will be parts of the building,

The shrinking process ends when split polygons fall intocreated through Boolean operation. While the ‘surface models’‘Vertex’ or ‘Line segment’ since they have no area.

trace the surface of the parts of 3D building model, the 3D

Consequently, a ‘Line segment’ can be a resulting shape ofmodels used for architectural design should consist of building

shrinking procedure, and we classify a ‘Line segment’ event incomponent created by CSG (Constructive Solid Geometry).

which two line segments collapse into one line segment.

Thus, the GIS and CG integrated system is proposed for

Usually three edges propagate into a node. Often it causes anacute angle shape that is not appropriate for roof boards shownin Figure 3(d). To avoid the inappropriate shape, a ‘Linesegment’ event is proposed. We also propose ‘monotone polygon
nodes sorting’ by which not self-intersecting monotone polygons
are formed, where ‘monotone polygons’ are the areas divided bya straight skeleton, as shown in Figure 2(c).

automatically generating 3D building models by CSG.
3. Pipeline of Automatic Generation
As the pipeline of automatic generation is shown in Figure 1, thesource of 3D models is a digital map that contains building
polygons linked with attributes data, such as the number ofstories and the type of roof, shown in Figure 1 left up. The maps
are then preprocessed at the GIS module, and the CG module
finally generates the 3D building model.

2. Related Work
Since 3D building models are utilized in several fields, various
types of technologies, ranging from computer vision, computer
graphics, photogrammetry, and remote sensing, have been
proposed and developed for creating 3D building models.
Procedural modeling is an effective technique to create 3Dmodels from sets of rules such as L-systems, fractals, andgenerative modeling language 6). Mueller et al.7) have created anarchaeological site of Pompeii by using a shape grammar. They
import data from a GIS database and try to classify imported
mass models as basic shapes in their shape vocabulary. If this is
not possible, they use a general extruded footprint together witha general roof obtained by the straight skeleton computation
defined by a continuous shrinking process 4).
As a new generalization of straight skeletons, Helda et al.8)
introduce

additively-weighted

straight

skeletons.

Anadditively-weighted straight skeleton is the result of a
wavefront-propagation process where wavefront edges do notnecessarily start to move at the begin of the propagation,
resulting in an automated generation of roofs in which theindividual facets have diﬀerent inclinations and start at diﬀerent
heights.
By using the straight skeleton, Kelly et al.9) present a userinterface for the exterior of architectural models to interactively
specify procedural extrusions, a sweep plane algorithm tocompute a two-manifold architectural surface.
By the interactive modeling, 3D building models withplausible detailed façade can be achieved. However, thelimitation of these modeling is the large amount of userinteraction

involved10),

The preprocessing at the GIS module includes theprocedures as follows: (1) Calculate the minimum receding
distance for an Edge event (including a Third and Line segment
event). Until the Edge event occurs, check if a Split event
happens by starting continuous shrinking process. (2) Start
continuous shrinking process in which edges of the polygon
move inward, parallel to themselves at a constant speed shown in
Figure 2(a)&2(b). (3) Detect any event such as a Split, Edge orLine segment event during shrinking process, and formation ofnodes by these events. The position of the node is calculated by
the intersection of angular bisectors. (4) Inherit and store three ormore ‘original edge ID’ (e.g. edgN in Figure 2(a)) linked to thenode during the shrinking process in which the topology of thepolygon will change. In shrinking process, Figure 2(b) shows
edg2 firstly disappears into Node1, and two edges (edg8 & 9)
secondly result in Node2. Since at least three original edges
sweep into the node, edg1,2 & 3 propagation result in Node1,
and edg4,5 & 10 propagation result in Node3 (by Split event). (5)Every (original) edge will inquire ‘each node’ having three ormore ID to find out which node has the same ‘original edge ID’.
If so, then nodes of the same ID are collected and the set ofnodes are sorted according to the edge vector to form ‘monotone
polygon’ and the straight skeleton. (6) Calculate the length,
width, center position and inclination of the bounding rectangles
for ‘monotone polygons’. (7) Export the coordinates ofpolygons’ vertices, ‘monotone polygons’ information, andattributes of buildings.
As shown in Figure 1, the CG module receives theand the models created are ‘surface

pre-processed data that the GIS module exports, generating 3Dmodels’ by sweeping or extruding, revolving 2D primitive

building models. In GIS module, the system measures the length

geometries. When creating 3D building models for architecturaland inclination of the bounding rectangle for the monotone

論文 R37－ 197 －

polygon that will be a roof board. The CG module generates athis edge, thus splitting the whole polygon. New adjacencies

bounding box of the length and width, measured in GIS module.

occur between the split edge and each of the two edges incident

The monotone polygons will be converted into primitives, i.e.,to the reflex vertex.

thin boxes by Boolean operation between the extrusion of themonotone polygon and the box primitive.

If the sum of the internal angles of two vertices incident toan edge is more than 360 degrees, then the length of the edge

In case of modeling a building with roofs, the CG module
follows these steps: (1) Generate primitives of appropriate size,
such as boxes, prisms or polyhedra that will form the various
parts of the house. (2) Boolean operations applied to theseprimitives to form the shapes of parts of the house, for examples,making holes in a building body for doors and windows, making
trapezoidal roof boards for a hipped roof and a temple roof. (3)Rotate parts of the house according to the inclination of thepartitioned rectangle. (4) Place parts of the house. (5) Texture
mapping onto these parts according to the attribute received. (6)Copy the 2nd floor to form the 3rd floor or more in case ofbuilding higher than 3 stories.

increases, otherwise the edge will be shrunk to a point (node).
Shrinking procedure is uniquely determined by the distance dshri
between the two edges of before & after shrinking procedure.
The distance e_dshri is the dshri when an edge event happens inthe shrinking process. e_dshri for the edge (edi) is calculated asfollows:

e_𝐝shri =Ｌi(1)

cot 0.5 ∗ θi + cot 0.5 ∗ θi+1

where Li is the length of edi, and θi & θi+1 are internal angles ofvertices incident to edi.
When 0.5*θi＋0.5*θi+1＜180 degrees, i.e., the sum of theinternal angles of two vertices incident to an edge is less than

4. Straight Skeleton Computation
Aichholzer et al. 4) introduced the straight skeleton defined as

360 degrees, an Edge event may happen unless the edge isthe union of the pieces of angular bisectors traced out by

Split event happens.

intersected by an angular bisector from a reflex vertex and apolygon vertices during a continuous shrinking process inwhich edges of the polygon move inward, parallel to themselves
at a constant speed. The straight skeleton is applied to

4.1. HOW STRAIGHT SKELETON IS FORMED
How a straight skeleton and monotone polygons are formed isconstructing general shaped roofs based on any simple building

as follows.

polygon, regardless of their being rectilinear or not.

(1) One simple polygon (P) is given such as shown in Figure

As shrinking process shown in Figure 2, each vertex of the2(a). If there is any reflex vertex in the P, then it can be divided

polygon moves along the angular bisector of its incident edges.

into two or more polygons.

This situation continues until the boundary change topologically.

(2) The system calculates e_dshri (receding distance for an Edge

According to Aichholzer et al. 4), there are two possible types of

event, shown in (1)) for all edges and finds the shortest of them.

changes:Then, the system checks if a Split event occurs by increasing(1) Edge event: An edge shrinks to zero, making its neighboring

dshri by (e_dshri /n_step). In this way, the shrinking process mayedges adjacent now.

proceed until dshri reaches the shortest e_dshri calculated.

(2) Split event: An edge is split, i.e., a reflex vertex runs into

(3) During shrinking until dshri reaches the shortest e_dshri, the

a)

edg1

pt1

pt2

b)

c)

d)

edg2
pt3

Node1

Node1

Node5 Node4

edg3
Node3
edg4

edg10

Node3

pt5 pt4

edg5
Node7

pt6

edg9

edg6

edg8
pt9

pt8

edg7

Node2

Node2

Node6

pt7

Figure 2. Shrinking process and a straight skeleton, a roof model generated. a) Input polygon (bold) start continuous shrinking process
in which edges of the polygon move inward, parallel to themselves at a constant speed. b) Shrinking polygons (blue) by edge or no
event, and red one by a split event. c) The straight skeleton (blue) and monotone polygons. d) A roof model automatically generated:each roof board is based on an ‘monotone polygon’.

論文 R37－ 198 －

system checks if a ‘checking angular bisector’ from a reflex
vertex intersects another edge of the polygon or not. If an edge

4.2. NODE STRUCTURE
The generated node is associated with the edges of an originalis found intersected, then the system calculates the node

polygon P (original edge: o-edge) which are identified byposition by the Split event. The position of the node is‘o-edge ID’, e.g. edg1 & edg2 in Figure 2(a), since at least threecalculated by the intersection of two angular bisectors: one fromo-edges (original edges) sweep to form a node. Therefore, atthe reflex vertex and the other between the intersected edge andeach event when the node is generated, at least three o-edges are

one of two edges incident to the reflex vertex. However, edges

linked to the node. This means more than three o-edges ID are

may be intersected by several ‘checking angular bisectors’ fromstored in the node with an appropriate structure.

several reflex vertices. Among the several reflex vertices, theIn our system, a node has the following properties; (a) ‘Nodereflex vertex that gives the shortest dshri will be selected forType’ (how the node is risen; by an Edge event or a Split event,calculating the node position.

Vertex event, Multiple Edge event and so on) (b) ‘Number of(4) In the process of (2), a Split event may happen and theforming edges’ (usually three edges sweep to form a node, butpolygon will be divided into some polygons: Ps.

more than three edges sweep in case of Multiple Edge event) (c)In this ‘Split event checking’ process, all divided polygons are‘o-edge ID preceding the vanishing edge’ (by an Edge event) or

checked if they can be divided more. As long as there are some‘o-edge ID of the edge incident to the reflex vertex’ (by a Split

Ps that can be divided, ‘Split event checking’ routine will

event) (d) ‘o-edge ID following the vanishing edge’ (by an Edge

continue. After that, the system concentrates on the Edge event

event) or ‘o-edge ID of the other edge incident to the reflex

procedure.

vertex’ (by a Split event) (e) ‘o-edge ID of at least one vanishing(5) In this stage, since the number of polygons divided does notedge’ (by an Edge event) or ‘o-edge ID of a split edge’ (by aincrease by the Split event, the system can focus on the Edge

Split event)

event including Third and Line segment event procedures. If theSince three edges usually sweep into the node, threepolygon divided has only three vertices, then the polygon‘o-edge IDs’ are stored in the property of a node. These IDs are(triangle) collapses to a node; this is the final stage for theused for forming a monotone polygon by collecting the nodes

polygon divided.

which has the same ‘o-edge ID’ as each own o-edge ID.

(6) While the Edge events are being executed, the topology ofIn special cases, four or more edges collapse into a node,

the polygon will change. If the change happens, then the systemsuch as Node2 in Figure 2 and Node2 & Node5 in Figure 3(e).

re-implement the process from (2) to (5) for the polygon whose

In extreme cases, such as a hexagon or a regular polygon, a

topology has changed. At that moment, the system recalculates

star-shaped polygon collapses to a node, four or more o-edges

the length of each edge and the internal angle of each vertex inwill sweep into a node. Therefore, a node needs ‘Number oforder to find the shortest dshri for next events. This

forming edges’ property. This is the case of a multiple Edge

re-implementation process continues until all polygons changed

event or the case Eppstein et al.5) defined as a ‘degenerate case’collapse to a node or a line segment.

in which the straight skeleton can have vertices of degree higher

a)

b)

c)

Figure 3. a) A building footprint (Anapproximately orthogonal polygon).
d)b) Input polygon & Shrinking
edg7 pt8
pt3 edg3 pt4
pt7
polygons (blue) moving inward,
edg4
edg2
edg8
parallel to themselves.
edg6
Node1
pt9 edg9
edg1 pt2
Node5edg5c) Input polygon & Shrinking
pt1
pt6
pt5
polygons: Line segment’ events are
Node6
Node2
considered. d) Straight skeleton &
Node7
Node3
monotone polygons with an acute
Node4
Node8
angle. e) Rectified monotone
polygons by ‘Line segment’ event.
edg11

論文 R37e)
pt3 edg3

pt7

edg4

edg2
edg1
pt1

edg7

pt4

Node1

pt2

edg5

pt5

pt8

edg8
Node4

pt9 edg9

pt6
Node5

Node2
Node3

Node6

edg11

－ 199 －

than three, introduced by simultaneous events at the sameprocess, then the line segment is disconnected from a body

location. However, in single or double precision floating point

skeleton. Therefore, the detached line segment leaves at least

calculation for the position of the node, it is quite rare for four

one vertex for next shrinking process. Examples are shown inor more vertices to reach exactly the same point simultaneously.

the line segment between Node2 and Node5 in Figure 4(c) andTo rectify monotone polygons to be appropriate shape for roof

Figure 5(b); one node whose interior angle is flat will remainboards, in our system, if multiple edges collapse into a certain

for the next shrinking process so as to create the border ofarea considered as a point for a node, then they are consideredmonotone polygons. For example, in Figure 4(c) & Figure 5(b),to converge into the same point and the node is formed.

four edges (edg11,12,14,15) propagate into Node2, and two
overlapping edges (edg12,14) turn into the line segment

4.3 LINE SEGMENT EVENT
Since three edges usually sweep into a node, very often thisincident to Node2 & nearby Node after edg13 disappeared.

causes a quite acute angle shape that is not appropriate for roof

will be extended, ending in Node5 as shown in Figure 5(a);board shape shown in Figure 3. In Figure 3(e), pt5 propagates tothree edges (edg12,14,15) result in Node2, and three edges

join pt2 and four edges (edg1,2,4,5) propagate into Node2,(edg1,11,15) result in Node5 whose inner angle is quite acute,

whereas, in Figure 3(d), pt5 does not join pt2 and goes off

which is improper for roof board shape.

If a configurable range is quite narrow, then edge propagation

Node2, and three edges (edg4,5,11) result in Node4 with acuteangle shape.
This acute angle shape is also found at the figure of

4.4 MONOTONE POLYGON NODES SORTING
According to Aichholzer et al.4), the area divided by a straight

Eppstein et al.5), which uses perturbation techniques, replacing

skeleton will be a ‘monotone polygon’. To get the monotone

the high-degree node with several nodes of degree three,polygons, the set of the nodes belonging to each original edge

connected by zero-length edge. In our system, using thewill be sorted according to the ‘coordinate value of node vector

technique completely opposite to Eppstein’s perturbation, aprojections’ onto the original edge vector parallel to each‘Line segment’ event is proposed where edges are overlapped

original edge. These nodes are coplanar and will form roof

and collapse into a line segment instead of a vertex to avoid theboards for a 3D building model. However, for some polygon,

acute angle shape. This so-called snapping function is done bythis methodology does not work, resulting in self-intersecting

setting up a certain range for possible ‘Line segment’ events, inpolygons. Figure 5(c) shows monotone polygons for edg13 arewhich edges converge into a certain area considered as a line

self-intersecting. This is because the edge (connecting Node3 &segment, then they are regarded as converging into the same

Node4) of the monotone polygon is perpendicular to the originalline segment.

edge (edg13) of the polygon, and the nodes are connected in the

By a ‘Line segment’ event, two parallel edges converge
into one edge (line segment), and the convergent line segment isorder of ‘node vector projection’. The self-intersections are also
found at edg29 in Figure 5(c) and edg21 in Figure 5(b).

detached from a next shrinking body polygon. But if the

To avoid self-intersection, the azimuth angle of the nodes

detached line segment leaves no vertex for next shrinking

belonging to the same monotone polygon is proposed, where

論文 R37－ 200 －

the azimuth is the angle between each original edge vector and anode vector. The first node in the monotone polygon vertices
numbering is selected from the node with least azimuth, and the

Acknowledgements
This work was funded by JSPS KAKENHI; Grant-in-Aid for Scientific
Research (C) Grant Numbers 18K04523, 16K01045.

last node is the node with greatest azimuth, since the nodes near
the both ends on an original edge may wrap around both ends
for some monotone polygons, and wrapping around nodes may
not have simply increasing ‘coordinate value’. For example, in
Figure 5(c), the edge (connecting Node1 & Node2) of themonotone polygon is perpendicular to the original edge (edg29),
and Node1 & Node2 have the same ‘coordinate value’, resulting
in self-intersection at nodes sorting. Thus, the nodes at ends are
sorted by the azimuth angles. Then, the sorting of the nodes isfound successful in a complicated shape polygon such as theones in Figure 1 and Figure 4(c).
5. Conclusion
Our system does not always aim at creating current 3D town
models (e.g. 3d models in Google Earth) but generating hippedroof building models. The roof models created by the straightskeleton computation are limited to hipped roofs, since shortedges are disappearing when shrinking process proceeds andlong edges are remain as the ridges of the roof shown in Figure
2 & 4. When creating hipped roof models, our system instantly
generates them from building polygons.
The advantage of our generation system is that our 3D
building models created can be utilized for architectural design,i.e., BIM, while 3D models created by procedural modeling are
not solid models but surface models which are to be converted
into geometric primitives (CSG) when they are used forconstruction design. In this paper, the straight skeleton

References
1） Sugihara K., Hayashi Y.: 2008, Automatic Generation of 3-D
Building Models with Multiple Roofs, Journal of Tsinghua
Science & Technology, 13, 368-374.
2） Sugihara, K. and Kikata, J.: 2013, Automatic Generation of 3D
Building Models from Complicated Building Polygons, Journalof Computing in Civil Engineering, ASCE (American Society of
Civil Engineers), 27(5), 476–488.
3） Sugihara K.: 2012, Straight Skeleton for Automatic Generation of
3-D Building Models with General Shaped Roofs,
Communication Proc., WSCG'2013, 175–183.
4） O. Aichholzer, F. Aurenhammer ,and D. Alberts, B. Gärtner: 1995,
A novel type of skeleton for polygons, Journal of Universal
Computer Science, 1 (12), 752–761.
5） Eppstein David, Erickson Jeff: 1999, Raising roofs, crashingcycles, and playing pool: applications of a data structure forfinding pairwise interactions, Discrete and Computational
Geometry, 22 (4): 569–592.
6） Yoav I. H. Parish, and Pascal Müller: 2001, Procedural modelingof cities, Proceedings of ACM SIGGRAPH 2001, ACM Press, E.
Fiume, Ed., New York, 301–308.
7） Pascal Mueller, Peter Wonka, Simon Haegler, Andreas Ulmer, Luc
Van Gool.: 2006, Procedural modeling of buildings, ACM
Transactions on Graphics 25, 3, 614–623.
8） Helda M., Palfradera P.: 2017, Straight Skeletons with Additive
and Multiplicative Weights and Their Application to the
Algorithmic Generation of Roofs and Terrains, Computer-Aided
Design, Elsevier B.V., 92, 33-41.
9） Tom Kelly, Peter Wonka: 2011, Interactive Architectural Modelingwith Procedural Extrusions, ACM Transactions on Graphics(TOG), 30 (2), 24-41.
10） Nianjuan, Jiang, Ping, Tan, and Loong-Fah, Cheong: 2009,
Symmetric architecture modeling with a single image, ACM
Transactions on Graphics (TOG), 28(5)computation optimized for automatic generation of 3D roof
model is proposed by adding ‘Line segment’ event besides theconventional events, and ‘monotone polygon nodes sorting’ bywhich self-intersecting monotone polygons are not formed.

論文 R37－ 201 －