Ray Tracing Acceleration Structures

Acceleration structures as the name implies are spatial data structures that speed up searching for triangles, distance fields, etc. in a given scene. Ray intersection tests for certain shapes like axis aligned bounding boxes (AABBs) are extremely cheap and easy to implement, so by traversing a hierarchical structure of AABBs, you can determine if a triangle is intersected, and use a triangle-ray intersection test to get the nessesary data such as baricentrics, interpolated attributes such as normals [McGuire 2018] to perform any number of ray traced effects such as accurate shadows, ambient occlusion, global illumination, reflections, or even a full path tracer [Kajiya 1986] [Pharr et al. 2016].

Controls: Hover over the AABB or triangle to do a ray hit test. Drag horizontally to rotate it.

AABB and Triangle Intersection Tests
// ✅ Boolean tests for AABB and Triangle-Ray intersection.
// You may need more information such as baricentric coordinates,
// Ray distance, etc.
//
// Adapted from David Eberly's Geometric Tools
// Copyright (c) 1998-2022 | Boost License, v1.0.
// https://www.geometrictools.com/GTE/Mathematics/IntrRay3AlignedBox3.h
// https://www.geometrictools.com/GTE/Mathematics/IntrRay3Triangle3.h
 
struct AABB
{
    float3 center;
    float3 extent;
};
 
bool intersectAABB(float3 origin, float3 direction, AABB box)
{
    float3 boxCenter = box.center;
    float3 boxExtent = box.extent;
 
    // Transform the ray to the aligned-box coordinate system.
    float3 rayOrigin = origin - boxCenter;
 
    if (any(abs(rayOrigin) > boxExtent && rayOrigin * direction >= 0.0))
    {
        return false;
    }
 
    // Perform AABB-line test
    float3 WxD = cross(direction, rayOrigin);
    float3 absWdU = abs(direction);
    if (any(WxD > float3(dot(boxExtent.yz, absWdU.zy),
                         dot(boxExtent.xz, absWdU.zx),
                         dot(boxExtent.xy, absWdU.yx))))
    {
        return false;
    }
 
    return true;
}
 
 
struct Triangle
{
    float3 v[3];
};
 
bool intersectTriangle(float3 origin, float3 direction, Triangle triangle)
{
    float3 diff = origin - triangle.v[0];
    float3 edge1 = triangle.v[1] - triangle.v[0];
    float3 edge2 = triangle.v[2] - triangle.v[0];
    float3 normal = cross(edge1, edge2);
 
    float DdN = dot(direction, normal);
    float sign = 0.0;
    if (DdN > 0.0)
    {
        sign = 1.0;
    }
    else if (DdN < 0)
    {
        sign = -1.0;
        DdN = -DdN;
    }
    else
    {
        // Ray and triangle are parallel.
        return false;
    }
 
    float DdQxE2 = sign * dot(direction, cross(diff, edge2));
    if (DdQxE2 >= 0.0)
    {
        float DdE1xQ = sign * dot(direction, cross(edge1, diff));
        if (DdE1xQ >= 0.0)
        {
            if (DdQxE2 + DdE1xQ <= DdN)
            {
                // Line intersects triangle, check whether ray does.
                float QdN = -sign * dot(diff, normal);
                if (QdN >= 0.0)
                {
                    // Ray intersects triangle.
                    return true;
                }
            }
        }
    }
 
    return false;
}

A ray intersection test for AABBs or triangles can easily be represented in only a few DirectX Intermediate Language (DXIL) instructions alone, and manufacturers can take that concept even further by converting those instructions to application specific integrated curcuits (ASICs), or even converting other aspects of a ray tracer such as acceleration structure builds [J. Doyle et al. 2012] or traversal [Liktor et al. 2016] [Vaidyanathan et al. 2016] to ASIC hardware.

Hardware accelerated intersection tests is what AMD did with the RDNA2 Architecture. When you executed your DirectX 12 Ray Tracing or Vulkan Ray Tracing shaders:


template<typename payload_t>
void TraceRay(RaytracingAccelerationStructure AccelerationStructure,
              uint RayFlags,
              uint InstanceInclusionMask,
              uint RayContributionToHitGroupIndex,
              uint MultiplierForGeometryContributionToHitGroupIndex,
              uint MissShaderIndex,
              RayDesc Ray,
              inout payload_t Payload);

All those calls to TraceRay become DXIL which eventually lead to this AMDIL instruction:

These instructions receive ray data from the Vector General Purpose Registers (VGPRs) and fetch Bounding Volume Hierarchy (BVH) data from memory. [AMD 2020]

Box BVH nodes perform 4x Ray/Box intersection, sorts the 4 children based on intersection distance and returns the child pointers and hit status.

Triangle nodes perform 1 Ray/Triangle intersection test and returns the intersection point and triangle ID.
; AMDIL for RDNA2
image_bvh_intersect_ray vgpr_d[4], vgpr_a[11], sgpr_r[4]
image_bvh_intersect_ray vgpr_d[4], vgpr_a[8], sgpr_r[4] A16=1
image_bvh64_intersect_ray vgpr_d[4], vgpr_a[12], sgpr_r[4]
image_bvh64_intersect_ray vgpr_d[4], vgpr_a[9], sgpr_r[4] A16=1

Despite the fact that in the application layer this is handled by a given graphics API, it's worth understanding how acceleration structures work, either for CPU based collision tests, or to better futureproof one's understanding of the subject. Let's review acceleration structures, how they can be represented, how they can be built/updated, and how they can be traversed to query for intersections.

Terminology

A Bounding Volume Hierarchy (BVH) is a hierarchical spatial structure of nodes, and can be represented in a variety of ways. You could use axis aligned bounding boxes (AABBs), maintain a tree of 2 leafs per node, a variable number of leafs per node (an example of a wide BVH [Vaidyanathan et al. 2019]), attempt to split the tree into smaller boxes to improve performance [Benthin et al. 2017], refit the bounds of the BVH nodes according to changes to the mesh, reorient the tree to avoid paths with many nodes or to prioritize nodes that are visited often, and much more. There's a vast swath of research in the area of tree based data structures that you can take advantage of as well. [Karras 2020]

Controls: Hover over a triangle in this Cornell Box to do a ray hit test, showing the triangle.

Bounding Boxes can be easily represented with lightweight nodes, for example, this struct can represent a node in as little as 64 bytes (and smaller if you take on compression schemes, use spare bits for cached information like the splitPlane), and you can encode extra data to that payload such as the AABB itself and an address to a triangle, parent, etc. [Meister et al. 2021]

Bounding Volume Hierarchy Node
struct BVHNode
{
    // 📤 Left AABB
    float3 leftMin;
    float3 leftMax;
    // 📥 Right AABB
    float3 rightMin;
    float3 rightMax;
    // *️ Pointers
    uint leftPointer;
    uint rightPointer;
};

Building a BVH can vary depending on your requirements, with the rule generally being a higher quality BVH is slower to build but can be traversed faster. BVH builders have been categorized as top-down, bottom-up and insertion-based. In general real time builders use fast techniques such as bottom up builders [Benthin et al. 2022] do well due to the highly parallel nature of the GPU.

KD Trees vs. BVH Diagram

Contrast a BVH with a KD-Tree, a simpler tree of data which is faster to construct and contains less information per node, but is slower to traverse. [Vinkler et al. 2014]

K-Dimensional Tree Node
struct KDNode
{
    uint parent;
    uint flags;
    uint leftPointer;
    uint rightPointer;
};

Notice that both of these examples include pointers, this could be to the triangle itself, but ideally should be to the triangle index stored in a separate list, that way the triangles can be rearanged in case the BVH needs to change due to animations, transformations, procedural geometry, etc. [Bikker 2022]

The Surface Area Heuristic (SAH) function can be used to estimate the efficiency of a BVH. In recent real time builders such as PLOC, this Heuristic is used to better perform splits when building a BVH.

P(N_c | N)^{SAH} = \frac{SA(N_c)}{SA(N)}

Where $SA$ is the surface area function, and $N$ represents a node. [Pharr et al. 2016]

Thanks to the SAH, we can better estimate the probability that we hit the sub-nodes of a given BVH node through the ratio surface area of their bounding boxes and their parent, which can be useful for optimization passes to the BVH, selecting split planes for building BVHs, optimzing the BVH much more.


// XYZ XYZ XYZ
uint morton = 0b001002003;

Morton codes are a small hash value that can encode a 3D position in 32 bits, so in BVH implementations one can use this to easily index a given location (or morton curve space) in the structure when building the hierarchy. Each bit can represent a location in the hierarchy and groups of bits can be used for locations in XYZ space.

A builder can encode the position of box nodes of a BVH as a morton code normalized by the scale of the scene, and easily store and query for that value when building a BVH. This is done by PLOC.

C++ Library: Libmorton (MIT)

Ray Tracing APIs

DirectX 12 and Vulkan both support hardware accelerated raytracing and the interface for these APIs is the same. Hardware accelerated ray tracing uses a 2-level BVH, one level for the scene and one for individual meshes.

Building acceleration structures with graphics APIs involves allocating scratch buffers for API and vendor specific data, providing the API with Bottom Level Acceleration Structure (BLAS) data in the form of your index and vertex position buffer, and top level acceleration structures (TLAS) built from your scene hierarchy with their transforms, and the instance of the BLAS the node correspond to.

Basic DirectX 12 Ray Tracing Example
// 👋 Declare Handles
ID3D12Device5* device;
ID3D12Resource* vertexBuffer;
ID3D12Resource* indexBuffer;
ID3D12GraphicsCommandList4* commandList;
 
// Declare Outputs
ID3D12Resource* asBuffer;
ID3D12Resource* asScratchBuffer;
ID3D12Resource* instanceDescs;
HRESULT hr;
 
// 🌳 Top Level Acceleration Structure
D3D12_RAYTRACING_GEOMETRY_DESC geomDescs[1];
geomDescs[0].Type = D3D12_RAYTRACING_GEOMETRY_TYPE_TRIANGLES;
geomDescs[0].Triangles.IndexBuffer = indexBuffer->GetGPUVirtualAddress();
geomDescs[0].Triangles.IndexCount =
    static_cast<UINT>(indexBuffer->GetDesc().Width) / sizeof(UINT16);
geomDescs[0].Triangles.IndexFormat = DXGI_FORMAT_R16_UINT;
geomDescs[0].Triangles.Transform3x4 = 0;
geomDescs[0].Triangles.VertexFormat = DXGI_FORMAT_R32G32B32_FLOAT;
geomDescs[0].Triangles.VertexCount =
    static_cast<UINT>(vertexBuffer->GetDesc().Width) / sizeof(Vertex);
geomDescs[0].Triangles.VertexBuffer.StartAddress =
    vertexBuffer->GetGPUVirtualAddress();
geomDescs[0].Triangles.VertexBuffer.StrideInBytes = sizeof(Vertex);
 
// 🧱 Get prebuild info
D3D12_BUILD_RAYTRACING_ACCELERATION_STRUCTURE_INPUTS topLevelInputs[1];
topLevelInputs[0].DescsLayout = D3D12_ELEMENTS_LAYOUT_ARRAY;
topLevelInputs[0].Flags =
    D3D12_RAYTRACING_ACCELERATION_STRUCTURE_BUILD_FLAG_PREFER_FAST_TRACE;
topLevelInputs[0].NumDescs = 1;
topLevelInputs[0].Type = D3D12_RAYTRACING_ACCELERATION_STRUCTURE_TYPE_TOP_LEVEL;
D3D12_RAYTRACING_ACCELERATION_STRUCTURE_PREBUILD_INFO topLevelPrebuildInfo = {};
device->GetRaytracingAccelerationStructurePrebuildInfo(topLevelInputs,
                                                       topLevelPrebuildInfo);
 
D3D12_BUILD_RAYTRACING_ACCELERATION_STRUCTURE_INPUTS bottomLevelInputs[1];
bottomLevelInputs[0] = topLevelInputs[0];
bottomLevelInputs.Type =
    D3D12_RAYTRACING_ACCELERATION_STRUCTURE_TYPE_BOTTOM_LEVEL;
bottomLevelInputs.pGeometryDescs = geomDescs;
D3D12_RAYTRACING_ACCELERATION_STRUCTURE_PREBUILD_INFO bottomLevelPrebuildInfo =
    {};
device->GetRaytracingAccelerationStructurePrebuildInfo(
    &bottomLevelInputs, &bottomLevelPrebuildInfo);
 
// 🍱 Create Scratch Buffer
D3D12_RESOURCE_DESC asResourceDesc;
asResourceDesc.Dimension = D3D12_RESOURCE_DIMENSION_BUFFER;
asResourceDesc.Alignment = 0;
asResourceDesc.Width = max(topLevelPrebuildInfo.ScratchDataSizeInBytes,
                           bottomLevelPrebuildInfo.ScratchDataSizeInBytes);
asResourceDesc.Height = 1;
asResourceDesc.DepthOrArraySize = 1;
asResourceDesc.MipLevels = 1;
asResourceDesc.Format = DXGI_FORMAT_UNKNOWN;
asResourceDesc.SampleDesc.Count = 1;
asResourceDesc.SampleDesc.Quality = 0;
asResourceDesc.Layout = D3D12_TEXTURE_LAYOUT_ROW_MAJOR;
asResourceDesc.Flags = D3D12_RESOURCE_FLAG_ALLOW_UNORDERED_ACCESS;
 
// 🍱 Create AS Scratch Buffer
hr = device->CreateCommittedResource(
    &heapProps, D3D12_HEAP_FLAG_NONE, &asResourceDesc,
    D3D12_RESOURCE_STATE_RAYTRACING_ACCELERATION_STRUCTURE, nullptr,
    IID_PPV_ARGS(&asScratchBuffer));
 
