Chandrajit Bajaj
Insung Ihm
Abstract
In this article, we characterize the solution space of low-degree, implicitly defined, algebraic surfaces which interpolate and/or least-squares approximate a collection of scattered point and curve data in three-dimensional space. The problem of higher-order interpolation and least-squares approximation with algebraic surfaces under a proper normalization reduces to a quadratic minimization problem with elegant and easily expressible solutions. We have implemented our algebraic surface-fitting algorithms, and included them in the distributed and collaborative geometric environment SHASTRA. Several examples are given to illustrate how our algorithms are applied to algebraic surface design.
- ALRANO A. 1974. Representation of digitized contours in terms of conic arcs and straight line segments. Comput. Graph. Image Process. 3, 23-33.Google Scholar
- ANUPAM, V., ANO BAJAJ, C. 1993. Collaborative multimedia scientific design in SHASTRA. In Proceedings of the 1993 ACM Multimedia Conference. ACM Press, New York, 447-456. Google Scholar
- BAJAJ, C. 1993. The emergence of algebraic curves and surfaces in geometric design. In Directions in Geometric Computing. Information Geometers Press, United Kingdom, 1-27.Google Scholar
- BAJAJ, C. 1992. Surface fitting with implicit algebraic surface patches. In Topics in Surface Modeling. SIAM Publications, Philadelphia, Pa., 23-52. Google Scholar
- BAJAJ, C. 1988. Geometric modeling with algebraic surfaces. In The Mathematics of Surfaces II1. Oxford University Press, New York, 3-48. Google Scholar
- BAJAJ, C., AND IHM, I. 1992a. Algebraic surface design with Hermite interpolation. ACM Trans. Graph. 11, 1 (Jan.), 61-91. Google Scholar
- BAJAJ, C., AND II~M, I. 1992b. Smoothing polyhedra using implicit algebraic splines. Comput. Graph. 26, 2 (July) 79-88. Google Scholar
- BAJAJ, C., ANO XU, G. 1992. A Splines: Local interpolation and approximation using Ckcontinuous piecewise real algebraic curves. Computer Science Tech. Rep. CAPO-92-95, Purdue Univ., West Lafayette, Ind.Google Scholar
- B^aAa, C., HOffMANN, C., HOPCROrT, J., ^NO LWCH, R. 1988. Tracing surface intersections. Comput. Aided Geom. Des. 5,285-307. Google Scholar
- BLOOMENTHAI., J. 1988. Polygonization of implicit surfaces. Comput. Aided Geom. Des. 5, 341 355. Google Scholar
- BOOKST~nN, F. 1979. Fitting conic sections to scattered data. Comput. Graph. Image Process. 9, 56-71.Google Scholar
- DERoSE, A. 1985. Geometric continuity: A parametrization independent measure of continuity for computer aided geometric design. PhD thesis, Computer Science, Univ. of California, Berkeley. Google Scholar
- FAROUKI, R. 1988. The approximation of nondegenerate offset surfaces. Comput. Aided Geom. Des. 3, 15-43. Google Scholar
- GARalTY, T., ^~D WARREN, J. 1991. Geometric continuity. Comput. Aided Geom. Des. 8, 51-65. Google Scholar
- GNANAD~;SIKAN, R. 1977. Methods for Statistical Data Analysis of Multivariate Observations. John Wiley & Sons, New York.Google Scholar
- GOLUB, G. 1973. Some modified matrix eigenvalue problems. SIAM Rev. 15, 2,318-334.Google Scholar
- GOLUB, G., ANI) USDERWOOI), R. 1970. Stationary values of the ratio of quadratic forms subject to linear constraints. Z. Agnew. Math. Phys. 21,318-326.Google Scholar
- Gokthq, G., AND VAN LOAN, C. 1983. Matrix Computation. The Johns Hopkins University Press, Baltimore, Md.Google Scholar
- HOFFMANN, C., AND HOPCROFT, J. 1987. The potential method for blending surfaces and corners. In Geometric Modeling: Algorithms and New Trends. SIAM, Philadelphia, Pa., 347 -366.Google Scholar
- IHM, I. 1991. On surface design with implicit algebraic surfaces. PhD thesis, Purdue Univ., West Lafayette, Ind. Google Scholar
- KUNZ, E. 1985. Introduction to Commutative Algebra and Algebraic Geometry. Birkhauser, New York.Google Scholar
- MACAUI,~Y, F. 1916. The Algebraic Theory of Modular Systems. Cambridge University Press, London, U.K.Google Scholar
- MoortE, D., AND WARREN, J. 1991. Approximation of dense scattered data using algebraic surfaces. In Proceedings of the 24th Hawaii International Conference on System Sciences (Kauai, Hawaii). IEEE Computer Society Press, Washington, D.C., 681-690.Google Scholar
- OWEN, J., ^ND ROCKWOOl), A. 1987. Blending surfaces in solid modeling. In Geometric Modeling: Algorithms and New Trends. SIAM, Philadelphia, Pa., 367-383.Google Scholar
- PRATT, V. 1987. Direct least squares fitting of algebraic surfaces. Comput. Graph. 21, 3, 145-152. Google Scholar
- SAM}mow, P. 1982. Fitting conic sections to very scattered data: An iterative refinement of the bookstein algorithm. Comput. Graph. Image Process. 18, 97-108.Google Scholar
- SEDEIaBER(;, T. 1990a. Techniques for cubic algebraic surfaces. IEEE Comput. Graph. Appl. 10, 4 (July), 14-25. Google Scholar
- SEDERSr~m;, T. 1990b. Techniques for cubic algebraic surfaces. IEEE Comput. Graph. Appl. 10, 5 (Sept.), 12 21. Google Scholar
- SEI)EI~BI~;RG, T. 1985. Piecewise algebraic surface patches. Comput. Aided Geom. Des. 2, 1-3, 53-59.Google Scholar
- STRANC, G. Linear Algebra and Its Applications. 3rd ed. Harcourt Brace Jovanovich, San Diego, Calif.Google Scholar
- WAm~EN, J. 1989. Blending algebraic surfaces. ACM Trans. Graph. 8, 4, 263 278. Google Scholar
- WARREN, J. 1986. On algebraic surfaces meeting with geometric continuity. PhD thesis, Cornell Univ., Ithaca, N.Y. Google Scholar
- WOODW^RK, J. 1987. Blends in geometric modelling. In The Mathematics of Surfaces, Volume 2. Oxford University Press, New York, 255-297. Google Scholar
Index Terms
- Higher-order interpolation and least-squares approximation using implicit algebraic surfaces
Recommendations
Direct least-squares fitting of algebraic surfaces
In the course of developing a system for fitting smooth curves to camera input we have developed several direct (i.e. noniterative) methods for fitting a shape (line, circle, conic, cubic, plane, sphere, quadric, etc.) to a set of points, namely exact ...
Algebraic surface design with Hermite interpolation
This paper presents an efficient algorithm called Hermite interpolation, for constructing low-degree algebraic surfaces, which contain, with C1 or tangent plane continuity, any given collection of points and algebraic space curves having derivative ...
Smooth spline surfaces over irregular meshes
SIGGRAPH '94: Proceedings of the 21st annual conference on Computer graphics and interactive techniquesAn algorithm for creating smooth spline surfaces over irregular meshes is presented. The algorithm is a generalization of quadratic B-splines; that is, if a mesh is (locally) regular, the resulting surface is equivalent to a B-spline. Otherwise, the ...
Comments