×

A survey of curve and surface methods in CAGD. (English) Zbl 0604.65005

CAGD - short for Computer Aided Geometric Design - is concerned with the approximation and representation of curves and surfaces that arise when these objects have to be processed by a computer. Designing curves and surfaces plays an important role in the construction of quite different products such as car bodies, ship hulls, airplane fuselages and wings, propeller blades, shoe insoles, bottles, etc, etc, but also in the description of geological, physical and even medical phenomena. In this survey we mainly present methods for the generation of curves and surfaces, not for subsequent operations such as viewing, intersections, etc. Also not covered are generation methods that construct curves and surfaces from other such objects, such as fillet curves/surfaces, offset curves/surfaces etc.

MSC:

65D05 Numerical interpolation
65D07 Numerical computation using splines
41A05 Interpolation in approximation theory
41A15 Spline approximation
41A63 Multidimensional problems
53A04 Curves in Euclidean and related spaces
53A05 Surfaces in Euclidean and related spaces
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Ball, A. A., Computer-aided Design, 9, 9-12 (1977) · Zbl 0539.65005
[2] Barnhill, R. E.; Birkhoff, G.; Gordon, W. J., Smooth interpolation in triangles, J. Approx. Theory, 8, 114-128 (1973) · Zbl 0271.41002
[3] (Barnhill, R. E.; Riesenfeld, R. F., Computer Aided Geometric Design (1974), Academic Press: Academic Press New York) · Zbl 0316.68006
[4] Barnhill, R. E.; Gregory, J. A., Compatible smooth interpolation in triangles, J. Approx. Theory, 16, 214-225 (1975) · Zbl 0348.41003
[5] Barnhill, R. E., Representation and approximation of Surfaces, (Rice, J. R., Mathematical Software III (1977), Academic Press: Academic Press New York) · Zbl 0597.65001
[6] Barnhill, R. E.; Brown, J. H.; Klucewicz, I. M., A new twist in CAGD, Computer Graphics and Image Processing, 8, 78-91 (1978)
[7] Barnhill, R. E.; Farin, G. E., \(C^1\) quintic interpolation over triangles: Two explicit representations, Int. J. Num. Methods in Engineering, 17, 1763-1778 (1981) · Zbl 0477.65009
[8] Barnhill, R. E., Coon’s patches, Computers in Industry, 3, 37-43 (1982)
[9] Barnhill, R. E., (Barnhill; etal., Computer aided surface representation and design (1983)), 1-24, ’83
[10] Barnhill, R. E., A survey of the representation and design of surfaces, IEEE Computer Graphics & Appl., 3, 9-16 (1983)
[11] (Barnhill, R. E.; Böhm, W., Surfaces in CAGD (1983), North-Holland: North-Holland Amsterdam)
[12] Barsky, B. A., The beta-spline: A local representation based on shape parameters and fundamental geometric measures, Diss. Univ. Salt Lake City (1981)
[13] Barsky, B. A., End conditions and boundary conditions for uniform B-spline curve and surface representations, Computers in Industry, 3, 17-29 (1982)
[14] Barsky, B. A.; Beatty, J. C., Local control of bias and tension in beta-splines, ACM Trans. on Graphics, 2, 109-134 (1983) · Zbl 0584.65004
[15] Bézier, P., Numerical Control, Mathematics and Applications (1972), Wiley: Wiley New York · Zbl 0251.93002
[16] Bézier, P., Essai de définition numérique des courbes et des surfaces expérimentales, Diss. Paris (1977)
[17] Böhm, W., Cubic B-spline curves and surfaces in CAGD, Computing, 19, 29-34 (1977) · Zbl 0364.65004
[18] Böhm, W.; Gose, G., Einführung in die Methoden der Numerischen Mathematik (1977), Vieweg · Zbl 0365.65001
[19] Böhm, W., Inserting new knots into B-spline curves, Computer-aided Design, 12, 199-201 (1980)
[20] Böhm, W., Generating the Bézier points of B-spline curves and surfaces, Computer-aided Design, 13, 365-366 (1981)
[21] Böhm, W., On cubics, A survey, Computer Graphics and Image Processing, 19, 201-226 (1982) · Zbl 0534.65095
[22] Böhm, W., (Barnhill; etal., Generating the Bézier points of triangular splines (1983)), 77-92, ’83
[23] Böhm, W., Subdividing multivariate splines, Computer-aided Design, 15, 345-352 (1983)
[24] Böhm, W.; Farin, G. E., Letter to the Editor, Computer-aided Design, 15, 260-261 (1983)
[25] Böhm, W., Efficient evaluation of splines, Computing, 30 (1984), (in print) · Zbl 0546.65003
[26] de Boor, C., On calculating with B-splines, J. Approx. Theory, 6, 50-62 (1972) · Zbl 0239.41006
[27] de Boor, C.; Fix, G., Spline approximation by quasi-interpolants, J. Approx. Theory, 8, 19-45 (1973) · Zbl 0279.41008
[28] de Boor, C., A Practical Guide to Splines (1978), Springer: Springer Berlin · Zbl 0406.41003
[29] Breden, D., Die Verwendung von bikubischen Splineflächen zur Darstellung von Tragflügeln und Propellern, Diss. TU Braunschweig (1982)
[30] Brown, J. H., Conforming and nonconforming finite element models for curved regions, Diss. Dunde (1976)
[31] de Casteljau, F., Outillage méthodes calcul (1959), André Citroën Automobiles SA: André Citroën Automobiles SA Paris
[32] de Casteljau, F., Courbes et surfâces a pôles (1963), André Citroën Automobilies SA: André Citroën Automobilies SA Paris
[33] Catmull, E. E.; Clark, J. H., Recursively generated B-spline surfaces on arbitrary topological meshes, Computer-aided Design, 10, 350-355 (1978)
[34] Chaikin, G. M., An algorithm for high speed curve generation, Computer Graphics and Image Processing, 3, 346-349 (1974)
[35] Chang, G.; Davis, P., A new proof for the convexity of the Bernstein-Bézier surfaces over triangles, J. Approx. Theory, 11-28 (1984)
[36] Cohen, E.; Lyche, T.; Riesenfeld, R. F., Discrete B-splines and subdivision techniques in computer aided geometric design and computer graphics, Computer Graphics and Image Processing, 14, 87-111 (1980)
[37] Cohen, E., Some mathematical tools for a modeler’s workbench, IEEE Computer Graphics & Appl., 3, 63-66 (1983)
[38] Conte, S. D.; de Boor, C., Elementary Numerical Analysis (1980), McGraw-Hill: McGraw-Hill New York · Zbl 0496.65001
[39] Coons, S. A., Surfaces for computer aided design of space forms, MIT Project MAC-TR-41 (1967)
[40] Cox, M. G., The numerical evaluation of B-splines (1971), Nat. Phys. Lab. Teddington: Nat. Phys. Lab. Teddington England · Zbl 0252.65007
[41] Dahmen, W.; Micchelli, C. A., (Barnhill; etal., Multivariate splines — A new approach (1983)), 191-215, ’83
[42] Doo, D.; Sabin, M. A., Behavior of recursive division surfaces near extraordinary points, Computer-aided Design, 6, 356-360 (1978)
[43] Doo, D. W.H., A subdivision algorithm for smoothing down irregularly shaped polyhedrons, (Proceedings: Interactive Techniques in Computer Aided Design. Proceedings: Interactive Techniques in Computer Aided Design, Bologna 1978 (1978)), 157-165
[44] Farin, G. E., Konstruktion und Eigenschaften von Bézier-Kurven und Bézier-Flächen, Diplom-Arbeit TU Braunschweig (1977)
[45] Farin, G. E., Subsplines über Dreiecken, Diss. TU Braunschweig (1979)
[46] Farin, G. E., Visually \(C^2\) cubic splines, Computer-aided Design, 14, 137-139 (1982)
[47] Farin, G. E., Designing \(C^1\) surfaces consisting of triangular cubic patches, Computer-aided Design, 14, 253-256 (1982)
[48] Farin, G. E., A construction for the visual \(C^1\) continuity of polynomial surface patches, Computer Graphics and Image Processing, 20, 272-282 (1982) · Zbl 0541.65006
[49] Farin, G. E., (Barnhill; etal., Smooth interpolation to scattered 3D data (1983)), 43-64, ’83
[50] Farin, G. E., Algorithms for rational Bézier curves, Computer-aided Design, 15, 73-77 (1983)
[51] Faux, I. E.; Pratt, M. J., Computational Geometry for Design and Manufacture (1979), Ellis Horwood: Ellis Horwood Chichester · Zbl 0395.51001
[52] Ferguson, J. C., Multivariable curve interpolation, J. ACM II/2, 221-228 (1964) · Zbl 0123.33004
[53] Forrest, A. R., Interactive interpolation and approximation by Bézier polynomials, Computer J., 15, 71-79 (1972) · Zbl 0243.68015
[54] Forrest, A. R., The twisted cubic curve: A computer aided geometric design approach, Computer-aided Design, 12, 165-172 (1980)
[55] Goldman, R. N., Using degenerate Bézier triangles and tetrahedra to subdivide Bézier curves, Computer-aided Design, 14, 307-311 (1982)
[56] Goldman, R. N., Subdivision algorithms for Bézier triangles, Computer-aided Design, 15, 159-166 (1983)
[57] Gordon, W., Distributive lattices and the approximation of multivariate functions, (Schoenberg, I., Approximation with Special Emphasis on Spline Functions (1969), Academic Press: Academic Press New York), 223-277
[58] Gordon, W., Blending-function methods of bivariate and multivariate interpolation and approximation, SIAM J. Numerical Analysis, 8, 158-177 (1971) · Zbl 0237.41008
[59] Gordon, W.; Riesenfeld, R. E., (Barnhill; etal., B-spline curves and surfaces (1974)), 95-126, ’74
[60] Gordon, W., An operator calculus for surface and volume modeling, IEEE Computer Graphics & Appl., 3, 18-22 (1983)
[61] Gould, R. J., Surface programs for numerical control, (Brown, J., Curved Surfaces in Engineering (1972), IPC Science and Technology Press: IPC Science and Technology Press Guildford) · Zbl 0693.05054
[62] Greene, P. J.; Sibson, R., Computing Dirichlet tesselations in the plane, Computer J., 21, 168-173 (1977) · Zbl 0377.52001
[63] Gregory, J. A., A \(C^1\) triangular interpolation patch for computer aided geometric design, Computer Graphics and Image Processing, 13, 80-87 (1980)
[64] Gregory, J. A., (Barnhill; etal., \(C^1\) rectangular and non-rectangular surface patches (1983)), 25-34, ’83
[65] Greville, T. N.E., On the normalisation of the B-splines and the location of the nodes for the case of unequally spaced knots, (Shisha, O., Inequalities (1967), Academic Press: Academic Press New York) · Zbl 0038.28901
[66] Hartley, P. J.; Judd, C. J., Parametrization and shape of B-spline curves and surfaces for CAD, Computer-aided Design, 12, 226-236 (1980)
[67] Hayes, J. G.; Halliday, J., The least-squares fitting of cubic spline surfaces to general data sets, J. Inst. Maths. Applics., 14, 89-103 (1974) · Zbl 0284.65005
[68] Herron, G., Smooth closed surfaces with discrete triangular interpolants (1984), (submitted for publication)
[69] Hosaka, M.; Kimura, F., Synthesis methods of curves and surfaces in interactive CAD, (Proceedings: Interactive Techniques in Computer Aided Design. Proceedings: Interactive Techniques in Computer Aided Design, Bologna 1978 (1978)), 151-156
[70] Kahmann, J., Krümmungsübergänge zusammengesetzter Kurven und Flächen, Diss. TU Braunschweig (1982)
[71] Lane, J. M.; Riesenfeld, R. F., A theoretical development for the computer generation of piecewise polynomial surfaces, IEEE Trans. on Pattern Analysis and Machine Intelligence, 2, 35-46 (1980) · Zbl 0436.68063
[72] Lane, J. M.; Riesenfeld, R. F., A geometric proof for the variation diminishing property of B-spline approximation, J. Approx. Theory, 37, 1-4 (1983) · Zbl 0514.41015
[73] Lawson, C. L., Software for \(C^1\) surface interpolation, (Rice, J. R., Mathematical Software III (1977), Academic Press: Academic Press New York), 161-194 · Zbl 0407.68033
[74] Lee, E., A simplified B-spline computation routine, Computing, 29, 365-373 (1982) · Zbl 0485.65008
[75] Little, F. F., (Barnhill; etal., Convex combination surfaces (1983)), 99-108, ’83
[76] Nielson, G. M., (Barnhill; etal., Some piecewise polynomial alternatives to splines under tension (1974)), 209-235, ’74
[77] Nielson, G. M.; Franke, R., (Barnhill; etal., Surface construction based upon triangulations (1983)), ’83
[78] Powell, M. J.; Sabin, M. A., Piecewise quadratic approximations on triangles, ACM Trans. on Mathematical Software, 3, 316-325 (1977) · Zbl 0375.41010
[79] Prautzsch, H., Unterteilungsalgorithmen für Bézier- und B-Spline-Flächen, Diplom-Arbeit TU Braunschweig (1983)
[80] Prautzsch, H., Unterteilungsalgorithmen für Multivariate Splines — ein geometrischer zugang, Diss. TU Braunschweig (1984) · Zbl 0647.41015
[81] Renner, G., A method of shape description for mechanical engineering practice, Computers in Industry, 3, 137-142 (1982)
[82] Riesenfeld, R. F., Applications of B-spline approximation to geometric problems of computer-aided design, Diss. Syracuse University (1973)
[83] Riesenfeld, R. F., On Chaikin’s algorithm, Computer Graphics and Image Processing, 4, 304-310 (1975)
[84] Sabin, M. A., The use of piecewise forms for the numerical representation of shape, Diss. MTA Budapest (1977)
[85] Sabin, M. A., A review of methods for scattered data, (Brodlie, K. W., Mathematical Methods in Computer Graphics and Design (1980), Academic Press: Academic Press New York) · Zbl 0345.65006
[86] Sabin, M. A., Non-rectangular surface patches suitable for inclusion in a B-spline surface, (Ten Hagen, P. J.W., Eurographics ’83 (1983), North-Holland: North-Holland Amsterdam), 57-69
[87] Sablonniere, P., Bases de Bernstein et approximants splines, Diss. L’Université de Lille (1982)
[88] Schelske, H. J., Lokale Glättung segmentierter Bezier-Kurven und Bezier-Flächen, Diss. TH Darmstadt (1984)
[89] Schmidt, R., Eine Methode zur Konstruktion von \(C^1- Flächen\) zur Interpolation unregelmässig verteilter Daten, (Schempp; Zeller, Multivariate Approximation II (1982), Birkhäuser: Birkhäuser Basel), 343-361 · Zbl 0566.65005
[90] Schmidt, R., (Barnhill; etal., Fitting scattered surface data with large gaps (1983)), 185-190, ’83
[91] Schoenberg, I., On variation diminishing approximation methods, (Langer, R., On Numerical Approximation (1959), Univ. Wisconsin Press: Univ. Wisconsin Press Madison) · Zbl 0171.31001
[92] Schoenberg, I., On spline functions, (Shisha, O., Inequalities (1967), Academic Press: Academic Press New York) · JFM 60.0946.03
[93] Shephard, D., A two dimensional interpolation function for irregularly spaced data, (Proc. ACM Nat. Conf. (1965)), 517-524
[94] Schumaker, L. L., Spline Functions: Basic Theory (1981), Wiley: Wiley New York · Zbl 0449.41004
[95] Stärk, E., Mehrfach differenzierbare Bézier-Kurven und Bézier-Flächen, Diss. TU Braunschweig (1976)
[96] Strang, G.; Fix, G., An Analysis of the Finite Element Method (1973), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0278.65116
[97] Tiller, W., Rational B-splines for curve and surface representation, IEEE Computer Graphics Appl., 3, 61-69 (1983)
[98] Versprille, K. J., Computer-aided design applications of the rational B-spline approximation form, Diss. Syracuse University (1975), More than 2000 references on CAGD are listed in:
[99] Barksy, B. A., Computer aided geometric design, A bibliography with keywords and classified index, IEEE Computer Graphics & Appl., 1, 67-109 (1981)
[100] Schrack, G. F., Survey, computer graphics: A keyword-indexed bibliography for the year 1979, Computer Graphics and Image Processing, 15, 45-78 (1981)
[101] Schrack, G. F., Survey, computer graphics: A keyword-indexed bibliography for the year 1980, Computer Graphics and Image Processing, 18, 145-187 (1982)
[102] Rosenfeld, A., Survey picture processing 1982, Computer Vision, Graphics, and Image Processing, 22, 339-387 (1983) · Zbl 0532.68082
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.