Computational intelligence in CAD/CAM applications

ABSTRACT

This paper presents a fundamental, direct, and powerful approach to the surface/surface intersection problem in CAD/CAM applications. The algorithm is designed and implemented in three steps: a) Preprocessing - locate the potentially intersecting sections of the surfaces and decompose the surfaces into surface elements within specified flatness tolerance; b) Intersection- decompose the possibly intersecting pairs of surface elements into continuous surface triangulations to find the approximate intersections between the pairs of surface elements; c) Postprocessing- assemble the intersection primitives into curves of intersection, refine the accuracy of computed intersection points, and compact the intersection curves. This surface/surface intersection algorithm is applicable to the widest class, Co, of parametric surfaces, an enhancement over the existing algorithms applicable to only Ck, k ≥ 1, surfaces. This implementation, based on computational intelligence, requires no human interaction for intersection curve pattern recognition.

REFERENCES

• 1: Akima, Hiroshi, On estimating partial derivatives for bivariate interpolation of scattered data, Rocky Mountain Journal of Mathematics, 14, 1984, pp. 41-52.
• 2: Robert E. Barnhill , Gerald Farin , M. Jordan , B. R. Piper, Surface/surface intersection, Computer Aided Geometric Design, v.4 n.1-2, p.3-16, July 1987 [doi>10.1016/0167-8396(87)90020-3]
• 3: Dokken, T., Finding intersections of B-spline represented geometries using recursive subdivision techniques, Computer Aided Geometric Design, 2, 1985, pp. 189-195.
• 4: Daniel Filip , Robert Magedson , Robert Markot, Surface algorithms using bounds on derivatives, Computer Aided Geometric Design, v.3 n.4, p.295-311, 1987 [doi>10.1016/0167-8396(86)90005-1]
• 5: Houghton, E. G., Emnett, R. F., Factor, J. D., & Sabharwal, C. L., Implementation of a divide-and-conquer method for intersection of parametric surfaces, Computer Aided Geometric Design, 2, 1985, pp. 173-183.
• 6: Lane, J. M. and Riesenfeld, R. F., A theoretical development for the computer generation and display of piecewise polynomial surfaces, IEEE Trans. Pattern Analysis and Machine Intelligence 2(1), 1980.
• 7: Melson, Thomas G., Surface/surface intersection, MCAIR Report 78-011, 1978, McDonnell Douglas Corporation, St. Louis, MO.
• 8: Sabharwal, C. L. & Factor, J. D., Cross intersection between any two C~ surfaces, Proc. Austr. International Comp Graph Conference, AUSGRAPH'88, 1988, pp. 37-42.
• 9: Sabharwal, C. L. & Melson, T. G., Intersection between non-smooth surfaces, MDC Report B 1472, 1989, McDonnell Douglas Corporation, St. Louis, MO.
• 10: Chaman L. Sabharwal , Thomas G. Melson, Implementation of cross intersection between triangular surfaces, Proceedings of the 1988 ACM sixteenth annual conference on Computer science, p.92-101, February 1988, Atlanta, Georgia, United States [doi>10.1145/322609.322621]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE

  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided manufacturing (CAM)

General Terms:
Algorithms, Design