GPU-native Embedding of Complex Geometries in Adaptive Octree Grids Applied to the Lattice Boltzmann Method

This paper presents a GPU-native algorithm that efficiently embeds complex triangle-mesh geometries into adaptive octree grids for the Lattice Boltzmann Method by utilizing local ray casting and flattened lookup tables to achieve accurate boundary conditions and near-wall refinement entirely on the device, thereby eliminating CPU-GPU synchronization overhead while maintaining computational performance.

The Gist

Imagine you are trying to simulate how wind blows around a complex object, like a dragon or a bunny, using a computer. To do this, the computer needs to break the space around the object into a grid of tiny boxes (like a 3D checkerboard) to calculate the physics.

The Problem:
If the object is a perfect cube, the grid lines fit perfectly against its sides. But real objects (like a dragon) have curves and jagged edges. If you try to fit a square grid against a curved dragon, you get a "staircase" effect. The computer sees the dragon as a blocky, pixelated mess, which makes the physics calculations inaccurate.

Traditionally, to fix this, scientists would use a powerful computer (the CPU) to figure out how to reshape the grid, and then send that data to a super-fast graphics card (the GPU) to do the math. But this "hand-off" is slow and wastes time.

The Solution:
This paper presents a new method where the GPU does everything itself. It's like giving the graphics card its own brain to not only do the math but also to reshape the grid and fit the dragon inside it, all without asking the CPU for help.

Here is how they did it, using some everyday analogies:

1. The "Smart Zoom" (Adaptive Mesh Refinement)

Imagine you are looking at a map of a city. You don't need to see every single brick on every building in the middle of the ocean. You only need high detail near the buildings.

• Old way: The computer tries to make every single square on the map tiny, everywhere. This is a waste of memory.
• New way: The computer uses a "smart zoom." It keeps the grid coarse (big blocks) far away from the object, but as it gets closer to the dragon, it automatically splits the big blocks into smaller and smaller pieces to hug the dragon's curves tightly. This saves massive amounts of computer memory.

2. The "Flashlight" and the "Bin System" (Ray Casting & Spatial Binning)

To figure out if a specific grid box is inside the dragon or outside, the computer has to check if the box touches the dragon's skin (which is made of thousands of tiny triangles).

• The Naive Approach: Imagine you are in a dark room with a flashlight, trying to find a specific person in a crowd of 10,000 people. If you shine your light on everyone one by one, it takes forever.
• The Paper's Approach: They built a "bin system." Imagine the room is divided into small cubbyholes. Before you even turn on the flashlight, you quickly sort the crowd so that you only shine your light into the cubbyholes where the person might be.
  • The computer groups the dragon's triangles into these "bins."
  • When checking a grid box, it only looks at the triangles in the specific bin nearby.
  • This is like checking a specific shelf in a library instead of walking down every single aisle. It makes the process incredibly fast.

3. The "Staircase Fix" (Interpolated Boundary Conditions)

Even with the smart zoom, the grid is still made of squares, so the dragon still looks a little bit like a staircase.

• The Fix: The authors created a "lookup table" (like a cheat sheet). When the computer calculates the wind hitting the dragon, it doesn't just guess where the wall is. It measures the exact distance from the grid line to the actual curve of the dragon.
• The Result: Instead of the wind bouncing off a blocky step, the computer knows exactly where the smooth curve is and calculates the physics as if the wall were perfectly smooth. This makes the simulation much more accurate.

4. The "All-in-One" Factory

The most important part of this paper is that the entire factory is on the GPU.

• Old way: The CPU (the manager) designs the grid, sends it to the GPU (the worker), the worker does the math, and sends it back. The manager and worker spend a lot of time talking on the phone (data transfer), which slows things down.
• New way: The GPU is the manager and the worker. It designs the grid, fits the dragon in, and calculates the wind all in one continuous flow. There is no phone call. This makes the simulation run much faster.

What Did They Prove?

They tested this method on two famous 3D models: the Stanford Bunny (a rabbit made of 112,000 triangles) and the XYZ RGB Dragon (a dragon made of over 7 million triangles).

• They showed that their method could fit these complex shapes into the grid quickly and accurately.
• They simulated wind blowing around a cylinder and a sphere. The results matched known scientific data, proving that their "staircase fix" works well.
• They found that while the process takes a little bit of extra time to set up the grid, the speed gained by doing everything on the GPU and the accuracy of the results make it a huge win.

In short: This paper teaches a computer's graphics card how to build its own custom, high-resolution puzzle pieces to fit around complex 3D shapes, all without needing help from the main processor, resulting in faster and more accurate weather and fluid simulations.

Technical Summary

1. Problem Statement

Computational Fluid Dynamics (CFD) simulations using GPUs face significant challenges when dealing with complex, non-aligned geometries on adaptive meshes.

• The Bottleneck: While Adaptive Mesh Refinement (AMR) reduces computational costs by concentrating resolution where needed, embedding complex geometries (e.g., triangle meshes) into block-structured, axis-aligned grids on GPUs is difficult.
• Current Limitations: Most existing GPU-accelerated CFD solvers rely on hybrid CPU-GPU approaches where the CPU manages the mesh topology and transfers data to the GPU. This creates communication bottlenecks. Furthermore, standard voxelization methods often rely on space-filling curves or hash tables, which are inefficient for data-parallel GPU execution or require complex index ordering.
• The Gap: There is a lack of GPU-native frameworks that can handle complex, stationary geometries within a forest-of-octrees AMR grid entirely on the device, while maintaining the specific requirements of explicit solvers like the Lattice Boltzmann Method (LBM), such as 2:1 grid balancing and accurate boundary condition imposition.

