Context Navigation

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,
73	title={Approximations and Optimal Geometric Divide-and-Conquer},
74	author={Ji{\v{r}}{\'\i} Matou{\v{s}}ek},
75	pages={203--208},
76	journal=jcss,
77	year=1995,
78	month=apr,
79	volume=50,
80	number=2,
81	preliminary={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
110	Article{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
531	Article{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
687	InProceedings{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
1383	ceedings{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
2024	generation of highly realistic displays. However, it is a computationally
2025	expensive approach. A basic ray-tracing algorithm employing no antialiasing
2026	may require several hours to render a scene of moderate complexity. Methods
2027	for attaining higher picture quality, such as supersampling, adaptive
2028	sampling, and distributed sampling, require even longer ray-processing
2029	times. One method for improving the performance of ray-tracing algorithms is
2030	to reduce ray-object intersection calculations by employing spatial
2031	subdivision techniques to group objects in a scene. Here, we consider some
2032	improvements that can be made to space-subdivision ray tracers by reducing
2033	ray-traversal calculations and by implementing the algorithms on parallel
2034	vector 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
2044	Extent Technique (SET) and its variations. SET partitions object space with
2045	slicing planes perpendicular to all three axes. Slicing planes are divided
2046	into two dimensional rectangular cells, which contain pointers to nearby
2047	objects. The novelty of SET is that rather than using a collection of
2048	volumes as an extent, SET uses a collection of planar cells and is based on
2049	analysis of projections of objects onto slicing planes. These rectangular
2050	cells are used to quickly traverse through the sparse area of the scene and
2051	also provide further subdivision in the highly populated dense area. These
2052	2D cells can also define tighter extents. In comparison to the existing
2053	space subdivision techniques for ray tracing, SET avoids tree traversal and
2054	multiple ray-object intersections. It guarantees no increase in image
2055	generation time when number of cells per slice increase in multiples of
2056	four. There is no reorganization when new objects arrive and preprocessing
2057	to create slices is inexpensive.",
2058	}
2059
2060	TechReport{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
2071	called extent tracing. The algorithm works on a structure that is
2072	conceptually related to a hierarchical tree of extents (HTE), but does not
2073	require the hierarchy. To speed up extent tracing, spatial subdivision is
2074	added, resulting in a nonuniform subdivision grid. Implementation details
2075	and the results of comparisons to some other established acceleration
2076	techniques 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
2091	acceleration scheme called extent tracing by comparing it to some
2092	established techniques on established benchmark scenes. The other techniques
2093	implemented for comparison are binary space-partitioning (BSP) tree,
2094	hierarchical tree of extents (HTE), octree, and uniform subdivision. The
2095	statistics used in the comparison are the execution times, memory
2096	requirements, object intersections per ray, bounding volume intersections
2097	per 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
2158	level of realism that can be attained in computer graphics. Recently many
2159	alternatives have been reported on ways to speed up this process and
2160	particularly by means of a space subdivision technique. We propose such an
2161	algorithm specially adapted to polygonal models. A BSP tree technique is
2162	used to perform space subdivision and a spatial index allows direct access
2163	to any cell. A method which minimizes primary ray computations and an
2164	algorithm which avoids the tracing of a large number of rays towards light
2165	sources have been studied. Results about time and space required by this
2166	algorithm 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
2180	of acceleration methods to the ray tracing process are presented. The
2181	acceleration possibilities at two stages have been distinguished: the stage
2182	of ray traversal through the scene space and ray-triangle intersection
2183	testing stage. At the first stage uniform space subdivision has been
2184	compared with two level n-tree schema. At the stage of ray-triangle
2185	intersection testing the computational complexity of the set of algorithms
2186	has been compared and the gains obtained as a result of a series of
2187	improvements 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.

Context Navigation

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

Download in other formats: