# Lecture #09. Acceleration structures

Computer graphics in Game development

01.10.2022

## Raytracing complexity

In the case of 1 ray per pixel without additional ray casting the complexity of ray tracing is rays number * (triangles number * MT algorithm cost + Closest Hit cost)



## Complexity reduction strategies

• Traversing bigger chunks of geometry at the same time
• Reducing the cost of the MT algorithm
• Using non-linear data structures

## Model grouping

Obj file was parsed to a vector of shapes. Each shape has its own vertex and index buffers. Let’s use the each shape as a single chunk for traversing. How we can find the shape-ray intersection?

## AABB intersection algorithm

float3 invRaydir = float3(1.0) / ray.direction;
float3 t0 = (aabb_max - ray.position) * invRaydir;
float3 t1 = (aabb_min - ray.position) * invRaydir;
float3 tmin = min(t0, t1);
float3 tmax = max(t0, t1);
return maxelem(tmin) <= minelem(tmax);



## Bounding volume hierarchy

• Top-level acceleration structures (TLAS)
• Bottom-level acceleration structures (BLAS)

## How to build trees of acceleration structures

Surface area heuristic (SAH):

$C(A, B) = t_{trav}+p_{A}\sum_{i=1}^{N_A}t_{int}(a_i) + p_{B}\sum_{i=1}^{N_B}t_{int}(b_i)$

where $C$ - cost of traversing the node, $p_{A}$ and $p_{B}$ are the probabilities that the ray passes through the subvolumes $A$ and $B$ 

## Lab: 2.05 Axis-aligned bounding boxes

1. Implement aabb class
2. Implement build_acceleration_structure method of raytracer class
3. Adjust trace_ray method of raytracer class to traverse the acceleration structure
4. Adjust ray_tracing_renderer class to build the acceleration structure