Data Layout Polymorphism for Bounding Volume Hierarchies DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Software and its engineering Compilers CCS: Software and

Christophe Gyurgyik, Alexander J Root, Fredrik Kjolstad · 2025

Read Data Layout Polymorphism for Bounding Volume Hierarchies DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Software and its engineering Compilers CCS: Software and by Christophe Gyurgyik, Alexander J Root, Fredrik Kjolstad (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-15028.txt.

Introduction

Christophe Gyurgyik, Alexander J Root, and Fredrik Kjolstad separate how bounding volume hierarchies store their data from how they are searched. These tree structures speed up graphics, simulation, and analytics by grouping nearby objects, and their speed hinges on memory layout: cache use, bandwidth, and vectorization. In most systems, layout choices are tangled into the search code, so neither side can be tuned freely.

Their language and compiler, called Scion, lets programmers state a hierarchy's layout on its own, apart from any traversal algorithm. The authors show Scion can express the broad range of layout tricks used in high-performance codes. Untangling the two choices should let one search routine run fast on many machines.

Catalog record

CREATORChristophe Gyurgyik, Alexander J Root, Fredrik Kjolstad
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE121 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-15028

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Data Layout Polymorphism for Bounding Volume Hierarchies DOI: XXXXXXX.XXXXXXX Conference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NY ISBN: 978-1-4503-XXXX-X/2018/06 CCS: Software and its engineering Compilers CCS: Software and its engineering Domain specific languages CCS: Computing methodologies Ray tracing CCS: Computing methodologies Collision detection Christophe Gyurgyik, Alexander J Root, Fredrik Kjolstad Abstract . Bounding volume hierarchies are ubiquitous acceleration structures in graphics, scientific computing, and data analytics. Their performance depends critically on data layout choices that affect cache utilization, memory bandwidth, and vectorization—increasingly dominant factors in modern computing. Yet, in most programming systems, these layout choices are hopelessly entangled with the traversal logic. This entanglement prevents developers from independently optimizing data layouts and algorithms across different contexts, perpetuating a false dichotomy between performance and portability. We introduce Scion , a domain-specific language and compiler for specifying the data layouts of bounding volume hierarchies independent of tree traversal algorithms. We show that Scion can express a broad spectrum of layout optimizations used in high performance computing while remaining architecture-agnostic. We demonstrate empirically that Pareto-optimal layouts (along performance and memory footprint axes) vary across algorithms, architectures, and workload characteristics. Through systematic design exploration, we also identify a novel ray tracing layout that combines optimization techniques from prior work, achieving Pareto-optimality across diverse architectures and scenes. 1. Introduction In high-performance graphics, scientific computing, and data analytics, bounding volume hierarchies (BVHs) are essential acceleration structures used for spatial queries such as ray tracing, closest point queries, and collision detection. Extensive research has focused on optimizing the layout of these structures due to their substantial impact on performance ( Christensen et al. 2025 ; Eisemann et al. 2012 ; Howard et al. 2019 ; Ericson 2004 ; Káčerik and Bittner 2024 ; Kay and Kajiya 1986a ; Laine et al. 2013 ; Meister et al. 2021 ; Pharr et al. 2023 ; Mahovsky and Wyvill 2006 ; Segovia and Ernst 2010 ; Vaidyanathan et al. 2016 ; Wald et al. 2008 ; Weghorst et al. 1984 ; Woop et al. 2014 ; Ylitie et al. 2017 ; Wodniok et al. 2013 ; Benthin et al. 2018 ; Kim et al. 2010 ; Wächter and Keller 2006 ; Eisemann et al. 2008 ; Havran et al. 2006 ; Lin et al. 2020 ; Bauszat et al. 2010 ; Mora 2011 ; Cline et al. 2006 ; Lauterbach et al. 2008 ; Wald et al. 2007 ; Dammertz et al. 2008 ; Ernst and Greiner 2008 ; Smits 2005 ; Wachter and Keller 2007 ; Mahovsky 2005 ; Stürzlinger and Tobler 1994 ; Wald et al. 2014 ; Benthin et al. 2017 ; Benthin et al. 2021 ; Chitalu et al. 2020 ; Liktor and Vaidyanathan 2016 ; Huang et al. 2025 ; Howard et al. 2016 ; Larsson and Akenine-Möller 2009 ) . However, no single layout is universally optimal. The Pareto frontier of layouts—balancing runtime performance and memory utilization—depends critically on three factors: the algorithm, hardware architecture, and characteristics of the input data. Layouts optimized to maximize performance on CPUs may increase the BVH memory footprint to reduce instruction count or improve cache utilization on latency-bound workloads ( Wald et al. 2014 ; Benthin et al. 2018 ; Woop et al. 2014 ) . On the other hand, memory-efficient layouts are essential for bandwidth-bound systems such as GPUs ( Laine et al. 2013 ; Liu et al. 2023 ; Saed et al. 2022 ; Huang et al. 2025 ) and memory-constrained platforms such as mobile devices ( Lee et al. 2013 ; Nah et al. 2014 ; Kosarevsky et al. 2025 ; Seo et al. 2017 ) , where compact representations directly reduce memory traffic and enable larger scenes to fit in limited memory. Scene properties further complicate the picture, e.g., extremely sparse scenes will benefit from different representations than dense scenes, and the spatial distribution of primitives affects the efficacy of quantization and compression schemes. This produces a substantial exploration space: even a conservative enumeration of k data layouts \times m machines \times n algorithms \times p scenes yields a multifarious set of evaluation contexts, each admitting a potentially different Pareto-optimal solution. Exploring this design space is complex because general-purpose languages tightly couple data layouts with application logic. Optimized layouts employ diverse techniques: global layout transformations, e.g., struct-of-arrays and hybrid variants ( Laine et al. 2013 ; Wodniok et al. 2013 ; Woop et al. 2014 ; Cline et al. 2006 ; Dammertz et al. 2008 ) ; bit field exploitation, e.g., union types ( Benthin et al. 2018 ; Meister et al. 2021 ; Eisemann et al. 2008 ; Pharr et al. 2023 ; Cline et al. 2006 ) ; increased branching factors (arity of the tree) ( Goldsmith and Salmon 1987 ; Woop et al. 2014 ; Ylitie et al. 2017 ; Dammertz et al. 2008 ; Ernst and Greiner 2008 ) ; specialized bounding volume representations ( Woop et al. 2014 ; Káčerik and Bittner 2024 ; Káčerik and Bittner 2025 ; Larsson and Akenine-Möller 2009 ) ; implicit indices ( Smits 2005 ; Cline et al. 2006 ; Bauszat et al. 2010 ; Eisemann et al. 2012 ) ; and compression ( Howard et al. 2019 ; Segovia and Ernst 2010 ; Cline et al. 2006 ; Mahovsky 2005 ; Benthin et al. 2018 ) . Each of these techniques requires pervasive changes throughout the application code, in how fields are accessed, nodes are referenced, and the tree is traversed. Orthogonally, programming language research has developed ways to decouple logical representations from physical layouts . This prior work has focused on fine-grain, per-node layout optimization ( Baudon et al. 2023 ; Chen et al. 2023 ; Colin et al. 2018 ) or coarse-grain composition of data structures hidden behind iterator interfaces ( Kjolstad et al. 2017 ; Liu et al. 2024 ; Hu et al. 2019 ; Pharr and Mark 2012 ) . However, state-of-the-art BVH layout optimization requires coordination across both levels of granularity: how individual nodes are represented and how collections of nodes are organized in memory. We propose a decoupling with control over both. Our key insight is that manual BVH layout optimizations explore different physical realizations of the same underlying logical structure. This enables a clean separation between a tree’s logical specification and its physical representation. This separation preserves the portability and maintainability of traversal algorithms while simultaneously enabling performance engineers to independently tune physical layouts for specific evaluation contexts. Akin to the separation of algorithm and schedule ( Ragan-Kelley et al. 2013 ; Ikarashi et al. 2022 ) , we introduce domain-specific languages to separate algorithm and physical layout. Our primary contributions are the following: • Two domain-specific languages that decouple a tree’s logical data structure from its physical representation: a layout language for specifying physical-to-logical mappings, and a build language for expressing the inverse logical-to-physical transformation. • A compilation strategy for destructor specialization that lowers pattern matching onto different physical layouts in accordance with the layout specification. • A complementary compilation strategy for constructor specialization that generates layout-specific constructors from canonical algebraic data types. We implement these ideas in Scion 1 1 1 The

Read the complete text