×

Constrained fitting in reverse engineering. (English) Zbl 0995.68152

Summary: This paper considers simultaneous fitting of multiple curves and surfaces to 3D measured data captured as part of a reverse engineering process, where constraints exist between the parameters of the curves or surfaces. Enforcing such constraints may be necessary (i) to produce models to sufficiently accurate tolerances for import into a CAD system, and (ii) to produce models which successfully reproduce regularities and symmetries required by engineering applications. The constraints to be satisfied may be determined manually, or more likely, by an automatic process. In the latter case, typically many more constraints are generated than can all be simultaneously satisfied. We present a new numerical method able to resolve conflicts between constraints. Secondly, reverse engineering generates large amounts of data. Constrained fitting methods are iterative in nature, and so an efficient method needs to restrict the amount of computation performed on each iteration. Our method achieves this through carefully constructed representations for objects and constraints, and approximations to distance functions. This paper describes our approach to constrained fitting, and illustrates its usefulness with some 2D and 3D examples taken from reverse engineering.

MSC:

68U07 Computer science aspects of computer-aided design
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abedie, J.; Carpentier, J., Generalization of the Wolfe reduced gradient method to the case of nonlinear constraints, (Fletcher, R., Optimization (1969), Academic Press: Academic Press London), 37-47
[2] Benkő, P.; Várady, T., Best fit translational and rotational surfaces for reverse engineering shapes, (The Mathematics of Surfaces IX (2000), Springer: Springer Berlin), 70-81 · Zbl 0967.65017
[3] Benkő, P.; Martin, R. R.; Várady, T., Algorithms for reverse engineering boundary representation models, Computer-Aided Design, 11, 839-851 (2001)
[4] (Brüderlin, B.; Roller, D., Geometric Constraint Solving and Applications (1998), Springer: Springer Berlin) · Zbl 0934.68094
[5] Celniker, G.; Gossard, D., Deformable curve and surface finite-elements for free-form shape design, Computer Graphics (SIGGRAPH 91), 25, 4, 257-266 (1991)
[6] Durand, C., Symbolic and numerical techniques for constraint solving, Ph.D. Thesis (1998), Purdue University Computer Science Department
[7] Fua, P.; Brechbuler, C., Imposing hard constraints on deformable models through optimisation in orthogonal subspaces, Computer Vision and Image Understanding, 65, 2, 148-162 (1997)
[8] Gibson, S. F.F.; Mirtich, B., A survey of deformable modeling in computer graphics (1997), Technical Report TR-97-19, Mitsubishi Electric Research Laboratory
[9] Hoffmann, C. M.; Joan-Arinyo, R., Symbolic constraints in constructive geometry, J. Symbolic Comput., 23, 287-300 (1997) · Zbl 0878.68135
[10] (Hoschek, J.; Kaklis, P., Advanced Course on FAIRSHAPE (1996), B.G. Teubner) · Zbl 0859.00013
[11] Joan-Arinyo, R.; Soto, A., A correct rule-based geometric constraint solver, Computers and Graphics, 21, 5, 599-609 (1997)
[12] Lamure, H.; Michelucci, D., Solving geometric constraint systems by homotopy, (Third ACM Symposium on Solid Modeling and its Applications (1995), ACM Press), 263-269
[13] Langbein, F. C.; Mills, B. I.; Marshall, A. D.; Martin, R. R., Recognizing geometric patterns for beautification of reconstructed solid models, (Proc. Int. Conf. on Solid Modelling and Applications (2001), IEEE Computer Society Press), 10-19
[14] Lukács, G.; Marshall, A. D.; Martin, R. R., Faithful least-squares fitting of spheres, cylinders, cones and tori for reliable segmentation, (Burkhardt, H.; Neumann, B., Proc. ECCV 98. Proc. ECCV 98, Lecture Notes in Computer Science, 1 (1998), Springer: Springer Berlin), 671-686
[15] Mills, B. I.; Langbein, F. C.; Marshall, A. D.; Martin, R. R., Estimate of frequencies of geometric regularities for use in reverse engineering of simple mechanical components, Internat. J. Shape Modeling (2001), Submitted
[16] Porrill, J., Optimal combination and constraints for geometrical sensor data, Internat. J. Robot. Res., 7, 6, 66-78 (1988)
[17] Robertson, C.; Fisher, R. B.; Corne, D.; Werghi, N.; Ashbrook, A. P., Investigating evolutionary optimisation of constrained functions to capture shape descriptions from range data, (Roy, R.; Furuhashi, T.; Chawdhry, P. K., Advances in Soft Computing—Engineering Design and Manufacturing (1999), Springer: Springer Berlin), 455-466
[18] Robertson, C.; Fisher, R. B.; Werghi, N.; Ashbrook, A. P., Fitting of constrained feature models to poor 3D data, (Proc. Adaptive Computing in Design and Manufacture (ACDM 2000) (2000)), 149-160
[19] Pratt, V., Direct least-squares fitting of algebraic surfaces, Computer Graphics (SIGGRAPH 87), 21, 4, 145-152 (1987)
[20] Terzopoulos, D.; Fleischer, K., Deformable models, The Visual Computer, 4, 6, 306-331 (1988)
[21] Triggs, B., Optimal estimation of matching constraints, (Koch, R.; Van Gool, L., 3D Structure from Multiple Images of Large-scale Environments (SMILE 98). 3D Structure from Multiple Images of Large-scale Environments (SMILE 98), Lecture Notes in Computer Science (1998), Springer: Springer Berlin) · Zbl 1034.68669
[22] Várady, T.; Martin, R. R.; Cox, J., Reverse engineering of geometric models—an introduction, Computer-Aided Design, 29, 4, 255-268 (1997)
[23] Weiß, V.; Renner, G.; Várady, T., Reconstruction of swept free-form features from measured data points, (Proc. 32nd CIRP International Seminar on Manufacturing Systems (1999)), 33-41
[24] Welch, W.; Witkin, A., Variational surface modeling, Computer Graphics (SIGGRAPH 92), 26 (1992)
[25] Werghi, N.; Fisher, R. B.; Robertson, C.; Ashbrook, A. P., Modelling objects having quadric surfaces incorporating geometric constraints, (Proc. 5th European Conference on Computer Vision, Vol. II (1998)), 185-201
[26] Werghi, N.; Fisher, R. B.; Robertson, C.; Ashbrook, A., Improvement of quadric surface estimation by global fitting, Internat. J. Shape Modelling, 6, 1, 65-78 (2000)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.