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

[#1]

It is over a decade now since 3D modellers became wide spread on PCs and today even small engineering companies can have tens of thousands of 3D models on their hard disks.

One obvious, but largely unanticipated, problem resulting from this success is simply keeping track of the contents of all the CAD files. Although it is easy to give every model file an ID number, this does not help exploit the information contained in these increasingly vast archives. Two examples of questions a part number can’t answer:

• Have we ever made a component with a similar shape before? (If so I want to copy the process plan used to manufacture it),

• How many duplicates of this model exist on the network? (If so I am going to rationalise them all into a single part number).

In days of drawing offices both these questions would be answered by long serving staff, but in today’s globally, digitally, distributed enterprise, with its itinerate work force, human memory is not an option. It is questions like these that motivated academics to start investigating tools for searching and navigating large databases of 3D models back in the 1990s.

Initially the academic work focused largely on algorithms for indexing models based on geometric similarity indexes (e.g. compactness) or feature content (e.g. imagine an SQL expression for returning all models containing a 12mm diameter hole). The results of this work  have been respectable rather than spectacular. Often automated search systems can get close to finding a good match, and isolate, say, 30 candidates out of 1000 parts but never reach human levels of discrimination (which might effortlessly choose the best, say,  3 out of a 1000 candidates).

However academics have a tendency to move the “goal posts” to particularly difficult places (overlooking the fact that, sometimes, effective solutions can be created from imperfect theory)!

Over the summer a small Scottish start-up (founded by an ex-academic colleague of mine, Dr Andrew Sherlock) has released an example of just this observation: a 3D search system that is effective even without “perfect” similarity matching algorithms.  

The Shapespace “PartBrowser” provides a view of a CAD model database, which appears to the user as a 3D array of components rotating in space. The user can zoom, and pan through this display in the normal way, but the brilliant insight embedded in the product is its ability to reorder the parts around a target (selected with a mouse click) dependent on their shape similarity.

So clicking on a particular shape of, say, bracket causes the array to refresh so that the components closest (ie adjacent) to it on the display are the most similar in shape.

Perhaps this doesn’t sound like much, but because you can instantly see all the results returned the fact that some of them might not be perfect matches to the target shape is not important. Even if the 3D search engine returns a whole bunch of “wrong” answers your eye is instantly drawn to the correct one. Like a lot of good ideas, the approach obvious ….when you see the video at the website   

( http://www.partbrowser.com/features.php )

Naturally behind the apparent simplicity, are some complex algorithms that carry out the rearrangement of the parts to reflect their geometric similarity. There is also hidden sophistication in the interface’s display allegory. For example if there are too many parts to display on the screen, the system’s shape matching algorithms  partition the database into families of “similar” shapes and displays a single, “representative”, family member in the array.

If you select a “representative” component (as a result of your initial search) it is like opening a folder that contains that shape’s family. Of course there can be families of parts, with-in families (i.e. nesting), so the approach can potentially support arbitrarily large numbers of models. Interestingly the makers also claim that by analysing (i.e. logging) the user’s actions, the system is able to refine the behaviour of its shape matching algorithms to better reflect what the user perceives as 'similar'.

What impact does this sort of interface have on the academic research agenda? Two I think: firstly that so called “false negatives” is the parameter to minimise in any 3D search engines performance. And secondly …..this is the first interface for a serious application, I’ve seen, that has aspects of a computer game……lots of  graphics, all over the screen, moving and rotating….

I’m probably too old to use it properly…but I can’t help wondering if it could be usefully interfaced to a Wii ?