degeneracy in the weighted straight skeleton

The following is something I wrote for an internal progress report. A more complete version is in my finished thesis. It describes a variant of the weighted straight skeleton that allows inwards and outwards moving edges. It follows my thoughts on the subject until I get stuck. (It was created with latex2html, which didn't do a very tidy job of conversion, sorry!). Other blog posts on the skeleton can be found here.

the straight skeleton
The straight skeleton (SS) is a 2d graph generated from an arbitrary polygon. Each of the edges of the polygon move towards the interior at a constant speed. Occasionally the topology of the polygon changes as an edge shrinks to zero length, or similar.
The movement of the corners of the polygon traces out the arcs (edges) of the graph. This 2d graph may be interpreted as a 3d roof to allow easy comparison between the standard, unweighted straight skeleton and the more complex weighted straight skeleton (WSS), introduced later.
In this section we introduce the SS using the roof model over the domain of real numbers. Later we will discuss an implementation that is robust over a floating point system.

Figure 14:
Straight skeleton terminology.

To distinguish between the under constrained term "polygon'' and a similar structure with additional constraints, we introduce a plan, Fig. 14. A plan is a planar partition (a straight line planar embedding of a planar graph) that divides a plane into a finite inside and infinite outside regions.

A plan has corners and edges, these are embedded in a plane parallel to the xy-plane (the ground plane), so that all corners of a plan have the same z (height) value. We require that the boundaries of a plan are a non-intersecting collection of oriented polygons. The inside is on the left-hand side of each oriented edge. The loops of edges are typically oriented counter-clockwise, but polygons describing holes are oriented clockwise. Additional bounded regions may be recursively located inside a hole.
A sweep plane that rises vertically from the input plan. This sweep plane defines an active plan that defines the cross sections of the output. The output of the system is a series of faces that make up the 3d output, the shell. The edges of the faces are named arcs after Aichholzer et al..
As the SS is constructed, the sweep plane rises and the active plan shrinks. In the unweighted straight skeleton, all the edges move with a constant speed towards the interior of the polygon. The movement of each edge over the active plan defines a plane, the direction plane in 3d. Each face lies in one of these direction planes. At all times in this process we must ensure that the active plan remains remains well formed. That is:

• The enclosed region remains to the left of every directed edge.
• No edge intersects another edge, except at the corners.
• Every enclosed region is has a finite, non-zero area.
• There may be a finite number of enclosed regions, that is zero or more.
• No parallel, overlapping edges exist .
  

To ensure these properties remain intact, we detect when more than two edges intersect and we make topological changes to the active plan. Fig. 15 shows that if we do nothing, the plan may becomes badly formed. We call these events, Fig. 16. Edge events occur as the length of an edge shrinks to zero. When an edge shrinks to zero the direction planes defined by three consecutive (linked by corners) edges collide (Fig. 16, 3). Split events take place when two adjacent direction planes, and one non adjacent direction plane collide (Fig. 16, 2). These split the region bounded by the active plan into two parts.

Figure 15:
Left: the anti-clockwise oriented input plan. Middle: The active plan at a split event (orange). Right: Without a split event, a portion of the active plan become badly formed. There are self-intersections at a and b, and the red region is defined by a clockwise loop; That is, the edges define an unbounded region outside the red area.

Figure 16:
Left: the straight skeleton is given by arcs (blue lines) tracing the verticies of a shrinking polygon (black lines). Each edge moves with a constant speed towards the interior of the polygon, and as it does the topology of the polygon changes in several different ways (dark green lines), during events. Right 1-3: The skeleton is calculated as a sequence of these events. Right 4: We can view the skeleton as a 3d structure with polygonal faces. The final skeleton, without the intermediate shrinking stages is shown at the bottom of the figure.

Figure 17:
Split (b) and edge events (a) that occur as a polygon shrinks.

The local changes that take place during an event must be consistent on a global scale.

• The plan must remain well formed globally.
• As the edges involved in the event continue to move across the active plan immediately after the event, they must not intersect each other. (This is made easier by the sector property introduced later.)

Given a ``random'' or irregular input plan these two (split and edge) events are the only features we are likely to see, Fig. 18. This is because the skeleton of irregular polygons do not have events where more than 3 faces meet at one point. We can describe these in terms of the local area around the edge intersection point, Fig. 17. Here we see the local active plan region before, during and after edge events (a), split events (b) as well as peaks (c & d).

Figure 18

However in contrived degenerate situations, we may see more than three edges colliding at a point, the previous work leaves these types of line intersection badly defined, Sec. 3.2. We may see several connected edges collapsing, (Fig 19, a) or multiple split-like events occurring at the same time (Fig 19, b). We note that in all situations, the region collapsing at any time is locally topologically equivalent to a disc immediately before the event. The disc may be bounded on some sides, and unbounded on others. This collapsing topology in SS events is always a disc as other features that may create a higher genus enclosed shape around the event could only away recede from the event as the sweep plane rises.

Figure 19: In degenerate situations, more than three edges will collapse at one time (a,b & e). We also note that sometimes the active plan collapses to a loop of two (c,e & e). We show these coincident edges as curved lines, with asterisks.

Later we will describe a general intersection event which combines edge and split events, as well as the more general situations.

Fig 19, c,d and e, shows an example of the active plan becoming a region with only two edges and zero area. A more complete example is shown in 20. After all the events at a certain height parallel edges may cause the active plan to become partially or entirely composed of these zero-area regions. We resolve this, following Felkel et al., by using the loop of two rule. Whenever parallel edges are adjacent before an event we ensure that after the event they are connected together, Fig. 19, c,d and e, ``during''. After creating such an connection we then check the loop to see if it has only 2 edges if so it is removed from the active plan, Fig. 19, ``after''. This ensures a global consistency of the plan, given only event processing on a local information.

Figure 20:
A more complex example of a straight skeleton, left, that creates a zero area plan, right. Note that the curved line segments are in reality straight, but drawn curved to represent the topology.

Another interesting case occurs when adjacent edges in the active plan become consecutive, the parallel consecutive edge (PCE) problem. Fig. 21 demonstrates such a case. Existing work leaves it undefined as to whether two edges that become colinear at a later point in the execution of the algorithm create a single face (the merge solution), or remain multiple faces (the separate solution. It is interesting to note that the same work seems to exclude such PCE in the input, however there is no easy way to tell if parallel edges will become consecutive as the skeleton is constructed. By symmetry we would expect to see PCEs in the input computed using the same solution.

Figure 21:
Several borderline cases where we may wish define more rigorously what constitutes an edge and what constitutes a face, the PCE problem. Left: The merge rule, middle: the separate rule, right: when there are PCE in the input do we apply the merge or separate rule?

If two PCE are combined using the separate rule (Fig. 21 a, in contrast to b) then the assertion that every input edge creates a face is correct, but then it is non trivial to describe this new arc between these two adjacent faces. We could define a special case for this situation, which defines the vertex to move perpendicularly to the edges involved, but this seems inelegant. However if we apply the merge rule (Fig. 21 b) then the assertion that one edge becomes one face is wrong.

We can generalise the split and edge events into a generalised intersection event (GIE). There is no particular reason that these events must be solved in this manner - many other ways to ensure the plan remains well formed can be imagined - however the GIE is consistent with the rules for the active plan, and with the intuition that the active plan always shrinks.

We begin by defining chains of edges that are involved in an event, Fig. 22. A chain is a list of consecutive edges that are colliding at the event. They are ordered corresponding to the edge's direction. These form the partial boundary to our possibly bounded topological disc region of the active plan that is collapsing at the event.

Figure 22:

Two regions of active plans corresponding to Fig. 19 b on the left and Fig. 19 a on the right. We can group the edges involved in an event into chains (red, yellow and blue edges) by asking which edges are consecutive.

Figure 23:
As three chains approach an event (a, orange), we can imagine their eventual topology by viewing the active plan if no event takes place (c). We observe that the last edge in the previous chain and the first edge in the following chain become adjacent, also that every chain is split into two (e).

In the case of the SS we can order the chains themselves around the event's location, Fig. 23 d. That is the chains are ordered in a cyclic list. Immediately before the event the location of the event is always within the region bounded by the active plan. We can note that after an event the last edge in the preceding chain, and the first edge in the following chain become adjacent, Fig. 23 c and e.
Therefore to process a GIE:

• Intra chain step: Within each chain, any edges in the middle (not the first or the last edge in a chain) shrink to 0-length and are removed from the active plan. This leaves only chains of length one or two remain.
• One chain step: Chains of 1 edge are split at the location of the event. All chains are now of length 2.
• Inter chain step: We connect adjacent chains in the cyclic list, that is we connect the start of the last edge in the previous chain to the end of the first edge in the following chain. This splits each chain in it's middle. All chains are still of length two.
• Loops of two step: Regions of the active plan defined only by a polygon with two edges (of zero area) are removed from the active plan.
• PCE step: We resolve newly parallel consecutive edges according to the merge or separate solutions.

the weighted straight skeleton

The weighted straight skeleton (WSS) is a variation of the straight skeleton. Each edge is allowed to move with an independent speed towards the interior or exterior of the bounded region as the sweep plane rises. As I hope later portions of this document will prove, the WSS is a useful tool for a number of different modeling applications. The WSS lies at the heart of the procedural extrusion modeling system introduced in Sec. 7.3.
The construction of the WSS is identical to the SS for nearly all events. There are, however, a number of cases that arise that are poorly defined. These lead to the conclusion that there are a large class of WSS-like constructions which are similar, except in their behaviour when certain degenerate events arise. We have already seen one example in the case of the SS, the parallel consecutive edge situation, which can be solved using either the merge or separate rules. These degenerate cases appear in two classes - line degeneracies, of which the PCE is one, and point degeneracies.

Although degenerate cases do not occur frequently, it is hard to defend the use of the WSS when a complete algorithm for all possible plans cannot be given.

To enable independently weighted edges we must introduce another property of every input edge, theta, an angle which measures its slope towards the interior of the polygon. We use the terms angles and weights interchangeably. Because the edges may not move with infinitely fast speed, we limit theta such that -pi/2 is less than theta which is less than pi/2.

Figure 24:
In the WSS, every input edge is also associated with an angle that defines the slope of the associated face.

The WSS enables many more shapes to be expressed. For example the active plan can grow, as well as shrink. This property means that certain WSS may not terminate when calculated, that is they continue to grow to an infinite area. It is very hard to determine if a given WSS will terminate if it contains any values of theta greater than 0, without attempting to calculate the skeleton itself. The shells of all possible WSS are are superset of all possible SS. The possible WSS events are also a superset of the SS events. Given a random input plan, we are likely to see only events involving three edges again. However the degenerate cases become much more intricate.

line degeneracies

The parallel consecutive edge problem of the SS, can again be observed in the WSS. This may occur in the same manner as the SS, Fig. 21. The edges which cause the degeneracy no longer need to parallel so there are a larger range of input plans that lead to PCEs in the active plan, Fig 25. This degenerate case arises when two (or more) neighbouring edges in the active plan become colinear on the same side of a region. This happens, for example, when edges previously separating the colinear edges are eliminated. We may also arrive in this situation if the input contains PCEs.

Figure 25:
A plan that leads to a PCE, a. We must choose between the red (middle) or yellow (right) faces to dominate.

If the two neighbouring and colinear edges bound different sides of a region the output is an arc representing a ridge and the computation proceeds as normal, assured that at the opposite end of the ridge the two edges will collide again via the loop of two rule. This is not an degenerate event and we can distinguish the regular ``roof ridge'' case from an degenerate event by making use of the fact that we use oriented edges to describe a plan. When the edges have the same orientation (they bound the same side of a region) we are not able to determine the direction of the output arc, Fig. 25.
We may look to situations where the edges are nearly parallel for guidance. As the angle between the edges approaches 180 degrees from different directions, we get suddenly different results. Either one or the other edge will be predominant. This singularity means that the limiting case is of little help when resolving the degeneracy.

The individual degenerate events need to be solved consistently from a global standpoint, Fig. 26 middle. We suggest the approach of choosing one edge to replace the others, Fig. 26 right. There are situations, similar to the SS PCE where multiple edges with the same weight at the same place, Fig. 27, left and right.

Figure 26:
A PCE that requires global coordination to resolve. If the event at a, and b do not coordinate, we may end up with non-enclosed regions on the plan (middle). We pick one edge globally to dominate, right.

This requirement for a global operation sets the WSS apart from the SS which can be defined using local operations, such as the loop of two rule.
Our strategy to resolve this degeneracy replaces the set of PCEs with a single edge. After collecting all colinear events which occur at a single height, we use a ordering derived from the angles of the edges to select one or more edges with the same angle, Fig. 26 right, to replace the others. We then use the merge solution to combine these faces to one, Fig. 27, middle.Typical orders are volume maximising (lowest theta first in ordering) or minimising (highest theta first in ordering).

Figure 27:
A WSS PCE, that is very similar to the SS PCE, except that global coordination is again required. Middle: we use the merge solution to combine faces with equal angle. Right: There are many alternate consistent resolution systems apart from the one presented here, that may use variants of the separate solution.

This PCE resolution method is one of a large number of alternatives. We can imagine other schemes, Fig 27, right, but find ours the simplest practical approach.

point degeneracies

If all the edges are moving with a positive theta, the the SS GIE introduced in Sec. 4.1 is still suitable. When this is the case, the collapsing area is again locally equivalent to the topological disc. However there are a complex set of increasingly degenerate events, Fig. 28, shows one possible event with many edges colliding. Here we can see chains of edges representing bounded, as well as unbounded areas, loops, and enclosed chains (Fig. 29), all colliding at one point. Fig. 39 gives an example of the GIE failing to process an event.

Figure 28:
Left: The active plan just before an event. A complex set of chains are collide at a single event (orange). Right: after the intra-chain step and one-chain step we are left with a simplified topology. Note that the curved edges marked with an asterisk represent the topology of two colinear edges.

Figure 29:
We say the chain a encloses chain b, since b is on the interior relative to the intersection point (orange).

We wish to have a consistent solution to these degenerate events, Fig. 30. That is, the plan remains is well formed (as defined above) after the event, and remains well formed until the subsequent event takes place. We have been unable to find a elegant solution to the problem. What we present here is a ``engineered'' solution that is as consistent as possible with the existing definition of the unweighted skeleton. Other characteristics that we find desirable may include:

• Similarity to the straight skeleton.
• Consistency with the straight skeleton when all angles are a positive constant.
• Invariance to rotation of the plan. This is one of the properties of the straight skeleton, and it is desirable that it still holds.

Figure 30:
Above: four chains collide at an event (orange). The desired plan topology after the event is unclear. We must keep the input edges (red) in the same locations to remain consistent with the remainder of the plan. Below: there are many possible options for the topology change at the event, we show the active plan a time after the event for clarity. Some using existing edges, others create new edges (initially these new edges are zero length, but subsequently grow) during the event.

A set of arbitrary loops of edges in an active plan may form an event at a single location, Fig. 31, given the correct set of weights. Alternately the edges may be part of a larger event, as in Fig. 28.

Figure 31:
Degenerate events can occur such that arbitrary loops (nested or unnested) can collapse to a point. This is due to the inclusion of weights in the skeleton.

To simplify this situation is that we can apply the SS intra chain step and one chain step, Fig. 28 right, to remove edges that shrink to zero length. This includes the loops of edges; As they approach an event they shrink to zero length and area, and as such we may remove them from the active plan, and not consider them further in the event handling.

We now define several descriptions of the WSS that help us. The major axis, approaching edges and the sector properties.

The major axis defines the direction that all chains of length one take. There may be more than one chain of length one in the WSS, Fig. 28. We can show that it impossible to have more than one orientation of 1-chains in a single event, Fig. 32.

Figure 32:

At an event (orange) we may not have more than one orientation of chains of length one. If this were the case (above), there would be a point (red) which the 1-chains (green and blue) arrived at before the event. There would, therefore, have been another (red) event which combines these edges before they arrive at the first event (orange).

At an event all the edges involved in the collision approach the location at an angle defined by the edge's current orientation. Fig. 34, left, shows the orientation-ordered points for Fig. 28. Any edges that do not approach according to their angle must have been removed by an earlier collision, Fig. 34, right. This property is known as the GE approaching edges property. This refers to the fact that the angle between consecutive edges around an intersection is equal to, or greater than, zero.

The situation that complicates further processing is approaching edges with the same angles. That is when two parallel edges, with different directions approach an event from the same side. The area between these edges approaches zero near the event, and should be removed by the loop of two rule. Therefore we remove these adjacent, parallel edges with the same orientation at the event, Fig. 33. After we remove these lines, we can say that the event has the G approaching edges property as all the angles between adjacent approaching edges are greater than zero.

Figure 33:
After the intra-chain step we remove all the zero area chains, giving us the topology shown (top, left). We show the chains just before the event for clarity. The black lines connect (asterisked) edges which would become adjacent and parallel at the event. We convert these pairs of edges into single chains as shown. We either use the interior bias (top right) or exterior bias (bottom left). After the corresponding events at remote sites, we will remove these chains using the loops of two rule (bottom right).

To remove the edges, and keep the global-consistency property defined above, we must make a local choice, that is globally consistent, Fig. 33b. In a similar manner to the loop of two rule in the SS, we connect these pairs of adjacent lines. At the other end of these parallel edges, another event at the same height must make consistent choices, such that we never have two coincident, overlapping, edges in the active plan, Fig. 33.

Figure 33b:

Given a plan (top left) that leads to a number of events (top middle, red blue and yellow circles) at the same height, which share a single edge (top middle, edge a), there are several possible solutions. We wish to avoid creating parallel, colinear edges that will immediately self-intersect again (top right), that is we must have a globally coordinated solution. Where there are an odd number of parallel edges approaching an intersection from the same direction we introduce two globally consistent options; Interior bias (bottom left) or exterior bias (bottom right).

This situation presents another choice. More than two approaching edges can have the same angle, Fig 33. If there are an even number of such edges at one angle, the adjacent pairs of edges can be connected together. However if there are an odd number of edges, we have to choose which adjacent pairs to merge. Here we present two solutions:

• interior bias: The pairs of lines surrounding an interior region of the plan are removed.
• exterior bias: The pairs of lines surrounding an exterior region of the plan are removed.

Figure 34:
As the chains of edges in the WSS approach the event (orange) they become ordered (left). If this were not the case (right), they would have intersected during an separate earlier event (red).

Another interesting fact can be observed by not handling an event, Fig. 35. If we ignore the rest of the plan away from the event, we may see that after the event the chains remain in the same configuration. That is the intersections of any edges remain at the same angle relative to the event location, Fig. 36, until another event may occur. We can see that this is true by recalling that the edges move in a direction parallel to themselves at a constant angle. They also all pass through the event location at the event at the same time. Therefore any intersections between these lines also move with constant speed directly away from the event location, that is they keep the same angle. We refer to this property as the sector property.
The sector property can also be observed before an event, but after any preceding events. We can therefore view it as the trivial statement "between events, no events occur''.

Figure 35:
The plan (green, blue and yellow areas) undergoes an event (orange). The sector property states that relative locations of the active plan corners remains unchanged after the event (after 1, through after 2).

Figure 36:
After an event (orange), any intersection between two edges, such as a corner, remains at constant angle, alpha, relative to the event location. This gives rise to the sector property.

At this point we (I!) am unclear how to handle the chains further. In the examples we have tried, there is always a solution that does not introduce any new (initially 0-length) edges into the active plan during the event, Fig. 37. However there is no way that I have found of consistently calculating this solution topology. While some sort of search technique may give the correct answer, we feel that there is probably be a more elegant solution.

Figure 37:
Several example events and solutions that do not require 0-length edges to be introduced into the active plan. The chains (green dashed lines) are shown after the event (orange). The ideal solutions are shown in purple.

multiple union approach

Therefore I present an engineered alternative system that does introduce zero length edges, the multiple union approach. We analyse the topology immediately after an event. Note that by the sector property, this topology of the chains is independent of time after the event. Therefore we define an ordering over the chains so that they can be added or subtracted from the output topology. We use 2d geometry operations to build up this topology.
We start by ordering the chains into enclosed levels of chains they contain before the event, Fig. 38. The levels are enumerated from the location of the event, towards the deepest level. If the location (before the event) is inside (respectively outside) the region the output topology is initialised to be an inside (outside) region. Using the chains after the event, we iterate over the level, starting with the lowest-ordered level chains and add or subtract the union of all chains at that level them from the output topology, Fig. 40.

Figure 38:
The levels of two different events. Note how the location of the event changes the definition of the levels. A chain's level is one if it is adjacent to the event, otherwise it is one higher than the enclosing chain.

Because the angles between consecutive chains around a point is always greater that zero, we can be sure that the output topology will be compatible with the global active plan.

While this is one solution to this relatively rare problem, there are situations where the result isn't equivalent to the SS, and other quite strange topologies can occur, Fig. 39

Figure 39:
In the WSS, the GIE and the multiple union procedure have different advantages. In the top example, the GIE creates the best output, without 0 length edges, while in the bottom example it creates an undesirable inverted (red) region on now badly formed active plan. The multiple union procedure adds additional zero length edges in the first example, but always creates valid geometry (top and bottom examples). Compare to "perfect" manual results in Fig. 37.

Figure 40:
An example multiple union calculation. Given an input plan (a), several edges (marked with an asterisk) may collide (orange point). The edges involved can be split into levels, just before the event (b). After the event we can view the topology without intersections (d: green chains bound interior regions, white chains bound exterior regions). We can then use an union operation on those chains in the first level (e), before calculating the union of those chains in level 2 (f, yellow). We can then subtract the second level from the first (g). Because of the sector property, this new topology of edges will not intersect immediately after the event. It is also still compatible with the global geometry (h).