source: trunk/VUT/doc/SciReport/Bib/want.bib @ 243

@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"
}