Finding approximate shape regularities in reverse engineered solid models bounded by simple surfaces

ABSTRACT

Current reverse engineering systems are able to generate simple valid boundary representation (B-rep) models from 3D range data. Such models suffer from various inaccuracies caused by noise in the input data and algorithms. The quality of reverse engineered geometric models can potentially be improved by finding candidate shape regularities in such an initial model, and imposing a suitable subset of them on the model by using constraints, in a postprocessing step called beautification. Finding such candidate regularities is a necessary first step, and is discussed in this paper. Algorithms for analysis are presented which use feature objects to describe properties of faces, edges and vertices, and small groups of these elements in a B-rep model with only planar, spherical, cylindrical, conical and toroidal faces. The methods seek similarities between feature objects, e.g. axes which are parallel, for each property type. For each group of similar feature objects they also try to find a special feature object which might represent the group, e.g. an integer value which approximates the radius of similar cylinders. The feature objects used represent shape parameters, directions, axes and positions present in the model. Experiments show that the regularities found by these algorithms include the desired regularities. Although other spurious regularities which must be discarded in subsequent beautification steps are also produced, their number can be reduced by appropriate choice of tolerance values.

REFERENCES

• 1: D. H. Bailey, S. Plouffe. Recognizing Numerical Constants. In: Proc. Organic Mathematics Workshop, Simon Fraser University, December 1995.
• 2: Pál Benk˝ , Géza Kós , Tamás Várady , László Andor , Ralph Martin, Constrained fitting in reverse engineering, Computer Aided Geometric Design, v.19 n.3, p.173-205, March 2002 [doi>10.1016/S0167-8396(01)00085-1]
• 3: P. Benke, R. R. Martin, T. Varady. Algorithms For Reverse Engineering Boundary Representation Models. To appear in Computer-Aided Design, 2001.
• 4: A. Bjork. Numerical Methods For Least Squares Problems. SIAM, Philadelphia, 1996.
• 5: National Design Repository, Drexel University, <uri: http://edge.mcs.drexel.edu/repository/>.
• 6: David Eppstein, Fast hiearchical clustering and other applications of dynamic closet pairs, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.619-628, January 25-27, 1998, San Francisco, California, United States
• 7: H. R. P. Ferguson D. H. Bailey. A Polynomial Time, Numerically Stable Integer Relation Algorithm. NASA Technical Report RNR-91--032, December 1991.
• 8: John A. Hartigan, Clustering Algorithms, John Wiley & Sons, Inc., New York, NY, 1975
• 9: A. Y. Khinchin. Continued Fractions. Dover Publications, 1997.
• 10: G. K6s. An Algorithm To Triangulate Surfaces In 3D Using Unorganised Point Clouds. To appear in Computing, 2001.
• 11: 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
• 12: 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]
• 13: B. I. Mills, E 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.
• 14: W. B. Thompson, J. C. Owen, J. de St. Germain, S. R. Stark, T. C. Henderson. Feature-Based Reverse Engineering Of Mechanical Parts. IEEE Trans. on Robotics and Automation, 15(1):57--66, 1999.
• 15: T. Varady, R. R. Martin, J. Cox. Reverse Engineering Of Geometric Models - An Introduction. Computer-Aided Design, 29(4):255-268, 1997.
• 16: N. Werghi, R. Fisher, C. Robertson, A. Ashbrook. Object Reconstruction By Incorporating Geometric Constraints In Reverse Engineering. Computer-AidedDesign, 31(6):363-399, 1999.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

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

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Boundary representations
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

General Terms:
Design, Measurement, Performance, Theory

Keywords:
beautification, geometric interrogations and reasoning, reverse engineering, shape regularities, similarity