A parametric algorithm for drawing pictures of solid objects composed of quadric surfaces

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A parametric algorithm for drawing pictures of solid objects composed of quadric surfaces

Full text

Pdf (785 KB)

Source

Communications of the ACM archive
Volume 19 , Issue 10 (October 1976) table of contents

Pages: 555 - 563

Year of Publication: 1976

ISSN:0001-0782

Author

Joshua Levin

New York Univ., and Renssalaer Polytechnic Institute, Troy, NY

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 8, Downloads (12 Months): 57, Citation Count: 31

Additional Information:

abstract references cited by index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/360349.360355 What is a DOI?

ABSTRACT

An algorithm for drawing pictures of three-dimensional objects, with surfaces made up of patches of quadric surfaces, is described. The emphasis of this algorithm is on calculating the intersections of quadric surfaces. A parameterization scheme is used. Each quadric surface intersection curve (QSIC) is represented as a set of coefficients and parameter limits. Each value of the parameter represents at most two points, and these may easily be distinguished. This scheme can find the coordinates of points of even quartic (fourth-order) intersection curves, using equations of no more than second order. Methods of parameterization for each type of QSIC are discussed, as well as surface bounding and hidden surface removal.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	I. C. Braid, The synthesis of solids bounded by many faces, Communications of the ACM, v.18 n.4, p.209-216, April 1975 [doi>10.1145/360715.360727]
	2	Paul G. Comba, A Procedure for Detecting Intersections of Three-Dimensional Objects, Journal of the ACM (JACM), v.15 n.3, p.354-366, July 1968 [doi>10.1145/321466.321468]
	3	Dresden, A. Solid Analytical Geometry and Determinants. Dover, New York, 1964.
	4	Levin, J.Z. A parametric algorithm for drawing pictures of solid objects bounded by quadric surfaces. Tech. Rep. CRL-46, School of Eng., Rensselaer Polytechnic Inst., Troy, N.Y., 1976.
	5	Loutrel, P. A solution to the hidden-line problem for computer-drawn polyhedra. IEEE Trans. Computers C-19, 3 (March 1970), 205-213.
	6	Mahl, R. Visible surface algorithm for quadric patches. IEEE Trans. Computers C-21, (Jan. 1972), 1-4.
	7	Metelli, F. The perception of transparency. Scientific American 230, 4 (April 1974), 90-98.
	8	William M. Newman , Robert F. Sproull, Principles of interactive computer graphics (2nd ed.), McGraw-Hill, Inc., New York, NY, 1979
	9	Bui Tuong Phong, Illumination for computer generated pictures, Communications of the ACM, v.18 n.6, p.311-317, June 1975 [doi>10.1145/360825.360839]
	10	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]
	11	Woon, P.Y. A computer procedure for generating visible-line drawings of solids bounded by quadric surfaces. Tech. Rep. 403-15, Dep. Electr. Eng., School of Eng. and Sci., New York U., New York, Nov. 1970.
	12	Woon, P.Y., and Freeman, H. A procedure for generating visible-line projections of solids bounded by quadric surfaces. Information Processing 71, Vol. 2, North-Holland Pub. Co., Amsterdam, 1971, pp. 1120-1125.

