Introduction

Traditional processes for reverse engineering objects and structures from 3D datasets have been initially data (e.g. triangulated models) and parametric surface (e.g. quadric surface) driven. These approaches has been successful for simple parts, but have resulted in reconstructions that have `frozen-in' errors. Typical errors are surfaces at incorrect relative positions or artifacts arising from noisy or missing data.

For several years our research group at Edinburgh University has been exploring `knowledge-based' techniques to help overcome these and other problems. The underlying theme behind this set of techniques is the exploitation of general knowledge about the domain of objects being reconstructed. The reconstruction process is not ``model-based'' reverse engineering, as then there would be no point to building the models - this would not be ``reverse engineering''. On the other hand, the knowledge is not arbitrary, because the objects that humans construct are not arbitrary: the shapes of most normal objects follow standard conventions arising from tradition, utility or engineering design. This is a ``knowledge-based'' approach.

Figure 1: Constrained quadric surface recovery.

We argue that exploiting this extra knowledge allows improved reverse engineering. This paper presents several different examples of the general approach, summarizing results from the full publications, which are cited within and can be found at: http://www.dai.ed.ac.uk/homes/rbf/publications.html.

One of the assumptions underlying the work summarized here is that the reverse engineering/reconstruction process need not be fully automated. Computers are good at data analysis and fitting; humans are good at recognizing and classifying patterns. Thus we are working in a cooperative problem solving paradigm, where a human might hypothesize that a given relationship holds (e.g. two surfaces are potentially parallel) and the computer can either help verify the relationship (e.g. calculate the probability that they are parallel) or compute some parameter that results from the relationship (e.g. the separation between the surfaces).

From these general ideas, we have been exploring techniques to improve reverse engineering of objects from 3D point data sets. These main themes are explored in the sections that follow:

1. There are many constraints on feature relationships in manufactured objects and buildings. Exploiting these constraints improves the recovery of object models.
2. General shape knowledge can allow recovery even when data is very noisy, sparse or incomplete.
3. Complete data acquisition can be impossible in practice, but inference of much occluded data is possible.
4. Euclidean fitting is now fast enough to be practical and gives better results.
5. Many of these recovery problems require discovery of shape and position parameters that satisfy the knowledge-derived constraints. Evolutionary search methods can be used to do this search effectively.