twak's blog

back from Kaust

2011-12-24T19:37:00.001Z

Before the holidays I had a short stint working out at GMSV@Kaust, King Abdullah University of Science and Technology in Saudi. I've written down a few notes about life at this crazy place:-

My initial impression was of the the amazing academic facilities. There are great offices, a visualization suite, 3d printing facilities and a super computer (which they seem to be trying to find a use for). As you'd expect for a university with a $10bn endowment, the buildings are beautiful - sweeping open atriums and harbour-views from many of the offices.

The campus itself has the feel of American suburbia - all speed bumps and sprinklers. Very nice, very liveable, but a little fake if you're European. While I was there I lived in several places -

The Kaust Inn (photos) - the campus hotel, same as any hotel anywhere. Watch out for the rooms at the back which point towards the grand mosque and its 5.30am prayer calls.
A one bedroom flat (photos) - A one bedroom flat on the island. Loads of space for entertaining guests, a good sized kitchen, and a study. Plenty enough room for a (European?!) couple.
A four bedroom house (photos) - Towards the end of my stay the research group rented one of the big colonial-style houses on the beach. (Due to some technicalities I had it to myself for most of my time there). This is a fantastic place that would normally be reserved for full Professors and their families. A sofa for every day of the week, waking up to eat breakfast overlooking the beach and the waves breaking on the reef.

The university has done a fantastic job of marketing and advertising itself. It is hard to find something on campus that isn't branded with the university's "unity seeds" logo.

Kaust made me reassess one of my old prejudices - old universities are good universities. Although I must have always realised that this was false, this place is a brilliant data point proving the contrary. The campus is three years old, has a formidable faculty and has forged (bought) alliances with the great and the good (Cambridge, Cornell, Oxford, Stanford...)

I think a spell at Kaust would look very good on anyone's CV. In particular for people looking for a fast track to high level research, or as a cheap way to get a graduate degree (the two year long Master's courses comes with a ~USD2000/mo scholarship).

There's several moral considerations that people should be concious of in Saudi. As well as the well known country-wide issues of civil liberties and women's rights (which are better documented elsewhere), there are also issues that are very pronounced on Campus -

I was also surprised at how many times I had to sign a bit of paper that threatened to kill me. Both the visa and customs paperwork make it clear that the death penalty is in use. While slightly tarnishing the Arabian hospitality of lore, this is still true of plenty of other countries (cough cough USA). This was something that was always in my mind when travelling to Saudi and added to the traveller's anxiety more than it should. My concerns seem to be unfounded - Sharia law isn't enforced on the campus, and I'm sure that 90% of the academic staff would quit if anyone lost a hand after being accused of theft (writing of the investment in the universitiy overnight).
The campus is kept clean and spotless by an army of (relatively) poorly paid foreigners. Mainly Indian and Filipino; These guys are driven in from Jeddah every morning, or live in gritty looking housing on the other side of campus. I guess while I realise that the world is a very unfair place, and I have my share of sweat-shop trainers, I wasn't expecting to have this reality thrown at me every day.

Saudi is historically suspicious, if not outright hostile, to outsiders. I did find myself asking if this kind of knowledge transfer is really moral if the country doesn't want to integrate with the rest of the world. For example there are no tourist visas available to Saudi, unlike many other Middle-Eastern countries, and most of the foreign workers find themselves living in gated communities away from the locals. The attitude to foreign workers seems to work, get paid, stay quiet, then get out.
However green the campus claims to be, the building refuse discarded on the other side of the motorways says otherwise. It is very unnatural to live the (24-7-air-con) American dream in the middle of the desert, and however well designed the campus' buildings are, there must be a significant environmental cost. Add to this the 100 mile drive to escape the campus, or air travel to escape the desert (at regular intervals if you want to remain sane), and it is possibly not the most environmentally sound living location.

The campus is modeled on American suburbia - after you pass the tank traps and security checks you find yourself in a very safe feeling environment. Palm trees (watered by the eternally present sprinkler systems) line the streets, and there's plenty of green open spaces (a couple of parks and a golf course). The supermarket is 15 minutes walk from anywhere on campus and is stocked to placate people from most parts of the world - Froot Loops for the Americans, Leerdammer and Emmental for the europeans, a reasonable wheat-free section and even beef-bacon for those with pig-withdrawal symptoms. Of course there's no beer, and occasional supply problems (the campus ran out of peanut m&m's!). Most critically, there was no dark chocolate - a certain prerequisite for doing research of any quality...

The feeling of cargo-cult westernism seems to permeate a lot of the campus. For example the workers in the supermarket wear disposable gloves when working with raw meat, but don't take the gloves off to pass you a piece of cheese. The fast food places in the malls in Jeddah (90 minutes on the frequent Kaust buses) are the slowest I've ever seen. The airport is another great example - there's been no checks for liquids, and was marched in a group of 20 passengers backwards through security (and the metal detectors) after a flight was cancelled. There's also the occasional path to nowhere, or bathroom sinks positioned to make the toilet impossible to sit on if you're over 5ft tall. This is a great blog detailing life on the early Kaust campus, including the epic floods!

My number one gripe was the feeling of being stuck on campus. As a gated community, there was a lot to do on the campus - a medium sized gum, windsurfing, snorkling trips, and a coed (racy!) beach. People who had families, and spent their time socializing with (sober) friends, seemed to get on fine with the setup. However I'm used to heading out at weekends and blowing of steam on 150km bike rides, and there was nothing that I found to come close to this - the roads were too large (and unsafe - almost all the cars looked like they'd been in some sort of collision in the last 6mo) to cycle on, and there were no real organised outdoor activities (no hiking, orienteering, or even yachting). If you so much as sail the rental dingy more than a few hundred meters from the beach, the coastguard comes and picks you up. While there's a great choice of stuff to do on campus, it is just that - a choice between several watersports. After a few weeks, all this left me feeling more than a bit trapped.

Still, when all is said and done, Kaust (not to be confused with ECUST, HKUST, KNUST or KUST) is a refreshing change to trying to do academia in the UK, where career advancement is difficult and basic funding is in question after the government pulled funding for most of the mathematics postdocs. The campus, and its sunsets, are really beautiful, and well worth visiting!

Procedural Generation of Parcels in Urban Modeling

2011-12-17T19:25:00.001Z

Eurographics 2012, to appear
C. Vanegas & T. Kelly, B. Weber, J. Halatsch, D. Aliaga, P. Muller
[ pdf ] [ additional materials ] [ implementation ]

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:

Location of teaser, figure 10, appendix B.
Original 3D images: first, second.

siteplan source release

2011-09-14T20:03:00.004Z

I'm very happy to finally announce the long overdue release of SitePlan, my procedural extrusions implementation. There is information about the project here (or just click here to run; java executable; run at your own risk).

Please use the software! The source code is here. This is a research project and it would really help me if you emailed me screen shots of your project and a description of what you used it for.

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.

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

Zurich & Procedural Inc

2011-05-26T13:19:00.003Z

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

uk epsrc ict pioneers

2011-04-14T12:12:00.004Z

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:

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

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

Interactive Architectural Modeling with Procedural Extrusions

2011-04-11T11:07:00.012Z

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

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.

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

3d environment construction times

2011-04-04T10:16:00.004Z

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.

some videos of procedural extrusions.

2011-03-28T17:55:00.010Z

Renders finished on some around procedural extrusions last week (paper). 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:

how to publish a paper

2011-02-20T19:10:00.015Z

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

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:

Online libraries only seem to exist for plans without locations - and without interesting boundary constraints, many features of the project weren't appreciated.
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.

fixing moodle

2011-02-09T20:03:00.009Z

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.

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:

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.

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.

straight skeleton for polygon simplification

2011-01-21T12:49:00.007Z

We can simplify shapes using the straight skeleton:

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:

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.

degeneracy in the weighted straight skeleton

2011-01-18T17:37:00.018Z

The following is something I wrote for an internal progress report. 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).

xkcd

2011-01-17T13:38:00.001Z

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

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

SICSA Demofest 2009 video/poster

2010-11-26T18:57:00.007Z

Catch a bit of (2 year old) hyperbole from me at around 39 seconds (on 'tube):

The poster I presented is below (pdf) - it is an attempt to put a commercial spin on the work that shows the future promise of the work (with about GBP 10^7 in funding)

Recursive weighted skeleton

2010-11-22T16:05:00.009Z

Given the weighted straight skeleton, and two features

The ability to change the speed of an edge at a certain time (height/offset depending on your model) (lets call this an edge direction event)
The ability to add edges on a particular edge at a certain time (lets call this a plan edit)

We can devise a language that allows the plan edits after a sequence of edge direction events. The question is - can this language be recursive? Turns out the answer is yes:

Here's another more discrete variant.

This is interesting because of it's similarity to two different types of automata - fractals (such as the Koch snowflake) and cellular automata (such as the game of life). Because the speed of edges can be forward or backward we can create edge direction events to model growth and decay - this is somewhat like the game of life. And because our language allows recursion we can model fractal shapes...

I get the feeling that system has the persistence and transmission of information to create high (Wolfram) classes of behaviour according to Wolfram. Will need a better implementation to go hunting for them...

ssd's and ubuntu

2010-06-18T17:41:00.005Z

So I got fed up with waiting for my new computer to boot or java to find the hundreds of files it needs, I decided to blow my spoils from a recent conference victory on a SSD hard disk for my desktop machine.

First surprise - it came in a flat envelope - thought it was a mistake at first, and they'd sent me an OEM cd, but sure enough it was an Intel 80Gb (SSDSA2MH080G2C1 to be precise...) . These things are really small, packaged in not much and must be quite robust.

Second surprise - well not really surprise, the speed boost is pretty noticeable. Overclocking takes second place to getting one of these on your development machine - top video is with my old HDD (320Gb WD Caviar drive), bottom with the Intel SSD.

So running ubuntu, there are two things I discovered people talked about - erase block alignment and trim support. Because I'll forget what I did this time, I'll note it in this blog, however I suspect that by the time anyone uses this, there will be a better guide available.

Erase block alignment

As explained here, when a SSD deletes data, but nuking entire erase blocks. On my intel ~~disk disc~~ drive the erase block size is 128K (128 * 2^10 bytes, different drives, such as the OCZ use different e/block sizes), so we want the sectors of the drive to align to this boundary. I used the instructions here to use the live Ubuntu CD and fdisk to ensure this was the case.

Then I reinstalled ubuntu and booted her up.

Trim support

Trim is an operating system function that tells a drive when pages are no longer in use, and can be handed back to the SSD's page-allocation system. But the default version of Ubuntu (currently lucid/10.04) uses kernel version 2.6.32, so there's no trim support. The instructions here give a painless way to upgrade the kernel to 2.6.34, once ubuntu is installed.

weighted straight skeleton source release

2010-06-17T11:31:00.014Z

[more skeleton blog posts]

The straight skeleton shrinks in the boundary of a polygon, whilst tracing out the corners to create a roof-like structure. Thus is quite useful for building things like roofs or offset surfaces. I never did find an impelmentation that wasn't CGAL's, so here's a floating point implementation.

The weighted skeleton allows the edges to move at different speeds. You could even assign negative weights to edges.

You can run it by clicking here (java webstart, binary code, run at your own risk).

Left drag the little orange squares at the corners of the cross
Right drag to move the view
To change the weights drag the big orange circles
Control-click to add corners
Shift-click to remove corners
There are known bugs (for example the polygons in the UI overlap, there will be cases where it doesn't tessellate).
Use alt-while-dragging to snap to grid

Google code project (java) is here.

Here's an example of how to skeleton a simple triangle. Points are defined counter clockwise. If you only want the 2d projection, discard the final (z) co-ordinate of the output-faces.


        Corner
        c1 = new Corner ( 0,0),
        c2 = new Corner (100,-100 ),
        c3 = new Corner (100,0 );
      
       Machine directionMachine = new Machine ();
      
       loop1.append(new Edge ( c1,c2 ) );
       loop1.append(new Edge ( c2, c3 ) );
       loop1.append(new Edge ( c3, c1 ) );
      
       for (Edge e : loop1)
        e.machine = directionMachine;
      
      
       Skeleton skel = new Skeleton (out, true);
       skel.skeleton();
      
       for ( Face face : skel.output.faces.values() )
       {
           System.out.println("face:");
           for (Loop  lp3 : face.points)
            for (Point3d pt : lp3)
             System.out.println(pt);
       }

equipment funding in academia

2010-06-16T14:10:00.005Z

So coming from industry to academia, the 50% pay cut was announced up front - fair enough - I can get up at any time after 11am, and only have to be in one place for an hour every week. But I didn't realise how hard it would be to get equipment and software that was trivially available in the commercial world. If you can make a case to your manager that a 30" monitor will save you an hour a week, it is more effort for them to reject the request (a 30 minute meeting costs more than the requested hardware), than to grant it - hence hardware and software are a non-issue.

But it turns out I had made an assumption that inviting someone to study graphics at a university meant that there would be equipment available to do graphics research of a globally publishable quality. I'm not talking about Cray supercomputers, I'm talking a decent current gaming pc (£1,500) to be able to do real-time graphics. Turns out that Glasgow's department of computer science starts PhD students off with really poor hardware:

and upgrade them if they complain enough - there's no money available for upgrades (all the budgets are maxed out in the current environment), so they shuffle graphics card and memory around the department to whoever needs them more. This was the specs of the machine that I was given when I started at the end of 2008, they don't come close to what I'd describe as "industry standard software development platform", closer to what you need to run office software:-

So that's no dedicated graphics card, and 19" monitor - most people in the vision group (who spend their days with 15 windows open, examining many images), still use this gear. Frankly I doubt this equipment cost £500 at that time, my similar machine (with a £200 graphics card, but without the £100 monitor) cost £600 a year earlier. And okay there are servers available - but mostly these are funded by individual research grants, rather than being open for all PhD students - and most importantly servers make it difficult to do the kind of real-time processing that graphics demands.

After complaining (and as way of apology for loosing my computer) I got a computer equivalent to that £600 machine - but most almost all students don't have industry experience, don't know what a development environment looks like, and don't complain loudly enough.

For example the last graphics paper I wrote had a nice render and an accompanying video. Either setting up the rendering of large scenes or editing video require a decent local computer, especially to compete in computer graphics at an international level.

Considering there's so little money required for decent hardware (£3000 over 3 years is probably sufficient, even for heavy graphics), compared to the cost of salaries (£40,000 over three years) it leaves a feeling that the department doesn't value PhD time. However when you start to look at where the hardware funding comes from, (for example Sicsa pays Glasgow £2000 a year for my hardware), it looks like it's being lost in the University's & Department's bureaucracy black-hole.

my dept pc - we're not talking state of the art here

I've ended up building my own gear for use at home - bit of a sad outcome, but guess I don't have to put Glasgow on any of the papers I write now ;)

copyright vs procedural content

2010-03-31T16:30:00.006Z

In 2006 the Damien Hurst was accused (via) of copying a design ("valium", top) from Robert Dixon ("true daisy", bottom). Hurst is a quite well known millionaire (valium's 500 prints sold for "four and five figure sums") and Dixon a relatively unknown computer/geometric artist. At first glance it looks like Hurst just coloured in, flipped and cropped Dixon's work, but looking a bit deeper it gets more interesting.

Dixon's work is based on the patterns of spiral Phyllotaxis, a natural phenomena that describes (among other things) the arrangement of needles on a pinecone and pattern of seeds on a sunflower head.

by RaeA

This is a old mathematical pattern that can be expressed as an formula, and was well known enough to be commented on by da Vinci. Because of this Dixon was able to write code (similar to mine, that produced my diagrams below) to generate his pattern.

Simply, Phyllotaxis is a spiral pattern of points. Although many different spacings are possible, the fantastic thing is that nature always chooses the same spacing. My diagram below shows a few possible spacings, and one jumps out as being "correct" as it covers the space most evenly. This is the pattern that is used by nature, Dixon and Hurst.

But the question is - should he be able to claim copyright on it? and is Hurst's work derivative of it? Copyright law say yes - Dixon has some claim over this figure, as he created it (no matter it's source) and has a copyright claim. The law just asks that he has the work is "original, and exhibits a degree of labour, skill or judgement". Maybe he was the first to use circles of that diameter to represent the pattern. So if I can build a general machine that with some parameter imitates Dixon's machine - does Dixon own the output of that machine?

Okay, so I built the above machine after viewing Dixon's work, at some point it probably outputs something that looks enough like Dixon's work. This is a real headache for me as a programmer - is the output of my program derivative? does Dixon own the copyright to the program he's never seen?

One answer is that I should block particular frames that contain copyrighted images. To do this in this single instance, I would have to describe Dixon's work in the program to stop it infringing. The program would then contain copyrighted material and be illegal. To do it in the general instance, for all copyrighted spiral patterns, I would need to do an international prior-art search, which would cost vastly more than the two hours it took to create the above video.

There are excuses for copyright, for example if you can prove you didn't know about the existing image, that you didn't "copy" it, then the use is mostly covered under fair deal (or fair use in the USofA). But some inventions are covered by the more powerful patents - in this case even if you come up with the idea independently yourself, the first person to be awarded the pattern hold all rights to it.

In situations like this, Intellectual Property (IP) lap feels very wrong, this is an algorithmic pattern, and if I'm allowed to copyright it, or copyright a video of all possible versions of it, there is nothing left for the rest of the world to use.

If I can write a program that recreates your patented "invention" or copyrighted "original" object do you own that program? If I can write a program that will write that program, given a certain command (abracadabra!), do you own that word? do you own/control the first program and the second program? are both programs illegal (under DMCA-like legislation they probably are). Does this mean that any program that can recreate patented work is illegal? does this include a computer compiler (probably not)?

At the moment these ideas are unlikely, and limited to toy examples. But in ten years, when anyone can ask the computer to create a program that lets you edit photos ("now I want a circular brush!"), and that program infringes on hundreds of patents, it seems like IP law will have to change.

Another reason to burst the IP bubble sooner rather than later? A previous post on copyright can be found here.

rapid prototyping procedural buildings

2010-03-22T18:27:00.004Z

via boing boing.

These guys have a set of templates you can send off to a rapid prototyper (or yourself) to build a kit-set for your own cathedral. You choose which sections you want printed

Then glue them together yourself -

This is what procedural architecture is all about - what they have here is a simple shape grammar! We're not far from the situation of having designs where you can define an arbitrary floor plan and style on a website, and download a solid file you can get printed. Or how about having it printed big enough to be a dog house? or somewhere to live in the summer? I can't wait for the first lorry to arrive with a procedurally generated building on the back :)

