Wednesday, March 04, 2009
that straight skeleton again
The straight skeleton is an algorithm that takes the floorplan (bird's eye view) of a house and produces the roof shape. Each edge of a polygon is moved inwards, in the direction of it's normal, tracing the intersections between the edges (gutters and crests) as they shrink in. Raising Roofs, Crashing Cycles, and Playing Pool (doi | web | Eppstein, Erickson | 1999 ) is an excellent introduction to the skeleton, even if the O(complexity) bits can be ignored on the first reading. For those looking for a decent implementation of the unweighted skeleton, I point ya'll to the masters of robust implementations at CGAL. [edit:] My floating point implementation of the weighted skeleton is here.
This data structure has always haunted my work in urban modeling. As an undergrad it took me a few weeks to understand fully and implement, and even then I kept running into nasty numerical issues. The data structure was described for the first time in 1995, but there's a been a fair bit of literature on it's implementation and computational complexity.
The straight skeleton was first described quite recently in A Novel Type of Skeleton for Polygons ( doi | pdf | Aichholzer, Alberts, Aurenhammer, Gärtner | 1995 ) as an alternative to the medial axis, but with straight edges. It is introduced as "that roof shape". It also points out that straight skeletons are unique, but as Eppstein's paper shows they are quite chaotic - small changes in the input or decisions made can lead to large changes in the output. There are assorted uses for it, beyond the obvious roofs in procedural urban geometry, you can even morph polygons by morphing their skeletons!
This algorithm took me a long time to implement (just getting back into the swing of coding, and picking up the equivalent of a couple of graphics courses in linear algebra along the way). It was implemented to define the weighted straight skeleton (see Eppstein's paper again) rather than just the straight skeleton. This was basically done in the method given by Straight Skeleton Implementation ( pdf | Felkel, Obdrzalek | 1998 ), although I have several issues with the paper, I'll write about that elsewhere (maybe a bathroom wall).
My first attempt at this was for Sity, (the results are here). It was a long time ago, but the algorithm gave me real trouble. I was basically using using a Jordan curve algorithm to detect line intersections, and tweaking it a little bit so that weighted skeletons could be created. I had endless problems with collision rays escaping from their bounding boxes (I was up to four rewrites). In an orthogonal environment, you very often get 45 degree bisectors targeted against square corners. This mean that it's a disaster if neither of the edges adjacent to the corner catch the ray. Because of the nature of floating point arithmetic, this is fairly likely when repeated a few hundred thousand times.
The next, more recent attempt at implementation, shrinks the outline (moved each vertex in the direction of it's bisector) a number of times, until termination. Figuring out where termination is a bit of a problem - my first reaction was to union the the resulting outline with itself and remove any negative areas (if the outline runs in the opposite direction to the original, it's area is, by convention, considered negative). The problem with this is that several intersections can happen within one shrinkage (question mark, above), making a mess of the mesh (and so it's union). In fact, since an arbitrary number of these events can happen in one shrink step, and we need to sort them out in order, this problem is just as complicated as the original! (doh) So not such a good approach - except maybe a time saver for the concave case :-
So I went back to Felkel's bisector collision with edges approach . My previous problem of dealing with these escaping bisectors could be dealt with by converting the n-sided outline shape, into n/2 planar slices through the completed skeleton. The following animations show a polygon with (dark) rainbow coloured edges, and the location of intersections with a slice collinear with a given edge (with a thick red edge). The intersections are in light rainbow colours:
I thought this approach would be successful, so much so that I made a nice series of images explaining the details.
But this approach turns out to be very fiddly. As the skeleton is constructed from the floor upwards we always remove edges (never adding them). Each time an edge is removed two other edges come together (unless we're at a peak). This means removing a edge from each 2d projection and re-running many intersections, which is a lot of book keeping (and it makes the already bad complexity even worse). Another complication is the need for a 2d representation for 3d faces (to represent parallel edges), this was done, but wasn't very tidy. In the end I learnt a lot about computational geometry, but it took ages (my current version took less than a day for rewrite). And the benefits of doing this way - more watertight boundaries - are more simply dealt with in 3d.
So...next time children you'll need an empty washing liquid up bottle and I'll show you how not to shoot both your feet at the same time while constructing the weighted straight skeleton.