On the lower degree intersections of two natural quadrics

ABSTRACT

In general, two quadric surface intersect in a space quartic curve. However, the intersection frequently degenerates to a collection of plane curves. Degenerate cases are frequent in geometric/solid modeling because degeneracies are often required by design. Their detection is important because degenerate intersections can be computed more easily and allow simpler treatment of important problems. In this paper, we investigate this problem for natural quadrics. Algorithms are presented to detect and compute conic intersections and linear intersections. These methods reveal the relationship between the planes of the degenerate intersections and the quadrics. Using the theory developed in the paper, we present a new and simplified proof of a necessary and sufficient condition for conic intersection. Finally, we present a simple method for determining the types of conic in a degenerate intersection without actually computing the intersection, and an enumeration of all possible conic types. Since only elementary geometric routines such as line intersection are used, all of the above algorithms are intuitive and easily implementable.

REFERENCES

• 1: S. S. Abhyankar , C. J. Bajaj, Automatic parameterization of rational curves and surfaces IV: algebraic space curves, ACM Transactions on Graphics (TOG), v.8 n.4, p.325-334, Oct. 1989 [doi>10.1145/77269.77273]
• 2: BEREIS, R. 1964. Darstellende Geometrie I. Akademie-Verlag, Berlin.
• 3: W. Boehm, On cyclides in geometric modeling, Computer Aided Geometric Design, v.7 n.1-4, p.243-255, Jun. 1990 [doi>10.1016/0167-8396(90)90034-O]
• 4: BROMWlCH, T.J. 1971. Quadratic forms and their classification by means of invariant-factors. Harrier Publishing Company, New York.
• 5: DANDELIN, G.P. 1822. M~moire sur quelques propri~t6s remarquables de la Focal Parabolique. Nouveaux Mdmoires de l'Academie Royale des Sciences et Belles-lettres de Bruxelles 2,171-202.
• 6: R. T. Farouki , C. Neff , M. A. O'Conner, Automatic parsing of degenerate quadric-surface intersections, ACM Transactions on Graphics (TOG), v.8 n.3, p.174-203, July 1989 [doi>10.1145/77055.77058]
• 7: Thomas Garrity , Joe Warren, On computing the intersection of a pair of algebraic surfaces, Computer Aided Geometric Design, v.6 n.2, p.137-153, May 1989 [doi>10.1016/0167-8396(89)90017-4]
• 8: GOLDMAN, R. N. 1983. Two approaches to a computer model for quadric surfaces. IEEE Comput. Graph. Appl. 3, 6, 21-24.
• 9: Ronald Goldman, Intersection of two lines in three-space, Graphics gems, Academic Press Professional, Inc., San Diego, CA, 1990
• 10: GOLDMAN, R. N., AND MILLER, J. R. 1990. Detecting and calculating conic sections in the intersection of two natural quadric surfaces, Part I: Detection. Drain, Oct.
• 11: Ronald N. Goldman , James R. Miller, Combining algebraic rigor with geometric robustness for the detection and calculation of conic sections in the intersection of two natural quadric surfaces, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.221-231, June 05-07, 1991, Austin, Texas, United States [doi>10.1145/112515.112545]
• 12: GOLDMAN, R. N., AND WARSEN, J. D. 1990. A sufficient condition for the intersection of two quadrics of revolution to degenerate into a pair of conic sections. Tech. Rep. Rice Univ., Dec.
• 13: GORDON, V. O., AND SEMENTSOV-OGIEVSKII, M.A. 1980. A Course in Descriptive Geometry. Translated from Russian by Leonid Levant, MIR Publishers, Moscow.
• 14: H~oa~, D. G., HILLYARD, R. C., NOURSE, B. E., AND MALR~dSON, P.J. 1980. Natural quadrics in mechanical design, in Proceedings of Autofact West 1 (Anaheim, Calif., Nov.) 363-378.
• 15: H/LBERT, D. AND COHN-VOSSEN, S. 1952. Geometry and the Imagination. Translated from the German edition, Anschauliche Geometric by P. Nemenyi, Chelsea, New York.
• 16: Christoph M. Hoffmann, Geometric and solid modeling: an introduction, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989
• 17: HOHMEYER, M. E. 1991. A surface intersection algorithm based on loop detection. Int. J. Comput. Geom. Appl. 1, 4 (Dec.), 473-490.
• 18: JOHNSTONE, J. K. AND SHENE, C.-K. 1992. Computing the intersection of a plane and a natural quadric. Comput. Graph. 16, 2, 179-186.
• 19: John K. Johnstone , Ching-Kuang Shene, Dupin Cyclides as Blending Surfaces Cones, Proceedings of the 5th IMA Conference on the Mathematics of Surfaces, p.3-29, September 14-16, 1992
• 20: 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]
• 21: L~ZVIN, J.Z. 1979. Mathematical models for determining the intersections of quadric surfaces. Comput. Graph. Image Process. ll, 73-87.
• 22: MANOCHA, D., AND CANNY, J. 1991. A new approach for surface intersection. Int. Comput. Geom. Appl. I, 4,491-516.
• 23: 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]
• 24: Mn.t,Ea, J. R., AND GOLDMAN, R. N. 1991. Detecting and calculating conic sections in the intersection of two natural quadric surfaces, Part II: Calculation. Draft, Feb.
• 25: James R. Miller , Ronald N. Goldman, Using Tangent Balls to Find Plane Sections of Natural Quadrics, IEEE Computer Graphics and Applications, v.12 n.2, p.68-82, March 1992 [doi>10.1109/38.124290]
• 26: O(:KEN, S., SCHWARTZ, J. T., AND SHARIR, M. 1987. Precise implementation of CAD primitives using rational parameterizations of standard surfaces. In Planning, Geometry, and Complexity of Robot Motion, J. T. Schwartz, M. Sharir and J. Hopcroft, Eds. Ablex Publishing Co., Norwood, N.J., 245 266.
• 27: M. A. O'Connor, Natural quadrics: projections and intersections, IBM Journal of Research and Development, v.33 n.4, p.417-446, July 1989
• 28: L. Piegl, Geometric method of intersecting natural quadrics represented in trimmed surface form, Computer-Aided Design, v.21 n.4, p.201-212, May 1989 [doi>10.1016/0010-4485(89)90045-6]
• 29: PIEGL, L. 1992. Constructive geometric approach to surface-surface intersection. In Geometry Processing for Design and Manufacturing, R. E. Barnhill, Ed. SIAM, Philadelphia, 137-159.
• 30: M. J. Pratt, Cyclides in computer aided geometric design, Computer Aided Geometric Design, v.7 n.1-4, p.221-242, Jun. 1990 [doi>10.1016/0167-8396(90)90033-N]
• 31: Mike Pratt, The virtues of cyclides in CAGD, Mathematical methods in computer aided geometric design II, Academic Press Professional, Inc., San Diego, CA, 1992
• 32: REJ4BOCK, F. 1964. Darstellende Geometrie, Second Ed., Springer-Verlag, New York.
• 33: SABIN, M.A. 1976. A method for displaying the intersection curve of two quadric surfaces. Comput. J. 19, 4, 336-338.
• 34: SAS}N, M.A. as communicated to Pratt {Pratt 1990}.
• 35: SAMUEL, N. M., REQUICHA, A. A. G., AND ELKIND, S.A. 1976. Methodology and results of an industrial part survey. Tech. Memo. No. 21, Production Automation Project, Univ. of Rochester, Rochester, NN.
• 36: SARRAGA, R.F. 1983. Algebraic methods for intersections of quadric surfaces in GMSOLID. Comput. Vis. Graph. Image Process. 22, 222-238.
• 37: Thomas W. Sederberg , Ray J. Meyers, Loop detection in surface patch intersections, Computer Aided Geometric Design, v.5 n.2, p.161-171, July 1988 [doi>10.1016/0167-8396(88)90029-5]
• 38: Ching-Kuang Shene, Planar intersection and blending of natural quadrics, Johns Hopkins University, Baltimore, MD, 1993
• 39: Ching-Kuang Shene, Planar intersection, common inscribed sphere and Dupin blending cyclides, Proceedings on the second ACM symposium on Solid modeling and applications, p.487-488, May 19-21, 1993, Montreal, Quebec, Canada [doi>10.1145/164360.164545]
• 40: Ching-Kuang Shene , John K. Johnstone, On the planar intersection of natural quadrics, Proceedings of the first ACM symposium on Solid modeling foundations and CAD/CAM applications, p.233-242, June 05-07, 1991, Austin, Texas, United States [doi>10.1145/112515.112546]
• 41: S~E~E, C.-K., AND JOHNSTONE, J.K. 1991b. On the lower degree intersections of two natural quadrics. Tech. Rep. JHU-91/15, Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, Md., Sept. 1991.
• 42: SHE~E, C.-K., ~u JOHNSTONE, J. K. 1991c. When does a quadrilateral have an inscribed circle? Tech. Rep. JHU-91/22, Dept. of Computer Science, The Johns Hopkins Univ., Baltimore, Md., Dec. 1991.
• 43: J. Warren, Blending quadric surfaces with quadric and cubic surfaces, Proceedings of the third annual symposium on Computational geometry, p.341-347, June 08-10, 1987, Waterloo, Ontario, Canada [doi>10.1145/41958.41995]
• 44: J. Warren, Blending algebraic surfaces, ACM Transactions on Graphics (TOG), v.8 n.4, p.263-278, Oct. 1989 [doi>10.1145/77269.77270]
• 45: WILSON, P.R. 1987. Conic representations for shape description. IEEE Comput. Graph. Appl. 7, 4 (April), 23-40.

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:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design

Keywords:
natural quadrics, planar intersection, solid modeling, surface intersection