// 🍱 Create TLAS Buffer
asResourceDesc.width = topLevelPrebuildInfo.ResultDataMaxSizeInBytes;
hr = device->CreateCommittedResource(
    &heapProps, D3D12_HEAP_FLAG_NONE, &asResourceDesc,
    D3D12_RESOURCE_STATE_RAYTRACING_ACCELERATION_STRUCTURE, nullptr,
    IID_PPV_ARGS(&tlasBuffer));
 
// 🍱 Create BLAS Buffer
asResourceDesc.width = bottomLevelPrebuildInfo.ResultDataMaxSizeInBytes;
hr = device->CreateCommittedResource(
    &heapProps, D3D12_HEAP_FLAG_NONE, &asResourceDesc,
    D3D12_RESOURCE_STATE_RAYTRACING_ACCELERATION_STRUCTURE, nullptr,
    IID_PPV_ARGS(&blasBuffer));
 
D3D12_RAYTRACING_INSTANCE_DESC instanceDesc = {};
instanceDesc.Transform[0][0] = instanceDesc.Transform[1][1] =
    instanceDesc.Transform[2][2] = 1;
instanceDesc.InstanceMask = 1;
instanceDesc.AccelerationStructure = blasBuffer->GetGPUVirtualAddress();
D3D12_HEAP_PROPERTIES uploadHeapProperties = {};
uploadHeapProperties.Type = D3D12_HEAP_TYPE_UPLOAD;
uploadHeapProperties.CPUPageProperty = D3D12_CPU_PAGE_PROPERTY_UNKNOWN;
uploadHeapProperties.MemoryPoolPreference = D3D12_MEMORY_POOL_UNKNOWN;
uploadHeapProperties.CreationNodeMask = 1;
uploadHeapProperties.VisibleNodeMask = 1;
 
D3D12_RESOURCE_DESC bufferDesc = {};
bufferDesc.Dimension = D3D12_RESOURCE_DIMENSION_BUFFER;
bufferDesc.Alignment = 0;
bufferDesc.Width = sizeof(instanceDesc);
bufferDesc.Height = 1;
bufferDesc.DepthOrArraySize = 1;
bufferDesc.MipLevels = 1;
bufferDesc.Format = DXGI_FORMAT_UNKNOWN;
bufferDesc.SampleDesc.Count = 1;
bufferDesc.SampleDesc.Quality = 0;
bufferDesc.Layout = D3D12_TEXTURE_LAYOUT_ROW_MAJOR;
bufferDesc.Flags = D3D12_RESOURCE_FLAG_NONE;
hr = device->CreateCommittedResource(
    &uploadHeapProperties, D3D12_HEAP_FLAG_NONE, &bufferDesc,
    D3D12_RESOURCE_STATE_GENERIC_READ, nullptr, IID_PPV_ARGS(instanceDescs));
 
void* pMappedData;
(*instanceDescs)->Map(0, nullptr, &pMappedData);
memcpy(pMappedData, &instanceDesc, sizeof(instanceDesc));
(*instanceDescs)->Unmap(0, nullptr);
 
// 🏗️ BLAS build command
D3D12_BUILD_RAYTRACING_ACCELERATION_STRUCTURE_DESC bottomLevelBuildDesc = {};
 
bottomLevelBuildDesc.Inputs = bottomLevelInputs;
bottomLevelBuildDesc.ScratchAccelerationStructureData =
    scratchResource->GetGPUVirtualAddress();
bottomLevelBuildDesc.DestAccelerationStructureData =
    blasBuffer->GetGPUVirtualAddress();
 
// 🏗️ TLAS build command
D3D12_BUILD_RAYTRACING_ACCELERATION_STRUCTURE_DESC topLevelBuildDesc = {};
 
topLevelInputs.InstanceDescs = instanceDescs->GetGPUVirtualAddress();
topLevelBuildDesc.Inputs = topLevelInputs;
topLevelBuildDesc.DestAccelerationStructureData =
    tlasBuffer->GetGPUVirtualAddress();
topLevelBuildDesc.ScratchAccelerationStructureData =
    scratchResource->GetGPUVirtualAddress();
 
// 🏢 Execute build
commandList->BuildRaytracingAccelerationStructure(&bottomLevelBuildDesc, 0,
                                                  nullptr);
 
D3D12_RESOURCE_BARRIER barrier = {};
barrier.Type = D3D12_RESOURCE_BARRIER_TYPE_UAV;
barrier.UAV.pResource = blasBuffer;
commandList->ResourceBarrier(1, &barrier);
commandList->BuildRaytracingAccelerationStructure(&topLevelBuildDesc, 0,
                                                  nullptr);

Traversal occurs by executing a ray tracing pipeline with a given graphics API, and further in ray tracing programmable shader steps when calling the builtin TraceRay function.

