Approximate symmetry detection for reverse engineering

ABSTRACT

The authors are developing an automated reverse engineering system for reconstructing the shape of simple mechanical parts. B-rep models are created by fitting surfaces to point clouds obtained by scanning an object using a 3D laser scanner. The resulting models, although valid, are often not suitable for purposes such as redesign because expected regularities and constraints are not present. This information is lost because each face of the model is determined independently. A global approach is required, in particular one that is capable of finding symmetries originally present. This paper describes a practical algorithm for finding global symmetries in suitable B-rep models built from planes, spheres, cylinders, cones and tori. It has been implemented and used to determine approximate symmetries of models with up to about 200 vertices in reasonable time. The time performance of the algorithm in the worst case is bounded by O(n ^3.5 log⁴ n), and a justification is given that on common engineering objects it takes about O(n² log⁴ n), making it a practical tool for use in a reverse engineering package. Details of the algorithm are given, along with some results from a number of illustrative test runs.

REFERENCES

• 1: Helmut Alt , Kurt Mehlhorn , Hubert Wagener , Emo Welzl, Congruence, similarity and symmetries of geometric objects, Discrete & Computational Geometry, v.3 n.3, p.237-256, Jan., 1988 [doi>10.1007/BF02187910]
• 2: P. Benke, R. Martin, T. Varady. Algorithms For Reverse Engineering Boundary Representation Models. To appear in Computer-Aided Design, 2001.
• 3: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 4: Jacob E. Goodman , Joseph O'Rourke, Handbook of discrete and computational geometry, CRC Press, Inc., Boca Raton, FL, 1997
• 5: Sebastian Iwanowski, Testing approximate symmetry in the plane is NP-hard, Theoretical Computer Science, v.80 n.2, p.227-262, March 29, 1991
• 6: X. Y. Jiang , H. Bunke, A simple and efficient algorithm for determining the symmetries of polyhedra, CVGIP: Graphical Models and Image Processing, v.54 n.1, p.91-95, Jan. 1992 [doi>10.1016/1049-9652(92)90037-X]
• 7: Frank Langbein , Bruce I. Mills , A. Dave Marshall , Ralph R. Martin, Finding approximate shape regularities in reverse engineered solid models bounded by simple surfaces, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.206-215, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376981]
• 8: E. Lockwood, R. Macmillan. Geometric Symmetry, Cambridge University Press, 1978.
• 9: Gabor Lukács , Ralph Martin , Dave Marshall, Faithful Least-Squares Fitting of Spheres, Cylinders, Cones and Tori for Reliable Segmentation, Proceedings of the 5th European Conference on Computer Vision-Volume I, p.671-686, June 02-06, 1998
• 10: B. I. Mills, F. C. Langbein, A. D. Marshall, R. R. Martin. Estimate Of Frequencies Of Geometric Regularities For Use In Reverse Engineering Of Simple Mechanical Components. Submitted to Computer-Aided Design, 2000.
• 11: K. Sugihara. An nlogn Algorithm For Determining The Congruity Of Polyhedra. Journal of Computer and System Science, vol. 29, pages 36-47, 1984.
• 12: S. Tate. Symmetry And Shape Analysis For Assembly-Oriented CAD. PhD Thesis, Cranfield University, 2000.
• 13: T. Vady, R. Martin, J. Cox. Reverse Engineering Of Geometric Models - An Introduction. Computer-Aided Design, 29(4):255-268, 1997.
• 14: J. Wolter, T. Woo, R. Volz. Optimal Algorithms For Symmetry Detection In Two And Three Dimensions. The Visual Computer, vol. 1, pages 37--48, 1985.
• 15: Derick Wood, Data structures, algorithms, and performance, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1993
• 16: H. Zabrodski, D. Avnir. Measuring Symmetry In Structural Chemistry. Advances in Molecular Structure Research, vol. 1, pages 1-31, 1995.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.7 Distribution, Maintenance, and Enhancement
          Subjects: Restructuring, reverse engineering, and reengineering

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
  I.4 IMAGE PROCESSING AND COMPUTER VISION

  J. Computer Applications

General Terms:
Algorithms, Design, Measurement, Performance, Reliability, Theory

Keywords:
approximate symmetry, beautification, geometric interrogations and reasoning, reverse engineering