2. Methodology

The authors present a fully GPU-native algorithm implemented in C++/CUDA that embeds stationary triangle-mesh geometries into a block-structured forest-of-octrees grid. The process is divided into several key stages:

A. Spatial Binning and Ray Casting Acceleration

To avoid the memory-bound nature of naive ray casting (where every cell checks every triangle), the authors employ a hierarchical spatial binning strategy:

• Bin Hierarchy: The geometry faces are mapped to a hierarchy of spatial bins (uniform grids) corresponding to the AMR grid levels.
• Face Filtering: Faces that do not intersect the current grid level's domain are filtered out early.
• Acceleration: This reduces the search space for each cell-block, allowing threads to only check a small subset of faces relevant to their local region. This eliminates the need for complex hash tables or space-filling curve traversals.

B. Top-Down Voxelization and Flag Propagation

The embedding process follows a top-down approach, level by level:

1. Partial Surface Voxelization: Cells near the geometry surface are flagged as "solid," "fluid," or "guard" using local ray casts. The algorithm uses a triangle-AABB (Axis-Aligned Bounding Box) overlap test to determine intersections, which is robust against floating-point round-off errors common in high-resolution grids.
2. Internal Propagation: Once surface cells are flagged, a parallel propagation routine fills the interior of the geometry. This is done efficiently within cell-blocks and across neighbors without requiring atomic operations or complex synchronization.
3. Refinement and Balancing: The algorithm enforces a 2:1 balance (adjacent grid elements cannot differ in size by more than a factor of two) required for explicit solvers. It refines blocks near the wall and propagates refinement flags into the fluid and solid regions to ensure sufficient resolution for temporal integration.

C. Link-Length Lookup Table

To handle the "staircase" approximation inherent in voxelization, the method computes the exact distance from the boundary cell center to the geometry surface along specific lattice links.

• A flattened lookup table is constructed storing these "cut-link" distances.
• This enables Interpolated Bounce-Back (IBB) boundary conditions for the LBM, which significantly improves accuracy over simple bounce-back (SBB) methods, especially for curved surfaces.

3. Key Contributions

1. Fully GPU-Native Pipeline: The entire process—from geometry loading and spatial binning to mesh construction, voxelization, and boundary condition setup—occurs on the GPU. No CPU-GPU data transfers occur during the mesh adaptation phase.
2. Efficient Spatial Binning: The introduction of a hierarchical spatial binning system with face filtering drastically reduces the computational cost of voxelization, making it scalable for models with millions of triangles (e.g., the 7.2M triangle XYZ RGB Dragon).
3. Cell-Granular Embedding: Unlike previous GPU-native AMR works limited to axis-aligned boundaries, this method handles arbitrary triangle meshes, supporting complex curvature.
4. Robust Boundary Handling: The construction of a link-length lookup table allows for accurate interpolated boundary conditions in the LBM, bridging the gap between voxelized grids and high-fidelity fluid dynamics.
5. Open-Source Implementation: The approach is implemented as an extension of the AGAL framework, providing a general solution for other explicit solvers requiring GPU-resident geometry embedding.

4. Results and Validation

The authors validated the method using standard benchmarks and complex models:

• Performance Benchmarks:

  • Tested on Stanford Bunny (112K triangles) and XYZ RGB Dragon (7.2M triangles).
  • Compared against the sparse voxel octree method of Schwarz and Seidel (originally for graphics). The proposed method showed comparable execution times (within an order of magnitude) despite the added complexity of AMR balancing and 2:1 constraints.
  • Optimizations: Face filtering and stream compaction reduced execution times significantly (up to 2 orders of magnitude on coarse grids) by minimizing the data processed during binning and voxelization.
  • Hardware: Tests were conducted on GPUs ranging from consumer-grade (GTX 970M) to datacenter-class (A100, H100), demonstrating scalability.

• CFD Validation (LBM):

  • 2D Circular/Square Cylinder ($Re=100$): Simulations showed that the Interpolated Bounce-Back (IBB) method converges faster to literature values for drag ($C_D$) and lift ($C_L$) coefficients than Simple Bounce-Back (SBB).
  • 3D Sphere ($Re \in \{10, 15, 20\}$): Results for drag coefficients matched experimental fits within a 4% error margin.
  • Accuracy: The method successfully captured coherent flow structures (vorticity) and provided stable near-wall resolution on adaptive Cartesian grids.

5. Significance and Future Work

• Significance: This work removes a major barrier to high-fidelity CFD on GPUs by enabling the direct embedding of complex, unstructured geometries into adaptive grids without CPU intervention. It proves that GPU-native AMR can handle the specific metadata and balancing requirements of explicit solvers like LBM.
• Limitations: Currently, the method supports only stationary geometries.
• Future Directions:
  • Extending the framework to moving geometries (requiring dynamic re-binning).
  • Implementing exact floating-point arithmetic to eliminate rare "spikes" caused by ray-cast misses due to round-off errors.
  • Scaling to multi-GPU distributed memory clusters, which will require new load-balancing strategies beyond the current single-GPU approach.
  • Supporting general boundary conditions (e.g., slip, pressure) beyond the current no-slip assumption.

In conclusion, this paper presents a robust, high-performance framework for integrating complex geometries into GPU-accelerated CFD simulations, paving the way for more efficient and accurate simulations of real-world engineering problems.