# Generating Buildings From Footprints

This is a collection of scrips i have written for extracting buildings from building footprints, for a project in the Computer Graphics course at KTH 2014.

It is written in C# for Unity 3D.

# How it works

It uses Moores-Neighbor Tracing algorithm to get all the boundary points of the footprint, then constructs a plane from them, and drags it out into the 3rd dimmension.

But it is not good to simply cunstruct a plane directly from these points, so I use another method to eliminate the *non-importan* points.

## Eliminating Boundary Points

From using the Moores-Neighbor tracing algorithm we get an ordered list of boundary points.
Now we want to pick out the most *important* points, from which we will construct a plane.
This is the hard part and might be a little tough to follow.

Let *Pn* and *Pm* be two boundary points where *n < m*, meaning *Pn* comes before *Pm* in the ordered list of boundary points.

Let *L = Line(Pn,Pm)* be a line between the points *Pn* and *Pm*, and *distance(Pi, L)* be the distance between the line *L* and some random boundary point *Pi*.

Now we can define the function *errorsum(Pn, Pm)* as
*errorsum(Pn,Pm) = distance(Pn+1, L)+distance(Pn+2,L)+...+distance(Pm-2,L)+distance(Pm-1,L)*

In this image *p1* and *p2* are *Pn* and *Pm*, *d1* to *d3* are *Pn+1* to *Pm-1*, *L* is *Line(Pn,Pm)* and the red lines are *distance(Pi, L)*

Now to pick out the most important points pick a value for the threshold, e.g. 7, and do the following

- Pick the first point and call it
*P1*. - Define the next
*good*point,*P2*, as the last point in the list for which it holds that*errorsum(P1,P2) <= threshold* - Add
*P1*to the list of*good points* - Rename
*P2*to*P1*. - Repeat from
*2.*until you hit the end of boundary points.

Now we have a list of *good points* from which we can construct a plane, add some walls and a roof and ** poof ** it's a building.

# Results

This is an example of a building footprint map:

After extraction we get this city!

And this is the effect of different values for the threshold

You can see that the lower the threshold is the more points we get in our plane.

# Problems

Before using these scripts you should be aware of a few problems

- This method will not generate buildings with holes.
- The footprint map should preferably be black and white.
- Because of the way I piece together the planes some buildings, like L-shaped once, will look weird if the threshold value is to high.
- The buildings don't actually look so good :P