Detecting approximate incomplete symmetries in discrete point sets

ABSTRACT

Motivated by the need to detect design intent in approximate boundary representation models, we give an algorithm to detect incomplete symmetries of discrete points, giving the models' potential local symmetries at various automatically detected tolerances. Here, incomplete symmetry is defined as a set of incomplete cycles which are constructed by, e.g., a set of consecutive vertices of an approximately regular polygon, induced by a single isometry. All seven 3D elementary isometries are considered for symmetry detection. Incomplete cycles are first found using a tolerance-controlled point expansion approach. Subsequently, these cycles are clustered for incomplete symmetry detection. The resulting clusters have welldefined, unambiguous approximate symmetries suitable for design intent detection, as demonstrated experimentally.

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: Barratt, K. 1989. Logic and Design in Art, Science and Mathematics. Herbet Press, London.
• 3: Peter Brass , Christian Knauer, Testing congruence and symmetry for general 3-dimensional objects, Computational Geometry: Theory and Applications, v.27 n.1, p.3-11, January 2004 [doi>10.1016/j.comgeo.2003.07.002]
• 4: Peter Brass, On finding maximum-cardinality symmetric subsets, Computational Geometry: Theory and Applications, v.24 n.1, p.19-25, January 2003
• 5: D. W. Eggert , A. Lorusso , R. B. Fisher, Estimating 3-D rigid body transformations: a comparison of four major algorithms, Machine Vision and Applications, v.9 n.5-6, p.272-290, March 1997 [doi>10.1007/s001380050048]
• 6: C. H. Gao , F. C. Langbein , A. D. Marshall , R. R. Martin, Approximate Congruence Detection of Model Features for Reverse Engineering, Proceedings of the Shape Modeling International 2003, p.69, May 12-15, 2003
• 7: Gao, X., Lin, Q., and Zhang, G. 2006. A C-tree decomposition algorithm for 2D and 3D geometric constraint solving. Computer-Aided Design 38, 1, 1--13.
• 8: Sebastian Iwanowski, Testing approximate symmetry in the plane is NP-hard, Theoretical Computer Science, v.80 n.2, p.227-262, March 29, 1991
• 9: Langbein, F., Marshall, A., and Martin, R. 2004. Choosing consistent constraints for beautification of reverse engineered geometric models. Computer-Aided Design 36, 3, 261--278.
• 10: Li, M., Langbein, F., and Martin, R. 2006. Detecting approximate symmetries of discrete point subsets. submitted.
• 11: B. I. Mills , F. C. Langbein , A. D. Marshall , R. R. Martin, Approximate symmetry detection for reverse engineering, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.241-248, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376985]
• 12: Mills, B., Langbein, F., Marshall, A., and Martin, R. 2001. Estimate of frequencies of geometric regularities for use in reverse engineering of simple mechanical components. Tech. Rep. GVG 2001-1, Cardiff University. http://ralph.cs.cf.ac.uk/papers/Geometry/survey.pdf
• 13: Niloy J. Mitra , Leonidas J. Guibas , Mark Pauly, Partial and approximate symmetry detection for 3D geometry, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 14: Joshua Podolak , Philip Shilane , Aleksey Golovinskiy , Szymon Rusinkiewicz , Thomas Funkhouser, A planar-reflective symmetry transform for 3D shapes, ACM Transactions on Graphics (TOG), v.25 n.3, July 2006
• 15: Robins, G., Robinson, B., and Sethi, B. 1999. On detecting spatial regularity in noisy images. Information Processing Letters 69, 189--195.
• 16: Sugihara, K. 1984. An nlogn algorithm for determining the congruity of polyhedra. Journal of Computer and System Sciences 29, 11, 36--47.
• 17: Changming Sun , Jamie Sherrah, 3D Symmetry Detection Using The Extended Gaussian Image, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.19 n.2, p.164-168, February 1997 [doi>10.1109/34.574800]
• 18: Tate, S., and Jared, G. 2003. Recognising symmetry in solid models. Computer-Aided Design 35, 7, 673--692.
• 19: Varady, T., Martin, R., and Cox, J. 1997. Reverse engineering of geometric models - an introduction. Computer-Aided Design 29, 4, 255--268.
• 20: Weyl, H. 1952. Symmetry. Princeton University Press.
• 21: Hagit Zabrodsky , Shmuel Peleg , David Avnir, Symmetry as a Continuous Feature, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.17 n.12, p.1154-1166, December 1995 [doi>10.1109/34.476508]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

Keywords:
approximate incomplete symmetry, design intent, reverse engineering