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.

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 local changes that take place during an event must be consistent on a global scale.

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.

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.

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.

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.

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:

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.

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.

###

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.

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).

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.

###

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:

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.

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.

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.

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.

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:

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''.

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.

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.

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

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.

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 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 .

- 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.)

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.

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.

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 (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.

### 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.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.

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).

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.- 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.

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.

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.

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.

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''.

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.

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.

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

Huber figured this out in "Planar Matchings for Weighted Straight

ReplyDeleteSkeletons": https://doi.org/10.1142/S0218195916600050