CITED BY 31

	Don Herbison-Evans, NUDES 2: A numeric utility displaying ellipsoid solids, version 2, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.354-356, August 1978
	Adrian E. Baer, Maintaining integrity in complex shape definitions, Proceedings of the 15th conference on Design automation, p.9-15, June 19-21, 1978, Las Vegas, Nevada, United States
	Nicola Geismann , Michael Hemmer , Elmar Schömer, Computing a 3-dimensional cell in an arrangement of quadrics: exactly and actually!, Proceedings of the seventeenth annual symposium on Computational geometry, p.264-273, June 2001, Medford, Massachusetts, United States
	Joshua Zev Levin, QUADRIL: A computer language for the description of quadric-surface bodies, ACM SIGGRAPH Computer Graphics, v.14 n.3, p.86-92, July 1980
	Norman Badler , Ruzena Bajcsy, Three-dimensional representations for computer graphics and computer vision, ACM SIGGRAPH Computer Graphics, v.12 n.3, p.153-160, August 1978
	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
	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
	Ching-Kuang Shene , John K. Johnstone, On the lower degree intersections of two natural quadrics, ACM Transactions on Graphics (TOG), v.13 n.4, p.400-424, Oct. 1994
	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
	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
	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
	Wayne E. Carlson, An algorithm and data structure for 3D object synthesis using surface patch intersections, ACM SIGGRAPH Computer Graphics, v.16 n.3, p.255-263, July 1982
	Laurent Dupont , Daniel Lazard , Sylvain Lazard , Sylvain Petitjean, Near-optimal parameterization of the intersection of quadrics, Proceedings of the nineteenth annual symposium on Computational geometry, June 08-10, 2003, San Diego, California, USA
	Elmar Schömer , Joachim Reichel , Thomas Warken, Efficient Collision Detection for Curved Solid Objects, Proceedings of the seventh ACM symposium on Solid modeling and applications, June 17-21, 2002, Saarbrücken, Germany
	Wenping Wang , Ronald Goldman , Changhe Tu, Enhancing Levin's method for computing quadric-surface intersections, Computer Aided Geometric Design, v.20 n.7, p.401-422, October 2003
	Yang Liu , Fa-Lai Chen, Algebraic conditions for classifying the positional relationships between two conics and their applications, Journal of Computer Science and Technology, v.19 n.5, p.665-673, September 2004
	James R. Miller, Analysis of Quadric-Surface-Based Solid Models, IEEE Computer Graphics and Applications, v.8 n.1, p.28-42, January 1988
	Jia Jinyuan , George Baciu , Ki-Wan Kwok, Quadric decomposition for computing the intersections of surfaces of revolution, Graphical Models, v.66 n.5, p.303-330, September 2004
	Gary Yngve , Greg Turk, Robust Creation of Implicit Surfaces from Polygonal Meshes, IEEE Transactions on Visualization and Computer Graphics, v.8 n.4, p.346-359, October 2002
	Eric Berberich , Michael Hemmer , Lutz Kettner , Elmar Schömer , Nicola Wolpert, An exact, complete and efficient implementation for computing planar maps of quadric intersection curves, Proceedings of the twenty-first annual symposium on Computational geometry, June 06-08, 2005, Pisa, Italy
	S. Lazard , L. M. Peñaranda , S. Petitjean, Intersecting quadrics: an efficient and exact implementation, Proceedings of the twentieth annual symposium on Computational geometry, June 08-11, 2004, Brooklyn, New York, USA
	Wenping Wang , Barry Joe , Ronald Goldman, Computing quadric surface intersections based on an analysis of plane cubic curves, Graphical Models, v.64 n.6, p.335-367, November 2002
	Elmar Schömer , Nicola Wolpert, An exact and efficient approach for computing a cell in an arrangement of quadrics, Computational Geometry: Theory and Applications, v.33 n.1-2, p.65-97, January 2006
	Sukhan Lee , Hernsoo Hahn, An Optimal Sensing Strategy for Recognition and Localization of 3D Natural Quadric Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.13 n.10, p.1018-1037, October 1991
	Sylvain Lazard , Luis Mariano Peñaranda , Sylvain Petitjean, Intersecting quadrics: an efficient and exact implementation, Computational Geometry: Theory and Applications, v.35 n.1, p.74-99, August 2006
	Zhi-qiang Xu , Xiaoshen Wang , Xiao-diao Chen , Jia-guang Sun, A robust algorithm for finding the real intersections of three quadric surfaces, Computer Aided Geometric Design, v.22 n.6, p.515-530, September 2005
	Pradeep Sinha , Eric Klassen , K. K. Wang, Exploiting topological and geometric properties for selective subdivision, Proceedings of the first annual symposium on Computational geometry, p.39-45, June 05-07, 1985, Baltimore, Maryland, United States
	Iddo Hanniel , Gershon Elber, Computing the Voronoi cells of planes, spheres and cylinders in R³, Proceedings of the 2008 ACM symposium on Solid and physical modeling, June 02-04, 2008, Stony Brook, New York
	Changhe Tu , Wenping Wang , Bernard Mourrain , Jiaye Wang, Using signature sequences to classify intersection curves of two quadrics, Computer Aided Geometric Design, v.26 n.3, p.317-335, March, 2009
	Laurent Dupont , Daniel Lazard , Sylvain Lazard , Sylvain Petitjean, Near-optimal parameterization of the intersection of quadrics: I. The generic algorithm, Journal of Symbolic Computation, v.43 n.3, p.168-191, March, 2008
	Iddo Hanniel , Gershon Elber, Computing the Voronoi cells of planes, spheres and cylinders in R3, Computer Aided Geometric Design, v.26 n.6, p.695-710, August, 2009

INDEX TERMS

Keywords:
computer graphics, hidden-surface removal, quadric surface intersection curves

Adobe Acrobat

QuickTime

Windows Media Player

Real Player