Another View on the Classic Ray-AABB Intersection Algorithm for BVH Traversal

Motivation

Most common algorithm

  • Hardware (CPU/GPU, Which architecture?)
  • Context (Where is this algorithm called? How many times? What outcoming values do we expect? (e.g. a boolean, parametric min and max values, hit normal?)
  • Performance, Precomputation
  • Ease of understanding and implementation

My story — and an idea

Applying my ideas to the classic Ray-AABB algorithm

  1. Use intrinsic GPU functions where possible: They are likely to be optimized and provide a faster solution than a manual implementation (I hope!).
  2. Prepare for the worst-case: Assume that our algorithm does not get an early out.
  3. Take advantage of vectorization where possible.
Andrew Kensler’s ray-AABB slab variant from Peter Shirley’s blog in HLSL. (the only differences beeing some minor naming changes and putting an AABB struct into the function arguments. That way, we can call it with varying AABBs)
First improvement with some vectorized computations and usage of rcp / min / max
Final ray-AABB intersection improvement prepared for the worst-case and using GPU and vector intrinsics

Results

Performance comparison: The Kensler algorithm from which we started vs. the final transformed algorithm
Heatmap example renderings of four scenes

What now?

Listing 1 from Majercik et al.

References (in order of appearance)

--

--

--

Passionate and mindful Software Engineer, explorer, and Broman

Love podcasts or audiobooks? Learn on the go with our new app.

Recommended from Medium

Machine Learning Cheet Sheets

What I Learned from SICP — Part I

OmniPass comming to metaverse

Do developers of various programming community express natural language knowledge differently?

Serverless Laravel Made Easy with Bref

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Roman Wiche

Roman Wiche

Passionate and mindful Software Engineer, explorer, and Broman

More from Medium

Offline Color Picker: Pick Color from Images

2022 NYX Game Awards: Interview With David Guo, CEO of Top Games Inc.

A Simple Approach to- Kruskal’s Algorithm

Random Framework for Dealing with Sadness