Article

Ray tracing dynamic scenes using selective restructuring

Authors:

Dinesh ManochaAuthors Info & Claims

EGSR'07: Proceedings of the 18th Eurographics conference on Rendering Techniques

Pages 73 - 84

Published: 25 June 2007 Publication History

Publisher Site Get Access

Abstract

We present a novel algorithm to selectively restructure bounding volume hierarchies (BVHs) for ray tracing dynamic scenes. We derive two new metrics to evaluate the culling efficiency and restructuring benefit of any BVH. Based on these metrics, we perform selective restructuring operations that efficiently reconstruct small portions of a BVH instead of the entire BVH. Our approach is general and applicable to complex and dynamic scenes, including topological changes. We use the selective restructuring algorithm to improve the performance of ray tracing dynamic scenes that consist of hundreds of thousands of triangles. In our benchmarks, we observe up to an order of magnitude improvement over prior BVH-based ray tracing algorithms.

References

[1]

BRADSHAW G., O'SULLIVAN C.: Adaptive medial-axis approximation for sphere-tree construction. ACM Trans. on Graphics 23, 1 (2004). 2

Digital Library

[2]

CARR N., HART J.: Two algorithms for fast reclustering of dynamic meshed surfaces. In Eurographics Symposium on Geometry Processing (2004). 3

Digital Library

[3]

CLINE D., STEELE K., EGBERT P. K.: Lightweight bounding volumes for ray tracing. Journal of Graphics Tools: JGT (2006). 1

[4]

GÜNTHER J., FRIEDRICH H., WALD I., SEIDEL H.-P., SLUSALLEK P.: Ray tracing animated scenes using motion decomposition. Computer Graphics Forum 25, 3 (September 2006). 3

[5]

GOTTSCHALK S., LIN M., MANOCHA D.: OBB-Tree: A hierarchical structure for rapid interference detection. Proc. of ACM Siggraph'96 (1996), 171-180. 2

Digital Library

[6]

GUIBAS L., NGUYEN A., RUSSEL D., ZHANG L.: Collision detection for deforming necklaces. In Symp. on Computational Geometry (2002), pp. 33-42. 3

Digital Library

[7]

GOLDSMITH J., SALMON J.: Automatic creation of object hierarchies for ray tracing. IEEE Comput. Graph. Appl. 7, 5 (1987), 14-20. 1, 4

Digital Library

[8]

HAVRAN V.: Heuristic Ray Shooting Algorithms. PhD thesis, Dept. of CSE, Czech Technical Univ. in Prague, 2000. 4, 10

[9]

HAVRAN V., HERZOG R., SEIDEL H.-P.: On the fast construction of spatial data structures for ray tracing. 71-80. 3

[10]

HUNT W., MARK W. R., STOLL G.: Fast kd-tree construction with an adaptive error-bounded heuristic. In IEEE Symposium on Interactive Ray Tracing (2006). 3, 11

[11]

HUBBARD P. M.: Interactive collision detection. In Proceedings of IEEE Symposium on Research Frontiers in Virtual Reality (October 1993). 2

[12]

IZE T., WALD I., PARKER S. G.: Asynchronous bvh construction for ray tracing dynamic scenes on parallel multi-core architectures. In Eurographics Symposium on Parallel Graphics and Visualization (2007). 11

Digital Library

[13]

JAMES D. L., PAI D. K.: BD-Tree: Output-sensitive collision detection for reduced deformable models. Proc. of ACM SIGGRAPH (2004), 393-398. 3

Digital Library

[14]

KLOSOWSKI J., HELD M., MITCHELL J., SOWIZRAL H., ZIKAN K.: Ef_cient collision detection using bounding volume hierarchies of k-dops. IEEE Trans. on Visualization and Computer Graphics 4, 1 (1998), 21-37. 2

Digital Library

[15]

KAT T., KAJIYA J.: Ray tracing complex scenes. Computer Graphics (1986), 269-278. 1

Digital Library

[16]

KRISHNAN S., PATTEKAR A., LIN M., MANOCHA D.: Spherical shell: A higher order bounding volume for fast proximity queries. In Proc. of Third International Workshop on Algorithmic Foundations of Robotics (1998), pp. 122-136. 2

Digital Library

[17]

LEXT J., ASSARSSON U., AKENINE-MÖLLER T.: A benchmark for animated ray tracing. In IEEE Computer Graphics and Applications (2001). 2, 3

Digital Library

[18]

LARSSON T., AKENINE-MÖLLER T.: Ef_cient collision detection for models deformed by morphing. Visual Computer 19 (2003), 164-174. 3

[19]

LARSSON T., AKENINE-MÖLLER T.: Strategies for Bounding Volume Hierarchy Updates for Ray Tracing of Deformable Models. Tech. rep., 2003. 1

[20]

LARSSON T., AKENINE-MÖLLER T.: A dynamic bounding volume hierarchy for generalized collision detection. Computers and Graphics 30, 3 (2006), 451-460. 2, 3, 8, 9

Digital Library

[21]

