An adaptive subdivision method for surface-fitting from sampled data

ABSTRACT

A method is developed for surface-fitting from sampled data. Surface-fitting is the process of constructing a compact representation to model the surface of an object based on a fairly large number of given data points. In our case, the data is obtained from a real object using an automatic three-dimensional digitizing system. The method is based on an adaptive subdivision approach, a technique previously used for the design and display of free-form curved surface objects. Our approach begins with a rough approximating surface and progressively refines it in successive steps in regions where the data is poorly approximated. The method has been implemented using a parametric piecewise bicubic Bernstein-Bézier surface possessing G¹ geometric continuity. An advantage of this approach is that the refinement is essentially local reducing the computational requirements which permits the processing of large databases. Furthermore, the method is simple in concept, yet realizes efficient data compression. Some experimental results are given which show that the representation constructed by this method is faithful to the original database.

REFERENCES

• Barsky81: Brian Andrew Barsky, The beta-spline: a local representation based on shape parameters and fundamental geometric measures, 1981
• Barsky84: Brian A. Barsky: "A Description and Evaluation of Various 3-D Model,"IEEE Computer Gra{hics and Applications, Vol. 4, NO. 1, January, 1984, pp.
• Barsky85: Brian A. Barsky, Arbitrary Subdivision of Bezier Curves, University of California at Berkeley, Berkeley, CA, 1985
• Barsky86: Brian A. Barsky, Computer graphics and geometric modeling using Beta-splines, Springer-Verlag New York, Inc., New York, NY, 1988
• Barsky83: Brian A. Barsky , John C. Beatty, Local Control of Bias and Tension in Beta-splines, ACM Transactions on Graphics (TOG), v.2 n.2, p.109-134, April 1983 [doi>10.1145/357318.357321]
• Barsky84a: Brian A. Barsky , Anthony D. DeRose, Geometric Continuity of Parametric Curves, University of California at Berkeley, Berkeley, CA, 1984
• Barsky85a: Brian A. Barsky and Tony D. DeRose: "The Beta2-spllne: A Special Case of the Beta-spline Curve and Surface Representation," IEEE Computer Graphics and Application, Vpl. 5., No. 9, September, 1985, pp. 46-58.
• Barsky86a: Brian A. Barsky, Tony D. DeRose and Mark D. Dippe: "An Adaptive Subdivision Method with Crack Prevention for Rendering Beta-spltne Objects," submitted for publication.
• Bartels87: Richard H. Bartels , John C. Beatty , Brian A. Barsky, An introduction to the use of splines in computer graphics, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1986
• Beeker86: Etienne Beeker, Smoothing of shapes designed with free-form surfaces, Computer-Aided Design, v.18 n.4, p.224-232, May 1986 [doi>10.1016/0010-4485(86)90134-X]
• Bézier70: Pierre E. Bezier: "Emploi des machines a commande num4rique," Masson et Cie., Paris, 1970. Translated by A. Robin Forrest and Anne P. Pankhurst as Numerical Control -- Mathematical and Applications, John Wiley and Sons Ltd., London, 1972.
• Bézier74: Pierre E. Bezler: "Mathematical and Practical Possibilities of UNISURF," in Computer-Aided Geometric Design, edited by Robert E. Barnhill and Richard,F. Riesenfeld, Academic Press, New York, 1974, pp. 127-152.
• Bézier77: Pierre E. Bdzier: Essai de ddfinitlon numerique des courdes et des surface experimental, Ph.D. Thesis, I'Univesite Pierre et Marie Curie, Paris, 1977.
• Boehm80: Wolfgang Boehm: "Inserting New Knots into B- spline Curves," Computer-Aided Design, Vol. 12, No. 4, 1980, pp. 199-202.
• Boehm84: Uolfgang Boehm: "On the Efficiency of Knot inset tion Algor i thins," Computer-Aided Geometric Vol. 1, 1984.
• Boehm84a: Wolfgang Böhm , Gerald Farin , Jürgen Kahmann, A survey of curve and surface methods in CAGD, Computer Aided Geometric Design, v.1 n.1, p.1-60, July 1984 [doi>10.1016/0167-8396(84)90003-7]
• Boehm85: Wolfgang Boehm and Hartmut Prautzsch: "The Insertion Algorithm," Computer-Aided Design Vol. 17, No. 2, March, 1985, pp. 58-59.
• Catmull75: Edwin E. Catmull: "Computer Display of Curved Surfaces," Proceedings of IEEE Conference on Computer Graphics, Pattern Recognition, and Data Structure,Los Angeles, May, 1975, pp. 11-17.
• Catmull78: Edwin E. Catmull and James H. Clark: "Recursively Generated B-spllne Surfaces on Arbitrary Topological Meshes," Computer-Aided Design, Vol. 10, No. 6, November, 1978, pp. 350-355.
• Chaikin74: George M. Chaiktn: "An Algorithm for High- Speed Curve Generation,"Computer Graphics and Image Processing, Vol. 3, No. 4, December, 1974, pp. 346- 349.
• Chung80: Won L. Chung, Automatic Curve Fitting Using an Adaptive Local Algorithm, ACM Transactions on Mathematical Software (TOMS), v.6 n.1, p.45-57, March 1980 [doi>10.1145/355873.355877]
• Clark79: James H. Clark, A fast scan-line algorithm for rendering parametric surfaces, Proceedings of the 6th annual conference on Computer graphics and interactive techniques, p.174, August 08-10, 1979, Chicago, Illinois, United States
• Cohen80: Elaine Cohen, Tom Lyche and Richard F. Riesenfeld: "Discrete B-spllnes and Subdivision Techniques in Computer-Aided Geometric Design and Computer Graphics,"Computer Graphics and Image Processing, Vol. 14, No. 2, October, 1980, pp. 87-111.
• Coons67: S. A. Coons, SURFACES FOR COMPUTER-AIDED DESIGN OF SPACE FORMS, Massachusetts Institute of Technology, Cambridge, MA, 1967
• Cox71: Morris G. Cox: "Curve Fitting with Piecewise Polynomials," J. Inst. Maths. Applications, Vol. 8, 1971, pp. 36-51.
• de Casteljau59: Paul de Casteljau: "Courbes et surfaces a poles," S. A. Andre Citroen, Paris, 1959.
• DeRose85: T D DeRose , B A Barsky, An intuitive approach to geometric continuity for parametric curves and surfaces, Proceedings of Graphics Interface '85 on Computer-generated images: the state of the art, p.159-175, January 1986, Montreal, Quebec, Canada
• Dierckx75: P. Dierckx: "An Algorithm for Smoothing, Differentiation and Integration of Experimental Data Using Spline Functions," J. Comput.Appl. Math., Vol. 1, 1975, pp. 165-184.
• Dierckx82: P. Dierckx: "Algorithms for Smoothing Data with Periodic and Parametric Splines," Computer Graphics and Image Processing Vol. 20, No. 2, 0ctober, 1982, pp. 171-184.
• Doo78: D. W. H. Doo: "A Subdivision Algorithm for Smoothing down Irregularly Shaped Polyhedrons," in the ProceedinKs of Interactire Techniques in Computer-Aided Design, Bologna, Italia, 1978, pp. 157-165.
• Doo78a: D. W. H. Doo and M. A. Sabin: "Behaviour of Recursive Division Surfaces Near Extraordinary Points," Computer-Aided Design, Vol. 10, No. 6, November, 1978, pp. 35~6-360.
• Farin82: Gerald Farin: "A Construction for Visual CI Continuity of Polynomial Surface Patches," computer Graphics and Image Processing, Vol. 20, 1982, pp. 272-282.
• Faux79: I. D. Faux , M. J. Pratt, Computational Geometry for Design and Manufacture, Halsted Press, New York, NY, 1979
• Fournier85: A Fournier , B A Barsky, Geometric continuity with interpolating Be´zier curves, Proceedings of Graphics Interface '85 on Computer-generated images: the state of the art, p.153-158, January 1986, Montreal, Quebec, Canada
• Gholizadeh85: Behrouz Gholizadeh: Reprdsentation par triangulation de la surface d'objets tridimensionnels.These de 3e Cycle. Universite de Paris-Sud, Centre d'Orsay, December, 1985.
• Goldman82: Ronald N. Goldman: "Using Degenerate Bezier Triangles and Tetrahedra to Subdivide B4zier Curves, " Computer-Aided Design, Vol. 14, No. 6, November, 1982, pp. 307-311.
• Ichida77: Kozo Ichida , Takeshi Kiyono , Fujiichi Yoshimoto, Curve Fitting by a One-Pass Method With a Piecewise Cubic Polynomial, ACM Transactions on Mathematical Software (TOMS), v.3 n.2, p.164-174, June 1977 [doi>10.1145/355732.355737]
• IEEE86: IEEE Computer Graphics and Applications, Special Issue on" Parametrlc Curves and Surfaces, Vol. 6, No. 2, February, 1986.
• Kahmann83: Juergen Kahmann: "Continuity of Curvature between Adjacent Bezier Patches," Surfaces in CAGD, edited by Robert E. Barnhill and Wolfgang Boehm, 1983, North-Holland Publishing Company, Amsterdam, pp. 65- 75.
• Knapp79: Lewis Charles Knapp, A design scheme using coons surfaces with nonuniform basis b-spline curves, 1979
• Koparkar83: P.A. Koparkar and S. P. Mudur: "A New Class of Algorithms for the Processing of Parametric Curves," Computer-Aided Design, Vol. 15, No. 1, January, 1983, pp. 41-45.
• Lane79: Jeffrey M. Lane and Loren C. Carpenter: "A Generalized Scan Line Algorithm for the Computer Display of Parametrically Defined Surfaces," Come Gra~ ics and Image Processing, Vol. ii, No. 3, November, 1979, pp. 290-- 297.
• Lane80: Jeffrey M. Lane , Loren C. Carpenter , Turner Whitted , James F. Blinn, Scan line methods for displaying parametrically defined surfaces, Communications of the ACM, v.23 n.1, p.23-34, Jan. 1980 [doi>10.1145/358808.358815]
• Lane80a: Jeffrey M. Lane and Richard F. Riesenfeld: "A Theoretical Development for the Computer Generation of Piecewise Polynomial Surfaces," IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. PAMI-2 No. 1, January, 1980, pp. 35-46.
• Lane81: Jeffrey M. Lane and Richard F. Riesenfeld: "Bounds on a Polynomial," BIT, Vol. 21, No. 1, 1981, pp. 112-117.
• Maitre81: Henri Maitre, Jaime Lopez-Krahe, Alain Clainchard, and Francis Schmitt: "Appareil automatique pour la numerisation d'une surface tridimensionnelle," BREVET No. 81-24418, 1981.
• Nydegger72: Robert W. Nydegger: A Data Minimization Algorithm of Analytical Models for computer Gaphics, Master's thesis, University of Utah, Salt Lake City, Utah, 1972.
• Piegl85: L. Piegl: "Recursive AIgorithms for the Representation of Parametric Curves and Surfaces," Computer-Aided ~Vol. 17, No. 5, June, 1985, pp. 225 -229.
• Plass83: Michael Plass , Maureen Stone, Curve-fitting with piecewise parametric cubics, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.229-239, July 25-29, 1983, Detroit, Michigan, United States
• Prautzsch84: Hartmut Prautzsch: "A Short Proof of the Oslo Algorithm," Computer-Aided Geometric Design, Vol. 1, No. 1, July, 1982, pp. 95'96.
• Ramer72: Urs Ramer: "An Iterative Procedure for the Polygonal Approximation of Plane Curves," and Image Processing, Vol. 1, No. 3, November, 1972, pp. 244-256.
• Reeves81: William Thomas Reeves, Quantitative representations of complex dynamic shape for motion analysis, 1980
• Rice76: John R. Rice: "Adaptive Approximation," Journal of Approximation Theory, Vol. 16, 1976, pp. 329-337.
• Rice78: John R. Rice, Algorithm 525: ADAPT, Adaptive Smooth Curve Fitting [E2], ACM Transactions on Mathematical Software (TOMS), v.4 n.1, p.82-94, March 1978 [doi>10.1145/355769.355777]
• Riesenfeld75: Richard F. Riesenfeld: "On Chaikin' s Algorithin, "Computer Graphics and Images Processing, Vol. 4, No. 3, September, 1975, pp. 304-310.
• Riesenfeld81: Richard F. Riesenfeld, Elaine Cohen, Russell D. Fish, Spencer W. Thomas, Elizabeth S. Cobb, Brian A. Barsky, Dino L. Schweltzer, and Jeffrey M. Lane: "Using the Oslo Algorithm as a Basis for CAD/CAM Geometric Modelling, " pp. 345-356 in the Proceedings of the Second Annual NCGA National Conference, National Computer Association, Inc., Baltimore, Maryland, 14-18 June, 1981.
• Schmitt85: Francis Schmitt and Behrouz Gholizadeh: "Adaptive Polyhedral Approximation of Digitized Surfaces, " SFIE Proceedings Vol. 595 of Conference on Computer vision for Robots, Cannes, France, 2-6 December, 1985.
• Schmitt85a: Francis Schmitt, Henri Maitre, Alain Clainchard and Jalme Lope z-Krahm: "Acquisition and Representation of Real Object Surface Data," SPIE Proceedings Vol. 602 of Biostereometrlcs'85 Conference. Cannes, France, 2-6 December, 1985.
• Wang84: Guo-Zhao Wang: "The Subdivision Method for Finding the Intersection between Two Bdzier Curves or Surfaces," Zhejiang University Journal, Special Issue on Computational Geometry (in Chinese), 1984.

INDEX TERMS

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

General Terms:
Algorithms