逆向工程经典Reverse engineering

PII: SSOOlO-4485(96)00054-l Computer-Aided Design. Vol. 29, No 4, pp. 255-268, 1997 0 1997 Elseviar Science Ltd PrInted I” Great Britain. All rights reserved 001~4485/97/517.00+0.00 ELSEVIER Research Reverse engineering of geometric models-an introduction Tam&s VArady, Ralph R Martin* and Jordan Coxt In many areas of industry, it is desirable to create geometric models of existing objects for which no such model is available. This paper reviews the process of reverse engineering of shapes. After identifying the purpose of reverse engineering and the main application areas, the most important algorithmic steps are outlined and various reconstruction strategies are presented. Pros and cons of various data acquisition techniques are described with related problems of boundary representation model construction. Specific issues addressed include charac- terization of geometric models and related surface representa- tions, segmentation and surface fitting for simple and free-form shapes, multiple view combination and creating consistent and accurate B-rep models. The limitations of currently known solutions are also described, and we point out areas in which further work is required before reverse engineering of shape becomes a practical, widely-available engineering tool. 0 1997 Elsevier Science Ltd. All rights reserved. Keywords: CAD, geometric modelling, reverse engineering, scanning, segmentation, surface fitting, boundary models INTRODUCTION Reverse engineering is a rapidly evolving discipline, which covers a multitude of activities. In this paper we will only be concerned with reverse engineering of shape, but a broader interpretation of the term to involve understanding of design intents and mechanisms is also possible. While conventional engineering transforms engineering concepts and models into real parts, in reverse engineering real parts are transformed into engineering models and concepts. The advantages of the extensive use of CAD/CAM systems need not be Computer and Automation Research Institute, Hungarian Academy of Sciences, 1111 Budapest, Kende u. 13-17, Hungary * University of Wales, Cardiff, PO Box 916, Cardiff CF2 3XF, UK t Brigham Young University, 133 CB, Provo, UT 84602, USA Paper received: 1S October 1995. Revised: 15 May 1996 reiterated here. The existence of a computer model provides enormous gains in improving the quality and efficiency of design, manufacture and analysis. Reverse engineering typically starts with measuring an existing object so that a surface or solid model can be deduced in order to exploit the advantages of CGD/CAM technologies. There are several application areas of reverse engineer- ing. It is often necessary to produce a copy of a part, when no original drawings or documentation are available. In other cases we may want to re-engineer an existing part, when analysis and modifications are required to construct a new improved product. In areas where aesthetic design is particularly important such as in the automobile industry, real-scale wood or clay models are needed because stylists often rely more on evaluating real 3D objects than on viewing projections of objects on high resolution 2D screens at reduced scale. Another important area of application is to generate custom fits to human surfaces, for mating parts such as helmets, space suits or prostheses. It seems important to clearly distinguish between the concepts of a 30 copier and a 30 scanner. A photocopier takes a piece of paper and produces another piece of paper just like the original. A 3D copier is a device which takes a solid object and makes another one of just the same shape (let us ignore material). In fact, copy machining has been a well established technology for a long time. A scanner however, in 2D, not only inputs a page of text into the computer, but can also recognize the characters and figures, thus providing a text file and graphical structures. Similarly, a 3D scanner will not only capture raw data from the object, but the data will be interpreted and some computer model will be created. Now, not only may a single copy be generated, but knowledge of the shape is obtained, and thus we can derive new shapes, make variations, analyse properties and determine characteristic quantities such as volume or surface area. The ultimate goal of reverse engineering systems is to realize an intelligent 3D scanner. However, there is a long way to go. Even capturing shape and translating it into a CAD model is a difficult and complex problem. In spite of several encouraging partial results in particular 255 Reverse engineering of geometric models: T Vkady et a/. I 1. Data capture I 1 I 2. Preprocessing 1 3. Segmentation and surface fitting 4 4. CAD model creation Figure 1 Basic phases of revel-x cngineerinp areas. a fully automatic solution to build a complete and consistent CAD model is still a goal. The purpose of this paper is to describe the most important elements of a reverse engineering system and to identify problems. which still require further research. At the same time. we attempt to summarize the basic achievements of current reverse engineering research. as well. The reverse engineering procedure can be characterized by the flowchart in Figuw I. Of course this sequence is fairly notional. In fact, these phases are often overlapping and instead of the sequential process shown, several iterations are required. Never- theless, this outline may help the reader to understand the information flow and serves as a basis for organizing the content of our paper. A crucial part of reverse engineering is dutu ucyuisition. After reviewing the most important measuring techni- ques, the relative merits and difficulties associated with these methods are discussed. Often. methods for reverse engineering are developed based on simulated data acquisition only. Our experience is that a certain amount of reservation is needed in such cases, as actual physical measurements may display many problems and undesir- able side effects not present in artificial data. As was indicated earlier, the main topic of this paper is the geometric part of reverse engineering. Data structures for representing shape can vary from point clouds to complete boundary representation models. We give later a hierarchy qf shape models. This is particularly important since the representation chosen fundamentally determines the computational algorithms applied to the data sets. The most critical parts of reverse engineering are segmentation and suyfaw .fitting. By means of these processes. data points are grouped into sets to which an appropriate single surface can be fitted. We believe that segmentation and surface fitting methods must be carefully matched to each other. A range of techniques and problems will be described in the following sections. including methods for various surface representations used in CAD ranging from planes and quadrics to composite free-form surfaces. Data acquisition systems are constrained by physical considerations to acquire data from a limited region of an object’s surface. Hence, multiple scans must be taken to completely measure a part. See the section on combining multiple vicw:s. The problems of creuring geometric, models will be discussed in the last section. There are various representa- tions providing approximate or incomplete models which may be sufficient for certain applications. such as computer vision, animation, collision checking. etc. DATA ACQUISITION METHODS .’ 1.. ..-.. NON-CONTACT METHODS TACTH,E METHODS TRIAN(:I~I.ATIOU 1 \, \ IMAGE ANALYSIS RANGING ‘, STRLlCTI!RIIL) LIGHTIN<; INTERFEROMETRY Figure 2 Classiticatwn of data acquisition methods For ( ALI purposes these will not be adequate. Here WC restrict our scope of interest and concentrate on accurate and consistent boundary representation models. using standard surfaces acceptable by commercial C‘AI)!C.AM systems. Identifying sharp edges, adding blends, provid- ing proper continuity where smooth connections are needed, tidying up the model and enforcing constraints are all part of the problem. Finally. in the conclusion we present our view of the current status of this technology and what are the most important research issues. This paper is an overview, so we do not attempt to describe individual topics in detail. We try to concentrate on important conceptual issues, while the reference list at the end will help readers to find the most relevant research contributions. DATA ACQUISITION There are many different methods for acquiring shape data. as shown in Figure 2. Essentially, each method uses some mechanism or phenomenon for interacting with the surface or volume of the object of interest. There are non-contact methods, where light, sound or magnetic fields are used, while in others the surface is touched by using mechanical probes at the end of an arm (trrctik methods). In each case an appropriate analysis must be performed to determine positions of points on the object’s surface from physical readings obtained. For example, in laser range finders, the time-of-flight is used to determine the distance travelled, and in image analysis the relative locations of landmarks in multiple images are related to position. Each method has strengths and weaknesses which require that the data acquisition system be carefully selected for the shape capture functionality desired. This section will discuss the principles of various methods and the next section will address the practical problems of acquiring data. Jarvis’ papersY is a very good survey on the different methods of data acquisition. Optical methods of shape capture are probably the broadest and most popular with relatively fast acquisition rates. There are five important categories of optical methods we discuss here: triangulation, ranging, inter- ferometry, structured lighting and image analysis. Triangulation is a method which uses location and angles between light sources and photo sensing devices to deduce position. A high energy light source is focused and projected at a prespecified angle at the surface of interest. A photosensitive device, usually a video camera, senses the reflection off the surface and then by using geometric triangulation from the known angle and distances. the position of a surface point relative to a 256 Reverse engineering of geometric models: T VBrady et al. reference plane can be calculated. The light source and the camera can be mounted on a travelling platform which then produces multiple scans of the surface. These scans are therefore relative measurements of the surface of interest. Various different high energy light sources are used, but lasers are the most common. Triangulation can acquire data at very fast rates. The accuracy is determined by the resolution of the photosensitive device and the distance between the surface and the scanner. Motavalli and Bidanda4* present a reverse engineering strategy using laser triangulation. Moss et al.41 present a detailed discussion of a classic laser triangulation system used to capture shape data from facial surfaces. A discussion of accuracy and applications is also included. The use of laser triangulation on a coordinate measuring machine is presented by Modjarrad3*. These references give a broad survey of methods, approaches to and limitations of triangulation. Ranging methods measure distances by sensing time- of-flight of light beams; practical methods are usually based on lasers and pulsed beams. Interferometry methods measure distances in terms of wavelengths using inter- ference patterns. This can be a very accurate method of measurement since visible light has a wavelength of the order of hundreds of nanometres, while most reverse engineering applications distances are in the centimetre to metre range. In principle, other parts of the electro- magnetic spectrum could also be used. In practice, a high energy light source is used to provide both a beam of monochromatic light to probe the object and a reference beam for comparison with the reflected light. Moring et al.40 describe a range finder based on time-of-flight calculations. The article presents some information on accuracy and performance. Jarvis3’ presents an in-depth article on time-of-flight range finders giving detailed results and analysis. Structured lighting involves projecting patterns of light upon a surface of interest and capturing an image of the resulting pattern as reflected by the surface. The image must then be analysed to determine coordinates of data points on the surface. A popular method of structured lighting is shadow Moire, where an inter- ference pattern is projected onto a surface producing lighted contour lines. These contour lines are captured in an image and are analysed to determine distances between the lines. This distance is proportional to the height of the surface at the point of interest and so the coordinates of surface points can be deduced. Structured lighting can acquire large amounts of data with a single image frame, but the analysis to determine positions of data can be rather complex. Will and Pennington use grids projected onto the surface of objects to determine point locations. Wang and Aggarwa16’ use a similar approach but use stripes of light and multiple images. The final optical shape capture method of interest is image analysis. This is similar to structured lighting methods in that frames are analysed to determine coordinate data. However, the analysis does not rely on projected patterns. Instead, typically, stereo pairs are used to provide enough information to determine height and coordinate position. This method is often referred to as a passive method since no structured lighting is used. Active methods are distinguished from passive methods in that artificial light is used in the acquisition of data. Correlation of image pairs and landmarks within the images are big difficulties with this method and this is why active methods are preferred. Another image analysis approach deals with lighting models, where an image is compared to a 3D model. The model is modified until the shaded images match the real images of the object of interest. Finally, intensity patterns within images can be used to determine coordinate information. There is a vast amount of literature on stereo imaging, and we just cite four papers that address this technique. Nishihara43 uses a real-time binocular stereo matching algorithm for making rapid range measurements. Posdamer and Altschuler4’ describe a method for real- time measurement of surface data using stereo methods. Also, see Woodham’s work65 on shape from shading. Finally, a contribution by Rockwood and Winget in this special issue describes an energy minimization approach of a mesh to match a collection of 2D images. Tactile methods represent another popular approach to shape capture. Tactile methods touch a surface using mechanical arms. Sensing devices in the joints of the arm determine the relative coordinate locations. These methods are mostly limited by the measuring device limitations. For example, a 3-axis milling machine can be fitted with a touch probe and used as a tactile measuring system. However, it is not very effective for concave surfaces. There are many different robotic devices which are used for tactile measurement. These methods are among the most robust (i.e. less noise, more accurate, more repeatable, etc.), but they are also the slowest method for data acquisition. Probably the most popular method is the use of coordinate measuring machines (CMM). These machines can be programmed to follow paths along a surface and collect very accurate, nearly noise-free data. Xiong66 gives an in depth discussion of measurement and profile error in tactile measurement. Sahoo and Menq49 use tactile systems for sensing complex sculptured surfaces. Butler6 provides a comparison of tactile methods and their performance. The final type of data acquisition methods we will examine are acoustic, where sound is reflected from a surface, and magnetic, where a magnetic field touches the surface. Acoustic methods have been used for decades for distance measuring. Sonar is used extensively for this purpose. Automatic focus cameras often use acoustic methods to determine range. The method is essentially the same as time-of-flight, where a sound source is reflected off a surface and then distance between the source and surface is determined knowing the speed of sound. Acoustic interference or noise is often a problem as well as determining focused point locations. Dynamic imaging is used extensively in ultrasound devices where a transducer can sweep a cross-section through an object to capture material data internal to an object. Magnetic field measurement involves sensing the strength of a magnetic field source. Magnetic touch probes are used which usually sense the location and orientation of a stylus within the field. A trigger allows the user to only record specific point data once the stylus is positioned at a point of interest. Magnetic resonance is used in similar applications to ultrasound when internal material properties are to be measured. MRI (magnetic resonance) activates atoms in the material to be measured and then measures the response. Watanabe62 uses an ultrasonic sensor for object recognition and Tsujimura et aZ.57 place the ultrasonic device on a manipulator. To sum up, all measuring methods must interact with 257 Reverse engineering of geometric models: T VBrady et a/. the surface or internal material using some phenomenon. either light. sound. magnetism or physical contact. The speed with which the phenomenon operates as well as the speed of the sensor device determines the speed of the data acquisition. The amount of analysis needed to compute the measured data and the accuracy arc also basically determined by the sensor type selected. On the technical parameters of various commercial 3D digitizers see the table in Reference 64. PRACTICAL PROBLEMS OF DATA ACQUISITION There are many practical problems with acquiring usable data. the rn;!jor ones being: . calibration, 0 accuracy. l accessibility. 0 occlusion. 0 fixturing. 0 multiple views. 0 noise and incomplete data. l statistical distributions of parts. and l surface finish. Calibration is an essential part of setting up and operating a position measuring device. Systematic sensing errors can occur through lens distortions, non- linear electronics in cameras, and similar sources. An) sensing must be calibrated so as (i) to accurately determine parameters such as camera points and orientations, and (ii) to model and allow for as accurately as possible systematic sources of error. Most of the papers cited present some discussion of accuracy ranges for the various types of scanners, but all methods of data acquisition require accurate calibration. Optical scanners’ accuracies typically depend largely on the resolution of the video system used. Distance from the measured surface and accuracy of the moving parts of the scanning system all contribute to the overall measurement error. Accessibility is the issue of scanning data that is not easily acquired due to the configuration or topology of the part. This usually requires multiple scans but can also make some data impossible to acquire with certain methods. Through holes are typical examples ol inaccessible surfaces. Occlusion is the blocking of the scanning medium due to shadowing or obstruction. This