Browse Prior Art Database

RAY TRACING PARAMETRIC PATCHES

IP.com Disclosure Number: IPCOM000127915D
Original Publication Date: 1982-Dec-31
Included in the Prior Art Database: 2005-Sep-14
Document File: 14 page(s) / 43K

Publishing Venue

Software Patent Institute

Related People

James T. Kajiya: AUTHOR [+3]

Abstract

This paper describes an algorithm that uses ray tracing techniques to display bivariate polynomial sur-face patches. A new intersection algorithm is developed which uses ideas from algebraic geometry to obtain a num-erical procedure for finding the intersection of a ray and a patch without subdivision. The algorithm may use complex coordinates for the (u, v~parameters of the patches. The choice of these coordinates makes the computations more uniform, so that there are fewer special cases to be con-sidered. In particular, the appearance and disappearance of silhouette edges can be handled quite naturally. The uniformity of these techniques may be suitable for imple-mentation on either a general purpose pipelined machine; or on special purpose hardware. KEYWORDS: computer graphics, raster graphics, ray trac-ing, parametric patches CR CATEGORIES: 1.3.3,1.3.5,1.3.7 From its inception, the method of ray tracing has al-ways been the technique of choice when ultimate rea-lism of computer generated images is the goal (Appel 1968. This paper describes a new technique for generating ray traced images of piecewise polynomial bivariate parametric patches. In contrast to other algorithms to do this, the new algorithm does not repeatedly subdivide a patch, but rather calculates an intersection between a patch and a ray using more or less direct numerical procedures. This procedure has a number of pleasant characteris-tics. First, for patches of low degree, the algorithm Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 1982 ACM 0-89791-076-1/82/007/0245 $00.75 proceeds more quickly. In fact, if the patch coefficients degenerate to a planar surface the amount of computa-tion needed to intersect a ray with it is roughly the same as for an algorithm tuned for ray-plane intersec-. tions. Second, the algorithm is robust - many patch. algorithms need preliminary subdivisions to satisfy some o, priors approximation [Blinn, et. at. 1980, the algorithm presented here has no such requirement. This paper treats the intersection problem only. There are many other components to a ray tracing system, such as the lighting model calculation (Whitted 1980, the use of object coherence to mitigate scene com-plexity [Rubin and Whitted 1980, antialiasing in the ray tracing context (Whined 1980], and the use of reflectance and normal vector perturbation mapping techniques to enhance realism [Blinn 1978b). We study the intersection problem because it has been found to be the most time critical step.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 10% of the total text.

Page 1 of 14

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

RAY TRACING PARAMETRIC PATCHES

James T. Kajiya California Institute of Technology Pasadena, CA 91125 5106 : T?VI : 82 Appears in ACM Computer Graphics, Volume 16, Number 3 July 1982, pages 245-254. Computer Graphics Volume 16, Number 3 July 198 RAY TRACING PARAMETRIC PATCHES James T. Kajiya California Institute of Technology Pasadena, Ca. 91125

ABSTRACT.

This paper describes an algorithm that uses ray tracing techniques to display bivariate polynomial sur-face patches. A new intersection algorithm is developed which uses ideas from algebraic geometry to obtain a num-erical procedure for finding the intersection of a ray and a patch without subdivision. The algorithm may use complex coordinates for the (u, v~parameters of the patches. The choice of these coordinates makes the computations more uniform, so that there are fewer special cases to be con-sidered. In particular, the appearance and disappearance of silhouette edges can be handled quite naturally. The uniformity of these techniques may be suitable for imple-mentation on either a general purpose pipelined machine; or on special purpose hardware.

KEYWORDS: computer graphics, raster graphics, ray trac-ing, parametric patches CR CATEGORIES: 1.3.3,1.3.5,1.3.7 From its inception, the method of ray tracing has al-ways been the technique of choice when ultimate rea-lism of computer generated images is the goal (Appel 1968. This paper describes a new technique for generating ray traced images of piecewise polynomial bivariate parametric patches. In contrast to other algorithms to do this, the new algorithm does not repeatedly subdivide a patch, but rather calculates an intersection between a patch and a ray using more or less direct numerical procedures.

This procedure has a number of pleasant characteris-tics. First, for patches of low degree, the algorithm

Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the ACM copyright notice and the title of the publication and its date appear, and notice is given that copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission. 1982 ACM 0-89791-076-1/82/007/0245 $00.75 proceeds more quickly. In fact, if the patch coefficients degenerate to a planar surface the amount of computa-tion needed to intersect a ray with it is roughly the same as for an algorithm tuned for ray-plane intersec-. tions. Second, the algorithm is robust - many patch. algorithms need preliminary subdivisions to satisfy some o, priors approximation [Blinn, et. at. 1980, the algorithm presented here has no such requirement.

This paper treats the intersection problem only. There are many other components to a ray tracing system, such as the lighting model calculation (Whitted 1980, the use of object coherence to mitigat...