but which is procedural?

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

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

[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

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, without any extra light, on a canon 500d. Sorry for the shaky bits.

sony cw "notebook"/laptop first thoughts

[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

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


Basic 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-slatted 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 refered 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 then it becomes very difficult to separate these symmetries.

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

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