LARSEN E., GOTTSCHALK S., LIN M., MANOCHA D.: Fast Proximity Queries with Swept Sphere Volumes. Tech. Rep. TR99-018, Department of Computer Science, University of North Carolina, 1999. 2

[22]

LIN M., MANOCHA D.: Collision and proximity queries. In Handbook of Discrete and Computational Geometry (2003). 1, 2

[23]

LAUTERBACH C., YOON S., TUFT D., MANOCHA D.: RT-DEFORM: Interactive ray tracing of dynamic scenes using bvhs. IEEE Symposium on Interactive Ray Tracing (2006). 1, 3, 8, 9, 11

[24]

MACDONALD J. D., BOOTH K. S.: Heuristics for ray tracing using space subdivision. Visual Computer (1990). 4

Digital Library

[25]

OTADUY M., CHASSOT O., STEINEMANN D., GROSS M.: Balanced hierarchies for collision detection between fracturing objects. In IEEE Virtual Reality (2007). 1, 3, 11

[26]

POPOV S., GÜNTHER J., SEIDEL H.-P., SLUSALLEK P.: Experiences with streaming construction of SAH KD-trees. In IEEE Symp. on Interactive Ray Tracing (2006). 3, 11

[27]

RESHETOV A., SOUPIKOV A., HURLEY J.: Multi-level ray tracing algorithm. ACM Trans. Graph. 24, 3 (2005), 1176- 1185. 10

Digital Library

[28]

RUBIN S. M., WHITTED T.: A 3-dimensional representation for fast rendering of complex scenes. Computer Graphics 14, 3 (July 1980), 110-116. 1

Digital Library

[29]

SAMET H.: Foundations of MultiDimensional and Metric Data Structures. Morgan Kaufmann, 2006. 2, 3

Digital Library

[30]

SANNA A., MILANI M.: CDFast: an algorithm combining different bounding volume strategies for real time collision detection. SCI Proceedings 2 (2004), 144-149. 2

[31]

TESCHNER M., KIMMERLE S., HEIDELBERGER B., ZACHMANN G., RAGHUPATHI L., FUHRMANN A., CANI M.-P., FAURE F., MAGNENAT-THALMANN N., STRASSER W., VOLINO P.: Collision detection for deformable objects. Computer Graphics Forum 19, 1 (2005), 61-81. 1, 2, 3

[32]

THRANE N., SIMONSEN L. O.: A comparison of acceleration structures for gpu assisted ray tracing, 2005. 11

[33]

VAN DEN BERGEN G.: Ef_cient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools 2, 4 (1997), 1-14. 2, 3

Digital Library

[34]

WALD I., BENTHIN C., SLUSALLEK P.: Distributed Interactive Ray Tracing of Dynamic Scenes. In Proceedings of the IEEE Symposium on Parallel and Large-Data Visualization and Graphics (PVG) (2003). 3

Digital Library

[35]

WALD I., BOULOS S., SHIRLEY P.: Ray Tracing Deformable Scenes using Dynamic Bounding Volume Hierarchies. ACM Transactions on Graphics (2007). 1, 3, 8, 9, 11

Digital Library

[36]

WALD I., HAVRAN V.: On building fast kd-trees for ray tracing, and on doing that in O(N log N). In Proceedings of the 2006 IEEE Symposium on Interactive Ray Tracing (2006). 4, 8

[37]

WÄCHTER C., KELLER A.: Instant ray tracing: The bounding interval hierarchy. In Proceedings of the Eurographics Symposium on Rendering (2006), pp. 139-149. 3

Digital Library

[38]

WOOP S., MARMITT G., SLUSALLEK P.: B-KD Trees for Hardware Accelerated Ray Tracing of Dynamic Scenes. In Proceedings of Graphics Hardware (2006). 3

Digital Library

[39]

