## Thursday, June 15, 2006

Here's my first blog video! WooWoo... Its my debugging render of the straight skeleton algorithm running on a non-regular octagon.

• Yellow is the output skeleton

• The red arrows show the list of active points still to be processed

• Green arrows show the current edge assignment of each point (eg which two edges collide at this points bisector)

• Blue arrows show the bisector of each point

Its only a maya playblast - I have no idea how to render colour in maya when you only have Vertex colours(Edit Polygon-> Colors-> Apply Color, but only grey when you render). But the time spent putting this together has already saved itself in debugging time. I've spotted two subtle but critical flaws in previous versions.

Again, but with weighted edges (a camp skeleton). The weight determines the speed or steepness of each edge. Note the bottom left where the skeleton goes outside of the base polygon due to a negative weight.

It even works with edges with 0 speed (as long as one edge has speed). Setting one edge to have a 0 speed allows a cross-gabled roof. Setting all but one edge to zero speed creates a flat-roof, with all the other sections vertical. The plan is to merge these vertical sections into the walls to create gabled rooves with windows in the gable.

This evening (took the afternoon off):

To convert the skeletons (yellow lines in the above animations) to solid roofs(hehe, had to look up the plural of roof there), we have to traverse the 2d heap of lines in some way. All the papers I read describe a method of using the minimum interior angle in a 2D projection, however this wont work with the vertical walls as the 2D projection will have the roof ridges ontop of the vertical 'wall' edges. By keeping track of the direction of each line in the skeleton (so we know which way is uphill) we can start from the two known corners of an output face (adjoinging edge points on the input shape) and work our way up the edges until they meet. Its important to ensure that the two sides of an output face dont miss each other, so we step them -
1. the first side moves up one edge on the output face
2. the second side moves up edges until it reaches the same corner as the first side (or very close, if so then done) or finds a corner higher than the first.
3. the first side moves up edges until it reaches the same corner as the second side (or very close, if so then done) or finds a corner higher than the second.
By storing all the pairs of edges in a hash table, we have a data structure that will take a lower point and return the next point up on a roof edge (edges only merge as you move upwards, they dont split) and be hot-turd fast (not that speed has anything to do with this).

The difficult thing here is dealing with the very small lines between output vertices in regular shapes, such as the top of a square based pyramid. Sometimes tie-breaking is required when, while climbing the two edges get to a common height that isn't the same point.

Assigning directions to lines is done arbirarily when the line is level. It is of little consequence which way the line is traversed.

The irregular skeleton above comes out easily of this:

Tommorow the plan is to fix the bit that converts the skeleton to 3D so it works with regular shapes. Then work on getting the skeleton to work on concave shapes. This means testing each bisector against each opposing face to find if it ever splits it before intersecting with any of its neighbours. That'll probably take the last two days of my (monday-centric) week. I was hoping to have a day to work on getting the base non-planar, but as ever on this project its time to move on...