exploring frequency responses for focus

2010-03-19T14:04:00.019Z

In the name of badly rushed science for conference deadlines I present the accumulation of a couple of week's evenings messing around learning about frequency space.

[tl;dr] This paper got accepted, and I "presented" it at the Sicsa 2010 conference. Here's the video:

(via wblo)

While I'd always seen the little bars on music amplifiers, I'd never thought of images being represented in the same way. The bars represent the frequencies being played back at any one time. The low frequencies (slower moving bars, normally to the right) are the deep sounds, and the high frequencies (fast bars on the left) are the high sounds. It turns out they have a nice analogue in the image plane, but because we don't look at at every pixel in a photo in order from start to end over 3 minutes we never see them.

If we identify the important areas of an image for each frequency (DoG pyramid/"monolith"), we can animate over the frequency (high frequencies first, then the low ones):

We can then see that a single point in the image has different intensities at different frequencies, as the shade of grey at a point changes. So there's one of the little bar-graphs for each pixel.

I built a little application that lets you see these graphs and the spatial frequencies in an image. It's quite fun to play with, you can start it by clicking here (java webstart, binary file, run at your own risk, source code below). Wait for it to load the preview images, select one, wait for it to build the map (lots of waiting here...) and then use the right-drag to move around, wheel to scroll, and the left button to show a frequency preview for a particular location. Move the mouse out of the frame to see the representative frequency map from the work.

As you drag the point around the lil bars change to show you what the frequency content is like in that area of the image.

This was neat, and I had to do something with it, so I built a hoodicky that takes a single image and recovers the depth map from the focus of a single image. I assume that stuff in focus is near the camera, and stuff out of focus is a long way away - photography just like your Mum used to do. It turns out that not too much work has been done in this region, these guys even got a book article out about it last year.

So just to late to be hot news... but interesting none-the-less. So I decided to twist the concept a bit and use it for blur aware image resizing. The motivation being that you need big (expensive) lenses to take photos with a shallow Depth of Field, but when you resize these images, you loose that depth of field:

In the smaller images, more of the logo appears to be in focus, but it's the same image, just scaled a bit.

So we want something that keeps that proportion of each frequency the same as you scale the image. So basically it's a thing that keeps foreground/background separation when scaling an image. We can use the focus of an image (closely connected to it's frequencies) to determine the depth, as this video shows.

In the following, a, b and d are normal scaling, while c & e use the depth map we've calculated using the frequency map.

This uses the frequencies on the edges of the photo to classify the segmented image. This shows the same kind of thing at the top, and the segment-frequency map bottom left, and the recovered depth map bottom right.

More results (SICSA are the people who pay half my rent...):

Here a,b,c are standard scalings and d,e are from my algorithm.

Results are better than I expected for the few days I spent putting this thing together, but the basic problem is there are two or three parameters that need to be tuned for each image to take into account the noise of the image and the bias towards foreground/background classification. Good working prototype, lots of effort required to do this for real.

The write up looks like this (non scribd pdf, src below), I'm a bit certain some of the equations are wrong - but this is computer science, no one actually reads equations do they?

Source code is here. Java. I think it uses Apache licensed stuff, that that's how it should be treated, but I scrounged a fair bit of code, who knows where it's from... Main class should be FrequencyMap, and after setting up an image in that class you'll need to play around with the four constants at the top:

fMapThreshhold: Increase if not enough red (high freq) in the freq map, decrease if noise is being counted as red
scaleFac: usually okay to leave alone. If you want a frequency map with more levels, decrease this, keeping it above one.
filterRadius: noise reduction on edge classification. Increase to classify more edges as higher frequency
Q: increase to increase the number of segmentations.

It will write files out to the disk. Use at your own risk.

[edit: 22/3/10]

While out riding this weekend I figured out that it should be possible to analyse the defocused edges for evidence of higher frequencies to determine if the edge is in front of, or behind the in-focus point. More importantly if we can't see any high frequency edges in the bokeh, then it doesn't matter if that part of the edge is in front of, or behind the defocused edge...

[edit:] woo! It's been accepted (probably because it's one of the few graphics papers from Scotland). Reviewers comments follow:

Dear Author,

Thank you for your submission to the SICSA PhD Conference. We are delighted to inform you that, subject to corrections, your paper has been provisionally accepted to be presented at the conference. The comments from reviewers are included at the bottom of this email.

We will be in touch with you soon regarding the nature of the corrections that must be made in order for your paper to be included. You should note that the absolute deadline for these corrections will be MAY 19th 2010. No deadline extensions can be offered.

Regards

---------------------------------------------

Paper: 21
Title: Blur Preserving Image Resizing

---------------------------- REVIEW 1 --------------------------
PAPER: 21
TITLE: Blur Preserving Image Resizing

OVERALL RATING: -1 (weak reject)
REVIEWER'S CONFIDENCE: 1 (low)
Audience Appeal: 4 (A typical CS honours graduate will fully understand what the paper is about, but is unlikely to understand all the details.)
Significance: 4 (Interesting work which will probably be cited even if it does not shake the field of research.)
Originality: 4 (A minor or incremental improvement to existing work that is not immediately obvious.)
Presentation: 4 (The paper makes sense and the story is intelligible. However, the structure or grammar is sub-optimal, potentially making it frustrating to read.)
Validity: 5 (Valid, practical, relevant approaches are made and are probably correct but may not be concrete.)
Recommendation: 3 (The paper is below average, but I do not feel strongly as to whether it should be accepted or rejected.)

Please provide a response to each of the following queries:

1) What was the paper about?

The paper presents a method for scaling images which attempts to retain the image's apparent depth of field by selectively blurring parts of the image. The amount of Gaussian blur applied to each segment is proportional to the depth of the scene at that segment. This depth information is automatically calculated from a single image using an augmented segmentation algorithm.

2) What claims or hypotheses did the paper make (if any)?

The paper claims that:

- When images are scaled down the apparent narrow depth of field is lost.
- It is desirable to keep the same proportion of the image with the same CoC.
- The presented method is able to retain the apparent depth of field in an image as it is scaled down.
- The presented method is capable of narrowing the depth of field apparent in images captured using commodity compact cameras to allow a larger aperature to be simulated.

3) What are the good points of the paper? Why might it be accepted? What did the author do right?

The paper introduces a significant new method which can be useful in practice (as it requires very little information and/or extra equipment). The method has been clearly presented and is understandable. Plenty of images have been provided which do add to the text. The algorithm appears to perform the intended task well.

4) What are the bad points of the paper? Why might it be rejected? How might the author improve their work?

The first claim (that apparent depth of field is lost when images are scaled down) has not been justified. The efficacy of the method at retaining the depth of field has not been quantitatively analysed, nor has it been compared to the bog-standard scaling algorithms or the naive blurring approaches. The method has only been demonstrated to work on a number of hand-chosen examples. The authors make a third claim in passing which has not been demonstrated or backed up in the paper.

The paper should be shortened down to 10 pages. Changes could be made to sentence structure (particularly in the introduction and conclusion) to make the paper more understandable. The relationship between the presented method and previous related work could be explained in more detail.

Please also provide a justification for the scores you have provided in each of the following areas:

Audience Appeal (1 - bad, 6 - good):

The presented method is easy to follow. Only the presentation occasionally gets in the way.

Significance (1 - bad, 6 - good):

Originality (1 - bad, 6 - good):

It is of interest to see how the presented method relates to the existing literature on single-image depth estimation. Whilst the application area is novel, the underlying machinery may not be.

Presentation (1 - bad, 6 - good):

A number of grammatical and spelling errors exist. The paper is too long (14 pages). Some parts of the text feel unfinished (in particular the introduction and conclusion.

Validity (1 - bad, 6 - good):

The authors present a convincing technique, and also point out its potential shortcomings in the conclusion section.

Recommendation (1 - bad, 6 - good):

The paper, in its current form, is not ready for publication. First, the method needs to be analysed and compared quantitatively. Second, the writing, layout and presentation in general should be improved.

Any other comments to make to the authors:

(Changes have been capitalised)

- Grammar: '... large apertures, WHICH has led ...'
- Readability: '... That is the sharp area of focus ...'
- Readability: '... apparent narrow depth of field is lost, figure 1 ...'
- Readability: best to define the Circle of Confusion (CoC) *immediately* after it is introduced in Section 3.
- Readability: the CoC could be explained more clearly in Section 3.1
- Readability: caption for Figure 2
- Style: figure 1, figure 2, etc should be Figure 1, Figure 2, etc
- Style: best not to begin figure captions with labels (a, b, etc)
- Style: there should be a space between citation numbers and preceding text:
'... an all-focused image[2] ...' should be '... an all-focused image [2] ...'
- Typos: extra bracket at the end of the 2nd equation on page 4
- Typos: '... whilst we examine the a larger frequency space.'
- Typos: '... the frequency content of ITS border ...'
- Citations: the first citation (Wikipedia) has not been made correctly

---------------------------- REVIEW 2 --------------------------
PAPER: 21
TITLE: Blur Preserving Image Resizing

OVERALL RATING: 2 (accept)
REVIEWER'S CONFIDENCE: 1 (low)
Audience Appeal: 5 (Easy to follow and read with minor points remaining unclarified.)
Significance: 4 (Interesting work which will probably be cited even if it does not shake the field of research.)
Originality: 4 (A minor or incremental improvement to existing work that is not immediately obvious.)
Presentation: 5 (The paper is well structured and can be fully understood. However, some sentences are badly or awkwardly written.)
Validity: 4 (Valid, relevant approaches are made, but they are not convincing or may be a little impractical.)
Recommendation: 5 (The paper is good and should be included.)

Please provide a response to each of the following queries:

1) What was the paper about?
This paper describes an image resizing algorithm that improves quality by
maintaining depth perspective.

2) What claims or hypotheses did the paper make (if any)?
This paper identifies that depth perspective is lost when images
are reduced in size resulting in a loss of quality. With a growing
number of collaborative image viewing sites where images are initially
viewed as a thumbnail the loss of depth perspective results in a loss
of quality in the resized images.

An algorithm is proposed for resizing images which maintains depth
perspective. The image is segmented, each segment is classified to a
depth using the frequency and then blurred to match the new size.

3) What are the good points of the paper? Why might it be accepted? What did the author do right?
I enjoyed reading this paper. It is a clear, well written paper with
a good structure that is easy to follow.

The problem being addressed is clearly identified and well described
both in the text and by example. Most readers will have practical
experience of this issue making the paper particularly relevant to
a general audience.

The paper makes good use of numerous examples to explain each stage
of the approach. This made it easier to understand the impact of each
stage of the resizing process even if some of the underlying technical
aspects were, by their nature, more difficult to follow.

4) What are the bad points of the paper? Why might it be rejected? How might the author improve their work?

My biggest issue with this paper is the evaluation. A new algorithm
is proposed with evidence of its effectiveness being left to the
reader by the inclusion of 4 sample images that have been resized.
I would expect to see stronger evidence to support the proposed
approach. While a quantitative evaluation may be difficult a user
evaluation should be possible and could provide evidence both that
the problem is important and that the proposed approach is a
perceived improvement.

The assumption that in focus object is in the foreground appears to
be a very limiting restriction of the approach. Although raised as
an issue in the conclusions, this issue was not discussed in sufficient
detail and merits more discussion on the extent to which this would
limit the use of the algorithm.

The abstract is OK as far as it goes but is too short. It should be
expanded to give, at least, an indication of the methodology adopted.

Please also provide a justification for the scores you have provided in each of the following areas:

Audience Appeal (1 - bad, 6 - good):5
Maintaining image quality on resized images is a subject area that
most of the audience will be able to relate to. This paper is likely
to be understandable and of interest to a wide spectrum of a general
audience. However, some aspects of the paper are understandably quite
technical.

Significance (1 - bad, 6 - good):4
The problem being investigated is clearly identified and appears to
be a genuine issue at least conceptually. However, given the lack of
a user evaluation it is difficult to judge the importance of the
problem and the extent to which this work solves it and improves
the quality of image resizing.

Originality (1 - bad, 6 - good):4
The work appears novel. Perhaps not in the broad approach used but at
least in the combination of techniques used and for the specific
application addressed in this paper.

Presentation (1 - bad, 6 - good):5
This paper is well written and has a good structure. Typos and minor issues
are listed below - although very few.

Validity (1 - bad, 6 - good):4
The methodology adopted appears fine and its success is demonstrated by
the inclusion of a number of sample images shown at different sizes.
However it is difficult to quantify the success of the approach on a
small number of images. A larger evaluation would provide more evidence
to support to the approach.

Recommendation (1 - bad, 6 - good):5
Overall a solid piece of work that merits a place in the conference.

Any other comments to make to the authors:

Typos and minor issues:

page2para4line4: "Alternatively[11]" --> "Alternatively [11]" numerous other examples
page2para8line7: "examine the a larger" --> "examine a larger" ?
page5para1line3: "from [9]" --> " from [9]"
page9para4line2: "allow the" --> "allows the"

---------------------------- REVIEW 3 --------------------------
PAPER: 21
TITLE: Blur Preserving Image Resizing

OVERALL RATING: 2 (accept)
REVIEWER'S CONFIDENCE: 2 (medium)
Audience Appeal: 4 (A typical CS honours graduate will fully understand what the paper is about, but is unlikely to understand all the details.)
Significance: 4 (Interesting work which will probably be cited even if it does not shake the field of research.)
Originality: 4 (A minor or incremental improvement to existing work that is not immediately obvious.)
Presentation: 4 (The paper makes sense and the story is intelligible. However, the structure or grammar is sub-optimal, potentially making it frustrating to read.)
Validity: 5 (Valid, practical, relevant approaches are made and are probably correct but may not be concrete.)
Recommendation: 5 (The paper is good and should be included.)

Please provide a response to each of the following queries:

1) What was the paper about?

This paper proposed a new method to extract depth information from a sigle image, which was used to resize the image while the blurriness caused by our-of-focus was maintained.

2) What claims or hypotheses did the paper make (if any)?

The authors claims a technique to calculate depth values for an image.

3) What are the good points of the paper? Why might it be accepted? What did the author do right?

