49 
all 
en 
ID 
of 
ns 
)W 
of 
ay 
ch 
nt 
h. 
;ir 
er 
to 
le 
>y 
its 
to 
re 
le 
Figure 5. Parallel line segments (green) form decomposition 
lines (red), rendering short segments in between (orange) 
unnecessary. 
Under the general assumption that ridge and eaves lines should 
strictly run horizontally, many roof shapes require the ground 
shape of cells to be trapezoids or rhomboids. Otherwise not all 
roof faces will be planar and must be split into triangles to form 
valid solids. Figure 6 shows an extreme example of a cell with a 
Berliner roof shape where none of the four sides of the ground 
shape are parallel. The middle face of the roof must be split into 
two triangles, which is generally not acceptable and should be 
avoided if possible. Due to the averaging process, the set of 
resulting decomposition lines are not guaranteed to be parallel. 
We therefore adjust the decomposition lines slightly so that 
parallelism and rectangularity are enforced for pairs of 
decomposition lines with small directional deviations. The same 
Berliner roof shape of Figure 6 with a trapezoid ground shape 
results in a valid solid after adjustment. 
Roof Shape Determination 
Now that a cell decomposition of the footprint is available, the 
parameterized roof shapes of all cells need to be found. We do 
this by examining the normal vectors of all points inside the 
same cell. As point normal vectors are usually not given in 
surface models, they first have to be generated. If the surface 
model is structured as a grid, we compute the normal vector of 
each point from the eight triangles fanned around it and average 
their normal vectors. However, if the raw data is available in 
form of an unstructured point cloud, we estimate a point’s local 
plane of regression from its five nearest neighbours and take the 
resulting surface normal vector. 
For the construction of the building’s roof, we classify the roof 
shapes that we use in our approach into three types: basic, 
connecting and manual shapes. Whereas the shapes of the first 
two classes can be determined in an automatic process, the last 
Figure 6. Extreme example of a Berliner roof primitive with a 
non-parallel before and a trapezoid roof shape after adjustment. 
Once the decomposition lines have been generated, a rectangle 
approximately two times the minimal bounding rectangle is 
taken and split by these lines, forming nonintersecting cells in 
the process. Then the cells are compared with the original 
footprint, and the ones with a low overlap value are discarded. 
Large cells assure that this classification fails only in few cases. 
Figure 7 shows an example cell decomposition of a given 
footprint. Cells with a low overlap with the original footprint 
were discarded in the process. The four “horizontal” lines are 
pair wise parallel, whereas the five “vertical” lines are all 
Figure 8. Flat, shed, gabled, hipped and Berliner roof shape. 
As not all houses have only one section, there is a need to 
connect the roofs of the sections with specific junction shapes. 
Figure 9 shows a small selection of connecting roof shapes. 
/ \ 
Figure 9. Examples of connecting roof shapes.