Wednesday, March 03, 2010

first year report

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.


  1. Hi,
    I didn't read your full report but just saw one of our (old) promotional image.
    very old. Don't hesitate to contact us if you want better material.

    I'll ping you back when I have read the report.

    Best Rgds,

  2. Hi
    I was working in procedural city framework in C++ (road, facade & indoor with real time visualisation). Your blog is a great source of information.

    PS : In your report you have a litte mistake page 13 : 60% + 3*10% = 90% where are the 10% missing. (Can have your source for this information)

  3. @Sophiane: Thanks! Yes you're quite correct, I think programming should be 20%. Source was a British Department of Trade and Industry Report:

    I should also have mentioned that it was the typical breakdown of a Japanese developer.

    Your work sounds fun - is it commercial? do you have screenshots? :)

    I've got some corrections from several people, so I'll update this report sometime next week.

  4. @soufiane : français ? je serai heureux de discuter avec un autre enthousiaste de la génération procédurale. Dans quel cadre le framework ?

  5. @twak : Thanks. It's personnal Work. I haven't real screenshot I just finish road generator. I begin facade generator with topological data structure (Generalized Map). When I finish this part I will show you my work.

    @LBarret : Vous êtes français ? Mon framework est un travail personnel. On pourrait en discuter par mail, MSN... Vous aussi devellopez des outils procéduraux ?

  6. @soufiane : notre soft : Urban PAD

  7. This comment has been removed by the author.

  8. @LBarret : Mais bien sur je connais gamr7 et Ürban PAD. Quand on fait des recherches sur la génération procédural on tombe forcement sur ces pages (UrbanPAD, CityEngine, ...). Est ce que votre entreprise chercherais des stagiaires parce que par le plus grand des hasards pour valider mon diplôme je suis à la recherche d'un stage ?

    @twak : To show my begin work on procedural generation you can see a first acticle of my portfolio : in French. You can just see a picture of road network I will give a full article when I finish facade generation

  9. @Soufiane : Envoie un CV à contact at, il y a peut-être quelque chose à faire.