The results of the work are well presented and the related work are clearly stated.

4) What are the bad points of the paper? Why might it be rejected? How might the author improve their work?

Please also provide a justification for the scores you have provided in each of the following areas:

Audience Appeal (1 - bad, 6 - good):

The paper is clearly structured and easy to follow. It may be of interest to researchers in the fields of Computer Vision and Image Processing.

Significance (1 - bad, 6 - good):

The contribution of this work may be considered incremental in nature.

Originality (1 - bad, 6 - good):

The work has some novel aspects including the segmentation of the iso-depth region.

Presentation (1 - bad, 6 - good):

The paper is well presentated and each section is clearly linked.

Validity (1 - bad, 6 - good):

The results showed in the paper are strong evidence to the validity.

Recommendation (1 - bad, 6 - good):

The paper should be accepted.

Any other comments to make to the authors:

procedural Inc are looking for a computer vision expert!

2010-03-05T23:25:00.003Z

Source.

Procedural create CityEngine, one of the few useful procedural urban tools around. Does this mean that they are looking for an easier way to create models of buildings? Reconstruction from street photographs? From aerial photographs? Why not from existing meshes (from video game artists)?

Image-based Street-side City Modeling (pdf) from Sigg09 shows some of the potential of this direction.

I'll be looking forward to seeing what these guys do next.

first year report

2010-03-03T16:08:00.000Z

Sorry, it's been a little quiet around here recently. One of many reasons is that I put together my first year report (updated pdf). Notes:.

[edit] Having taken criticism from blog readers and supervisors alike, I've updated this. Some of the cut bits appear below - if you've already read it, don't bother reading it again, nothing significant has changed.
Some of the more interesting results from my time at ASU have been cut for client confidentiality. This is getting quite annoying now, will try not to fall into non-disclosure hole again.
It's mainly a bunch of blog posts end on end.
It isn't really of the quality required for a thesis.

Bits that didn't make the cut:

Possible Theses

Here I present a few possible directions that I see my work progressing in. Because of the new ground that is being covered, posing these direction as theses is a little artificial at this point.

Procedural Workflow

Useful procedural systems can be constructed by non-technical users
Three dimensional modelling packages such as Wavefront's 3D Studio Max or Maya present artists with very complicated interfaces for the creation of 3D content. These systems include data flows, such as 3DSM's hypergraph which allows different properties of a material to be edited, and construction histories. It should be possible to build a system of similar complexity, that can be used by 3D artists to enable them to build procedural objects. This would involve investigating subjects such as intelligent primitives (such as blobby objects or z-spheres), the generative modelling language (GML), and current 3D workflows.

Reverse proceduralization

Reverse engineering real world or artist created objects allows for effective proceduralization of geometry
From a design perspective reverse proceduralization, or reverse engineering allows artists to use their current tools to create a single instance, and then perform proceduralization as an after-thought. This would give the easiest integration into the current workflows of all proposed procedural solutions. Study in this subject would involve machine learning techniques to extract form from designs, after sufficient pattern-analysis has been performed.

Floating Point Robustness

It is possible to perform robust geometrical computations in a floating point environment.
One of the upshots of my work with the straight skeleton and the Voronoi tessellation is the realisation of how hard it is to work with geometry in a floating point environment. I found that the vast majority of my time was concerned with robustness issues. For example a point that is on one side of a line can appear on the other if the calculation is repeated with an indentical line travelling in the opposite direction.

There are well known limits, within which standard geometric queries fail to behave in a predictable fashion. The result is quite chaotic, and makes designing robust algorithms both time consuming and bug-prone.

There are several attempts to make computational geometry more robust, but I've found none to make it easier. The ideal goal here would be to create an library that an undergraduate could use for robust geometric manipulation, in place of CGAL or similar.

emergent behaviour papers

2010-02-11T11:18:00.008Z

After this (bbc) fantastic documentary, I thought I should restart my reading in this area. More to come!

Computations at the Edge of Chaos: Phase Transitions and Emergent Computation (Physica D | pdf | bib | 2002 )
Chris Langton

This paper examines the behaviour of Cellular Automata (CA) as one property of their rule-set changes. It is the first description of emergent behaviour occurring somewhere on the spectrum from a dull, homogeneous environment to a random, chaotic one.

The variable that is changed is lambda, a statistical variable saying how likely it is to end up in an "active" state. That is, what fraction of rules lead to a cell becoming active. As the above image shows, as lambda changes, so does the typical output patterns. These changing patterns are what first attracted me to the paper (useful for procedural?!), but the real significance is that really interesting patterns only occur for a limited range of lambda values. Too low and we don't get anything happening (deep space), too high and all we see is Chaos (center of the sun). Between we get "just right", where interesting CA's live.

Computationally we see that we need storage and transmission to get interesting systems. Storage leads to homogeneous environments (low entropy), and transmission to chaos (high entropy). Both are required for meaningful computation, and we only see them both in small parts of the range of possible CA's.

This paper caused me to put A New Kind of Science onto my must-read list.

Reverse engineering of spatial patterns in cellular automata ( springer | pdf | 2008 )
Yuuichi Ichise & Yoshiteru Ishida

This is a short paper that describes how to reverse engineer a CA from the results. They use the algorithm that you'd imagine, taking each observed result and filling in an entry in the rule-table. They also explore reverse engineering probabilistic CA's by accumulating the observed instances of each each particular rule. In both PCA (probabilistic cellular automata) and CA's case they return a CA with unknowns in the case that there is no example data. The important observation is that if there is insufficient data, there are a set of CA's that will reproduce a given pattern.

evaluation papers

2010-01-22T20:54:00.003Z

There are many questions around evaluating the results from procedural graphics. I while back I wrote up the following notes about a couple of evaluation papers from recent graphics journals.

How Well Do Line Drawings Depict Shape? ( pdf | web | acm | 2009 )
Forrester Cole, Kevin Sanik, Doug DeCarlo, Adam Finkelstein, Thomas Funkhouser, Szymon Rusinkiewicz, Manish Singh

This paper is the reverse of last year's attempt - it asks a sample of people to guess the curvature of a set of objects from line drawings.

however there is little scientific evidence in the literature for these observations. Moreover, while a recent thread of the computer graphics literature devoted to the automatic algorithms for line drawings is flourishing, to date researchers have had no objective way to evaluate the effectiveness of such algorithms in depicting shape.

There are a bunch of different ways to generate contours for an image:

suggestive contours - marginal occluding contours (appear with small POV change)
ridges and valleys - local maxi-minima of surface curves
apparent ridges - view dependent ridges and valleys

Bonus points for mentioning Team Fortress 2 and using NPR (non photorealistic rendering).

Psychophysics defines a gauge figure - a 2d representation of a thumbtack with the spike giving the normal direction - there's a body of previous work of asking people to guess normals from outlines etc... These are the little brown dots in the above image.

The study then involved asking 560 people to position 275,000 gauges on different line drawings, to get an idea of the perceived surface direction.

An interesting idea here is the use of Amazon's Mechanical Turk to get lots of people to participate in the activity, in return for a micropayment. Basically there is very little control over the environment in which someone encounters the game -

there may be someone at the next desk playing the game, so you might be able to sneak a look at other representations of the same object
there might be all sort of distractions (cat walking on the keyboard)
visual display will not be calibrated in the same way (different gamma curves may lead to different perceptions of normals?)

However, these situations are quite rare and more than likely compensated for by the large volume of data produced. It's kind of exciting that this method of data collection is considered scientific enough for publication.

The study compensates for the "bas-relief" effect (assumed projection by the viewer) by scaling the results to a standard depth.

The results look solid - more ambiguous figures had a higher deviation from the median surface normal.

The occluding contour technique was worse than the others, with the other line drawing techniques being about equal. Comfortingly a 3D rendered/shaded image gave better results than all the line drawings.

A more detailed analysis of contentious areas of the models was performed and gave the interesting conclusion that sometimes and artist's representation was more reliable (the above computer generated image of a screwdriver has dark brown gauges showing ambiguity in the surface direction), but sometimes they over did it and gave the wrong impression. In these cases the computer generated outlines were better.

Wilcoxon/Mann-Whitney is a non-parametric test for comparing distributions that I hadn't stumbled across before.

Toward Evaluating Lighting Design Interface Paradigms for Novice Users ( pdf | acm | 2009 )
William B. Kerr, Fabio Pellacini

It turns out there are a few interfaces for defining lighting in a 3d scene:

direct (Maya/3DSMax style) - drag lights around
indirect - drag the shadows, edge of lights, and their results around
painting - a constraint solution that optimizes the light's position to make the scene look most like a sketch you just coloured in (above, right two images)

This paper evaulates these different techniques, as used by untrained people. They ask them to match the lighting in an example (same geometry, rendering etc...) and in a still frame from a movie onto simple geometry.

20 people are used, with 5 hours use per person (include warm up time...). The error differences between the rendered scenes are compared for the exact-match trial, while the movie-scene sections are evaluated in a more subjective manner. The results are also recorded over time, allowing the authors to graph how long each technique takes to converge.

They also do a questionnaire:

Natural way to think about lighting
ease of determining what to modify (selection)
how it should be modified (intention)
carryout the adjustment
preference on few lights
many lights
preference in matching trials (goal image)
open trials (no goal image)
overall preference.

The general results was that the newer technique, painting doesn't do so well, and that direct and indirect illumination are better. Between direct and indirect, indirect gets to the result fastest.

The two statistical tools used are

Repeated Measures ANOVA (book)
Friedman test

but which is procedural?

2009-12-04T16:21:00.005Z

Comparison of a procedural city and a photo of a city: which is which? How long did you have to look?

The procedural image (of a reconstructed Pompeii) was from Procedural Inc (right), the photo was by mharrsch (left). Highlight this paragraph in your browser for the answer! Filter was a quickie "photocopy" in gimp.

The lack of real scientific method in computer science is quite apparent in fast moving and new fields, like procedural modelling. Evaluating procedural content has been an ignored subject in the journals, there is very little said about the quality or the believability of the output of a procedural system. In contrast lots is said about the number of processor cycles or the lack of artist involvement. This a sketch of a project that hopes to address this issue. We can the above idea turn this into a web-game (similar to the google image labeller game) that challenges people to spot the fake photograph in a certain time, and rewards them with points for being right.

Going even further we can build a competitive game that find the realistic and unrealistic areas of an image by asking you to attempting to fool your opposition. The computer invents a goal ("prove to your opposition that this is a real photo"), and you get points for doing it. The more of the image you reveal, the less points you get. When it's your turn, you see an image slowly revealed as your opponent reveals the bits he can see. You have to decide if it's a photo or a render (in this case). It could create a "believability" map of each image by examining the areas scratched off by the subjects. The following example just asks the user to distinguish between a render and a photograph but by using a filter that obscures the geometry (such as the photocopies in the above example) it would be possible to compare procedural & artist-defined geometry.

Images for this were stolen from this guy. Video (or on youtube):

You can play a simulated ("offline") version of this game by clicking here (Java 1.6 needed, binary file - run at your own risk). Your own moves are played back when it's your turn to guess. There is an option to add image noise to make the game harder to play.

This is one of the most promising avenues of exploration I've thought of when it comes to evaluating procedural modelling systems. Of course it is very hard to count the contributions from the artist and from the procedural mechanisms. To solve this some sort of test of artist generated geometry against procedurally generated content may be called for. In both cases we would record the quantity of programmer/artist time taken to create a scene, and then evaluate it. The hope would be that the procedural models show comparable realism, while absorbing many fewer man-hours.

Future ideas:

Could do this for videos
Could render examples from a procedural model in real time, get feedback on them, and update the model automatically. This kind of technology ("which parts of these models represent the door knobs that the guy scratched out?") is a few years away yet...
Add in distractors (trees, people, lens flare, motion blur) to allow a fair test against a random selection of architecture photos (from flickr, say).

Let me know if you think this is an interesting project, and have some ideas for carrying the idea further. It should make a half decent paper when written up.

One of the biggest problems with this is that there aren't many examples of detailed procedural models. The Pompeii examples from Procedural is a couple of years old and is still one of the best/most complex examples. As the above image shows, it is only just detailed enough to make this test plausible. I had to hunt around on the web for a while to find a photo of Pompeii without too many people/clues etc... to make the above a reasonable comparison.

It's getting harder and harder to tell rendered images from photos, if you look at the top right of this image of houses in Glasgow (park circus), it's hard to tell it's just a photograph. The houses were being refurbished, so no people to leave distinguising features, and they had just been cleaned using sand-blasting.

skeleton project progress

2009-12-02T22:42:00.002Z

[straight skeleton post index]

I can't say a lot about the skeleton project*, however, we got a very rushed paper together that was rejected, but we got some nice renders (and a whole bunch of feedback) about on the work. A few sneaky pictures follow :) as ever, they were all made with the blender render template I've made, and rendered in yafaray. Basic idea is a straight-skeleton based rapid prototyping tool for architecture. At a stretch it could even be called procedural.

I was worried the paper-reviewers would complain about the artsy backgrounds to the renders, however that was the one part of the work that wasn't panned. Most of the backgrounds were my own photos, many from this flickr set.

Something that took longer than it should have, but really makes these renders special is the tiling. Each tile on the roof is a polygon, and it basically involved writing an old-school rasterizer so each roof edge could position it's tiles. Never got around to creating tiles for the roof edges tho - so it looks like they are all made out of cardboard, which is really cute and make them look like real architectural models.

*that's one thing about working with collaborators, I've got to protect their investments as well as mine. Yes that means we're going to make this project even more awesome and try again.

higher dimensional skeletons

2009-11-19T17:45:00.002Z

[more straight skeleton posts]

from Weighted skeletons and fixed-share decomposition ( Aurenhammer | 2007 | ps | doi )

Higher dimensions

The concept of weighted skeleton (or weighted medial axis) is not limited to two dimensions. Given a convex polytope P in Ęd and an assignment of positive weights to its facets, a unique convex cell complex inside P can be defined, either by the respective shrinking process, or based on weighted distances to the hyperplanes that support P. In fact, the decomposition and optimality results presented in Section 3 and Section 4, respectively, directly generalize to higher dimensions.

Thusly we may draw:

Fun thing here is to compare what happens through the dimensions and see how high you can go before your head explodes. Also what the procedural modeling ramifications of each step are.

very dull video of the sony cw

2009-11-07T09:24:00.005Z

Here's a long, uninteresting video of the Sony Vaio CW booting Ubuntu (64 bit, wifi not a problem, but the video took a little work for the nVidia drivers how to in this post), then it shows the splash-top an instant-on web browser (that takes about to long to boot as the other operating systems take to come out of standby). This works well (flash videos play fullscreen), and I wave the screen around a bit to show the not-so-great viewing angle, but great brightness compared to my old powerbook laptop. Finally we see it booting windows 7, which is very pretty and does everything it should do.

What I didn't manage to show was the rattling battery. There's half a millimeter or so of space around it, and it doesn't lock into place properly. You don't notice it when you're using the laptop, but it's annoying when you're packing the laptop up.

Still really liking this 'top. A bit to much shiny-toy plastic, but generally responsive and enjoyable to use.

Video was taken inside, with indoor lighting, on a canon 500d. Sorry for the shaky bits.

[edit:] One year on, and generally I've loved this laptop. It now runs only windows (*nix is for work, windows for play), for video games. But just before the (international!) year's warranty ran out I had to get the the screen and the power-socket on the laptop fixed. The screen was graying out when you moved the monitor and it suffered from the classic Vaio fault of needing the power lead held to one side to charge. I was, however, impressed by the speed and ease of the returns process tho (apart from the premium rate number you had to call to arrange collection).

sony cw "notebook"/laptop first thoughts

2009-10-29T05:07:00.020Z

[video here]

It's a bit early for a full review, but here are some of my first thoughts about this shiny machine. I decided I couldn't justify a mac this time, so I got a Sony CW with 4Gb memory, a nVidia GT230M and the Core 2 Duo T6600 2.2G. This is a replacement for my 12" PowerBook G4, so there'll be some unfair comparisions to a five year old machine. After not giving us Java 6 for powerPC's and having the mac repaired 4 or 5 times, I didn't think all the shinyness was worth the 50% price premium. For a 15% premium I can get a Sony machine! This was written roughly in the order that I experienced it.

old mac on the left, new sony on the right (bigger)

