Academic Facets: News and Views from Spatial's University Community

[#1]

I have an old book called the “Principles of computer-aided design” from the 1980’s which gives a broad introduction to the fundamentals of CAD/CAM systems, from kinematics and geometric modelling through to aspects of Artificial Intelligence (AI). Although the basics are unchanged, many of the topics covered have advanced to the point where the “state of the art” illustrations now looks dated. But it is striking that progress hasn’t been uniform and chapters covering topics like Expert Systems and Shape Synthesis describe technologies that appear to have changed only incrementally in 20 years.

The chapter on “shape grammars” is like this, clever, fascinating stuff and yet stuck for ever repeating a few impressive tricks (another “Palladian villa” anyone), because no one could figure-out how to apply the approach in an interactive CAD system. But a few weeks ago I realised I was wrong to think the subject was moribund.

Shape grammars are a compelling idea: in the same way an English sentence has a grammar (i.e. noun phrase, verb phrase, adjective etc) that defines a “correct” sequence of words, “shape grammars” offer the prospect of defining when collections of geometric primitives (i.e. lines, circles, blocks, cylinders etc) are arranged in away that match a pattern, or structure. For example, although there are many different designs of chessboard (ie different colours, materials, playing pieces) they all conform to some implicit understanding we have of the object’s grammar.

It’s a great idea, but of course there are some catches; firstly it’s not clear what the equivalent of nouns and verbs are in geometry (perhaps edges or face, or volumes, or cells, or ?) and secondly system that use grammars to generate shapes have a tendency to explode, with millions of possible designs being generated by only a few grammar rules.

So until recently I believed this is where the story ended, to the best of my knowledge, all the shape grammar researchers had retired or moved away! But then I was invited to lunch with a group involved in a project called “Design Synthesis and Shape Generation” (DSSG)”. http://www.engineering.leeds.ac.uk/dssg/index.htm

Seeing the DSSG’s presentations I realized that shape grammars were alive and, possibly, a work round for these long standing issues had been found by making the definition and execution of the grammar “rules” highly interactive.
You can see the DSSG system on YouTube.

The video starts slowly, but keep watching and you will see several neat, but rather subtle ideas towards the end. Notice, for example, that the shape matching has variable precision, the user can interactively define the grammar rules, and the deformations applied to the profiles are independent of the underlying representations (ie straight lines can be warped into free form shapes).

The shape matching algorithm (that makes the system so forgiving) has not been published yet, but I can say that it is an application of a technique well know in computer vision for image matching. The DSSG system in the demo video only handles 2D geometry but 3D shape similarity matching has also been used to support shape generation.

The prolific Thomas Funkhouser, at Princeton University, described a system at SIGGRAPH 04 which synthesized new 3D shapes by carrying out partial similarity matches. The process goes something like this: if you are designing a chair, you upload an existing chair model, select a leg, ask the system to search its 3D data base for all models that contain “similar” leg like geometry, select the legs you like and use a 3D cut and paste facility to insert the new geometry into your model. The paper describing the process is here and a movie of the system in action is also available for download as an AVI file.

http://www.cs.princeton.edu/~funk/sig04a.pdf

Are the two approaches so different? Both are automatically recognising shape features in a model and replacing them with a different form to create a new, hybrid shape. In one case the replacement shape is generate by grammar rules (DSSG) and in the other, features extracted from a database of 3D models (Princeton). I don’t think designers will be throwing away their paper and pencils anytime soon, but at least there are signs of progress towards tools supporting for real creative 3D design.