Tuesday, October 06, 2009

accelerating the straight skeleton

I've been investigating ways to accelerate the straight skeleton computation. In my implementation, the main problem is finding the next point where three sides of the "roof-shape" collide. In the below there are two such points ((abc) and (adc)), but the complexity becomes a killer on larger shapes. Edges are removed, and added (by some of my contortions to the algorithm) as the algorithm continues.


0) Naive! Best start at the beginning, what my code does at the moment is intersect all pairs of adjacent edges against all other edges. This takes lots of time (n2) and space (n2).

1) Conga Lines. As Eppstein points out(Raising Roofs, Crashing Cycles, and Playing Pool (doi | web | informal | Eppstein, Erickson | 1999 )), a conga line data structure provides a great way to track closest pair problems (not the only way tho!). In this situation the pair is made up from a bisector (two adjacent edges that collide to form a ray) and a quad (the face that the bisector collides with). The "distance" between these two is the height at which they intersect.

The key observation is that we can form log(n) set of chains of things. Within each chain each object is chained to it's nearest object. Then inserting an item takes O(n log (n)) and removing takes O( n log^2 n).

2) Divide and conquer. Given the (below, left) dark grey input shape (and blue corners).


We can subdivide it into a set of cells, each of which is a weighted skeleton, such as the one shown in blurry green. The image on the right shows one such cell in 3D. Interior edges have a zero (vertical) weight, shown in red. We can then find the next event by locating the lowest collision within each cell. Each of the above cells has only two edges, but I'm not sure that's an optimum number.

When events hit the boundary of cells, they are propagated into the neighbouring cells. If there are too many edges in one cell then the cell gets subdivided. This means we only have to consider local collisions when calculating the skeleton, and maybe pushes another log(n) into the complexity for the straight skeleton (I'm still trying to figure this one out, along with the fact that the weighted skeleton is ambiguous...).


  1. Anonymous05:43

    i'm Rene an engineer from the Nederlands.
    The solution of Eppstein is wrong it takes to long to generate a roof.
    I made a roofengine for AutoCAD,
    which can generate a(complex) roof with less intersection calculations (in realtime).

  2. Eppstein's solution is right, but there are probably faster algorithms still to be discovered. His work runs easily quick enough for real time editing on realistic roof-data.


    Your work sounds fun, do you have video of your project Rene?