Graphics Gems III (IBM Version)

VI. 6

A LINEAR-TIME SIMPLE BOUNDING VOLUME ALGORITHM

Xiaolin Wu,     University of Western Ontario, London, Ontario, Canada

Publisher Summary

Three-dimensional bounding volume is a ubiquitous tool of accelerating ray tracing and visibility testing. The two most common types of bounding volume are box and sphere. That is because the intersections between rays and boxes or rays and spheres involve very simple computations. The smallest bounding volume has received considerable attention in the computational geometry community. The O(N) algorithm for the smallest bounding sphere and the O(N log N) algorithm for the three-dimensional Voronoi diagram exist, and they are both optimal. Simple and fast approximation algorithms for smallest bounding ...