`Page 1 of 23
`
`Page 1 of 23
`
`GIA EXHIBIT 1003
`
`
`
`
`
`
`
`_,
`
`w-'-
`
`An Introduction 0
`Ray;/Tracing o
`
`
`
`
`
`_
`* Edited by
`ANDREW S. GLASSNER
`
`Xerox PARC
`
`3333 Coyote Hill Road
`Palo Alto CA 94304
`
`USA
`
`ACADEMIC PRESS
`
`
`
`Harcourt Brace _]ovanovich, Publishers
`' London ' San Diego ' New York ' Berkeley ' Boston
`Sydney ' Tokyo - Toronto
`
`rE1.
`
`‘
`.5L‘
`
`Page 2 of 23
`
`
`
`Page 3 of 23
`
`Page 3 of 23
`
`
`
`Andrew S. G/assner 13
`
`2.6 Reflection Rays
`
`If we look at a perfectly flat, shiny table, we will see reflections ofother objects
`in the tabletop. We see those reflections because light
`is arriving at
`the
`tabletop from the other objects, bouncing off of the tabletop, and then arriving
`in our eye. For a fixed eyepoint, each position on the table has exactly one
`direction from which light can come that will be bounced back into our eye.
`For example, Figure 9 shows a photon of light bouncing around a scene,
`ending up finally passing through the screen and into the eye. On its last
`bounce, the photon hit point P and then went into the eye. Photon B also hit
`point P, but it was bounced (or reflected) into a direction that didn’t end up
`going into our eye. So for that eyepoint and that object, only a photon
`travelling along the path marked A could have been reflected into our
`direction ofinterest.
`When we wish to find what light is reflected from a particular point into the
`direction of the incident ray, we find the rgflected my (or n_*}‘?ec:.‘ion ray) for that
`point and direction; this is the ray that can carry light to the surface that will
`be perfectly reflected into the direction of the incident ray. To find the color of
`the reflected ray, we follow it backwards to find from which object it began.
`The color of the light leaving that. object along the line of the reflected ray is
`the color of that reflected ray. When we know the reflectecl ray’s color, we can
`contribute it to any other light leaving the original surface struck by the
`incident ray.
`Note the peculiar terminology of backward ray tracing: light arrives along
`the reflected ray and departs along the incident ray.
`
`
`
`Image "plane
`
`
`
`Once
`reflected
`
`
`
`
` Twice
`reflected
`
` Reflected
`
`B
`
`Fig. 9. The color of perfectly reflected light is dependent on the color of the
`object and the color of the incoming light that bounces off in the direction we
`care about. For example, at point P we want to know the color of the light
`coming in on ray A, since that light is then bounced into the eye.
`
`
`
`Page 4 of 23
`
`
`
`Page 5 of 23
`
`Page 5 of 23
`
`
`
`
`
`ques
`
`are do begin
`
`no’ B;
`lhih‘ B;
`ts S do begin
`list‘
`
`nee’ algorithm. The
`hero, or after all the
`
`[mm-S,3CtiOn_ This is
`
`:5 the Candidatfiligfg
`35 are a1]5phe1~eS or
`unit Vector and an
`[ing wheres and a
`
`Ii: [3}, does not use
`aneration rays. The
`;s for other rays is.
`Ray classification is
`ave five degrees of
`-'2 is the unit sphere
`TIE five-dimensional
`
`3 hypercubes, and
`ach. A hypercube
`ilar directions, and
`hit by any of these
`
`ronment, we locate
`Ly and test only the
`
`Jiently encoded as
`fy the origin of the
`.ined from a face of
`31 by Such a 5-tup]e
`
`_.
`
`—
`
`_
`
`i
`
`James Arm and David Kirk 235
`
`and an element of the set {+X, —X, + Y, — Y, +Z, —Z]. If B is a 3-D box
`which contains the environment,
`then a set containing all rays which are
`relevant to this environment can be represented by six ‘copies’ of the space
`B X [— I,’ 1] X [— 1,1]. These bounding /zypercubes, corresponding to the six
`dominant axes, are a basis for combined spatial and directional subdivision
`using a hyper-octree, a 5-D analog of an octree. The 5-D hypercubes at the
`leaves of the hyper-octree are assigned lists of candidate objects in direct
`analogy with the voxels of a 3-D spatial subdivision scheme. We find the
`candidate list for a given ray by converting the ray into a 5~tuple and,
`beginning at the root of the hyper-octree corresponding to the ray’s dominant
`axis, traversing the tree until we find the leaf node containing that 5-tuple.
`The most recently accessed hypercubes can be cached in order to avoid this
`hierarchy traversal in most cases.
`To construct
`the candidate lists, we observe that a 5-D hypercube
`represents a collection of rays which originate from a 3-D voxel and possess
`directions given by a single direction cell. This collection of rays sweeps out
`an unbounded 3«D polyhedral volume called a beam. See Figure 22. The
`candidate list of a hypercube must contain all objects which intersect this
`beam. As the nodes of the hyper—octree are subdivided, a child’s candidate list
`can be obtained from the parent list by removing those objects which fall
`outside ofits narrower beam. By bounding objects with convex polyhedra, the
`operation of comparing objects with a beam reduces to detecting polyhedral
`
`
`
`Di'e5“°"5
`
`(bi
`
`
`Beam
`El
`
`+
`
`Directions
`
`Origins
`
`I
`
`Beam
`
`Fig. 22. Beams in la) 2—space and in (b) 3-space. A beam can be defined as
`the set sum of the direction pyramid and the voxel. That is, every point of the
`beam can be expressed as the vector sum of a point within the pyramid volume
`and a point within the voxel.
`
`Page 6 of 23
`
`
`
`Page 7 of 23
`
`Page 7 of 23
`
`
`
`
`
`
`
`James /'-lrvo and David Kirk 237
`
`procedure RC_|ntersectl ray )
`begin
`
`classil‘icarion
`of the ray
`
`lazy
`Subd,-W-S,-on
`& candidate
`list creation
`
`p 2 the 5'-tuple corresponding to ray;
`axis = dominant axis of ray;
`H = the leaf hypercube cf hyper—octree{ axis ] containing o;
`if C(Hl is "inherited” then C(H) = CH) O BeamlHl;
`
`while C(Hl is too large and H is not too small do begin
`partition H along each of the 5 axes;
`Let all the new children "inl7erit” C(|-ll;
`
`H = the child hypercube which contains p;
`C(Hl = CH) 0 BearnlHl:
`l reclassify candidates I
`endwhile;
`for each candidate in CH) do begin { stepping in
`ascending order }
`
`Candidate
`processing
`
`d zprcjection of ray.interva|.max onto axis;
`if cl < candidate.min then return; '{ past distance interval }
`lntersectl ray, candidate l;
`endfor
`end
`
`Fig. 23. An outline of the ray classification algorithm. The construction of the
`5-D hierarchy is an integral part of the algorithm because it occurs as a side
`effect of tracing rays. Subdivision continues until the candidate list is suffi-
`ciently small, or H becomes too small.
`
`6.5 Comparing the Directional Techniques
`
`Figure 24 shows a number of important similarities and differences among the
`directional techniques. Only features in which there is some variation are
`shown. Most of the differences are a direct result of nonuniform versus
`
`uniform direction subdivision. For instance, nonuniform subdivision leads
`naturally toward lazy evaluation and also requires more parameters and
`heuristics to control it. Conversely, uniform subdivision requires few param-
`eters and leads to very efficient loot-:—up, but also encourages construction as a
`pre-processing step. Note that these are not necessarily immutable properties
`but merely a reflection of the initial descriptions of
`these aigorithrns.
`Improvements and generalizations are no doubt possibie in each case.
`
` S
`
`for example,
`g,
`ive alternative is
`
`—sphere intersec-
`is also possible to
`. The techniques
`ration of ‘beam
`
`sts are sorted by
`optimization. A
`e candidate lists
`)rted. These lists
`
`s with respect to
`. All subsequent
`ed order can be
`
`i can potentially
`saving measures
`cting subdivision
`slated by rays of
`v on demand, as
`r lazy evaluation
`re actually used
`y the bounding
`
`ndidate lists. We
`
`oeam origin and
`mce. In order to
`
`of the remaining
`and begin anew
`nation makes the
`atial subdivision
`
`1 algorithm. The
`‘percube H, and
`ieh intersects the
`t we do not form
`:eded. When we
`
`h of5 axes), only
`‘he others simply
`:her children are
`. their beams.
`
`
`
`Page 8 of 23
`
`
`
`Page 9 of 23
`
`Page 9 of 23
`
`
`
`
`
`represented by an apex, center line, and spread angle. For the purpose of
`antivaiiasing, the intersection calculation not only needs to detect when a cone
`and an object intersect, but how much of the cone is blocked by the object. A
`sorted list of the closest few objects which intersect the cone is required so that
`the partial coverages can be properly combined. For reflection and refraction,
`the new center line is computed using standard ray tracing techniques. The
`calculation of the new virtual origin and spread angle required knowledge of
`the surface curvature. The method of cone tracing also extends the repertoire
`of ray tracing to inciude penurnbrae (from area light sources) and dull
`reflections. Due to the difficulty of the cone‘ intersection and partial coverage
`calculation for most objects, the environment is restricted to spheres, planes,
`and polygons.
`Kirk [38] extended the cone technique by accelerating the processing of
`partial intersections. The projected area of cone—sphere and cone—plane
`intersections can be pre-calculated for a wide range of cases and stored in a
`table. Using a table look-up instead of a direct calculation produces an
`approximate but
`fast partial coverage calculation. The cone area at
`the
`intersection can also be used toproperly anti-alias procedural textures. The
`cone radius at the intersection determines the aperture size of the smallest
`feature which should be represented in the texture.
`Heckbert and Hanrahan [30] introduced a different ray generalization in
`their beam tracing algorithm. In this approach rays are replaced by beams
`which are cones with arbitrary polygonal cross section. That is, a beam
`consists of a collection of rays which originate at a common apex and pass
`through some planar polygon. Note that this is different from the definition of
`a bearntin the context of the ray classification algorithm discussed in Section
`6.4. There the rays are restricted to pass through a rectangular polygon and
`the origins are not restricted to a single point.
`The restriction placed on the environment by this algorithm is that all
`objects must be constructed with planar polygonal facets. This preserves the
`basic characteristics of -beams under various interactions with the environ
`men
`t. For instance, the portion of a beam which continues past a partially
`(Figure 26), as do beams
`occluding object still has polygonal cross section
`). Refraction is
`the one
`which are reflected from any surface (Figure 27
`phenomenon which does not preserve the nature of beams. Because of
`nonlinearity, a refracted beam may no longer be a cone. One remedy is to
`approximate the elfect of refraction with a linear transformation. This is
`another compromise which must be made in order to obtain the benefits of
`beam tracing.
`Many aspects of the beam tracing algorithm are very similar to those of
`standard ray tracing. A beam tree is constructed by recursive reflection and
`transmission of beams, though the process of applying these operations to
`
`‘U93
`
`James Arvo and David Kirk 243
`
`61 at prion", we could
`ad to be drawn from
`
`hard to produce,
`led is large due to
`practical solution is
`fnate the integral of
`31:‘. If the variation
`
`samples need to be
`
`stimate of the true
`
`-m variable, and its
`re assume that the
`
`to
`1] used this fact
`sampling process,
`of the image. The
`puted pixel values,
`s the probability of
`aw that the samples
`‘ameters T and fit
`stored in a table.
`
`6 is incrementally
`he computed value
`11 of the N samples ,
`t1 the Student .5-test
`
`ray tracing stems
`form of these rays
`lations, and great
`gc for others, One
`.
`instead, operate
`ed as beams [30},
`uires some type of
`ts on the environ~
`
`r we may need to
`spting an approxi-
`e faster execution,
`
`cones which are
`
`
`
`Page 10 of 23
`
`
`
`Page 11 of 23
`
`Page 11 of 23
`
`
`
`achnfques
`
`1
`
`_,,.C|ipped beom
`cross-section
`
`James /lrvo and 1.9a-vi'd Kirk 245
`
`for rays. It makes it possible to avoid processing far awayobjects which are
`occluded by near ones. Heckbert and Hanrahan [30] therefore performed a
`sorting operation on the polygons intersected by the beam before processing
`‘them.
`-
`ii
`
`polygons similar to;t;l‘iose described by Weiler and Atherton [64-]. We must be
`able to subtract one polygon from another, or find their intersection, and
`express the result as another polygon. These operations can quickly lead to
`nonconvex or fragmented polygons containing holes. Because of the recursive
`nature of the beam tracing algorithm, the output of one such operation may
`become the input to another. This requires robust methods which can operate
`on arbitrarily complex polygons.
`Beam tracing can be broken down into three basic subproblems: intersec-
`tion, sorting, and clipping. Dadoun and Kirkpatrick [13] showed that all
`three of these can be accelerated by introducing a fiierarciiical scene repratent‘atz'on.
`This data structure employs both nested convex hulls and partitioning planes,
`combining aspects of bounding volume hierarchies with spatial subdivision.
`To construct it, the environment is first recursively subdivided, top-down,
`using a BSP tree. As in Fuch’s hidden surface algorithm {I6}, the partitioning
`planes may be selected to contain given polygons in the environment. All
`remaining polygons are grouped according to the two half—spaces defined by
`the plane, which requires splitting polygons which straddle the plane. After
`the BSP decomposition, we build a’ binary tree of nested convex hulls,
`bottom-up, beginning at the leaves of the BSP tree. The convex hulls at
`intermediate levels ofthe tree are constructed from the convex hulls of the two
`linearly separated child nodes. This operation is linear in the number of hull
`points, making this part of the pre-processing phase very fast. As Dadoun and
`Kirkpatrick [13] point out, the hierarchy thus constructed allows us to exploit
`convexity even in highly nonconvex environments. It can greatly accelerate
`beam intersection testing by rejecting objects in clusters
`rather
`than
`individually, which is exactly analogous to the bounding volume hierarchy
`techniques of Section 4.
`The hierarchical scene representation is a binary tree of convex hulls
`separated by planar partitions. Given a beam origin, the partitions provide an
`efficient means of assigning a priority to the groups of enclosed objects in
`exactly the same way that polygons are prioritized in the BSP hidden surface
`algorithm [16]. This moves much of the sorting operation into the initial
`construction of this data structure. The recursive traversal algorithm shown
`in Figure 12 is based upon the same principle and requires little modification to
`be applicable in this context. The result is similar to that achieved by the
`algorithm of Kay and Kajiya shown in Figure 9. Hierarchically nested convex
`hulls are examined in the order in which they are encountered by the beam.
`
`
`
`
`
`
`
`cross section of a beam.
`; which are non~simpIe
`
`_
`
`.
`
`3
`
`polygon
`
`aject
`
`‘hen a reflective face is
`uy reflecting the original
`he polygon against the
`
`ions used "in construct-
`zncountered, a ‘virtual’
`
`rn through the plane of
`3 its apex and its cross
`-ctive polygon with the
`as is that they can be
`' not. When a beam is
`ruction from the beam
`
`. See Figure 26. This
`interval optimization
`
`
`
`Page 12 of 23
`
`
`
`Page 13 of 23
`
`Page 13 of 23
`
`
`
`Page 14 of 23
`
`Page 14 of 23
`
`
`
`
`
`.
`
`-Tn.
`
`‘i
`
`Andrew S. Glassner 307
`
` n
`
`I R T N
`
`
`
`fe
`
`1 the polygon and the
`
`nci estimates For
`
`the
`
`estimating the visible
`within the pixel, and
`issing it (Figure 1).
`nd the surface normal
`
`I the surface normal at
`iigurc 2).
`
`efracted) ray and the
`:e from which it began
`
`passes. The relative
`ny the diameter of the
`
`)OSii('_‘ to that in which
`
`ive because one may
`
`:1
`
`incidentruy
`Reflected ray
`Transmitted ray
`Surface normal
`
`Fig. 2. Reflection and refraction.
`
`direct attention on only those rays that are known to be important for a particular
`image. This is the most popular mode of ray tracing in use today.
`
`beam tracing By using a polygonal cone as a primitive imaging element, one may
`take advantage of the coherence between rays with a common origin. In some
`situations, beam tracing can provide very accurate estimates ofthe incident light,
`useful For high~quality shading and anti-aliasing techniques. Under certain circum~
`stances, the computational savings from using a single plane to represent many rays
`can outweigh the additional cost per plane.
`
`bidirectional reflectance A function which relates incoming intensity in a given
`direction to outgoing intensity in another direction, within a small solid angle.
`
`binary space partition (BSP) tree A data structure for space subdivision.
`
`bleeding The eflect ofdilfuse inter-rctlections between objects. One object is said to
`‘bleed’ color to another, such as a red carpet ‘bleeding’ a pink tinge to nearby white
`walls.
`
`blue noise A set of samples with a frequency distribution close to that of a Poisson
`distribution.
`
`bounce light Synonym for bleeding.
`
`bounding volume This term (sometimes abbreviated as bound) usually refers to a
`mathematicaliy simple surface that encloses one or more objects. Bounding
`volumes are usuaily designed so that it is less expensive to intersect a ray with the
`
`Page 15 of 23
`
`
`
`Page 16 of 23
`
`Page 16 of 23
`
`
`
`
`
`Accelerating ray tracing,
`background to, 203—204-
`classification, 2042205
`Active subtree, 247
`Adaptive division graph, 252
`Adaptive sampling, 162
`Adaptive supersampling, 24--25
`Adaptive tree-depth control, 17, 205
`Aggregate object, 257
`A.k.a. picking, 34-
`Algebraic surface, 80, 86459
`Aliasing, 17-29, 196
`spatial, 19-20
`temporal, 20-22
`Ambient light, 157
`Analytic algorithms, 161
`Analytic surface, 80
`Angle of incidence, 131, 135
`Angle of reflection, 132
`Angle of refraction, 135
`Anti-aliasing, 19, 22-23
`Axial ray, 246
`
`Index
`
`Bounding volume, 206-208
`optimization 209-211
`Bresenhams’s algorithm, 99
`B-spline surfaces, 205
`BSP-trees, 99, 221, 245
`
`Backward ray tracing, 7-9
`Beam, 235
`Beam tracing, 24-3
`Beam tree, 24-3
`Bernstein basis, 95
`Bezier patches, 113
`Bezier spline, 95
`Eicubic patches, 94, 101
`Eilinear patches, 94-
`Binary search, 37
`Binary Space Partitioning (BSP)
`algorithm, 249
`Binary space partitioning trees (BSP—
`trees), 99, 221, 245
`Blend and join surfaces, 93434
`Blobs, 97~99
`B-net, 95
`Bounding boxes, 206
`Bounding hypercubes, 235
`
`
`
`Candidate, 217
`Candidate nodes, 112
`Cheesecake extent, 113
`Classification, 80
`Clipping plane, 3
`Coherence, 2384241
`Color, 121
`definition, 5 .
`and the eye, 129
`of photon, 5-7’
`and spectra, 12-'1—125
`Gone, 91
`inverse mappings, 75—76
`quadrics, 91
`Constructive solid geometry, (CSG),
`81,82, 86, 108-111
`optimizations for, 246~249
`Contributions of rays, 16
`Control points, 94
`Convex quadrilateral inverse mapping,
`59-54
`
`Convexity, 214-217
`Cook and Torrance shading model, 173
`Coordinate volumes, 248
`Critical angle, 137
`Cube,
`I04»
`Cylinder, 91
`inverse mapppings, 74-75
`quadrics, 91
`Cyprus—Beck clipping algorithm, 104.-
`
`Deformed surfaces, 115
`Depth of field, 28, 174-179
`Descartes’ rule of sign, 87
`
`Page 17 of 23
`
`
`
`
`
`
`
`8 ARay Tracing
`«
`Bibliography
`
`J
`
`Collected and annotated by
`
`PAUL S. HECKBERT and ERIC HAINES
`
`,.
`
`and Foumier, A., Ray casting using divide and conquer in
`1. Amanatides,
`Int. Conf. on Engineering and Computer Graphics, Beijing,
`screen space.
`China, Aug. 1984, similar to Siggraph ’84- paper but more emphasis on recursive
`screen subdivision, extents [screen subdivision, bounding volume].
`2. Amanatides, J., Ray tracing with cones. Comput. Graph. (Siggraph ’84 Proceed-
`ings), 18(3), 129—135, July 1984-. Ray tracing spheres and polygons with
`circular conical rays [cone tracing, anti—aliasing].
`3. Amanatides, J., Ray tracing with cones. Proceeding: of Graphic: Interface #594, May
`1984-, 97~98. Brief summary of his Siggraph paper [cone tracing].
`4. Amanatides, J., A Fast voxel traversal algorithm for ray tracing. Eurografihzics ’37,
`North-Holland, Amsterdam. Uniform grid space subdivision.
`5. Appxel, A., Some techniques for shading machine renderings of solids. AFIPS
`1963 Spring_]a£nt Computer Ctmf., 32, 37-45, 1968. First ray tracing paper, light
`ray tracing, b&w pictures on Calcomp plotter.
`6. Arnaldi, B., Priol, T., and Bouatouch, K., A new space subdivision method for
`ray tracing CSG modelied scenes. Vii‘. Campus’. 3, 98-108, 1987 [CSG].
`7. Arvo, J., Backward ray tracing. Siggraph ’86 Developments in Ray Tracing
`seminar notes, Aug. 1986. Light ray tracing.
`8. Arvo, J. and Kirk, D., Fast ray tracing by ray classification. Comput. Grapli.
`(Siggraph ’87 Proceedings), 21(4), 55-64-, July 1937 [octree], five dimensional
`space subdivision.
`9. Atherton, P. R., A scaniine hidden surface removal procedure for constructive
`solid geometry. Camput. Graph. (Siggraph ’83 Proceedings), 17(3), 73-82, July
`1983 [CSG].
`4
`10. Barr, A. H., Decal projections. Siggraph ’84 Mathematics of Computer
`Graphics seminar notes, July 1984 [texture mapping].
`11. Barr, A. H., Ray tracing deformed surfaces. Camput. Graph. (Siggraph '86
`I Proceedings), 20(4), 287-296, Aug. 1935.
`12. Bier, E. A., Solidviews, an interactive three-dimensional illustrator. BS & MS
`thesis, Dept. of EE&CS, MIT, May 1983. Use of Roth’s GSG ray tracer as part
`of an interactive system ECSG}.
`
`
`
`
`Page 18 of 23
`
`
`
`Page 19 of 23
`
`Page 19 of 23
`
`
`
`Paul S. Heckberr and Eric Hafnes 297
`
`a parallel ray tracing computer, Proceedings Graphics Interface ‘83’, 33-34, May
`1983,
`(also Proceedings XI Association of Simula Users Conference, 1983),
`
`
`
`
`
`H,___,,,..,.._,w....___,...._.
`
`in computer generated
`er on texture mapping,
`tion].
`rig. ACM Trans. Graph.
`finding roots of sums of
`
`using a oso modei.
`
`C., Image synthesis by
`494259, 1934.
`lg high quality pictures
`J84, pp. 151-177 (also
`
`ection. Camput. Graph.
`Junding volume].
`:~T1'tre, France, '50 pp.,
`
`sweep-defined objects.
`U. of Tech., Delft,
`
`3
`
`‘is use of ray casting in
`. 1984 [CSG].
`/V., Two methods for
`. Computer-Aided Design
`Loth: scanline interval
`subdivision.
`cylinders. ACM Trans.
`issue, Vol. 6, N0. 3,
`
`GEOM Program (for
`3/A~000 897, MAGI:
`.lI1Cl1 card era [CSG,
`
`35.
`
`38.
`
`39.
`
`40.
`
`41.
`
`42.
`
`43.
`
`[hardware], analysis of square and cubical processor arrays for ray tracing.
`33. Cleary, j. G. and Wyvill, G., An analysis of an algorithm for fast ray tracing
`using uniform space subdivision, Research Report 87/2'64/12, U. of Calgary,
`Dept. of CS, 1987.
`34. Cook, R. L., Porter, T. and Carpenter, L., Distributed ray tracing, Campui‘.
`Graph. (Siggraph ’84 proceedings), 18(3), 137-145, July 1984, Monte Carlo
`distribution of rays to get gloss, translucency, penuinbras, depth of‘ field, motion
`blur [probabilistic ray tracing, monte carlo, motion blur, stochastic sampling].
`Cook, R. L., Stochastic sampling in computer graphics, ACM Trans. Crap/1.,
`5(1), 51—72,jan. 1986.
`. Cook, R. L., Practical aspects of distributed ray tracing, Siggraph ’86 develop-
`ments in ray tracing seminar notes, Aug. 1986 [probabilistic ray tracing].
`37.
`Coquillart, S., An improvement of the ray tracing algorithm, Eurogrcywzzbs ’6’5
`77~8B, Sept. 1985, North-Holland, Amsterdam.
`,
`Cordonnier, E., Bouville, C., Marchal, I. and Dubois,
`L., Creating CSH
`-modelled pictures for ray casting display, Eurographics ’6'.5, Sept. 1985, North-
`Holland, Amsterdam.
`Dadoun, N., Kirkpatrick, D. G. and Walsh, J. P., The geometry of beam
`tracing, Prac. ijtfie Symp. on Comput. Geometry, 55-61, June 1985, the use of ESP
`trees and hierarchical bounding volumes for fast beam intersection testing.
`Davis, J. R., Nagel, R. and Guber, W., A model making and display technique
`for 3-D pictures, Proceedings aft/it 7:15 Annual zl/[eating of UAIDE, San Francisco,
`4'7-72, Oct. 1968 [CSG], synthavision genesis: CSG, primitives, optimization
`by region adjacency lists and adaptive subdivision for line drawings.
`Davis, E., Bailey, M. and Anderson, D. C., Realistic image generation and
`the modeling of mechanical solids, .C.‘amputers 2'21 Mecizanz'cal Engz'nem'ng, 1(1), Aug.
`1982, intro to CAD, solid modeling, and Whitted ray tracing, pre-Roth.
`Davis, j. E., Recursive ray tracing for the realistic display of solid models,
`MSME thesis, dept of ME, Purdue U., May 1982 [CAD].
`Deguchi, H., Nishimura, H., Yoshimura, H., Kawata, T., Shirakawa, I. and
`Omura, K., A parallel processing scheme for three~dimensional image creation,
`Caryl Pros.
`Int. Sjimp.
`art Circus"! and .SjJ.rtqms (ISCAS 34), 1285-1288, 1984
`[hardware], LINKS-1 hardware.
`Deguchi, H., Nishimura, H., Tatsumi, T., Kawata, T., Shirakawa,
`I. and
`Oinura, K., Performance evaluation of parallel processing in computer graphics
`system LINKS-I, submitted to Siggraph ’85, I985 [hardware].
`Dippe, M. A. Z. and Wold, E. H., Antialiasing through stochastic sampling,
`Comput. Graph. (Siggraph ’85 proceedings), 19(3), 69—78,_]uly 1985 [probabilis~
`tic ray tracing, stochastic sampling].
`Dippe, M. E. and Swensen, j., An adaptive subdivision algorithm and parallel
`architecture for realistic image synthesis, Comput. Graph. (Siggraph ’84 proceed-
`ings), 18(3), 149-158, July 1984, 3-D network of processors, algorithm for
`adaptive load distribution [hardware].
`Edwards, B. E.,
`Implementation of a ray tracing algorithm for rendering
`superquadric solids, Masters thesis, TR~820lB, Rensselaer Polytechnic Insti-
`
`Stelnberg, H. A., An
`Jdeling Vegetation and
`e1974, NTIS AD-732
`.bsarr1pli1'1g, pine tree
`
`anical design systems,
`
`nulation of reflectance
`
`Eng. 3 (4), 69~7‘i-, Jan.
`
`g graphics techniques,
`
`-acing, Camput. Graph.
`.343, 1937.
`:1 modelling, CAD34,
`r. 1984 [CSG].
`Design and analysis of
`
`
`
`44.
`
`45.
`
`46.
`
`47.
`
`Page 20 of 23
`
`
`
`Page 21 of 23
`
`Page 21 of 23
`
`
`
`Paul S. Heckbert and Eric Haines 299
`
`67.
`
`70.
`
`71.
`
`7‘2.
`
`73.
`
`74.
`
`‘75.
`
`ances of superquadrics
`
`_31exity analysis of ray
`1., Fort Collins, CO,
`
`I/,',«,,a[
`Gomput. Grap};_,-
`TOICYO '85), Tosiyasu
`
`Cilray-tracing system,
`e .
`Inter representation of
`modeling’
`technique,
`1985 [dynamic ray
`
`Comput. Graph. and
`cl Intersection testing
`
`TE Camput. Graph. and
`
`3 hypercube, Caltech,
`
`tct hierarchies for ray
`. bounding volume].
`3 objects, Proceedings
`
`H: Stimulation, 16(1),
`or’s language [QS(}]_
`PP». Mayfjune 1987,
`
`A ray tracer shadow
`). 5-16, Sept. 1986
`
`tents, IEEE Campuif,
`derer bench-marking
`
`tasters thesis, Cornell
`
`718-36 Synthesis, IEEE
`us shading and color
`
`’33
`;’1‘(.I1lJ}Z.
`es for finding roots of
`
`racing, Intl. Canf on
`’- Aug- 1934', early
`
`Peed up ray tracing,
`ze].
`nal objects, Comput,
`134. Weilcr-Atherton
`
`
`
`Heckbert, P. A., Ray tracing JELL-O (R) brand gelatin, Camput. Graph.
`(Siggraph '87 proceedings), 21(4), 73-74, July 1987.
`68. Jansen, 17., Data Structures for Ray tracing, Kessener L. R. A. Peters, F. and
`van Lierop M," L. P. eds, Data Structures for Raster Graphics,
`(Eurographic
`Seminar), New York, Springer-Verlag, 57-73, 1986, [data structures, CSG],
`overview of published algorithms for ray tracing using spatial subdivision.
`69. Joy, K. I; and Bhetanobhoktla, M. N., Ray tracing parametric surface patches
`utilizing numerical techniques and ray coherence, Camper. Graph. (Siggraph ‘S6
`Proceedings), 20(4), 279-285, Aug. 1986.
`Kajiya,
`T., Ray tracing parametric patches, Comput. Graph. (Siggraph '82
`proceedings) 16(3), 24-59254, July 1982,
`ray tracing bivariate polynomial
`patches, [patches].
`Kajiya,
`T., New techniques for ray tracing procedurally defined objects, ACM
`Trans. on Graph. 2 (3) 161-181, July 1983,
`(also appeared in Siggraph ’83
`proceedings), ray tracing‘ fractals, prisms, and surfaces of revolution,
`[fractal].
`Kajiya, J. T., Siggraph '83 tutorial on ray tracing, Siggraph ’83 State of the Art
`in Image Synthesis seminar notes, July 1983, good survey of ray tracing.
`Kajiya, J. T. and Von Herzen, B. P., Ray tracing volume densities, Compul.
`Graph. (Siggraph ’84 proceedings), 18(3),
`l65—17‘l-, July -1984, ray tracing and
`meterological simulation of clouds, [cloud].
`Kajiya, J. T., The Rendering Equation, Camput. Graph. (Siggraph '86 Proceed-
`ings), 20(4) 143-150, Aug. 1986, [shading, difiuse rellection, radiosity].
`Kaplan, M. R., Space-tracing, a constant time ray tracer,. Siggraph ’85 State of
`the Art in Image Synthesis seminar notes, July 1985, like Giassner.
`Kay, D. S. and Greenberg, D. P., Transparency for computer synthesized
`images’, Camput. Graph. (Siggraph ’79 proceedings), 13(2) 158-464, Aug. 1979,
`2.5—D ray tracing: refraction by warping background image, contains better
`refraction formula than Whitted.
`Kay, D. S., Transparency, refraction, and ray tracing for computer synthesized
`images, Masters thesis, Cornell U., Jan. 1979.
`Kay, T. L. and Kajiya, J. T., Ray tracing complex scenes, Compact. Graph.
`(Siggraph ’86 Proceedings), 20(4) 269~278, Aug. 1986, [bounding volume].
`Kedem, G. and Ellis,J. L., The Raycasting Machine, Prar. IEEE Intl. Conf on
`Computer Design: VLSI in Computers (ICCD ’84), (Port Chestner, NY 8-11
`Oct. 1984:), IEEE Computer Society Press, Silver Spring, MD, 5334538, 1984-.
`Kirk, D. 13., The simulation of natural features using cone tracing, Advanced
`Computer Graphics (Proc. of CG Tokyo '86), Tosiyasu Kunii ed., 129m144-,
`Springer Verlag, Tokyo, 1986, [antialiasing].
`Kitaoka, S., Kit: An experimental solid modelling system, MS thesis, University
`of Utah, April 1985, Roth-style ray tracer with the addition of several new
`surfaces including patches, sweeps, etc. Produced ‘Scene with Corkscrew’ on
`Siggraph ’85 back cover, [solid modeling, primitive shapes].
`Kitaoka, S., KIT: An experimental solid modeling system, The Visual Computer,
`2(1), 9, Jan 5986, Roth-style ray tracer with the addition of several new surfaces
`including patches, sweeps etc.,
`[solid modeling, primitive shapes].
`Lee, M. E., Redner, R. A. and Uselton, S. P., Statistically optimized satnpiing
`for distributed ray tracing, Comput. Graph. (Siggraph ’85 Proceedings), 19(3)
`6l—67, July 1985, [probabilisticray tracing, stochastic sampiing].
`Levner, G., Tassinari, P. and Marini, D., A simple method for ray tracing
`bicubic surfaces, Comput. Graph. 1987, Tosiyasu Kunii ed., 2854502, Springer
`Verlag, Tokyo, 1987.
`
`76.
`
`77.
`
`78.
`
`79.
`
`80.
`
`81.
`
`82.
`
`83.
`
`84.
`
`
`
`Page 22 of 23
`
`
`
`l
`
`H 7
`
`'
`
`-
`
`.
`
`.
`
`_
`
`'
`'
`
`The creation of realistic 3-D images is one ofthe most _-
`powerful applications of Com uter Graphics. The Ray.
`_ Tracing technique has quickly ecome one of the most.
`popular approaches to creating synthetic images. The 3
`._'_algori'thm-is sim le,‘ elegant. and easily-"implemented by the
`professionalancl)
`novice programmer alike. Ray Tracing is a '
`" powerful tool both for understanding image rendering. and
`for creating new pictures.
`" 7_ An Introduction to Ray Tracing begins
`the basic ideas of
`tracing, and builds to a survey
`he state-of-the-art in efficient :
`s. Along the way:-'-'_
`i< covers the basic '
`"
`"algorithms in depth. and reviews
`important material from surface
`physics. the geometry of shapes '-
`and surfaces. and a detailed analysis
`of the intersection routines at the
`heart of every ray tracing program.
`The book is heavily illustrated with
`color and black-and-white figures.
`This book will be welcomed by
`ne interested in the art and
`
`.-
`Academic Press '
`_ Harcourt Brace Jovanovich. Publishers, if
`.LONDON SAN DIEGO NEW YORK
`'
`.1. BEFlK_ELE‘( aosron. SYDNEY.
`-
`T
`-
`"TOKYO
`-
`
`'
`
`'
`
`.
`
`'
`
`'
`Harcourt Brace Jovimnvicli Limited
`24128 Oval Road. London NW1 TDX. England
`Academic Press
`I250 sixm Avenue. San Diego. California 92101-4311. USA
`Harcourt Brace Jovanavich Group (Australia) Pty Limited
`Locked Bag 16. Marrickviila. NSW 2204. Australia
`Harcourt Brace Jovanovlch Japan. Inc.
`lchibanchci Cenlral Building, 224. lchibancho. Cliiyoda-ku.
`Tokyo 102. Japan
`
`-
`
`'
`
`'
`
`Page 23 of 23
`
`Page 23 of 23