WALD I., SLUSALLEK P., BENTHIN C.: Interactive distributed ray tracing of highly complex models. In Rendering Techniques 2001 (Proc. of the 12th EUROGRAPHICS Workshop on Rendering (2001), pp. 277-288. 10

Digital Library

[40]

YOON S.-E., MANOCHA D.: Cache-ef_cient layouts of bounding volume hierarchies. Computer Graphics Forum (Eurographics) 25 (2006), 507-516. 4

[41]

ZACHMANN G., WELLER R.: Kinetic bounding volume hierarchies for deforming objects. In ACM Int'l Conf. on Virtual Reality Continuum and its Applications (2006).

Digital Library

Cited By

Benthin CWoop SWald IÁfra AMcGuire MPatney A(2017)Improved two-level BVHs using partial re-braidingProceedings of High Performance Graphics10.1145/3105762.3105776(1-8)Online publication date: 28-Jul-2017
https://dl.acm.org/doi/10.1145/3105762.3105776
Weller RDebowski NZachmann G(2017)kDetComputer Graphics Forum10.1111/cgf.1311336:2(131-141)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1111/cgf.13113
He LOrtiz REnquobahrie AManocha DKeyser JSander PSubr KWei L(2015)Interactive continuous collision detection for topology changing models using dynamic clusteringProceedings of the 19th Symposium on Interactive 3D Graphics and Games10.1145/2699276.2699286(47-54)Online publication date: 27-Feb-2015
https://dl.acm.org/doi/10.1145/2699276.2699286
Show More Cited By

Index Terms

Ray tracing dynamic scenes using selective restructuring
1. Computing methodologies
  1. Computer graphics
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

Ray tracing deformable scenes using dynamic bounding volume hierarchies

The most significant deficiency of most of today's interactive ray tracers is that they are restricted to static walkthroughs. This restriction is due to the static nature of the acceleration structures used. While the best reported frame rates for ...
Ray tracing dynamic scenes using selective restructuring
SIGGRAPH '07: ACM SIGGRAPH 2007 sketches

Ray tracing has been widely researched due to its ability to generate realistic images. However, the performance of current ray tracing algorithms is considerably slower than GPU-based rasterization algorithms, especially on dynamic scenes. In this ...
Whitted ray-tracing for dynamic scenes using a ray-space hierarchy on the GPU
EGSR'07: Proceedings of the 18th Eurographics conference on Rendering Techniques

In this paper, we present a new algorithm for interactive rendering of animated scenes with Whitted Ray-Tracing, running on the GPU. We focus our attention on the secondary rays (the rays generated by one or more bounces on specular objects), and use ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EGSR'07: Proceedings of the 18th Eurographics conference on Rendering Techniques

June 2007

370 pages

ISBN:9783905673524

Editors:
Jan Kautz
University College London
,
Sumanta Pattanaik
University of Central Florida

Sponsors

ACM: Association for Computing Machinery
Rhône-Alpes La Region: Rhône-Alpes La Region
LA METRO: LA METRO
INRIA: INRIA Rhône-Alpes
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Eurographics Association

Goslar, Germany

Publication History

Published: 25 June 2007

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

12
Total Citations
View Citations
70
Total Downloads

Downloads (Last 12 months)6
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Benthin CWoop SWald IÁfra AMcGuire MPatney A(2017)Improved two-level BVHs using partial re-braidingProceedings of High Performance Graphics10.1145/3105762.3105776(1-8)Online publication date: 28-Jul-2017
https://dl.acm.org/doi/10.1145/3105762.3105776
Weller RDebowski NZachmann G(2017)kDetComputer Graphics Forum10.1111/cgf.1311336:2(131-141)Online publication date: 1-May-2017
https://dl.acm.org/doi/10.1111/cgf.13113
He LOrtiz REnquobahrie AManocha DKeyser JSander PSubr KWei L(2015)Interactive continuous collision detection for topology changing models using dynamic clusteringProceedings of the 19th Symposium on Interactive 3D Graphics and Games10.1145/2699276.2699286(47-54)Online publication date: 27-Feb-2015
https://dl.acm.org/doi/10.1145/2699276.2699286
Bittner JMeister D(2015)T-SAHComputer Graphics Forum10.1111/cgf.1258134:2(527-536)Online publication date: 1-May-2015
https://dl.acm.org/doi/10.1111/cgf.12581
Torkhani FWang KChassery J(2015)Perceptual quality assessment of 3D dynamic meshesImage Communication10.1016/j.image.2014.12.00831:C(185-204)Online publication date: 1-Feb-2015
https://dl.acm.org/doi/10.1016/j.image.2014.12.008
Heo JSeong JKim DOtaduy MHong JTang MYoon SFaure FLarboulette CPopović ZOtaduy M(2010)FASTCDProceedings of the 2010 ACM SIGGRAPH/Eurographics Symposium on Computer Animation10.5555/1921427.1921450(149-158)Online publication date: 2-Jul-2010
https://dl.acm.org/doi/10.5555/1921427.1921450
Garanzha K(2009)The use of precomputed triangle clusters for accelerated ray tracing in dynamic scenesProceedings of the Twentieth Eurographics conference on Rendering10.1111/j.1467-8659.2009.01497.x(1199-1206)Online publication date: 29-Jun-2009
https://dl.acm.org/doi/10.1111/j.1467-8659.2009.01497.x
Zhou KHou QWang RGuo B(2008)Real-time KD-tree construction on graphics hardwareACM SIGGRAPH Asia 2008 papers10.1145/1457515.1409079(1-11)Online publication date: 10-Dec-2008
https://dl.acm.org/doi/10.1145/1457515.1409079
Kasik DDietrich AGobbetti EMarton FManocha DSlusallek PStephens AYoon S(2008)Massive model visualization techniquesACM SIGGRAPH 2008 classes10.1145/1401132.1401190(1-188)Online publication date: 11-Aug-2008
https://dl.acm.org/doi/10.1145/1401132.1401190
Gobbetti EKasik DYoon SHaines EMcGuire M(2008)Technical strategies for massive model visualizationProceedings of the 2008 ACM symposium on Solid and physical modeling10.1145/1364901.1364960(405-415)Online publication date: 2-Jun-2008
https://dl.acm.org/doi/10.1145/1364901.1364960
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten