Parallel Construction of Bounding Volumes

Mattias Karlsson
Mälardalen University, Sweden

Olov Winberg
Mälardalen University, Sweden

Thomas Larsson
Mälardalen University, Sweden

Ladda ner artikel

Ingår i: Proceedings of SIGRAD 2010

Linköping Electronic Conference Proceedings 52:11, s. 65-69

Visa mer +

Publicerad: 2010-11-29

ISBN: 978-91-7393-281-3

ISSN: 1650-3686 (tryckt), 1650-3740 (online)


This paper presents techniques for speeding up commonly used algorithms for bounding volume construction using Intel’s SIMD SSE instructions. A case study is presented; which shows that speed-ups between 7–9 can be reached in the computation of k-DOPs. For the computation of tight fitting spheres; a speed-up factor of approximately 4 is obtained. In addition; it is shown how multi-core CPUs can be used to speed up the algorithms further.

Categories and Subject Descriptors (according to ACM CCS): I.3.6 [Computer Graphics]: Methodology and techniques—Graphics data structures and data types


Inga nyckelord är tillgängliga


[Bik04] BIK A. J. C.: The Software Vectorization Handbook. Intel Press; 2004. 1

[DHK07] DAMMERTZ H.; HANIKA J.; KELLER A.: Shallow bounding volume hierarchies for fast SIMD ray tracing of incoherent rays. Computer Graphics Forum 27; 4 (2007); 1225–1233. 1

[GBST06] GERBER R.; BIK A. J. C.; SMITH K. B.; TIAN X.: The Software Optimization Cookbook; 2nd Ed. Intel Press; 2006. 1; 2

[HOM08] HASSABALLAH M.; OMRAN S.; MAHDY Y. B.: A review of SIMD multimedia extensions and their usage in scientific and engineering applications. The Computer Journal 51; 6 (2008); 630–649. 1

[KHM98] KLOSOWSKI J. T.; HELD M.; MITCHELL J. S. B.; SOWIZRAL H.; ZIKAN K.: Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Transactions on visualization and Computer Graphics 4; 1 (1998); 21–36. 1

[LAM06] LARSSON T.; AKENINE-MÖLLER T.: A dynamic bounding volume hierarchy for generalized collision detection. Computers & Graphics 30; 3 (2006); 450–459. 1

[LAML07] LARSSON T.; AKENINE-MÖLLER T.; LENGYEL E.: On faster sphere-box overlap testing. journal of graphics tools 12; 1 (2007); 3–8. 1

[Lar08] LARSSON T.: Fast and tight fitting bounding spheres. In Proceedings of The Annual SIGRAD Conference (November 2008); Linköping University Electronic Press; pp. 27–30. 2

[LGS09] LAUTERBACH C.; GARLAND M.; SENGUPTA S.; LUEBKE D.; MANOCHA D.: Fast BVH construction on GPUs. Computer Graphics Forum 28; 2 (2009). 5

[MKE03] MEZGER J.; KIMMERLE S.; ETZMUSS O.: Hierarchical techniques in collision detection for cloth animation. Journal of WSCG 11 (2003); 322–329. 1

[MY02] MA W.-C.; YANG C.-L.: Using intel streaming SIMD extensions for 3D geometry processing. In PCM ’02: Proceedings of the Third IEEE Pacific Rim Conference on Multimedia (2002); Springer-Verlag; pp. 1080–1087. 1

[Rit90] RITTER J.: An efficient bounding sphere. In Graphics Gems; Glassner A.; (Ed.). Academic Press; 1990; pp. 301–303. 3

[WBS07] WALD I.; BOULOS S.; SHIRLEY P.: Ray tracing deformable scenes using dynamic bounding volume hierarchies. ACM Transactions on Graphics 26; 1 (2007). 1

[WIP08] WALD I.; IZE T.; PARKER S. G.: Fast; parallel; and asynchronous construction of BVHs for ray tracing animated scenes. Computers & Graphics 32; 1 (2008); 3–13. 5

[YSL98] YANG C.-L.; SANO B.; LEBECK A. R.: Exploiting instruction level parallelism in geometry processing for three dimensional graphics applications. In Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture (1998); pp. 14–24. 1

Citeringar i Crossref