23 September 1999 Image space subdivision for fast ray tracing
Author Affiliations +
Ray-tracing is notorious of its computational requirement. There were a number of techniques to speed up the process. However, a famous statistic indicated that ray-object intersections occupies over 95% of the total image generation time. Thus, it is most beneficial to work on this bottle-neck. There were a number of ray-object intersection reduction techniques and they could be classified into three major categories: bounding volume hierarchies, space subdivision, and directional subdivision. This paper introduces a technique falling into the third category. To further speed up the process, it takes advantages of hierarchy by adopting a MX-CIF quadtree in the image space. This special kind of quadtree provides simple objects allocation and ease of implementation. The text also included a theoretical proof of the expected performance. For ray-polygon comparison, the technique reduces the order of complexity from linear to square-root, O(n) -> O(2(root)n). Experiments with various shape, size and complexity were conducted to verify the expectation. Results shown that computational improvement grew with the complexity of the sceneries. The experimental improvement was more than 90% and it agreed with the theoretical value when the number of polygons exceeded 3000. The more complex was the scene, the more efficient was the acceleration. The algorithm described was implemented in the polygonal level, however, it could be easily enhanced and extended to the object or higher levels.
© (1999) COPYRIGHT Society of Photo-Optical Instrumentation Engineers (SPIE). Downloading of the abstract is permitted for personal use only.
Billy T.W. Yu, Billy T.W. Yu, William W.H. Yu, William W.H. Yu, "Image space subdivision for fast ray tracing", Proc. SPIE 3811, Vision Geometry VIII, (23 September 1999); doi: 10.1117/12.364088; https://doi.org/10.1117/12.364088


Real Time Perspective Image Generation
Proceedings of SPIE (April 04 1989)
Parallax Barrier 3DTV
Proceedings of SPIE (September 10 1989)
Nonlinear ray tracing for vessel enhanced visualization
Proceedings of SPIE (February 16 2012)

Back to Top