@article{bb9633, AUTHOR = "Upstill, S.", TITLE = "The Renderman Companion, Addison-Wesley, Reading", JOURNAL = "MA", VOLUME = "89", YEAR = "1989", PAGES = "1989" } @inproceedings{BerDobEpp-SODA-90, title = {{Visibility with a moving point of view}}, author = {Marshall W. Bern and David P. Dobkin and David Eppstein and Robert L. Grossman}, booktitle = {Proc. 1st Symp. Discrete Algorithms}, publisher = {Assoc. Comput. Mach. and Soc. Industrial {\&} Applied Mathematics}, pages = {107--118}, month = {January}, year = {1990} } @article{BerDobEpp-Algo-94, title = {{Visibility with a moving point of view}}, author = {Marshall W. Bern and David P. Dobkin and David Eppstein and Robert L. Grossman}, journal = {Algorithmica}, volume = {11}, number = {4}, pages = {360--378}, month = {April}, year = {1994}, review = {MR-94j:68307} } @article{MR-94j:68307, author = {Marshall W. Bern and David P. Dobkin and David Eppstein and Robert L. Grossman}, reviews = {BerDobEpp-Algo-94}, journal = {Mathematical Reviews}, publisher = {Amer. Math. Soc.}, title = {{Visibility with a moving point of view}}, number = {94j:68307}, year = {1994} } @article{ma4, author="J. Matousek", title="Efficient partition trees", journal="Discrete and Computational Geometry", year="1992", volume="8", number="", pages="315-334" } @inproceedings{ma92acm, author="J. Matousek", title="Range searching with efficient hierarchical cuttings", booktitle="$8^{th}$ ACM Conf. in Comp. Geom.", address="Berlin", year="1992", pages="276-285" } @article {ma1, author="J. Matousek", title="Range searching with efficient hierarchical cuttings", journal="Discrete and Computational Geometry", year="1993", volume="10", number="", pages="157-182" } @Article{Matousek95, title={Approximations and Optimal Geometric Divide-and-Conquer}, author={Ji{\v{r}}{\'\i} Matou{\v{s}}ek}, pages={203--208}, journal=jcss, year=1995, month=apr, volume=50, number=2, preliminary={STOC::Matousek1991} } @Article{Adelson:1995:GER, author = "Stephen J. Adelson and Larry F. Hodges", title = "Generating Exact Ray-Traced Animation Frames by Reprojection", journal = "j-IEEE-CGA", volume = "15", number = "3", pages = "43--52", month = may, year = "1995", CODEN = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", bibsource = "Compendex database", acknowledgement = ack-nhfb, affiliation = "Comput. Res. and Applications, Los Alamos Nat. Lab., NM, USA", classification = "723; 723.5; 741.1; 742.2", journalabr = "IEEE Comput Graphics Appl", keywords = "Algorithms; Animation; Animation frames; Cameras; Color; Color image processing; Computer graphics; Interactive animation; Light sources; Ray tracing; Reprojection; Spatiotemporal coherence; Three dimensional; Visualization; Volume visualization", } Article{Dias:1994:RTI, author = "Maria Lurdes Dias", title = "Ray tracing interference color: visualizing {Newton}'s rings", journal = "j-IEEE-CGA", volume = "14", number = "3", pages = "17--20", month = may, year = "1994", CODEN = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", bibsource = "Compendex database", abstract = "Generalized Fresnel's reflectance formulas provide the basis for this ray tracing method, which simulates the natural phenomenon of interference color. A visualization of Newton's rings demonstrates its accuracy.", acknowledgement = ack-nhfb, affiliation = "Dept. de Fisica, Coimbra Univ., Portugal", classification = "723.2; 723.5; 741.1; 921.6; 931.2", journalabr = "IEEE Comput Graphics Appl", keywords = "Algorithms; Color; Color computer graphics; Color image processing; Computer simulation; Computer vision; Fresnel's reflectance formula; Interference color; Light reflection; Mathematical models; Newton's ring; Polarization; Ray tracing; Reflectance model; Refractive angle; Refractive index; Thick films; Thin films; Visualization", } @Article{Meinzer:1991:HRT, author = "Hans-Peter Meinzer and Kirsten Meetz and Dinu Scheppelmann and Uwe Engelmann and Hans Jurgen Baur", title = "The {Heidelberg} Ray Tracing Model", journal = "j-IEEE-CGA", volume = "11", number = "6", pages = "34--43", month = nov, year = "1991", CODEN = "ICGADZ", ISSN = "0272-1716", bibsource = "Graphics/siggraph/91.bib", keywords = "volume rendering", } @Article{Dias:1991:RTI, author = "Maria Lurdes Dias", title = "Ray Tracing Interference Color", journal = "j-IEEE-CGA", volume = "11", number = "2", pages = "54--60", month = mar, year = "1991", CODEN = "ICGADZ", ISSN = "0272-1716", bibdate = "Wed Jan 29 06:15:39 1997", bibsource = "Graphics/siggraph/91.bib, Compendex database", acknowledgement = ack-nhfb, affiliation = "Phys Dept, Univ of Coimbra, Portugal", classification = "723; 741", journalabr = "IEEE Comput Graphics Appl", keywords = "Color; Computer Graphics; Constructive Interference; Destructive Interference; External Reflection; Light --- Interference; Optical Thickness; Ray Tracing Interference Color; shading; Thin Film Reflectance", } @Article{Woodwark:1991:RHC, author = "John Woodwark", title = "Reconstructing history with computer graphics", journal = "j-IEEE-CGA", volume = "11", number = "1", pages = "18--20", month = jan, year = "1991", CODEN = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", bibsource = "Graphics/siggraph/91.bib, Compendex database", acknowledgement = ack-nhfb, affiliation = "Information Geometers, Winchester, UK", annote = "Corrections on some statements done in haggerty90d IEEE CGA July 90.", classification = "402; 723; 901", journalabr = "IEEE Comput Graphics Appl", keywords = "Applications; Archeology; Architecture --- History; architecture, archaeology; Churches --- Design; Computer Graphics; Computer Programming --- Algorithms; Computer Simulation; Divided Object Space Ray Casting Algorithm (DORA); Models; Ray Casters; Resistivity Results; Roman Baths; Roman Temples", } @Article{Mastin:1987:FSO, author = "Gary A. Mastin and Peter A. Watterberg and John F. Mareda", title = "{Fourier} Synthesis of Ocean Scenes", journal = "j-IEEE-CGA", volume = "7", number = "3", pages = "16--23", month = mar, year = "1987", CODEN = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", bibsource = "Compendex database, Graphics/siggraph/87.bib", acknowledgement = ack-nhfb, affiliationaddress = "Sandia Natl Lab, Albuquerque, NM, USA", classification = "471; 723; 921", journalabr = "IEEE Comput Graphics Appl", keywords = "Computer Applications; computer graphics; computer programming --- Algorithms; mathematical transformations --- Fourier Transforms; model natural wave; oceanography; ray tracing; signal filtering and prediction; white-noise images", } @Article{Amanatides:1987:RCG, author = "John Amanatides", title = "Realism in Computer Graphics: a Survey", journal = "j-IEEE-CGA", volume = "7", number = "1", pages = "44--56", month = jan, year = "1987", CODEN = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", bibsource = "Compendex database, Graphics/siggraph/87.bib", acknowledgement = ack-nhfb, affiliationaddress = "Univ of Toronto, Ont, Can", annote = "This article surveys most of the major issues to be dealt with when generating realistic images, and covers papers up to December 1985. It begins with an overview of the rendering process and a quick review of visible surface-determination algorithms. Then, in more detail, it discusses shading, antialiasing, texture mapping, shadows, and optical effects and closes with a discussion of modeling primitives.", classification = "723; 741; 921", journalabr = "IEEE Comput Graphics Appl", keywords = "computer graphics; general survey, bibliography, tutorial; image processing --- Synthesis; mathematical techniques --- Algorithms; pixel boundary; ray tracing geometry; Reviews; sampling; shading geometry; signal filtering and prediction; texture mapping; visibility --- Mathematical Models; visibility algorithms", } @Article{Greene:1986:EMO, author = "Ned Greene", title = "Environment Mapping and Other Applications of World Projection", journal = "j-IEEE-CGA", volume = "6", number = "11", pages = "21--29", month = nov, year = "1986", CODEN = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", bibsource = "Compendex database", acknowledgement = ack-nhfb, affiliationaddress = "New York Inst of Technology, Old Westbury, NY, USA", classification = "723; 741", conference = "Graphics Interface 86", journalabr = "IEEE Comput Graphics Appl", keywords = "computer graphics; diffuse surface illumination; imaging techniques; optics; ray tracing; specular surface illumination; texture filtering; world projections", meetingaddress = "Vancouver, BC, Can", meetingdate = "1986", meetingdate2 = "86", } @Article{Steinberg:1984:SSB, author = "Herbert A. Steinberg", title = "A Smooth Surface Based on Biquadratic Patches", journal = "j-IEEE-CGA", volume = "4", number = "9", pages = "20--23", month = sep, year = "1984", CODEN = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", bibsource = "Compendex database", acknowledgement = ack-nhfb, classification = "723", journalabr = "IEEE Comput Graphics Appl", keywords = "biquadratic patches; computer graphics; I35 biquadratic patches and I37 ray-tracing", } @Article{Coquillart:1984:SDD, author = "Sabine Coquillart and Michel Gangnet", title = "Shaded Display of Digital Maps", journal = "j-IEEE-CGA", volume = "4", number = "7", pages = "35--42", month = jul, year = "1984", CODEN = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", bibsource = "Compendex database, Graphics/siggraph/84.bib", acknowledgement = ack-nhfb, annote = "Several methods for displaying height fields are presented. Bilinear interpolation of patches is used to define the surface. Efficient algorithms, and quite elegant. Reminiscent of Kajiya's cut planes for surfaces of revolution.", classification = "405; 723; 741", journalabr = "IEEE Comput Graphics Appl", keywords = "computer graphics --- Applications; digital maps; maps and mapping; maps, terrain, ray tracing, priority list, I37 Ray Tracing, I37 Shading, I3m Cartography; priority lists; ray-tracing techniques; shaded images of terrain", } @MASTERSTHESIS{ Westin-Thesis, AUTHOR = "Stephen H. Westin", TITLE = "Predicting Reflectance Functions from Complex Surfaces", SCHOOL = "Cornell University", MONTH = Aug, YEAR = 1992 } @InProceedings{westin92a, author = "Stephen H. Westin and James R. Arvo and Kenneth E. Torrance", title = "Predicting reflectance functions from complex surfaces", pages = "255--264", booktitle = "Computer Graphics (SIGGRAPH '92 Proceedings)", volume = "26", number = "2", year = "1992", month = jul, editor = "Edwin E. Catmull", conference = "held in Chicago, Illinois; 26-31 July 1992", keywords = "spherical harmonics, monte carlo, anisotropic reflection, brdf", } @InProceedings{sillion91b, author = "Francois X. Sillion and James R. Arvo and Stephen H. Westin and Donald P. Greenberg", title = "A global illumination solution for general reflectance distributions", pages = "187--196", booktitle = "Computer Graphics (SIGGRAPH '91 Proceedings)", volume = "25", number = "4", year = "1991", month = jul, editor = "Thomas W. Sederberg", conference = "held in Las Vegas, Nevada; 28 July - 2 August 1991", keywords = "global illumination, brdf, specular reflection, directional-diffuse, progressive radiosity, spherical harmonics", annote = "A general light transfer simulation algorithm for environments composed of materials with arbitrary reflectance functions is presented. This algorithm removes the previous practical restriction to ideal specular and/or ideal diffuse environments, and supports complex physically based reflectance distributions. This is accomplished by extending previous two-pass ray-casting radiosity approaches to handle non-uniform intensity distributions, and resolving all possible energy transfers between sample points. An implementation is described based on a spherical harmonic decomposition for encoding both bidirectional reflectance distribution functions for materials, and directional intensity distributions for illuminated surfaces. The method compares favorably with experimental measurements.", } @Article{Poulin:1991:SSL, author = "Pierre Poulin and John Amanatides", title = "Shading and shadowing with linear light sources", journal = "Computers and Graphics", volume = "15", number = "2", pages = "259--265", year = "1991", coden = "COGRD2", ISSN = "0097-8493", bibdate = "Wed Feb 5 07:22:58 MST 1997", acknowledgement = ack-nhfb, affiliation = "Univ of British Columbia", affiliationaddress = "Vancouver, BC, Can", annote = "Eurographics '90 award paper.", classification = "723; 741; 921", journalabr = "Comput Graphics (Pergamon)", keywords = "Computer Graphics --- Three Dimensional Graphics; Graphic Methods --- Research; Lambert's Laws; Light Sources; Linear Light Source Shading And Shadowing; Mathematical Techniques --- Chebyshev Approximation; Models; Shadowing Algorithms", } @TECHREPORT{ Novins92b, AUTHOR = "Kevin Novins and James Arvo and David Salesin", TITLE = "Adaptive Error Bracketing for Controlled-Precision Volume Rendering", INSTITUTION = "Department of Computer Science, Cornell University", NUMBER = "92-1312", MONTH = Nov, YEAR = 1992 } @INPROCEEDINGS{ Mitchell90, AUTHOR = "Don P. Mitchell", TITLE = "Robust Ray Intersection with Interval Arithmetic", BOOKTITLE = "Proceedings of Graphics Interface '90", YEAR = 1990, PAGES = "68--74" } @ARTICLE{Gigus90, AUTHOR = "Ziv Gigus and Jitendra Malik", TITLE = "Computing the aspect graph for line drawings of polyhedral objects", JOURNAL = "IEEE Transactions on Pattern Analysis and Machine Intelligence", VOLUME = 12, NUMBER = 2, MONTH = Feb, YEAR = 1990, PAGES = "113--122" } @Article{Sung:1992:ASB, author = "K. Sung", title = "Area sampling buffer: tracing rays with {Z}-buffer hardware", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "11", number = "3", pages = "C299--C310, C480--C481", month = "????", year = "1992", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Mon Apr 14 10:23:20 MDT 1997", acknowledgement = ack-nhfb, classification = "C6130B (Graphics techniques)", conflocation = "Cambridge, UK; 7-11 Sept. 1992", conftitle = "European Association for Computer Graphics 13th Annual Conference. EUROGRAPHICS 92", corpsource = "Dept. of Comput. Sci., Illinois Univ., Urbana, IL, USA", keywords = "area sampling; Area sampling; area sampling; buffer storage; computer graphics; Frame-buffer systems; frame-buffer systems; geometrical optics; hardware-assisted ray; Hardware-assisted ray tracing; image synthesis processes; Image synthesis processes; image synthesis processes; Light source area; light source area; Ray tracing; ray tracing; renderer; Renderer; Sampling area; sampling area; storage management; tracing; Z-buffer hardware", thesaurus = "Buffer storage; Computer graphics; Geometrical optics; Storage management", treatment = "P Practical", } @PhdThesis{spackman90a, author = "John Spackman", title = "Scene Decompositions for Accelerated Ray Tracing", year = "1990", type = "Ph.D. Thesis", school = "University of Bath, UK", annote = "Available as Bath Computer Science Technical Report 90/33. \\ Ray tracing has come to the fore in the computer synthesis of realistic images over the last decade. This algorithm synthesises a particularly high degree of realism in both the shading and shape of surfaces. Surface shading calculations incorporate not only local diffuse and specular radiance but also global shadowing, multiple reflection and refraction of view and light attenuation, all according to the laws of optical physics. Complex object shapes may be modelled as boolean constructs from exact specifications of many common geometries. A wide range of objects may be modelled exactly without resorting to polyhedral approximation. \\ Early implementations of ray tracing synthesised some of the most realistic images up to that date, but imposed an extremely high computational load for complex scenes. Synthesis times proved to be linear in object count, and projected times for scenes of a few thousand objects extended into months on popular mini-computers. This prevented the wide-spread application of ray tracing on non-specialised hardware. Various methods have been proposed over the last few years to improve the efficiency of ray tracing for more viable synthesis times. \\ This thesis addresses scene decompositions for the acceleration of ray traced image synthesis. The decomposition of a globally complicated scene into simpler local regions is shown to reduce the computational load imposed by ray tracing. Algorithms are presented for the construction and use of various types of scene decomposition. Their relative merits are compared and the ``octtree'' decomposition is shown to be particularly suitable for accelerating the synthesis of complex scenes.", } Article{Spackman:1991:SNR, author = "John Spackman and Philip Willis", title = "The {SMART} Navigation of a Ray Through an Oct-Tree", journal = "Computers and Graphics", volume = "15", number = "2", pages = "185--194", year = "1991", coden = "COGRD2", ISSN = "0097-8493", bibdate = "Wed Feb 5 07:22:58 MST 1997", acknowledgement = ack-nhfb, affiliation = "Univ of Bath", affiliationaddress = "Avon, Engl", classification = "723; 921", journalabr = "Comput Graphics (Pergamon)", keywords = "Computer Graphics; Computer Image Synthesis; Data Processing --- Data Structures; Digital Differential Analyzers; Graphic Methods --- Research; Imaging Techniques --- Research; Mathematical Techniques --- Trees; Oct Tree Scene Decompositions; octree; Ray Traced Image Synthesis; Research; Spatial Measure For Accelerated Ray Tracing (smart); Spatial Object Coherence", } @InCollection{Skytta:1991:DDM, author = "Jorma Skytta and Tapio Takala", title = "A Distributed Data Model for Raytracing", year = "1991", booktitle = "Advances in Computer Graphics Hardware III", editor = "A. A. M. Kuijk", publisher = "Springer Verlag", pages = "19--26", address = "New York", keywords = "parallelism", } @InProceedings{morris89a, author = "D. T. Morris and P. M. Dew", title = "Dynamic Dataflow Algorithms for Ray Tracing {CSG} Objects", pages = "452--460", booktitle = "Parallel Processing for Computer Vision and Display", year = "1989", editor = "P. M. Dew and R. A. Earnshaw and T. R. Heywood", publisher = "Addison-Wesley", annote = "This paper describes how solid objects may be rendered by use of dynamic dataflow techniques. Particular emphasis is given to the ray-tracing algorithm. The objects are described by constructive solid geometry. The algorithms are designed to be executed on a processor farm coupled with a data-driven dataflow machine. Many of the limitations of previous approaches, such as the Kedem-Ellis ray-casting machine are overcome. For example, the size of the objects that can be drawn directly is increased, the shading computations are made more efficient and there is better hardware utilization.", } @Article{Ohta:1990:RBT, author = "Masataka Ohta and Mamoru Maekawa", title = "Ray-Bound Tracing for Perfect and Efficient Anti-Aliasing", journal = "The Visual Computer", pages = "125--133", volume = "6", number = "3", month = jun, year = "1990", keywords = "ray tracing, antialiasing, coherence, bound", annote = "A complete detection of whether aliasing occurs in a given pixel is possible by using the concept of bounded rays and ray-bound tracing. A coherent set of rays can be bounded by bounding both their origins (by a sphere) and directions (by a circle on a unit sphere). By tracing bounds of rays in a pixel, along the direction of reflection, refraction or to light sources, it is possible to obtain an upper bound on the degree of aliasing in the pixel. Ray bound tracing is possible against various shapes and with various shading algorithms.", } @InProceedings{Ohta:1987:RCT, author = "Masataka Ohta and Mamoru Maekawa", title = "Ray Coherence Theorem and Constant Time Ray Tracing Algorithm", pages = "303--314", booktitle = "Computer Graphics 1987 (Proceedings of CG International '87)", year = "1987", editor = "Tsiyasu L. Kunii", publisher = "Springer-Verlag", keywords = "ray tracing, cull, computational geometry, spherical geometry, complexity", annote = "The concept of ray coherence is formalized as a ray coherence theorem to decrease the amount of computation in a ray object intersection of the ray tracing algorithm. Using the theorem, the calculation time of ray-object intersection in a ray tracing algorithm can be drastically decreased, by calculating a table which is used to limit the number of objects which may intersect with a given ray. The overhead of the algorithm is so small that it is effective even when there are only two objects. For more objects, the computation time of the ray-object intersection remains almost constant.", } @InProceedings{Hanrahan:1986:UCB, author = "Pat Hanrahan", title = "Using Caching and Breadth-First Search to Speed Up Ray-Tracing", year = "1986", month = may, booktitle = "Proceedings of Graphics Interface '86", publisher = "Canadian Information Processing Society", pages = "56--61", address = "Toronto, Ontario", keywords = "seed fill, coherence", } @Article{hall83a, author = "R. A. Hall and D. P. Greenberg", title = "A Testbed for Realistic Image Synthesis", pages = "10--20", journal = "IEEE Computer Graphics and Applications", volume = "3", number = "8", year = "1983", month = nov, keywords = "ray tracing cull, I37 Image Synthesis, I37 Surface Finish, shading, color", annote = "concerns shading and color more than ray tracing, but nice pictures! \\ As we have shown here, Cornell University's testbed image synthesis system has helped in the development of a number of improvements of existing ray-tracing techniques. In summary, these include a hybrid reflection model, a spectral-sampling method, the incorporation of light sources, and adaptive tree-depth control. Nevertheless, we point out again that many of the problems of realistic image generation through ray tracing have not been solved. The inherent point-sampling technique is prone to aliasing, the reflection models proposed do not include the correct energy formulations, and the computational expense is currently too high. The use of environmental image coherence techniques would probably make these approaches more tractable. It is our hope that the testbed imaging system will provide an appropriate environment for further exploration of these problems.", } InProceedings{Groller:1991:UTS, author = "E. Groller and W. Purgathofer", title = "Using Temporal and Spatial Coherence for Accelerating the Calculation of Animation Sequences", pages = "103--113", 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", } @InProceedings{Gigante:1988:ART, author = "Michael Gigante", title = "Accelerated Ray Tracing Using Non-Uniform Grids", pages = "157--163", booktitle = "Proceedings of Ausgraph '90", year = "1988", annote = "A new space-partitioning method for ray tracing complex environments is described in this paper. Elements of a scene are placed into a collection of non-hierarchical, variable-sized voxels. \\ The creation of this structure is the result of a simple pre-processing step. In a scheme similar to that used by uniform grid methods, the non-uniform grid can be traversed very efficiently. \\ Unlike uniform grid methods, this method generates voxels with approximately uniform density of primitives per voxel. Its performance is less sensitive to the type of scene and does not fail on scenes with local, high-density clusters of primitives.", } @Article{deb94, author = "M. De Berg and D. Halperin and M. Overmars and J. Snoeyink and M. Van Kreveld", title = "Efficient ray shooting and hidden surface removal", journal = "Algorithmica: An International Journal in Computer Science", volume = "12", number = "1", year = "1994", publisher = "Springer Verlag, New York", pages = "30--53", topic = "visibility", } @TechReport{Kreveld:1992:NRD, author = "M. J. van Kreveld", title = "New results on data structures in computational geometry", type = "Ph.{D}. {Dissertation}", institution = "Dept. Comput. Sci., Univ. Utrecht", address = "Utrecht, Netherlands", year = "1992", keywords = "doctoral thesis", } @TechReport{Rushmeier91-RMVR, author = "Holly E. Rushmeier", year = "1991", title = "Radiosity {Methods} for {Volume} {Rendering}", number = "GIT-GVU-91-01", publisher = "Graphics, Visualization and Usability Center", institution = "Georgia Institute of Technology", address = "Atlanata, GA", } @Article{Roth:1982:RCM, author = "Scott D. Roth", title = "Ray Casting for Modeling Solids", journal = "Computer Graphics and Image Processing", volume = "18", number = "2", pages = "109--144", month = feb, year = "1982", coden = "CGIPBG", ISSN = "0146-664X", bibdate = "Fri Feb 7 08:36:21 MST 1997", note = "Also in SIGGRAPH '87, '88, '89 Introduction to Ray Tracing course notes. The other classic ray tracing paper.", acknowledgement = ack-nhfb, annote = "the other classic ray tracing paper \\ This paper presents ray casting as the methodological basis for a CAD/CAM solid modeling system. Solid objects are modeled by combining primitive solids, such as blocks and cylinders, using the set operators union, intersection, and difference. To visualize and analyze the composite solids modeled, virtual light rays are cast as probes. By virtue of its simplicity, ray casting is reliable and extensible. The most difficult mathematical problem is finding line-surface intersection points. So surfaces such as planes, quadrics, tori, and probably even parametric surface patches may bound the primitive solids. The adequacy and efficiency of ray casting are issues addressed here. A fast picture generation capability for interactive modeling is the biggest challenge. New methods are presented, accompanied by sample pictures and CPU times, to meet the challenge.", classification = "723", journalabr = "Comput Graphics Image Process", keywords = "computer aided design; computer graphics; ray casting; ray tracing casting intersect CSG, tracing, hidden line, I35 ray casting for a CAD/CAM solid modeling system, CSG", } @PhdThesis{Pattanaik:1990:CMG, author = "Sumanta N. Pattanaik", title = "Computational Methods for Global Illumination and Visualisation of Complex 3{D} Environments", year = "1990", month = nov, school = "Birla Institute of Technology \& Science, Computer Science Department, Pilani, India", keywords = "adjoint illumination equations, particle model of light, random walk, importance sampling", } @Article{Pattanaik:1994:FWR, author = "S. N. Pattanaik and K. Bouatouch", title = "Fast Wavelet Radiosity Method", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "13", number = "3", pages = "C/407--C/420", month = "????", year = "1994", 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 = "Oslo, Norway; 12-16 Sept. 1994", conftitle = "15th Annual Conference and Exhibition. EUROGRAPHICS'94", corpsource = "Campus de Beaulieu, IRISA, Rennes, France", keywords = "computational geometry; Computer graphics; computer graphics; decomposition technique; hierarchical; Hierarchical decomposition technique; inner products; interpolating wavelets; Interpolating wavelets; interpolating wavelets; multidimensional; Multidimensional inner products; optimal adaptive subdivision; Optimal adaptive subdivision; ray tracing; wavelet analysis; Wavelet analysis; wavelet radiosity method; Wavelet radiosity method; wavelet transforms", thesaurus = "Computational geometry; Ray tracing; Wavelet transforms", treatment = "T Theoretical or Mathematical", } @InProceedings{Ferwerda:1997:MVM, author = "James A. Ferwerda and Sumanta N. Pattanaik and Peter Shirley and Donald P. Greenberg", title = "A Model of Visual Masking for Computer Graphics", booktitle = "SIGGRAPH 97 Conference Proceedings", editor = "Turner Whitted", series = "Annual Conference Series", year = "1997", organization = "ACM SIGGRAPH", publisher = "Addison Wesley", month = aug, pages = "143--152", note = "ISBN 0-89791-896-7", keywords = "visual perception, masking, image quality, error metrics", annote = "In this paper we develop a computational model of visual masking based on psychophysical data. The model predicts how the presence of one visual pattern affects the detectability of another. The model allows us to choose texture patterns for computer graphics images that hide the effects of faceting, banding, aliasing, noise and other visual artifacts produced by sources of error in graphics algorithms. We demonstrate the utility of the model by choosing a texture pattern to mask faceting artifacts caused by polygonal tesselation of a at-shaded curved surface. The model predicts how changes in the contrast, spatial frequency, and orientation of the texture pattern, or changes in the tesselation of the surface will alter the masking effect. The model is general and has uses in geometric modeling, realistic image synthesis, scientific visualization, image compression, and image-based rendering.", } @Article{Levoy:1990:ERT, author = "Marc Levoy", title = "Efficient Ray Tracing of Volume Data", journal = "ACM Transactions on Graphics", volume = "9", number = "3", pages = "245--261", month = jul, year = "1990", coden = "ATGRDF", ISSN = "0730-0301", bibdate = "Fri Jan 5 07:58:42 MST 1996", url = "http://www.acm.org/pubs/toc/Abstracts/0730-0301/78965.html", acknowledgement = ack-nhfb, annote = "{\em Volume Rendering} is a technique for visualizing sampled scalar or vector fields of three spatial dimensions without fitting geometric primitives to the data. A subset of these techniques generates images by computing 2-D projections of a colored semitransparent volume, where the color and opacity at each point are derived from the data using local operators. Since all voxels participate in the generation of each image, rendering time grows linearly with the size of the dataset. This paper presents a front-to-back image-order volume-rendering algorithm and discusses two techniques for improving its performance. The first technique employs a pyramid of binary volumes to encode spatial coherence present in the data, and the second technique uses an opacity threshold to adaptively terminate ray tracing. Although the actual time saved depends on the data, speedups of an order of magnitude have been observed for datasets of useful size and complexity. Examples from two applications are given: medical imaging and molecular graphics.", keywords = "algorithms; design; hierarchical spatial enumeration; medical imaging; molecular graphics; octree; performance; ray tracing; scientific visualization; volume rendering; volume visualization; voxel", subject = "{\bf I.3.3}: Computing Methodologies, COMPUTER GRAPHICS, Picture/Image Generation, Display algorithms. {\bf I.3.5}: Computing Methodologies, COMPUTER GRAPHICS, Computational Geometry and Object Modeling, Curve, surface, solid, and object representations. {\bf I.3.7}: Computing Methodologies, COMPUTER GRAPHICS, Three-Dimensional Graphics and Realism, Visible line/surface algorithms.", } @InProceedings{Heckbert92discon, author = "Paul S. Heckbert", title = "Discontinuity Meshing for Radiosity", booktitle = "Third Eurographics Workshop on Rendering", month = may, year = "1992", address = "Bristol, UK", pages = "203--216", keywords = "radiosity, adaptive mesh, visibility", } @InProceedings{hashimoto89a, author = "Akihiko Hashimoto and Taka-aki Akimoto and Kenji Mase and Yasuhito Suenaga", title = "Vista Ray-Tracing: High Speed Ray Tracing Using Perspective Projection Image", pages = "549--561", booktitle = "New Advances in Computer Graphics (Proceedings of CG International '89)", year = "1989", editor = "R. A. Earnshaw and B. Wyvill", publisher = "Springer-Verlag", annote = "This paper presents a new high speed algorithm of ray-tracing named Vista Ray-tracing. In Vista Ray-tracing, time consuming intensity calculations are done only for ``active'' pixels which really need precise ray-tracing, while the intensity of ``moderate'' pixels in calculated by interpolation. The perspective projection image, or Vista, is generated at the first stage to be used as a guide map in active pixel selection. In this paper, a new method for obtaining Vistas for CSG models of quadratic surface objects is presented as a key technology. A new texture mapping algorithm is also presented. Vista Ray-tracing is actually 16-75 times faster than standard ray-tracing, and can be even faster if other acceleration methods are employed. Consequently, Vista Ray-tracing is very useful for intermediate processes in making various images for TV animation, movies, high definition television, printing, etc.", } @Article{Hanrahan:1990:LSL, author = "Pat Hanrahan and Jim Lawson", editor = "Forest Baskett", title = "A Language for Shading and Lighting Calculations", journal = "Computer Graphics", volume = "24", number = "4", pages = "289--298", month = aug, year = "1990", coden = "CGRADI, CPGPBZ", ISSN = "0097-8930", conference = "held in Dallas, Texas; 6--10 August 1990", keywords = "shading language, little language, illumination, lighting, rendering", } @Article{Cook:1984:ST, author = "R. L. Cook", title = "Shade trees", journal = "Computer Graphics", volume = "18", number = "3", pages = "223--231", month = jul, year = "1984", coden = "CGRADI, CPGPBZ", ISSN = "0097-8930", annote = "Cook developed a special shade tree language for defining textures and coloration for objects. Interesting because it separates shading from the rest of rendering, and allows a library of surface types to be built up gradually. \\ Ray tracing is one of the most elegant techniques in computer graphics. Many phenomena that are difficult or impossible with other techniques are simple with ray tracing, including shadows, reflections, and refracted light. Ray directions, however, have been determined precisely, and this has limited the capabilities of ray tracing. By distributing the directions of the rays according to the analytic function they sample, ray tracing can incorporate fuzzy phenomena. This provides correct and easy solutions to some previously unsolved or partially solved problems, including motion blur, depth of field, penumbras, translucency, and fuzzy reflections. Motion blur and depth of field calculations can be integrated with the visible surface calculations, avoiding the problems found in previous methods.", conference = "held in Minneapolis, Minnesota; 23--27 July 1984", keywords = "texturing, procedural models, languages, I37 Shade Trees", } @Article{Goldfeather:1989:NRC, author = "Jack Goldfeather and Steven Molnar and Greg Turk and Henry Fuchs", title = "Near Real-Time {CSG} Rendering Using Tree Normalization and Geometric Pruning", journal = "IEEE Computer Graphics and Applications", volume = "9", number = "3", pages = "20--28", month = may, year = "1989", coden = "ICGADZ", ISSN = "0272-1716", bibdate = "Sat Jan 25 06:42:48 MST 1997", acknowledgement = ack-nhfb, affiliation = "Carleton Coll, Dep of Math, Northfield, MN, USA", classification = "723; 741; 921", journalabr = "IEEE Comput Graphics Appl", keywords = "Boolean Switching Functions; Computer Aided Design; Computer Aided Engineering; Computer Graphics --- Interactive; Constructive Solid Geometry (CSG); Geometric Pruning; Imaging Techniques; solid modeling; Surfaces; Tree Normalization", } @Article{Pavlidis:1990:RCS, author = "Theo Pavlidis", title = "Re: Comments on ``{Stochastic Sampling in Computer Graphics}''", journal = "ACM Transactions on Graphics", volume = "9", number = "2", pages = "233--236", month = apr, year = "1990", coden = "ATGRDF", ISSN = "0730-0301", bibdate = "Fri Jan 5 07:58:42 MST 1996", note = "See \cite{Cook:1986:SSC,Wold:1990:RCS}.", acknowledgement = ack-nhfb, } @InCollection{Whitted88, author = "Turner Whitted and Robert L. Cook", editor = "Kenneth I. Joy and Charles W. Grant and Nelson L. Max and Lansing Hatfield", title = "A Comprehensive Shading Model", booktitle = "Tutorial: Computer Graphics: Image Synthesis", pages = "232--43", publisher = "Computer Society Press", address = "Washington, DC", year = "1988", keywords = "shading", note = "also in SIGGRAPH '85 course notes \#11", } @Article{Cook:1986:SSC, author = "Robert L. Cook", title = "Stochastic Sampling in Computer Graphics", journal = "ACM Transactions on Graphics", volume = "5", number = "1", pages = "51--72", month = jan, year = "1986", coden = "ATGRDF", ISSN = "0730-0301", bibdate = "Thu Aug 25 23:39:28 1994", note = "See remarks \cite{Pavlidis:1990:RCS,Wold:1990:RCS}. Also in Tutorial: Computer Graphics: Image Synthesis, Computer Society Press, Washington, 1988, pp. 283--304.", url = "http://www.acm.org/pubs/toc/Abstracts/0730-0301/8927.html", acknowledgement = ack-nhfb, keywords = "algorithms; antialiasing; depth of field; filtering; image synthesis; Monte Carlo integration; motion blur; raster graphics; ray tracing; stochastic sampling", review = "ACM CR 8709-0784", subject = "{\bf I.3.3}: Computing Methodologies, COMPUTER GRAPHICS, Picture/Image Generation, Viewing algorithms. {\bf G.3}: Mathematics of Computing, PROBABILITY AND STATISTICS, Probabilistic algorithms (including Monte Carlo).", } @InProceedings{Torrance87a, author = "R. L. Cook and K. E. Torrance", title = "A Reflectance Model for Computer Graphics", year = "1987", editor = "W. Richards and S. Ullman", booktitle = "Image Understanding 1985--86", publisher = "Ablex", address = "Norwood, NJ", institution = "Cornell U", pages = "1--19", keywords = "IMAGE OUTPUT", } @TechReport{EVL-1996-11, author = "Andr{\'e} Hinkenjann and Markus Kubuk and Heinrich M{\"u}ller", title = "Answering Line Segment Intersection Queries Based On Sample Answers", number = "620/1996", type = "Research Report", institution = "University of Dortmund", address = "Universit{\"a}t Dortmund, 44221 Dortmund, Germany", month = aug, year = "1996", abstract = "Geometric query problems can be solved by preprocessing the answers for a representative set of sample queries. An arbitrary query is answered by the response of a closest sample query. In general, this answer will not be correct. A framework is presented in which the quality of approximation of this approach can be characterized. Futher, efficiency considerations are performed. They consist in empirical experiments for the classical line segment intersection query problem, but also in giving theoretical time and space bounds describing the trade-off between quality of approximation and computational complexity. Finally, approaches to the choice of favorable sample queries are discussed.", postscript-url = "ftp://euklid.informatik.uni-dortmund.de/pub/reports/ls7/rr-620.ps.gz", evlib-url = "http://infovis.zib.de:8000/Dienst/UI/2.0/Describe/evl.computationalgeometry%2FEVL-1996-11", evlib-revision = "1st", evlib-postscript-md5 = "14a18f6a52af153a3c3eb1c7037c344c", } @Article{Sbert:1997:OSS, author = "Mateu Sbert", title = "Optimal Source Selection in Shooting Random Walk {Monte Carlo} Radiosity", journal = "Com{\-}pu{\-}ter Graphics Forum", volume = "16", number = "3", pages = "C301--C308", month = sep # " 4--8", year = "1997", coden = "CGFODY", ISSN = "0167-7055", bibdate = "Tue Mar 17 15:44:38 MST 1998", acknowledgement = ack-nhfb, affiliation = "Universitat de Girona", affiliationaddress = "Girona, Spain", classification = "723.5; 741.1; 921.5; 922.1; 922.2", journalabr = "Comput Graphics Forum", keywords = "Computer graphics; Computer simulation; Lighting; Monte Carlo methods; Optimization; Probability; Radiosity; Rendering method", } @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", } @article{gt-drssp-97 , author = "M. T. Goodrich and R. Tamassia" , title = "Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations" , journal = "J. Algorithms" , volume = 23 , year = 1997 , pages = "51--73" , update = "97.07 smid" } @article{ekltmmv-rcerr-91 , author = "J. L. Ellis and G. Kedem and T. C. Lyerly and D. G. Thielman and R. J. Marisa and J. P. Menon and H. B. Voelcker" , title = "The ray casting engine and ray representations: a technical summary" , journal = "Internat. J. Comput. Geom. Appl." , volume = 1 , number = 4 , year = 1991 , pages = "347--380" , keywords = "mechanical CAD CAM, solid modeling, parallel computation, ray representation" } @inproceedings{cj-sersi-91 , author = "S. W. Cheng and R. Janardan" , title = "Space-efficient ray shooting and intersection searching: algorithms, dynamization and applications" , booktitle = "Proc. 2nd ACM-SIAM Sympos. Discrete Algorithms" , year = 1991 , pages = "7--16" , keywords = "ray tracing, dynamization, spanning trees of low stabbing number" } @article{cj-arsis-92 , author = "S. W. Cheng and R. Janardan" , title = "Algorithms for ray-shooting and intersection searching" , journal = "J. Algorithms" , volume = 13 , year = 1992 , pages = "670--692" , update = "93.09 smid" } @techreport{bf-vrs-90 , author = "R. Bar-Yehuda and S. Fogel" , title = "Variations on Ray Shooting" , type = "Technical {Report}" , number = 639 , institution = "Technion IIT" , address = "Haifa, Israel" , year = 1990 , keywords = "sheaf, ES-trees" , update = "95.01 smid, 93.09 milone+mitchell" } @inproceedings{af-acrsm-97 , author = "B. Aronov and S. Fortune" , title = "Average-Case Ray Shooting and Minimum Weight Triangulations" , booktitle = "Proc. 13th Annu. ACM Sympos. Comput. Geom." , year = 1997 , pages = "203--212" , update = "97.07 efrat" } @inproceedings{b-lsbsp-95 , author = "Mark de Berg" , title = "Linear Size Binary Space Partitions for Fat Objects" , booktitle = "Proc. 3rd Annu. European Sympos. Algorithms" , series = "Lecture Notes Comput. Sci." , volume = 979 , publisher = "Springer-Verlag" , year = 1995 , pages = "252--263" , update = "97.03 murali+schwarzkopf" } @inproceedings{bg-bspsc-94 , author = "M. de Berg and M. de Groot" , title = "Binary space partitions for sets of cubes" , booktitle = "Abstracts 10th European Workshop Comput. Geom." , nickname = "CG'94" , year = 1994 , pages = "84--88" , update = "94.05 schwarzkopf" } @inproceedings{bgo-nrbsp-94 , author = "M. de Berg and M. de Groot and M. Overmars" , title = "New results on binary space partitions in the plane" , booktitle = "Proc. 4th Scand. Workshop Algorithm Theory" , series = "Lecture Notes Comput. Sci." , volume = 824 , publisher = "Springer-Verlag" , year = 1994 , pages = "61--72" , update = "95.01 schwarzkopf+smid, 94.05 schwarzkopf" } @inproceedings{bgo-pbsp-93 , author = "M. de Berg and M. de Groot and M. Overmars" , title = "Perfect binary space partitions" , booktitle = "Proc. 5th Canad. Conf. Comput. Geom." , site = "Waterloo, Canada" , year = 1993 , pages = "109--114" , precedes = "bgo-pbsp-97" , update = "97.03 devillers, 93.09 milone+mitchell" } @article{bgo-pbsp-97 , author = "M. de Berg and M. de Groot and M. Overmars" , title = "Perfect binary space partitions" , journal = "Comput. Geom. Theory Appl." , volume = 7 , year = 1997 , pages = "81--91" , succeeds = "bgo-pbsp-93" , update = "97.03 devillers" } @article{py-ebsph-90 , author = "M. S. Paterson and F. F. Yao" , title = "Efficient binary space partitions for hidden-surface removal and solid modeling" , journal = "Discrete Comput. Geom." , volume = 5 , year = 1990 , pages = "485--503" , succeeds = "py-bpahs-89" } @inproceedings{py-obspo-90 , author = "M. S. Paterson and F. F. Yao" , title = "Optimal binary space partitions for orthogonal objects" , booktitle = "Proc. 1st ACM-SIAM Sympos. Discrete Algorithms" , year = 1990 , pages = "100--106" , precedes = "py-obspo-92" } @article{py-obspo-92 , author = "M. S. Paterson and F. F. Yao" , title = "Optimal binary space partitions for orthogonal objects" , journal = "J. Algorithms" , volume = 13 , year = 1992 , pages = "99--113" , succeeds = "py-obspo-90" } @inproceedings{l-hmelr-83 , author = "A. Lingas" , title = "Heuristics for minimum edge length rectangular partitions of rectilinear figures" , booktitle = "Proc. 6th GI Conf. Theoret. Comput. Sci." , series = "Lecture Notes Comput. Sci." , volume = 145 , publisher = "Springer-Verlag" , year = 1983 , pages = "199--210" , keywords = "design of algorithms, VLSI design, length, partition, approximation, polygons, geometric graphs, rectangles" } @incollection{s-ghsgc-83 , author = "K. J. Supowit" , title = "Grid heuristics for some geometric covering problems" , editor = "F. P. Preparata" , booktitle = "Computational Geometry" , series = "Adv. Comput. Res." , volume = 1 , publisher = "JAI Press" , address = "Greenwich, CT" , year = 1983 , pages = "215--233" , keywords = "balls, $d$-dimensional, covering, heuristics" } @inproceedings{lls-nohbs-87 , author = "C. Levcopoulos and A. Lingas and J.-R. Sack" , title = "Nearly optimal heuristics for binary search trees with geometric generalizations" , booktitle = "Proc. 14th Internat. Colloq. Automata Lang. Program." , series = "Lecture Notes Comput. Sci." , volume = 267 , publisher = "Springer-Verlag" , year = 1987 , pages = "376--385" , keywords = "decomposition, partition, polygons, two-dimensional" } @article{dz-hmlrp-90 , author = "D. Du and Y. Zhang" , title = "On heuristics for minimum length rectilinear partitions" , journal = "Algorithmica" , volume = 5 , year = 1990 , pages = "111--128" } ceedings{l-fhmlr-86 , author = "C. Levcopoulos" , title = "Fast heuristics for minimum length rectangular partitions of polygons" , booktitle = "Proc. 2nd Annu. ACM Sympos. Comput. Geom." , year = 1986 , pages = "100--108" , cites = "cd-vdbcd-85, f-fapct-85, gz-bprp-85, ia-dsisa-84, ks-mdpo-85, k-ubsir-80, ll-blcpp-84, l-hmelr-83, lprs-melpr-82, l-tspp-77, ps-cgi-85, r-ppis-82, ZZZ" , update = "97.11 bibrelex" } @article{lls-hobst-89 , author = "Christos Levcopoulos and Andrzej Lingas and Jorg-R. Sack" , title = "Heuristics For Optimum Binary Search Trees And Minimum Weight Triangulation Problems" , journal = "Theoret. Comput. Sci." , volume = 66 , number = 2 , month = aug , year = 1989 , pages = "181--203" , keywords = "optimum binary search trees, minimum weight triangulation, amortization argument" , annote = "Amortized linear algorithm for GT of semi-circular polygons." , abstract = "We establish new bounds on the problem of constructing optimum binary search trees with zero-key access probabilities (with applications e.g. to point location problems). We present a linear-time heuristic for constructing such trees so that their cost is within a factor of 1 plus epsilon from the optimum cost, where epsilon is an arbitrary positive constant. Furthermore, by using an interesting amortization argument, we give a simple and practical, linear-time implementation of a known greedy heuristics for such trees. The above results are obtained in a more general setting, namely, in the context of minimum length triangulations of so- called semi-circular polygons. They are carried over to binary search trees by proving a duality between optimum (m minus 1)-way search trees and minimum weight partitions of infinitely-flat semi-circular polygons into m- gons. With this duality we can also obtain better heuristics for minimum length partitions of polygons by using known algorithms for optimum search trees. (Author abstract) 14 Refs." } @article{dr-hmrst-93 , author = "C. C. {De Souza} and C. C. Ribeiro" , title = "Heuristics for the minimum rectilinear {Steiner} tree problem: new algorithms and a computational study" , journal = "Discrete Appl. Math." , volume = 45 , number = 3 , year = 1993 , pages = "205--220" , keywords = "Steiner tree, $L_{1}$ metric, heuristics" , update = "95.09 korneenko" } @InProceedings{Bar-Yehuda90, author = "R. Bar-Yehuda and S. Fogel", title = "Good splitters with applications to ray shooting", booktitle = "Proc. 2nd Canad. Conf. Comput. Geom.", pages = "81--84", year = "1990", keywords = "computational geometry, arrangements", } @InProceedings{Edelsbrunner91, author = "Herbert Edelsbrunner and Bernard Chazelle and Michelangelo Grigni and Leonidas Guibas and John Hershberger and Misha Sharir and Jack Snoeyink", title = "Ray Shooting in Polygons Using Geodesic Triangulations", booktitle = "Proc. 18th Internat. Colloq. Automata Lang. Program., Lecture Notes in Computer Science{"} series no. 150", pages = "661--673", publisher = "Springer-Verlag", year = "1991", keywords = "computational geometry, simple polygon, geodesics", note = "also as Princeton University, Computer Science Department, TR-350-91, Sept. 1991", } @TechReport{Guibas89, author = "L. Guibas and M. Overmars and M. Sharir", title = "Ray shooting, implicit point location, and related queries in arrangements of segments{"}", institution = "Dept. Comput. Sci., New York Univ.", number = "433", address = "New York, NY", month = mar, year = "1989", keywords = "random sampling, arrangements, point location", } @Article{Matousek93, author = "J. Matousek", title = "On Vertical Ray Shooting in Arrangements", journal = "Comput. Geom. Theory Appl.", volume = "2", number = "5", pages = "279--285", month = mar, year = "1993", keywords = "computational geometry, zone theorem, cutting, hyperplane arrangement", note = "update = 93.09 Held+Matousek+Milone+Mitchell", } @Article{bronsvoort84b, author = "Willem F. Bronsvoort and Jarke J. van Wijk and Frederik W. Jansen", title = "Two Methods for Improving the Efficiency of Ray Casting in Solid Modeling", pages = "110--116", journal = "Computer-Aided Design", volume = "16", number = "1", year = "1984", month = jan, keywords = "CSG, I35 Ray Tracing, I35 Solid Modeling", annote = "enhancements to Roth: scanline interval enclosures, CSG tree optimization, and recursive screen subdivision \\ In solid modelling based on constructive solid geometry and primitive instancing, ray casting is a very suitable technique for visualization of models on a raster display. In its present form, it is, however, too inefficient for interactive use. \\ Two methods for improving the efficiency are given here. The first uses scan-line interval enclosures instead of box enclosures, and also bypasses non-contributing nodes during each traversal of the CSG (constructive solid geometry) tree. The second refines the image step by step by subdivision, thereby avoiding explicit computation of the intensities of many pixels of the image. The second method reduces computing time more than the first, but has the disadvantage that slivers may occasionally be lost from the image.", } @Article{tvcg-1996-22, author = "Daniel Cohen-Or and Eran Rich and Uri Lerner and Victor Shenkar", email = "daniel@math.tau.ac.il and none and none and none", title = "A Real-Time Photo-Realistic Visual Flythrough", journal = "IEEE Transaction on Visualization and Computer Graphics", volume = "2", number = "3", month = sep, year = "1996", pages = "255--264", abstract = "In this paper we present a comprehensive flythrough system which generates photo-realistic images in true real-time. The high performance is due to an innovative rendering algorithm based on a discrete ray casting approach, accelerated by ray coherence and multiresolution traversal. The terrain as well as the 3D objects are represented by a textured mapped voxel-based model. The system is based on a pure software algorithm and is thus portable. It was first implemented on a workstation and then ported to a general-purpose parallel architecture to achieve real-time performance.", keywords = "Terrain visualization, parallel rendering, flight simulator, visual simulations, voxel-based modeling, ray casting", tvcg-abstract-url = "http://www.computer.org/pubs/tvcg/abs96.htm#255tg0996", } @InProceedings{dadoun85a, author = "Nou Dadoun and David G. Kirkpatrick and John P. Walsh", title = "The Geometry of Beam Tracing", booktitle = "Proceedings of the ACM Symposium on Computational Geometry", pages = "55--61", year = "1985", month = jun, annote = "the use of BSP trees and hierarchical bounding volumes for fast beam intersection testing. \\ A solution to the hidden surface elimination problem called beam tracing is described. Beam tracing is related to ray tracing but uses spatial coherence within the scene, and area coherence within the image to batch computations. Beam tracing is an object space solution to the hidden surface problem. \\ Beam tracing is formulated in terms of its principal subprocesses: intersection, sorting, and clipping. A hierarchical scene representation is proposed. This incorporates the space decomposition idea of the BSP tree [Fuchs, Kedem, and Naylor, 80] along with the convex polytope intersection detection technique of [Dobkin and Kirkpatrick, 83] to interleave and efficiently solve the intersection and sorting subproblems of beam tracing.", } @InBook{kaplan85a, author = "M. Kaplan", title = "Space-Tracing: {A} Constant Time Ray-Tracer", pages = "149--158", booktitle = "SIGGRAPH '85 State of the Art in Image Synthesis seminar notes", year = "1985", month = jul, keywords = "ray tracing cull", } @Book{Samet90, author = "Hanan Samet", title = "Applications of Spatial Data Structures", publisher = "Addison-Wesley", address = "Reading, Mass.", year = "1990", keywords = "quadtree, octree, radiosity", note = "chapter on ray tracing and efficiency, also discusses radiosity", } @InProceedings{glassner88d, author = "Andrew S. Glassner", title = "Space Subdivision for Fast Ray Tracing", pages = "159--167", booktitle = "Tutorial: Computer Graphics: Image Synthesis", year = "1988", editor = "Kenneth I. Joy and Charles W. Grant and Nelson L. Max and Lansing Hatfield", publisher = "Computer Society Press", annote = "We have seen that the infamous slowness of ray-tracing techniques is caused primarily by the time required for ray-object intersection calculations. We have also seen a new way of tracing the ray through small subsets of space at a speed that reduces the number of ray-object intersections that must be made, thereby cutting the overall ray-tracing time considerably. \\ This new algorithm makes possible the ray tracing of complex scenes by medium- and small-scale computers. It is hoped that this will enable the power of ray tracing to be embraced by more people, helping them generate pictures at the leading edge of computer graphics.", } @TechReport{fussell88a, author = "Donald Fussell and K. R. Subramanian", title = "Fast Ray Tracing Using {K}-{D} Trees", institution = "U. of Texas, Austin, Dept. Of Computer Science", type = "Technical Report", number = "TR-88-07", month = mar, year = "1988", keywords = "hierarchies", } @PhdThesis{subramanian90a, author = "K. R. Subramanian", title = "Adapting Search Structures to Scene Characteristics for Ray Tracing", month = dec, year = "1990", type = "Ph.D. Thesis", school = "Department of Computer Sciences, University of Texas at Austin", annote = "We present new results in adapting search structures to scene characteristics for improving the performance of ray tracing. A cost model is developed for evaluating search structures currently being used in ray tracing. The model has been successfully used to terminate search structure construction, thus making it unnecessary to set termination parameters in advance. The model has also been used with limited success to compare the performance of different search structures for a given scene. \\ A detailed experimental study of some of the important properties of search structures has been performed. This has resulted in a new adaptive search structure that is based on {\em k-d} trees, a multi-dimensional binary search structure which outperforms existing methods. Its high performance is primarily due to the fact that it combines the advantages of such structures based on space partitioning and those based on bounding volumes. The greater flexibility of this search structure allows it to terminate automatically at a point where further subdivision would result in no additional benefits. \\ Finally, this search structure has been used to render volume models from scientific applications such as medical imaging and molecular modeling. Its advantages over traditional volume rendering techniques have been demonstrated.", } @TechReport{subramanian90b, author = "K. R. Subramanian and Donald Fussell", title = "A Cost Model for Ray Tracing Hierarchies", institution = "U. of Texas, Austin, Dept. Of Computer Science", type = "Technical Report", number = "TR-90-04", month = mar, year = "1990", keywords = "hierarchies", } @TechReport{Subramanian:1990:FAP, author = "K. R. Subramanian and Donald Fussell", title = "Factors Affecting Performance of Ray Tracing Hierarchies", year = "1990", month = jul, number = "R-90-21", type = "Technical Report", institution = "Dept. of Computer Sciences, Univ. of Texas at Austin", keywords = "octree", } @Article{Vanecek:1991:BIM, author = "G. {Vanecek, Jr.}", title = "Brep-index: a multidimensional space partitioning tree", journal = "Internat. J. Comput. Geom. Appl.", volume = "1", number = "3", year = "1991", pages = "243--261", keywords = "classification, Brep, BSP tree, data structures", } @PhdThesis{semwal87a, author = "S. K. Semwal", title = "The Slicing Extent Technique for Fast Ray Tracing", year = "1987", type = "Ph.D. Thesis", school = "Department of Computer Science, University of Central Florida", annote = "A new technique for image generation using ray tracing is introduced. The `Slicing Extent Technique'' (SET) partitions object space with slicing planes perpendicular to all three axes. Planes are divided into two dimensional rectangular cells, which contain pointers to nearby objects. \\ Cell size and the space slices varies, and is determined by the objects' locations and orientations. Unlike oct-tree and other space-partitioning methods, SET is not primarily concerned with dividing space into mutually exclusive volume elements (Voxels') and identifying objects within each voxel. Instead, SET is based on analysis of projections of objects onto slicing planes. \\ In comparison to the existing space subdivision methods for ray tracing, SET avoids tree traversal and exhibits no anomalous behavior. There is no reorganization when new objects arrive. Preprocessing to create slices is inexpensive and produces a finely tuned filter mechanism which supports rapid ray tracing.", } @TechReport{semwal86a, author = "S. K. Semwal and J. M. Moshell", title = "Geometric Issues of the Slicing Extent Technique for Ray Tracing", year = "1986", type = "Technical Report", number = "CS-TR-86-17", institution = "Department of Computer Science, University of Central Florida", annote = "We introduce a new technique for image generation using ray tracing. The `Slicing Extent Technique'' (SET) partitions object space with slicing planes perpendicular to all three axes. Planes are dividied into two dimensional rectangular cells, which contain pointers to nearby objects. \\ Cell size and the space between slices varies, and is determined by objects' locations and orientations. Unlilke oct-tree and other space partitioning methods, SET is not primarily concerned with dividing space into mutually exclusive volume elements (oxels') and identifying objects within each voxel. Instead, SET is based on analysis of projections of objects onto slicing planes. \\ The analysis of projections onto planes leads to an interesting geometric problem of `marking the cells'' on the various planes so that no ray-object intersection goes undetected. In this paper, we show that our method of `marking the cells'' for spheres and polyhedras is sufficient in this sense. The nature of these extents is analyzed. \\ In comparison to the existing methods for ray tracing, SET avoids tree traversal. Preprocessing to create slices is inexpensive and produces a finely tuned filter mechanism which supports rapid ray tracing. \\ SET resembles other efforts to speed up ray tracing inasmuch as a two step process is used. First, an approximate `filter'' technique eliminates most possible ray/object collisions. Then an accurate computation evaluates the remaining possible collisions and provides information for the generation of subsequent rays.", } @Article{jevans89b, author = "David Jevans and Brian Wyvill", title = "Adaptive voxel subdivision for ray tracing", pages = "164--172", journal = "Proceedings of Graphics Interface '89", year = "1989", month = jun, conference = "held in London, Ontario; 19-23 June 1989", keywords = "spatial subdivision, octree", annote = "Although regular subdivision has been shown to be efficient at ray tracing scenes where objects are evenly distributed, such algorithms perform poorly when objects are concentrated in a small number of voxels. In this paper, a method is presented where voxels in a regular grid are examined and recursively subdivided depending on object density. This integration of regular and adaptive spatial subdivision methods allows images consisting of large regularly distributed objects and small dense objects to be ray traced efficiently. The parameters controlling the coarseness of the voxel grid, depth of adaptive subdivision trees, and maximum number of polygons per voxel are varied and their effects on execution time, subdivision time, and memory use are measured.", } @InProceedings{Jevans:1990:RTS, author = "David A. J. Jevans", title = "Ray tracing scenes of varying local complexity", booktitle = "Proceedings of the 1990 Western Computer Graphics Symposium", year = "1990", month = mar, conference = "held in Banff, Alberta; 4-8 March 1990", keywords = "space subdivision, adaptive, cost function", } @InProceedings{Nemoto:1986:ASS, author = "Keiji Nemoto and Takao Omachi", title = "An Adaptive Subdivision by Sliding Boundary Surfaces for Fast Ray Tracing", pages = "43--48", booktitle = "Proceedings of Graphics Interface '86", year = "1986", month = may, editor = "M. Green", conference = "held in Vancouver, B.C.; 26-30 May 1986", keywords = "adaptive subdivision algorithm on a parallel architecture, parallel processing", annote = "They describe a dynamic load-balanced ray tracer. One of the first load-balanced ray tracers. \\ This paper presents an adaptive subdivision algorithm for fast ray tracing implemented on parallel architecture using a three dimensional computer array. The object space is divided into several subregions and boundary surfaces for the subregions are adaptively slid to redistribute loads of the computers uniformly. Since the shape of the subregions is preserved as orthogonal parallelepiped the redistribution overhead can be kept small. The algorithm is quite simple but can avoid load concentration to a particular computer. \\ Simulation results reveal that the adaptive space subdivision algorithm by sliding boundary surfaces reduces the computing time to 3/4 - 1/5 as much as that for the conventional space subdivision algorithm with no redistribution, which reduces the computing time almost proportionally to the number of computers.", } @MastersThesis{Jevans90, author = "David Jevans", title = "Adaptive Voxel Subdivision for Ray Tracing", school = "Dept. of Computer Science, Univ. of Calgary", type = "Master's Thesis", year = "1990", keywords = "grid subdivision, hierarchical subdivision", note = "long version of paper", } @TechReport{naylor86a, author = "Bruce Naylor and William Thibault", title = "Application of {BSP} Trees to Ray-Tracing and {CGS} Evaluation", institution = "Georgia Institute of Tech., School of Information and Computer Science", type = "Technical Report", address = "Atlanta, Georgia", number = "GIT-ICS 86/03", month = feb, year = "1986", keywords = "hierarchies, BSP tree, CSG", note = "true BSP-trees (not just generalized octrees) used for efficiency", } @MastersThesis{lin87a, author = "Jimmy Jih-Ming Lin", title = "Fast Ray Tracing on {BSP}-Trees", year = "1987", type = "M.Sc. Thesis", school = "Department of Computer Science, University of Central Florida", keywords = "hierarchies", annote = "Based on these analyses and experiments, the BSP-Trace Method may not be the best solution for speeding up the ray tracing, but it is worthwhile subject for research. The potential drawbacks of the BSP-Trace which make it no better than the Octree Method are: \\ (1) The number of surfaces on the BSP-Tree is typically far more than the original number of surfaces, because of the splitting of surfaces into two by other surfaces' planes; \\ (2) The Octree Method only needs to test those objects which reside in the selected voxels, and the BSP-Trace needs to consider the objects in the whole half-space. \\ [FUJI86] mentioned that the memory requirement for the octree is very costly, but for the BSP-Tree, it can be taken care of very efficiently. The bottleneck of the Octree Method is the time spent on traveling up and down the Octree [FUJI86], and our experiments show that this time is around 35\% of the total time. The solution to reduce the traveling time is to lower the height of the octree, but meanwhile the increase in the number of objects contained in the voxel means more intersections per ray. Thus, a new data structure for fast ray tracing which combines the Octree and BSP-Tree is proposed. \\ The new data structure contains an octree on the top, and every leaf voxel consists of a BSP-Tree. This will cut down both the tree traveling time (by lowering the tree height) and the memory consumed by the octree. Also, if we can keep the number of objects inside the voxel down, the increased number of surfaces by using the BSP-Tree is limited. This thus will reduce the number of intersection tests made inside the voxel.", } @InProceedings{devillers89b, author = "Olivier Devillers", title = "Tools to Study the Efficiency of Space Subdivision Structures for Ray Tracing", pages = "467--481", booktitle = "Proceedings of the PIXIM '89", year = "1989", annote = "Space Subdivision structures are often used to improve the performance of ray tracing. The subject of this article is to study theoretically the effects of the subdivision on the CPU time. The average number of regions crossed by a ray is calculated in several cases of subdivision. \\ With a space subdivision scheme, the complexity of ray tracing is due to two main factors: computation of the intersections within a region, and computation of the sequence of regions intersected by a given ray. The complexity of these two points is studied. The distribution of the objects among the regions is evaluated, and a method to compute the average number of regions crossed by a ray for a given method of subdivisions is proposed. This method is applied to some usual space subdivision techniques: octree, bounding boxes, grid, and macro-regions.", } @InProceedings{dAmore:1992:OBP, author = "F. d'Amore and P. G. Franciosa", title = "On the optimal binary plane partition for sets of isothetic rectangles", booktitle = "Proc. 4th Canad. Conf. Comput. Geom.", year = "1992", pages = "1--5", } @InProceedings{Chin:1992:FOP, author = "Norman Chin and Steven Feiner", title = "Fast object-precision shadow generation for areal light sources using {BSP} trees", pages = "21--30", booktitle = "Computer Graphics (1992 Symposium on Interactive 3D Graphics)", volume = "25", number = "2", year = "1992", month = mar, editor = "David Zeltzer", conference = "held in Boston; 29 March - 1 April 1992", keywords = "shadow volume, area light source, penumbra, umbra", annote = "", } @InProceedings{Chrysanthou:1995:SVB, author = "Yiorgos Chrysanthou and Mel Slater", title = "Shadow Volume {BSP} Trees for Computation of Shadows in Dynamic Scenes", editor = "Pat Hanrahan and Jim Winget", pages = "45--50", booktitle = "1995 Symposium on Interactive {3D} Graphics", year = "1995", organization = "ACM SIGGRAPH", month = apr, note = "ISBN 0-89791-736-7", } @MastersThesis{macdonald88a, author = "David MacDonald", title = "Space Subdivision Algorithms for Ray Tracing", year = "1988", type = "M.Sc. Thesis", school = "Department of Computer Science, University of Waterloo", annote = "Ray tracing provides computer rendering of synthetic images with many realistic qualities, but is computationally expensive. Ray tracing requires testing of rays against a scene to see which objects, if any, are intersected. The high number of such tests required by typical ray tracers contributes significantly to the computational expense of ray tracing. \\ An efficient method of reducing the computation involved in the intersection tests is to organize the objects composing the scene into one of several types of hierarchical data structures. \\ This thesis describes algorithms for the construction, storage, and traversal of the space subdivision hierarchy. Methods are suggested for decreasing computational requirements of the data structure with respect to these three areas. \\ One suggested strategy for improving performance in all three areas (construction, storage, and traversal) is implemented for the bintree structure. The performance of these simulations is compared with implementations of contemporary methods and some efficiency gains are shown. \\ Further work is suggested, including adaptation of some of the ideas presented within this thesis to more general types of hierarchical structures.", } @TechReport{Quek:1988:ESS, author = "Lee Hian Quek and D. D. Hearn", title = "Efficient Space-Subdivision Methods in Ray-Tracing Algorithms", year = "1988", month = nov, number = "UIUCDCS-R-88-1468", type = "Report No.", institution = "Dept. of Computer Science, Univ. of Illinois at Urbana-Champaign", keywords = "efficiency", anote = "Ray tracing provides a simple and powerful tool for the generation of highly realistic displays. However, it is a computationally expensive approach. A basic ray-tracing algorithm employing no antialiasing may require several hours to render a scene of moderate complexity. Methods for attaining higher picture quality, such as supersampling, adaptive sampling, and distributed sampling, require even longer ray-processing times. One method for improving the performance of ray-tracing algorithms is to reduce ray-object intersection calculations by employing spatial subdivision techniques to group objects in a scene. Here, we consider some improvements that can be made to space-subdivision ray tracers by reducing ray-traversal calculations and by implementing the algorithms on parallel vector architectures.", } @Book{Semwal:1992:RTU, author = "Sudhanshu Kumar Semwal and Charulata K. Kearney and J. Michael Moshell", title = "Ray Tracing Using the Slicing Extent Technique", year = "1992", publisher = "International Conference on 3D Graphics (?)", anote = "We present a novel approach to ray tracing called the Slicing Extent Technique (SET) and its variations. SET partitions object space with slicing planes perpendicular to all three axes. Slicing planes are divided into two dimensional rectangular cells, which contain pointers to nearby objects. The novelty of SET is that rather than using a collection of volumes as an extent, SET uses a collection of planar cells and is based on analysis of projections of objects onto slicing planes. These rectangular cells are used to quickly traverse through the sparse area of the scene and also provide further subdivision in the highly populated dense area. These 2D cells can also define tighter extents. In comparison to the existing space subdivision techniques for ray tracing, SET avoids tree traversal and multiple ray-object intersections. It guarantees no increase in image generation time when number of cells per slice increase in multiples of four. There is no reorganization when new objects arrive and preprocessing to create slices is inexpensive.", } TechReport{Wilson92b, author = "Tom Wilson and Narsingh Deo", title = "Extent Tracing: Algorithm and Implementation", institution = "Department of Computer Science, University of Central Florida", type = "Technical Report", number = "CS-TR-92-34", month = dec, year = "1992", keywords = "efficiency", anote = "This paper describes a new ray tracing acceleration algorithm called extent tracing. The algorithm works on a structure that is conceptually related to a hierarchical tree of extents (HTE), but does not require the hierarchy. To speed up extent tracing, spatial subdivision is added, resulting in a nonuniform subdivision grid. Implementation details and the results of comparisons to some other established acceleration techniques are given.", } @TechReport{Wilson92, author = "Tom Wilson and Narsingh Deo", title = "Comparing Extent Tracing to Other Ray Tracing Accelerators", institution = "Department of Computer Science, University of Central Florida", type = "Technical Report", number = "CS-TR-92-21", month = sep, year = "1992", keywords = "efficiency", anote = "This report examines the feasibility of a new ray-tracing acceleration scheme called extent tracing by comparing it to some established techniques on established benchmark scenes. The other techniques implemented for comparison are binary space-partitioning (BSP) tree, hierarchical tree of extents (HTE), octree, and uniform subdivision. The statistics used in the comparison are the execution times, memory requirements, object intersections per ray, bounding volume intersections per ray, and voxels traversed per ray.", } @TechReport{Wilson92a, author = "Tom Wilson and Narsingh Deo", title = "Acceleration Schemes for Ray Tracing", institution = "Department of Computer Science, University of Central Florida", type = "Technical Report", number = "CS-TR-92-22", month = sep, year = "1992", keywords = "efficiency", } @InProceedings{Speer:1985:TEA, author = "L. R. Speer and T. D. Derose and B. A. Barsky", title = "A Theoretical and Empirical Analysis of Coherent Ray-Tracing", booktitle = "Graphics Interface '85 Proceedings", pages = "1--8", year = "1985", editor = "M. Wein and E. M. Kidd", organization = "Canadian Inf. Process. Soc.", conference = "held in Montreal, Quebec, Canada; 27--31 May 1985", keywords = "I37 ray-tracing, I37 image synthesis, I30 picture processing", annote = "The use of {\em coherence} has been advocated as a means of reducing the large computational cost of the ray-tracing method of image synthesis. This paper examines the theoretical and empirical performance of a typical coherent ray-tracing algorithm, one that exploits the similarity between the intersection trees generated by successive rays. It is shown that despite the large degree of coherence present in a scene, the need to ensure the validity of ray-object intersections prevents any significant computational savings. This indicates that other algorithmic methods must be used in order to substantially reduce the computational cost of ray-traced imagery.", } @InProceedings{Isler:1991:HSS, author = "Veysi Isler and Cevdet Aykanat and Bulent {\"{O}}zgu\c{c}", title = "A heuristic 3{D} space subdivision algorithm for ray tracing", pages = "499--504", booktitle = "COMPUGRAPHICS '91", volume = "I", year = "1991", conference = "held in Sesimbra, Portugal; 16-20 September 1991", } @Article{Bouville??, author = "Christian Bouville and Jean-Luc Dubois and Isabelle Marchal", title = "A Space Tracing Method Applied to Polygonal Models", journal = "course paper", year = "???", anote = " The ray-tracing rendering method gives the highest possible level of realism that can be attained in computer graphics. Recently many alternatives have been reported on ways to speed up this process and particularly by means of a space subdivision technique. We propose such an algorithm specially adapted to polygonal models. A BSP tree technique is used to perform space subdivision and a spatial index allows direct access to any cell. A method which minimizes primary ray computations and an algorithm which avoids the tracing of a large number of rays towards light sources have been studied. Results about time and space required by this algorithm are presented.", } @Article{Kalinowski94, author= "Kalinowski J. and Sas J.", title= "Acceleration Techniques for Ray Tracing - Experimental Comparison", journal= "MICROCOMPUTER '94 Computer Graphics and Vision", month = "feb", year = "1994", pages = "??-??", place = "Zakopane in Poland", note = "uniform subdivision", anote = "In this paper the experimental results of applying a series of acceleration methods to the ray tracing process are presented. The acceleration possibilities at two stages have been distinguished: the stage of ray traversal through the scene space and ray-triangle intersection testing stage. At the first stage uniform space subdivision has been compared with two level n-tree schema. At the stage of ray-triangle intersection testing the computational complexity of the set of algorithms has been compared and the gains obtained as a result of a series of improvements to the ordinary algorithm are presented.", } @article{vko91, author="M. van Kreveld and H. Overmars", title="Divided k-d Trees", journal="Algorithmica", year="1991", volume="6", number="", pages="840-858" }