Unboxing - okay, so sony isn't apple. The box was a little goofy - the logo on the top is upside down when you figure out how to open it. The box then unfolds like a crab, before throwing the power adaptor and battery onto the floor. A couple of slim manuals, but no CD's in the box - guess there's no chance of a windows reinstall then. Academic Alliance (aka "the please don't use linux fund") to the rescue.

That's all there is in the box. On my bed ;)

I managed to fumble and push the "web" button on the laptop after installing the battery. After a couple of seconds pause, it booked to the spashtop (a linux distro running firefox?) very quickly. The browser was quite active and functional - happily playing youtube videos. Hopefully this will make running Ubuntu easier as there have to be drivers around.

The keyboard is great - not quite enough travel on the keys but very spacious and mac-esque (except the funtion and control buttons have switched place again!). The key-letters look a bit stuck on, and I'm sure they use too many fonts over the front of the computer for my typographic sensibilities. Just the usual range of garish stickers next to it. I wonder what it'll take to get them off... I've just come back to the paragraph, from the future to say I really like the keyboard :) Since this is going to be a coding machine, it's a good thing too.

Something strange about the delete rate - it removes entire sentences beforewith a light touch. I'm sure there's a setting somewehre to fix it. Ah yeah, in the Vaio settings, it's turned up all the way...

So just the usual keys on the board, plus four little ones under the screen (photo above) - a display-off button that seems to kill the (LED) backlight, a "Vaio button" that when I pushed just now started installing Sony's Media Gallery software, that then started probing my network for new media...won't do that again. The "web" button in windows seems to close the tab that I'm using to write this blog post and take me to Chrome's homepage. When the computer is off, the web button starts the nix splashtop for quickie web browsing sessions. I think they can all be remapped.

Trackpad is a little unresponsive compared to the mac, and doesn't seem to do multitouch (edit: thanks anon commenter - it does multitouch - it's just well hidden, and no nice two fingered scrolling) gestures, but decent enough. The right hand side of the pad does scrolling, but it seems a bit unsensitive (and brings up a really ugly mouse cursor in windows). In Chrome scrolling jumps down the screen, but in IE it's smooth but feels like there's quite a bit of lag.

Wifi reception is great, the splashtop found a bunch of networks I'd never seen on the mac and the reception seems decent enough. Seems to stay quite cool too, as long as you don't spin that graphics card up! There are some quirks with the splashtop setup - the keymapping is wonky (@ and " are reversed, but since I alternate between keyboards with both conventions, it's easy enough to ignore) and if your laptop is in hibernating (doesn't work at all if in standby), it doesn't record your history. Also (as noted in the comments) there's no brightness control.

After a restart the Windows7 desktop came up there was a nice suprise - google chrome was installed by default! Take that European Commission :)

Some random sony rubbish, like the choice to get the "Sony" theme on the default home page (is this the reward from google for bundling with chrome?). .

Windows 7. Not really a fan of windows in general, but it hasn't got in my way yet. It even looks quite pretty. Apart from a crash the first time it booted (well i did shut the lid as it was booting - i had to look at the shiny case one last time), I've rather enjoyed it. Still I'd rather not run the thing until the first service pack (50Mb of urgent updates already....), will get going on Ubuntu later today. I think windows is still running NTFS, so should be able to share a big partition between the two.

Next up was putting the graphics card through it's paces. It's a nVidia GT 230M behind that beast of a vent on the left hand side, since I do a fair bit of graphics I thought it was worth the $100 upgrade to a card that could at least pretend to do 3d. Best thing is it can run Cuda code - that might be useful in the future. DirectX wasn't isntalled (strangely enough - surprised it isn't part of window these day). The Medusa demo from nVidea ran at between 7 and 20fps. Tho mostly 7fps. I guess this would improve with some updated drivers, and after nVidia has a chance to figure out Windows7. But it still looked mighty impressive on screen.

Having some issues with the charger - after i installed some windows update it complained about low battery, and however i giggled the charger, and whatever i plugged/unplugged it wouldn't charge. I brought it into the kitchen, and restarted and it seems fine now. Ah, got it - the led on the power brick takes a long time to go out, just need to fight a tighter fitting wall socket!

Screen is impressive, the LED backlight makes a real difference, and the brightness is comparable to the screen on my desktop machine. Not sure I like the glossyness, I suspect it's a ploy to get you to buy a screen filter, but it's what all the cool kids are using so I guess I'll have to get used to it. It's going to take a few weeks before I know that I like the widescreen format, but movies look awsome on it! The HDMI out is enough to drive my 24" monitor with the right cables.

Hmmm.... all those little sticky labels that come on a new laptop have very different levels of stickability. The energy star and windows7 came off easily, the nVidia one was a bit more stubborn, but the intel one left a nasty glob on the glossy surface that's going to take some detergent to get off property.

So already it's covered in fingerprints, but that was expected, so I'm not too concerned. My gear tends to gets used, so I'm not going to complain again a few prints. It's also picking up white cat hair like there's no tomorrow, but I guess that's my fault for not ordering the white one. Who knows why i would want the red one - chronic nose bleeds?

Theres not much bloatware at all - jsut the usual MS office trial and a couple of antivirus trials. And there are actually useful apps like acrobat reader and Chrome already installed. But there is a fair bit of marketing pomp. I'm now fed up with the Vaio logo (it's everywhere) and there's a strange button on the start bar that brings up a screen that announces that it's a "Sony Vaio CW series with Virbrant color inside and out", and tells me how much it weighs. I don't think it's got a weight sensor (am now pushing on it to make sure).

Sleep works nicely - it suspends in a couple of seconds and comes back when you press the power button.

I can't quite get used to the two USB ports on the left hand side being toward the front of the computer. I'm used to holding onto the computer there. I guess they got moved forward to make room for the massive (gpu?) vent on theleft side at the back - This baby's much wider towards the back than the front, and this makes for nice photoshoots, and makes it feel smaller than it is. It also slopes the keyboard toward you a little, but this isn't really a bad thing.

