“Implicitization using moving curves and surfaces” by Sederberg and Chen

This paper presents a radically new approach to the century old problem of computing the implicit equation of a parametric surface. For surfaces without base points, the new method expresses the implicit equation in a determinant which is one fourth the size of the conventional expression based on Dixon’s resultant. If base points do exist, previous implicitization methods either fail or become much more complicated, while the new method actually simplifies. The new method is illustrated using the bicubic patches from Newell’s teapot model. Dixon’s method can successfully implicitize only 8 of those 32 patches, expressing the implicit equation as an 18 x 18 determinant. The new method successfully implicitizes all 32 of the patches. Four of the implicit equations can be written as 3 x 3 determinants, eight can be written as 4 x 4 determinants, and the remaining 20 implicit equations can be written using 9 x 9 determinants.

1. Buchberger, Bruno. Applications of Gr6bner Bases in Nonlinear Computational Geometry. In D. Kapur and J. L. Mundy, editors, Geometric Reasoning, pages 413-446. Elsevier Science Publisher, MIT Press, 1989.
2. Chionh, Eng Wee. Base Points, Resultants, and the Implicit Representation of Rational Surfaces. PhD thesis, University of Waterloo, 1990.
3. Chionh, Eng Wee and Ronald N. Goldman. Degree, Multiplicity, and Inversion Formulas for Rational Surfaces using U-resultants. Computer Aided Geometric Design, 9:93-108, 1992.
4. Chionh, Eng Wee and Ronald N. Goldman. Using Multivariate Resultants to Find the Implicit Equation of a Rational Surface. The Visual Computer, 8(3):171-180, 1992.
5. Coolidge, Julian. A History of the Conic Sections and Quadric Surfaces. Oxford, 1945.
6. Cox, David, John Little and Donal O’Shea. Ideals, Varieties, and Algorithms. Undergraduate Texts in Mathematics. Springer-Verlag, 1992.
7. Crow, Frank. The Origins of the Teapot. IEEE Computer Graphics and Applications, 7(1 ):8-19, 1987.
8. Dixon, A. L. The Eliminant of Three Quantics in Two Independent Variables. Proceedings of London Mathematical Society, 6:46-49,473-492, 1908.
9. Hoffmann, Christoph. Geometric and Solid Modeling: An Introduction. Morgan Kaufmann, 1989.
10. Hoffmann, Christoph. Implicit Curves and Surfaces in CAGD. IEEE Computer Graphics & Applications, 13(1 ):79-88, 1993.
11. Kajiya, James. Ray Tracing Parametric Patches. Proceedings of SIGGRAPH 82 (Boston, July 26-30, 1982). In Computer Graphics, 16,3 (July 1982), 245-254.
12. Kalkbrener, Michael. Three Contributions to Elimination Theory. PhD thesis, Johannes Kepler Universitat, Linz, Austria, 1991.
13. Katz, Sheldon and Thomas W. Sederberg. Genus of the Intersection Curve of Two Parametric Surface Patches. Computer Aided Geometric Design, 5:253-258, 1988.
14. Krishnan, S. and Dinesh Manocha. An Efficient Surface Intersection Algorithm Based on the Lower Dimensional Formulation. Technical Report TR94-062, Department of Computer Science, University of North Carolina, 1994.
15. Manocha, Dinesh and John F. Canny. Algorithms for Implicitizing Rational Parametric Surfaces. Computer-Aided Geometric Design, 9:25-50, 1992.
16. Manocha, Dinesh and John F. Canny. The Implicit Representation of Rational Parametric Surfaces. Journal of Symbolic Computation, 13:485-510, 1992.
17. Salmon, George. Modern Higher Algebra. Chelsea, New York, 5th edition, pp. 83-86, 1885.
18. Salmon, George. A Treatise on the Analytic Geometry of Three Dimensions. Longmans, Green and Co., London, 5th edition, p. 264, 1915.
19. Sederberg, Thomas W. Implicit and Parametric Curves and Surfaces for Computer Aided Geometric Design. PhD thesis, Purdue University, 1983.
20. Sederberg, Thomas W. Improperly Parametrized Rational Curves. Computer Aided Geometric Design, 3:67-75, 1986.
21. Sederberg, Thomas W. Techniques for Cubic Algebraic Surfaces. IEEE Computer Graphics and Applications, 10(4): 14- 26, 1990.
22. Sederberg, Thomas W., David C. Anderson, and Ronald N. Goldman. Implicit Representation of Parametric Curves and Surfaces. Computer Vision, Graphics and Image Processing, 28:72-84, 1984.
23. Sederberg, Thomas W. and Scott R. Parry. A Comparison of Curve-Curve Intersection Algorithms. Computer-Aided Design, 18:58-63, 1986.
24. Sederberg, Thomas W., Takafumi Saito, Dongxu Qi, and Krzysztof S. Klimaszewski. Curve Implicitization using Moving Lines. Computer Aided Geometric Design, 11:687-706, 1994.