Ray Tracing HLSL Shader
// 🌎 Global Resources
RaytracingAccelerationStructure Scene : register(t0, space0);
RWTexture2D<float4> tOutput : register(u0);
cbuffer cb : register(b0)
{
    row_major float4x4 projectionMatrix : packoffset(c0);
    row_major float4x4 viewMatrix : packoffset(c4);
    float3 origin : packoffset(c8);
    float near : packoffset(c9.x);
    float far : packoffset(c9.y);
};
 
[shader("raygeneration")]
void raygen()
{
    float2 screenCoords =
        (float2)DispatchRaysIndex() / (float2)DispatchRaysDimensions();
    float2 ndc = screenCoords * 2.0 - float2(1.0, 1.0);
 
    float near = .1;
    float far = 300.0;
 
    float3 rayDir =
        normalize(mul(mul(viewMatrix, projectionMatrix),
                      float4(ndc * (far - near), far + near, far - near)))
            .xyz;
 
    RayDesc ray;
    ray.Origin = origin.xyz;
    ray.Direction = rayDir;
    ray.TMin = 0.1;
    ray.TMax = 300.0;
    RayPayload payload = {float4(0, 0, 0.5, 0)};
    TraceRay(Scene, RAY_FLAG_NONE, ~0, 0, 1, 0, ray, payload);
 
    // Write the raytraced color to the output texture.
    tOutput[DispatchRaysIndex().xy] = payload.color;
}

More Resources

Tero Karras (NVIDIA) released a 3 part series describing collision detection, tree traversal, and tree construction on the GPU.
Jacco Bikker (@j_bikker) wrote a series of blog posts on BVH construction here.
My Raw DirectX 12 Book - Chapter 4 focuses on ray tracing with DirectX 12 and provides more details on how to execute ray tracing in DirectX 12.
Geometric Tools for Computer Graphics by Philip Schneider and David H. Eberly has a resources page that provides C++ header files for intersection tests for axis aligned bounding boxes as well as other volumes.
There's a video presentation on a Survey on Bounding Volume Hierarchies for Ray Tracing provided by High Performance Graphics.
Computer Graphics at TU Wien gave a lecture on spatial acceleration structures here.
Ray Tracing: The Next Week reviews these concepts as well.

[McGuire 2018]

The Graphics Codex

Morgan McGuire (@CasualEffects)
Casual Effects 2018
graphicscodex.courses.nvidia.com

[Kajiya 1986]

The Rendering Equation
James Kajiya
ACM, SIGGRAPH Computer Graphics 1986
doi.acm.org

[Pharr et al. 2016]

Physically based rendering: From theory to implementation

Matt Pharr,

Wenzel Jakob and Greg Humphreys
Morgan Kaufmann 2016
pbr-book.org

[J. Doyle et al. 2012]

Hardware Accelerated Construction of SAH-Based Bounding Volume Hierarchies for Interactive Ray Tracing
Michael J. Doyle, Colin Fowler and Michael Manzke
ACM 2012
doi.org

[Liktor et al. 2016]

Bandwidth-Efficient BVH Layout for Incremental Hardware Traversal
Gabor Liktor and Karthik Vaidyanathan
Eurographics 2016
intel.com

[Vaidyanathan et al. 2016]

Watertight Ray Traversal with Reduced Precision
Karthik Vaidyanathan,

Tomas Akenine-Möller (@inversepixel) and Marco Salvi (@marcosalvi)
Eurographics 2016
intel.com

[AMD 2020]

RDNA 2 Instruction Set Architecture
AMD 2020
developer.amd.com

[Vaidyanathan et al. 2019]

Wide BVH Traversal with a Short Stack
Karthik Vaidyanathan, Sven Woop and Carsten Benthin
Eurographics 2019
intel.com

[Benthin et al. 2017]

Improved Two-Level BVHs Using Partial Re-Braiding
Carsten Benthin, Sven Woop,

Ingo Wald (@IngoWald) and Attila T. Afra
ACM 2017
sven-woop.de

[Karras 2020]

Thinking parallel, part III: Tree construction on the GPU
Tero Karras
NVIDIA 2020
developer.nvidia.com

[Meister et al. 2021]

A Survey on Bounding Volume Hierarchies for Ray Tracing

Daniel Meister,

Shinji Ogaki (@ShinjiOgaki), Carsten Benthin, Michael J. Doyle (@mjdoyle0), Michael Guthe and Jiří Bittner
Computer Graphics Forum 2021
meistdan.github.io

[Benthin et al. 2022]

PLOC++: Parallel Locally-Ordered Clustering for Bounding Volume Hierarchy Construction Revisited
Carsten Benthin, Radoslaw Drabinski, Lorenzo Tessari and Addis Dittebrandt
ACM 2022
intel.com

[Vinkler et al. 2014]