Overall the build quality is decent, not quite a unibody mac, but I wasn't expecting it. It looks like it'll take the shocks and spills that I'll no doubt give it. Everything feels very rigid, with a bit of give in the wrist rest, but not a lot. Speakers aren't up to much. System is real quiet, so you really notice when that CD/DVD (there's no way i was paying for blue ray drive) drive spins up.

Final word: so far it's exactly what I hoped for. With a decent screen :)

Comedy quote from the control panel - "Using a white color for your desktop saves power" - Hold on, you're telling me that it uses less power to emit more energy?! This LED technology is going to take some getting used to!

[edit:]
Now have it set up nicely to boot Ubuntu as well as win7!

symmetry papers

2009-10-27T13:29:00.001Z

Symmetry is a very much under-explored area in procedural modelling. Here's some papers talking about things you can do with it.

Constructing Regularity Feature Trees for Solid Models ( doi | springer | 2006 )M. Li, F. C. Langbein and R. R. Martin

"Reverse Engineering" is a phrase I normally associate with software engineering, but in the geometric-meaning of the word, it's used to describe recovering the structure from a model. Typically, given a mesh, you want to find out which primitives were combined to create the mesh.

This paper takes the approach that you have a 3D mesh and want to recreate the constructive-solid-geometry primitives and operations used to create that mesh.

The idea is to identify recoverable vertices, edges and faces that the original mesh hints at. These might be external to the volume defined by the mesh, or internal. This is done by intersecting existing features (such as edges or faces) to recovered features (such as vertices or edges).

There's an additional note that gives more credit to Leyton's book.

Partial and approximate symmetry detection for 3D geometry ( pdf | web | doi | video | 2006 )
Niloy J. Mitra, Leonidas J. Guibas, Mark Pauly

The idea here is to define the symmetry as a set of parameters that we can define as points, and then cluster, to reveal the strongest symmetries. For example the equation of a line when looking for 2D reflection symmetries. These parameters can then be clustered and analysed for density to find the most common symmetry constraints. This would give an O(n^2) algorithm in the number of points analysed, however by quickly rejecting pairs biased on the local features (eg: the normals around a point aren't symmetrical over the proposed symmetry line), the number of points to compare is reduced by an order of magnitude.

Mean shift-clustering is used to merge nearby points. This walks uphill on a landscape of Gaussian-splatted data points. Because the Euclidean symmetry space used is 7 dimensional, there is little chance of the maxima converging. Clustering is needed because noisy input mesh is rarely perfectly symmetrical.

To identify mesh patches from the located point pairs, corresponding pairs of input points are grown outwards while the symmetrical surface is within a given tolerance.

As the number of possible symmetries increase, it is desirable to compress the required symmetries to a minimal set. For example two "translate by 10" symmetries should be expressed as two "translate by 5" symmetries. This is process is referred to as "finding a reduced symmetry basis" (frame image, above).

Convincing results, such as the decimation of the above castle mesh to 14% of it's original size (transparent boxes are removed data) make this an interesting technique.

Discovering Structural Regularity in 3D Geometry ( pdf | doi | web | 2008 )
Mark Pauly, Niloy J. Mitra, Johannes Wallner, Helmut Pottmann, Leonidas Guibas

This is an extension of the previous paper (Partial and approximate symmetry detection for 3D geometry, above), presented a few years later. They use the symmetry matching techniques developed to reconstruct data from scattered point samples.

We only consider scale, rotations and translations using one or two parameters - this assumption nicely decreases the number of degrees of freedom to compute. By identifying repeated patches, and accumulating the possible transforms, it is possible to identify the parameters of the transform, even in noisy data. The paper discusses these as "generator functions", that take one (below left four examples) or two (right three examples) parameters, as the basis for symmetry.

A set of random patches from the surface are grouped according the their local feature descriptors (polynomial fitting of osculating jets). Each of these are then locally aligned, and analysed in a cunningly designed space such that their two parameters will be revealed in a lattice (below in one dimension). By plotting all the found dimensions, the most frequent transform (T) becomes the most plotted location. We know the identity transform must be a member of the set of generator functions, and this limits the search space. An energy minimisation function/RANSAC is then used to identify the lattice.

The results include reconstructing a castle and the Colosseum from partial point cloud data.

Symmetry Detection Using Line Features ( pdf | doi | web )
M. Bokeloh A. Berner M. Wand H.-P. Seidel & A. Schilling

The above papers cluster symmetries to identify them. However if two different symmetries are clustered together in symmetry space, they it becomes very difficult to separate.

The routine take a cloud of points-with-normals and create feature identifiers, then then run a couple of loops through these identifiers looks for similar clusters of points to call symmetrical.

The first step Poisson down-sample the input cloud to find points with one linear degree of slippage locally. That is they search for extruded (elongated) features, such as the edge of window frame or column. These are locally clustered into bases, non-slippable graphs of local features. A RANSAC-like algorithm is then used to find similar bases over the model, while flipping a couple of the coordinates to account for mirroring. The features' curvatures are compared between bases to find compatible bases. Region growing maximizes each of these regions, and a geometry matching stage ensures that the base abstraction really matches the input point set. Because of the simplicity of the bases, and their tendency to be localized, many comparisons can be made.

Once symmetry has between detected, the usual things can be done - holes filled, missing sections reconstructed, and data compressed.

The system doesn't really find nested symmeteries, just repeated instances or flipped instances.

Very curiously, in future work these guys mention

In future work, we would like to build morphable statistical models of symmetric parts to better represent subtle variations beyond the accuracy of the region growing algorithm

which is one of the thoughts I've been having a lot recently for generative, rather that reconstructive procedural modelling.

accelerating the straight skeleton

2009-10-06T16:50:00.002Z

[straight skeleton post index]

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

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

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

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

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

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

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

skeleton index page

2009-10-06T10:52:00.012Z

Round up of straight skeleton related content on this blog, roughly ordered by interestingness.

Oh, and the image on the wikipedia page is an old one of mine.

matte renders in blender

2009-10-05T14:36:00.002Z

This post is in response to a professor saying that it is hard to get students to make nice (publishable) renders. It isn't! There's a few bits of theory you should know (colour theory, basic lighting setup, rule of thirds, global illumination) but you can mostly fake it by borrowing other people's work, such as this this template for getting nice blender renders...

So getting a nice render out of blender takes a little tweaking. Here's a ready rolled blender scene and demo video for getting nice matte-white light-box renders with global illumination. Grab this template file here, and follow the video, or the following instructions.

First grab: blender, yafray and the gimp.

In linux, something like this:

sudo apt-get install blender yafray gimp

In windows, go to the websites and install (haven't checked that this works for yafray yet...)

Then start up blender. Load the template file. Delete the house-like thing you can see by right clicking on it, and pressing the delete key, and answering ok to the pop up box. Import the object you want to render. Obj is an easy format to work with when there's no textures. File->import->Wavefront(obj). There's a tutorial on moving stuff with blender here, otherwise select the object you want to move and use 'control-shift-g' to bring up the control widget, then left click and drag to move it around. "control-shift-r" (who makes up keystrokes like that?) for the rotate widget, and "control-shift-s" for scaling. The viewpoint when editing (not the camera) can be moved using a combination of control, shift and alt together with the middle mouse button (or tutorial here). To view the scene from the camera's pov, use the '0' key on the keypad (or view -> cameras -> camera).

This is the beast-of-a-render-panel:

After setting the aliasing quality (1), and the percentage render size (2), you can choose the frame ratio (3), before rendering (4). The combo box directly below the render button ("Blender internal" selects the renderer - in the example file it's set to yafray). At this point blender looks like it's crashed (if you're using yafray). After it's rendered (can take a while - go get a strong cup of something) push F3 with the output window selected to save in the format dictated by combo box (5).

You probably want to do a low quality render to check the details, before doing a full one (waiting 20 minutes just to find out that the top of the model is clipped is kinda annoying).

Once you've got the render, you probably want to open it in the gimp, and use colors -> adjust levels to get the exposure right for your medium (print, web etc...). Then save out the final image.

orthogonal basis transform

2009-07-16T20:39:00.006Z

Here's a trick I learnt from Strang - to convert (rotation/translation) between two arbitrary frames:

convert both to orthonormal bases (A,B above), ignoring the translation component for now.
use the inverse == transpose trick to find the inverse of the first transform (A^T), then apply (multiply by) the second transform(B)
(...fudge the translation component (not shown)...)

It's even better if you want to axis-align something, you just need the transposed matrix. This got a post of it's own because I've been told by several professors over the years to move it to the origin, calculate the x and y rotational components and multiply together - this takes lots of multiplication, and you end up with a hideous zombie-like matrix.

The transpose is equal to the inverse only if it's an orthonormal matrix - to project vector line onto another, it's a simple dot product. What's more each axis in an orthogonal frame is independent, so that's all we need - 9 dot products, or one matrix multiplication.

a couple of procedural facades

2009-07-06T15:20:00.001Z

A few weeks back I put together these two as examples of how to create a procedural facades from a static facade image.

This image is from the fantastic project from Washington. They had a project to stitch images, and were good enough to publish some hi res street fronts. Charleston, South Carolina:

The second image is of the willard hotel - around the corner from the White House (image by dbking):

Some of the issues that came up:

There is a limit to how far you procedural-ize. For example, windows in the above were atomic units. Tricks like content aware image resizing (seam carving et al) might help do this automatically.
How do we tell if an element should scale or repeat with size? should some elements keep the same size and others be scaled relative to each other?
In the vanishing case (as the facade become small) which elements disappear first?
Negative space often plays a part (first met this concept in latex)
Many different schemes for layouts (see Java's Swing for lots of examples) - only one data point (the input image) which do we use?
Conflict between top-down (layout downwards - space subdivision at each step) and bottom up (components know how big they should be, eg a window, rather than a side of a house, knows how big it should be). Similar in principle to top down vs bottom up design arguments
Many features to balance, and everyone's goals are different - feels a lot like software engineering.

phd insanities

2009-07-06T05:36:00.007Z

Every house I see has me trying to model it procedurally in my head. This is really driving me insane. Perhaps it's time for a holiday. How about the roof windows on the family guy house? Why doesn't it have any guttering? Why do some windows have shutters and others don't?

then ASU has buildings like this - did the tree come first and they built the house around it? Did the tree grow through the gap?

phoenix weather warning

2009-06-09T22:59:00.003Z

Hmmm.... turns out that storm cloud on the google homepage that means "it'll piss down all day" in Scotland means "10 mins of drizzle" in the desert. Well...you know...one thousand words for snow and the rest of it.

semantic deformation

2009-06-08T10:15:00.003Z

Last week I did a rather slap-dash job at presenting Semantic Deformation Transfer ( pdf | acm | 2009 ) by Baran, Vlasic, Grinspun and Popović. I didn't do a very good job, but here're the slides:

There are typos in the document. It says re-encoding the base pose doesn't give the base pose, when the paper says it does. I think I meant that they don't show re-encoding an arbitrary input pose.

The videos are missing from the presentation, they can be found

Semantic Deformation Transfer
Deformation Transfer for Triangle Meshes
Linear Rotation Invariant Coordinates ( missing link, or shoddy acm streaming )

and here:

Spotify

2009-06-07T21:10:00.002Z

Am a bit of a fan of spotify and am just jotting down some experiences of using it abroad. I signed up while in the UK, and was happy enough with the service (even if they kept increasing the number of adverts). It worked through the notorious Glasgow University proxy (after some tweaking) and had a large enough selection of music for me (if not my obscure-scandinavian-rock-loving brother).

When I moved to Arizona, spotify continued to work...but the adverts stopped! So I'm getting the 10 pound per month premium service for free. (Even though it doesn't seem to hard to circumvent, even from the UK) This is really strange - if I'm on holiday why not just serve me British adverts? I guess they're preparing for their US launch.

The service abroad stops working every two weeks. But you just need a friend to log in for you (or know the correct tunneling incantations) to log in via a UK ip adress (see notes on the notorious Glasgow University Proxy).

misc. architecture papers

2009-05-26T13:41:00.000Z

Some of the recent paper's I've browsed on procedural urban modelling and tangential subjects.

Detailed Building Facades ( doi | pdf | ieee | 2008 )
Dieter Finkenzeller

This is a procedural system that uses two separate geometry trees, one for the course model and one for the style.

The course system starts with a floorplan - this comprises a concave set of abutting polygons that represents the main building, a wing or a balcony. Apparently the concave condition is required when generating the roof. These are combined using union operations.

A floor plan like this is created for each floor of the building. At each height the user has the option to add, remove or subdivide one of these polygons (to add a balcony for example)

Cornaces (decorative moulding strips) are extruded from a sequence of paths and curves. Consoles are blocks placed along the Cornaces, that you can stick arbitrary meshes (gargoyles!) onto. Cornaces-cross sections are defined use a turtle-like grammar. This is also used to define the perimeter of doors and windows.

Roofs are either flat, or constructed using a ridge-placing algorithm. The single, central ridge is defined, and each corner of the floorplan is connected to the nearest end of the roof. The straight skeleton is rejected as it is unique (not that I'm biased towards that skeleton or anything ;) however all the shapes described could be produced using the weighted straight skeleton, and it would have worked on concave shapes).

The second hierarchy of geometry is for the style, the finer components, such as wall subdivisons or windows/doors (windoors) (I've visited this several times, and the abstracting is going to be quite useful, and can be extended to the general idea of a border/frame). The different components of the windoors are created by a multitude of cornice and frame elements.

After the entire semantic tree is produced, it is traversed by a geometry engine that creates polygonal output.

Inclined walls aren't supported, and a lot of use input is required to define the features of each floor of the building.

Affective scene generation ( pdf | doi | acm | 2006 )
Carl Hultquist, James Gain, David Cairns

The idea here is to infer from adjectives, the parameters to a procedural system.

Merry et. al. apparently couldn't get it to work (but didn't show any results), and there's a thesis by Polichroniadis (cl@cam.ac.uk) that describes a similar method for animation.

There are two massive spaces involved

The descriptive space - a set of adjectives, one for each axis of the space, and a value for each axis.
The model space - one axis for each parameter, and a value for each axis

The game is to find a mapping between these spaces. It's likely that the mapping is different from person to person.

The approach to solving this is via learning algorithms, in particular a neural network (of the radial basis network function variety - a one perception deep network).

The procedural world is generated using:

Landscape: Perlin noise
Trees: meshes
Sky: Coloured based on time of day
Clouds/Rain - Perlin noise clouds.

Current controlling adjectives are wet, sparse, tropical, cloudy, light, mountainous and undulating. Users are shown images and have to assign a real (0..1) value to each adjective for a set of test scenes. This trains up the neural network. This seems to work reasonably. There wasn't much more to this paper, except the results, above.

It's a afrigraph paper, and there's an interesting emphasis on technologies for developing nations with lower skill sets.

3d modeling for non-expert users with the castle construction kit v0. 5 ( pdf | vast | 2005 )
Gerth, B, Berndt, R, Havemann, S, Fellner, D W

These guys build a nicely interactive castle editor. Particular emphasis is placed on the internal representations used.

GML is a postscript like way of describing 3D models using a stack. It's a nice description because it's so flexible - functions can take an arbitrary number of inputs from the stack etc...
Open Scene Graph is another scene graph engine, with a decent feature list - it represents geometry as number arrays etc...

The two packages were combined in the expected way - GML is used for the local descriptions, and fitted into the scene graph as components. There's a little munging of data types between the two packages, but they seem like a reasonable fit.

There's an reference to an excellent looking book about churches and cathederals by Kotch (Baustilkunde : das Standardwerk zur europäischen Baukunst von der Antike bis zur Gegenwart). After recognising that castles are often on hills, they proceed to make castles on flat-ground.

Wall editing takes place via a set of handles (red things in the above images), one for each corner. The need for constrains on the handle positions is discussed - angles on walls shouldn't be too large, houses shouldn intersect walls (but be aligned to them) etc...

Out of context quote-of-the-day:

As it turns out a whole number of objects can be suitably represented by polygons.

Finally they say that they want to advance the work towards non-flat terrains and castles. This is actually a remarkable uncluttered topic in the literature, and looks like a promising area of research.

Here's a thesis talking about GML (in German).

The FL-system: a functional L-system for procedural geometric modeling ( pdf | doi | springer | 2005 )
Jean-Eudes Marvie, Julien Perret, Kadi Bouatouch

The paper presents a variation on the theme of L-Systems and applies the result to architecture.

There are a couple of useful additions to the parameterized L-System

A(n) → for(i = 0; i <= n; i + +) B

Describes a repeated element. This replaces the decreasing-parameter trick used previously. It's only syntactic sugar, but given how twisted L-system grammars become it's quite welcome.

The terminals of the grammar are functions that can evaluate to geometrical primitives (window/door meshes). These can be modified by the parameters of the system at a given time.

The system outputs geometry at many grammar depths (rather than the tradditional post-evaluation using a turtle) . Because of the implicit evaluation order of L-Systems it's relatively simple to stop evaluation early to construct different levels of detail (LOD). These LODs are made more efficient by sharing geometry.

The system is integrated with the VRML97 standard, using embedded scripts.

An example grammar is constructed that creates a town house using standard façade decomposition techniques.

The above image shows a few result - the three buildings on the left are procedurally derived from the same grammar, with different texture sets.

The more I read about these system, the more I'm convinced that traditional formal grammars are very much the wrong way to go. There's no way artist's will use these grammars, and artist's can't be limited to domain specific languages.

Creating models of truss structures with optimization ( doi | pdf | acm | 2002 )
Jeffrey Smith, Jessica Hodgins, Irving Oppenheim, Andrew Witkin,

The idea here is to construct truss structures (think Eiffel tower) by taking a set of contact points (above, left, cones) and load bearing points (above, left green balls) and finding an optimal (for some meaning of the word) mesh (above, left, green and brown mesh). The system is given an arbitrary set of input beams, and then iterates under user guidance to find an optimal solution.

Truss structures are meshes of connected beams designed to hold a certain load. They're used in bridges, towers etc... The fun thing here is that while physical constraints are used to converge on a solution, a physical model isn't the primary goal. Rather these guys aim for a graphically pleasing representation. There is a large body of engineering work given to engineering trusses dating from the early 1900's, using various forms of numerical optimizations.

The optimization starts with a "rich" (overly generous) set of beams (above - top, left shows how a generous configuration (left) is whittled down (middle) to an efficient structure, in this case mirroring the standard solution (right) in this case of a Michell truss). There a set of build in fudge constraints to specify beams above or below the load bearning nodes, or to constrain beams to a vertical plane.

The optmization uses a simple physical model of the forces involved, and work to minimize some function, typically the total weight of the structure. This constraints (apparently) make the problem non-linear, so the chosen solver is of the sequential quadratic programming variety.

There are a misc. set of other constrains, such as obstical avoidence (above, bottom right, shows a truss holding the small green sphere, but avoiding the large red sphere in it's starting state (left) and two solutions (middle, right)), or max beam length.

After the system is solved, very short beams or those carrying no force are removed. The user then decides if the solution is viable, and the process is repeated until a desirable truss is produced. The results tend to look very similar to those of engineered trusses. In the case of some of their Eiffel tower models, almost too good to be true! - great results for a numerical solver.

inkscape, pdf and posters

2009-05-24T17:41:00.007Z

SICSA asked everyone to make a big poster to make their opening do more academic (here's the result). This was the first time I'd used inkscape to produce an A0 pdf, and there were some hiccups due to the large number of vector illustrations I included [edit - some glitch with scribd, click zoom out to view] -

The first time I exported to pdf, all the non-screen grab figures were vector line art. This gave a nice 3Mb PDF file that would take a massive 3 minutes to open, and without Inkscape's nice blurs. This wasn't really good enough. I decided to turn those diagrams into bitmaps to render nicely. The Glasgow guidelines for creation of PDF posters (as well as specifiying sensible font sizes) says that 300 dpi is the target printing resolution - so this is what I should target in my conversions.

[edit] the rest of this post is for an old version of inkscape. Newer versions export blurs to pdf automatically (save copy as..., select .pdf, in dialogue box "rasterise filter effects" is selected automatically), and you can set the "Create Bitmap Copy" resolution in file -> inkscape preferences -> bitmaps -> resolution for Create Bitmap Copy.

The default image res was 90 dpi, not enough for printing. To set inkscape's default conversion dpi to 300 - I followed instructions here & then restarted inkscape-

The resolution or size of the created bitmaps can be set in preferences.xml (no GUI yet). In , specifying minsize= gives the minimum size of the generated bitmap in pixels (regardless of the object size), while resolution= sets the constant resolution (different pixel size for different object sizes).

Then it was a case of selecting all figures in the document and using Edit->Make bitmap copy. Because of the bounds of the outlines in inkscape doesn't include blurs, sometimes it was necessary to add a large white background rectangle before creating the bitmap copy. Once the copy is made, the original vector art can be deleted.

There were a couple of bugs were the converted figures had a small transparent border that rendered grey in Adobe's PDF reader, but this was remedied by editing the bitmap copies in the gimp and painting out the border, the re-opening the inkscape document.

After this the Save As... -> pdf -> OK worked like a charm. The result was 8Mb, but loaded much quicker and with less glitches.

The PDF included the above image in vector form - it was created from a 3D model that was imported into blender (from my prototype code). The poster was made on a bit of a deadline and rendering out this geometry nicely would have taken too long. Thankfully the render-to-svg script for blender worked like a charm and created vector art from the blender scene. Then a nice blur was added from the input geometry.

Here's another poster I made in inkscape - waaay better than some of the powerpoint mush you get out there!

Finally, if you've got lots of graphics getting the poster to print can be a little difficut - our department has a HP DesignJet (500 plus) connected to an old print server. I've wasted a ton of ink of buffer-underflows - an "out of memory - data lost" error and big missing portions of the poster (white rectangles). The solution was to spool from a laptop connected straight to the printer. Here're the settings I used to print a landscape poster sideways:

skeletons on non-planar input

2009-05-20T12:20:00.002Z

[straight skeleton blog index]

The standard straight skeleton algorithm relies on a sweep plane. By adding points in at different heights we should be able to grow nice houses on hills. We should also be able to preserve semantic data from the skeleton. The naive method has some problems:

It's not too clear in the above, but lower points and edges can intersect with higher edges, because of changes to the points after events. There's a couple of ways out of this - we could say "user beware" and run away, or we could automate something. Turns out this isn't so hard -

[edit: turns out this is hard - it relies on intersecting two parallel vertical planes to a single line, gah! but given a topological approach to the skeleton algorithm, it should eventually work]

We project subterranean edges with a vertical gradient until they come to the surface. this guarantees that the current polygon on the sweep plane.

On a different track, there's a lovely idea of using non-planar sweep planes, such as fields, to define some really interesting geometries. As long as the sweep plane never intersects itself at a previous time, the geometry will remain non-intersecting. If we bound the sweep surface (no polygons allowed outside the limits), or define a Poincare disk/Escher -like vanishing horizon on the surface we could get some really interesting fields. These might be suitable for modelling growth in plants (or animals...?). I'd better find that book on differential geometry.

smoke me a kipper, I'll be back for breakfast

2009-05-13T23:43:00.002Z

Attention Glasgow: URE DOING IT WRONG

am working at the prism lab at arizona state for 6 Months :)

ambiguous weighted skeleton

2009-05-12T23:56:00.007Z

[straight skeleton blog index]

I've just come up with a better example of the straight skeleton's ambiguity:

The top figure shows a situation where we need to make a decision. The bottom figures, a,b,c are examples of different resolution methods, that might be one of the following:

use the nearest intersection (raytracing!)
invent a priority system that pleases us (artist driven)
use an average weighting of the two edges (b, above)

Of course this follows from the fact that a weighted skeleton with consecutive parallel edges of different gradients is invalid. I'm not certain there's a clean way to resolve it...I'm looking...

This is probably similar to the ambiguity problem in 3d, described in Straight Skeletons of Three-Dimensional Polyhedra ( doi | pdf | 2008 )

engineering a weighted straight skeleton algorithm

2009-05-01T11:04:00.010Z

[straight skeleton post index]

This post details an implementation of the Straight Skeleton in the method of Felkel ( pdf | Felkel, Obdrzalek | 1998 ), modified to construct weighted skeletons. Source code is available here. [edit: At the time I wrote the post, I didn't understand a few things about some of the strange cases that occur in the weighted straight skeleton - you can read more about them, here.]

It contributes a method for dealing with multiple co-sited "split events" in a floating point environment, as well as a resolution strategy for horizontal roof edges, this leads to a degenerate case in which the weighted straight skeleton is ambiguous (detailed here). In this post I concentrate on showing an algorithm exists, rather than finding it's speed.

The straight skeleton takes a simple polygon as input and outputs a graph connecting the input vertices as output.

As defined by A Novel Type of Skeleton for Polygons ( doi | pdf | Aichholzer, Alberts, Aurenhammer, Gärtner | 1995 ) the straight skeleton shrinks in the edges of a polygon, tracing out the lines made by the corners of the polygon. These traced lines form the skeleton.

Strictly the skeleton is a 2D construction, however here I regard as a 3D "roof" - given the floorplan of a house, the skeleton is the gutters and crest lines of a roof when viewed from above (4, figure below).

Some properties of the skeleton include:

Unique for a given input polygon
Related to the medial axis and voronoi tesselations for convex shapes
The skeleton of convex shapes is a directed, acyclic graph (DAG) with the input corners as leaves
Each face is monotonic in a direction perpendicular to it's defining edge

Overview

The algorithm uses a sweep plane - staring from the input polygon as the lowest set of points, intersections between planes are considered in height order (perpendicularly to the input polygon's plane). The planes are defined by the gradient associated with each edge of the input polygon, in the unweighed case there are all assumed to be the same value.

There are collisions that occur between faces that aren't valid. These must be ignored.

After all collisions have been accounted for, the algorithm is complete.

Loops of corners

The primary structure used is a set of corners. Each corner has pointers to:

the adjacent (next and previous) input edges (I assume a counter clockwise ordering of points).
the adjacent corners

A partially evaluated skeleton is shown in the following diagram.

Via the normal graphic conventions, holes are represented by backwards (clockwise) loops of corners. There are additional structures that list all input edges, current edges and current corners. Each edge keeps track of the skeleton's output edges.

As the algorithm runs there is one loop of corner pointers for every volume that intersects the current sweep plane. If a skeleton produces a roof with two peaks, there would be two loops of corner points at the corresponding heights. Here it is important to note that an edge can then belong to two different corners. This is the cause of much grief later on.

Collisions between three edges

When the planes defined by edges collide to a point we have to modify the data structures accordingly. Often we will remove old corners, insert new corners or add output edges to the polygon. There are only so many ways that three edges can collide:

In 1) two adjacent edges meet another edge in it's centre, 2) shows three consecutive edges colliding in 3) we see a variation where three consecutive edges that form a loop collide. There are two other important cases:

When there is only one plane at a point, it is just a plane(!?). When there are two, it is just an edge (above, green). These aren't registered as events and no action is taken. 1,2 & 3) covered all possible topologies except three unconnected edges colliding (red, above). The arrangement is impossible (in the simple unweighted straight skeleton case) as there must be something between the edges that also collides at that point, at which point it is a degenerate case. I'll get onto these in a bit.

Each plane defined by each input edge cannot collide with just any old other edge-plane. Eppstein (Raising Roofs, Crashing Cycles, and Playing Pool (doi | web | Eppstein, Erickson | 1999 )) gives more ideas on a fast approach, but to just understand correctness we can start by noting that when two planes collide it forms an edge. We need three planes to collide to form a point; Before three planes can collide, two of these planes must already be adjacent. (Unlike Felkel's approach I'm less interested in the "bisectors" defined by each corner's pair of edges - this quickly becomes misleading in the weighted case). Using the above list of possible intersections, we can see we should only be testing for collisions between pairs of adjacent edges and one other edge.

This digram gives an overview of the data structure additions for each three plane case (the manipulations implemented are detailed in the following section):

These three types of collisions are sufficient the calculate the straight skeleton of almost all random input polygons (see following video or image). The other cases are degenerate and are discussed in the next section.

Collisions must occur on the faces

One way to view the algorithm, is that after the first event, we calculate a "new input polygon" at the given height and start again - so we might see a the algorithms executing on a pile of contours, one for every event, fig. 1 below.

So far the collisions have been presented as infinite planes, however we are really colliding a set of three sided polygons or faces. For example the back edge (bold, 2) in the above figure changes it's topology (red, 2) after some of the events. After event b (view the above larger) the face belongs to two volumes, and hence gives two polygons to collide against. This means that for all of the three faces involved in a collision we must ensure that a collision occurs within it's bounds.

[diagram showing what happens when we don't bother with these checks]

There are two obvious places to perform this check:

Store a list of events between polygons - After an event, find new events and remove old events involving each edge or bisector that's changed.
Store a list of events between planes (planes don't have bounds). Before evaluating an event, ensure it occurs within all three faces. This is the simpler method I implemented.

One trick here (as Felkel describes) is to realize that if two adjacent edges are involved, then the collision is within the bounds for those faces. The faces are adjacent on a surface of the skeleton volume, so they intersect only along this line (and any intersection must also occur on this line). These adjacent edges form Felkel's "bisectors", and as Eppstein explains reduces this to a ray-casting problem that has very fast known solutions. Each of the three types of collisions identified involves a pair of adjacent edges colliding.

These "three sided" faces that we're colliding are sometime triangles, but sometimes they are unbounded, when the adjacent edge move away from each other. (They are triangles with infinite area!)

Floating point calculations sometimes miss collisions that we expect, topologically, to happen. However we can increase the chances of getting a topologically sound result if we increase the margin (epsilon-error range) until we catch all collisions, even if we pick up some additional errors. There are two places where we need to be careful - in checking that a collision really happens on an edge's face and in finding events that happen "at the same height" or "in the same place". I use a cylinder shaped volume to accumulate events that occur at a given height range and within a certain distance to a centre point.

Collisions between many edges

In a degenerate case, more than three planes can meet at one point. This happens in the center of regular polygons, as well as examples such as the following image (where five or eight faces meet single points). Here I present a resolution algorithm that processes pairs of adjacent corners, for any number of edges meeting at a point.

It is important that these occasions are detected and treated with respect, as we assume that the linked-list of corners and their locations form a simple polygon (when projected down onto the input plane). This takes a little patience when working with floating point calculations. Luckily we can generalise some rules for handling point collisions, whether three, or any number of planes meet at a point.

The collision resolution technique takes a set of planes that meet at a point as input. It processes these into lists of chains of adjacent corners that reference these edges. While constructing these chains we perform the face collisions to determine which (if any) corner references the correct portion of the edge.

Chains consist of ordered lists of edges meeting at a point. If the edges are adjacent, they are in the same chain.

Remember that one edge can be referenced by more that one corner, when there are are more than one "peaks" in the output roof shape.

In figure 1 we see the input structure - a chain of edges abc and their associated corners (dark blue circles). We now process each pair of edges that are adjacent (orange lines) as in figures 2 and 3:

We remove each of these corners from the master-list. (note that inter-corner pointers, green arrows, don't need to be adjusted).
We add in output edges to the skeleton.

Then we process the non-adjacent edge pairs as in figure 4, adding in a new input corner and finally adjusting the inter-corner pointers, (cutting out the internal corners). However non-adjacent edge pairs take a little more thought as multiple chains can collide at one point.

As the above shows, once the inter-chain edges are processed (figure 2, above) we can then move onto intra-chain collisions (figure 3). We still process corners by pairs, but this time we process the three pairs that are non-adjacent, the red, yellow and orange edges in figure 3. We order these around the collision point (in the unweighted case this can be done by the angle any corner on the chain makes with the collision point, but see later comments on the weighted case), and process the pair made by first corner in the first chain, with the last corner of the next.

For each of these pairs we add one additional corner that is adjacent to each edge. This corner is at the location of the collision, and cuts out the inter-chain corners from any edge loops.

Horizontal roof edges

When evaluating rectilinear shapes, such as the above cross-shape, we often see horizontal skeleton lines. This is another degenerate case that we often see along side the >3 planes at a point case.

We can note that before processing events at one height, there should be no adjacent edges that form a horizontal edge in the skeleton. Also that after processing there should be no such edges.

Because every horizontal skeleton edge must have an event at it's start and end, we can be sure that if we process all the events at one height together, we will have closed all horizontal edges. [edit: this assumption is wrong - see later post on ambiguous cases]

As all events co-heighted occur simultaneously there is no interaction between events and the algorithm is to be deterministic. There is no way to sort co-heighted events, so we let them occur in an arbitrary order.

After one event occurs we may be in the situation where two consecutive, adjacent edges form a horizontal edge. Because this edge has no height, there is no way to determine which events it causes can occur first:

In the above figure, there is a collision at x, then at the same height, faces a,b,c &d collide at y. Face a should be rejected because we're outside the bisector. However as the edge forms a horizontal skeleton line, the bisector is poorly defined (green boundaries), so we would have to accept that all four faces collide, resulting in deformed output.

We do not track events created by consecutive horizontal edges, safe in the knowledge that after we've dealt with all events at the same height there won't be be any left. In a similar way, we can't ascertain whether collisions between planes occur within the current face boundaries.

For this reason all face-collision checks for events at one height are performed before any are evaluated. I do this by caching a list of chains. This brings with it the problem that the corner used in a chain may have been superseded, or "cut off" from it's intended collision (see figure below) by an earlier event at the same height.

The resolution strategy here depends on the chain type:

If the chain has more than one corner in it, it represents the intersection of two faces, so there will always be a corner lying on this intersection whose adjacencies will lead to the correct corner.
If the chain is of length 1, we must resort to more geometric calculations to project all referenced corners onto the input edge, and choose the preceding corner.

In the above figure 1, faces a,b,c,d and e collide at point x. We find their positions in the given volumes by locating the corresponding corners. As co-heighted events occur in an arbitrary order, by the time figure 2 occurs the corners (u & v) are no longer valid.

In the case of u (or any chain with 2+ edges), we can can use the following corner's previous corner to find u'. This is because the corner references two edges used in a collision, so must take part it (and horizontal events are independent - they can't effect each other's edges or validity).

This trick won't work to find v' as it is part of a chain of length 1. We project all corners that reference the edge onto the collision line. We then use the point (v') that is just before the projected collision as the previous corner. We ignore any points that reference the edge before the found corner. This is valid as all these points lie on the edge's plane, and all the points occur at the same height, so their order is defined by their projection. There is no question that the event occurs as there is no interaction between co-heighted events.

Negative edge gradients

By changing the weight or gradient of an edge, we can drastically change the output shape. There is even the possibility of giving the edges a negative (outwards) gradient, to create "overhangs".

No modifications are required to the given algorithm to allow these gradients.

It is fun to note that negating the gradient (reversed polarity result in the figure below) produces the same shape as reversing the polarity (loop direction) of the input, but with a different final meaning - no longer is the result the top of the roof-shape (a surface whose normals point upwards), it becomes the ceiling of the building from the inside (a surface whose normals point downwards).

When edges have negative gradients, it becomes much harder to guarantee termination of the skeleton - it may define an infinite volume! Sometimes it will terminate, others not. Determining which polygons will terminate and which won't would be a good future research direction. Of course it is always possible to specify an arbitrarily high horizontal plane, which terminates the algorithm.

The following animation places several weighted straight skeletons with varying gradients on top of each other to create some primitive architecture.

Determining the order of chains

Determining the order of corners within a chain can be accomplished by following adjacency pointers to other corners. But between chains it becomes harder. In the weighted skeleton case we must project the corners to the collision height, before determining the order.

Angles around the intersection point are less than a full circle. If they weren't they would have overlapped collided at a lower height.

Adjacent parallel edges

If two skeleton edges are parallel (here I mean edges going in the same direction, not opposites), the intersection of their planes with a third is no longer a point (it is either a line or not an intersection at all). This leaves the straight skeleton poorly defined. This condition can occur in two places

the input polygon
when intermediate edges are removed to being two parallel edges together

This also causes much "instability" or chaotic behavior in the algorithm. In the unweighted case it is possible to define the collision of two consecutive parallel edge-planes as the gradient vector starting from the intersection point. This is not possible if the edges have different weights, see the following video as the weight changes:

There has to be an artificial resolution method for parallel consecutive edges. The simplest is to remove one of the offending edges - this choice can be arbitrary and is justified by the limiting case (as we approach Pi degrees from either side, we resolve to one edge or the other). This works in the first case, parallel consecutives in the input polygon.

In the above figure edge a and b are parallel and have the same weight, they are not consecutive at the start, but become consecutive after an event. Theoretically any line that lies on a and b's face could become the bisector after the collision, however it must be consistently chosen throughout the algorithm. As I'm interested in clean 3D solids, the outcome in the figure is most desirable. By merging the two faces together we can see that the input to the algorithm shouldn't have been the two separate edges a and b, but rather one edge referenced twice. This is the approach I take.

On the subject of chaotic elements of the straight skeleton, another situation deserves to be pointed out. If concave faces' bisectors pass each other ("split events" in Felkel's terminology), there is often a sudden shift in the topology of the skeleton.

Adjacent and horizontal faces form an ambiguous case

When the skeleton is weighted (different gradients on each edge), there is an ill defined condition:

In figure 1, we see the input, a weighted skeleton where edge a has a lower gradient than edge b. These two edges meet to form a horizontal edge. At this point there are two resolution possibilities that make topological sense, 2a, letting the lower gradient take priority and 2b, letting the higher gradient take priority.

[edit: this is wrong, either 2a or 2b, above, are equally valid] ~~A sensible implementation should choose to give the steeper edge priority (figure 2a) for two reasons:~~

~~If we look at the limiting case as edges a and b become parallel, as we reduce the angle between them, we get output topology favoring the steeper edge.~~
~~Topology 2b leads to the situation where one horizontal event causes another, breaking earlier assumptions in the implementation. This would mean that we could no longer order events by height.~~

However this is not consistent with the concept of the skeleton being a "wavefront".

Aichholzer et al. do not describe the weighted skeleton, and so do not come across this situation in their text. I'm not aware of a description of the weighted skeleton that avoids this ambiguity.

Building faces

Once the edges of the skeleton are known, it is desirable to be able to define faces (we might want to tile our roof). There is one edge for each face.

The implemented algorithm keeps a single graph (a hash-map) of all edges in the skeleton, and for each input edge there is a list of corners that once referenced that edge. This information is sufficient to re-construct each face:

As there may be parallel edges with the same gradient, the algorithm needs to be a little smarter:

mudslingin'

2009-05-01T02:25:00.003Z

The other project I'd forgotten about (until I read this paper) was Mudslingin', the second year undergrad (5 year old), 5 person "group" project. It's a two player, network enabled game in which you try to drown your opponent by throwing balloons full of mud or water at them. Your opponent has bombs to blow up your dams - great fun for the whole family. It has quite a lot of features now I look back on it, even it it was rough around the edges.

Click here to play (binary file run at your own risk, requires Java 1.5+). There are lots of bugs, many to do with a 40 minute conversion into the webstart format. Sound, save and networking probably won't work in the webstart edition. The options menu seems to freeze everything. You also need another person to play against! Keys:

Menus: Up, Down, Enter
Player 1: Up, Down, Left, Right
Player 2: K,L,O,M
Quit: Escape

Go "start game" then pick one of the levels like 'blood fountain'.

Group report is here. Source files are here (I'm releasing them under a WTFPL), and includes the (bizarre) perl server.

I think we came top of the year (after a database blunder I ended up being able to see the whole year's grades).

Now this is published, I can pack my computer up so it can go into storage.

random talk on procedural

2009-04-30T00:33:00.000Z

Ruth Aylett asked me to give a talk to members of the graphics group at Heriot Watt, so here it is.

Was mostly a rehash of my Master's dissertation slides. Sorry, some slides make no sense without me talking over them - use your imagination...

buildings on curved roads in glasgow

2009-04-26T06:54:00.004Z

Park Circus

Oblique angle on live maps.

Dundonald Road

(back of:)

Kensington Gate

Oblique view on live maps.

geometric robustness papers

2009-03-31T16:13:00.017Z

I've suddenly lost faith in floating point (FP) arithmetic for geometry. This is best explained by the CGAL people. Here are my notes on papers I've read:

Classroom Examples of Robustness Problems in Geometric Computations ( web | Lutz Kettner, Kurt Mehlhorn, Sylvain Pion, Stefan Schirra & Chee Yap | 2006 )

This is a great introduction to the properties of floating point arithmetic in a floating point environment. The authors set out to describe a complete set situations where floating point upsets a few simple algorithms.

The authors describe this in respect to calculating the convex hull (gift wrapping algorithms) and finding the 3d Delunay triangulation of a set of points. They give the facts that the algorithms rely on, and show how these often do not exist in the floating point situations.

The most common cause of error is that when working with number of different sizes, the smaller one is always rounded to fit into the larger one. When working with points, this means that the precision of a calculation is limited by the largest point involved. In many situations these number can be spatially remote. The below image shows the results of trying to decide which side (of the black) line a point lies on. The point is moved over the (256x256) grid in the smallest steps allowed by double precision. The grid is the colour coded based on which side of the line the algorithm reports the point to be on (red, yellow and blue for right, on-the-line and left respectively).

Different lines are examined in each of the three images - the patters of the errors are quite non-intuitive. We often see points classified on the wrong side of the line.

The patterns get messier if we look at higher precision floating point types. The paper does a very good job at explaining how these properties of floating point can lead to gross errors in the algorithms.

It briefly looks at techniques that don't solve the problem - adding an epsilon value (video below) and perturbing the input.

Here is my video of animating the epsilon value in a geometric floating point context:

We're evaluating the same function to determine which side of a line a point is on (except the horizontal is flipped). Over each frame we move the point around. Blue is one side, red the other, yellow on the line. We move the point by the smallest quantity allowed by the double precision floating point system.

The animation shows an increasing "fudge factor" or epsilon added to try and make the computation more robust. The boundary stays just as strange!

Animating the epsilon value of the first example in the paper from 0 in steps of 2^-44 @ 3 frames per second. Java code.

Construction of the Voronoi diagram for `one million' generators in single-precision arithmetic ( pdf | ieee | doi | Sugihara, Iri | 1992 )

Hence, we change our goal; we try to construct a diagram which shares some topological properties with the true Voronoi digram....the output "converges" to the true Vornoi digram as the precision in computation becomes higher.

To do this the paper's authors present version of the insertion Voronoi algorithm that modifies the topology from one consistent state to the next. The basic step is to query the topological model before each cell is included in the insertion of a new point.

Given a new point to insert (i, below), the topological model has three rules relate to finding the set of cell-corners to modify:

The set of cell corners is not empty
The set of cell corners form a tree
Every corner is reachable from every other corner by traversing existing Voronoi edges that lie between cells in the set.

These properties have are not shown to be necessary and sufficient to derive the Voronoi (I think they are, elsewhere, see the references in next paper - Topologically Orientated Implementation), but they get close - selecting topologically consistent cells. The algorithm "flood-fills" a region of the cell-corners, starting with the nearest to the new point (blue, i, below), collecting cell-corners (ii, green dots) that satisfy these conditions. Once all adjacent corners have been shown to be inadmissible (red dots), all the admissible ones can be proved to have been found. Then (iii), the Voronoi graph and the topological map is updated, and we move onto the next new point:

There is also a section on how to compute with the least floating point inaccuracy, but it isn't as interesting. The cunning work here was breaking the algorithm down into a set of topological manipulations that are always valid.

Sometimes the floating point output isn't valid, that is cells and lines overlap. But that happens in areas proportional in size to the error margin (FP accuracy) - they could easily be post-filtered out if required. The robustness of the algorithm can produce output such as the million points in the above (black and white) figure, that would otherwise cause visible trouble.

The approach can be seen as using the topology as the central structure that is guided by the inaccurate floating point calculations.

Topology-Oriented Implementation—An Approach to Robust Geometric Algorithms ( doi | pdf | K. Sugihara, M. Iri, H. Inagaki & T. Imai | 2000 )

This is another presentation of the previous material with a couple of different examples. Logical and combinatorial computations can be done correctly while geometric ones are unreliable.

The overview is that geometric algorithms have a set of topological solutions, that branch from each other. One of these is the correct solution, but as long as we end up somewhere on tree of valid solutions we're doing ok. The floating point gods (inaccuracies) decide which branch the algorithm will follow. More formally (quoted:)

Collect purely topolgical properties that should be satisfied by the solutions of the problem and can be checked efficiently
Describe the basic part of the algorithm only in terms of combinatorial and topological computation in such a way that the properties are guaranteed
Conduct numerical compuations at each note of the tree in order to choose the branch that is most licely to lead to the correction solution

Since we can't even detect degerate geometric cases consistently, the output might be degenerate, but if well designed, the degeneracies will be at around the floating-point-accuracy-scale. As the precision of the FP calculations increases, the solution converges on the desired one.

The paper includes examples for surface-slicing and Voronoi tessellation.

Lazy Arithmetic ( doi | pdf | ieee | Dominique Michelucci & Jean-Michel Moreau | 1997 )

This is a subject overview paper.

It outlines several solid geometric examples that are broken by floating point arithmetic -

The point where two lines cross is on a different side of each line
Zero determinants of non-singular matrices (the result changes depending on how the calculation is done)
Lexicographical order of line crossing (y1 < y1 ="=">
Simple comutations expressed in different ways suffer different truncation limits so one equation has two answers
Pappus' theorem doesn't generally hold
Borderline cases when using matrix determinants to identify angles less than or greater than a right angle

Two main classes of ways of dealing with these problems are presented - inexact and exact algorithms.

Inexact algorithms do not produce the exact mathematical result, but approximate this result. Since FP is only an approximation in the first place, these can be viewed as a set of tools for ensuring that the algorithms do not end up in an inconsistent state (they don't infinetely loop or teminate abnormally).

Warned programming involves coding tricks using limited reasoning (topological data or exact number representation) as each borderline case is found.
Epsilon Heuristics - assume that two items are identical if they are within a given range (epsilon). There is no way to guarantee that this approach will produce a consistent internal state - we are effectively shuffling points in one region of space.
Symbolic Programming - By ensuring that the algorithm's choices are guided by topological or combinatorial reasoning, floating point errors will only change the path not create invalid results. This is the idea presented in the Topology-Orientated Implementation paper by Sugihara.
Historical Book-keeping - By keeping a list of decisions and ensuring that all following decisions are consistent with previous decisions, the world is consistent from the algorithms perspective. This approach is described as being cumbersome and using lots of memory.
Confidence Intervals - Formalised Epsilon Heuristics - results involving floating point calculations can be "I don't know" when FP is known to be incorrect.

Entirely exact methods on the other hand always calculate the true value of every expression. Since we're often interested in boolean answers (is this point on the left or right of that line), we do a lot of additional work.

Ten random points with double-precision coordinates were triangulated using floating-point arithmetic in .1 seconds; 10 random points with rational coordinates (two-digit numerator, three-digit denominator, in base 2) were triangulated using rational arithmetic in 1,200 seconds, generating intermediate values with as many as 81 digits. ^{[Efficient Delaunay Triangulation Using Rational Arithmetic: Karasick et.al]}

The additional processing makes exact methods formidable, therefore mixed methods are introduced. These first perform the calculations in a specific accuracy, but track the error bounds to ensure the result is correct. Classes of language such as XSC do this automatically. If the result is unstable around the bounds then the algorithm reverts to exact arithmetic.

One approach (Karasick/Yamagushi) converts all calculations to computing the sign of a 4x4 determinant. This is then calculated using the most significant bits, then adds additional bits until the result is unambiguous. While I haven't seen enough geometry to be able to say if all problems can be found my calculating the det of a matrix - I am sure many of the important ones (which side of a line does a point lie on?) can be. Fortune and van Wyk implement an automatic system along these lines that compiles down to c++ source.

Several of the exact methods pre-process a specific problem to calculate how much precision is required, then calculate using these figures.

At this point the authors of the paper point out that using a specific tolerance ("long integer libraries" eg BigNum) means that division often has to be barred for fear of recurring decimals. All of the presented exact methods need lots of additional work by the programmer.

The paper continues to introduce Lazy Evaluation - floating point calculations are performed until the error is enough to introduce uncertainty. At this point it reverts to using exact? evaluation.

The operations performed on the values ("Lazy Numbers") are tracked by a parse-tree (or symbolic computing) like graph specifying operators and operands. When an operation is ambiguous (within the error bounds) the graph is evaluated using exact arithmetic.

This seems like a dream answer for Declarative programming enthusiasts (Haskell!).

The cost of Lazy Arithmetic is given as a 4-10 decrease in speed, which considering it's a big leap away from the computer's architecture, is very pleasing. Even better it's claimed to be 150 times faster than purely exact methods. In systems where this method is used (CGAL) the cost appears to be much larger for more complicated algorithms.

The paper describes a method for hashing lazy numbers, and shows that non trivial equality tests can be expensive. The system implemented only does very simple algebraic/symbolic equivilences, otherwise expesive tests are needed. (Probabilistic hashing is given as a possible solution)

Problems with Lazy Numbers include

lack of hardware support,
need for the programming lanaguage to allow a new number types, along with operators on those numbers.
conversion back to FP for output is problematic - polygons may self-intersect after processing. (But at least the algorithm will run, and at least the errors will be close to the size of FP accuracy)
numbers such as pi or e can still cause lots of problems

copyright vs fun [rant]***

2009-03-30T15:20:00.006Z

Copyright is a privilege that the population has given to creators. The governments allow this copyright deal - that the contents of a published can only be published by the author for a given time - in the hope that the creators create more. The child's argument goes "I made it, so it's mine", the grown-up's "creation of a work takes time, the author deserves to be repaid". But I think these arguments are getting less persuasive as technology advances.

My main problems with copyright are that it is a false economy, and that for a lot of media it is not in the interest of people. I'm a student & there's little reason for me to support copyright* - I'm not invested in the system. I own little valuable IP, I expect to create very little, but every day my activities are constrained by copyright law.

"The American people would just have to get over the fact that software no longer had any economic values. It wasn't fair, it wasn't just, but it was a fait accompli. In many ways, Oscar had to give the Chinese credit for their cleverness in making all English language intellectual property available on their nets at no charge. The Chinese hadn't even needed to leave their own borders in order to kick the blocks out from under the American economy." - Bruce Sterling's Distraction.

But it doesn't need to be China to expose the deceptive value of copyright, the twak consortium (or seasteaders) might declare moonbase alpha it's very own sovereign territory and remove copyright. Moonbase alpha can then listen to all of Earth's music without charge, it's a no brainier for those uninvested in copyright.

Massive piracy means that copyright is making most consumers illegal. Piracy is commonplace, trivial and increasingly accidental (copyrighted works in the background of hi res photos, music in the background of a youtube video, buying used software often breaks the EULA). It is becoming very difficult to live a life in which you do not break copyright laws. Perhaps this should be taken as a hint that they aren't compatible with today's technologies.

Industries that rely on copyright have started to look dubious. Print newspapers' revenue is in free fall, the music industry is trying to sue its customers and book publishers are trying to stop computers reading their books aloud. These are not activities that secure, upcoming companies engage in. The companies in these sectors that are doing well, are doing so because they are moving away from a copyright dependent model. Perhaps they're worried that their wealth is based on a bubble? (In the light of current financial problems, it might be unsporting to point out that we're building a bubble around IP that could burst). It could be burst by another country as an act of war or it could be burst by new technology (undetectable music copying?). Overnight our copyrighted material, our copyrighted assets, might be worth as much as the canvas, paper or disk that they're held on. We've added a lot of value to something that isn't tangible, and is making less and less sense every day. If that bubble bursts, lots of value will be dumped from the big companies - it's best we slowly deflate the bubble slowly, rather than wait for the time bomb to explode.

So the main question is how much content wouldn't get published without copyright? And how much broader content would each person experience without copyright? Here's a fun gedankenexperiment:

We only need copyright on things that are expensive to create. On things that wouldn't be created without it. Music is fun to make, people can do it very cheaply in the evenings, and they enjoy it. What about abolishing music copyright? Would the population as a whole suffer? All currently available music would be free to all people - I think the value of this person is more than the value of the record companies. Distribution by the record companies isn't needed, the net is a suitable medium - music is quick and easy to download and many people who like music use portable mp3 players and never see CDs. However the very popular artists with all the money would loose most of their incomes, as would the record companies. But would music continue to exist? yes - we have huge backlogs of material that we mostly don't get access to because of copyright. Would music continue to be made? yes - it's very cheap to create music (you can do it your basement), and more importantly it's so much fun you couldn't stop people creating it if you wanted to.

This is very much a socialist argument. It's benefits wouldn't be measurable in market capitalizations or economic figures, it's benefits would be in the breadth and quality of music people end up listening to every day

Which other arenas is copyright unnecessary in? Photography maybe, but there aren't too many other media with which the above argument holds today, but films and video games are starting to get to the point where they can be made to a comparable quality by people in their bedrooms, for fun. Not for profit feature films include Bloodspell and Star Wreck, although their quality isn't up to it yet, it will one day.

We're just waiting, in all these media, for the quality of the work by people-who-do-it-for-fun to get good enough. It doesn't have to be perfect, it just has to be sufficient, such that 90% of the people don't notice it 90% of the time. As more people get involved in doing it for fun, the quality gets better. You can look at the "most interesting" photos in flickr and the quality is immaculate (a million monkeys with a million Canon 400d's). This is because of the number of people involved, the sophistication of the technology they use, and because it's fun!

Copyright protects the establishment. In a certain way I think it stops people being able to publish their own work. People have been groomed into accepting high production values in their media. What if the established publishing houses disappeared - if the Hollywood studios vaporized?** I might start reading more interesting books and watching a broader range of movies. So much is spent on polish and advertisements that smaller artists are drowned out (do you really think that the profits of an artist correlate with how good their music is?). Social media techniques like digg.com would allow you find what other people think is good, rather than who's paid most for advertising.

Of course this doesn't reach to all areas, copyright in more hi-tech industries still seems to be needed (such as software engineering), until they too can be done entirely in the bedroom. When I can ask a computer "computer, write me a word processing application!" I think the copyright on software should be abolished (and probably patents too, but that's an argument for another day).

modders: ye be warned

But today we have to ask if copyright is still a benefit to the people? It has got to the point where copyright is holding back a tide (academic paper on the subject) of new exciting & valuable content. Copyright prevents derivative works - new content from that which exists. The Grey Album or American Edit are great bits of music that the world will not hear because of copyright. This work cannot take place under copyright law - the people who do it for fun can't afford to use copyrighted materials. Licensing copyrighted media is expensive, time consuming and not much fun at all.

My final point is that we may soon find ourselves in a world where computers can create desirable content unassisted (this is part of my work, finding tools to help (and maybe replace) 3D artists). When a computer can write you a pop song, does copyright make sense?

Copying can't be stopped, as long as I can point a camcorder at the screen of my telly; As long as I view the movie with my eyes and store it in my brain. Copyright just feels broken.

* A land of copyright-haves and have-nots. I own little copyright, I consume huge quantities of copyrighted material. So how much of it would have been written without copyright? What incentive do I have to welcome stronger IP laws?
** can tell I'm trying to be persuasive, I keep using question marks?
*** sorry for the rant. had to be said. yes the blog is copyright. yes I'll put it under CC, but not until next year...

[edit] this is another summary of the issues surrounding copyright:

View more presentations from Rob Mcminn.

bike review giant scr 2

2009-03-29T01:34:00.010Z

So I've had this bike since June last year (9 months). I've given it some real punishment, and thought I'd jot down some stats and figures. It's probably equivalent to Giant's 2009 Defy 3 or 2.5.

Now I've been careful with it, but it's been ridden from west spain to east denmark, been on a couple of planes, carted around on more trains than I can remember, and left to defend for itself in the back of a transit with 10 mtb's (gang bang!). It's also just gone through a Glasgow winter, which means freezing nights, being drenched in salt water (road grid) daily and potholes like nothing I've seen the western world. I also think I've done about 5000km over about 8 months.

The only changes I made to the bike before touring was a pannier rack (yes the defy and scr ranges are drilled for pannier racks) and spd-cleats.

This was the first bike I had with cartridge brakes. Me no like. Stopping power is pants, and they need replacing quite frequently. And it costs 5 quid for a new pair. Will be looking to replace these with some v-brakes. Some of the problem was the front rim became so scratched (by crap stuck in the brake pads) that it slices through pads at a rate. This means a whole new whole front wheel to replace as well as the back with a bust hub...

When I was touring (15-20kg of gear, but I'm only 65kg) the back wheel lost 2 spokes every 3 days for a fortnight before it was replaced (with a Mavic Aksium). Bit annoyed with this, it might have been shunted while in the airplane hold (above)...but nothing visible and it was really well packed up. Original front wheel has held up with minimum hastle tho.

I was really impressed with the Mavic Aksium replacement back wheel. No dents or creases and at it has straight pull spokes (not the j-ones) which are awesomely hard to break. So hard, in fact, that the hub gave out last weekend (after 6 months) when one of the steel spokes was pulled through the aluminium fastening - the spoke still looks like new, the hub is a write off (seems to happen to other people as well). Still I rode 80 miles one spoke short (after some spoke-key persuasion, and disconnecting the back brakes to allow for 1.5cm of wobble) and it didn't get any worse. I'm going to try and repair the wheel, so that says something about how much I like it.

Was totally shocked when the rear mech hanger gave out on me for no good reason 7 months in, leaving me stranded on the edge of town. Was torn in two at what looks like a weak point where one of the nuts went through. Thing is you never check the condition of the hanger, because you can't see it and lets face it, it's a inanimate lump of metal. Was cheesed off tho, because when it went it snapped the chain, meaning new chain and rear cassette. Plus my back wheel locked up in the middle of a busy junction...but that's another story. There aren't many giant dealers around, and normal bike shops don't carry mech hangers for all bikes, so in the end it was a mail order job. Because I'm paranoid, now I carry a spare hanger.

The bundled tyres also weren't up to too much either. They ate tread quickly and punctured easily. Ended up replacing them with some kevlar (Vittoria Rubino Kevlar Tyre) ones that are holding up well, and their yellow nicely matches the panniers.

Running costs for 8 months (pounds sterling):

20 misc spokes
30 Replacement pads (front and back x 3 at five quid each)
20 Chain
25 Rear cassette
15 Rear mech hanger
75 back wheel - Mavic Aksium
130 for touring wheel pair - Deore hubs and Mavic A719 rims (300g heavier, but am fed up about going through rear wheels so fast.
25 tyres

So that's a non-trivial 340 to keep the bike on the road for 8 months, about 3/4 the cost of the bike. Then again it's about 7 pence per km, or 7 pounds for every day out/100km. That's about the cost of fuel for a car doing the same distance. Other (optional) stuff I've brought includes:

[edit:]
Last week my left shifter barfed out in the middle of a tour (10 months after purchase) stranding me in bottom gear for two days before I botched on a temp thumb shifter. It would have been another £150 on that list, if it wasn't for the fact that I managed to get home to the dealer the bike came from, and got him to get giant to buy me a new shifter.
[end edit]

40 Tools/oil
25 Saddle bag
60 SPD pedals and shoes
20 Pannier (+90 for Panniers, indestructible and fantastic Ortliebs)
60 Lights (already had a helmet)
30 Lock (that was certified by the insurance company, and is too heavy to really carry around)

235 in accessories and vanity goods... but these are by choice.

Stuff I still want

V-brakes - Glasgow eats cartridge brakes for breakfast and they're fuppin expensive.
A saddle bag not made by topeak (both of these have crapped out on me very quickly - if you buy anything by topeak, expect all the plastic catches on it to crap out quicky (two saddle bags and a multi tool have fallen this way))
New front light (Cateyes turn out not to be waterproof)

I guess the long and short of it is that a road racer isn't a tourer. Racers are for 2 hours every weekend, instead of going to the gym. Touring bikes are heavier and can take extended punishment. I want both, but am poor, generally I'm leaning towards a tourer now. For all it's problems I've liked the bike and it's been a great introduction to serious biking etc... & it's been a whole lotta fun :)

at least we're good at being told what to do

2009-03-28T16:54:00.000Z

Here's something that missed me last year, the country that spends most on online advertising, per person, is the UK - 214 dollars for every netizen. If you're going to do an online start up, with an advertising-based business model, there's some serious thinking about where it's going to easiest to get going - the US is down in 4th place. (via 'crunch and PWC)

Unique Visitors (000) - Apr 08	Total # of Internet Users in market (thousands)	Total Interactive Ad Spend Per Market in $ (millions) for '08	Per Capita Interactive Spend ($)
United Kingdom	34124	7302	213.98
Australia	11229	1673	148.99
Denmark	3438	496	144.27
United States	190728	25200	132.13
Germany	34539	4105	118.85
Sweden	5785	651	112.53
Netherlands	11029	1047	94.93
Japan	55260	4965	89.85
France	26263	2326	88.57
Italy	18997	1450	76.33
Canada	23947	1582	66.06
Finland	2984	192	64.34
Norway	2802	179	63.88
Spain	15705	906	57.69
Rest of Europe	82441	2058	24.96
Brazil	19320	402	20.81
Mexico	11773	119	10.11
India	28375	102	3.59
Rest of Latin America	30516	60	1.97

robust straight skeleton

2009-03-27T22:26:00.005Z

[straight skeleton blog index]

Have been trying to figure out how robust you can make the skeleton to floating point errors. I suspect it's impossible to do entirely, without it reducing to a very expensive operation, but am not really sure. (edit: source code here)

marvin the robot

2009-03-25T00:36:00.002Z

I realised that some of my old projects never got put back onto the web, like they deserve. So presenting my UCSC CMPS160 final project marvin-the-robot

It was made in C++, with a meg/sec memory leak to show for its troubles (this was a work of graphics not engineering). The windowing code came from the fltk system. The only bit of code that might be useful to someone is the downhill iterative IK solver that's in there, somewhere.

Controls:

R - change camera mode

1..6 - ask marvin to do some actions

< > - move camera forward / back

[ ] - move camera in / out

Is an IK example of robot riding around a small moon endlessly. Was written in C++, source is here use it under the normal WTFPL.

The binaries for OS X are here. If anyone builds it, it'd be great to have some binaries for other OSes, also if you've got a mac powerful enough to run the app and do a screen capture at the same time, a youtube video would make me very happy :)

Eurographics 09 papers

2009-03-24T17:47:00.013Z

A couple of procedural-ish papers from this years Eurographics:

Arches: a Framework for Modeling Complex Terrains ( [tba:eurographics] | pdf | web | 2009 )
A. Peytavie, E. Galin, J. Grosjean, S. Merillou

This paper presents a method for generating and editing terrains that include overhangs.

A discrete block model describes columns of materials. This is covered by a simple implicit surface (using a cubic kernal giving a C-0 continuity) to smooth it. The block model describes which material is present between which heights, this is presented as a lower memory version of a voxel system.

These techniques are intended for use in realtime editing, so instead of complex physical models that can only be used offline, Arches uses a simplistic physical simulation in each column. Where sand and loose rock are clustered above bedrock, the materials are unadjusted to form contiguous columns. Then adjacent columns with the same materials are allowed to settle (with different viscosity etc..).

The bedrock layer can be edited using a tool that adds or removes material from the columns, taking into account the fact the user is viewing the implicit surface. This just adds a sphere of material at a time, and isn't particularly useful when building up large cliffs - so some sweep tools were also introduced.

An erosion tool takes a volume of bedrock, and converts it to loose rock and sand. These are then allowed to settle to give the appearance of decay. Similarly loose rocks are made by tessellating a volume of bedrock using Voronoi cells, then erroding the outlines, leaving contact point unchanged. As these rock piles are not the result of physical simulation, they might not be physically plausible, but the results are good enough.

To render the scene, the implicit surfaces of the bedrock and sand are polgonized. The loose rock's implicit surface is polgonized separately. To avoid computing UV's a 3D volumetric texture is used that includes the normals of the local surface.

This paper contains quantities of unnecessary equations. There's something inside every computer scientist that believes a really good paper has to have lots of equations! It's also an offline system - the textures and meshes are generated from the column model at design time and we only see "normal" meshes and textures at run time - the potential is almost there for real time generation, but it just falls short.

The results are very nicely presented and represent a system that is an obvious improvement on current games-industry practice. I've been meaning to review more terrain generation techniques, because it's one of the best sources of mesh generation literature.

Cheeky note: this system of columns for representing rock was used in a undergrad project ("mudslignin'") to represent a 2D landscape of mud and water - it was even fast enough to calculate 2d "water" (aka jelly) simulations in real time:)

Structure Preserving Reshape for Textured Architectural Scenes ( [tba:eurographics] | pdf | web | 2009 )
Marcio Cabral, Sylvain Lefebvre, Carsten Dachsbacher, George Drettakis

This paper presents a method to intelligently reshape existing 3d models. By using context-sensitivity image resizing and attempting to keep angles constant, an artist's models can be manipulated to a new shape by dragging a few handles around.

An input model is pre-processed into a set of constraints and a solution. Then the model can be reshaped using a set of point handles, while the constraints are satisfied to position each vertex in real time.

There are a few different constraints, edge direction constraint attempt to keep the angle between two consecutive polygons close to the original. Edge length constrains attempt to preserve the length of shorter edges more than longer ones. There is a minimum edge length to stop degeneration. When two parts of the mesh touch, but are not connected, a contact constraint enforces continuity. This constraint triangulates one of the touching faces and constrains the other part of the mesh to this position. To capture the requirement that ornaments (windows etc..) stay the same size, similar sets of faces are detected and (optionally) constrained.

This set of hard and soft constraints is dumped into a matrix and solved using least-squares. At run time the users input is projected using the found solution and analyzed - if it is degenerate, the users edit is rejected.

Unlike the content-aware image resizing that made the front page of digg last year, the texture resizing algorithm is specialized for rectilinear architecture. The input texture analyzed for self-similarity, and only those parts that are self-similar are stretched on a rectangular grid. Sample patches are used to reduce blurring.

This paper is one in a growing trend towards manipulating existing meshes into new forms. I have always felt that this approach isn't competitive with outright procedural generation for the pro-artist due to over constraining the user:

"To enable interactivity, we rely on a simple solver and allow it to fail or reuse user input if this leads to degeneracies (ie collapsing edges or collisions). We argue this behavior is reasonable since the user has full freedom to assign new handles and guide the solver in avoiding degeneracies)"

However as a method for quickly splicing together geometry for a un-trained user this looks really effective. The video is really worth checking out.

when an irresistible force meets...outlook!

2009-03-19T13:34:00.002Z

[edit] apparently this problem's been fixed in the latest version of Elgg.

So after signing up to SICSA's Elgg (social networking hoodicky) I had a bit of a mail fail:

Found some great new toys debugging this one:

Export Cookies allows you to de-sql-arize the Firefox cookies file and use the output in wget's --load-cookies argument.
Live HTTP headers allows you to view the headers for all the page's content as it streams by.

Combining the power of these two showed what happened - Outlook's web access (gobshite!) uses javascript forwarding on all email links...

window.location.href = foo.html

...but Elgg's email confirmation scripts forwards to the referrer (for some unknown reason, perhaps the idea is that you never see it). So we have the irresistible force of Outlook vs the immovable object Elgg, giving a redirect loop that sends me an email every time round. The following downloads google's homepage (yay for cheap HTTPS pages without real certs):

wget --no-check-certificate --referer "http://google.com" "https://projectnets.cs.st-andrews.ac.uk/sicsa/action/email/confirm"

The thousand little edge cases like this (browser #342.b with web app #564.j) is the reason we all use commercial networking sites. They have the time and willingness to fix these before release (so I don't have to find them). They also have enough existing users to make it worthwhile filling in the sign up form.

Still it's one more tool to use when rick-rolling academic types eh?

[edit] Here's Elgg's source - looks like someone wasn't quite thinking straight. Bugged.

00043 forward($_SERVER['HTTP_REFERER']);

There's no way this was ever a good idea...

netbeans combobox

2009-03-17T18:14:00.004Z

The simple solution to the broken combo-box (drop down box) rendering in netbeans under linux (Ubuntu hardy/8.04) is to update java. Grab the 6.12 jdk installer, install then update the symlink in /usr/lib/jvm


twak@xxx:~$ cd /usr/lib/jvm
twak@xxx:/usr/lib/jvm$ sudo rm java-6-sun
twak@xxx:/usr/lib/jvm$ sudo ln -s jdk1.6.0_12/ java-6-sun

After and before:

I'm not sure this is the official way to switch jdk, but it works. Am getting fed up with netbeans niggles now....

gizmodo'd

2009-03-15T21:36:00.001Z

Thanks to Sean for pointing out that Gizmodo used a self portrait of me in a set of images. Must have been a slow news day, so they scraped the flickr group for creative commons content....

from here:

this is the hardest thing I've done

2009-03-12T23:17:00.005Z

and this is the second time I've done it. Sorry this is another rant about PhDs!

I've spent a lot of this week working on the problem of 'horizontal bisectors in the straight skeleton'. The solution (i'll publish it here when I'm sure it works) was stupidly simple, but it's just one of a thousand snarls while implementing what I thought was a fairly simple routine. It means that this term has been effectively been a crash course in implementing computational geometry algorithms. The thing I feel guilty about is the small amount of output -the total code is less than a day's output when I was employed as a code monkey last year.

I've built this algorithm, for Sity, but a lot of the theory was lost on me. It's a bit of a legendary quest that I want to finish. I should understand this implementation well enough to really fix (rather than patch) any problems that occur, and extend it in bizzare and interesting ways. But the best thing is - I haven't been bored since I started.

I chose my own subject, it's up to me to get my supervisors interested in the subject rather than vice-versa. There's little related work going on at Glasgow (or anywhere in the UK really). The thing is, this is what I secretly always wanted (being a bit of a loner at heart), but keeping motivated is going to be a challenge.

I guess you build up tools that keep you going - conferences, daily/weekly routines and presentations. But I think there is very much another skill in keeping yourself interested. I've noticed this in a lot of the older generation of people who studied for PhD's years ago,will motivate themselves to thoughily research an area in (what looks like) zero effort. I guess it's an aquired skill. It means paying great attention to your state of mind, when you're energised you're ready to takle hard work, or break into pastures new. If you're tired it's important to have a juicy area to work on that's very involving and provides effortless motivation (for me this is programming).

It's much like tending a flame...add just wood to keep it going when there's a good bed of ashes, and pour on the petrol when it's about to go out. Perhaps silly metaphores are best not dwelt on, and attributed to the bleak Glaswegan winter.

blender animated obj import

2009-03-04T11:35:00.001Z

I needed an animated mesh import to blender and .obj is always an easy format to work with, so here's a modification to the blender import script that loads a sequence of .obj's in a directory and animates them together in a new scene in the current blender file. All the meshes get dumped onto layer 1, and moved onto layer 2 for one frame only. Result!:

that straight skeleton again

2009-03-04T01:57:00.006Z

[more skeleton entries]

The straight skeleton is an algorithm that takes the floorplan (bird's eye view) of a house and produces the roof shape. Each edge of a polygon is moved inwards, in the direction of it's normal, tracing the intersections between the edges (gutters and crests) as they shrink in. Raising Roofs, Crashing Cycles, and Playing Pool (doi | web | Eppstein, Erickson | 1999 ) is an excellent introduction to the skeleton, even if the O(complexity) bits can be ignored on the first reading. For those looking for a decent implementation of the unweighted skeleton, I point ya'll to the masters of robust implementations at CGAL. [edit:] My floating point implementation of the weighted skeleton is here.

This data structure has always haunted my work in urban modeling. As an undergrad it took me a few weeks to understand fully and implement, and even then I kept running into nasty numerical issues. The data structure was described for the first time in 1995, but there's a been a fair bit of literature on it's implementation and computational complexity.

The straight skeleton was first described quite recently in A Novel Type of Skeleton for Polygons ( doi | pdf | Aichholzer, Alberts, Aurenhammer, Gärtner | 1995 ) as an alternative to the medial axis, but with straight edges. It is introduced as "that roof shape". It also points out that straight skeletons are unique, but as Eppstein's paper shows they are quite chaotic - small changes in the input or decisions made can lead to large changes in the output. There are assorted uses for it, beyond the obvious roofs in procedural urban geometry, you can even morph polygons by morphing their skeletons!

This algorithm took me a long time to implement (just getting back into the swing of coding, and picking up the equivalent of a couple of graphics courses in linear algebra along the way). It was implemented to define the weighted straight skeleton (see Eppstein's paper again) rather than just the straight skeleton. This was basically done in the method given by Straight Skeleton Implementation ( pdf | Felkel, Obdrzalek | 1998 ), although I have several issues with the paper, I'll write about that elsewhere (maybe a bathroom wall).

My first attempt at this was for Sity, (the results are here). It was a long time ago, but the algorithm gave me real trouble. I was basically using using a Jordan curve algorithm to detect line intersections, and tweaking it a little bit so that weighted skeletons could be created. I had endless problems with collision rays escaping from their bounding boxes (I was up to four rewrites). In an orthogonal environment, you very often get 45 degree bisectors targeted against square corners. This mean that it's a disaster if neither of the edges adjacent to the corner catch the ray. Because of the nature of floating point arithmetic, this is fairly likely when repeated a few hundred thousand times.

The next, more recent attempt at implementation, shrinks the outline (moved each vertex in the direction of it's bisector) a number of times, until termination. Figuring out where termination is a bit of a problem - my first reaction was to union the the resulting outline with itself and remove any negative areas (if the outline runs in the opposite direction to the original, it's area is, by convention, considered negative). The problem with this is that several intersections can happen within one shrinkage (question mark, above), making a mess of the mesh (and so it's union). In fact, since an arbitrary number of these events can happen in one shrink step, and we need to sort them out in order, this problem is just as complicated as the original! (doh) So not such a good approach - except maybe a time saver for the concave case :-

So I went back to Felkel's bisector collision with edges approach . My previous problem of dealing with these escaping bisectors could be dealt with by converting the n-sided outline shape, into n/2 planar slices through the completed skeleton. The following animations show a polygon with (dark) rainbow coloured edges, and the location of intersections with a slice collinear with a given edge (with a thick red edge). The intersections are in light rainbow colours:

I thought this approach would be successful, so much so that I made a nice series of images explaining the details.

But this approach turns out to be very fiddly. As the skeleton is constructed from the floor upwards we always remove edges (never adding them). Each time an edge is removed two other edges come together (unless we're at a peak). This means removing a edge from each 2d projection and re-running many intersections, which is a lot of book keeping (and it makes the already bad complexity even worse). Another complication is the need for a 2d representation for 3d faces (to represent parallel edges), this was done, but wasn't very tidy. In the end I learnt a lot about computational geometry, but it took ages (my current version took less than a day for rewrite). And the benefits of doing this way - more watertight boundaries - are more simply dealt with in 3d.

So...next time children you'll need an empty washing liquid up bottle and I'll show you how not to shoot both your feet at the same time while constructing the weighted straight skeleton.