Rendering Rooftops – Triangulating polygons

Now that we have the walls complete, I thought it would be a good time to move onto rendering the rooftops! Instead of having to triangulate the polygons myself, I looked online to find a triangular to do it for me. I stumbled across an old flipcode article that had a triangular in it. I simply ported this to objective-c to allow me to use it inside my project (I could have also compiled it as an objective-c++ class).

The triangular is pretty simple to use – it expects the caller to call the “Process” function passing in the polygon as a list of points, and an array to output the results. The function returns a boolean to let the user know if the triangulation was succesful. The output is a list of 2d points which are in the format of a triangle list. This makes it trivial to convert to vertices and then draw using the GL_TRIANGLES primitive type.

Something to watch out for, and not mentioned in the article, is that the polygon’s should NOT be closed – the first and last point in the polygon should not be the same. To triangulate the polygons as returned from open street map, you must exclude the last vertex when passing the polygons to the triangulator. The results were not perfect, there is a few polygons which fail to triangulate correctly – there are shown as the pink coloured rooftops in the screenshots. At the moment the results are good enough for me, and I will investigate the other issues later on.

Hopefully this post will help someone looking to quickly find a way to triangulate 2D polygons!

The screenshots below show the results so far! Next on the list is to calculate the normals for each vertex, so the buildings can be lit properly.

IMG_2082 IMG_2081 IMG_2080



Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: