Automatic parsing of degenerate quadric-surface intersections

ABSTRACT

In general, two quadric surfaces intersect in a nonsingular quartic space curve. Under special circumstances, however, this intersection may “degenerate” into a quartic with a double point, or a composite of lines, conics, and twisted cubics whose degrees, counted over the complex projective domain, sum to four. Such degenerate forms are important since they occur with surprising frequency in practice and, unlike the generic case, they admit rational parameterizations. Invoking concepts from classical algebraic geometry, we formulate the condition for a degenerate intersection in terms of the vanishing of a polynomial expression in the quadric coefficients. When this is satisfied, we apply a multivariate polynomial factorization algorithm to the projecting cone of the intersection curve. Factors of this cone which correspond to intersection components “at infinity” may be removed a priori. A careful examination of the remaining cone factors then facilitates the identification and parameterization of the various real, affine intersection elements that may arise: isolated points, lines, conics, cubics, and singular quartics. The procedure is essentially automatic (avoiding the tedium of case-by-case analyses), encompasses the full range of quadric forms, and is amenable to implementation in exact (symbolic) arithmetic.

REFERENCES

• 1: S. S. Abhyankar , C. Bajaj, Automatic parameterization of rational curves and surfaces 1: conics and conicoids, Computer-Aided Design, v.19 n.1, p.11-14, Jan./Feb. 1987 [doi>10.1016/0010-4485(87)90147-3]
• 2: BROMWICH, T. J. I '. A. Quadratic Forms and Their Classification By Means of Invariant-Factors. U~:IIIIUI'ILIg~ 1 l'~l.L;bB 111 ~VltJ.bll~lll/t:tblL;~ i:tllU LVl;t:tbll~llli:tblL;i:U _r-llyblL;t'.i, ~NU. 3. I ~fiDLl'~lJ'r~ ____:_a.l.lll b. .{1/c;IILII~I',IJI'-- ~_ __ IN York.
• 3: DRESDEN, A. Solid Analytic Geometry and Determinants. 1930. Reprint. Dover, New York, 1964.
• 4: EISENHART, L.P. Coordinate Geometry. 1939. Reprint. Dover, New York, 1960.
• 5: HAKALA, D. G., HILLYARD, R. C., NOURSE, B. E., AND MALRAISON, P.J. Natural quadrics in mechanical desio~a_. In Proceedings of Autofact West !, Anaheim, CA., Nov. 1980, pp. 363-378:
• 6: HERSTEIN, I.i. Topics in Algebra. Blaisdell, New York, 1964.
• 7: LANDAU, S. Factoring polynomials quickly. Notices of the A.M.S. 34, 1 (1987), 3-8.
• 8: LENSTRA, A. K., LENSTRA, H. W., AND LOVASZ, L. Factoring oolynomials with rational coefficients. Mathematische Annalen 261, (1982), 515-534.
• 9: Joshua Levin, A parametric algorithm for drawing pictures of solid objects composed of quadric surfaces, Communications of the ACM, v.19 n.10, p.555-563, Oct. 1976 [doi>10.1145/360349.360355]
• 10: LEVIN, J.Z. Mathematical models for determining the intersections of quadric surfaces. Comput. Graph. Image Process. 11 (1979), 73-87.
• 11: James R. Miller, Geometric approaches to nonplanar quadric surface intersection curves, ACM Transactions on Graphics (TOG), v.6 n.4, p.274-307, Oct. 1987 [doi>10.1145/35039.35041]
• 12: OCKEN, S., SCHWARTZ, J. T., AND SHARIR, M. Precise implementation of CAD primitives using rational parameterizations of standard surfaces. Tech. Rep. No. 67, Computer Science Department, New York University, New York, 1983.
• 13: M. A. O'Connor, Natural quadrics: projections and intersections, IBM Journal of Research and Development, v.33 n.4, p.417-446, July 1989
• 14: 0t"~klSIL'~I, lV1. . IIIH;~blIULI llVlt Ll.l~{Jl~:lk~lll~ bllll~ lithe:linteL, bit)it t..,kltlVt~ UI bVVU ~L/ggU.ltlb ~tallO.L,t~iD. ULtt'f~./Jgg.{.,. J. 19 (1976), 336-338.
• 15: SALMON, G. Lessons Introductory to the Modern Higher Algebra. 1885. Reprint. Chelsea, New Varlr
• 16: SALMON, G. A Treatise on the Analytic Geometry of Three Dimensions, Vol. I. 1911. Reprint. Chelsea, New York.
• 17: SAMUEL, N, M., REQUICHA, A. A. G., AND ELKIND, S. A. Methodology and results of an industrial part survey. Tech. Memo. No. 21, Production Automation Project, University of Rochester, Rochester, N.Y., 1976.
• 18: SARRAGA, R.F. Algebraic methods for intersections of quadric surfaces in GMSOLID. Comput. Vision Graph. Image Process. 22 (1983), 222-238.
• 19: SNYDER, V., AND SISAM, C.H. Analytic Geometry of Space. Henry Holt, New York, 1914.
• 20: SOMMERVILLE, D. M.Y. Analytical Geometry of Three Dimensions. Cambridge University Press, Cambridge, England, 1951.
• 21: TILOVE, R. B., AND REQUICHA, A. A.G. Closure of boolean operations on geometric entities. Comput. Aided Des. 12, 5 (1980), 219-220.
• 22: USPENSKY, J. V. Theory of Equations. McGraw-Hill, New York, 1948.
• 23: Ruth A. Weiss, BE VISION, A Package of IBM 7090 FORTRAN Programs to Draw Orthographic Views of Combinations of Plane and Quadric Surfaces, Journal of the ACM (JACM), v.13 n.2, p.194-204, April 1966 [doi>10.1145/321328.321330]
• 24: woon, AND "~n~,t,~,m,,~T LI A ,-,,..,-,,..,,A,,,..., f-,-,,. ~,-,,-...o+;,-.,-, .~,;oiKl-,_l;,-,-- n~,-.-;--,-,~-inno ~~ or,,1;Ao bounded by quadric surfaces. Information Processing 71, North Holland, Amsterdam, 1971, pp. 1120-1125.

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:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.2 Algorithms
          Subjects: Algebraic algorithms

General Terms:
Algorithms, Theory