@TechReport{Bala98rep, author = "K. Bala and J. Dorsey and S. Teller", title = "Bounded-Error Interactive Ray Tracing", pages = "1--17", institution = "MIT", year = 1998, month = mar, number = "MIT LCS TR-748", who = "Havran Vlastimil: RT-0183", } @InProceedings{GGW-1998-cgf, pages = "C--29--C--54", year = "1998", title = "Adaptive Supersampling in Object Space Using Pyramidal Rays", author = "J. Genetti and D. Gordon and G. Williams", url = "http:// www.sdsc.edu/~genetti/Papers/CGF98/ASOS.html", language = "en", booktitle = "Computer Graphics Forum", who = "Havran Vlastimil: RT-0182", } @InProceedings{EVL-1995-34, pages = "C--311--C--324", year = "1995", title = "Using Procedural {RenderMan} Shaders for Global Illumination", author = "Philipp Slusallek and Thomas Pflaum and Hans-Peter Seidel", url = "http://visinfo.zib.de/EVlib/Show?EVL-1995-34", language = "en", abstract = "Global illumination techniques like radiosity or Monte-Carlo ray-tracing are becoming standard features of rendering systems. However, there is currently no accepted interface format which supports an appropriate physically-based scene description. In this paper we present extensions to the well-known RenderMan interface, which allow for a physically based scene description and support advanced global illumination techniques. Special emphasis has been laid on the support for procedural descriptions of reflection and emission by RenderMan surface shaders. So far, they could not be used with most global illumination algorithms. The extensions have been implemented in a physically-based rendering system and are illustrated with examples.", editor = "F. Post and M. G{\"{o}}bel", booktitle = "Computer Graphics Forum (Proceedings EUROGRAPHICS '95)", who = "Havran Vlastimil: RT-0181", } @Article{Nakamaru97, author = "Koji Nakamaru and Yoshio Ohno", title = "{Breadth-First Ray Tracing Utilizing Uniform Spatial Subdivision}", journal = "IEEE Transactions on Visualization and Computer Graphics", volume = "3", number = "4", month = oct, year = "1997", pages = "316--328", abstract = "Breadth-first ray tracing is based on the idea of exchanging the roles of rays and objects. For scenes with a large number of objects, it may be profitable to form a set of rays and compare each object in turn against this set. By doing so, thrashing, due to disk access, can be minimized. In this paper, we present ways to combine breadth-first methods with traditional efficient algorithms, along with new schemes to minimize accessing objects stored on disk. Experimental analysis, including comparisons with depth-first ray tracing, shows that large databases can be handled efficiently with this approach.", keywords = "breadth-first ray tracing, uniform spatial subdivision", tvcg-abstract-url = "http://www.computer.org/tvcg/tg1997/v0316abs.htm", tvcg-pdf-url = "http://pdf.computer.org/tg/books/tg1997/pdf/v0316.pdf", who = "Havran Vlastimil: RT-0180", } @Article{Elber:1997:RT, author = "Gershon Elber and {Jung-Ju} Choi and {Myung-Soo} Kim", title = "Ruled Tracing", journal = "The Visual Computer", year = "1997", volume = "13", number = "2", pages = "78--94", publisher = "Springer-Verlag", note = "ISSN 0178-2789", annote = "The traditional ray-tracing technique based on a ray-surface intersection is reduced to a ruled or developable surface-surface intersection problem. That enables direct freeform surface rendering. By exploiting the spatial coherence gained in the ruled/developable surface-tracing approach presented, the emulation of shadows, specular reflections, and/or refractions in a freeform surface environment can all be implemented efficiently. The approach provides a direct freeform surface-rendering alternative to ray tracing. An implementation of a direct freeform surface renderer that emulates shadows as well as specular reflections is discussed. This renderer processes isoparametric curves as its basic building block, eliminating the need for polygonal approximation.", keywords = "Ray tracing, light wavefronts, direct freeform surface rendering, shadow computation, reflection/refraction", who = "Havran Vlastimil: RT-0179", } @Article{Ip:1997:EPS, author = "Horace H. S. Ip and Ken C. K. Law and Gabriel K. P. Fung", title = "Epipolar plane space subdivision method in stereoscopic ray tracing", journal = "The Visual Computer", year = "1997", volume = "13", number = "6", pages = "247--264", publisher = "Springer-Verlag", note = "ISSN 0178-2789", keywords = "ray tracing, stereoscopic rendering, epipolar geometry", annote = "This paper presents a novel space subdivision scheme based on epipolar geometry. It is particularly suited to stereoscopic ray tracing in the backprojection method. The resulting rendering algorithm gives a substantial speed improvement over generating stereo pair images separately, and the generated stereo images are effectively identical to those generated separately. In this work, the generation of stereoscopic images is accelerated by two methods, namely stereoscopic backprojection and epipolar plane-space subdivision. The performance of our algorithm is evaluated and compared with the octree algorithm. Experimental results demonstrating the efficiency of the approach are presented.", who = "Havran Vlastimil: RT-0178", } @Article{Choi92, author = "H. K. Choi and C. M. Kyung", title = "{PYSHA}: a shadow-testing acceleration scheme for ray tracing", journal = "Computer-aided design", volume = "24", number = "2", month = feb, year = "1992", note = "hybrid scheme of light buffer and grid subdivision with cost comparison on the fly", who = "Havran Vlastimil: RT-0177", } @TechReport{Sherstyuk96:TCHR, author = "A. Sherstyuk", title = "Ray-tracing implicit surfaces: a generalized approach", year = "1996", type = "Technical Report", number = "1996/290", institution = "Monash University", keywords = "implicit surfaces, ray-tracing", who = "Havran Vlastimil: RT-0176", } @InProceedings{Genetti:1993:RTA, author = "Jon Genetti and Dan Gordon", title = "Ray Tracing with Adaptive Supersampling in Object Space", year = "1993", month = may, booktitle = "Proceedings of Graphics Interface '93", publisher = "Canadian Information Processing Society", pages = "70--77", address = "Toronto, Ontario", keywords = "sampling, antialiasing, penumbrae", who = "Havran Vlastimil: RT-0175", } @Article{Redner:1995:SBI, author = "Richard A. Redner and Mark E. Lee and Samuel P. Uselton", title = "Smooth {B}-Spline Illumination Maps for Bidirectional Ray Tracing", journal = "ACM Transactions on Graphics", volume = "14", number = "4", pages = "337--362", month = oct, year = "1995", coden = "ATGRDF", ISSN = "0730-0301", bibdate = "Mon May 26 09:17:43 1997", url = "http://www.acm.org/pubs/toc/Abstracts/0730-0301/225296.html", abstract = "In this paper we introduce B-spline illumination maps and their generalizations and extensions for use in realistic image generation algorithms. The B-spline lighting functions (i.e., illumination maps) are defined as weighted probability density functions. The lighting functions can be estimated from random data and may be used in bidirectional distributed ray tracing programs as well as radiosity oriented algorithms. The use of these lighting functions in a bidirectional ray tracing system that can handle dispersion as well as the focusing of light through lenses is presented.", acknowledgement = ack-nhfb, keywords = "algorithms; theory", subject = "{\bf I.3.7}: Computing Methodologies, COMPUTER GRAPHICS, Three-Dimensional Graphics and Realism, Visible line/surface algorithms.", note = "Corrections to Figures 4--9 are available on the World-Wide Web at path=http://www.acm.org/tog/AandE.html=.", who = "Havran Vlastimil: RT-0174", } @Article{Lee:1985:SOS, author = "Mark E. Lee and Richard A. Redner and Samuel P. Uselton", editor = "B. A. Barsky", title = "Statistically Optimized Sampling for Distributed Ray Tracing", journal = "Computer Graphics", volume = "19", number = "3", pages = "61--67", month = jul, year = "1985", coden = "CGRADI, CPGPBZ", ISSN = "0097-8930", annote = "Cook, Porter, and Carpenter coined the phrase ``distributed ray tracing'' to describe a technique for using each ray of a super-sampled ray tracing procedure as a sample in several dimensions to achieve effects such as penumbras and motion blur in addition to spatial antialiasing. The shade to be displayed at a pixel is a weighted integral of the image function. The purpose of using many rays per pixel is to estimate the value of this integral. In this work, a relationship between the number of sample rays and the quality of the estimate of this integral is derived. Furthermore, the number of rays required does not depend on the dimensionality of the space being sampled, but only on the variance of the multi-dimensional image function. The algorithm has been optimized through the use of statistical testing and stratified sampling.", conference = "held in San Francisco, CA; 22--26 July 1985", keywords = "I37 ray-tracing, distributed, I3m optimization, I37 motion blur, stratified point sampling, ray tracing anti aliasing stochastic", who = "Havran Vlastimil: RT-0173", } @Article{Mitchell:1992:RTI, author = "Don P. Mitchell", title = "Ray Tracing and Irregularities of Distribution", year = "1992", month = may, journal = "Third Eurographics Workshop on Rendering", pages = "61--69", address = "Bristol, UK", keywords = "monte carlo", who = "Havran Vlastimil: RT-0172", } @inproceedings{Cook84, author = "Robert L. Cook and Thomas Porter and Loren Carpenter", title = "Distributed Ray Tracing", booktitle = "Computer Graphics (SIGGRAPH '84 Proceedings)", month = jul, year = "1984", pages = "137-45", keywords = "monte carlo, stochastic, penumbrae, depth of field, motion blur, antialiasing", comments = "also in Tutorial: Computer Graphics: Image Synthesis, Computer Society Press, Washington, 1988, pp. 139-147", who = "Havran Vlastimil: RT-0171", } @InProceedings{amanatides84a, author = "John Amanatides", title = "Ray Tracing with Cones", pages = "129--135", booktitle = "Computer Graphics (SIGGRAPH '84 Proceedings)", volume = "18", number = "3", year = "1984", month = jul, conference = "held in Minneapolis, Minnesota; 23--27 July 1984", keywords = "cone tracing, antialiasing, I35 Ray Tracing", annote = "ray tracing spheres and polygons with circular conical rays A technique for antialiasing in ray tracing is presented which utilizes cones instead of rays. Cones prevent problems generally associated with point sampling, and therefore allow for more natural images. The mathematics involved seem only ``pretty'' for spherical objects, so an acid test has yet to be performed. \\ A new approach to ray tracing is introduced. The definition of a ``ray'' is extended into a cone by including information on the spread angle and the virtual origin. The advantages of this approach, which tries to model light propagation with more fidelity, include a better method of antialiasing, a way of calculating fuzzy shadows and dull reflections, a method of calculating the correct level of detail in a procedural model and texture map, and finally, a procedure for faster intersection calculation.", who = "Havran Vlastimil: RT-0170", } @InProceedings{shinya87a, author = "Mikio Shinya and Tokiichiro Takahashi and Seiichiro Naito", title = "Principles and Applications of Pencil Tracing", pages = "45--54", booktitle = "Computer Graphics (SIGGRAPH '87 Proceedings)", volume = "21", number = "4", year = "1987", month = jul, editor = "Maureen C. Stone", conference = "held in Anaheim, California; 27 -- 31 July 1987", keywords = "ray tracing, paraxial theory", annote = "Pencil tracing, a new approach to ray tracing, is introduced for faster image synthesis with more physical fidelity. The paraxial approximation theory for efficiently tracing a pencil of rays is described and analysis of its errors is conducted to insure the accuracy required for pencil tracing. The paraxial approximation is formulated from a 4x4 matrix (a system matrix) that provides the basis for pencil tracing and a variety of ray tracing techniques, such as beam tracing, ray tracing with cones, ray-object intersection tolerance, and a lighting model for reflection and refraction. In the error analysis, functions that estimate approximation errors and determine a constraint on the spread angle of a pencil are given. \\ The theory results in the following fast ray tracing algorithms; ray tracing using a system matrix, ray interpolation, and extended `beam tracing' using a `generalized perspective transform.' Some experiments are described to show their advantages. A lighting model is also developed to calculate the illuminance for refracted and reflected light.", who = "Havran Vlastimil: RT-0169", } @InProceedings{mitchell87a, author = "Don P. Mitchell", title = "Generating Antialiased Images at Low Sampling Densities", pages = "65--72", booktitle = "Computer Graphics (SIGGRAPH '87 Proceedings)", volume = "21", number = "4", year = "1987", month = jul, editor = "Maureen C. Stone", conference = "held in Anaheim, California; 27 -- 31 July 1987", keywords = "adaptive sampling, antialiasing, filtering, noise perception, nonuniform sampling, ray tracing, reconstruction", who = "Havran Vlastimil: RT-0168", } @Article{Heckbert:1984:BTP, author = "Paul S. Heckbert and Pat Hanrahan", title = "Beam Tracing Polygonal Objects", journal = "Computer Graphics (SIGGRAPH'84 Proceedings)", volume = "18", number = "3", pages = "119--127", month = jul, year = "1984", coden = "CGRADI, CPGPBZ", ISSN = "0097-8930", annote = "Weiler-Atherton algorithm applied to ray tracing. Heckbert and Hanrahan present an elegant image space algorithm for rendering objects composed of polygonal facets. It utilizes image coherence and generates a final picture consisting of polygons. \\ Ray tracing has produced some of the most realistic computer generated pictures to date. They contain surface texturing, local shading, shadows, reflections, and refractions. The major disadvantage of ray tracing results from its point-sampling approach. Because calculation proceeds {\em ab initio} at each pixel it is very CPU intensive and may contain noticeable aliasing artifacts. It is difficult to take advantage of spatial coherence because the shapes of reflections and refractions from curved surfaces are so complex. \\ In this paper we describe an algorithm that utilizes the spatial coherence of polygonal environments by combining features of both image and object space hidden surface algorithms. Instead of tracing infinitesimally thin rays of light, we sweep areas through a scene to form ``beams.'' This technique works particularly well for polygonal models since for this case the reflections are linear transformation, and refractions are often approximately so. \\ The recursive beam tracer begins by sweeping the projection plane through the scene. Beam-surface intersections are computed using two-dimensional polygonal set operations and an occlusion algorithm similar to the Weiler-Atherton hidden surface algorithm. For each beam-polygon intersection the beam is fragmented and new beams created for the reflected and transmitted swath of light. These sub-beams are redirected with a 4x4 matrix transformation and recursively traced. This beam tree is an object space representation of the entire picture.", conference = "held in Minneapolis, Minnesota; 23--27 July 1984", keywords = "polygon, ray tracing beam antialiasing, Weiler-Atherton polygon clipping", who = "Havran Vlastimil: RT-0167", } InProceedings{snyder87a, author = "John M. Snyder and Alan H. Barr", title = "Ray Tracing Complex Models Containing Surface Tessellations", pages = "119--128", booktitle = "Computer Graphics (SIGGRAPH '87 Proceedings)", volume = "21", number = "4", year = "1987", month = jul, editor = "Maureen C. Stone", conference = "held in Anaheim, California; 27 -- 31 July 1987", keywords = "parametric surface, triangle, list, 3d grid", annote = "An approach to ray tracing complex models containing mathematically defined surfaces is presented. Parametric and implicit surfaces, and boolean combinations of these, are first tessellated into triangles. The resulting triangles from many such surfaces are organized into a hierarchy of lists and 3D grids, allowing efficient calculation of ray/model intersections. \\ The technique has been used to ray trace models containing billions of triangles and surfaces never before traced. The organizing scheme developed is also independently useful for efficiently ray tracing any any complex model, whether or not it contains surfaces tessellations.", who = "Havran Vlastimil: RT-0166", } @Article{Ke93, author = "Hao-Ren Ke and Ruei-Chuan Chang", title = "An Efficient Hierarchical Traversal Algorithm for Ray Tracing", journal = "Visual Computer", volume = "10", number = "2", pages = "79--87", year = "1993", keywords = "efficiency", who = "Havran Vlastimil: RT-0165", } @Article{Ke:1995:RCV, author = "H. R. Ke and R. C. Chang", title = "Ray-cast volume rendering accelerated by incremental trilinear interpolation and cell templates", journal = "The Visual Computer", year = "1995", volume = "11", number = "6", publisher = "Springer-Verlag", pages = "297--308", note = "ISSN 0178-2789", who = "Havran Vlastimil: RT-0164", } @Article{Ke:1993:SBP, author = "Hao-ren Ke and Ruei-Chuan Chang", title = "Sample buffer: {A} progressive refinement ray-casting algorithm for volume rendering", journal = "Computers and Graphics", volume = "17", number = "3", pages = "277--283", month = may # "--" # jun, year = "1993", coden = "COGRD2", ISSN = "0097-8493", bibdate = "Fri Feb 07 11:04:26 1997", acknowledgement = ack-nhfb, affiliation = "Natl Chiao Tung Univ", affiliationaddress = "Hsinchu, Taiwan", classification = "723.5; 741.2; 902.1; 921.6", journalabr = "Comput Graphics (Pergamon)", keywords = "Algorithms; Color; Image processing; Image quality; Interpolation; Opacity; Ray casting algorithm; Sample buffer; Three dimensional computer graphics; Transfer functions; Transparency; Visualization; Volume data rendering; Volume visualization", who = "Havran Vlastimil: RT-0163", } @InProceedings{Sung:1991:DOT, author = "K. Sung", title = "A {DDA} Octree Traversal Algorithm for Ray Tracing", pages = "73--85", booktitle = "Eurographics '91", year = "1991", month = sep, editor = "Werner Purgathofer", publisher = "North-Holland", conference = "European Computer Graphics Conference and Exhibition; held in Vienna, Austria; 2-6 September 1991", keywords = "ray tracing", who = "Havran Vlastimil: RT-0162", } @InProceedings{Coquillart:1985:IRT, author = "S. Coquillart", title = "An Improvement of the Ray-Tracing Algorithm", booktitle = "Computer Graphics Forum (Eurographics '85 Proceedings)", volume = "4", number = "3", pages = "77--88", year = "1985", month = sep, publisher = "North-Holland", conference = "European Computer Graphics Conference and Exhibition in Bath, England; 28 -- 29 March 1985", annote = "This paper describes an improvement of the ray-tracing algorithm. The new method takes advantage of a data structure which allows us to consider only the closest objects to the path of the ray. This technique can be applied to primary and secondary rays. Using this method, the run-time depends more on the complexity of the generated picture than on the complexity of the scene.", who = "Havran Vlastimil: RT-0161", } @InProceedings{Sousa:1990:IRT, author = "A. Augusto Sousa and Antonio M. C. Costa and Fernando N. Ferreira", title = "Interactive Ray-Tracing for Image Production with Increasing Realism", pages = "449--457", booktitle = "Eurographics '90", year = "1990", month = sep, editor = "C. E. Vandoni and D. A. Duce", publisher = "North-Holland", conference = "European Computer Graphics Conference and Exhibition; held in Montreux, Switzerland; 3 -- 7 September 1990", keywords = "rendering, interactive ray tracing, increasing realism, modular and paralle architectures, transputers, parallel processing", who = "Havran Vlastimil: RT-0160", } @InProceedings{Speer92, author = "L. Richard Speer", title = "A New Subdivision Method for High-speed, Memory Efficient Ray Shooting", booktitle = "Third Eurographics Workshop on Rendering", pages = "45--60", address = "Bristol, UK", month = may, year = "1992", who = "Havran Vlastimil: RT-0159", } @Article{Maillot:1992:PRT, author = "J-L. Maillot and L. Carraro and B. Peroche", title = "Progressive Ray Tracing", year = "1992", month = may, journal = "Third Eurographics Workshop on Rendering", pages = "9--20", address = "Bristol, UK", who = "Havran Vlastimil: RT-0158", } @TechReport{Sherstyuk98:TCHR, author = "A. Sherstyuk", title = "Fast Ray Tracing of Implicit Surfaces", year = "1998", type = "Technical Report", number = "1998/04", institution = "Monash University", keywords = "implicit surfaces, ray-tracing", who = "Havran Vlastimil: RT-0157", } @TechReport{Sherstyuk97:TCHR, author = "A. Sherstyuk", title = "Shells, crabs and seahorses: expanding the modeling power of implicit surfaces", year = "1997", type = "Technical Report", number = "1997/330", institution = "Monash University", keywords = "natural forms, convolution surfaces, geometric modelling, implicit surfaces", who = "Havran Vlastimil: RT-0156", } @TechReport{McCormack97:TCHR, author = "J. McCormack and A. Sherstyuk", title = "Creating and Rendering Convolution Surfaces", year = "1997", type = "Technical Report", number = "1997/324", institution = "Monash University", keywords = "convolution surfaces, geometric modelling, implicit surfaces, ray-tracing", who = "Havran Vlastimil: RT-0155", } @InProceedings{Heckbert87, author = "Paul S. Heckbert", title = "Ray Tracing {JELL}-{O} ({R}) Brand Gelatin", booktitle = "Computer Graphics (SIGGRAPH '87 Proceedings)", pages = "73--4", month = jul, year = "1987", keywords = "lattice algorithm, Jell-O (TM), gelatin", note = "revision appears in CACM, Vol. 31, \#2, Feb. 1988, p. 130-134 Published as Computer Graphics (SIGGRAPH '87 Proceedings), volume 21, number 4", who = "Havran Vlastimil: RT-0154", } @Article{Slusallek:1994:IRP, author = "Ph. Slusallek and Th. Pflaum and H.-P. Seidel", title = "Implementing {RenderMan} --- Practice, Problems and Enhancements", volume = "13", number = "3", pages = "C/443--C/454", month = "????", year = "1994", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Mon Apr 14 10:23:20 MDT 1997", acknowledgement = ack-nhfb, classification = "C6130B (Graphics techniques); C6150E (General utility programs); C6180 (User interfaces)", conflocation = "Oslo, Norway; 12-16 Sept. 1994", conftitle = "15th Annual Conference and Exhibition. EUROGRAPHICS'94", corpsource = "Comput. Graphics Group, Erlangen Univ., Germany", keywords = "interfaces; rendering (computer graphics); Rendering systems; rendering systems; RenderMan; Shading Language; solid modelling; user", thesaurus = "Rendering [computer graphics]; Solid modelling; User interfaces", treatment = "A Application; P Practical", url = "http://visinfo.zib.de/EVlib/Show?EVL-1994-19", language = "en", abstract = "The RenderMan interface has been proposed as a general interface to rendering systems, yet only a few implementations of the interface exist. In this paper we describe the implementation of the RenderMan interface on a general rendering architecture that supports various rendering algorithms. Speci,cally we discuss the implementation of the RenderMan Shading Language and its integration into our rendering architecture. Special attention is focused on the problems that we have encountered and how they can be solved. Additionally, we suggest extensions and enhancements to the current interface de,nition, which would make RenderMan easier to implement and more ,exible to use.", journal = "Computer Graphics Forum (Proc. Eurographics '94)", who = "Havran Vlastimil: RT-0153", } @InProceedings{Rushmeier93, author = "Holly E. Rushmeier and Charles Patterson and Aravindan Veerasamy", title = "Geometric Simplification for Indirect Illumination Calculations", booktitle = "Proc. Graphics Interface '93", publisher = "Canadian Inf. Proc. Soc.", address = "Toronto, Ontario", month = may, year = "1993", pages = "227--236", keywords = "Monte Carlo, progressive refinement, ray tracing, multiresolution modeling", note = "http://www.cc.gatech.edu/gvu/people/Phd/Charles.Patterson", annote = "multiresolution model creation (clustering) not fully automated", who = "Havran Vlastimil: RT-0152", } @InProceedings{Shirley:1991:RTF, author = "Peter Shirley and Kelvin Sung and William Brown", title = "A Ray Tracing Framework for Global Illumination Systems", pages = "117--128", booktitle = "Proceedings of Graphics Interface '91", year = "1991", month = jun, conference = "held in Calgary, Alberta; 3-7 June 1991", keywords = "ray tracing, radiosity, object-oriented design, software components, zonal method, visual realism", who = "Havran Vlastimil: RT-0151", } @InProceedings{Marton:1996:SEM, author = "L. {Szirmay-Kalos} and G. Marton", title = "On the Complexity of Ray Shooting", booktitle = "Dagstuhl Seminar on Rendering, 1996", year = "1996", who = "Havran Vlastimil: RT-0150", } @PhdThesis{bronsvoort90a, author = "Willem F. Bronsvoort", title = "Direct Display Algorithms for Solid Modelling", month = jun, year = "1990", type = "Ph.D. Thesis", school = "Delft University of Technology", annote = "Advisor: Denis J. McConalogue In this thesis algorithms are discussed for displaying geometric models of three-dimensional objects. An important use of such algorithms is in CAD/CAM-systems to give the designer insight in the shape of the design. \\ Of particular concern here are direct display algorithms for constructive solid geometry models and generalized cylinders. `Direct' in this context means that a solid object is displayed without the need to convert its model into a boundary representation providing the information about faces, edges and vertices required by the standard display algorithms. \\ For constructive solid geometry models, the starting point is a collection of primitive objects, such as cubes, spheres and cylinders, that can be combined into more complex objects with set operations. The two alternatives for displaying such models, namely conversion into a boundary representation followed by display with a standard algorithm, and direct display with an adapted algorithm, are weighed. An overview of direct display algorithms for constructive solid geometry models is also given. \\ Generalized cylinders are objects defined by an arbitrary two-dimensional contour, or cross-section, and an arbitrary three-dimensional trajectory along which to sweep the contour. With profiled generalized cylinders, the contour can be scaaed along the trajectory in two perpendicular directions according to two profile curves. An exact definition of such objects is given. Here also the alternative for display, namely conversion into a boundary representation followed by display with a standard algorithm, and direct display with a special algorithm, are compared. \\ Finally, some conclusions are drawn, and directions for further research on direct display algorithms for solid models are identified.", who = "Havran Vlastimil: RT-0149", } @InProceedings{kajiya83a, author = "J. T. Kajiya", title = "New Techniques For Ray Tracing Procedurally Defined Objects", pages = "91--102", booktitle = "Computer Graphics (SIGGRAPH '83 Proceedings)", volume = "17", number = "3", year = "1983", month = jul, conference = "held in Detroit, Michigan; 25--29 July 1983", keywords = "I37 fractal surfaces, I37 prisms, I37 ray tracing, I37 surfaces of revolution, ray tracing intersect, procedural models, fractals, revolution, prisms", annote = "Also appears in {\bf Tutorial: Computer Graphics: Image Synthesis}, Kenneth I. Joy, Charles W. Grant, Nelson L. Max, and Lansing Hatfield (eds.), Computer Society Press, Washington, 1988, p. 168-188. \\ We present new algorithms for efficient ray tracing of three procedurally defined objects: fractal surfaces, prisms, and surfaces of revolution. The fractal surface algorithm performs recursive subdivision adaptively. Subsurfaces which cannot intersect a given ray are culled from further consideration. The prism algorithm transforms the three-dimensional ray-surface intersection problem into a two-dimensional ray-curve intersection problem, which is solved by the method of strip trees. The surface-of-revolution algorithm transforms the three-dimensional ray-surface intersection problem into a two-dimensional curve-curve intersection problem, which again is solved by strip trees. \\ Kajiya presents good solid methods for ray tracing various models which are represented procedurally. Fractals are ray traced as they are built, which keeps unseen fractal surfaces from being evolved. Prisms are ray traced in a fairly simple fashion. A clever use of geometric transforms is used to ray trace surfaces of revolution. Makes good use of strip trees (see Ballard).", who = "Havran Vlastimil: RT-0148", } @Article{Hanrahan:1983:RTA, author = "Pat Hanrahan", title = "Ray Tracing Algebraic Surfaces", journal = "Computer Graphics (SIGGRAPH '83 Proceedings)", volume = "17", number = "3", pages = "83--90", month = jul, year = "1983", coden = "CGRADI, CPGPBZ", ISSN = "0097-8930", annote = "numerical techniques for finding roots of polynomials \\ Many interesting surfaces can be written as polynomial functions of the spatial coordinates, often of low degree. We present a method based on a ray casting algorithm, extended to work in more than three dimensions, to produce pictures of these surfaces. The method uses a symbolic algebra system to automatically derive the equation of intersection between the ray and the surface and then solves this equation using an exact polynomial root finding algorithm. \\ Included are illustrations of the cusp catastrophe surface, and two unusually shaped quartic surfaces, Kummer's quadruple and Steiner's surface.", conference = "held in Detroit, Michigan; 25--29 July 1983", keywords = "root finding, algebraic surface, ray tracing intersect blob, I33 ray tracing, I37 algebraic surface", who = "Havran Vlastimil: RT-0147", } @InProceedings{heidrich-gi98, title = "Ray-Tracing Procedural Displacement Shaders", author = "Wolfgang Heidrich and Hans-Peter Seidel", booktitle = "Graphics Interface", year = "1998", month = jun, pages = "8--16", url = "http://www.dgp.toronto.edu/gi/gi98/papers/111/111.html", who = "Havran Vlastimil: RT-0146", } @inproceedings{gonzalez:cgi:98, author = "P. Gonzalez and F. Gisbert", title = "Object and Ray Coherence in the Optimization of the Ray Tracing Algorithm", booktitle = "Proceedings of Computer Graphics International '98 (CGI'98)", year = "1998", month = jun, pages = "264--267", address = "Hannover, Germany", publisher = "IEEE, NY", who = "Havran Vlastimil: RT-0145", } @Article{Moeller:1997:FMS, author = "Tomas M{\"{o}}ller and Ben Trumbore", title = "Fast, Minimum Storage Ray-Triangle Intersection", journal = "Journal of Graphics Tools", year = "1997", volume = "2", number = "1", note = "ISSN 1086-7651", annote = "We present a clean algorithm for determining whether a ray intersects a triangle. The algorithm translates the origin of the ray and then changes the base to yield a vector (t u v)T, where t is the distance to the plane in which the triangle lies and (u,v) represents the coordinates inside the triangle. One advantage of this method is that the plane equation need not be computed on the fly nor be stored, which can amount to significant memory savings for triangle meshes. As we found our method to be comparable in speed to previous methods, we believe it is the fastest ray-triangle intersection routine for triangles that do not have precomputed plane equations.", who = "Havran Vlastimil: RT-0144", } @Article{pulleyblank87a, author = "Ron Pulleyblank and John Kapenga", title = "The Feasibility of a {VLSI} Chip for Ray Tracing Bicubic Patches", pages = "33--44", journal = "IEEE Computer Graphics and Applications", volume = "7", number = "3", year = "1987", month = mar, keywords = "bicubic patch", annote = "Also appears as ``A VLSI Chip for Ray Tracing Bicubic Patches'' in {\bf Advances in Computer Graphics Hardware I}, W. Stra\mbox{\ss}er (ed.), 1987, p. 125-140. \\ In this article we explore the possibility of a VLSI chip for ray tracing bicubic patches in B\'{e}zier form. The purpose of the chip is to calculate the intersection point of a ray with the bicubic patch to a specified level of accuracy, returning parameter values $(u,v)$ specifing the location of the intersection on the patch, and a parameter value, $t$, which specifies the location of the intersection on the ray. The intersection is calculated by successively subdividing the patch and computing the intersection of the ray with a bounding box of each subpatch until the bounding volume meets the accuracy requirement. There are two operating modes: one in which only the nearest intersection is found, and another in which all intersections are found. This algorithm (and the chip) correctly handle the difficult cases of the ray tangentially intersecting a planar patch and intersections of the ray at a silhouette edge of the patch. Estimates indicate that such a chip could be implemented with 2-micron NMOS (N-type metal oxide semiconductor) and could compute patch-ray intersections at the rate of one every 15 microseconds for patches that are prescaled and specified to a 12-bit fixed point for each of the $x, y$, and $z$ components. A version capable of handling 24-bit patches could compute patch-ray intersections at the rate of one every 140 microseconds. Calculations of the normal at the intersection point could be performed with the addition of Re scalar subtractions and six scalar multiplies. Images drawn using a software version of the algorithm are presented and discussed.", who = "Havran Vlastimil: RT-0143", } @InProceedings{Pearce:1991:ESC, author = "Andrew Pearce and David Jevans", title = "Exploiting Shadow Coherence in Ray Tracing", pages = "109--116", booktitle = "Proceedings of Graphics Interface '91", year = "1991", month = jun, conference = "held in Calgary, Alberta; 3-7 June 1991", keywords = "ray tracing, shadow testing, shadow caching, spatial subdivision", who = "Havran Vlastimil: RT-0142", } @Article{haines86a, author = "Eric A. Haines and Donald P. Greenberg", title = "The Light Buffer: {A} Ray Tracer Shadow Testing Accelerator", pages = "6--16", journal = "IEEE Computer Graphics and Applications", volume = "6", number = "9", year = "1986", month = sep, keywords = "shading, ray tracing, shadows, ray tracing shadow cull", abstract = "In one area of computer graphics, realistic image synthesis, the ultimate goal is to produce a picture indistinguishable from a photograph of a real environment. A particularly powerful technique for simulating light reflection---an important element in creating this realism---is called ray tracing. This method produces images of excellent quality, but suffers from lengthy computation time that limits its practical use. \\ This article presents a new method to reduce shadow testing time during ray tracing. The technique involves generating light buffers, each of which partition the environment with respect to an individual light source. These partition descriptions are then used during shadow testing to quickly determine a small subset of objects that may have to be tested for intersection. \\ The results of timing tests illustrate the beneficial performance of these techniques. The tests compare the standard ray-tracing algorithm to light buffers of varying resolution.", who = "Havran Vlastimil: RT-0141", } @InProceedings{shirley90b, author = "Peter Shirley", title = "A Ray Tracing Method for Illumination Calculation in Diffuse-Specular Scenes", pages = "205--212", booktitle = "Proceedings of Graphics Interface '90", year = "1990", month = may, conference = "held in Halifax, Nova Scotia; 14-18 May 1990", keywords = "bump mapping, illumination, radiosity, radiance, ray tracing, realism, stratified sampling, texture mapping", annote = "Several ways of improving the realism of the results of traditional ray tracing are presented. The essential physical quantities of spectral radiant power and spectral radiance and their use in lighting calculations are discussed. Global illumination terms are derived by employing illumination ray tracing for calculation of quickly changing indirect lighting components, and radiosity ray tracing for slowly changing indirect lighting components. Direct lighting is calculated during the viewing phase allowing the use of bump maps. Finally, a method is introduced that reduces the total number of shadow rays to no more than the total number of viewing rays for a given picture.", who = "Havran Vlastimil: RT-0140", } @InProceedings{Shirley:1991:DLC, author = "Peter Shirley and Changyaw Wang", title = "Direct lighting calculation by Monte Carlo integration", booktitle = "Eurographics Workshop on Rendering", year = "1991", conference = "held in Barcelona, Spain; 13-15 May 1991", keywords = "monte carlo, illumination", annote = "Application of Monte Carlo techniques for rendering scenes with multiple light sources. Only one shadow ray per viewing ray is used. Some issues for the design of probability densities for light sources are given.", who = "Havran Vlastimil: RT-0139", } @Article{Shirley:1996:MCT, author = "Peter Shirley and Changyaw Wang and Kurt Zimmerman", title = "{Monte Carlo} Techniques for Direct Lighting Calculations", journal = "ACM Transactions on Graphics", volume = "15", number = "1", pages = "1--36", month = jan, year = "1996", coden = "ATGRDF", ISSN = "0730-0301", bibdate = "Wed Apr 24 07:49:27 1996", url = "http://www.acm.org/pubs/toc/Abstracts/0730-0301/225887.html, http://www.acm.org/pubs/toc/Abstracts/0730-0301/226151.html", abstract = "In a distributed ray tracer, the sampling strategy is the crucial part of the direct lighting calculation. Monte Carlo integration with importance sampling is used to carry out this calculation. Importance sampling involves the design of integrand-specific probability density functions that are used to generate sample points for the numerical quadrature. Probability density functions are presented that aid in the direct lighting calculation from luminaires of various simple shapes. A method for defining a probability density function over a set of luminaires is presented that allows the direct lighting calculation to be carried out with a number of sample points that is independent of the number of luminaires.", acknowledgement = ack-nhfb, keywords = "algorithms; design; theory", subject = "{\bf G.3}: Mathematics of Computing, PROBABILITY AND STATISTICS. {\bf G.1.4}: Mathematics of Computing, NUMERICAL ANALYSIS, Quadrature and Numerical Differentiation. {\bf I.3.0}: Computing Methodologies, COMPUTER GRAPHICS, General. {\bf I.4.1}: Computing Methodologies, IMAGE PROCESSING, Digitization, Sampling.", who = "Havran Vlastimil: RT-0138", } @InProceedings{Shirley92-DRTTP, author = "Peter Shirley and Changyaw Wang", month = may, year = "1992", title = "Distribution {Ray} {Tracing}: {Theory} and {Practice}", booktitle = "Third Eurographics Workshop on Rendering", pages = "33--43", address = "Bristol, UK", keywords = "Monte Carlo", who = "Havran Vlastimil: RT-0137", } @Article{Musgrave:1989:SRE, author = "F. Kenton Musgrave and Craig E. Kolb and Robert S. Mace", editor = "Jeffrey Lane", title = "The Synthesis and Rendering of Eroded Fractal Terrains", journal = "Computer Graphics (SIGGRAPH '89 Proceedings)", volume = "23", number = "3", pages = "41--50", month = jul, year = "1989", coden = "CGRADI, CPGPBZ", ISSN = "0097-8930", annote = "info on efficiently ray tracing height fields \\ In standard fractal terrain models based on fractional Brownian motion the statistical character of the surface is, by design, the same everywhere. A new approach to the synthesis of fractal terrain height fields is presented which, in contrast to previous techniques, features locally independent control of the frequencies composing the surface, and thus local control of fractal dimension and other statistical characteristics. The new technique, termed {\em noise synthesis}, is intermediate in difficulty of implementation, between simple stochastic subdivision and Fourier filtering or generalized stochastic subdivision, and does not suffer the drawbacks of creases or periodicity. Varying the local crossover scale of fractal character or the fractal dimension with altitude or other functions yields more realistic first approximations to eroded landscapes. A simple physical erosion model is then suggested which simulates hydraulic and thermal erosion processes to create global stream/valley networks and talus slopes. Finally, an efficient ray tracing algorithm for general height fields, of which most fractal terrains are a subset, is presented.", conference = "held in Boston, Massachusetts; 31 July -- 4 August 1989", keywords = "fractal, terrain models, stochastic subdivision, fractional Brownian motion, fractal dimension, lacunarity, crossover scale, erosion models, height fields, ray tracing", who = "Havran Vlastimil: RT-0136", } @InProceedings{musgrave89c, author = "F. Kenton Musgrave", title = "Prisms and rainbows: a dispersion model for computer graphics", pages = "227--234", booktitle = "Proceedings of Graphics Interface '89", year = "1989", month = jun, conference = "held in London, Ontario; 19-23 June 1989", keywords = "refraction, stochastic sampling, distributed ray tracing, spectrum, color gamut", annote = "{\em Dispersion} is the spreading of refracted light into its component colors or spectrum. A model of refraction including dispersion is developed using the techniques of distributed ray tracing. Two models of the rainbow, one empirical or impressionistic, the other purely physical, are developed using the results of the dispersion model. The problem of representing the spectrum of monochromatic colors using the rgb primaries of the graphics color monitor is addressed.", who = "Havran Vlastimil: RT-0135", } @TechReport{Musgrave:1988:GTF, author = "F. Kenton Musgrave", title = "Grid Tracing: Fast Ray Tracing for Height Fields", year = "1988", type = "Technical Report", number = "YALEU/DCS/RR-639", institution = "Yale University Dept. of Computer Science Research", keywords = "parallel processing", annote = "An implementation of ray tracing using Linda. \\ A fast algorithm for ray tracing height fields is presented. The algorithm employs a modified Bresenham DDA to traverse a two dimensional array of height values. At each cell the altitude of the ray is compared with the heights of the four corners of the cell; ray/object intersections need only be calculated when the altitude of the ray is in the range of those heights. The average number of ray/object intersections performed is about two per ray; the two objects tested for intersection are located in $O(\sqrt{N-1})$ time where $N$ is the number of height values in the field.", who = "Havran Vlastimil: RT-0134", } @InProceedings{Chapman90, author = "John Chapman and Thomas W. Calvert and John Dill", title = "Exploiting Temporal Coherence in Ray Tracing", booktitle = "Proceedings of Graphics Interface '90", pages = "196--204", publisher = "Canadian Information Processing Society", address = "Toronto, Ontario", month = may, year = "1990", keywords = "animation, temporal coherence", who = "Havran Vlastimil: RT-0133", } @InProceedings{Woo:1990:VOT, author = "Andrew Woo and John Amanatides", title = "Voxel Occlusion Testing: {A} Shadow Determination Accelerator for Ray Tracing", pages = "213--220", booktitle = "Proceedings of Graphics Interface '90", year = "1990", month = may, conference = "held in Halifax, Nova Scotia; 14-18 May 1990", keywords = "grid, intersection culling, occlusion, penumbra, ray tracing, shadows, umbra, voxel traversal", annote = "A shadow determination accelerator for ray tracing is presented. It is built on top of the uniform voxel traversal grid structure. The accelerator proves to be rather efficient, requires little additional memory and the worst case scenario per shadow determination just reduces down to traditional voxel traversal. It can also be extended to model linear, area lights, as well as atmospheric shadows.", who = "Havran Vlastimil: RT-0132", } @InProceedings{Jevans92, author = "David Jevans", title = "Object Space Temporal Coherence for Ray Tracing", booktitle = "Proceedings of Graphics Interface '92", pages = "176--183", publisher = "Canadian Information Processing Society", address = "Toronto, Ontario", month = may, year = "1992", keywords = "temporal coherence, efficiency, space subdivision", who = "Havran Vlastimil: RT-0131", } @InProceedings{Woo:1992:RTP, author = "Andrew Woo", title = "Ray tracing polygons using spatial subdivision", pages = "184--191", booktitle = "Proceedings of Graphics Interface '92", year = "1992", month = may, conference = "held in Vancouver, B.C.; 11-15 May 1992", keywords = "intersection culling, subdivision, voxel traversal", who = "Havran Vlastimil: RT-0130", } @InProceedings{Marton95a, author = "Gabor Marton", editor = "H.P. Seidel, B. Girod, H. Niemann", title = "Surfaces for Ray Tracing: A Fast View-Dependent Algorithm", booktitle = "Proceedings of 3D Image Analysis and Synthesis '97", pages = "19--26", year = "1997", month = nov, who = "Havran Vlastimil: RT-0129", } @InCollection{Marton95b, author = "Gabor Marton", editor = "Alan W. Paeth", title = "Acceleration of Ray Tracing via Voronoi Diagrams", booktitle = "Graphics Gems V", pages = "268--284", publisher = "Academic Press", address = "Boston MA", year = "1995", who = "Havran Vlastimil: RT-0128", } @InCollection{Moeller95a, author = "Tomas Moeller", editor = "Alan W. Paeth", title = "A Linear-time simple bounding volume algorithm", booktitle = "Graphics Gems V", pages = "242--257", publisher = "Academic Press", address = "Boston MA", year = "1995", who = "Havran Vlastimil: RT-0127", } @InCollection{Wu93a, author = "Xiaolin Wu", editor = "David Kirk", title = "A Linear-time simple bounding volume algorithm", booktitle = "Graphics Gems III", pages = "301-306", publisher = "Academic Press", address = "San Diego", year = "1992", who = "Havran Vlastimil: RT-0126", } @Unpublished{Subramanian91a, author = "K.R. Subramanian and D.S. Fussel", title = "Applying Space Subdivision Techniques to Volume Rendering", pages = 9, institution = "The University of Texas at Austin", year = 1991, note = "from WWW", who = "Havran Vlastimil: RT-0125", } @TechReport{Subramanian92a, author = "K.R. Subramanian and D.S. Fussel", title = "A Search Structure based on K-d Trees for Efficient Ray Tracing", pages = 39, institution = "The University of Texas at Austin", year = 1992, number = "Tx 78712-1188", who = "Havran Vlastimil: RT-0124", } @TechReport{Subramanian90a, author = "K.R. Subramanian and D.S. Fussel", title = "Factors Affecting Performance of Ray Tracing Hierarchies", pages = 27, institution = "The University of Texas at Austin", year = 1990, month = jul, number = "Tx 78712", who = "Havran Vlastimil: RT-0123", } @Unpublished{Duc97a, author = "N.C. Duc", title = "An exploration of coherence-based acceleration methods using the ray tracing kernel G/GX", year = 1997, month = mar, note = "from WWW", who = "Havran Vlastimil: RT-0122", } @InProceedings{Groeller93a, author = "E. Groeller", title = "Oct-tracing animation sequences", pages = "96--101", booktitle = "Summer school in computer graphics in Bratislava (SCCG93)", year = "1993", month = jun, keywords = "ray tracing", who = "Havran Vlastimil: RT-0121", } @InProceedings{Martinka94, author = "J. Martinka", title = "Pouzitie octree struktury na urychlenie metody ray tracing", booktitle = "Winter School of Computer Graphics 1994", year = "1994", month = "feb", pages = "106--112", note = "held at University of West Bohemia, Plzen, Czech Republic, February 1994", who = "Havran Vlastimil: RT-0120", } @InProceedings{Kolingerova92, author = "I. Kolingerova", title = "Vyuziti dualniho prostoru pro metodu sledovani paprsku", booktitle = "Winter School of Computer Graphics 1992", year = "1992", month = "feb", pages = "66--80", note = "held at University of West Bohemia, Plzen, Czech Republic, February 1992", who = "Havran Vlastimil: RT-0119", } @Article{Arvo88a, author="J. Arvo", title="Linear-time Voxel Walking for Octrees", journal="Ray Tracing News (available at htpp://www.acm.org/tog/resources/RTNew s/html/rtnews2d.html)", year="1988", editor = "Eric Haines", volume="1", number="5", pages="", owner = "Havran Vlastimil: RT-0118", } @InProceedings{Sramek92a, author = "M. \v{S}r\'{a}mek", title = "Ray tracing volume data with subvoxel precision", booktitle = "Winter School of Computer Graphics 1992", year = "1992", month = feb, pages = "47--65", note = "held at University of West Bohemia, Plzen, Czech Republic, February 1992", who = "Havran Vlastimil: RT-0117", } @Unpublished{Schregle96a, author = "Roland Schregle", title = "t\_{}DistLight A Distributed Light Source Class for the Minimal Ray Tracer", year = 1996, month = sep, note = "from WWW", who = "Havran Vlastimil: RT-0116", } @InProceedings{Stuerzlinger94a, author = "Wolfgang Stuerzlinger and R.F. Tobler", title = "Two Optimization Methods for Raytracing", pages = "104--107", booktitle = "Summer school in computer graphics in Bratislava (SCCG94)", year = "1994", month = jun, keywords = "ray tracing", who = "Havran Vlastimil: RT-0115", } @Misc{Qual96a, author = "Matthew Quail", title = "Space Time Ray Tracing using Ray Classification", howpublished = "Bachelor thesis", year = "1996", month = nov, who = "Havran Vlastimil: RT-0114", } @InProceedings{Stuerzlinger96a, author = "Wolfgang Stuerzlinger", title = "Bounding Volume Construction using Point Clouds", pages = "239--246", booktitle = "Summer school in computer graphics in Bratislava (SCCG96)", year = "1996", month = jun, keywords = "bounding volume, bounding volume hierarchy, ray tracing", who = "Havran Vlastimil: RT-0113", } @Unpublished{Smith95a, author = "Otto J.A. Smith", title = "Ray-Tracing with Affine Transforms", year = 1995, month = jan, note = "from WWW", who = "Havran Vlastimil: RT-0112", } @Unpublished{Cak96a, author = "S. Cak", title = "An Effective Rendering System for Visual Realism", year = 1996, month = dec, note = "from WWW", who = "Havran Vlastimil: RT-0111", } @MastersThesis{Duc96a, author = "N.C. Duc", title = "Adaptives Verfahren zur Beschleunigung der generativen 3D-Grafikberechnung", school = "Technical University Dresden", year = "1996", month = "july", note = "in German", who = "Havran Vlastimil: RT-0110", } @Unpublished{Fellner93b, author = "D.W. Fellner", title = "Extensible Image Synthesis", pages = "1--18", year = 1993, month = apr, note = "from WWW", anote = "similar to RT-0108", who = "Havran Vlastimil: RT-0109", } @Unpublished{Fellner93a, author = "D.W. Fellner", title = "Extensible Image Synthesis", pages = "1--14", year = 1993, month = apr, note = "from WWW", anote = "similar to RT-0109", who = "Havran Vlastimil: RT-0108", } @Unpublished{Aguado96, author = "F.A. Aguado and F. F. Perez and A. Formella", title = "Fast Ray Tracing for Microcellular and Indoor Environments", pages = "1--4", year = 1996, month = mar, note = "concerns radio waves", who = "Havran Vlastimil: RT-0107", } @TechReport{Teller96rep, author = "S. Teller and K. Bala and J. Dorsey", title = "Conservative Interpolants for Ray Tracing", pages = "1--13", institution = "MIT", year = 1996, month = apr, number = "MIT/LCS/TM-549", who = "Havran Vlastimil: RT-0106", } @InCollection{Woo90a, author = "Andrew Woo", editor = "Andrew S. Glassner", title = "Fast Ray-Box Intersection", booktitle = "Graphics Gems", pages = "395--396", publisher = "Academic Press", address = "San Diego", year = "1990", keywords = "efficiency", who = "Havran Vlastimil: RT-0105", } @InCollection{Woo90, author = "Andrew Woo", editor = "Andrew S. Glassner", title = "Fast Ray-Polygon Intersection", booktitle = "Graphics Gems", pages = "394", publisher = "Academic Press", address = "San Diego", year = "1990", keywords = "efficiency", note = "includes code", who = "Havran Vlastimil: RT-0104", } @InCollection{Haines91, author = "Eric Haines", editor = "James Arvo", title = "Fast Ray-Convex Polyhedron Intersection", booktitle = "Graphics Gems II", pages = "247--250", publisher = "Academic Press", address = "San Diego", year = "1991", keywords = "efficiency", note = "includes code", who = "Havran Vlastimil: RT-0103", } @InCollection{Ritter90, author = "Jack Ritter", editor = "Andrew S. Glassner", title = "A Simple Ray Rejection Test", booktitle = "Graphics Gems", pages = "385--386", publisher = "Academic Press", address = "San Diego", year = "1990", who = "Havran Vlastimil: RT-00102", } @InCollection{Cychosz92a, author = "Joseph M. Cychosz", editor = "David Kirk", title = "Use of Residency Masks and Object Space Partitioning to Eliminate Ray-Object Intersection Calculations", booktitle = "Graphics Gems III", pages = "284--287", publisher = "Academic Press", address = "San Diego", year = "1992", who = "Havran Vlastimil: RT-0101", } @InCollection{Haines91a, author = "Eric Haines", editor = "James Arvo", title = "Efficiency Improvements for Hierarchy Traversal", booktitle = "Graphics Gems II", pages = "267--273", publisher = "Academic Press", address = "San Diego", year = "1991", keywords = "efficiency", who = "Havran Vlastimil: RT-0100", } @InCollection{Pearce91, author = "Andrew Pearce", editor = "James Arvo", title = "A Recursive Shadow Voxel Cache for Ray Tracing", booktitle = "Graphics Gems II", pages = "273--274", publisher = "Academic Press", address = "San Diego", year = "1991", keywords = "efficiency", note = "includes code", who = "Havran Vlastimil: RT-0099", } @InCollection{Pearce91a, author = "Andrew Pearce", editor = "James Arvo", title = "Avoiding Incorrect Shadow Intersections for Ray Tracing", booktitle = "Graphics Gems II", pages = "275--276", publisher = "Academic Press", address = "San Diego", year = "1991", who = "Havran Vlastimil: RT-0098", } @InCollection{Voorhies91, author = "Douglas Voorhies and David Kirk", editor = "James Arvo", title = "Ray-Triangle Intersection Using Binary Recursive Subdivision", booktitle = "Graphics Gems II", pages = "257--263", publisher = "Academic Press", address = "San Diego", year = "1991", who = "Havran Vlastimil: RT-0097", } @InCollection{Kirk91, author = "David Kirk and James Arvo", editor = "James Arvo", title = "Improved Ray Tagging for Voxel-Based Ray Tracing", booktitle = "Graphics Gems II", pages = "264--266", publisher = "Academic Press", address = "San Diego", year = "1991", keywords = "efficiency", who = "Havran Vlastimil: RT-0096", } @InCollection{Cohen:1994:VTA, author = "Daniel Cohen", editor = "Paul Heckbert", booktitle = "Graphics Gems IV", title = "Voxel Traversal along a 3{D} Line", publisher = "Academic Press", address = "Boston", pages = "366--369", year = "1994", keywords = "digital line drawing, grid traversal, ray tracing, scan conversion", summary = "Visits all the voxels along a 3D line segment with integer endpoints, something like a 3D Bresenham's algorithm. This code could be modified to take endpoints with fixed point coordinates. Then the algorithm could be very useful for ray tracing, when a uniform grid is being used as a spatial data structure for optimization, or for volume rendering of grid data. Contains C code.", who = "Havran Vlastimil: RT-0095", } @InProceedings{GARGANTINI:1995:EEI, author = "Irene GARGANTINI and J. H. G. REDEKOP", title = "Evaluating Exact Intersections of an Octree with Full Rays using only Radix-Sort and Meet Operations", booktitle = "Compugraphics '95", pages = "278--284", year = "1995", month = dec, editor = "Harold P. Santo", note = "ISBN 972-8342-00-4", who = "Havran Vlastimil: RT-0094", } @InProceedings{Marton:1997:ACC, author = "L. {Szirmay-Kalos} and G. Marton", title = "On the Limitations of Worst--case Optimal Ray Shooting Algorithms", booktitle = "Winter School of Computer Graphics 1997", year = "1997", month = feb, pages = "562--571", note = "held at University of West Bohemia, Plzen, Czech Republic, 14-18 February 1997", who = "Havran Vlastimil: RT-0093", } @Article{strauss90a, author = "Paul S. Strauss", title = "A Realistic Lighting Model for Computer Animators", journal = "IEEE Computer Graphics and Applications", pages = "56--64", volume = "10", number = "6", month = nov, year = "1990", keywords = "modeling, lighting model, Torrance-Sparrow, Cook, Phong", annote = "Phong's illumination model is simple and widely used. However it is incomplete. Torrance-Sparrow and Cook's models produce results closer to the reality but its many parameters, often dependent between themselves, are difficult to tune to obtain desired results. Moreover inconsistencies can arise for given choices of parameters. Strauss introduces a reformulation of the standard illumination functions, trying to restrict the values of the parameters between 0 and 1 and to make them as independent as possible. This should make illumination easier for non-expert while an expert or someone desiring ``unrealistic'' effects could be penalized.", who = "Havran Vlastimil: RT-0092", } @Article{Zemcik:1995:OCT, author = "Pavel Zemcik and Alan Chalmers", title = "Optimised {CSG} Tree Evaluation for Space Subdivision", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "14", number = "2", pages = "139--146", month = jun, year = "1995", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Tue Mar 17 15:44:38 MST 1998", acknowledgement = ack-nhfb, affiliation = "Technical Univ of Brno", affiliationaddress = "Czech", classification = "721.1; 723.2; 723.5; 921; 921.5; C4260 (Computational geometry); C6120 (File organisation); C6130B (Graphics techniques)", corpsource = "Tech. Univ. of Brno, Czech Republic", journalabr = "Comput Graphics Forum", keywords = "Binary tree; Binary tree, Optimised CSG tree evaluation; Complex scenes; complex scenes; computational; computational geometry; Computational methods; Computational requirements; Computer graphics; computer graphics; Computer graphics; computer graphics; Computer images; Computer selection and evaluation; Constructive solid geometry; constructive solid geometry; Constructive solid geometry; constructive solid geometry; Data structures; Geometry; images; optimised CSG tree evaluation; Optimization; photorealistic; Photorealistic images; ray; Ray object intersection evaluations; Ray tracing; ray tracing; Ray tracing; Realistic computer images; realistic computer images; realistic images; Rendering; rendering; rendering (computer graphics); requirements; solid modelling; Space subdivision; space subdivision; Space subdivision; Status tree approach; status tree approach; structures; tracing; tree data", thesaurus = "Computational geometry; Ray tracing; Realistic images; Rendering [computer graphics]; Solid modelling; Tree data structures", treatment = "P Practical; T Theoretical or Mathematical", who = "Havran Vlastimil: RT-0091", } @Article{Gervautz:1992:CSA, author = "Michael Gervautz", title = "Consistent schemes for addressing surfaces when ray tracing transparent {CSG} objects", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "11", number = "4", pages = "203--211", month = oct, year = "1992", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Mon Apr 14 10:23:20 MDT 1997", acknowledgement = ack-nhfb, affiliation = "Technical Univ Vienna", affiliationaddress = "Vienna, Austria", classification = "723.1; 723.2; 741.1; 921.4; 931.2; C4260 (Computational geometry); C6130B (Graphics techniques)", corpsource = "Inst. for Comput. Graphics, Tech. Univ. Vienna, Austria", keywords = "Asymmetric CSG-operators; asymmetric CSG-operators; Classification (of information); classification scheme; Classification scheme; classification scheme; computational geometry; constructive solid geometry; Constructive Solid Geometry (CSG) modelling; CSG modelling; CSG trees; Data representation, Constructive solid geometry; geometrical optics; Geometry; Graphic primitives; Image processing; Light refraction; Material boundaries; material boundaries; material properties; Material properties; material properties; Mathematical models; Mathematical operators; objects; properties; ray tracing; Ray tracing; Refraction; refraction; Set theory; shading; Shading; shading; solid modelling; surface; Surface properties; Surfaces; Three dimensional computer graphics; Transparency; transparent CSG; Transparent CSG objects; Trees (mathematics); Unambiguous model; unambiguous model; Visualization", thesaurus = "Computational geometry; Geometrical optics; Solid modelling", treatment = "P Practical; T Theoretical or Mathematical", who = "Havran Vlastimil: RT-0090", } Article{Horvath:1992:RCB, author = "T. Horvath and G. Marton and P. Risztics and L. Szirmay-Kalos", title = "Ray coherence between a sphere and a convex polyhedron", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "11", number = "2", pages = "163--172", month = jun, year = "1992", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Mon Apr 14 10:23:20 MDT 1997", acknowledgement = ack-nhfb, classification = "C4240 (Programming and algorithm theory); C4260 (Computational geometry); C6130B (Graphics techniques)", corpsource = "Dept. of Process Control, Tech. Univ. of Budapest, Hungary", keywords = "computational complexity; computational geometry; computer; Convex polyhedron; convex polyhedron; graphics; ray; ray coherence theorems; Ray coherence theorems; Ray tracing algorithms; Sphere; sphere; tracing algorithms", thesaurus = "Computational complexity; Computational geometry; Computer graphics", treatment = "T Theoretical or Mathematical", who = "Havran Vlastimil: RT-0089", } @Article{Barequet:1996:BHR, author = "Gill Barequet and Bernard Chazelle and Leonidas J. Guibas and Joseph S. B. Mitchell and Ayellet Tal", title = "{BOXTREE}: {A} Hierarchical Representation for Surfaces in {3D}", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "15", number = "3", pages = "C387--C396, C484", month = sep, year = "1996", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Tue Mar 17 15:44:38 MST 1998", acknowledgement = ack-nhfb, affiliation = "Tel Aviv Univ", affiliationaddress = "Tel Aviv, Isr", affiliationaddress = "Isr", classification = "723.2; 723.5; 921.4; C4260 (Computational geometry); C6120 (File organisation); C6130B (Graphics techniques)", conference = "Proceedings of the 1996 17th Annual Conference and Exhibition of the European Association for Computer Graphics, EUROGRAPHICS'96", conflocation = "Poitiers, France; 26-30 Aug. 1996", conftitle = "European Association for Computer Graphics 17th Annual Conference and Exhibition. EUROGRAPHICS '96", corpsource = "Dept. of Comput. Sci., Tel Aviv Univ., Israel", journalabr = "Comput Graphics Forum", keywords = "Boxtree; Collision detection; Computational geometry; Data structures; Hierarchical systems; Octrees; Piecewise linear techniques; Ray shooting; Ray tracing; Surfaces; Three dimensional computer graphics", keywords = "3D representation; boxtree; BOXTREE; BSP trees; collision detection; Collision detection; computational geometry; Computational geometry; Data structures; data structures; hierarchical representation; Hierarchical systems; meshed surfaces; nested boxes; octrees; Octrees; Piecewise linear techniques; R-trees; Ray shooting; ray tracing; Ray tracing; ray tracing; surface fitting; Surfaces; Three dimensional computer graphics; three dimensional representation; tree; tree data structure; triangulated surfaces", meetingaddress = "Poitiers, Fr", meetingdate = "Aug 26--30 1996", meetingdate2 = "08/26--30/96", sponsor = "CNRS; ERCIM; BARCO; EDF; SUN; et al", sponsororg = "CNRS; BARCO; Electr. France; et al", treatment = "P Practical; T Theoretical or Mathematical", who = "Havran Vlastimil: RT-0088", } @InProceedings{ENDL:1995:OOR, author = "Robert ENDL", title = "An Object-Oriented Ray Tracing Architecture for the Analysis of Ray-Generators in Spatial Subdivisions", booktitle = "Compugraphics '95", pages = "268--277", year = "1995", month = dec, editor = "Harold P. Santo", note = "ISBN 972-8342-00-4", who = "Havran Vlastimil: RT-0087", } @InProceedings{Pharr:1997:RCS, author = "Matt Pharr and Craig Kolb and Reid Gershbein and Pat Hanrahan", title = "Rendering Complex Scenes with Memory-Coherent Ray Tracing", booktitle = "SIGGRAPH 97 Conference Proceedings", editor = "Turner Whitted", series = "Annual Conference Series", year = "1997", organization = "ACM SIGGRAPH", publisher = "Addison Wesley", month = aug, pages = "101--108", note = "ISBN 0-89791-896-7", keywords = "scene data management, caching, computation re-ordering, coherence", annote = "Simulating realistic lighting and rendering complex scenes are usually considered separate problems with incompatible solutions. Accurate lighting calculations are typically performed using ray tracing algorithms, which require that the entire scene database reside in memory to perform well. Conversely, most systems capable of rendering complex scenes use scan-conversion algorithms that access memory coherently, but are unable to incorporate sophisticated illumination. We have developed algorithms that use caching and lazy creation of texture and geometry to manage scene complexity. To improve cache performance, we increase locality of reference by dynamically reordering the rendering computation based on the contents of the cache. We have used these algorithms to compute images of scenes containing millions of primitives, while storing ten percent of the scene description in memory. Thus, a machine of a given memory capacity can render realistic scenes that are an order of magnitude more complex than was previously possible.", who = "Havran Vlastimil: RT-0086", } @InProceedings{kalra89a, author = "Devendra Kalra and Alan H. Barr", title = "Guaranteed Ray Intersections with Implicit Surfaces", pages = "297--306", booktitle = "SIGGRAPH '89 Proceedings", journal = "Computer Graphics (SIGGRAPH '89 Proceedings)", volume = "23", number = "3", year = "1989", month = jul, editor = "Jeffrey Lane", conference = "held in Boston, Massachusetts; 31 July -- 4 August 1989", keywords = "implicit surfaces, ray tracing, rendering, sampling, subdivision, Lipschitz constant, root finding", annote = "Automatic interval finding for implicit surface intersection \\ In this paper, we present a robust and mathematically sound ray-intersection algorithm for implicit surfaces. The algorithm is guaranteed to numerically find the nearest intersection of the surface with a ray, and is guaranteed not to miss fine features of the surface. It does not require fine tuning or human choice of interactive parameters. Instead, it requires two upper bounds: ``L'' that limits the net rate of change of the implicit surface function $f(x,y,z)$ and ``G'' that limits the rate of change of the gradient. An implicit surface with these rate limits is referred to as an ``LG-implicit surface.'' \\ Existing schemes to intersect a ray with an implicit surface have typically been guaranteed to work only for a limited set of implicit functions, such as quadric surfaces or polynomials, or else have been ad-hoc and have not been guaranteed to work. Our technique significanty extends the ability to intersect rays with implicit surfaces in a guaranteed fashion.", who = "Havran Vlastimil: RT-0085", } @Article{Woo:1993:ESC, author = "Andrew Woo", title = "Efficient shadow computations in ray tracing", journal = "IEEE Computer Graphics and Applications", volume = "13", number = "5", pages = "78--83", month = sep, year = "1993", coden = "ICGADZ", ISSN = "0272-1716", bibdate = "Fri Jan 5 07:58:42 MST 1996", abstract = "Two simple techniques speed up shadows in ray tracing. Both require little memory and easily extend to other types. One can also benefit radiosity- related computations.", acknowledgement = ack-nhfb, annote = "Two simple techniques speed up shadows in ray tracing. Both require little memory and easily extend to other ray types. One can also benefit radiosity-related computations.", who = "Havran Vlastimil: RT-0084", } @InProceedings{Milosmek:1994:AFV, author = "Milos Sramek", title = "An Algorithm for Fast Voxel Scene Traversal", booktitle = "Winter School of Computer Graphics 1994", year = "1994", month = jan, note = "held at University of West Bohemia, Plzen, Czech Republic, 19-20 January 1994", who = "Havran Vlastimil: RT-0083", } @InProceedings{rubin80a, author = "Steven M. Rubin and Turner Whitted", title = "A 3-Dimensional Representation for Fast Rendering of Complex Scenes", pages = "110--116", booktitle = "SIGGRAPH '80 Proceedings", journal = "Computer Graphics (SIGGRAPH '80 Proceedings)", volume = "14", number = "3", year = "1980", month = jul, keywords = "bounding volume, ray tracing cull, graphical data/base/structure representation, Methodologies, Techniques, Modeling scene, Algorithmic Aspects surface representation", annote = "hierarchical bounding boxes, used to speed up ray tracing and other algorithms \\ Hierarchical representations of 3-dimensional objects are both time and space efficient. They typically consist of trees whose branches represent bounding volumes and whose terminal nodes represent primitive object elements (usually polygons). This paper describes a method whereby the object space is represented entirely by a hierarchical data structure consisting of bounding volumes, with no other form of representation. This homogeneity allows the visible surface rendering to be performed simply and efficiently. \\ The bounding volumes selected for this algorithm are parallelepipeds oriented to minimize their sizes. With this representation, any surface can be rendered since in the limit the bounding volumes make up a point representation of the object. The advantage is that the visibility calculations consist only of a search through the data structure to determine the correspondence between terminal level bounding volumes and the current pixel. For ray tracing algorithms, this means that a simplified operation will produce the point of intersection of each ray with the bounding volumes. \\ Memory requirements are minimized by expanding or fetching lower levels of the hierarchy only when required. Because the viewing process has a single operation and primitive type, the software and hardware chosen to implement the search can be highly optimized for very fast execution.", who = "Havran Vlastimil: RT-0082", } @Article{Kuzmin:1994:RTS, author = "Y. P. Kuzmin", title = "Ray Traversal of Spatial Structures", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "13", number = "4", pages = "223--227", month = oct, year = "1994", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Mon Apr 14 10:23:20 MDT 1997", acknowledgement = ack-nhfb, classification = "C6130B (Graphics techniques)", corpsource = "Dept. of Math. and Mech., Moscow State Univ., Russia", keywords = "computer graphics; Efficient algorithm; efficient algorithm; error accumulation; Error accumulation; error accumulation; errors; hardware implementation; Hardware implementation; hardware implementation; hierarchical spatial; Hierarchical spatial structures; integer operations; Integer operations; Logical operations; logical operations; ray; ray casting; Ray casting; ray casting; ray tracing; Ray tracing acceleration; ray traversal; Ray traversal; Software implementation; software implementation; structures; tracing acceleration; uniform spatial structures; Uniform spatial structures", thesaurus = "Computer graphics; Errors; Ray tracing", treatment = "P Practical; T Theoretical or Mathematical", who = "Havran Vlastimil: RT-0081", } @Article{Akimoto:1991:PRT, author = "Takaaki Akimoto and Kenji Mase and Yasuhito Suenaga", title = "Pixel-selected ray tracing", journal = "IEEE Computer Graphics and Applications", volume = "11", number = "4", pages = "14--22", month = jul, year = "1991", coden = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", acknowledgement = ack-nhfb, affiliation = "NTT Corp, Kanagawa, Japan", classification = "723; 741", journalabr = "IEEE Comput Graphics Appl", keywords = "Computer Graphics; Image Processing --- Image Coding; Ray Tracing; ray tracing, acceleration; Three Dimensional Graphics", who = "Havran Vlastimil: RT-0080", } @Article{McNeill:1992:PSS, author = "M. D. J. McNeill and B. C. Shah and M.-P. Hebert and P. F. Lister and R. L. Grimsdale", title = "Performance of space subdivision techniques in ray tracing", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "11", number = "4", pages = "213--220", month = oct, year = "1992", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Mon Apr 14 10:23:20 MDT 1997", acknowledgement = ack-nhfb, affiliation = "Univ of Sussex", affiliationaddress = "Brighton, Engl", classification = "721.1; 722.4; 723.1; 723.2; 921.5; C4240P (Parallel programming and algorithm theory); C6120 (File organisation); C6130B (Graphics techniques)", corpsource = "Sch. of Eng., Sussex Univ., Brighton, UK", keywords = "algorithm; Algorithms; Computational complexity; computer graphics; Data structure; data structure; data structures; Data structures; dynamic; dynamic building; Dynamic building algorithm; Dynamic scenes; dynamic structure building; Dynamic structure building; dynamic structure building; Dynamic structure building algorithms; geometrical optics; Image parallelism performance; image parallelism performance; Image processing; Image quality; Image synthesis, Ray tracing; Optimization; parallel; parallel algorithms; Parallel processing systems; Performance; processing systems; ray tracing; Ray tracing; ray tracing; rendering; Rendering; rendering; scenes; Space subdivision algorithms; space subdivision algorithms; Three dimensional computer graphics", thesaurus = "Computer graphics; Data structures; Geometrical optics; Parallel algorithms", treatment = "P Practical; T Theoretical or Mathematical", who = "Havran Vlastimil: RT-0079", } @InProceedings{sequin89a, author = "Carlo H. Sequin and Eliot K. Smyrl", title = "Parameterized Ray Tracing", pages = "307--314", booktitle = "SIGGRAPH '89 Proceedings", journal = "Computer Graphics (SIGGRAPH '89 Proceedings)", volume = "23", number = "3", year = "1989", month = jul, editor = "Jeffrey Lane", conference = "held in Boston, Massachusetts; 31 July -- 4 August 1989", keywords = "ray tracing, rendering, parameterization, surface properties, runlength encoding, subexpression elimination, hashing", annote = "store ray tree data to allow quick material changes \\ The construction and refinement of a computer graphics scene is unacceptably slow when using ray tracing. We introduce a new technique to speed up the generation of successive ray traced images when the geometry of the scene remains constant and only the light source intensities and the surface properties need to be adjusted. When the scene is first traced, an expression parameterized in the color of all lights and the surface property coefficients of all objects is calculated and stored for each pixel. Redisplaying a scene with a new set of lights and colors then consists of substituting values for the corresponding parameters and re-evaluating the expressions for the pixels. This parameter updating and redisplay takes only a few seconds, as compared to the many minutes or hours required to ray trace the entire scene again, but it uses much more memory and disk space. With suitable expression sharing, however, these storage needs can be reduced to an acceptable level.", who = "Havran Vlastimil: RT-0078", } @InProceedings{hart89a, author = "John C. Hart and Daniel J. Sandin and Louis H. Kauffman", title = "Ray Tracing Deterministic 3-{D} Fractals", pages = "289--296", booktitle = "Computer Graphics (SIGGRAPH '89 Proceedings)", volume = "23", number = "3", year = "1989", month = jul, editor = "Jeffrey Lane", conference = "held in Boston, Massachusetts; 31 July -- 4 August 1989", keywords = "fractal", annote = "As shown in 1982, Julia sets of quadratic functions as well as many other deterministic fractals exist in spaces of higher dimensionality than the complex plane. Originally a boundary-tracking algorithm was used to view these structures but required a large amount of storage space to operate. By ray tracing these objects, the storage facilities of a graphics workstation frame buffer are sufficient. A short discussion of a specific set of 3-D deterministic fractals precedes a full description of a ray-tracing algorithm applied to these objects. A comparision with the boundary-tracing method and applications to other 3-D deterministic fractals are also included.", who = "Havran Vlastimil: RT-0077", } @InProceedings{Marton:1995:ACC, author = "G. Marton and L. {Szirmay-Kalos}", title = "On Average-case Complexity of Ray Tracing Algorithms", booktitle = "Winter School of Computer Graphics 1995", year = "1995", month = feb, note = "held at University of West Bohemia, Plzen, Czech Republic, 14-18 February 1995", who = "Havran Vlastimil: RT-0076", } @InProceedings{painter89a, author = "James Painter and Kenneth Sloan", title = "Antialiased Ray Tracing by Adaptive Progressive Refinement", pages = "281--288", booktitle = "Computer Graphics (SIGGRAPH '89 Proceedings)", journal = "Computer Graphics (SIGGRAPH '89 Proceedings)", volume = "23", number = "3", year = "1989", month = jul, editor = "Jeffrey Lane", conference = "held in Boston, Massachusetts; 31 July -- 4 August 1989", keywords = "adaptive sampling, antialiasing, filtering, progressive refinement, ray tracing", annote = "We describe an antialiasing system for ray tracing based on adaptive progressive refinement. The goals of the system are to produce high quality antialiased images at a modest average sample rate, and to refine the image progressively so that the image is available in a usable form early and is refined gradually toward the final result. \\ The method proceeds by adaptive stochastic sampling of the image plane, evaluation of the samples by ray tracing, and image reconstruction from the samples. Adaptive control of the sample generation process is driven by three basic goals: coverage of the image, location of features, and confidence in the values at a distinguished ``pixel level'' resolution. \\ A three-stage process of interpolating, filtering, and resampling is used to reconstruct a regular grid of display pixels. This reconstruction can be either batch or incremental.", who = "Havran Vlastimil: RT-0075", } @InProceedings{Foris:1996:RSL, author = "T. Foris and G. Marton and L. {Szirmay-Kalos}", title = "Ray Shooting in Logarithmic Time", booktitle = "Winter School of Computer Graphics 1996", year = "1996", month = feb, note = "held at University of West Bohemia, Plzen, Czech Republic, 12-16 February 1996", who = "Havran Vlastimil: RT-0074", } @Article{sweeney86a, author = "Michael Sweeney and Richard H. Bartels", title = "Ray Tracing Free-Form {B}-Spline Surfaces", pages = "41", journal = "IEEE Computer Graphics and Applications", volume = "6", number = "2", year = "1986", month = feb, annote = "We present a method for using ray tracing to render spline surfaces--one that is suitable for any object generated from control vertices via tensor-product B-splines. The method derives from Kajiya's work on ray tracing procedurally defined surfaces and make use of two preprocessing steps. One involves the control-vertex refinement recurrences due to Riesenfeld {\em et al}.\ and the second generates a tree of nested bounding boxes. Intersection testing involves running Kajiya's algorithm on the tree, followed by two or three (on the average) iterations of Newton's method.", who = "Havran Vlastimil: RT-0073", } @InProceedings{Pharr:1996:GCR, author = "Matt Pharr and Pat Hanrahan", title = "Geometry Caching for Ray-Tracing Displacement Maps", booktitle = "Eurographics Rendering Workshop 1996", editor = "Xavier Pueyo and Peter Schr{\"{o}}der", year = "1996", organization = "Eurographics", publisher = "Springer Wein", address = "New York City, NY", month = jun, pages = "31--40", note = "ISBN 3-211-82883-4", annote = "We present a technique for rendering displacement mapped geometry in a ray-tracing renderer. Displacement mapping is an important technique for adding detail to surface geometry in rendering systems. It allows complex geometric variation to be added to simpler geometry, without the cost in geometric complexity of completely describing the nuances of the geometry at modeling time and with the advantage that the detail can be added adaptively at rendering time. The cost of displacement mapping is geometric complexity. Renderers that provide it must be able to efficiently render scenes that have effectively millions of geometric primitives. Scan-line renderers process primitives one at a time, so this complexity doesn't tax them, but traditional ray-tracing algorithms require random access to the entire scene database, so any part of the scene geometry may need to be available at any point during rendering. If the displaced geometry is fully instantiated in memory, it is straightforward to intersect rays with it, but displacement mapping has not yet been practical in ray-tracers due to the memory cost of holding this much geometry. We introduce the use of a geometry cache in order to handle the large amounts of geometry created by displacement mapping. By caching a subset of the geometry created and rendering the image in a coherent manner, we are able to take advantage of the fact that the rays spawned by traditional ray-tracing algorithms are spatially coherent. Using our algorithm, we have efficiently rendered highly complex scenes while using a limited amount of memory.", who = "Havran Vlastimil: RT-0072", } @Article{Musgrave:1990:NRT, author = "F. Kenton Musgrave", title = "A Note on Ray Tracing Mirages", journal = "IEEE Computer Graphics and Applications", volume = "10", number = "6", pages = "10--12", month = nov, year = "1990", coden = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", acknowledgement = ack-nhfb, affiliation = "Yale Univ, New Haven, CT, USA", annote = "Discuss Berger's [berger90a] technique to render mirages, stressing mirages come more from internal interreflection than refraction.", classification = "723; 741", journalabr = "IEEE Comput Graphics Appl", keywords = "Bending Agent; Computer Graphics; Dispersive Ray Tracing; Image Processing; Light --- Reflection; Mirage Formation; mirages, internal reflection; Optics; Ray Tracing Mirages; Total Internal Reflection", who = "Havran Vlastimil: RT-0071", } @Article{Berger:1990:RTM, author = "Marc Berger and Terry Trout and Nancy Levit", title = "Ray Tracing Mirages", journal = "IEEE Computer Graphics and Applications", volume = "10", number = "3", pages = "36--41", month = may, year = "1990", coden = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", acknowledgement = ack-nhfb, affiliation = "Univ of Adelaide, Adelaide, SA, Aust", annote = "Ray tracing has been used extensively to produce realistic images. Traditional algorithms simulate various optical phenomena, including reflections, refractions, and shadows. With all of these the direction of the ray changes only when it intersects an object. Atmospheric variations, however, can cause light rays to bend, thereby changing their direction at any time. Mirages are just one possible visual effect of these bent rays. We generate mirages by sending rays through an object with multiple air layers having different refractive indices. As a ray enters this virtual object, it strikes several air layers and causes repeated bending of the ray, which results in the mirage effect.", classification = "723; 741", journalabr = "IEEE Comput Graphics Appl", keywords = "Color; Computer Generated Images; Computer Graphics; Image Processing --- Image Analysis; Mirages; ray tracing; Ray Tracing", who = "Havran Vlastimil: RT-0070", } @Article{Maurel:1993:RT, author = "H. Maurel and Y. Duthen and R. Caubet", title = "A {4D} ray tracing", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "12", number = "3", pages = "C285--C294", month = "????", year = "1993", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Mon Apr 14 10:23:20 MDT 1997", acknowledgement = ack-nhfb, classification = "C4260 (Computational geometry); C6130B (Graphics techniques)", conflocation = "Barcelona, Spain; 6-10 Sept. 1993", conftitle = "European Association for Computer Graphics 14th Annual Conference and Exhibition. EUROGRAPHICS '93", corpsource = "Inst. de Recherche en Inf. de Toulouse, Univ. Paul Sabatier, France", keywords = "4D ray tracing; Animation sequences; animation sequences; computer animation; graphics); illumination calculations; Illumination calculations; illumination calculations; intersection; Intersection; optical event; Optical event; optical event; ray tracing; rendering (computer; temporal coherence; Temporal coherence", thesaurus = "Computer animation; Ray tracing; Rendering [computer graphics]", treatment = "P Practical", who = "Havran Vlastimil: RT-0069", } @PhDThesis{Simiakakis95, author="G. Simiakakis", title ="Accelerating RayTracing with Directional Subdivision and Parallel Processing", school = "University of East Anglia", year = "1995", month = "october", note = "available at ftp://ftp.sys.uea.ac.uk/pub/ah/G.Simiakakis\_PhD.ps", who = "Havran Vlastimil: RT-0068", } @InProceedings{Cazals97, author="F. Cazals and C. Puech", title="Bucket-like space partitioning data-structures with applications to ray-tracing", booktitle="13th ACM Symposium on Computational Geometry", address="Nice", year="1997", pages="To Appear", who = "Havran Vlastimil: RT-0067", } @InCollection{Jansen:1986:DSR, author = "Frederik W. Jansen", editor = "L. R. A. Kessener and F. J. Peters and M. L. P. van Lierop", title = "Data Structures for Ray Tracing", booktitle = "Data Structures for Raster Graphics", pages = "57--73", publisher = "Springer-Verlag", address = "New York", year = "1986", keywords = "efficiency, CSG, BSP tree, data structures", note = "Eurographic Seminar", anote = "overview of published algorithms for ray tracing using spatial subdivision", where = " MAJI V STK !!!!!", who = "Havran Vlastimil: RT-0066", } @InProceedings{Semwal97, author= "Semwal S and Kvarnstrom H", title = "Directional Safe Zones \& Dual Extent Algorithms for Efficient Grid Traversal", booktitle = "Graphics Interface 97", year = "1997", pages = "to appear", note = "University of Colorado", who = "Havran Vlastimil: RT-0065", } @Article{Levoy:1990:HRT, author = "Marc Levoy", title = "A Hybrid Ray Tracer for Rendering Polygon and Volume Data", journal = "IEEE Computer Graphics and Applications", volume = "10", number = "2", pages = "33--40", month = mar, year = "1990", coden = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", acknowledgement = ack-nhfb, affiliation = "Univ of North Carolina, Dep of Comput Sci, Chapel Hill, NC, USA", annote = "Volume rendering is a technique for visualizing sampled functions of three spatial dimensions by computing 2D projections of a colored semitransparent volume. In this article I address the problem of extending volume rendering to handle polygonally defined objects. The solution I propose is a hybrid ray-tracing algorithm. Rays are simultaneously cast through a set of polygons and a volume data array. Samples of each are drawn at equally spaced intervals along the rays, and the resulting colors and opacities are composited together in depth-sorted order. To avoid aliasing of polygonal edges at modest computational expense, I use a form of selective supersampling. To avoid errors in visibility at polygon-volume intersections, I give special treatment to volume samples lying immediately in front of and behind polygons. I will evaluate the cost, image quality, and versatility of the algorithm using data from 3D medical imaging applications.", classification = "461; 723", journalabr = "IEEE Comput Graphics Appl", keywords = "Computer Graphics; Computer Programming --- Algorithms; Medical Applications; Polygon Data; Ray Tracing; Sampling; Selective Supersampling; Volume Rendering; volume rendering", who = "Havran Vlastimil: RT-0064", } @Article{Gargantini:1993:RTO, author = "I. Gargantini and H. H. Atkinson", title = "Ray tracing an octree: numerical evaluation of the first intersection", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "12", number = "4", pages = "199--210", month = oct, year = "1993", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Mon Apr 14 10:23:20 MDT 1997", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C4260 (Computational geometry); C6120 (File organisation); C6130B (Graphics techniques)", corpsource = "Dept. of Comput. Sci., Univ. of Western Ontario, London, Ont., Canada", keywords = "based region octree; Bisecting planes; bisecting planes; computational geometry; data structures; directed graphs; directed semi-infinite straight-line; Directed semi-infinite straight-line; first; First intersection; Floating-point arithmetic; floating-point arithmetic; intersection; local ordering; Local ordering; numerical accuracy; Numerical accuracy; numerical accuracy; numerical evaluation; Numerical evaluation; numerical evaluation; octree; Octree; octree; pointer-; Pointer-based region octree; ray tracing; Ray tracing; tree", thesaurus = "Computational geometry; Directed graphs; Ray tracing; Tree data structures", treatment = "T Theoretical or Mathematical", who = "Havran Vlastimil: RT-0063", } @Article{charney90a, author = "Mark J. Charney and Isaac D. Scherson", title = "Efficient Traversal of Well-Behaved Hierarchicial Trees of Extents for Ray-Tracing Complex Scenes", journal = "The Visual Computer", pages = "167--178", volume = "6", number = "3", month = jun, year = "1990", keywords = "ray tracing, hierarchy, bounding volumes, tree of extents, hte, hidden surface removal, traversal", annote = "Traversal of hierarchical trees of extents (HTE) requires computation of intersections between rays and bounding volumes whose faces are parallel to the cartesian axes. By redefining the HTE so that non-overlapping bounding volumes are generated, a well-behaved data structure is obtained in which `geometrical coherence'' is applied to speed up its traversal. We distinguish two types of bounding volumes: {\em internal} boxes contain the ray's origin while {\em external} bounding volumes do not contain the ray's origin. To traverse the HTE, we look first to polygons in the internal bounding volumes and external boxes are dealt with only when no ray-polygon intersection is found in internal nodes. As external nodes in the HTE define pruned subtrees of external bounding volumes, geometrical characteristics of the boxes are exploited for HTE traversal. A coding scheme allows a 6-bit code to determine which faces of a bounding volume need to be tested for intersection. Also, our well-behaved HTE allows for reuse of intersection points at lower levels of the tree.", who = "Havran Vlastimil: RT-0062", } @Article{Cohen:1994, author = "D.Cohen and Z.Sheffer", title = "Proximity clouds - an acceleration technique for 3D grid traversal", journal = "The Visual Computer", volume = "11", pages = "27-38", year = "1994", keywords = "ray tracing, space subdivision, distance transformation, distance map, grid traversal", who = "Havran Vlastimil: RT-0061", } @Article{Kok:1994:ECR, author = "Arjan J. F. Kok and Frederik W. Jansen and C. Woodward", title = "Efficient, Complete Radiosity Ray Tracing Using a Shadow-Coherence Method", journal = "The Visual Computer", volume = "10", pages = "19--33", year = "1993", month = "oct", bibsource = "sig-11-1993", keywords = "rendering, radiosity, ray tracing, source selection, shadow coherence", who = "Havran Vlastimil: RT-0060", } @Article{wyvill86d, author = "G. Wyvill and T. L. Kunii and Y. Shirai", title = "Space Division for Ray Tracing in {CSG} (Constructive Solid Geometry)", pages = "28--34", journal = "IEEE Computer Graphics and Applications", volume = "6", number = "4", year = "1986", month = apr, keywords = "I35 CSG, I35 trees (mathematics), I37 ray tracing", annote = "A system of Constructive Solid Geometry (CSG) enables an engineering designer to compose three-dimensional shapes by combining simpler ones. Definitions of such objects are represented by tree structures or direct acyclic graphs. \\ Most existing systems convert this representation to a more conventional boundary representation of the solids in order to render pictures from the model. More recently, a number of systems have been described that render the pictures directly from the CSG structure. We describe such a system. We render a scene by ray tracing from a directed acyclic graph. This process is made efficient for large models by using an adaptive method of space division to reduce the number of intersection calculations needed.", who = "Havran Vlastimil: RT-0059", } @Article{Kok:1992:ASA, author = "Arjan J. F. Kok and Frederik W. Jansen", title = "Adaptive Sampling of Area Light Sources in Ray Tracing Including Diffuse Interreflection", journal = "Computer Graphics Forum (Eurographics '92)", volume = "11", number = "3", address = "Cambridge, UK", pages = "289--298", month = sep, year = "1992", bibsource = "sig-11-1994", who = "Havran Vlastimil: RT-0058", } @Article{Haines87, author = "Eric A. Haines", title = "A Proposal for Standard Graphics Environments", journal = "IEEE Computer Graphics and Applications", volume = "7", number = "11", pages = "3--5", month = nov, year = "1987", keywords = "benchmark", note = "also in SIGGRAPH '87, '88, '89 Introduction to Ray Tracing course notes, code available via FTP from princeton.edu:/pub/Graphics", anote = "renderer benchmarking environments and how to obtain them", who = "Havran Vlastimil: RT-0057", } @Article{glassner88a, author = "Andrew S. Glassner", title = "Spacetime ray tracing for animation", journal = "IEEE Computer Graphics and Applications", pages = "60--70", volume = "8", number = "2", month = mar, year = "1988", keywords = "animation, ray tracing cull", annote = "We are presenting techniques for the efficient ray tracing of animated scenes. These techniques are based on two central concepts: spacetime ray tracing, and a hybrid adaptive subdivision/bounding volume technique for generating efficient, nonoverlapping hierarchies of bounding volumes. \\ In spacetime ray tracing, instead of rendering dynamically moving objects in 3D space, we render static objects in 4D spacetime. To support spacetime ray tracing, we use 4-dimensional analogues to familiar 3-dimensional ray-tracing techniques. \\ The new bounding volume hierarchy combines elements of adaptive space subdivision and bounding volume techniques. The quality of the hierarchy and its nonoverlapping character make it an improvement over previous algorithms, because both attributes reduce the number of ray/object intersections that must be computed. These savings are amplified in animation because of the much higher cost of computing ray/object intersections for motion-blurred animation. \\ We show it is possible to ray trace large animations more quickly with spacetime ray tracing using this hierarchy than with straightforward frame-by-frame rendering.", who = "Havran Vlastimil: RT-0056", } @Article{Elber:1997:RT, author = "Gershon Elber and {Jung-Ju} Choi and {Myung-Soo} Kim", title = "Ruled Tracing", journal = "The Visual Computer", year = "1997", volume = "13", number = "2", pages = "78--94", publisher = "Springer-Verlag", note = "ISSN 0178-2789", annote = "The traditional ray-tracing technique based on a ray-surface intersection is reduced to a ruled or developable surface-surface intersection problem. That enables direct freeform surface rendering. By exploiting the spatial coherence gained in the ruled/developable surface-tracing approach presented, the emulation of shadows, specular reflections, and/or refractions in a freeform surface environment can all be implemented efficiently. The approach provides a direct freeform surface-rendering alternative to ray tracing. An implementation of a direct freeform surface renderer that emulates shadows as well as specular reflections is discussed. This renderer processes isoparametric curves as its basic building block, eliminating the need for polygonal approximation.", keywords = "Ray tracing, light wavefronts, direct freeform surface rendering, shadow computation, reflection/refraction", who = "Havran Vlastimil: RT-0055", } @Article{Cazals:1995:FCH, author = "F. Cazals and G. Drettakis and C. Puech", title = "Filtering, Clustering and Hierarchy Construction: {A} New Solution for Ray-Tracing Complex Scenes", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "14", number = "3", pages = "C/371--382", year = "1995", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Fri Sep 13 06:22:32 MDT 1996", acknowledgement = ack-nhfb, classification = "C6130B (Graphics techniques); C6120 (File organisation); C6115 (Programming support)", keywords = "Hierarchy construction; Ray tracing; Complex scenes; Data structures; Input objects; Clustering step; Uniform grids; Memory requirements; Memory usage; Computational efficiency; HUG", thesaurus = "Automatic programming; Data structures; Ray tracing", who = "Havran Vlastimil: RT-0054", } @Article{Simiakakis:1994:FAS, author= "G. Simiakakis and A. M. Day", title= "Five-dimensional Adaptive Subdivision for Ray Tracing", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "13", number = "2", pages = "133--140", month = jun, year = "1994", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Fri Sep 13 06:30:31 MDT 1996", acknowledgement = ack-nhfb, classification = "C6130B (Graphics techniques)", keywords = "Five-dimensional adaptive subdivision; Ray tracing; Directional subdivision method; Memory saving scheme", pubcountry = "UK", thesaurus = "Computer graphics; Ray tracing", who = "Havran Vlastimil: RT-0053", } @InCollection{Voorhies90, author = "Douglas Voorhies", editor = "James Arvo", title = "Space-Filling Curves and a Measure of Coherence", booktitle = "Graphics Gems", pages = "257--262", publisher = "Academic Press", address = "San Diego", year = "1990", who = "Havran Vlastimil: RT-0052", } @Article{Yagel:1992:DRT, author = "Roni Yagel and Daniel Cohen and Arie Kaufman", title = "Discrete Ray Tracing", journal = "IEEE Computer Graphics and Applications", volume = "12", number = "5", pages = "19--??", month = sep, year = "1992", coden = "ICGADZ", ISSN = "0272-1716", bibdate = "Fri Jan 5 07:58:42 MST 1996", abstract = "This ray tracing method, called 3D raster ray tracing, is insensitive to a scene's complexity and thus substantially improves computational speed over existing algorithms.", acknowledgement = ack-nhfb, who = "Havran Vlastimil: RT-0051", } InProceedings{Stolte:1995:DRT, author = "N. Stolte and R. Caubet", title = "Discrete Ray Tracing High Resolution {3D} Grids", booktitle = "Winter School of Computer Graphics 1995", year = "1995", month = feb, note = "held at University of West Bohemia, Plzen, Czech Republic, 14-18 February 1995", who = "Havran Vlastimil: RT-0050", } @TechReport{EVL-1996-84, author = "S. Campagna and Ph. Slusallek", title = "Rendering of Quadric Surfaces According to the RenderMan-Standard", number = "5", institution = "Universit{\"a}t Erlangen-N{\"u}rnberg", year = "1996", abstract = "Rendering of high-quality pictures has two basic requirements: a renderer and a modeler. In practice, only the modeler has to comunicate with the renderer. Usually this is done by a specified file-format. Each renderer capable of that format has to produce pictures with exactly the desired surfaces, e.g. compared to a reference-platform. One popular and powerful format is the RenderMan Interface Bytestream Protocol by Pixar. Unfortunately, its specification is ambiguous in some cases. This paper clarifies the usage especially of the geometric primitives according to the RenderMan-Interface.", postscript-url = "ftp://faui90.informatik.uni-erlangen.de/pub/Publications/1996/TR.1996.5.ps.gz", postscript-url-md5 = "0ad1de6e9d65add7b740cfff92a03238", evlib-url = "http://infovis.zib.de:8000/Dienst/UI/2.0/Describe/evl.surfacerendering%2FEVL-1996-83", evlib-revision = "1st", who = "Havran Vlastimil: RT-0049", } @TechReport{EVL-1996-83, author = "S. Campagna and W. Heidrich and Ph. Slusallek", title = "Rendering of Geometric Primitives According to the RenderMan-Standard", number = "5", institution = "Universit{\"a}t Erlangen-N{\"u}rnberg", year = "1996", abstract = "Rendering of high-quality pictures has two basic requirements: a renderer and a modeler. In practice, only the modeler has to comunicate with the renderer. Usually this is done by a specified file-format. Each renderer capable of that format has to produce pictures with exactly the desired surfaces, e.g. compared to a reference-platform. One popular and powerful format is the RenderMan Interface Bytestream Protocol by Pixar. Unfortunately, its specification is ambiguous in some cases. This paper clarifies the usage especially of the geometric primitives according to the RenderMan-Interface.", postscript-url = "ftp://faui90.informatik.uni-erlangen.de/pub/Publications/1996/TR.1996.5.ps.gz", postscript-url-md5 = "0ad1de6e9d65add7b740cfff92a03238", evlib-url = "http://infovis.zib.de:8000/Dienst/UI/2.0/Describe/evl.surfacerendering%2FEVL-1996-83", evlib-revision = "1st", who = "Havran Vlastimil: RT-0048", } @InProceedings{Haines94, author = "Eric A. Haines and John R. Wallace", editor = "P. Brunet and F. W. Jansen", title = "Shaft Culling for Efficient Ray-Traced Radiosity", booktitle = "Photorealistic Rendering in Computer Graphics (Proceedings of the Second Eurographics Workshop on Rendering)", publisher = "Springer-Verlag", address = "New York, NY", year = "1994", keywords = "ray tracing", note = "also available via FTP from princeton.edu:/pub/Graphics/Papers", anote = "also in ACM SIGGRAPH '91 Course Notes - Frontiers in Rendering", who = "Havran Vlastimil: RT-0047", } @TechReport{Loofbourrow93, author = "Nathan Loofbourrow", title = "Optimizing ray tracing with visual coherence", institution = "Carnegie-Mellon University, Department of Computer Science", number = "CMU-CS-93-209", year = "1993", keywords = "adaptive sampling, nonuniform sampling, antialiasing, filtering, progressive refinement", who = "Havran Vlastimil: RT-0046", } @InProceedings{gunter96, author = "Gunter Raidl and Wilhelm Barth", title = "Fast Adaptive Previewing by Ray Tracing", pages = "(do not know)", booktitle = "Summer school in computer graphics in Bratislava (SCCG96)", year = "1996", month = jun, keywords = "ray tracing, previewing", who = "Havran Vlastimil: RT-0045", } @Article{MacDonald90, author = "J. David MacDonald and Kellogg S. Booth", title = "Heuristics for Ray Tracing Using Space Subdivision", journal = "Visual Computer", pages = "153--65", publisher = "Springer Verlag", year = "1990", volume = "6", number = "6", who = "Havran Vlastimil: RT-0044", } @InCollection{Sung92, author = "Kelvin Sung and Peter Shirley", editor = "David Kirk", title = "Ray Tracing with the {BSP} Tree", booktitle = "Graphics Gems III", pages = "271--274", publisher = "Academic Press", address = "San Diego", year = "1992", keywords = "efficiency, BSP tree, octree", note = "includes code", who = "Havran Vlastimil: RT-0043", } @Article{Whang:1995:ORA, author = "K. Y. Whang and J. W. Song and J. W. Chang and J. Y. Kim and W. S. Cho and C. M. Park and I. Y. Song", title = "{Octree-R}: an adaptive octree for efficient ray tracing", journal = "IEEE Transactions on Visualization and Computer Graphics", year = "1995", volume = "1", number = "4", pages = "343--349", month = dec, note = "ISSN 1077-2626", who = "Havran Vlastimil: RT-0042", } @PhdThesis{Thompson:1991:RTA, author = "Karl Kelvin Thompson", title = "Ray tracing with amalgams", month = may, year = "1991", type = "Ph.D. Thesis", school = "University of Texas at Austin", annote = "Supervisors: Alan Bovik and Donald Fussell; Traditional ray tracing databases that use bounding volumes attach only geometric properties (e.g. position, orientation, size) to each bounding volume. By also associating shading properties (e.g. color, translucency, reflectance) with each bounding volume, the database can become a multi-resolution database - a database that represents objects at different levels of detail. Specifically, the bounding region itself may be rendered to coarsely represent the objects inside it. With a minor extension to the traditional ray tracing algorithm, a ray tracing renderer can traverse such a database with fewer intersection tests per ray, improving antialiasing, and (arguably) better asymptotic time complexity. The enhanced database and algorithm are particularly suited to scenes containing a large number of primitives at a wide range of scales.", who = "Havran Vlastimil: RT-0041", } @Article{cleary88a, author = "John G. Cleary and Geoff Wyvill", title = "Analysis of an algorithm for fast ray tracing using uniform space subdivision", journal = "The Visual Computer", pages = "65--83", volume = "4", number = "2", month = jul, year = "1988", keywords = "rendering", annote = "Ray tracing is becoming popular as the best method of rendering high quality images from three dimensional models. Unfortunately, the computational cost is high. Recently, a number of authors have reported on ways to speed up this process by means of space subdivision which is used to minimize the number of intersection calculations. We describe such an algorithm together with an analysis of the factors which affect its performance. The critical operation of skipping an empty space subdivision can be done very quickly, using only integer addition and comparison. A theoretical analysis of the algorithm is developed. It shows how the space and time requirements vary with the number of objects in the scene.", who = "Havran Vlastimil: RT-0040", } @InProceedings{Arvo86-BRT, author = "James R. Arvo", month = aug, year = "1986", title = "Backward {Ray} {Tracing}", booktitle = "ACM SIGGRAPH '86 Course Notes - Developments in Ray Tracing", volume = "12", keywords = "light tracing", comments = "also appeared in ACM SIGGRAPH '89 Course Notes - Radiosity", who = "Havran Vlastimil: RT-0039", } @Article{Chuang:1995:NSS, author = "Jung-Hong Chuang and Weun-Jier Hwang", title = "A new space subdivision for ray tracing {CSG} solids", journal = "IEEE Computer Graphics and Applications", volume = "15", number = "6", pages = "56--62", month = nov, year = "1995", coden = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", acknowledgement = ack-nhfb, affiliation = "Natl Chiao Tung Univ", affiliationaddress = "Hsinchu, Taiwan", classification = "721.1; 722.2; 723.2; 723.5; 921.4", journalabr = "IEEE Comput Graphics Appl", keywords = "Algorithms; Computational complexity; Computational methods; Computer graphics; Computer simulation; Constructive solid geometry; Heuristic methods; Image processing; Ray tracing; Space subdivision; Trees (mathematics)", who = "Havran Vlastimil: RT-0038", } @Article{wolff90a, author = "Lawrence B. Wolff and David J. Kurlander", title = "Ray Tracing with Polarization Parameters", journal = "IEEE Computer Graphics and Applications", pages = "44--55", volume = "10", number = "6", month = nov, year = "1990", keywords = "ray tracing, lighting model, Torrance-Sparrow, Fresnel, polarization", annote = "Implement a polarization scheme for the reflection off surfaces with the Torrance-Sparrow illumination model. They use a technique suggested by Emil Wolf, a 2x2 matrix that indicates the polarization state of the wavelength. \\ We demonstrate that incorporating polarization parameters into the lighting model can enhance the physical realism of images rendered with a ray tracer. Polarization effects can be importantin certain scenes, and the difference in rendering even simple scenes with and without proper treatment of polarization can be rather striking. All light waves possess a state of polarization, which changes almost every time light reflects off a material surface. A single reflection partially polarizes and may even completely polarize previously unpolarized light. Polarization influences the rendering of a scene because the reflected radiant intensity depends largely on the incident light wave's polarization state. \\ We have incorporated Emil Wolf's coherence matrix formalism for polarization into the Torrance-Sparrow reflectance model. This combination enables elegant quantitative derivations of the altered polarization state of light upon reflection in a ray tracer. Comparisons of identicala scenes rendered with a conventional ray tracer and our ray tracer. Incorporating a polarization model show that our method renders specular interobject reflections more accurately with respect to reflected radiance and color.", who = "Havran Vlastimil: RT-0037", } @Article{Endl:1994:CRU, author = "R. Endl and M. Sommer", title = "Classification of ray-generators in uniform subdivisions and octrees for ray tracing", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "13", number = "1", pages = "3--19", month = mar, year = "1994", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Fri Sep 13 06:30:31 MDT 1996", acknowledgement = ack-nhfb, classification = "C6130B (Graphics techniques); C6120 (File organisation); C6180 (User interfaces)", keywords = "Ray-generator classification; Uniform subdivisions; Octrees; Ray tracing; Spatial subdivisions; Ray-object intersections; Ray-cell sequence generation; X-ray-generators; Global time measurements; Random rays; Ray cell initialization; Ray cell determination", pubcountry = "UK", thesaurus = "Computer graphics; Ray tracing; Tree data structures", who = "Havran Vlastimil: RT-0036", } @Article{goldsmith87a, author = "Jeffrey Goldsmith and John Salmon", title = "Automatic Creation of Object Hierarchies for Ray Tracing", pages = "14--20", journal = "IEEE Computer Graphics and Applications", volume = "7", number = "5", year = "1987", month = may, keywords = "ray tracing cull, bounding volume", annote = "Intersection calculations dominate the run time of canonical ray tracers. A common algorithm to reduce the number of intersection tests required is the intersection of rays with a tree of extents, rather than the whole database of objects. A shortcomming of this method is that these trees are difficult to generate. Additionally, manually generated trees are poor, greatly reducing the run-time improvement available. We present methods for evaluation of these trees in approximate number of intersection calculations required and for automatic generation of good trees. These methods run in $O(n \log n)$ expected time where $n$ is the number of objects in the scene. Some examples of speedup are reported.", who = "Havran Vlastimil: RT-0035", } @InProceedings{arvo87a, author = "James Arvo and David Kirk", title = "Fast Ray Tracing by Ray Classification", pages = "55--64", booktitle = "(SIGGRAPH '87 Proceedings)", volume = "21", number = "4", year = "1987", month = jul, editor = "Maureen C. Stone", conference = "held in Anaheim, California; 27 -- 31 July 1987", keywords = "visible surface algorithms, extent, bounding volume, hierarchy, traversal, octree", annote = "five dimensional space subdivision \\ We describe a new approach to ray tracing which drastically reduces the number of ray-object and ray-bounds intersection calculations by means of 5-dimensional space subdivision. Collections of rays originating from a common 3D rectangular volume and directed through a 2D solid angle are represented as hypercubes in 5-space. A 5D volume bounding the space of rays is dynamically subdivided into hypercubes, each linked to a set of objects which are candidates for intersection. Rays are classified into unique hypercubes and checked for intersection with the associated candidate object set. We compare several techniques for object extent testing, including boxes, spheres, plane-sets, and convex poyhedra. In addition, we examine optimizations made possible by the directional nature of the algorithm, such as sorting, caching and backface culling. Results indicate that this algorithm significantly outperforms previous ray tracing techniques, especially for complex environments.", who = "Havran Vlastimil: RT-0034", } @InCollection{Arvo:1990:RTM, author = "James Arvo", title = "Ray Tracing with Meta-Hierarchies", year = "1990", month = aug, booktitle = "SIGGRAPH '90 Advanced Topics in Ray Tracing course notes", keywords = "hierarchical space subdivision, octree, grid subdivision", publisher = "ACM Press", who = "Havran Vlastimil: RT-0033", } @InProceedings{Cassen95, author = "Cassen T. and Subramanian K.R. and Michalewicz Z.", title = "Near-Optimal Construction of Partitioning Trees by Evolutionary Techniques", booktitle = "Proceedings of Graphics Interface '95", pages = "263--271", address = "Canada", month = jun, year = "1995", keywords = "BSP tree, genetic algorithms", who = "Havran Vlastimil: RT-0032", } @Article{Samet89, author = "Hanan Samet", title = "Implementing Ray Tracing with Octrees and Neighbor Finding", journal = "Computers and Graphics", volume = "13", number = "4", pages = "445--60", year = "1989", keywords = "octree", note = "includes code", anote = "A Ray Tracing implementation is described that is based on an octree representation of a scene. Rays are traced through the scene by calculating the blocks through which they pass. This calculation is performed in a bottom-up manner through the use of neighbor finding. The octrees are assumed to be implemented by a pointer representation.", who = "Havran Vlastimil: RT-0031", } @InProceedings{wallace89a, author = "John R. Wallace and Kells A. Elmquist and Eric A. Haines", title = "A Ray Tracing Algorithm for Progressive Radiosity", pages = "315--324", booktitle = "SIGGRAPH '89 Proceedings", journal = "Computer Graphics (SIGGRAPH '89 Proceedings)", year = "1989", month = jul, conference = "held in Boston, Massachusetts; 31 July -- 4 August 1989", keywords = "radiosity, ray tracing, progressive refinement, distributed ray tracing, global illumination", annote = "calculating form-factors via ray tracing to avoid hemicube problems \\ A new method for computing form-factors within a progressive radiosity approach is presented. Previously, the progressive radiosity approach has depended on the use of the hemi-cube algorithm to determine form-factors. However, sampling problems inherent in the hemi-cube algorithm limit its usefulness for complex images. A more robust approach is described in which ray tracing is used to perform the numerical integration of the form-factor equation. The approach is tailored to provide good, approximate results for a low number of rays, while still providing a smooth continuum of increasing accuracy for higher number of rays. Quantitative comparisons between analytically derived form-factors and ray traced form-factors are presented.", who = "Havran Vlastimil: RT-0030", } @InProceedings{peng87a, author = "Qunsheng Peng and Yining Zhu and Youdong Liang", title = "A Fast Ray Tracing Algorithm Using Space Indexing Techniques", pages = "11--23", booktitle = "Eurographics '87", year = "1987", month = aug, editor = "G. Marechal", publisher = "North-Holland", conference = "European Computer Graphics Conference and Exhibition; held in Amsterdam, The Netherlands; 24 -- 28 August 1987", keywords = "octree", annote = "A fast ray tracing algorithm is presented. Spatial coherency is exploited by adopting a linear octree data structure which corresponds to an adaptive partitioning of space. A ray strides over a number of empty regions aligning on its way and intersects the desired objects directly. Efficiency of the algorithm is achieved by decreasing the number of regions that the ray must be checked with, by reducing the computations involved in skipping an empty region and performing a binary search to find the next region. An efficient algorithm based on linear programming for mapping the whole environment into a sorted linear octree is also described. Only the terminal nodes containing boundary surfaces of objects are explicitly represented, which not only shortens the searching process but also leads to a considerable saving on storage space.", who = "Havran Vlastimil: RT-0029", } @InProceedings{Ward:1991:AST, author = "Gregory Ward", title = "Adaptive shadow testing for ray tracing", booktitle = "Eurographics Workshop on Rendering", year = "1991", conference = "held in Barcelona, Spain; 13-15 May 1991", annote = "Method for reducing the number of shadow rays for scenes with a large number of light sources. The sources are sorted on their contribution, and only for the most important sources rays are cast. The influence of the other sources is estimated statistically. Tests are done with different tolerances (threshold to determine whether sources are important) and certainties (rate of accuracy). The method gives good reduction and is able to find the most important shadows because it selects contrast as criterion.", who = "Havran Vlastimil: RT-0028", } @Article{Pradhan:1991:ACD, author = "B. S. S. Pradhan and A. Mukhopadhyay", title = "Adaptive cell division for ray tracing", journal= "Computers and Graphics", volume = "15", number = "4", pages = "549--552", year = "1991", coden = "COGRD2", ISSN = "0097-8493", bibdate= "Wed Feb 5 07:22:58 MST 1997", acknowledgement= ack-nhfb, affiliation="Indian Inst of Technology", affiliationaddress="Kanpur, India", classification="723", journalabr="Comput Graphics (Pergamon)", keywords="Computer Graphics; Data Processing--Data Structures; Three Dimensional Graphics", who = "Havran Vlastimil: RT-0027", } @Article{scherson87a, author = "Isaac D. Scherson and Elisha Caspary", title = "Data Structures and the Time Complexity of Ray Tracing", pages = "201--213", journal = "The Visual Computer", volume = "3", number = "4", year = "1987", month = dec, annote = "The time complexity of ray tracing is a function of the data structures used for space division. Octree and hierarchical extents have been suggested as effective choices. In this paper, complexity parameters are suggested to characterize images and show that both octrees and hierarchies are appropriate choices if given most favorable images. Also, a unified technique is proposed and shown to be better than previous methods for all images. Octrees and hierarchies are particular cases of the new proposed algorithm.", who = "Havran Vlastimil: RT-0026", } @InProceedings{Reinhard96, author= "Erik Reinhard and Arjan J. F. Kok and Frederik W. Jansen", title = "Cost Prediction in Ray Tracing", booktitle= "Rendering Techniques '96 (Proceedings of the Seventh Eurographics Workshop on Rendering)", pages= "41--50", publisher= "Springer-Verlag/Wien", address= "New York, NY", year= "1996", ISBN= "3-211-82883-4", who = "Havran Vlastimil: RT-0025", } @InProceedings{devillers89a, author = "Olivier Devillers", title = "The Macro-regions: an Efficient Space Subdivision Structure for Ray Tracing", pages = "27--38", booktitle = "Eurographics '89", year = "1989", month = sep, editor = "W. Hansmann and F. R. A. Hopgood and W. Strasser", publisher = "Elsevier / North-Holland", conference = "European Computer Graphics Conference and Exhibition; h eld in , ; -- September 1989", annote = "Ray tracing is the usual image synthesis technique which allows rendering of specular effects. The use of space subdivision for ray tracing optimization is studied. A new method of subdivision is proposed: the macro-regions. This structure allows a different treatment of the regions with a low density of information, and the regions with a high density of information. A theoretical and practical study of space subdivision methods--grid, octree--and the macro-regions structure is presented.", who = "Havran Vlastimil: RT-0024", } @Article{Stolte:1995:DRH, author = "N. Stolte and R. Caubet", title = "Discrete Ray-Tracing of Huge Voxel Spaces", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "14", number = "3", pages = "C/383--C/394", month = sep, year = "1995", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Fri Jul 18 14:10:31 1997", acknowledgement = ack-nhfb, classification = "C1160 (Combinatorial mathematics); C5470 (Performance evaluation and testing); C6120 (File organisation); C6130B (Graphics techniques)", conflocation = "Maastricht, Netherlands; 18 Aug.-1 Sept. 1995", conftitle = "EUROGRAPHICS '95", corpsource = "Inst. de Recherche en Inf. de Toulouse, France", keywords = "3D; 3D grid resolution; discrete ray tracing voxel spaces; Discrete ray tracing voxel spaces; discrete traversal; Discrete traversal; discrete traversal; grid resolution; Huge voxel spaces; huge voxel spaces; memory problem; Memory problem; octree; Octree; octrees; optimal times; Optimal times; optimal times; performance evaluation; Practical visualization algorithm; practical visualization algorithm; raster; Raster ray tracing; ray tracing; three dimensional DDA; Three dimensional DDA; three dimensional DDA", thesaurus = "Octrees; Performance evaluation; Ray tracing", treatment = "P Practical", who = "Havran Vlastimil: RT-0023", } @InProceedings{kay86a, author = "Timothy L. Kay and James T. Kajiya", title = "Ray Tracing Complex Scenes", pages = "269--278", booktitle = "SIGGRAPH '86 Proceedings)", journal = "Computer Graphics (SIGGRAPH '86 Proceedings)", volume = "20", number = "4", year = "1986", month = aug, editor = "David C. Evans and Rusell J. Athay", conference = "held in Dallas, Texas, August 18--22, 1986", keywords = "I37 ray tracing, cull, bounding volume", annote = "A new algorithm for speeding up ray-object intersection calculations is presented. Objects are bounded by a new type of extent, which can be made to fit convex hulls arbitrarily tightly. The objects are placed into a hierarchy. A new hierarchy traversal algorithm is presented which is efficient in the sense that objects along the ray are queried in an efficient order. \\ Results are presented which demonstrate that our technique is several times faster than other published algorithms. Furthermore, it is demonstrated that it is currently possible to ray trace scenes containing hundreds of thousands of objects.", who = "Havran Vlastimil: RT-0022", } @Article{Glassner:1984:SSF, author = "Andrew S. Glassner", title = "Space Subdivision For Fast Ray Tracing", pages = "15--22", journal = "IEEE Computer Graphics and Applications", volume = "4", number = "10", year = "1984", month = oct, keywords = "I35 Ray Tracing, culling, parallel processing, bounding volume, octree", annote = "use of octrees to speed intersection testing `If we want to reduce the time spent on ray-object intersections, we have at least two choices. We can speed up the intersection process itself, possibly with specialized hardware. Alternately, we can reduce the number of ray-object intersections that must be made to fully trace a given ray.''Goes onto to describe how to use octrees to reduce the number of intersection tests. Glassner proposes an octree as structure to partition space for faster ray tracing. The solution is interesting, but non-intuitive. It also has the problem of splitting objects among many octree nodes. Hence, the same object may be intersected multiple times per ray. Bleh!", who = "Havran Vlastimil: RT-0021", } @Article{Hsiung92, author = "Ping-Kang Hsiung and Robert H. Thibadeau", title = "Accelerating {ARTS}", journal = "The Visual Computer", volume = "8", number = "3", pages = "181--190", month = mar, year = "1992", keywords = "grid subdivision, hierarchical subdivision", note = "nested grid subdivision structures", who = "Havran Vlastimil: RT-0020", } @Article{fujimoto86a, author = "Akira Fujimoto and Takayuki Tanaka and Kansei Iwata", title = "{ARTS}: Accelerated Ray Tracing System", pages = "16--26", journal = "IEEE Computer Graphics and Applications", volume = "6", number = "4", year = "1986", keywords = "ray tracing cull, parallel processing, octree", annote = "Describes an encoding format, similar to octrees, which allows ray tracing to become as fast as other rendering methods for large databases. Good review of other techniques used to speed up ray tracing. Their method, SEADS (Spatially Enumerated Auxiliary Data Structures), {provides an environment for ray tracing that outpaces the hybrid octree approaches ... by an order of magnitude. Various experimental results have shown that the rendering time is virtually independent of the number of objects in the scene. When the number of objects is very large, ray tracing --- despite its reputation for ineffiency --- actually becomes faster than other rendering methods.} \\ In this paper, we propose algorithms that address the two basic problems encountered in generating continuous-tone images by ray tracing: speed and aliasing. We examine previous approaches to the problem and propose a scheme based on the coherency of an auxiliary data structure imposed on the original object domain. After investigating both simple spatial enumeration and a hybrid octree approach, we develop the 3DDDA, a 3D line generator, for efficient traversing of both structures. \\ 3DDDA provides an order of magnitude improvement in processing speed compared to other known ray-tracing methods. Processing time is found to be virtually independent of the number of objects involved in the scene. For large numbers of objects, this method actually becomes faster than scan-line methods. To remove jags from edges, a scheme for identifying edge orientation and distance from pixel center to true edge has been implemented. The time required for antialiasing depends on the total length of the edges encountered, but it is normally only a fractional addition to the time needed to produce the scene without antialiasing.", who = "Havran Vlastimil: RT-0019", } @InProceedings{bouatouch87a, author = "Kadi Bouatouch and M. O. Madani and Thierry Priol and Bruno Arnaldi", title = "A New Algorithm of Space Tracing Using a {CSG} Model", pages = "65--78", booktitle = "Eurographics '87", year = "1987", month = aug, editor = "G. Marechal", publisher = "North-Holland", conference = "European Computer Graphics Conference and Exhibition; held in Amsterdam, The Netherlands; 24 -- 28 August 1987", annote = "This paper describes a new algorithm of space tracing. Scenes are modeled by a CSG tree. Space is subdivided regularly into 3D regions called boxes. With each box is associated a subtree which is the restriction of the whole scene CSG tree to primitives belonging to this box. A 3D grid is ued to access boxes.", who = "Havran Vlastimil: RT-0018", } @Article{Bouville:1985:GHQ, author = "C. Bouville and R. Brusq and J. L. Dubois and I. Marchal", title = "Generating High Quality Pictures by Ray-Tracing", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "4", number = "2", pages = "87--99", month = jun, year = "1985", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Mon Apr 14 10:23:20 MDT 1997", acknowledgement = ack-nhfb, affiliation = "Cent Commun d'Etudes de Telediffusion et Telecommunications, Cesson-Sevigne, Fr", affiliationaddress = "Cent Commun d'Etudes de Telediffusion et Telecommunications, Cesson-Sevigne, Fr", classification = "723; 741; 921; A4210D (Wave-front and ray tracing in homogeneous media); C6130B (Graphics techniques)", corpsource = "Centre Commun d'Etudes de Telediffusion et Telecommun., Cesson-Sevigne, France", keywords = "algebraic surfaces; bodies of revolution --- Surfaces; casting; computational geometry; computer graphics; computer graphics --- Imaging Techniques; full lighting model; geometrical; high quality pictures developing; illumination model; image processing; lighting models; Mathematical Models; mathematical surface representation, design; optics; parallel; picture generation; processors; ray-; ray-casting technique; ray-tracing; surface of revolution; theoretical approach", subject = "J.6 Computer Applications, COMPUTER-AIDED ENGINEERING, Computer-aided design (CAD) \\ I.3.5 Computing Methodologies, COMPUTER GRAPHICS, Computational Geometry and Object Modeling, Curve, surface, solid, and object representations", treatment = "P Practical; T Theoretical or Mathematical", who = "Havran Vlastimil: RT-0017", } @Article{thomas89a, author = "D. Thomas and Arun N. Netravali and D. S. Fox", title = "Anti-aliased ray tracing with covers", pages = "325--336", journal = "Computer Graphics Forum", volume = "8", number = "4", month = dec, year = "1989", publisher = "North-Holland", keywords = "antialiasing", annote = "A fast and effective object space method for anti-aliasing ray-traced pictures is introduced. Traditionally, anti-aliasing has been done using super-sampling. However, this is costly since it requires casting large numbers of rays to obtain sample densities above the displayed pixel density. It is also wasteful since much of the information in these samples is discarded when they are filtered to yield the anti-aliasing pixels. We avoid these problems by performing the filtering in the object space using the geometry of ray-surface intersections rather than by casting extra rays. In addition, we only perform filtering at a pixel if edges are nearby. We detect these edges by observing the order in which the pixel's rays pass through cover surfaces constructed just inside and outside the surface of each object. Shadows, reflections and refractions can be anti-aliased using this method and a variety of object types can be handled including ellipsoids, polyhedra, and objects formed using set operations. \\ Our anti-aliasing gives high image quality that can only be approached by using super-sampling densities at least four times the display pixel density. Moreover, since the overhead of our method is small, it would take three to four times as long to render an anti-aliased image using super-sampling than it would with our method. Furthermore, covers allow sampling densities less than the displayed pixel density. When this is done, anti-aliased images can be rendered twice as fast as with no anti-aliasing and six to eight times as fast as when super-sampling is used for anti-aliasing.", who = "Havran Vlastimil: RT-0016", } @Article{Campagna:1997:RTS, author = "Swen Campagna and Philipp Slusallek and {Hans-Peter} Seidel", title = "Ray tracing of spline surfaces: {B}{\'{e}}zier clipping, {C}hebyshev boxing, and bounding volume hierarchy - a critical comparison with new results", journal = "The Visual Computer", year = "1997", volume = "13", number = "6", pages = "265--282", publisher = "Springer-Verlag", note = "ISSN 0178-2789", keywords = "ray tracing, spline surfaces, surface rendering", annote = "Ray tracing is a well-known rendering technique for producing high-quality and photorealistic pictures. Spline surfaces are also well known and widely used. Thus, there is the need for fast and robust methods for computing the intersections of rays with these surfaces. In this paper, we discuss and compare three recent geometric algorithms for solving the ray-patch intersection problem and present new results that are helpful in dealing with this problem.", who = "Havran Vlastimil: RT-0015", } @Article{Weghorst:1984:ICM, author = "Hank Weghorst and Gary Hooper and Donald P. Greenberg", title = "Improved Computational Methods for Ray Tracing", journal = "ACM Transactions on Graphics", volume = "3", number = "1", pages = "52--69", month = jan, year = "1984", coden = "ATGRDF", ISSN = "0730-0301", annote = "discussion of bounding volumes, hierarchical structures and the `item buffer'' \\ This paper describes algorithmic procedures that have been implemented to reduce the computational expense of producing ray-traced images. The selection of bounding volumes is examined to reduce the computational cost of the ray-intersection test. The use of object coherence, which relies on a hierarchical description of the environment, is then presented. Finally, since the building of the ray-intersection trees is such a large portion of the computation, a method using image coherence is described. This visible-surface preprocessing method, which is dependent upon the creation of an `item buffer,'' takes advantage of {\em a priori} image formation. Examples that indicate the efficiency of these techniques for a variety of representative environments are presented.", keywords = "bounding volume; I35 Ray Tracing", who = "Havran Vlastimil: RT-0014", } @InCollection{Kaplan:1987:USC, author = "Michael R. Kaplan", title = "The Use of Spatial Coherence in Ray Tracing", booktitle = "Techniques for Computer Graphics", pages = "173--193", year = "1987", editor = "David E. Rogers and Ray A. Earnshaw", publisher = "Springer Verlag", keywords = "octree", annote = "improved version of course notes article \\ Although ray tracing has proven to be a valuable technique in realistic image synthesis and a variety of other disciplines, it traditionally has not been viable in highly complex, unstructured environments. Spatial coherence algorithms for ray tracing are proposed as a solution to this problem, and the tradeoffs between various spatial coherence schemes are discussed.", who = "Havran Vlastimil: RT-0013", } @InProceedings{Zwaan95, author = "Maurice van der Zwaan and Erik Reinhard and Frederik W. Jansen", title = "Pyramid Clipping for Efficient Ray Traversal", booktitle = "Proceedings of the Sixth Eurographics Rendering Workshop", address = "Dublin, Ireland", year = "1995", who = "Havran Vlastimil: RT-0012", } @Article{badt88a, author = "Sig Badt Jr.", title = "Two Algorithms for Taking Advantage of Temporal Coherence in Ray Tracing", pages = "123--132", journal = "The Visual Computer", volume = "4", number = "3", year = "1988", month = sep, annote = "The basic ray-tracing algorithm is adapted to make ray-tracing faster for the production of motion pictures. Two algorithms are presented. The image space temporal coherence algorithm takes advantage of the fact that motion picture images do not change very much from frame to frame. The reprojection algorithm uses information about the object space saved from the previous frame to accelerate the processing of the current frame. The reprojection algorithm is used when the viewpoint of the current frame is changed by a small amount from the viewpoint of the previous frame.", who = "Havran Vlastimil: RT-0011", } @InProceedings{amanatides87b, author = "John Amanatides and Andrew Woo", title = "A fast voxel traversal algorithm for ray tracing", pages = "3--10", booktitle = "Eurographics '87", year = "1987", month = aug, editor = "G. Marechal", publisher = "North-Holland", conference = "European Computer Graphics Conference and Exhibition; held in Amsterdam, The Netherlands; 24 -- 28 August 1987", annote = "uniform grid space subdivision \\ This paper discusses a fast and simple voxel traversal algorithm through a 3D space partition. Going from one voxel to its neighbor requires only two floating point comparisons and one floating point addition. Also, multiple ray intersections with objects that are in more than one voxel are eliminated.", who = "Havran Vlastimil: RT-0010", } InProceedings{Kirk:1988:RTK, author = "David Kirk and James Arvo", title = "The Ray Tracing Kernel", pages = "75--82", booktitle = "Proceedings of Ausgraph '88", year = "1988", annote = "We describe a methodology for implementing a ray tracer which provides both a convenient testbed for developing new algorithms and a way to exploit the growing number of acceleration techniques. These benefits are a natural consequence of a collection of data abstractions called the ``ray tracing kernel.'' By defining an ``object'' in a broad sense, the kernel allows a single abstraction to encapsulate a wide spectrum of concepts including geometric primitives, acceleration techniques, CSG operators, and object transformations. Through hierarchical nesting of instances of these objects we are able to construct and efficiently render complex environments.", who = "Havran Vlastimil: RT-0009", } @InProceedings{Fournier:1993:RTA, author = "Alain Fournier and Pierre Poulin", title = "A Ray Tracing Accelerator Based on a Hierarchy of 1{D} Sorted Lists", year = "1993", month = may, booktitle = "Proceedings of Graphics Interface '93", publisher = "Canadian Information Processing Society", pages = "53--61", address = "Toronto, Ontario", keywords = "efficiency", who = "Havran Vlastimil: RT-0008", } @InProceedings{Thirion:1990:TDS, author = "Jean-Philippe Thirion", title = "{TRIES}: Data Structures Based on Binary Representation for Ray Tracing", pages = "531--541", booktitle = "Eurographics '90", year = "1990", month = sep, editor = "C. E. Vandoni and D. A. Duce", publisher = "North-Holland", conference = "European Computer Graphics Conference and Exhibition; held in Montreux, Switzerland; 3 -- 7 September 1990", keywords = "ray tracing, data structure, binary tree, boolean operation, trie", who = "Havran Vlastimil: RT-0007", } @InProceedings{Subramanian:1991:ATC, author = "K. R. Subramanian and Donald S. Fussell", title = "Automatic Termination Criteria for Ray Tracing Hierarchies", pages = "93--100", booktitle = "Proceedings of Graphics Interface '91", year = "1991", month = jun, conference = "held in Calgary, Alberta; 3-7 June 1991", keywords = "ray tracing, bounding volume, extent, partitioning plane, search structure, traversal", who = "Havran Vlastimil: RT-0006", } @InProceedings{Formella94a, author = "A. Formella and C. Gill and V. Hofmeyer", title = "Fast Ray Tracing of Sequences by Ray History Evaluation", booktitle = "Proceedings of Computer Animation '94", conference = "Computer Animation '94", pages = "184--191", year = 1994, month = may, publisher = "IEEE Computer Society Press", who = "Havran Vlastimil: RT-0005", } @InProceedings{dauenhauer90a, author = "David Elliott Dauenhauer and Sudhanshu Kumar Semwal", title = "Approximate Ray Tracing", pages = "75--82", booktitle = "Proceedings of Graphics Interface '90", year = "1990", month = may, conference = "held in Halifax, Nova Scotia; 14-18 May 1990", keywords = "shading, rendering algorithm", who = "Havran Vlastimil: RT-0004", } @Article{Formella97a, author = "F. Aguado and F.P. Fontan and A. Formella", title = "Indoor and Outdoor Channel Simulator Based on Ray Tracing", journal = "IEEE Transactions on Magnetics", year = "1997", volume = "33", number = "2", publisher = "", pages = "1484--1487", who = "Havran Vlastimil: RT-0003", } @Article{Formella:1995:RTQ, author = "A. Formella and C. Gill", title = "Ray tracing: a quantitative analysis and a new practical algorithm", journal = "The Visual Computer", year = "1995", volume = "11", number = "9", publisher = "Springer-Verlag", pages = "465--476", note = "ISSN 0178-2789", who = "Havran Vlastimil: RT-0002", } @Article{Klimaszewski:1997:FRT, author= "Kryzsztof S. Klimaszewski and Thomas W. Sederberg", title = "Faster Ray Tracing Using Adaptive Grids", journal= "IEEE Computer Graphics and Applications", volume= "17", number = "1", pages = "42--51", month = jan # "\slash " # feb, year = "1997", coden = "ICGADZ", ISSN = "0272-1716", bibdate= "Sat Jan 25 10:55:04 MST 1997", acknowledgement=ack-nhfb, who = "Havran Vlastimil: RT-0001", } @Article{Kwon98, author = "Bomjun Kwon and Dae Seoung Kim and Kyung-Yong Chwa and Sung Yong Shin", title = "Memory-Efficient Ray Classification for Visibility Operations", journal = "IEEE Transactions on Visualization and Computer Graphics", volume = "4", number = "3", month = {jul--sep}, year = "1998", pages = "193--201", abstract = "", keywords = "ray shooting, ray classification, ray tracing, rendering", who = "Havran Vlastimil: RT-0197", }