Regular curves and proper parametrizations

ABSTRACT

We present an algorithm for determining whether a given rational parametric curve, defined as vector valued function over a finite domain, has a regular parametrization. A curve has a regular parametrization if it has no cusps in its defining interval. It has been known that the vanishing of the derivative vector is a necessary condition for the existence of cusps. We show that if a curve is properly parametrized, then the vanishing of the derivative vector is a necessary and sufficient condition for the existence of cusps. If a curve has no cusps in its defining interval, its proper parametrization is a regular parametrization. We present a simple algorithm to compute the proper parametrization of a polynomial parametric curve which is used to analyze for cusps and later on reduce the problem of detecting cusps in a rational curve to that of a polynomial curve.

REFERENCES

• Bo: Wolfgang Boehm, Curvature continuous curves and surfaces, Computer Aided Geometric Design, v.2 n.4, p.313-323, Dec. 1985 [doi>10.1016/S0167-8396(85)80006-6]
• Co: Collins. G.E. (1977) "Infallible Calculation of Polynomial Zeros to Specified Precision", in Mathematical Software III, edited by John R. Rice, pp. 35-68, .Academic Press, New York.
• De: Anthony David Derose, Geometric continuity: a parametrization independent measure of continuity for computer aided geometric design (curves, surfaces, splines), 1985
• DM: Dyn, Nira and Micchelli, Charles A. (September 1985) Piecewise Polynomial Spaces and Geometric Continuity of Curves, IBM Thomas J. Watson Research Center, Yorktown Heights, New York.
• DS: Maureen C. Stone , Tony D. DeRose, A geometric characterization of parametric cubic curves, ACM Transactions on Graphics (TOG), v.8 n.3, p.147-163, July 1989 [doi>10.1145/77055.77056]
• Ho: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• MC1: Dinesh Manocha , John F. Canny, Detecting Cusps and Inflection Points in Curves, University of California at Berkeley, Berkeley, CA, 1989
• MC2: Manocha, Oinesh and Canny, John F. (1990b) "Polynomial Parametrizations for Rational Curves," to appear in SPIE conference on Curves and Surfaces in Computer Graphics and Vision.
• Po: Pogorolev, A.V. (1957) Differential Geometry, P. Noordhoff, N.V.,Groningen, Netherlands.
• Se: 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]
• SK: Semple, J.G. and Kneebone G.T. (1959) Algebraic Curves, Oxford University Press, London.
• St: Stoker, James J. (1969) Differential Geometry, John Wiley & Sons Inc.
• Wa: Wang, C.~. ( July 1981) "Shape classification of the parametric cubic curve and parametric B-spline curve," Computer Aided Design, vol. 13, no. 4, pp. 199-206.
• Wl: Walker, Robert J. (1950) Algebraic Curves, Princeton University Press, New Jersey.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on polynomials

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems

General Terms:
Algorithms