Saturday, December 17, 2011

Procedural Generation of Parcels in Urban Modeling

Eurographics 2012
C. Vanegas & T. Kelly, B. Weber, J. Halatsch, D. AliagaP. Muller
[ pdf | doi | implementation ]

teaser
We present a method for interactive procedural generation of parcels within the urban modeling pipeline. Our approach performs a partitioning of the interior of city blocks using user-specified subdivision attributes and style parameters. Moreover, our method is both robust and persistent in the sense of being able to map individual parcels from before an edit operation to after an edit operation - this enables transferring most, if not all, customizations despite small to large-scale interactive editing operations. The guidelines guarantee that the resulting subdivisions are functionally and geometrically plausible for subsequent building modeling and construction. Our results include visual and statistical comparisons that demonstrate how the parcel configurations created by our method can closely resemble those found in real-world cities of a large variety of styles. By directly addressing the block subdivision problem, we intend to increase the editability and realism of the urban modeling pipeline and to become a standard in parcel generation for future urban modeling methods.






Other resources:

Wednesday, September 14, 2011

siteplan source release

rect3075

I'm very happy to finally announce the long overdue release of SitePlan, my procedural extrusions implementation. There is information about the project here.

Please use the software! The source code is here

Here's a very clumsy demonstration video of me using the software:





And some of the kinds of things you can create if you invest a little more time.


50
With any luck I'll have the slides from Siggraph converted into video any week now...

Thursday, May 26, 2011

Zurich & Procedural Inc

I'm finally settled and interning at Procedural in Zurich for the Summer :) These guys are just about the only people commercial world of procedural urban modeling.


My first impressions of Zurich are that it has a lot in common with half-life...





again with the half-life zurich

Thursday, April 14, 2011

uk epsrc ict pioneers

A couple of weeks back I won the 'Transforming Society' award from the EPSRC's UK ICT Pioneers contest. Not sure I'll ever transform society, but it was a fun event, with lots of interesting people to chat to.

Another poster:

city sculpt - ict pioneers poster

And some video-with-pretty-lights:



Press coverage here, here and here. Was kind of fun for a Sicsa student to win a prize at an Epsrc event ;)

Shout out to Zdenek for making the front page of reddit with his winning entry :)

IMG_7833

The best thing is that I'm funded by sicsa, a Scottish competitor to Epsrc!
sicsa logo

Monday, April 11, 2011

Interactive Architectural Modeling with Procedural Extrusions

ACM Transactions on Graphics, volume 30. issue 2. pages 14:1-14:15.2011
[ doi | pdf | pptx | code ]

We present an interactive procedural modeling system for the exterior of architectural models. Our modeling system is based on procedural extrusions of building footprints. The main novelty of our work is that we can model difficult architectural surfaces in a procedural framework, e.g. curved roofs, overhanging roofs, dormer windows, interior dormer windows, roof constructions with vertical walls, buttresses, chimneys, bay windows, columns, pilasters, and alcoves. We present a user interface to interactively specify procedural extrusions, a sweep plane algorithm to compute a two-manifold architectural surface, and applications to architectural modeling.
house of horrors

Example-video (not finished in time to be refereed...)









Monday, April 04, 2011

3d environment construction times

I've been having real difficulty trying to find real-world figures for how long it takes artists to create 3d environments. Does anyone out there have experience creating these environments regularly?

The kind of information I'm looking for:
  • an image of the constructed scene,
  • the tools used (Maya, Max, Sketchup...),
  • an estimate of the number of hours using each tool.
These figures would really help the motivation of procedural tools for the rapid construction of cities. With a bit of luck (and a few more years research...) creating virtual repetitive architecture manually will be a thing of the past.

now thats what I call architecture

Monday, March 28, 2011

some videos of procedural extrusions.

Renders finished on some around procedural extrusions last week (paper, extra videos). This is a technique for the procedural modeling of buildings. A fade of the same set of 6,000 footprints synthesized from Atlanta.




