Polyhedral subdivision methods for free-form surfaces

ABSTRACT

One of the central issues in computer-aided geometric design is the representation of free-form surfaces which are needed for many purposes in engineering and science. Several limitations are imposed on most available surface systems: the rectangularity of the network describing a surface and the manipulation of surfaces without regard to the volume enclosed are examples. Polyhedral subdivision methods suggest themselves as a solution to these problems. Their use, however, is not widespread for several reasons such as the lack of boundary control, and interpolation and interrogation capabilities. In this paper the original work on subdivision methods is extended to overcome these problems. Two methods are described, one for controlling the boundary curves of such surfaces, and another for interpolating points on irregular networks. A general surface/surface intersection algorithm is also provided: seven decisions need to be made in order to specify a particular implementation. The algorithm is also suitable for intersecting other classes of surfaces amongst which are the popular Bézier and B-spline surfaces.

REFERENCES

• 1: BALL, A. A., AND STORRY, D. J.T. Recursively generated B-spline surfaces. In Proceedings of CAD 84 (Brighton, England, Apr.), Butterworths, London, 1984, pp. 112-119.
• 2: CATMULL, E., AND CLARK, J. Recursively generated B-spline surfaces on arbitrary topological meshes. CAD J. I0, 6 (Nov. 1978), 350-355.
• 3: CHAIKIN, G.M. An algorithm for high speed curve generation. Comput. Graph. Image Process. 3 (Dec. 1974), 346-349.
• 4: Doo, D. W. H. A recursive subdivision algorithm for fitting quadratic surfaces to irregular polyhedrons. Ph.D. dissertation, Dept. of Computer Science, Brunel Univ., Oxbridge, England, 1978.
• 5: Doo, D. W. H., AND SABIN, M.A. Behaviour of recursive subdivision surfaces near extraordinary points. CAD J. 10, 6 (Nov. 1978), 356-360.
• 6: A. R. Forrest, A unified approach to geometric modelling, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.264-269, August 1978
• 7: NASRI, A.H. Polyhedron subdivision methods for free-form surfaces. Ph.D. dissertation, Cornput. Geom. Proj. Memo CGP84/6, School of Computing Studies and Accountancy, Univ. of East Anglia, Norwich, England, 1984.
• 8: SABIN, M. A. Recursive division. In Mathematics of Sur{aces, J. A. Gregory, Ed. Oxford University Press, 1986.
• 9: WIELINGA, R.F. Constrained interpolation using B~zier curves as a new tool in computer-aided design. In Computer-Aided Geometric Design, R. E. Barnhill and R. F. Riesenfeld, Eds. Academic Press, Orlando, Fla., 1974, pp. 153-172.
• 10: YAMAGUCHI, F. A new curve fitting method using a CRT computer display. Comput. Graph. Image Process. 7 (1978), 425-437.

INDEX TERMS

Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

General Terms:
Algorithms, Design