On local implicit approximation and its applications

ABSTRACT

A method is proposed for computing an implicit approximant at a point to a parametric curve or surface. The method works for both polynomially and rationally parameterized curves and surfaces and achieves an order of contact that can be prescribed. In the case of nonsingular curve points, the approximant must be irreducible, but in the surface case additional safeguards are incorporated into the algorithm to ensure irreducibility. The method also yields meaningful results at most singularities. In principle, the method is capable of exact implicitization and has a theoretical relationship with certain resultant-based elimination methods.

REFERENCES

• 1: BAJAJ, C. L. Local parameterization, implicitization and inversion of real algebraic curves. Tech. Pep. 89-863, Dept. of Computer Science, Purdue University, West Lafayette, Ind., 1989.
• 2: C. Bajaj , I. Ihm, Hermite interpolation of rational space curves using real algebraic surfaces, Proceedings of the fifth annual symposium on Computational geometry, p.94-103, June 05-07, 1989, Saarbruchen, West Germany [doi>10.1145/73833.73844]
• 3: BAJAJ, C. L., GARRIT'~, T., AtCV WARREN, J. On the applications of multi-equational resultants. Tech. Rep. 88-826, Dept. of Computer Science, Purdue University, West Lafayette, ind., 1988,
• 4: C. L. Bajaj , C. M. Hoffman , R. E. Lynch , J. E. H. Hopcroft, Tracing surface intersections, Computer Aided Geometric Design, v.5 n.4, p.285-307, Nov. 1988 [doi>10.1016/0167-8396(88)90010-6]
• 5: BUCHBERGER, B. Gr6bner bases: An algorithmic method in polynomial ideal theory. In Recent Results in Multidimensional Systems Theory, N. K. Bose, Ed. Reidel, Amsterdam, 1985.
• 6: John F. Canny, Generalized Characteristic Polynomials, Proceedings of the International Symposium ISSAC'88 on Symbolic and Algebraic Computation, p.293-299, July 04-08, 1988
• 7: R T Farouki, The characterization of parametric surface sections, Computer Vision, Graphics, and Image Processing, v.33 n.2, p.209-236, Feb. 1986 [doi>10.1016/0734-189X(86)90115-5]
• 8: GARRITY, T., AND WARREN, J. On computing the intersection of a pair of algebraic surfaces. To be published.
• 9: Christopher M. Hoffmann, Algebraic curves, Mathematical aspects of scientific software, Springer-Verlag New York, Inc., New York, NY, 1988
• 10: HOFFMANN, C.M. A dimensionality paradigm for surface interrogations, Tech. Rep. TR-88- 837, Dept. of Computer Science, Purdue University, West Lafayette, Ind., 1988. To appear in Comput-Aided Geom. Des.
• 11: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 12: HOUGHTON, E. G., EMNETT, R. F., FACTOR, J?D., AND SABHARWAL, C.L. Implementation of a divide-and-conquer method for intersection of parametric surfaces. Comput.-Aided Geom. Des. 2 (1985), pp. 173-183.
• 13: KAHAN, W. A survey of error analysis. In Proceedings of the International Federation for Information Processing Congress, 2 (Ljubljana, Yugoslavia, August 1971), North-Holland, pp. 1214-1239.
• 14: P A Koparkar , S P Mudur, Generation of continuous smooth curves resulting from operations on parametric surface patches, Computer-Aided Design, v.18 n.4, p.193-206, May 1986 [doi>10.1016/0010-4485(86)90131-4]
• 15: LANE, J. M., AND RIESENFELD, R. f. A theoretical development for the computer generation and display of piecewise polynomial surfaces. IEEE Trans. Pattern Anal. Mach. Intel. PAMI-2, 1, (1980).
• 16: Dieter Lasser, Intersection of parametric surfaces in the Bernstein—Be´zier representation, Computer-Aided Design, v.18 n.4, p.186-192, May 1986 [doi>10.1016/0010-4485(86)90130-2]
• 17: LEVIN, J.Z. Mathematical models for determining the intersection of quadric surfaces. Comput. Gr. Image Process. 11, 73-87, (1979).
• 18: MACAULAY, F.S. Some formulae in elimination. Proc. London Math. Soc. 35, (1902), 3-27.
• 19: MACAULAY, F. S. The Algebraic Theory of Modular Systems, Cambridge University Press, New York, 1916.
• 20: Y de Montaudouin , W Tiller , H Vold, Applications of power series in computational geometry, Computer-Aided Design, v.18 n.10, p.514-524, Dec. 1986 [doi>10.1016/0010-4485(86)90038-2]
• 21: NETTO, E. Algebra, Vol. 1, p. 169 and Vol. 2, p. 79, Midland Press, Ann Arbor, Michigan, 1896.
• 22: PENG, Q. S. An algorithm fi)r finding the intersection lines between two b-spline surfaces. Comput.-Aided Des. 16, 4 (1984).
• 23: PRAKASH, P. V., AND PATRIKALAKIS, N.M. Algebraic and rational polynomial surface intersections. To be published.
• 24: REQUICHA, A. A. G., AND VOELCKER, S. B. Solid modeling: Current status and research directions. IEEE Comput. Gr. Appl. (Oct. 1983).
• 25: SARRAGA, R.F. Algebraic methods for intersections of quadric surfaces in GMSOLID. Comput. Vision, Gr. Image Process. 22 (t983).
• 26: Thomas Warren Sederberg, Implicit and parametric curves and surfaces for computer aided geometric design, 1983
• 27: T W Sederberg, Improperly parametrized rational curves, Computer Aided Geometric Design, v.3 n.1, p.67-75, May 1986 [doi>10.1016/0167-8396(86)90025-7]
• 28: WAGGENSPACK, JR., W. J. Parametric curve approximations for surface intersection, Ph.D. dissertation Purdue University, Dept. of Mechanical Engineering, West Lafayette, ind., 1987.
• 29: Warren N. Waggenspack, Jr. , David C. Anderson, Piecewise parametric approximations for algebraic curves, Computer Aided Geometric Design, v.6 n.1, p.33-53, February 1989 [doi>10.1016/0167-8396(89)90005-8]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.2 Approximation
          Subjects: Linear approximation; Spline and piecewise polynomial approximation
      G.1.3 Numerical Linear Algebra
          Subjects: Linear systems (direct and iterative methods)

General Terms:
Algorithms, Design, Theory