A natural step is a perturbation of the plan of a building at a height. By growing the shape of the step, we create more robust geometry:




We can use this footprint to grow features of the building, such as this dormer window. The important point here, is that even though we ask the algorithm to position the step in strange places, the result is always "quite" valid and "quite" architectural. The result is always a well-formed mesh.




We can animate the floorplan to create a wide range of architectural forms.


And if you spend more time using the interactive tool, you can make some really intricate examples (all modelled from photos/plans).



These are the stretchy elements that we stick onto the architectural shells when we're done - (note that you should only let them stretch in certain ways)



Shoddy rendering for Siggraph-fast forward video:

Sunday, February 20, 2011

how to publish a TOG paper

In celebration of finally getting my work into a decent journal, I decided to have a look back to see how the paper developed over time.

City Architecture Generation ( Master's Dissertation 2006 | pdf )

Way back in the past I was doing a degree at bristol, and wrote my dissertation on an interesting concept for architecture generation. This original document is very flawed, and the results quite rough, however the code (just about) worked. I seem to remember it being a few months work. I got a decent enough grade for it at the time, so was happy enough.

The important thing is it gave me enough of an insight into a new & useful technique. I went off into work in the real world for a few years, and thought about the project again every now and then. Then I decided to head back to academia, and start over again with a PhD...

The fun results are on page 75.



The Extrusion Skeleton for Procedural Architectural Modeling ( Eurographics 2009 | pdf ) rejected

For the 9 months or so, I messed around with a few systems, and finally got the straight-skeleton system working to the point where I was reasonably happy with it.

We decided a couple of weeks before the deadline to really go for the Eurographics submission. We made great progress in two weeks, but the reviewers rightly rejected it as being sloppy.



The summary we got back from CGF:

"The paper presents a simple interactive procedural method to create a variety of architectural shapes. The core of the method generalizes the existing ''straight skeleton'' algorithm for computing roof shapes, by (a) allowing different slopes on each edge of the input polygon, and (b) by allowing edits on the polygon ''during'' the algorithm. An easy to use interface is proposed.

The reviewers consider that this paper proposes a number of incremental but very useful additions to existing methods in the area. These additions are carefully selected and blend well together, the method is nicely integrated in a functional interactive systems and produces impressive results.

Unfortunately, the paper has major problems: the presentation is confusing, the algorithmic description is sloppy and contains several errors, and the method has not been carefully evaluated. Cleaned up, the reviewers think this paper could be useful to the community. However the required revisions are major and the paper cannot be considered for the Eurographics conference."

Other comments:

"I definitely miss references to interactive sketching systems, such as SESAME and Sketch-up, and to have a discussion on this issues. Since the main focus of the paper is on interactive design, the real comparison is with interactive systems, not only grammar-based systems."

"The proposed extensions to straight skeletons seem to be of limited novelty. Some of the extensions (like multiple footprints and the avoidance of ''angle restrictions'') appear to be done before. Other extensions (multiple wall profiles, plan edits and robust computation) might be novel. However, they are mostly straightforward and represent only a minor contribution for a Eurographics paper."

"This is actually very good except where it isn't."


Interactive Architectural Modeling with Procedural Extrusions ( Siggraph Asia 2010 | pdf ) rejected

The next deadline we wanted to try for was Sigg-Asia. The big step here was getting it to work over a large input set to make the pretty first figure. We made an attempt to add some comparisons to existing modeling techniques. As ever I ran out of time trying to submit, and didn't manage a video (the editor kept crashing at the last minute).

21 feet

In the reviews I took a lot of heat for the lack of an evaluation and the picture of my co-author hidden in the paper. But the thing that really killed it was us pretending that we had a perfect geometric algorithm when there were (rare) situations where it would fail.



Reviewer summary:

"1. The paper doesnt provides an algorithm in the proper sense of the word. You present a set of heuristics that works on a large set of models. This can be very useful from the modeling perspective as the user is in the loop to fix the degenerate results. Please try to make this clear early on, and in the review cycle we want to agree on this change in exposition style.
2. In computational geometry the stress is to present provable algorithms. Hence, in many cases the algorithms end up complicated to implement to address various degenerate inputs. This is not the case for the modeling scenario where the user can update the inputs in case of failures. Again this distinction should be clear in the paper.
3. Please remove figure 25, it weakens the paper.
4. Please perform a proper evaluation. Take a large number 50-100 floor plans from some publicly available repository, and use your framework to come up with buildings there. It will be excellent if you can use google streetview or like to take existing building profiles and try to replicate them. In your rebuttal you already mentioned about cities where such complicated roof structures are common. We feel the work will have an important effect in this area, so we want to see this in a form that is easy to understand and judge."

Other comments:

"You need to be very careful about using a single word or term for each concept: you can't have a priority queue that becomes a priority list; you can't have a wall-angle that becomes a weight, and so on. "

"I've suggested that the introduction should discuss an experiment that tests the generality of your system. Providing this support for your claim of a good working system --- support with solid factual evidence --- would be the best service you could possibly perform. The reviewers agreed that the way to do this is to take a collection of house-plans (for example, go to XXX.com"

"The algorithm is interesting, but the scope is rather restricted. While it is true slanted roof structures and similar extrusions (figure 22) make the models realistic, but it is unclear if such a specialized and general algorithm is required. It may be sufficient to have a template based model. "

"Overall this paper presents a powerful system able to generate complex building geometry that can be edited interactively. My concerns are with the amount of manual effort that is needed and with how well all (most?) special cases are handled. The former is empirically shown to be reasonable - ok. The latter is more unclear."

"The main problem with this paper is in the GOAL -- not of the work, but of the paper itself."

"(I apologize for any typos or unclearness in these notes; I have wrist problems which make me not want to take the time to do any more editing than necessary.)"**


Interactive Architectural Modeling with Procedural Extrusions ( Transactions on Graphics 2011 | pdf ) accepted

We got an offer to publish our work in TOG after the Siggraph rejection, if I made the suggested corrections. This meant that I spent a lot of time on evaluation (playing with our application) - however when I was done I had a much better idea of the weaknesses and strengths of the system. I followed the suggestions of one of the previous reviews to use an online library of floor plans. In hindsight this was probably a mistake because:
  1. Online libraries only seem to exist for plans without locations - and without interesting boundary constraints, many features of the project weren't appreciated.
  2. The online library didn't give us copyright permission to also show the library of plan/images we used for the modeling process. The reviewers were able to see it, but we weren't able to publish them. Available here (40Mb).
There was also a lot of effort done to tighten up the technical writing in the middle of the paper. One challenge was to choose an appropriate depth of explanation - too deep and you end up explaining too much, too shallow and you invite many additional questions.

The other challenge was keeping the terminology consistent throughout(!). This becomes non-trivial after so many paper drafts, and the fact the implementation (the source code) uses an entirely different set of terminology.






Of course, there are always new problems that come up with the concepts when you keep digging, one is detailed in a previous blog post.


Just for reference, here are the edits made by the ACM copy editors before the final article was drawn up. Apparently paragraphs should start on the same line, and never use "Fig. X" in the body of text, always "Figure X":



Finally I would like to thank the many reviewers who helped us scrape this paper together. Especially the few guys that stood up for this work! It's been an exercise in learning how these things are really done, and how they turn out under time pressure. Hopefully the next one will be a little easier on us all :)
** - never say this in anonymous reviews, it leads to whoever-you-are being known as "wrist guy" for the months while we redraft the paper.

Wednesday, February 09, 2011

fixing moodle

As a PhD student I take pride in doing a job properly. And putting more effort into avoiding work than doing it in the first place. Therefore I am proud to present the sketch of a method to download a (java) assignment from the University of Glasgow's moodle site, run it against a marker, and create a pdf file (via latex) of the output for marking.

This process isn't easy or well polished. It will take a bit of hacking to get it to work for you. But it'll probably save you time over a few weeks of marking. It's hard wired to work on the first assignment for Patrick's ADS2 course.

From moodle, we need two things. The first is a class list, log into the moodle course, view grades, and set the "visible groups" to your tutor group. Then download the webpage (save as...) as class.php in a folder.

Screenshot-3

The second thing you need are all the files. To grab these, use the tool Download them All! for the firefox web browser. Navigate to the page assignment page, and click "view 999 submitted assignments", and use the "show submitted assignments" field (at the bottom) to put all the submissions on one page.

Now we start Download them all:

Screenshot-ADS2: Exercise 1: A Small Face Book - Mozilla Firefox

And we're given the following box. We need to download all .java and (sometimes) .zip files for this assignment, so we set the "fast-filtering" field accordingly. We also want to specify the file-names to include the url, so we set the "renaming mask" to *curl*_*name*.*ext*. Then click start, and wait for the magic.

Screenshot-4


If any students have zipped their work, you currently have to unzip it and find the file they should have submitted manually. The name it using the moodle naming convention (obvious from the other files in the directory!).

We now setup the java program and run it. The code is here (file, paste.org), you need to change:
  • class.php to whatever the class-list file you downloaded is called
  • "/home/twak/Downloads/ads2/fims.moodle.gla.ac.uk/file.php/158/moddata/assignment/50"to wherever the assignments were downloaded to
  • setup a subfolder with the assignment in it. I've called it "./problem".
  • "javac -cp problem problem/FBook.java" to whatever command you use to compile their code with
  • "java -cp problem" Marker to whatever command you want to run on the code
  • you may want to edit "pdflatex output.tex" to your favourite latex command to create the final output.

Issues with the script:
  • Quite untested at the moment. Use at your own risk.
  • Assignments not run in a sandbox - malicious code can blow your system away.
  • The script doesn't currently truncate overly-long outputs. I've had students work go into infinite loops when attached to a printer before...
  • It should really be a single greasemonkey script to run...but this would have taken more effort.
  • For a script that's used on the Advanced Data Structures and Software Engineering courses, the code is really awful.

Friday, January 21, 2011

straight skeleton for polygon simplification

We can simplify shapes using the straight skeleton:

simplify_outlines

If we grow (offset) the polygon (a) we remove reflex corners(c), and if we shrink it we remove convex corners(b) (for lack of a better phrase). If we apply both offsets in sequence we have a fairly robust polygon simplification tool (d).

There are several drawbacks with the straight skeleton as a simplification tool. It does not introduce new edges to the polygon, so polygons that do not contain an edge with a good approximation for the local region are not simplified well. "Very" reflex corners have a disproportionate effect on the result. However this may be rectified using a variation of the linear axis. The computational complexity is also higher than that of existing algorithms.

If we view the process as 3d roofs, we get the following diagrams for interior-offset, exterior offset and a combination of both:
simplify

The advantages are that it is very conceptually simple, robust to any input shape and can effect genus change in the process of simplification. The weighted straight skeleton would also allow different weights to be applied to different edges. Perhaps this could be used to preserve particular features? The theory extends (easily?) into higher dimensions.



Tuesday, January 18, 2011

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.

skel_terms

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.




skel_inverted

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.



skel_intro

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

skel_unweighted_intro

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




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




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



skel_loop_two

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?

skel_linear_ambig

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.



skel_chains

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



skel_gie_intro

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.



wss_terms

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.



wss_linear_ambig_1

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.



wss_linear_ambig_2


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.



wss_linear_ambig_3


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.



wss_example_topology

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



wss_enclosing_chain

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.



wss_options

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.



wss_loops_go


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



wss_major_axis


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



wss_equal_approach_killer

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.

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




wss_ordered_point

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



wss_sector

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.



skel_sector_2


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.



wss_hand_examples




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.



wss_numbered_union


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.



wss_union_vs_gie


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



wss_gie_example

Monday, January 17, 2011

xkcd

xkcd
well it's either waiting for it to render, or to compile.

modified from the great http://xkcd.com/303/