Bounding Volume Hierarchies versus Kd-Trees on Contemporary Many-Core Architectures
Marek Vinkler, Vlastimil Havran and Jiří Bittner
ACM 2014
doi.org

[Bikker 2022]

How to build a BVH – Part 1: Basics
Jacco Bikker (@j_bikker)
2022
jacco.ompf2.com

	// ✅ Boolean tests for AABB and Triangle-Ray intersection.
	// You may need more information such as baricentric coordinates,
	// Ray distance, etc.
	//
	// Adapted from David Eberly's Geometric Tools
	// Copyright (c) 1998-2022 \| Boost License, v1.0.
	// https://www.geometrictools.com/GTE/Mathematics/IntrRay3AlignedBox3.h
	// https://www.geometrictools.com/GTE/Mathematics/IntrRay3Triangle3.h

	struct AABB
	{
	float3 center;
	float3 extent;
	};

	bool intersectAABB(float3 origin, float3 direction, AABB box)
	{
	float3 boxCenter = box.center;
	float3 boxExtent = box.extent;

	// Transform the ray to the aligned-box coordinate system.
	float3 rayOrigin = origin - boxCenter;

	if (any(abs(rayOrigin) > boxExtent && rayOrigin * direction >= 0.0))
	{
	return false;
	}

	// Perform AABB-line test
	float3 WxD = cross(direction, rayOrigin);
	float3 absWdU = abs(direction);
	if (any(WxD > float3(dot(boxExtent.yz, absWdU.zy),
	dot(boxExtent.xz, absWdU.zx),
	dot(boxExtent.xy, absWdU.yx))))
	{
	return false;
	}

	return true;
	}


	struct Triangle
	{
	float3 v[3];
	};

	bool intersectTriangle(float3 origin, float3 direction, Triangle triangle)
	{
	float3 diff = origin - triangle.v[0];
	float3 edge1 = triangle.v[1] - triangle.v[0];
	float3 edge2 = triangle.v[2] - triangle.v[0];
	float3 normal = cross(edge1, edge2);

	float DdN = dot(direction, normal);
	float sign = 0.0;
	if (DdN > 0.0)
	{
	sign = 1.0;
	}
	else if (DdN < 0)
	{
	sign = -1.0;
	DdN = -DdN;
	}
	else
	{
	// Ray and triangle are parallel.
	return false;
	}

	float DdQxE2 = sign * dot(direction, cross(diff, edge2));
	if (DdQxE2 >= 0.0)
	{
	float DdE1xQ = sign * dot(direction, cross(edge1, diff));
	if (DdE1xQ >= 0.0)
	{
	if (DdQxE2 + DdE1xQ <= DdN)
	{
	// Line intersects triangle, check whether ray does.
	float QdN = -sign * dot(diff, normal);
	if (QdN >= 0.0)
	{
	// Ray intersects triangle.
	return true;
	}
	}
	}
	}

	return false;
	}

	struct BVHNode
	{
	// 📤 Left AABB
	float3 leftMin;
	float3 leftMax;
	// 📥 Right AABB
	float3 rightMin;
	float3 rightMax;
	// *️ Pointers
	uint leftPointer;
	uint rightPointer;
	};

	struct KDNode
	{
	uint parent;
	uint flags;
	uint leftPointer;
	uint rightPointer;
	};

	// 👋 Declare Handles
	ID3D12Device5* device;
	ID3D12Resource* vertexBuffer;
	ID3D12Resource* indexBuffer;
	ID3D12GraphicsCommandList4* commandList;

	// Declare Outputs
	ID3D12Resource* asBuffer;
	ID3D12Resource* asScratchBuffer;
	ID3D12Resource* instanceDescs;
	HRESULT hr;

	// 🌳 Top Level Acceleration Structure
	D3D12_RAYTRACING_GEOMETRY_DESC geomDescs[1];
	geomDescs[0].Type = D3D12_RAYTRACING_GEOMETRY_TYPE_TRIANGLES;
	geomDescs[0].Triangles.IndexBuffer = indexBuffer->GetGPUVirtualAddress();
	geomDescs[0].Triangles.IndexCount =
	static_cast<UINT>(indexBuffer->GetDesc().Width) / sizeof(UINT16);
	geomDescs[0].Triangles.IndexFormat = DXGI_FORMAT_R16_UINT;
	geomDescs[0].Triangles.Transform3x4 = 0;
	geomDescs[0].Triangles.VertexFormat = DXGI_FORMAT_R32G32B32_FLOAT;
	geomDescs[0].Triangles.VertexCount =
	static_cast<UINT>(vertexBuffer->GetDesc().Width) / sizeof(Vertex);
	geomDescs[0].Triangles.VertexBuffer.StartAddress =
	vertexBuffer->GetGPUVirtualAddress();
	geomDescs[0].Triangles.VertexBuffer.StrideInBytes = sizeof(Vertex);

	// 🧱 Get prebuild info
	D3D12_BUILD_RAYTRACING_ACCELERATION_STRUCTURE_INPUTS topLevelInputs[1];
	topLevelInputs[0].DescsLayout = D3D12_ELEMENTS_LAYOUT_ARRAY;
	topLevelInputs[0].Flags =
	D3D12_RAYTRACING_ACCELERATION_STRUCTURE_BUILD_FLAG_PREFER_FAST_TRACE;
	topLevelInputs[0].NumDescs = 1;
	topLevelInputs[0].Type = D3D12_RAYTRACING_ACCELERATION_STRUCTURE_TYPE_TOP_LEVEL;
	D3D12_RAYTRACING_ACCELERATION_STRUCTURE_PREBUILD_INFO topLevelPrebuildInfo = {};
	device->GetRaytracingAccelerationStructurePrebuildInfo(topLevelInputs,
	topLevelPrebuildInfo);

	D3D12_BUILD_RAYTRACING_ACCELERATION_STRUCTURE_INPUTS bottomLevelInputs[1];
	bottomLevelInputs[0] = topLevelInputs[0];
	bottomLevelInputs.Type =
	D3D12_RAYTRACING_ACCELERATION_STRUCTURE_TYPE_BOTTOM_LEVEL;
	bottomLevelInputs.pGeometryDescs = geomDescs;
	D3D12_RAYTRACING_ACCELERATION_STRUCTURE_PREBUILD_INFO bottomLevelPrebuildInfo =
	{};
	device->GetRaytracingAccelerationStructurePrebuildInfo(
	&bottomLevelInputs, &bottomLevelPrebuildInfo);

	// 🍱 Create Scratch Buffer
	D3D12_RESOURCE_DESC asResourceDesc;
	asResourceDesc.Dimension = D3D12_RESOURCE_DIMENSION_BUFFER;
	asResourceDesc.Alignment = 0;
	asResourceDesc.Width = max(topLevelPrebuildInfo.ScratchDataSizeInBytes,
	bottomLevelPrebuildInfo.ScratchDataSizeInBytes);
	asResourceDesc.Height = 1;
	asResourceDesc.DepthOrArraySize = 1;
	asResourceDesc.MipLevels = 1;
	asResourceDesc.Format = DXGI_FORMAT_UNKNOWN;
	asResourceDesc.SampleDesc.Count = 1;
	asResourceDesc.SampleDesc.Quality = 0;
	asResourceDesc.Layout = D3D12_TEXTURE_LAYOUT_ROW_MAJOR;
	asResourceDesc.Flags = D3D12_RESOURCE_FLAG_ALLOW_UNORDERED_ACCESS;

	// 🍱 Create AS Scratch Buffer
	hr = device->CreateCommittedResource(
	&heapProps, D3D12_HEAP_FLAG_NONE, &asResourceDesc,
	D3D12_RESOURCE_STATE_RAYTRACING_ACCELERATION_STRUCTURE, nullptr,
	IID_PPV_ARGS(&asScratchBuffer));

	// 🍱 Create TLAS Buffer
	asResourceDesc.width = topLevelPrebuildInfo.ResultDataMaxSizeInBytes;
	hr = device->CreateCommittedResource(
	&heapProps, D3D12_HEAP_FLAG_NONE, &asResourceDesc,
	D3D12_RESOURCE_STATE_RAYTRACING_ACCELERATION_STRUCTURE, nullptr,
	IID_PPV_ARGS(&tlasBuffer));

	// 🍱 Create BLAS Buffer
	asResourceDesc.width = bottomLevelPrebuildInfo.ResultDataMaxSizeInBytes;
	hr = device->CreateCommittedResource(
	&heapProps, D3D12_HEAP_FLAG_NONE, &asResourceDesc,
	D3D12_RESOURCE_STATE_RAYTRACING_ACCELERATION_STRUCTURE, nullptr,
	IID_PPV_ARGS(&blasBuffer));

	D3D12_RAYTRACING_INSTANCE_DESC instanceDesc = {};
	instanceDesc.Transform[0][0] = instanceDesc.Transform[1][1] =
	instanceDesc.Transform[2][2] = 1;
	instanceDesc.InstanceMask = 1;
	instanceDesc.AccelerationStructure = blasBuffer->GetGPUVirtualAddress();
	D3D12_HEAP_PROPERTIES uploadHeapProperties = {};
	uploadHeapProperties.Type = D3D12_HEAP_TYPE_UPLOAD;
	uploadHeapProperties.CPUPageProperty = D3D12_CPU_PAGE_PROPERTY_UNKNOWN;
	uploadHeapProperties.MemoryPoolPreference = D3D12_MEMORY_POOL_UNKNOWN;
	uploadHeapProperties.CreationNodeMask = 1;
	uploadHeapProperties.VisibleNodeMask = 1;

	D3D12_RESOURCE_DESC bufferDesc = {};
	bufferDesc.Dimension = D3D12_RESOURCE_DIMENSION_BUFFER;
	bufferDesc.Alignment = 0;
	bufferDesc.Width = sizeof(instanceDesc);
	bufferDesc.Height = 1;
	bufferDesc.DepthOrArraySize = 1;
	bufferDesc.MipLevels = 1;
	bufferDesc.Format = DXGI_FORMAT_UNKNOWN;
	bufferDesc.SampleDesc.Count = 1;
	bufferDesc.SampleDesc.Quality = 0;
	bufferDesc.Layout = D3D12_TEXTURE_LAYOUT_ROW_MAJOR;
	bufferDesc.Flags = D3D12_RESOURCE_FLAG_NONE;
	hr = device->CreateCommittedResource(
	&uploadHeapProperties, D3D12_HEAP_FLAG_NONE, &bufferDesc,
	D3D12_RESOURCE_STATE_GENERIC_READ, nullptr, IID_PPV_ARGS(instanceDescs));

	void* pMappedData;
	(*instanceDescs)->Map(0, nullptr, &pMappedData);
	memcpy(pMappedData, &instanceDesc, sizeof(instanceDesc));
	(*instanceDescs)->Unmap(0, nullptr);

	// 🏗️ BLAS build command
	D3D12_BUILD_RAYTRACING_ACCELERATION_STRUCTURE_DESC bottomLevelBuildDesc = {};

	bottomLevelBuildDesc.Inputs = bottomLevelInputs;
	bottomLevelBuildDesc.ScratchAccelerationStructureData =
	scratchResource->GetGPUVirtualAddress();
	bottomLevelBuildDesc.DestAccelerationStructureData =
	blasBuffer->GetGPUVirtualAddress();

	// 🏗️ TLAS build command
	D3D12_BUILD_RAYTRACING_ACCELERATION_STRUCTURE_DESC topLevelBuildDesc = {};

	topLevelInputs.InstanceDescs = instanceDescs->GetGPUVirtualAddress();
	topLevelBuildDesc.Inputs = topLevelInputs;
	topLevelBuildDesc.DestAccelerationStructureData =
	tlasBuffer->GetGPUVirtualAddress();
	topLevelBuildDesc.ScratchAccelerationStructureData =
	scratchResource->GetGPUVirtualAddress();

	// 🏢 Execute build
	commandList->BuildRaytracingAccelerationStructure(&bottomLevelBuildDesc, 0,
	nullptr);

	D3D12_RESOURCE_BARRIER barrier = {};
	barrier.Type = D3D12_RESOURCE_BARRIER_TYPE_UAV;
	barrier.UAV.pResource = blasBuffer;
	commandList->ResourceBarrier(1, &barrier);
	commandList->BuildRaytracingAccelerationStructure(&topLevelBuildDesc, 0,
	nullptr);

	// 🌎 Global Resources
	RaytracingAccelerationStructure Scene : register(t0, space0);
	RWTexture2D<float4> tOutput : register(u0);
	cbuffer cb : register(b0)
	{
	row_major float4x4 projectionMatrix : packoffset(c0);
	row_major float4x4 viewMatrix : packoffset(c4);
	float3 origin : packoffset(c8);
	float near : packoffset(c9.x);
	float far : packoffset(c9.y);
	};

	[shader("raygeneration")]
	void raygen()
	{
	float2 screenCoords =
	(float2)DispatchRaysIndex() / (float2)DispatchRaysDimensions();
	float2 ndc = screenCoords * 2.0 - float2(1.0, 1.0);

	float near = .1;
	float far = 300.0;

	float3 rayDir =
	normalize(mul(mul(viewMatrix, projectionMatrix),
	float4(ndc * (far - near), far + near, far - near)))
	.xyz;

	RayDesc ray;
	ray.Origin = origin.xyz;
	ray.Direction = rayDir;
	ray.TMin = 0.1;
	ray.TMax = 300.0;
	RayPayload payload = {float4(0, 0, 0.5, 0)};
	TraceRay(Scene, RAY_FLAG_NONE, ~0, 0, 1, 0, ray, payload);

	// Write the raytraced color to the output texture.
	tOutput[DispatchRaysIndex().xy] = payload.color;
	}

Ray Tracing Acceleration Structures

Terminology

Ray Tracing APIs

More Resources

GitHub Comments

Terminology

Ray Tracing APIs

More Resources