Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

Implicitizing Rational Parametric Surfaces

Dinesh Manocha and John F. Canny

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-90-592
September 1990

http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/CSD-90-592.pdf

Many current geometric modeling systems use the rational parametric form to represent surfaces. Although the parametric representation is useful for tracing, rendering and surface fitting, many operations like surface intersection desire one of the surfaces to be represented implicitly. Moreover, the implicit representation can be used for testing whether a point lies on the surface boundary and to represent an object as a semi-algebraic set. In the past, resultants and Grobner basis have been used to implicitize parametric surfaces. In particular, different formulations of resultants have been used to implimentize tensor product surfaces and triangular patches and in many cases the resulting expression consists of an extraneous factor. The separation of these extraneous factors can be a time consuming task involving multivariate factorization. Furthermore, these algorithms fail altogether if the given parametrization has base points. The parametrizations of many commonly used rational surfaces, like the quadrics and some cubics, have base points.

In this paper we present an algorithm to implicitize parametric surfaces. If a parametrization has no base points, we formulate the parametric equations in such a manner that their resultant corresponds exactly to the implicit equation without generating any extraneous factor. We also analyze the problem of implicitization in the presence of base points. In particular, we perturb the given parametrizations and use resultants or Grobner basis of the perturbed system to compute the implicit representation. Our algorithm perturbs only one of the three equations and shows that the implicit equation is contained in the lowest degree term of the resultant of the perturbed equations (expressed in terms of the perturbing variable). The strength of the algorithm lies in the fact that it makes use of the GCD operation as opposed to multivariate factorization to extract the implicit equation out of the lowest degree term. The base points blow up to rational curves and the extraneous factors in the lowest degree term of the resultant of perturbed equations is used to compute the rational parametrizations of these curves. We also describe an efficient implementation of the algorithm.


BibTeX citation:

@techreport{Manocha:CSD-90-592,
    Author = {Manocha, Dinesh and Canny, John F.},
    Title = {Implicitizing Rational Parametric Surfaces},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1990},
    Month = {Sep},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/6369.html},
    Number = {UCB/CSD-90-592},
    Abstract = {Many current geometric modeling systems use the rational parametric form to represent surfaces. Although the parametric representation is useful for tracing, rendering and surface fitting, many operations like surface intersection desire one of the surfaces to be represented implicitly. Moreover, the implicit representation can be used for testing whether a point lies on the surface boundary and to represent an object as a semi-algebraic set. In the past, resultants and Grobner basis have been used to implicitize parametric surfaces. In particular, different formulations of resultants have been used to implimentize tensor product surfaces and triangular patches and in many cases the resulting expression consists of an extraneous factor. The separation of these extraneous factors can be a time consuming task involving multivariate factorization. Furthermore, these algorithms fail altogether if the given parametrization has base points. The parametrizations of many commonly used rational surfaces, like the quadrics and some cubics, have base points. <p>In this paper we present an algorithm to implicitize parametric surfaces. If a parametrization has no base points, we formulate the parametric equations in such a manner that their resultant corresponds exactly to the implicit equation without generating any extraneous factor. We also analyze the problem of implicitization in the presence of base points. In particular, we perturb the given parametrizations and use resultants or Grobner basis of the perturbed system to compute the implicit representation. Our algorithm perturbs only one of the three equations and shows that the implicit equation is contained in the lowest degree term of the resultant of the perturbed equations (expressed in terms of the perturbing variable). The strength of the algorithm lies in the fact that it makes use of the GCD operation as opposed to multivariate factorization to extract the implicit equation out of the lowest degree term. The base points blow up to rational curves and the extraneous factors in the lowest degree term of the resultant of perturbed equations is used to compute the rational parametrizations of these curves. We also describe an efficient implementation of the algorithm.}
}

EndNote citation:

%0 Report
%A Manocha, Dinesh
%A Canny, John F.
%T Implicitizing Rational Parametric Surfaces
%I EECS Department, University of California, Berkeley
%D 1990
%@ UCB/CSD-90-592
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1990/6369.html
%F Manocha:CSD-90-592