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

Revision 243, 95.5 KB checked in by bittner, 19 years ago (diff)

SciReport? template

Line 
1@article{bb9633,
2        AUTHOR = "Upstill, S.",
3        TITLE = "The Renderman Companion, Addison-Wesley, Reading",
4        JOURNAL = "MA",
5        VOLUME = "89",
6        YEAR = "1989",
7        PAGES = "1989"
8}
9
10@inproceedings{BerDobEpp-SODA-90,
11  title = {{Visibility with a moving point of view}},
12  author = {Marshall W. Bern and David P. Dobkin and David Eppstein and Robert L. Grossman},
13  booktitle = {Proc. 1st Symp. Discrete Algorithms},
14  publisher = {Assoc. Comput. Mach. and Soc. Industrial {\&} Applied Mathematics},
15  pages = {107--118},
16  month = {January},
17  year = {1990}
18}
19
20@article{BerDobEpp-Algo-94,
21  title = {{Visibility with a moving point of view}},
22  author = {Marshall W. Bern and David P. Dobkin and David Eppstein and Robert L. Grossman},
23  journal = {Algorithmica},
24  volume = {11},
25  number = {4},
26  pages = {360--378},
27  month = {April},
28  year = {1994},
29  review = {MR-94j:68307}
30}
31
32@article{MR-94j:68307,
33  author = {Marshall W. Bern and David P. Dobkin and David Eppstein and Robert L. Grossman},
34  reviews = {BerDobEpp-Algo-94},
35  journal = {Mathematical Reviews},
36  publisher = {Amer. Math. Soc.},
37  title = {{Visibility with a moving point of view}},
38  number = {94j:68307},
39  year = {1994}
40}
41
42@article{ma4,
43  author="J. Matousek",
44  title="Efficient partition trees",
45  journal="Discrete and Computational Geometry",
46  year="1992",
47  volume="8",
48  number="",
49  pages="315-334"
50}
51
52@inproceedings{ma92acm,
53  author="J. Matousek",
54  title="Range searching with efficient hierarchical cuttings",
55  booktitle="$8^{th}$ ACM Conf. in Comp. Geom.",
56  address="Berlin",
57  year="1992",
58  pages="276-285"
59}
60
61@article
62 {ma1,
63  author="J. Matousek",
64  title="Range searching with efficient hierarchical cuttings",
65  journal="Discrete and Computational Geometry",
66  year="1993",
67  volume="10",
68  number="",
69  pages="157-182"
70}
71
72@Article{Matousek95,
73title={Approximations and Optimal Geometric Divide-and-Conquer},
74author={Ji{\v{r}}{\'\i} Matou{\v{s}}ek},
75pages={203--208},
76journal=jcss,
77year=1995,
78month=apr,
79volume=50,
80number=2,
81preliminary={STOC::Matousek1991}
82}
83
84@Article{Adelson:1995:GER,
85  author =       "Stephen J. Adelson and Larry F. Hodges",
86  title =        "Generating Exact Ray-Traced Animation Frames by
87                 Reprojection",
88  journal =      "j-IEEE-CGA",
89  volume =       "15",
90  number =       "3",
91  pages =        "43--52",
92  month =        may,
93  year =         "1995",
94  CODEN =        "ICGADZ",
95  ISSN =         "0272-1716",
96  bibdate =      "Sat Jan 25 06:42:48 MST 1997",
97  bibsource =    "Compendex database",
98  acknowledgement = ack-nhfb,
99  affiliation =  "Comput. Res. and Applications, Los Alamos Nat. Lab.,
100                 NM, USA",
101  classification = "723; 723.5; 741.1; 742.2",
102  journalabr =   "IEEE Comput Graphics Appl",
103  keywords =     "Algorithms; Animation; Animation frames; Cameras;
104                 Color; Color image processing; Computer graphics;
105                 Interactive animation; Light sources; Ray tracing;
106                 Reprojection; Spatiotemporal coherence; Three
107                 dimensional; Visualization; Volume visualization",
108}
109
110Article{Dias:1994:RTI,
111  author =       "Maria Lurdes Dias",
112  title =        "Ray tracing interference color: visualizing {Newton}'s
113                 rings",
114  journal =      "j-IEEE-CGA",
115  volume =       "14",
116  number =       "3",
117  pages =        "17--20",
118  month =        may,
119  year =         "1994",
120  CODEN =        "ICGADZ",
121  ISSN =         "0272-1716",
122  bibdate =      "Sat Jan 25 06:42:48 MST 1997",
123  bibsource =    "Compendex database",
124  abstract =     "Generalized Fresnel's reflectance formulas provide the
125                 basis for this ray tracing method, which simulates the
126                 natural phenomenon of interference color. A
127                 visualization of Newton's rings demonstrates its
128                 accuracy.",
129  acknowledgement = ack-nhfb,
130  affiliation =  "Dept. de Fisica, Coimbra Univ., Portugal",
131  classification = "723.2; 723.5; 741.1; 921.6; 931.2",
132  journalabr =   "IEEE Comput Graphics Appl",
133  keywords =     "Algorithms; Color; Color computer graphics; Color
134                 image processing; Computer simulation; Computer vision;
135                 Fresnel's reflectance formula; Interference color;
136                 Light reflection; Mathematical models; Newton's ring;
137                 Polarization; Ray tracing; Reflectance model;
138                 Refractive angle; Refractive index; Thick films; Thin
139                 films; Visualization",
140}
141
142@Article{Meinzer:1991:HRT,
143  author =       "Hans-Peter Meinzer and Kirsten Meetz and Dinu
144                 Scheppelmann and Uwe Engelmann and Hans Jurgen Baur",
145  title =        "The {Heidelberg} Ray Tracing Model",
146  journal =      "j-IEEE-CGA",
147  volume =       "11",
148  number =       "6",
149  pages =        "34--43",
150  month =        nov,
151  year =         "1991",
152  CODEN =        "ICGADZ",
153  ISSN =         "0272-1716",
154  bibsource =    "Graphics/siggraph/91.bib",
155  keywords =     "volume rendering",
156}
157
158@Article{Dias:1991:RTI,
159  author =       "Maria Lurdes Dias",
160  title =        "Ray Tracing Interference Color",
161  journal =      "j-IEEE-CGA",
162  volume =       "11",
163  number =       "2",
164  pages =        "54--60",
165  month =        mar,
166  year =         "1991",
167  CODEN =        "ICGADZ",
168  ISSN =         "0272-1716",
169  bibdate =      "Wed Jan 29 06:15:39 1997",
170  bibsource =    "Graphics/siggraph/91.bib, Compendex database",
171  acknowledgement = ack-nhfb,
172  affiliation =  "Phys Dept, Univ of Coimbra, Portugal",
173  classification = "723; 741",
174  journalabr =   "IEEE Comput Graphics Appl",
175  keywords =     "Color; Computer Graphics; Constructive Interference;
176                 Destructive Interference; External Reflection; Light
177                 --- Interference; Optical Thickness; Ray Tracing
178                 Interference Color; shading; Thin Film Reflectance",
179}
180
181@Article{Woodwark:1991:RHC,
182  author =       "John Woodwark",
183  title =        "Reconstructing history with computer graphics",
184  journal =      "j-IEEE-CGA",
185  volume =       "11",
186  number =       "1",
187  pages =        "18--20",
188  month =        jan,
189  year =         "1991",
190  CODEN =        "ICGADZ",
191  ISSN =         "0272-1716",
192  bibdate =      "Sat Jan 25 06:42:48 MST 1997",
193  bibsource =    "Graphics/siggraph/91.bib, Compendex database",
194  acknowledgement = ack-nhfb,
195  affiliation =  "Information Geometers, Winchester, UK",
196  annote =       "Corrections on some statements done in haggerty90d
197                 IEEE CGA July 90.",
198  classification = "402; 723; 901",
199  journalabr =   "IEEE Comput Graphics Appl",
200  keywords =     "Applications; Archeology; Architecture --- History;
201                 architecture, archaeology; Churches --- Design;
202                 Computer Graphics; Computer Programming --- Algorithms;
203                 Computer Simulation; Divided Object Space Ray Casting
204                 Algorithm (DORA); Models; Ray Casters; Resistivity
205                 Results; Roman Baths; Roman Temples",
206}
207
208@Article{Mastin:1987:FSO,
209  author =       "Gary A. Mastin and Peter A. Watterberg and John F.
210                 Mareda",
211  title =        "{Fourier} Synthesis of Ocean Scenes",
212  journal =      "j-IEEE-CGA",
213  volume =       "7",
214  number =       "3",
215  pages =        "16--23",
216  month =        mar,
217  year =         "1987",
218  CODEN =        "ICGADZ",
219  ISSN =         "0272-1716",
220  bibdate =      "Sat Jan 25 06:42:48 MST 1997",
221  bibsource =    "Compendex database, Graphics/siggraph/87.bib",
222  acknowledgement = ack-nhfb,
223  affiliationaddress = "Sandia Natl Lab, Albuquerque, NM, USA",
224  classification = "471; 723; 921",
225  journalabr =   "IEEE Comput Graphics Appl",
226  keywords =     "Computer Applications; computer graphics; computer
227                 programming --- Algorithms; mathematical
228                 transformations --- Fourier Transforms; model natural
229                 wave; oceanography; ray tracing; signal filtering and
230                 prediction; white-noise images",
231}
232
233@Article{Amanatides:1987:RCG,
234  author =       "John Amanatides",
235  title =        "Realism in Computer Graphics: a Survey",
236  journal =      "j-IEEE-CGA",
237  volume =       "7",
238  number =       "1",
239  pages =        "44--56",
240  month =        jan,
241  year =         "1987",
242  CODEN =        "ICGADZ",
243  ISSN =         "0272-1716",
244  bibdate =      "Sat Jan 25 06:42:48 MST 1997",
245  bibsource =    "Compendex database, Graphics/siggraph/87.bib",
246  acknowledgement = ack-nhfb,
247  affiliationaddress = "Univ of Toronto, Ont, Can",
248  annote =       "This article surveys most of the major issues to be
249                 dealt with when generating realistic images, and covers
250                 papers up to December 1985. It begins with an overview
251                 of the rendering process and a quick review of visible
252                 surface-determination algorithms. Then, in more detail,
253                 it discusses shading, antialiasing, texture mapping,
254                 shadows, and optical effects and closes with a
255                 discussion of modeling primitives.",
256  classification = "723; 741; 921",
257  journalabr =   "IEEE Comput Graphics Appl",
258  keywords =     "computer graphics; general survey, bibliography,
259                 tutorial; image processing --- Synthesis; mathematical
260                 techniques --- Algorithms; pixel boundary; ray tracing
261                 geometry; Reviews; sampling; shading geometry; signal
262                 filtering and prediction; texture mapping; visibility
263                 --- Mathematical Models; visibility algorithms",
264}
265
266@Article{Greene:1986:EMO,
267  author =       "Ned Greene",
268  title =        "Environment Mapping and Other Applications of World
269                 Projection",
270  journal =      "j-IEEE-CGA",
271  volume =       "6",
272  number =       "11",
273  pages =        "21--29",
274  month =        nov,
275  year =         "1986",
276  CODEN =        "ICGADZ",
277  ISSN =         "0272-1716",
278  bibdate =      "Sat Jan 25 06:42:48 MST 1997",
279  bibsource =    "Compendex database",
280  acknowledgement = ack-nhfb,
281  affiliationaddress = "New York Inst of Technology, Old Westbury, NY,
282                 USA",
283  classification = "723; 741",
284  conference =   "Graphics Interface 86",
285  journalabr =   "IEEE Comput Graphics Appl",
286  keywords =     "computer graphics; diffuse surface illumination;
287                 imaging techniques; optics; ray tracing; specular
288                 surface illumination; texture filtering; world
289                 projections",
290  meetingaddress = "Vancouver, BC, Can",
291  meetingdate =  "1986",
292  meetingdate2 = "86",
293}
294
295@Article{Steinberg:1984:SSB,
296  author =       "Herbert A. Steinberg",
297  title =        "A Smooth Surface Based on Biquadratic Patches",
298  journal =      "j-IEEE-CGA",
299  volume =       "4",
300  number =       "9",
301  pages =        "20--23",
302  month =        sep,
303  year =         "1984",
304  CODEN =        "ICGADZ",
305  ISSN =         "0272-1716",
306  bibdate =      "Sat Jan 25 06:42:48 MST 1997",
307  bibsource =    "Compendex database",
308  acknowledgement = ack-nhfb,
309  classification = "723",
310  journalabr =   "IEEE Comput Graphics Appl",
311  keywords =     "biquadratic patches; computer graphics; I35
312                 biquadratic patches and I37 ray-tracing",
313}
314
315@Article{Coquillart:1984:SDD,
316  author =       "Sabine Coquillart and Michel Gangnet",
317  title =        "Shaded Display of Digital Maps",
318  journal =      "j-IEEE-CGA",
319  volume =       "4",
320  number =       "7",
321  pages =        "35--42",
322  month =        jul,
323  year =         "1984",
324  CODEN =        "ICGADZ",
325  ISSN =         "0272-1716",
326  bibdate =      "Sat Jan 25 06:42:48 MST 1997",
327  bibsource =    "Compendex database, Graphics/siggraph/84.bib",
328  acknowledgement = ack-nhfb,
329  annote =       "Several methods for displaying height fields are
330                 presented. Bilinear interpolation of patches is used to
331                 define the surface. Efficient algorithms, and quite
332                 elegant. Reminiscent of Kajiya's cut planes for
333                 surfaces of revolution.",
334  classification = "405; 723; 741",
335  journalabr =   "IEEE Comput Graphics Appl",
336  keywords =     "computer graphics --- Applications; digital maps; maps
337                 and mapping; maps, terrain, ray tracing, priority list,
338                 I37 Ray Tracing, I37 Shading, I3m Cartography; priority
339                 lists; ray-tracing techniques; shaded images of
340                 terrain",
341}
342
343@MASTERSTHESIS{ Westin-Thesis,
344    AUTHOR    = "Stephen H. Westin",
345    TITLE     = "Predicting Reflectance Functions from Complex Surfaces",
346    SCHOOL    = "Cornell University",
347    MONTH     = Aug,
348    YEAR      = 1992
349}
350
351@InProceedings{westin92a,
352  author =       "Stephen H. Westin and James R. Arvo and Kenneth E.
353                 Torrance",
354  title =        "Predicting reflectance functions from complex
355                 surfaces",
356  pages =        "255--264",
357  booktitle =      "Computer Graphics (SIGGRAPH '92 Proceedings)",
358  volume =       "26",
359  number =       "2",
360  year =         "1992",
361  month =        jul,
362  editor =       "Edwin E. Catmull",
363  conference =   "held in Chicago, Illinois; 26-31 July 1992",
364  keywords =     "spherical harmonics, monte carlo, anisotropic
365                 reflection, brdf",
366}
367
368@InProceedings{sillion91b,
369  author =       "Francois X. Sillion and James R. Arvo and Stephen H.
370                 Westin and Donald P. Greenberg",
371  title =        "A global illumination solution for general reflectance
372                 distributions",
373  pages =        "187--196",
374  booktitle =      "Computer Graphics (SIGGRAPH '91 Proceedings)",
375  volume =       "25",
376  number =       "4",
377  year =         "1991",
378  month =        jul,
379  editor =       "Thomas W. Sederberg",
380  conference =   "held in Las Vegas, Nevada; 28 July - 2 August 1991",
381  keywords =     "global illumination, brdf, specular reflection,
382                 directional-diffuse, progressive radiosity, spherical
383                 harmonics",
384  annote =       "A general light transfer simulation algorithm for
385                 environments composed of materials with arbitrary
386                 reflectance functions is presented. This algorithm
387                 removes the previous practical restriction to ideal
388                 specular and/or ideal diffuse environments, and
389                 supports complex physically based reflectance
390                 distributions. This is accomplished by extending
391                 previous two-pass ray-casting radiosity approaches to
392                 handle non-uniform intensity distributions, and
393                 resolving all possible energy transfers between sample
394                 points. An implementation is described based on a
395                 spherical harmonic decomposition for encoding both
396                 bidirectional reflectance distribution functions for
397                 materials, and directional intensity distributions for
398                 illuminated surfaces. The method compares favorably
399                 with experimental measurements.",
400}
401
402@Article{Poulin:1991:SSL,
403  author =       "Pierre Poulin and John Amanatides",
404  title =        "Shading and shadowing with linear light sources",
405  journal =      "Computers and Graphics",
406  volume =       "15",
407  number =       "2",
408  pages =        "259--265",
409  year =         "1991",
410  coden =        "COGRD2",
411  ISSN =         "0097-8493",
412  bibdate =      "Wed Feb 5 07:22:58 MST 1997",
413  acknowledgement = ack-nhfb,
414  affiliation =  "Univ of British Columbia",
415  affiliationaddress = "Vancouver, BC, Can",
416  annote =       "Eurographics '90 award paper.",
417  classification = "723; 741; 921",
418  journalabr =   "Comput Graphics (Pergamon)",
419  keywords =     "Computer Graphics --- Three Dimensional Graphics;
420                 Graphic Methods --- Research; Lambert's Laws; Light
421                 Sources; Linear Light Source Shading And Shadowing;
422                 Mathematical Techniques --- Chebyshev Approximation;
423                 Models; Shadowing Algorithms",
424}
425
426@TECHREPORT{ Novins92b,
427    AUTHOR      = "Kevin Novins and James Arvo and David Salesin",
428    TITLE       = "Adaptive Error Bracketing for Controlled-Precision Volume Rendering",
429    INSTITUTION = "Department of Computer Science, Cornell University",
430    NUMBER      = "92-1312",
431    MONTH       = Nov,
432    YEAR        = 1992
433}
434
435@INPROCEEDINGS{ Mitchell90,
436    AUTHOR    = "Don P. Mitchell",
437    TITLE     = "Robust Ray Intersection with Interval Arithmetic",
438    BOOKTITLE = "Proceedings of Graphics Interface '90",
439    YEAR      = 1990,
440    PAGES     = "68--74"
441}
442
443
444@ARTICLE{Gigus90,
445    AUTHOR    = "Ziv Gigus and Jitendra Malik",
446    TITLE     = "Computing the aspect graph for line drawings of polyhedral objects",
447    JOURNAL   = "IEEE Transactions on Pattern Analysis and Machine Intelligence",
448    VOLUME    = 12,
449    NUMBER    = 2,
450    MONTH     = Feb,
451    YEAR      = 1990,
452    PAGES     = "113--122"
453}
454
455@Article{Sung:1992:ASB,
456  author =       "K. Sung",
457  title =        "Area sampling buffer: tracing rays with {Z}-buffer
458                 hardware",
459  journal =      "Com{\-}pu{\-}ter Graphics Forum",
460  volume =       "11",
461  number =       "3",
462  pages =        "C299--C310, C480--C481",
463  month =        "????",
464  year =         "1992",
465  coden =        "CGFODY",
466  ISSN =         "0167-7055",
467  bibdate =      "Mon Apr 14 10:23:20 MDT 1997",
468  acknowledgement = ack-nhfb,
469  classification = "C6130B (Graphics techniques)",
470  conflocation = "Cambridge, UK; 7-11 Sept. 1992",
471  conftitle =    "European Association for Computer Graphics 13th Annual
472                 Conference. EUROGRAPHICS 92",
473  corpsource =   "Dept. of Comput. Sci., Illinois Univ., Urbana, IL,
474                 USA",
475  keywords =     "area sampling; Area sampling; area sampling; buffer
476                 storage; computer graphics; Frame-buffer systems;
477                 frame-buffer systems; geometrical optics;
478                 hardware-assisted ray; Hardware-assisted ray tracing;
479                 image synthesis processes; Image synthesis processes;
480                 image synthesis processes; Light source area; light
481                 source area; Ray tracing; ray tracing; renderer;
482                 Renderer; Sampling area; sampling area; storage
483                 management; tracing; Z-buffer hardware",
484  thesaurus =    "Buffer storage; Computer graphics; Geometrical optics;
485                 Storage management",
486  treatment =    "P Practical",
487}
488
489@PhdThesis{spackman90a,
490  author =       "John Spackman",
491  title =        "Scene Decompositions for Accelerated Ray Tracing",
492  year =         "1990",
493  type =         "Ph.D. Thesis",
494  school =       "University of Bath, UK",
495  annote =       "Available as Bath Computer Science Technical Report
496                 90/33. \\ Ray tracing has come to the fore in the
497                 computer synthesis of realistic images over the last
498                 decade. This algorithm synthesises a particularly high
499                 degree of realism in both the shading and shape of
500                 surfaces. Surface shading calculations incorporate not
501                 only local diffuse and specular radiance but also
502                 global shadowing, multiple reflection and refraction of
503                 view and light attenuation, all according to the laws
504                 of optical physics. Complex object shapes may be
505                 modelled as boolean constructs from exact
506                 specifications of many common geometries. A wide range
507                 of objects may be modelled exactly without resorting to
508                 polyhedral approximation. \\ Early implementations of
509                 ray tracing synthesised some of the most realistic
510                 images up to that date, but imposed an extremely high
511                 computational load for complex scenes. Synthesis times
512                 proved to be linear in object count, and projected
513                 times for scenes of a few thousand objects extended
514                 into months on popular mini-computers. This prevented
515                 the wide-spread application of ray tracing on
516                 non-specialised hardware. Various methods have been
517                 proposed over the last few years to improve the
518                 efficiency of ray tracing for more viable synthesis
519                 times. \\ This thesis addresses scene decompositions
520                 for the acceleration of ray traced image synthesis. The
521                 decomposition of a globally complicated scene into
522                 simpler local regions is shown to reduce the
523                 computational load imposed by ray tracing. Algorithms
524                 are presented for the construction and use of various
525                 types of scene decomposition. Their relative merits are
526                 compared and the ``octtree'' decomposition is shown to
527                 be particularly suitable for accelerating the synthesis
528                 of complex scenes.",
529}
530
531Article{Spackman:1991:SNR,
532  author =       "John Spackman and Philip Willis",
533  title =        "The {SMART} Navigation of a Ray Through an Oct-Tree",
534  journal =      "Computers and Graphics",
535  volume =       "15",
536  number =       "2",
537  pages =        "185--194",
538  year =         "1991",
539  coden =        "COGRD2",
540  ISSN =         "0097-8493",
541  bibdate =      "Wed Feb 5 07:22:58 MST 1997",
542  acknowledgement = ack-nhfb,
543  affiliation =  "Univ of Bath",
544  affiliationaddress = "Avon, Engl",
545  classification = "723; 921",
546  journalabr =   "Comput Graphics (Pergamon)",
547  keywords =     "Computer Graphics; Computer Image Synthesis; Data
548                 Processing --- Data Structures; Digital Differential
549                 Analyzers; Graphic Methods --- Research; Imaging
550                 Techniques --- Research; Mathematical Techniques ---
551                 Trees; Oct Tree Scene Decompositions; octree; Ray
552                 Traced Image Synthesis; Research; Spatial Measure For
553                 Accelerated Ray Tracing (smart); Spatial Object
554                 Coherence",
555}
556
557@InCollection{Skytta:1991:DDM,
558  author =       "Jorma Skytta and Tapio Takala",
559  title =        "A Distributed Data Model for Raytracing",
560  year =         "1991",
561  booktitle =    "Advances in Computer Graphics Hardware III",
562  editor =       "A. A. M. Kuijk",
563  publisher =    "Springer Verlag",
564  pages =        "19--26",
565  address =      "New York",
566  keywords =     "parallelism",
567}
568
569@InProceedings{morris89a,
570  author =       "D. T. Morris and P. M. Dew",
571  title =        "Dynamic Dataflow Algorithms for Ray Tracing {CSG}
572                 Objects",
573  pages =        "452--460",
574  booktitle =    "Parallel Processing for Computer Vision and Display",
575  year =         "1989",
576  editor =       "P. M. Dew and R. A. Earnshaw and T. R. Heywood",
577  publisher =    "Addison-Wesley",
578  annote =       "This paper describes how solid objects may be rendered
579                 by use of dynamic dataflow techniques. Particular
580                 emphasis is given to the ray-tracing algorithm. The
581                 objects are described by constructive solid geometry.
582                 The algorithms are designed to be executed on a
583                 processor farm coupled with a data-driven dataflow
584                 machine. Many of the limitations of previous
585                 approaches, such as the Kedem-Ellis ray-casting machine
586                 are overcome. For example, the size of the objects that
587                 can be drawn directly is increased, the shading
588                 computations are made more efficient and there is
589                 better hardware utilization.",
590}
591
592@Article{Ohta:1990:RBT,
593  author =       "Masataka Ohta and Mamoru Maekawa",
594  title =        "Ray-Bound Tracing for Perfect and Efficient
595                 Anti-Aliasing",
596  journal =      "The Visual Computer",
597  pages =        "125--133",
598  volume =       "6",
599  number =       "3",
600  month =        jun,
601  year =         "1990",
602  keywords =     "ray tracing, antialiasing, coherence, bound",
603  annote =       "A complete detection of whether aliasing occurs in a
604                 given pixel is possible by using the concept of bounded
605                 rays and ray-bound tracing. A coherent set of rays can
606                 be bounded by bounding both their origins (by a sphere)
607                 and directions (by a circle on a unit sphere). By
608                 tracing bounds of rays in a pixel, along the direction
609                 of reflection, refraction or to light sources, it is
610                 possible to obtain an upper bound on the degree of
611                 aliasing in the pixel. Ray bound tracing is possible
612                 against various shapes and with various shading
613                 algorithms.",
614}
615
616@InProceedings{Ohta:1987:RCT,
617  author =       "Masataka Ohta and Mamoru Maekawa",
618  title =        "Ray Coherence Theorem and Constant Time Ray Tracing
619                 Algorithm",
620  pages =        "303--314",
621  booktitle =    "Computer Graphics 1987 (Proceedings of CG
622                 International '87)",
623  year =         "1987",
624  editor =       "Tsiyasu L. Kunii",
625  publisher =    "Springer-Verlag",
626  keywords =     "ray tracing, cull, computational geometry, spherical
627                 geometry, complexity",
628  annote =       "The concept of ray coherence is formalized as a ray
629                 coherence theorem to decrease the amount of computation
630                 in a ray object intersection of the ray tracing
631                 algorithm. Using the theorem, the calculation time of
632                 ray-object intersection in a ray tracing algorithm can
633                 be drastically decreased, by calculating a table which
634                 is used to limit the number of objects which may
635                 intersect with a given ray. The overhead of the
636                 algorithm is so small that it is effective even when
637                 there are only two objects. For more objects, the
638                 computation time of the ray-object intersection remains
639                 almost constant.",
640}
641
642@InProceedings{Hanrahan:1986:UCB,
643  author =       "Pat Hanrahan",
644  title =        "Using Caching and Breadth-First Search to Speed Up
645                 Ray-Tracing",
646  year =         "1986",
647  month =        may,
648  booktitle =    "Proceedings of Graphics Interface '86",
649  publisher =    "Canadian Information Processing Society",
650  pages =        "56--61",
651  address =      "Toronto, Ontario",
652  keywords =     "seed fill, coherence",
653}
654
655@Article{hall83a,
656  author =       "R. A. Hall and D. P. Greenberg",
657  title =        "A Testbed for Realistic Image Synthesis",
658  pages =        "10--20",
659  journal =      "IEEE Computer Graphics and Applications",
660  volume =       "3",
661  number =       "8",
662  year =         "1983",
663  month =        nov,
664  keywords =     "ray tracing cull, I37 Image Synthesis, I37 Surface
665                 Finish, shading, color",
666  annote =       "concerns shading and color more than ray tracing, but
667                 nice pictures! \\ As we have shown here, Cornell
668                 University's testbed image synthesis system has helped
669                 in the development of a number of improvements of
670                 existing ray-tracing techniques. In summary, these
671                 include a hybrid reflection model, a spectral-sampling
672                 method, the incorporation of light sources, and
673                 adaptive tree-depth control. Nevertheless, we point out
674                 again that many of the problems of realistic image
675                 generation through ray tracing have not been solved.
676                 The inherent point-sampling technique is prone to
677                 aliasing, the reflection models proposed do not include
678                 the correct energy formulations, and the computational
679                 expense is currently too high. The use of environmental
680                 image coherence techniques would probably make these
681                 approaches more tractable. It is our hope that the
682                 testbed imaging system will provide an appropriate
683                 environment for further exploration of these
684                 problems.",
685}
686
687InProceedings{Groller:1991:UTS,
688  author =       "E. Groller and W. Purgathofer",
689  title =        "Using Temporal and Spatial Coherence for Accelerating
690                 the Calculation of Animation Sequences",
691  pages =        "103--113",
692  booktitle =    "Eurographics '91",
693  year =         "1991",
694  month =        sep,
695  editor =       "Werner Purgathofer",
696  publisher =    "North-Holland",
697  conference =   "European Computer Graphics Conference and Exhibition;
698                 held in Vienna, Austria; 2-6 September 1991",
699  keywords =     "ray tracing",
700}
701
702@InProceedings{Gigante:1988:ART,
703  author =       "Michael Gigante",
704  title =        "Accelerated Ray Tracing Using Non-Uniform Grids",
705  pages =        "157--163",
706  booktitle =    "Proceedings of Ausgraph '90",
707  year =         "1988",
708  annote =       "A new space-partitioning method for ray tracing
709                 complex environments is described in this paper.
710                 Elements of a scene are placed into a collection of
711                 non-hierarchical, variable-sized voxels. \\ The
712                 creation of this structure is the result of a simple
713                 pre-processing step. In a scheme similar to that used
714                 by uniform grid methods, the non-uniform grid can be
715                 traversed very efficiently. \\ Unlike uniform grid
716                 methods, this method generates voxels with
717                 approximately uniform density of primitives per voxel.
718                 Its performance is less sensitive to the type of scene
719                 and does not fail on scenes with local, high-density
720                 clusters of primitives.",
721}
722
723@Article{deb94,
724  author =       "M. De Berg and D. Halperin and M. Overmars and J.
725                 Snoeyink and M. Van Kreveld",
726  title =        "Efficient ray shooting and hidden surface removal",
727  journal =      "Algorithmica: An International Journal in Computer
728                 Science",
729  volume =       "12",
730  number =       "1",
731  year =         "1994",
732  publisher =    "Springer Verlag, New York",
733  pages =        "30--53",
734  topic =        "visibility",
735}
736
737@TechReport{Kreveld:1992:NRD,
738  author =       "M. J. van Kreveld",
739  title =        "New results on data structures in computational
740                 geometry",
741  type =         "Ph.{D}. {Dissertation}",
742  institution =  "Dept. Comput. Sci., Univ. Utrecht",
743  address =      "Utrecht, Netherlands",
744  year =         "1992",
745  keywords =     "doctoral thesis",
746}
747
748@TechReport{Rushmeier91-RMVR,
749  author =       "Holly E. Rushmeier",
750  year =         "1991",
751  title =        "Radiosity {Methods} for {Volume} {Rendering}",
752  number =       "GIT-GVU-91-01",
753  publisher =    "Graphics, Visualization and Usability Center",
754  institution = "Georgia Institute of Technology",
755  address =      "Atlanata, GA",
756}
757
758@Article{Roth:1982:RCM,
759  author =       "Scott D. Roth",
760  title =        "Ray Casting for Modeling Solids",
761  journal =      "Computer Graphics and Image Processing",
762  volume =       "18",
763  number =       "2",
764  pages =        "109--144",
765  month =        feb,
766  year =         "1982",
767  coden =        "CGIPBG",
768  ISSN =         "0146-664X",
769  bibdate =      "Fri Feb 7 08:36:21 MST 1997",
770  note =         "Also in SIGGRAPH '87, '88, '89 Introduction to Ray
771                 Tracing course notes. The other classic ray tracing
772                 paper.",
773  acknowledgement = ack-nhfb,
774  annote =       "the other classic ray tracing paper \\ This paper
775                 presents ray casting as the methodological basis for a
776                 CAD/CAM solid modeling system. Solid objects are
777                 modeled by combining primitive solids, such as blocks
778                 and cylinders, using the set operators union,
779                 intersection, and difference. To visualize and analyze
780                 the composite solids modeled, virtual light rays are
781                 cast as probes. By virtue of its simplicity, ray
782                 casting is reliable and extensible. The most difficult
783                 mathematical problem is finding line-surface
784                 intersection points. So surfaces such as planes,
785                 quadrics, tori, and probably even parametric surface
786                 patches may bound the primitive solids. The adequacy
787                 and efficiency of ray casting are issues addressed
788                 here. A fast picture generation capability for
789                 interactive modeling is the biggest challenge. New
790                 methods are presented, accompanied by sample pictures
791                 and CPU times, to meet the challenge.",
792  classification = "723",
793  journalabr =   "Comput Graphics Image Process",
794  keywords =     "computer aided design; computer graphics; ray casting;
795                 ray tracing casting intersect CSG, tracing, hidden
796                 line, I35 ray casting for a CAD/CAM solid modeling
797                 system, CSG",
798}
799
800@PhdThesis{Pattanaik:1990:CMG,
801  author =       "Sumanta N. Pattanaik",
802  title =        "Computational Methods for Global Illumination and
803                 Visualisation of Complex 3{D} Environments",
804  year =         "1990",
805  month =        nov,
806  school =       "Birla Institute of Technology \& Science, Computer
807                 Science Department, Pilani, India",
808  keywords =     "adjoint illumination equations, particle model of
809                 light, random walk, importance sampling",
810}
811
812@Article{Pattanaik:1994:FWR,
813  author =       "S. N. Pattanaik and K. Bouatouch",
814  title =        "Fast Wavelet Radiosity Method",
815  journal =      "Com{\-}pu{\-}ter Graphics Forum",
816  volume =       "13",
817  number =       "3",
818  pages =        "C/407--C/420",
819  month =        "????",
820  year =         "1994",
821  coden =        "CGFODY",
822  ISSN =         "0167-7055",
823  bibdate =      "Mon Apr 14 10:23:20 MDT 1997",
824  acknowledgement = ack-nhfb,
825  classification = "C4260 (Computational geometry); C6130B (Graphics
826                 techniques)",
827  conflocation = "Oslo, Norway; 12-16 Sept. 1994",
828  conftitle =    "15th Annual Conference and Exhibition.
829                 EUROGRAPHICS'94",
830  corpsource =   "Campus de Beaulieu, IRISA, Rennes, France",
831  keywords =     "computational geometry; Computer graphics; computer
832                 graphics; decomposition technique; hierarchical;
833                 Hierarchical decomposition technique; inner products;
834                 interpolating wavelets; Interpolating wavelets;
835                 interpolating wavelets; multidimensional;
836                 Multidimensional inner products; optimal adaptive
837                 subdivision; Optimal adaptive subdivision; ray tracing;
838                 wavelet analysis; Wavelet analysis; wavelet radiosity
839                 method; Wavelet radiosity method; wavelet transforms",
840  thesaurus =    "Computational geometry; Ray tracing; Wavelet
841                 transforms",
842  treatment =    "T Theoretical or Mathematical",
843}
844
845@InProceedings{Ferwerda:1997:MVM,
846  author =       "James A. Ferwerda and Sumanta N. Pattanaik and Peter
847                 Shirley and Donald P. Greenberg",
848  title =        "A Model of Visual Masking for Computer Graphics",
849  booktitle =    "SIGGRAPH 97 Conference Proceedings",
850  editor =       "Turner Whitted",
851  series =       "Annual Conference Series",
852  year =         "1997",
853  organization = "ACM SIGGRAPH",
854  publisher =    "Addison Wesley",
855  month =        aug,
856  pages =        "143--152",
857  note =         "ISBN 0-89791-896-7",
858  keywords =     "visual perception, masking, image quality, error
859                 metrics",
860  annote =       "In this paper we develop a computational model of
861                 visual masking based on psychophysical data. The model
862                 predicts how the presence of one visual pattern affects
863                 the detectability of another. The model allows us to
864                 choose texture patterns for computer graphics images
865                 that hide the effects of faceting, banding, aliasing,
866                 noise and other visual artifacts produced by sources of
867                 error in graphics algorithms. We demonstrate the
868                 utility of the model by choosing a texture pattern to
869                 mask faceting artifacts caused by polygonal tesselation
870                 of a at-shaded curved surface. The model predicts how
871                 changes in the contrast, spatial frequency, and
872                 orientation of the texture pattern, or changes in the
873                 tesselation of the surface will alter the masking
874                 effect. The model is general and has uses in geometric
875                 modeling, realistic image synthesis, scientific
876                 visualization, image compression, and image-based
877                 rendering.",
878}
879
880@Article{Levoy:1990:ERT,
881  author =       "Marc Levoy",
882  title =        "Efficient Ray Tracing of Volume Data",
883  journal =      "ACM Transactions on Graphics",
884  volume =       "9",
885  number =       "3",
886  pages =        "245--261",
887  month =        jul,
888  year =         "1990",
889  coden =        "ATGRDF",
890  ISSN =         "0730-0301",
891  bibdate =      "Fri Jan 5 07:58:42 MST 1996",
892  url =          "http://www.acm.org/pubs/toc/Abstracts/0730-0301/78965.html",
893  acknowledgement = ack-nhfb,
894  annote =       "{\em Volume Rendering} is a technique for visualizing
895                 sampled scalar or vector fields of three spatial
896                 dimensions without fitting geometric primitives to the
897                 data. A subset of these techniques generates images by
898                 computing 2-D projections of a colored semitransparent
899                 volume, where the color and opacity at each point are
900                 derived from the data using local operators. Since all
901                 voxels participate in the generation of each image,
902                 rendering time grows linearly with the size of the
903                 dataset. This paper presents a front-to-back
904                 image-order volume-rendering algorithm and discusses
905                 two techniques for improving its performance. The first
906                 technique employs a pyramid of binary volumes to encode
907                 spatial coherence present in the data, and the second
908                 technique uses an opacity threshold to adaptively
909                 terminate ray tracing. Although the actual time saved
910                 depends on the data, speedups of an order of magnitude
911                 have been observed for datasets of useful size and
912                 complexity. Examples from two applications are given:
913                 medical imaging and molecular graphics.",
914  keywords =     "algorithms; design; hierarchical spatial enumeration;
915                 medical imaging; molecular graphics; octree;
916                 performance; ray tracing; scientific visualization;
917                 volume rendering; volume visualization; voxel",
918  subject =      "{\bf I.3.3}: Computing Methodologies, COMPUTER
919                 GRAPHICS, Picture/Image Generation, Display algorithms.
920                 {\bf I.3.5}: Computing Methodologies, COMPUTER
921                 GRAPHICS, Computational Geometry and Object Modeling,
922                 Curve, surface, solid, and object representations. {\bf
923                 I.3.7}: Computing Methodologies, COMPUTER GRAPHICS,
924                 Three-Dimensional Graphics and Realism, Visible
925                 line/surface algorithms.",
926}
927
928@InProceedings{Heckbert92discon,
929  author =       "Paul S. Heckbert",
930  title =        "Discontinuity Meshing for Radiosity",
931  booktitle =    "Third Eurographics Workshop on Rendering",
932  month =        may,
933  year =         "1992",
934  address =      "Bristol, UK",
935  pages =        "203--216",
936  keywords =     "radiosity, adaptive mesh, visibility",
937}
938
939@InProceedings{hashimoto89a,
940  author =       "Akihiko Hashimoto and Taka-aki Akimoto and Kenji Mase
941                 and Yasuhito Suenaga",
942  title =        "Vista Ray-Tracing: High Speed Ray Tracing Using
943                 Perspective Projection Image",
944  pages =        "549--561",
945  booktitle =    "New Advances in Computer Graphics (Proceedings of CG
946                 International '89)",
947  year =         "1989",
948  editor =       "R. A. Earnshaw and B. Wyvill",
949  publisher =    "Springer-Verlag",
950  annote =       "This paper presents a new high speed algorithm of
951                 ray-tracing named Vista Ray-tracing. In Vista
952                 Ray-tracing, time consuming intensity calculations are
953                 done only for ``active'' pixels which really need
954                 precise ray-tracing, while the intensity of
955                 ``moderate'' pixels in calculated by interpolation. The
956                 perspective projection image, or Vista, is generated at
957                 the first stage to be used as a guide map in active
958                 pixel selection. In this paper, a new method for
959                 obtaining Vistas for CSG models of quadratic surface
960                 objects is presented as a key technology. A new texture
961                 mapping algorithm is also presented. Vista Ray-tracing
962                 is actually 16-75 times faster than standard
963                 ray-tracing, and can be even faster if other
964                 acceleration methods are employed. Consequently, Vista
965                 Ray-tracing is very useful for intermediate processes
966                 in making various images for TV animation, movies, high
967                 definition television, printing, etc.",
968}
969
970@Article{Hanrahan:1990:LSL,
971  author =       "Pat Hanrahan and Jim Lawson",
972  editor =       "Forest Baskett",
973  title =        "A Language for Shading and Lighting Calculations",
974  journal =      "Computer Graphics",
975  volume =       "24",
976  number =       "4",
977  pages =        "289--298",
978  month =        aug,
979  year =         "1990",
980  coden =        "CGRADI, CPGPBZ",
981  ISSN =         "0097-8930",
982  conference =   "held in Dallas, Texas; 6--10 August 1990",
983  keywords =     "shading language, little language, illumination,
984                 lighting, rendering",
985}
986
987@Article{Cook:1984:ST,
988  author =       "R. L. Cook",
989  title =        "Shade trees",
990  journal =      "Computer Graphics",
991  volume =       "18",
992  number =       "3",
993  pages =        "223--231",
994  month =        jul,
995  year =         "1984",
996  coden =        "CGRADI, CPGPBZ",
997  ISSN =         "0097-8930",
998  annote =       "Cook developed a special shade tree language for
999                 defining textures and coloration for objects.
1000                 Interesting because it separates shading from the rest
1001                 of rendering, and allows a library of surface types to
1002                 be built up gradually. \\ Ray tracing is one of the
1003                 most elegant techniques in computer graphics. Many
1004                 phenomena that are difficult or impossible with other
1005                 techniques are simple with ray tracing, including
1006                 shadows, reflections, and refracted light. Ray
1007                 directions, however, have been determined precisely,
1008                 and this has limited the capabilities of ray tracing.
1009                 By distributing the directions of the rays according to
1010                 the analytic function they sample, ray tracing can
1011                 incorporate fuzzy phenomena. This provides correct and
1012                 easy solutions to some previously unsolved or partially
1013                 solved problems, including motion blur, depth of field,
1014                 penumbras, translucency, and fuzzy reflections. Motion
1015                 blur and depth of field calculations can be integrated
1016                 with the visible surface calculations, avoiding the
1017                 problems found in previous methods.",
1018  conference =   "held in Minneapolis, Minnesota; 23--27 July 1984",
1019  keywords =     "texturing, procedural models, languages, I37 Shade
1020                 Trees",
1021}
1022
1023@Article{Goldfeather:1989:NRC,
1024  author =       "Jack Goldfeather and Steven Molnar and Greg Turk and
1025                 Henry Fuchs",
1026  title =        "Near Real-Time {CSG} Rendering Using Tree
1027                 Normalization and Geometric Pruning",
1028  journal =      "IEEE Computer Graphics and Applications",
1029  volume =       "9",
1030  number =       "3",
1031  pages =        "20--28",
1032  month =        may,
1033  year =         "1989",
1034  coden =        "ICGADZ",
1035  ISSN =         "0272-1716",
1036  bibdate =      "Sat Jan 25 06:42:48 MST 1997",
1037  acknowledgement = ack-nhfb,
1038  affiliation =  "Carleton Coll, Dep of Math, Northfield, MN, USA",
1039  classification = "723; 741; 921",
1040  journalabr =   "IEEE Comput Graphics Appl",
1041  keywords =     "Boolean Switching Functions; Computer Aided Design;
1042                 Computer Aided Engineering; Computer Graphics ---
1043                 Interactive; Constructive Solid Geometry (CSG);
1044                 Geometric Pruning; Imaging Techniques; solid modeling;
1045                 Surfaces; Tree Normalization",
1046}
1047
1048@Article{Pavlidis:1990:RCS,
1049  author =       "Theo Pavlidis",
1050  title =        "Re: Comments on ``{Stochastic Sampling in Computer
1051                 Graphics}''",
1052  journal =      "ACM Transactions on Graphics",
1053  volume =       "9",
1054  number =       "2",
1055  pages =        "233--236",
1056  month =        apr,
1057  year =         "1990",
1058  coden =        "ATGRDF",
1059  ISSN =         "0730-0301",
1060  bibdate =      "Fri Jan 5 07:58:42 MST 1996",
1061  note =         "See \cite{Cook:1986:SSC,Wold:1990:RCS}.",
1062  acknowledgement = ack-nhfb,
1063}
1064
1065@InCollection{Whitted88,
1066  author =       "Turner Whitted and Robert L. Cook",
1067  editor =       "Kenneth I. Joy and Charles W. Grant and Nelson L. Max
1068                 and Lansing Hatfield",
1069  title =        "A Comprehensive Shading Model",
1070  booktitle =    "Tutorial: Computer Graphics: Image Synthesis",
1071  pages =        "232--43",
1072  publisher =    "Computer Society Press",
1073  address =      "Washington, DC",
1074  year =         "1988",
1075  keywords =     "shading",
1076  note =         "also in SIGGRAPH '85 course notes \#11",
1077}
1078
1079@Article{Cook:1986:SSC,
1080  author =       "Robert L. Cook",
1081  title =        "Stochastic Sampling in Computer Graphics",
1082  journal =      "ACM Transactions on Graphics",
1083  volume =       "5",
1084  number =       "1",
1085  pages =        "51--72",
1086  month =        jan,
1087  year =         "1986",
1088  coden =        "ATGRDF",
1089  ISSN =         "0730-0301",
1090  bibdate =      "Thu Aug 25 23:39:28 1994",
1091  note =         "See remarks \cite{Pavlidis:1990:RCS,Wold:1990:RCS}.
1092                 Also in Tutorial: Computer Graphics: Image Synthesis,
1093                 Computer Society Press, Washington, 1988, pp.
1094                 283--304.",
1095  url =          "http://www.acm.org/pubs/toc/Abstracts/0730-0301/8927.html",
1096  acknowledgement = ack-nhfb,
1097  keywords =     "algorithms; antialiasing; depth of field; filtering;
1098                 image synthesis; Monte Carlo integration; motion blur;
1099                 raster graphics; ray tracing; stochastic sampling",
1100  review =       "ACM CR 8709-0784",
1101  subject =      "{\bf I.3.3}: Computing Methodologies, COMPUTER
1102                 GRAPHICS, Picture/Image Generation, Viewing algorithms.
1103                 {\bf G.3}: Mathematics of Computing, PROBABILITY AND
1104                 STATISTICS, Probabilistic algorithms (including Monte
1105                 Carlo).",
1106}
1107
1108@InProceedings{Torrance87a,
1109  author =       "R. L. Cook and K. E. Torrance",
1110  title =        "A Reflectance Model for Computer Graphics",
1111  year =         "1987",
1112  editor =       "W. Richards and S. Ullman",
1113  booktitle =    "Image Understanding 1985--86",
1114  publisher =    "Ablex",
1115  address =      "Norwood, NJ",
1116  institution =  "Cornell U",
1117  pages =        "1--19",
1118  keywords =     "IMAGE OUTPUT",
1119}
1120
1121@TechReport{EVL-1996-11,
1122  author =       "Andr{\'e} Hinkenjann and Markus Kubuk and Heinrich
1123                 M{\"u}ller",
1124  title =        "Answering Line Segment Intersection Queries Based On
1125                 Sample Answers",
1126  number =       "620/1996",
1127  type =         "Research Report",
1128  institution =  "University of Dortmund",
1129  address =      "Universit{\"a}t Dortmund, 44221 Dortmund, Germany",
1130  month =        aug,
1131  year =         "1996",
1132  abstract =     "Geometric query problems can be solved by
1133                 preprocessing the answers for a representative set of
1134                 sample queries. An arbitrary query is answered by the
1135                 response of a closest sample query. In general, this
1136                 answer will not be correct. A framework is presented in
1137                 which the quality of approximation of this approach can
1138                 be characterized. Futher, efficiency considerations are
1139                 performed. They consist in empirical experiments for
1140                 the classical line segment intersection query problem,
1141                 but also in giving theoretical time and space bounds
1142                 describing the trade-off between quality of
1143                 approximation and computational complexity. Finally,
1144                 approaches to the choice of favorable sample queries
1145                 are discussed.",
1146  postscript-url = "ftp://euklid.informatik.uni-dortmund.de/pub/reports/ls7/rr-620.ps.gz",
1147  evlib-url =    "http://infovis.zib.de:8000/Dienst/UI/2.0/Describe/evl.computationalgeometry%2FEVL-1996-11",
1148  evlib-revision = "1st",
1149  evlib-postscript-md5 = "14a18f6a52af153a3c3eb1c7037c344c",
1150}
1151
1152@Article{Sbert:1997:OSS,
1153  author =       "Mateu Sbert",
1154  title =        "Optimal Source Selection in Shooting Random Walk
1155                 {Monte Carlo} Radiosity",
1156  journal =      "Com{\-}pu{\-}ter Graphics Forum",
1157  volume =       "16",
1158  number =       "3",
1159  pages =        "C301--C308",
1160  month =        sep # " 4--8",
1161  year =         "1997",
1162  coden =        "CGFODY",
1163  ISSN =         "0167-7055",
1164  bibdate =      "Tue Mar 17 15:44:38 MST 1998",
1165  acknowledgement = ack-nhfb,
1166  affiliation =  "Universitat de Girona",
1167  affiliationaddress = "Girona, Spain",
1168  classification = "723.5; 741.1; 921.5; 922.1; 922.2",
1169  journalabr =   "Comput Graphics Forum",
1170  keywords =     "Computer graphics; Computer simulation; Lighting;
1171                 Monte Carlo methods; Optimization; Probability;
1172                 Radiosity; Rendering method",
1173}
1174
1175@Article{Choi92,
1176  author =       "H. K. Choi and C. M. Kyung",
1177  title =        "{PYSHA}: a shadow-testing acceleration scheme for ray
1178                 tracing",
1179  journal =      "Computer-aided design",
1180  volume =       "24",
1181  number =       "2",
1182  month =        feb,
1183  year =         "1992",
1184  note =         "hybrid scheme of light buffer and grid subdivision
1185                 with cost comparison on the fly",
1186}
1187
1188@article{gt-drssp-97
1189, author =      "M. T. Goodrich and R. Tamassia"
1190, title =       "Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations"
1191, journal =     "J. Algorithms"
1192, volume =      23
1193, year =        1997
1194, pages =       "51--73"
1195, update =      "97.07 smid"
1196}
1197
1198@article{ekltmmv-rcerr-91
1199, 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"
1200, title =       "The ray casting engine and ray representations: a technical summary"
1201, journal =     "Internat. J. Comput. Geom. Appl."
1202, volume =      1
1203, number =      4
1204, year =        1991
1205, pages =       "347--380"
1206, keywords =    "mechanical CAD CAM, solid modeling, parallel computation, ray representation"
1207}
1208
1209@inproceedings{cj-sersi-91
1210, author =      "S. W. Cheng and R. Janardan"
1211, title =       "Space-efficient ray shooting and intersection searching: algorithms, dynamization and applications"
1212, booktitle =   "Proc. 2nd ACM-SIAM Sympos. Discrete Algorithms"
1213, year =        1991
1214, pages =       "7--16"
1215, keywords =    "ray tracing, dynamization, spanning trees of low stabbing number"
1216}
1217
1218@article{cj-arsis-92
1219, author =      "S. W. Cheng and R. Janardan"
1220, title =       "Algorithms for ray-shooting and intersection searching"
1221, journal =     "J. Algorithms"
1222, volume =      13
1223, year =        1992
1224, pages =       "670--692"
1225, update =      "93.09 smid"
1226}
1227
1228@techreport{bf-vrs-90
1229, author =      "R. Bar-Yehuda and S. Fogel"
1230, title =       "Variations on Ray Shooting"
1231, type =        "Technical {Report}"
1232, number =      639
1233, institution = "Technion IIT"
1234, address =     "Haifa, Israel"
1235, year =        1990
1236, keywords =    "sheaf, ES-trees"
1237, update =      "95.01 smid, 93.09 milone+mitchell"
1238}
1239
1240@inproceedings{af-acrsm-97
1241, author =      "B. Aronov and S. Fortune"
1242, title =       "Average-Case Ray Shooting and Minimum Weight Triangulations"
1243, booktitle =   "Proc. 13th Annu. ACM Sympos. Comput. Geom."
1244, year =        1997
1245, pages =       "203--212"
1246, update =      "97.07 efrat"
1247}
1248
1249@inproceedings{b-lsbsp-95
1250, author =      "Mark de Berg"
1251, title =       "Linear Size Binary Space Partitions for Fat Objects"
1252, booktitle =   "Proc. 3rd Annu. European Sympos. Algorithms"
1253, series =      "Lecture Notes Comput. Sci."
1254, volume =      979
1255, publisher =   "Springer-Verlag"
1256, year =        1995
1257, pages =       "252--263"
1258, update =      "97.03 murali+schwarzkopf"
1259}
1260
1261@inproceedings{bg-bspsc-94
1262, author =      "M. de Berg and M. de Groot"
1263, title =       "Binary space partitions for sets of cubes"
1264, booktitle =   "Abstracts 10th European Workshop Comput. Geom."
1265, nickname =    "CG'94"
1266, year =        1994
1267, pages =       "84--88"
1268, update =      "94.05 schwarzkopf"
1269}
1270
1271@inproceedings{bgo-nrbsp-94
1272, author =      "M. de Berg and M. de Groot and M. Overmars"
1273, title =       "New results on binary space partitions in the plane"
1274, booktitle =   "Proc. 4th Scand. Workshop Algorithm Theory"
1275, series =      "Lecture Notes Comput. Sci."
1276, volume =      824
1277, publisher =   "Springer-Verlag"
1278, year =        1994
1279, pages =       "61--72"
1280, update =      "95.01 schwarzkopf+smid, 94.05 schwarzkopf"
1281}
1282
1283@inproceedings{bgo-pbsp-93
1284, author =      "M. de Berg and M. de Groot and M. Overmars"
1285, title =       "Perfect binary space partitions"
1286, booktitle =   "Proc. 5th Canad. Conf. Comput. Geom."
1287, site =        "Waterloo, Canada"
1288, year =        1993
1289, pages =       "109--114"
1290, precedes =    "bgo-pbsp-97"
1291, update =      "97.03 devillers, 93.09 milone+mitchell"
1292}
1293
1294@article{bgo-pbsp-97
1295, author =      "M. de Berg and M. de Groot and M. Overmars"
1296, title =       "Perfect binary space partitions"
1297, journal =     "Comput. Geom. Theory Appl."
1298, volume =      7
1299, year =        1997
1300, pages =       "81--91"
1301, succeeds =    "bgo-pbsp-93"
1302, update =      "97.03 devillers"
1303}
1304
1305@article{py-ebsph-90
1306, author =      "M. S. Paterson and F. F. Yao"
1307, title =       "Efficient binary space partitions for hidden-surface removal and solid modeling"
1308, journal =     "Discrete Comput. Geom."
1309, volume =      5
1310, year =        1990
1311, pages =       "485--503"
1312, succeeds =    "py-bpahs-89"
1313}
1314
1315@inproceedings{py-obspo-90
1316, author =      "M. S. Paterson and F. F. Yao"
1317, title =       "Optimal binary space partitions for orthogonal objects"
1318, booktitle =   "Proc. 1st ACM-SIAM Sympos. Discrete Algorithms"
1319, year =        1990
1320, pages =       "100--106"
1321, precedes =    "py-obspo-92"
1322}
1323
1324@article{py-obspo-92
1325, author =      "M. S. Paterson and F. F. Yao"
1326, title =       "Optimal binary space partitions for orthogonal objects"
1327, journal =     "J. Algorithms"
1328, volume =      13
1329, year =        1992
1330, pages =       "99--113"
1331, succeeds =    "py-obspo-90"
1332}
1333
1334
1335
1336@inproceedings{l-hmelr-83
1337, author =      "A. Lingas"
1338, title =       "Heuristics for minimum edge length rectangular partitions of rectilinear figures"
1339, booktitle =   "Proc. 6th GI Conf. Theoret. Comput. Sci."
1340, series =      "Lecture Notes Comput. Sci."
1341, volume =      145
1342, publisher =   "Springer-Verlag"
1343, year =        1983
1344, pages =       "199--210"
1345, keywords =    "design of algorithms, VLSI design, length, partition, approximation, polygons, geometric graphs, rectangles"
1346}
1347
1348@incollection{s-ghsgc-83
1349, author =      "K. J. Supowit"
1350, title =       "Grid heuristics for some geometric covering problems"
1351, editor =      "F. P. Preparata"
1352, booktitle =   "Computational Geometry"
1353, series =      "Adv. Comput. Res."
1354, volume =      1
1355, publisher =   "JAI Press"
1356, address =     "Greenwich, CT"
1357, year =        1983
1358, pages =       "215--233"
1359, keywords =    "balls, $d$-dimensional, covering, heuristics"
1360}
1361
1362@inproceedings{lls-nohbs-87
1363, author =      "C. Levcopoulos and A. Lingas and J.-R. Sack"
1364, title =       "Nearly optimal heuristics for binary search trees with geometric generalizations"
1365, booktitle =   "Proc. 14th Internat. Colloq. Automata Lang. Program."
1366, series =      "Lecture Notes Comput. Sci."
1367, volume =      267
1368, publisher =   "Springer-Verlag"
1369, year =        1987
1370, pages =       "376--385"
1371, keywords =    "decomposition, partition, polygons, two-dimensional"
1372}
1373
1374@article{dz-hmlrp-90
1375, author =      "D. Du and Y. Zhang"
1376, title =       "On heuristics for minimum length rectilinear partitions"
1377, journal =     "Algorithmica"
1378, volume =      5
1379, year =        1990
1380, pages =       "111--128"
1381}
1382
1383ceedings{l-fhmlr-86
1384, author =      "C. Levcopoulos"
1385, title =       "Fast heuristics for minimum length rectangular partitions of polygons"
1386, booktitle =   "Proc. 2nd Annu. ACM Sympos. Comput. Geom."
1387, year =        1986
1388, pages =       "100--108"
1389, 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"
1390, update =      "97.11 bibrelex"
1391}
1392
1393@article{lls-hobst-89
1394, author =      "Christos Levcopoulos and Andrzej Lingas and Jorg-R. Sack"
1395, title =       "Heuristics For Optimum Binary Search Trees And Minimum Weight Triangulation Problems"
1396, journal =     "Theoret. Comput. Sci."
1397, volume =      66
1398, number =      2
1399, month =       aug
1400, year =        1989
1401, pages =       "181--203"
1402, keywords =    "optimum binary search trees, minimum weight triangulation, amortization argument"
1403, annote =      "Amortized linear algorithm for GT of semi-circular
1404                 polygons."
1405, abstract =    "We establish new bounds on the problem of constructing
1406                 optimum binary search trees with zero-key access
1407                 probabilities (with applications e.g. to point location
1408                 problems). We present a linear-time heuristic for
1409                 constructing such trees so that their cost is within a
1410                 factor of 1 plus epsilon from the optimum cost, where
1411                 epsilon is an arbitrary positive constant. Furthermore,
1412                 by using an interesting amortization argument, we give
1413                 a simple and practical, linear-time implementation of a
1414                 known greedy heuristics for such trees. The above
1415                 results are obtained in a more general setting, namely,
1416                 in the context of minimum length triangulations of so-
1417                 called semi-circular polygons. They are carried over to
1418                 binary search trees by proving a duality between
1419                 optimum (m minus 1)-way search trees and minimum weight
1420                 partitions of infinitely-flat semi-circular polygons
1421                 into m- gons. With this duality we can also obtain
1422                 better heuristics for minimum length partitions of
1423                 polygons by using known algorithms for optimum search
1424                 trees. (Author abstract) 14 Refs."
1425}
1426
1427@article{dr-hmrst-93
1428, author =      "C. C. {De Souza} and C. C. Ribeiro"
1429, title =       "Heuristics for the minimum rectilinear {Steiner} tree problem: new algorithms and a computational study"
1430, journal =     "Discrete Appl. Math."
1431, volume =      45
1432, number =      3
1433, year =        1993
1434, pages =       "205--220"
1435, keywords =    "Steiner tree, $L_{1}$ metric, heuristics"
1436, update =      "95.09 korneenko"
1437}
1438
1439@InProceedings{Bar-Yehuda90,
1440  author =       "R. Bar-Yehuda and S. Fogel",
1441  title =        "Good splitters with applications to ray shooting",
1442  booktitle =    "Proc. 2nd Canad. Conf. Comput. Geom.",
1443  pages =        "81--84",
1444  year =         "1990",
1445  keywords =     "computational geometry, arrangements",
1446}
1447
1448@InProceedings{Edelsbrunner91,
1449  author =       "Herbert Edelsbrunner and Bernard Chazelle and
1450                 Michelangelo Grigni and Leonidas Guibas and John
1451                 Hershberger and Misha Sharir and Jack Snoeyink",
1452  title =        "Ray Shooting in Polygons Using Geodesic
1453                 Triangulations",
1454  booktitle =    "Proc. 18th Internat. Colloq. Automata Lang. Program.,
1455                 Lecture Notes in Computer Science{"} series no. 150",
1456  pages =        "661--673",
1457  publisher =    "Springer-Verlag",
1458  year =         "1991",
1459  keywords =     "computational geometry, simple polygon, geodesics",
1460  note =         "also as Princeton University, Computer Science
1461                 Department, TR-350-91, Sept. 1991",
1462}
1463
1464@TechReport{Guibas89,
1465  author =       "L. Guibas and M. Overmars and M. Sharir",
1466  title =        "Ray shooting, implicit point location, and related
1467                 queries in arrangements of segments{"}",
1468  institution =  "Dept. Comput. Sci., New York Univ.",
1469  number =       "433",
1470  address =      "New York, NY",
1471  month =        mar,
1472  year =         "1989",
1473  keywords =     "random sampling, arrangements, point location",
1474}
1475
1476@Article{Matousek93,
1477  author =       "J. Matousek",
1478  title =        "On Vertical Ray Shooting in Arrangements",
1479  journal =      "Comput. Geom. Theory Appl.",
1480  volume =       "2",
1481  number =       "5",
1482  pages =        "279--285",
1483  month =        mar,
1484  year =         "1993",
1485  keywords =     "computational geometry, zone theorem, cutting,
1486                 hyperplane arrangement",
1487  note =         "update = 93.09 Held+Matousek+Milone+Mitchell",
1488}
1489
1490@Article{bronsvoort84b,
1491  author =       "Willem F. Bronsvoort and Jarke J. van Wijk and
1492                 Frederik W. Jansen",
1493  title =        "Two Methods for Improving the Efficiency of Ray
1494                 Casting in Solid Modeling",
1495  pages =        "110--116",
1496  journal =      "Computer-Aided Design",
1497  volume =       "16",
1498  number =       "1",
1499  year =         "1984",
1500  month =        jan,
1501  keywords =     "CSG, I35 Ray Tracing, I35 Solid Modeling",
1502  annote =       "enhancements to Roth: scanline interval enclosures,
1503                 CSG tree optimization, and recursive screen subdivision
1504                 \\ In solid modelling based on constructive solid
1505                 geometry and primitive instancing, ray casting is a
1506                 very suitable technique for visualization of models on
1507                 a raster display. In its present form, it is, however,
1508                 too inefficient for interactive use. \\ Two methods for
1509                 improving the efficiency are given here. The first uses
1510                 scan-line interval enclosures instead of box
1511                 enclosures, and also bypasses non-contributing nodes
1512                 during each traversal of the CSG (constructive solid
1513                 geometry) tree. The second refines the image step by
1514                 step by subdivision, thereby avoiding explicit
1515                 computation of the intensities of many pixels of the
1516                 image. The second method reduces computing time more
1517                 than the first, but has the disadvantage that slivers
1518                 may occasionally be lost from the image.",
1519}
1520
1521@Article{tvcg-1996-22,
1522  author =       "Daniel Cohen-Or and Eran Rich and Uri Lerner and
1523                 Victor Shenkar",
1524  email =        "daniel@math.tau.ac.il and none and none and none",
1525  title =        "A Real-Time Photo-Realistic Visual Flythrough",
1526  journal =      "IEEE Transaction on Visualization and Computer
1527                 Graphics",
1528  volume =       "2",
1529  number =       "3",
1530  month =        sep,
1531  year =         "1996",
1532  pages =        "255--264",
1533  abstract =     "In this paper we present a comprehensive flythrough
1534                 system which generates photo-realistic images in true
1535                 real-time. The high performance is due to an innovative
1536                 rendering algorithm based on a discrete ray casting
1537                 approach, accelerated by ray coherence and
1538                 multiresolution traversal. The terrain as well as the
1539                 3D objects are represented by a textured mapped
1540                 voxel-based model. The system is based on a pure
1541                 software algorithm and is thus portable. It was first
1542                 implemented on a workstation and then ported to a
1543                 general-purpose parallel architecture to achieve
1544                 real-time performance.",
1545  keywords =     "Terrain visualization, parallel rendering, flight
1546                 simulator, visual simulations, voxel-based modeling,
1547                 ray casting",
1548  tvcg-abstract-url = "http://www.computer.org/pubs/tvcg/abs96.htm#255tg0996",
1549}
1550
1551@InProceedings{dadoun85a,
1552        author =       "Nou Dadoun and David G. Kirkpatrick and John P.
1553                       Walsh",
1554        title =        "The Geometry of Beam Tracing",
1555        booktitle =    "Proceedings of the ACM Symposium on Computational
1556                       Geometry",
1557        pages =        "55--61",
1558        year =         "1985",
1559        month =        jun,
1560        annote =       "the use of BSP trees and hierarchical bounding volumes
1561                       for fast beam intersection testing. \\ A solution to
1562                       the hidden surface elimination problem called beam
1563                       tracing is described. Beam tracing is related to ray
1564                       tracing but uses spatial coherence within the scene,
1565                       and area coherence within the image to batch
1566                       computations. Beam tracing is an object space solution
1567                       to the hidden surface problem. \\ Beam tracing is
1568                       formulated in terms of its principal subprocesses:
1569                       intersection, sorting, and clipping. A hierarchical
1570                       scene representation is proposed. This incorporates the
1571                       space decomposition idea of the BSP tree [Fuchs, Kedem,
1572                       and Naylor, 80] along with the convex polytope
1573                       intersection detection technique of [Dobkin and
1574                       Kirkpatrick, 83] to interleave and efficiently solve
1575                       the intersection and sorting subproblems of beam
1576                       tracing.",
1577}
1578
1579
1580@InBook{kaplan85a,
1581        author =       "M. Kaplan",
1582        title =        "Space-Tracing: {A} Constant Time Ray-Tracer",
1583        pages =        "149--158",
1584        booktitle =    "SIGGRAPH '85 State of the Art in Image Synthesis
1585                       seminar notes",
1586        year =         "1985",
1587        month =        jul,
1588        keywords =     "ray tracing cull",
1589}
1590
1591@Book{Samet90,
1592        author =       "Hanan Samet",
1593        title =        "Applications of Spatial Data Structures",
1594        publisher =    "Addison-Wesley",
1595        address =      "Reading, Mass.",
1596        year =         "1990",
1597        keywords =     "quadtree, octree, radiosity",
1598        note =         "chapter on ray tracing and efficiency, also discusses
1599                       radiosity",
1600}
1601
1602@InProceedings{glassner88d,
1603        author =       "Andrew S. Glassner",
1604        title =        "Space Subdivision for Fast Ray Tracing",
1605        pages =        "159--167",
1606        booktitle =    "Tutorial: Computer Graphics: Image Synthesis",
1607        year =         "1988",
1608        editor =       "Kenneth I. Joy and Charles W. Grant and Nelson L. Max
1609                       and Lansing Hatfield",
1610        publisher =    "Computer Society Press",
1611        annote =       "We have seen that the infamous slowness of ray-tracing
1612                       techniques is caused primarily by the time required for
1613                       ray-object intersection calculations. We have also seen
1614                       a new way of tracing the ray through small subsets of
1615                       space at a speed that reduces the number of ray-object
1616                       intersections that must be made, thereby cutting the
1617                       overall ray-tracing time considerably. \\ This new
1618                       algorithm makes possible the ray tracing of complex
1619                       scenes by medium- and small-scale computers. It is
1620                       hoped that this will enable the power of ray tracing to
1621                       be embraced by more people, helping them generate
1622                       pictures at the leading edge of computer graphics.",
1623}
1624
1625@TechReport{fussell88a,
1626        author =       "Donald Fussell and K. R. Subramanian",
1627        title =        "Fast Ray Tracing Using {K}-{D} Trees",
1628        institution =  "U. of Texas, Austin, Dept. Of Computer Science",
1629        type =         "Technical Report",
1630        number =       "TR-88-07",
1631        month =        mar,
1632        year =         "1988",
1633        keywords =     "hierarchies",
1634}
1635
1636@PhdThesis{subramanian90a,
1637        author =       "K. R. Subramanian",
1638        title =        "Adapting Search Structures to Scene Characteristics
1639                       for Ray Tracing",
1640        month =        dec,
1641        year =         "1990",
1642        type =         "Ph.D. Thesis",
1643        school =       "Department of Computer Sciences, University of Texas
1644                       at Austin",
1645        annote =       "We present new results in adapting search structures
1646                       to scene characteristics for improving the performance
1647                       of ray tracing. A cost model is developed for
1648                       evaluating search structures currently being used in
1649                       ray tracing. The model has been successfully used to
1650                       terminate search structure construction, thus making it
1651                       unnecessary to set termination parameters in advance.
1652                       The model has also been used with limited success to
1653                       compare the performance of different search structures
1654                       for a given scene. \\ A detailed experimental study of
1655                       some of the important properties of search structures
1656                       has been performed. This has resulted in a new adaptive
1657                       search structure that is based on {\em k-d} trees, a
1658                       multi-dimensional binary search structure which
1659                       outperforms existing methods. Its high performance is
1660                       primarily due to the fact that it combines the
1661                       advantages of such structures based on space
1662                       partitioning and those based on bounding volumes. The
1663                       greater flexibility of this search structure allows it
1664                       to terminate automatically at a point where further
1665                       subdivision would result in no additional benefits. \\
1666                       Finally, this search structure has been used to render
1667                       volume models from scientific applications such as
1668                       medical imaging and molecular modeling. Its advantages
1669                       over traditional volume rendering techniques have been
1670                       demonstrated.",
1671}
1672
1673@TechReport{subramanian90b,
1674        author =       "K. R. Subramanian and Donald Fussell",
1675        title =        "A Cost Model for Ray Tracing Hierarchies",
1676        institution =  "U. of Texas, Austin, Dept. Of Computer Science",
1677        type =         "Technical Report",
1678        number =       "TR-90-04",
1679        month =        mar,
1680        year =         "1990",
1681        keywords =     "hierarchies",
1682}
1683
1684@TechReport{Subramanian:1990:FAP,
1685        author =       "K. R. Subramanian and Donald Fussell",
1686        title =        "Factors Affecting Performance of Ray Tracing
1687                       Hierarchies",
1688        year =         "1990",
1689        month =        jul,
1690        number =       "R-90-21",
1691        type =         "Technical Report",
1692        institution =  "Dept. of Computer Sciences, Univ. of Texas at Austin",
1693        keywords =     "octree",
1694}
1695
1696@Article{Vanecek:1991:BIM,
1697  author =       "G. {Vanecek, Jr.}",
1698  title =        "Brep-index: a multidimensional space partitioning
1699                 tree",
1700  journal =      "Internat. J. Comput. Geom. Appl.",
1701  volume =       "1",
1702  number =       "3",
1703  year =         "1991",
1704  pages =        "243--261",
1705  keywords =     "classification, Brep, BSP tree, data structures",
1706}
1707
1708@PhdThesis{semwal87a,
1709        author =       "S. K. Semwal",
1710        title =        "The Slicing Extent Technique for Fast Ray Tracing",
1711        year =         "1987",
1712        type =         "Ph.D. Thesis",
1713        school =       "Department of Computer Science, University of Central
1714                       Florida",
1715        annote =       "A new technique for image generation using ray tracing
1716                       is introduced. The `Slicing Extent Technique'' (SET)
1717                       partitions object space with slicing planes
1718                       perpendicular to all three axes. Planes are divided
1719                       into two dimensional rectangular cells, which contain
1720                       pointers to nearby objects. \\ Cell size and the space
1721                       slices varies, and is determined by the objects'
1722                       locations and orientations. Unlike oct-tree and other
1723                       space-partitioning methods, SET is not primarily
1724                       concerned with dividing space into mutually exclusive
1725                       volume elements (Voxels') and identifying objects
1726                       within each voxel. Instead, SET is based on analysis of
1727                       projections of objects onto slicing planes. \\ In
1728                       comparison to the existing space subdivision methods
1729                       for ray tracing, SET avoids tree traversal and exhibits
1730                       no anomalous behavior. There is no reorganization when
1731                       new objects arrive. Preprocessing to create slices is
1732                       inexpensive and produces a finely tuned filter
1733                       mechanism which supports rapid ray tracing.",
1734}
1735
1736@TechReport{semwal86a,
1737        author =       "S. K. Semwal and J. M. Moshell",
1738        title =        "Geometric Issues of the Slicing Extent Technique for
1739                       Ray Tracing",
1740        year =         "1986",
1741        type =         "Technical Report",
1742        number =       "CS-TR-86-17",
1743        institution =  "Department of Computer Science, University of Central
1744                       Florida",
1745        annote =       "We introduce a new technique for image generation
1746                       using ray tracing. The `Slicing Extent Technique''
1747                       (SET) partitions object space with slicing planes
1748                       perpendicular to all three axes. Planes are dividied
1749                       into two dimensional rectangular cells, which contain
1750                       pointers to nearby objects. \\ Cell size and the space
1751                       between slices varies, and is determined by objects'
1752                       locations and orientations. Unlilke oct-tree and other
1753                       space partitioning methods, SET is not primarily
1754                       concerned with dividing space into mutually exclusive
1755                       volume elements (oxels') and identifying objects
1756                       within each voxel. Instead, SET is based on analysis of
1757                       projections of objects onto slicing planes. \\ The
1758                       analysis of projections onto planes leads to an
1759                       interesting geometric problem of `marking the cells''
1760                       on the various planes so that no ray-object
1761                       intersection goes undetected. In this paper, we show
1762                       that our method of `marking the cells'' for spheres
1763                       and polyhedras is sufficient in this sense. The nature
1764                       of these extents is analyzed. \\ In comparison to the
1765                       existing methods for ray tracing, SET avoids tree
1766                       traversal. Preprocessing to create slices is
1767                       inexpensive and produces a finely tuned filter
1768                       mechanism which supports rapid ray tracing. \\ SET
1769                       resembles other efforts to speed up ray tracing
1770                       inasmuch as a two step process is used. First, an
1771                       approximate `filter'' technique eliminates most
1772                       possible ray/object collisions. Then an accurate
1773                       computation evaluates the remaining possible collisions
1774                       and provides information for the generation of
1775                       subsequent rays.",
1776}
1777
1778@Article{jevans89b,
1779      author =       "David Jevans and Brian Wyvill",
1780      title =        "Adaptive voxel subdivision for ray tracing",
1781      pages =        "164--172",
1782      journal =      "Proceedings of Graphics Interface '89",
1783      year =         "1989",
1784      month =        jun,
1785      conference =   "held in London, Ontario; 19-23 June 1989",
1786      keywords =     "spatial subdivision, octree",
1787      annote =       "Although regular subdivision has been shown to be
1788                     efficient at ray tracing scenes where objects are
1789                     evenly distributed, such algorithms perform poorly when
1790                     objects are concentrated in a small number of voxels.
1791                     In this paper, a method is presented where voxels in a
1792                     regular grid are examined and recursively subdivided
1793                     depending on object density. This integration of
1794                     regular and adaptive spatial subdivision methods allows
1795                     images consisting of large regularly distributed
1796                     objects and small dense objects to be ray traced
1797                     efficiently. The parameters controlling the coarseness
1798                     of the voxel grid, depth of adaptive subdivision trees,
1799                     and maximum number of polygons per voxel are varied and
1800                     their effects on execution time, subdivision time, and
1801                     memory use are measured.",
1802}
1803
1804@InProceedings{Jevans:1990:RTS,
1805      author =       "David A. J. Jevans",
1806      title =        "Ray tracing scenes of varying local complexity",
1807      booktitle =    "Proceedings of the 1990 Western Computer Graphics
1808                     Symposium",
1809      year =         "1990",
1810      month =        mar,
1811      conference =   "held in Banff, Alberta; 4-8 March 1990",
1812      keywords =     "space subdivision, adaptive, cost function",
1813}
1814
1815@InProceedings{Nemoto:1986:ASS,
1816      author =       "Keiji Nemoto and Takao Omachi",
1817      title =        "An Adaptive Subdivision by Sliding Boundary Surfaces
1818                     for Fast Ray Tracing",
1819      pages =        "43--48",
1820      booktitle =    "Proceedings of Graphics Interface '86",
1821      year =         "1986",
1822      month =        may,
1823      editor =       "M. Green",
1824      conference =   "held in Vancouver, B.C.; 26-30 May 1986",
1825      keywords =     "adaptive subdivision algorithm on a parallel
1826                     architecture, parallel processing",
1827      annote =       "They describe a dynamic load-balanced ray tracer. One
1828                     of the first load-balanced ray tracers. \\ This paper
1829                     presents an adaptive subdivision algorithm for fast ray
1830                     tracing implemented on parallel architecture using a
1831                     three dimensional computer array. The object space is
1832                     divided into several subregions and boundary surfaces
1833                     for the subregions are adaptively slid to redistribute
1834                     loads of the computers uniformly. Since the shape of
1835                     the subregions is preserved as orthogonal
1836                     parallelepiped the redistribution overhead can be kept
1837                     small. The algorithm is quite simple but can avoid load
1838                     concentration to a particular computer. \\ Simulation
1839                     results reveal that the adaptive space subdivision
1840                     algorithm by sliding boundary surfaces reduces the
1841                     computing time to 3/4 - 1/5 as much as that for the
1842                     conventional space subdivision algorithm with no
1843                     redistribution, which reduces the computing time almost
1844                     proportionally to the number of computers.",
1845}
1846
1847@MastersThesis{Jevans90,
1848      author =       "David Jevans",
1849      title =        "Adaptive Voxel Subdivision for Ray Tracing",
1850      school =       "Dept. of Computer Science, Univ. of Calgary",
1851      type =         "Master's Thesis",
1852      year =         "1990",
1853      keywords =     "grid subdivision, hierarchical subdivision",
1854      note =         "long version of paper",
1855}
1856
1857@TechReport{naylor86a,
1858      author =       "Bruce Naylor and William Thibault",
1859      title =        "Application of {BSP} Trees to Ray-Tracing and {CGS}
1860                     Evaluation",
1861      institution =  "Georgia Institute of Tech., School of Information and
1862                     Computer Science",
1863      type =         "Technical Report",
1864      address =      "Atlanta, Georgia",
1865      number =       "GIT-ICS 86/03",
1866      month =        feb,
1867      year =         "1986",
1868      keywords =     "hierarchies, BSP tree, CSG",
1869      note =         "true BSP-trees (not just generalized octrees) used for
1870                     efficiency",
1871}
1872
1873@MastersThesis{lin87a,
1874      author =       "Jimmy Jih-Ming Lin",
1875      title =        "Fast Ray Tracing on {BSP}-Trees",
1876      year =         "1987",
1877      type =         "M.Sc. Thesis",
1878      school =       "Department of Computer Science, University of Central
1879                     Florida",
1880      keywords =     "hierarchies",
1881      annote =       "Based on these analyses and experiments, the BSP-Trace
1882                     Method may not be the best solution for speeding up the
1883                     ray tracing, but it is worthwhile subject for research.
1884                     The potential drawbacks of the BSP-Trace which make it
1885                     no better than the Octree Method are: \\ (1) The number
1886                     of surfaces on the BSP-Tree is typically far more than
1887                     the original number of surfaces, because of the
1888                     splitting of surfaces into two by other surfaces'
1889                     planes; \\ (2) The Octree Method only needs to test
1890                     those objects which reside in the selected voxels, and
1891                     the BSP-Trace needs to consider the objects in the
1892                     whole half-space. \\ [FUJI86] mentioned that the memory
1893                     requirement for the octree is very costly, but for the
1894                     BSP-Tree, it can be taken care of very efficiently. The
1895                     bottleneck of the Octree Method is the time spent on
1896                     traveling up and down the Octree [FUJI86], and our
1897                     experiments show that this time is around 35\% of the
1898                     total time. The solution to reduce the traveling time
1899                     is to lower the height of the octree, but meanwhile the
1900                     increase in the number of objects contained in the
1901                     voxel means more intersections per ray. Thus, a new
1902                     data structure for fast ray tracing which combines the
1903                     Octree and BSP-Tree is proposed. \\ The new data
1904                     structure contains an octree on the top, and every leaf
1905                     voxel consists of a BSP-Tree. This will cut down both
1906                     the tree traveling time (by lowering the tree height)
1907                     and the memory consumed by the octree. Also, if we can
1908                     keep the number of objects inside the voxel down, the
1909                     increased number of surfaces by using the BSP-Tree is
1910                     limited. This thus will reduce the number of
1911                     intersection tests made inside the voxel.",
1912}
1913
1914
1915@InProceedings{devillers89b,
1916        author =       "Olivier Devillers",
1917        title =        "Tools to Study the Efficiency of Space Subdivision
1918                       Structures for Ray Tracing",
1919        pages =        "467--481",
1920        booktitle =      "Proceedings of the PIXIM '89",
1921        year =         "1989",
1922        annote =       "Space Subdivision structures are often used to improve
1923                       the performance of ray tracing. The subject of this
1924                       article is to study theoretically the effects of the
1925                       subdivision on the CPU time. The average number of
1926                       regions crossed by a ray is calculated in several cases
1927                       of subdivision. \\ With a space subdivision scheme, the
1928                       complexity of ray tracing is due to two main factors:
1929                       computation of the intersections within a region, and
1930                       computation of the sequence of regions intersected by a
1931                       given ray. The complexity of these two points is
1932                       studied. The distribution of the objects among the
1933                       regions is evaluated, and a method to compute the
1934                       average number of regions crossed by a ray for a given
1935                       method of subdivisions is proposed. This method is
1936                       applied to some usual space subdivision techniques:
1937                       octree, bounding boxes, grid, and macro-regions.",
1938}
1939
1940@InProceedings{dAmore:1992:OBP,
1941  author =       "F. d'Amore and P. G. Franciosa",
1942  title =        "On the optimal binary plane partition for sets of
1943                 isothetic rectangles",
1944  booktitle =    "Proc. 4th Canad. Conf. Comput. Geom.",
1945  year =         "1992",
1946  pages =        "1--5",
1947}
1948
1949@InProceedings{Chin:1992:FOP,
1950  author =       "Norman Chin and Steven Feiner",
1951  title =        "Fast object-precision shadow generation for areal
1952                 light sources using {BSP} trees",
1953  pages =        "21--30",
1954  booktitle =    "Computer Graphics (1992 Symposium on Interactive 3D
1955                 Graphics)",
1956  volume =       "25",
1957  number =       "2",
1958  year =         "1992",
1959  month =        mar,
1960  editor =       "David Zeltzer",
1961  conference =   "held in Boston; 29 March - 1 April 1992",
1962  keywords =     "shadow volume, area light source, penumbra, umbra",
1963  annote =       "",
1964}
1965
1966@InProceedings{Chrysanthou:1995:SVB,
1967  author =       "Yiorgos Chrysanthou and Mel Slater",
1968  title =        "Shadow Volume {BSP} Trees for Computation of Shadows
1969                 in Dynamic Scenes",
1970  editor =       "Pat Hanrahan and Jim Winget",
1971  pages =        "45--50", 
1972  booktitle =    "1995 Symposium on Interactive {3D} Graphics",
1973  year =         "1995",
1974  organization = "ACM SIGGRAPH",
1975  month =        apr,
1976  note =         "ISBN 0-89791-736-7",
1977}
1978
1979@MastersThesis{macdonald88a,
1980  author =       "David MacDonald",
1981  title =        "Space Subdivision Algorithms for Ray Tracing",
1982  year =         "1988",
1983  type =         "M.Sc. Thesis",
1984  school =       "Department of Computer Science, University of
1985                 Waterloo",
1986  annote =       "Ray tracing provides computer rendering of synthetic
1987                 images with many realistic qualities, but is
1988                 computationally expensive. Ray tracing requires testing
1989                 of rays against a scene to see which objects, if any,
1990                 are intersected. The high number of such tests required
1991                 by typical ray tracers contributes significantly to the
1992                 computational expense of ray tracing. \\ An efficient
1993                 method of reducing the computation involved in the
1994                 intersection tests is to organize the objects composing
1995                 the scene into one of several types of hierarchical
1996                 data structures. \\ This thesis describes algorithms
1997                 for the construction, storage, and traversal of the
1998                 space subdivision hierarchy. Methods are suggested for
1999                 decreasing computational requirements of the data
2000                 structure with respect to these three areas. \\ One
2001                 suggested strategy for improving performance in all
2002                 three areas (construction, storage, and traversal) is
2003                 implemented for the bintree structure. The performance
2004                 of these simulations is compared with implementations
2005                 of contemporary methods and some efficiency gains are
2006                 shown. \\ Further work is suggested, including
2007                 adaptation of some of the ideas presented within this
2008                 thesis to more general types of hierarchical
2009                 structures.",
2010}
2011
2012@TechReport{Quek:1988:ESS,
2013  author =       "Lee Hian Quek and D. D. Hearn",
2014  title =        "Efficient Space-Subdivision Methods in Ray-Tracing
2015                 Algorithms",
2016  year =         "1988",
2017  month =        nov,
2018  number =       "UIUCDCS-R-88-1468",
2019  type =         "Report No.",
2020  institution =  "Dept. of Computer Science, Univ. of Illinois at
2021                 Urbana-Champaign",
2022  keywords =     "efficiency",
2023  anote  = "Ray tracing provides a simple and powerful tool for the
2024generation of highly realistic displays. However, it is a computationally
2025expensive approach. A basic ray-tracing algorithm employing no antialiasing
2026may require several hours to render a scene of moderate complexity. Methods
2027for attaining higher picture quality, such as supersampling, adaptive
2028sampling, and distributed sampling, require even longer ray-processing
2029times. One method for improving the performance of ray-tracing algorithms is
2030to reduce ray-object intersection calculations by employing spatial
2031subdivision techniques to group objects in a scene. Here, we consider some
2032improvements that can be made to space-subdivision ray tracers by reducing
2033ray-traversal calculations and by implementing the algorithms on parallel
2034vector architectures.",
2035}
2036
2037@Book{Semwal:1992:RTU,
2038  author =       "Sudhanshu Kumar Semwal and Charulata K. Kearney and J.
2039                 Michael Moshell",
2040  title =        "Ray Tracing Using the Slicing Extent Technique",
2041  year =         "1992",
2042  publisher =    "International Conference on 3D Graphics (?)",
2043  anote = "We present a novel approach to ray tracing called the Slicing
2044Extent Technique (SET) and its variations. SET partitions object space with
2045slicing planes perpendicular to all three axes. Slicing planes are divided
2046into two dimensional rectangular cells, which contain pointers to nearby
2047objects. The novelty of SET is that rather than using a collection of
2048volumes as an extent, SET uses a collection of planar cells and is based on
2049analysis of projections of objects onto slicing planes. These rectangular
2050cells are used to quickly traverse through the sparse area of the scene and
2051also provide further subdivision in the highly populated dense area. These
20522D cells can also define tighter extents. In comparison to the existing
2053space subdivision techniques for ray tracing, SET avoids tree traversal and
2054multiple ray-object intersections. It guarantees no increase in image
2055generation time when number of cells per slice increase in multiples of
2056four. There is no reorganization when new objects arrive and preprocessing
2057to create slices is inexpensive.",
2058}
2059
2060TechReport{Wilson92b,
2061  author =       "Tom Wilson and Narsingh Deo",
2062  title =        "Extent Tracing: Algorithm and Implementation",
2063  institution =  "Department of Computer Science, University of Central
2064                 Florida",
2065  type =         "Technical Report",
2066  number =       "CS-TR-92-34",
2067  month =        dec,
2068  year =         "1992",
2069  keywords =     "efficiency",
2070  anote = "This paper describes a new ray tracing acceleration algorithm
2071called extent tracing. The algorithm works on a structure that is
2072conceptually related to a hierarchical tree of extents (HTE), but does not
2073require the hierarchy. To speed up extent tracing, spatial subdivision is
2074added, resulting in a nonuniform subdivision grid. Implementation details
2075and the results of comparisons to some other established acceleration
2076techniques are given.",
2077}
2078
2079@TechReport{Wilson92,
2080  author =       "Tom Wilson and Narsingh Deo",
2081  title =        "Comparing Extent Tracing to Other Ray Tracing
2082                 Accelerators",
2083  institution =  "Department of Computer Science, University of Central
2084                 Florida",
2085  type =         "Technical Report",
2086  number =       "CS-TR-92-21",
2087  month =        sep,
2088  year =         "1992",
2089  keywords =     "efficiency",
2090  anote = "This report examines the feasibility of a new ray-tracing
2091acceleration scheme called extent tracing by comparing it to some
2092established techniques on established benchmark scenes. The other techniques
2093implemented for comparison are binary space-partitioning (BSP) tree,
2094hierarchical tree of extents (HTE), octree, and uniform subdivision. The
2095statistics used in the comparison are the execution times, memory
2096requirements, object intersections per ray, bounding volume intersections
2097per ray, and voxels traversed per ray.",
2098}
2099
2100@TechReport{Wilson92a,
2101  author =       "Tom Wilson and Narsingh Deo",
2102  title =        "Acceleration Schemes for Ray Tracing",
2103  institution =  "Department of Computer Science, University of Central
2104                 Florida",
2105  type =         "Technical Report",
2106  number =       "CS-TR-92-22",
2107  month =        sep,
2108  year =         "1992",
2109  keywords =     "efficiency",
2110}
2111
2112@InProceedings{Speer:1985:TEA,
2113  author =       "L. R. Speer and T. D. Derose and B. A. Barsky",
2114  title =        "A Theoretical and Empirical Analysis of Coherent
2115                 Ray-Tracing",
2116  booktitle =    "Graphics Interface '85 Proceedings",
2117  pages =        "1--8",
2118  year =         "1985",
2119  editor =       "M. Wein and E. M. Kidd",
2120  organization = "Canadian Inf. Process. Soc.",
2121  conference =   "held in Montreal, Quebec, Canada; 27--31 May 1985",
2122  keywords =     "I37 ray-tracing, I37 image synthesis, I30 picture
2123                 processing",
2124  annote =       "The use of {\em coherence} has been advocated as a
2125                 means of reducing the large computational cost of the
2126                 ray-tracing method of image synthesis. This paper
2127                 examines the theoretical and empirical performance of a
2128                 typical coherent ray-tracing algorithm, one that
2129                 exploits the similarity between the intersection trees
2130                 generated by successive rays. It is shown that despite
2131                 the large degree of coherence present in a scene, the
2132                 need to ensure the validity of ray-object intersections
2133                 prevents any significant computational savings. This
2134                 indicates that other algorithmic methods must be used
2135                 in order to substantially reduce the computational cost
2136                 of ray-traced imagery.",
2137}
2138
2139@InProceedings{Isler:1991:HSS,
2140  author =       "Veysi Isler and Cevdet Aykanat and Bulent
2141                 {\"{O}}zgu\c{c}",
2142  title =        "A heuristic 3{D} space subdivision algorithm for ray
2143                 tracing",
2144  pages =        "499--504",
2145  booktitle =    "COMPUGRAPHICS '91",
2146  volume =       "I",
2147  year =         "1991",
2148  conference =   "held in Sesimbra, Portugal; 16-20 September 1991",
2149}
2150
2151@Article{Bouville??,
2152  author =       "Christian Bouville and Jean-Luc Dubois and Isabelle
2153                 Marchal",
2154  title =        "A Space Tracing Method Applied to Polygonal Models",
2155  journal =      "course paper",
2156  year = "???",
2157  anote = " The ray-tracing rendering method gives the highest possible
2158level of realism that can be attained in computer graphics. Recently many
2159alternatives have been reported on ways to speed up this process and
2160particularly by means of a space subdivision technique. We propose such an
2161algorithm specially adapted to polygonal models. A BSP tree technique is
2162used to perform space subdivision and a spatial index allows direct access
2163to any cell. A method which minimizes primary ray computations and an
2164algorithm which avoids the tracing of a large number of rays towards light
2165sources have been studied. Results about time and space required by this
2166algorithm are presented.",
2167}
2168
2169@Article{Kalinowski94,
2170       author= "Kalinowski J. and Sas J.",
2171        title= "Acceleration Techniques for Ray Tracing - Experimental
2172                 Comparison",
2173      journal= "MICROCOMPUTER '94 Computer Graphics and Vision",
2174      month  = "feb",
2175      year   = "1994",
2176      pages  = "??-??",
2177      place  = "Zakopane in Poland",
2178      note   = "uniform subdivision",
2179      anote  = "In this paper the experimental results of applying a series
2180of acceleration methods to the ray tracing process are presented. The
2181acceleration possibilities at two stages have been distinguished: the stage
2182of ray traversal through the scene space and ray-triangle intersection
2183testing stage. At the first stage uniform space subdivision has been
2184compared with two level n-tree schema. At the stage of ray-triangle
2185intersection testing the computational complexity of the set of algorithms
2186has been compared and the gains obtained as a result of a series of
2187improvements to the ordinary algorithm are presented.",
2188}
2189
2190
2191
2192@article{vko91,
2193  author="M. van Kreveld and H. Overmars",
2194  title="Divided k-d Trees",
2195  journal="Algorithmica",
2196  year="1991",
2197  volume="6",
2198  number="",
2199  pages="840-858"
2200}
Note: See TracBrowser for help on using the repository browser.