💻 computer science

Geometrically Approximated Modeling for Emitter-Centric Ray-Triangle Filtering in Arbitrarily Dynamic LiDAR Simulation

This paper introduces the Geometrically Approximated Modeling (GRCA) algorithm, which inverts traditional ray-tracing by determining which rays can hit each triangle based on emitter-centric geometric approximations, thereby achieving significantly faster real-time LiDAR simulation in highly dynamic scenes without the need for costly acceleration structure rebuilds.

Original authors: Rabin Gajmer, Joonas Haapala, Zoltan Beck

Published 2026-07-21

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Rabin Gajmer, Joonas Haapala, Zoltan Beck

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to find the perfect spot to take a selfie in a crowded, chaotic park where people are running, jumping, and spinning around. Now, imagine you have a camera that doesn't just take one photo, but fires millions of invisible laser beams in every single direction at once, trying to hit every single person, tree, and bench to measure exactly how far away they are. This is what a LiDAR sensor does. It's the "eyes" of many self-driving cars and robots, painting a 3D picture of the world by shooting light and waiting for it to bounce back.

The tricky part is that the world is always moving. In computer simulations, where engineers test these cars before they hit the road, the objects in the scene—cars, pedestrians, buildings—can change shape or position every single frame of the animation. To figure out which laser beam hits which object, computers usually use a clever filing system called a "Bounding Volume Hierarchy" (BVH). Think of this like a giant, nested set of Russian nesting dolls. The computer checks the biggest doll first; if the laser misses the big doll, it knows it missed everything inside. If it hits the big doll, it opens it up to check the smaller ones inside. But here's the catch: if the people in the park start dancing and changing their positions, the computer has to completely rebuild this entire set of nesting dolls from scratch for every single frame. It's like having to re-sort a library of a million books every time a single book moves a few inches. This takes a massive amount of time and computing power, making real-time simulation of fast-moving scenes incredibly difficult.

This is where a new approach called the Gajmer Ray-Casting Algorithm (GRCA) comes in, offering a clever twist on the problem. Instead of asking, "Which object does this laser beam hit?" (which forces the computer to check every beam against every object), GRCA flips the question around: "Which laser beams could possibly hit this specific object?"

Imagine you are a security guard standing in the center of a room, and instead of checking every single person to see if they are holding a weapon, you look at the weapon first. You ask, "If this person is holding a knife, which guards in the room could possibly see it?" You realize that only the guards standing in a specific arc in front of the person could see the knife. You instantly ignore all the guards behind the person or to the far sides. GRCA does exactly this for lasers and triangles (the tiny flat shapes that make up 3D objects).

The authors, working with Toyota, realized that a spinning LiDAR sensor doesn't shoot random beams; it shoots them in neat, predictable patterns. A single row of lasers spinning around creates a cone shape, and a row at the horizon creates a flat plane. GRCA uses this geometry to draw a "cone" or "plane" around every single triangle in the scene. It then asks, "Does this triangle's cone overlap with any of the sensor's laser channels?" If the answer is no, the computer throws that triangle away immediately without doing any heavy math. If the answer is yes, it only checks the specific lasers that pass through that cone.

To make this even faster, the algorithm sorts triangles into two groups based on how big they look from the sensor's point of view. Small, distant triangles (which look tiny) get a quick, rough check. Large, close-up triangles get a more precise check. This two-step process means the computer spends almost no time on the millions of tiny, far-away objects that don't matter much, and focuses its power on the big, important ones.

The results of this method are impressive. In tests involving complex scenes with millions of moving triangles and up to eight different LiDAR sensors firing over 4 million rays per frame, GRCA was significantly faster than the current industry standards. On a standard computer processor, it was up to 14.55 times faster than the leading software library (Embree). On a graphics card (GPU), it was up to 7.97 times faster than the top hardware-accelerated tool (OptiX). Even in the most chaotic scenarios, where objects are deforming and moving wildly, GRCA maintained its speed because it didn't have to rebuild its "filing system" every time something moved.

The paper also shows that this method can be mixed with the old way: using GRCA for the moving parts of the scene and the traditional method for the static parts. This "hybrid" approach was even faster, reaching up to 19.2 times the speed of the standard CPU method in the most complex tests.

Ultimately, this research suggests that by changing the way we ask the question—from "what does the ray hit?" to "what rays can hit this?"—we can simulate dynamic, real-world environments much more efficiently. This could mean faster, more realistic testing for self-driving cars and robots, allowing engineers to simulate millions of miles of driving in a fraction of the time it currently takes, all without needing to rebuild the world's filing system every single second.

Technical Summary: Geometrically Approximated Modeling for Emitter-Centric Ray-Triangle Filtering in Arbitrarily Dynamic LiDAR Simulation

1. Problem Statement

Real-time Light Detection And Ranging (LiDAR) simulation requires identifying the closest intersecting triangle for every emitted ray within dynamic scenes containing large numbers of moving and deformable objects. The computational cost of a brute-force approach scales linearly with the product of the number of rays and the total triangle count ( $\Omega \times \gamma \times \chi \times \tau$ ), resulting in approximately $5.2 \times 10^{12}$ intersection tests per frame for a representative scene.

Current state-of-the-art solutions rely on Bounding Volume Hierarchies (BVH) and hardware-accelerated ray tracing (e.g., OptiX, Embree). However, these methods face three structural shortcomings in dynamic LiDAR simulation:

Dynamic Scenes: BVHs require a full per-frame rebuild for scenes with significant motion or deformation, a cost proportional to the total triangle count regardless of how little geometry actually moved.
360° LiDARs: Spinning LiDARs emit rays in all directions simultaneously, eliminating ray coherence. This prevents the amortization of node-test costs that BVH traversal relies on.
No Upfront Triangle Filtering: Standard BVH APIs condition all culling on an active ray. Triangles that are out-of-range or back-facing but share a bounding volume with contributing geometry are still tested per ray. In dynamic scenes, loose bounding volumes further degrade performance by enclosing non-contributing geometry.

2. Methodology: The Gajmer Ray-Casting Algorithm (GRCA)

GRCA inverts the traditional ray-casting paradigm. Instead of asking "what does each ray hit?", it asks "which rays can each triangle possibly hit?". This approach eliminates the need for acceleration structures and per-frame scene rebuilding.

2.1 Geometric Modeling (GACP)

The algorithm models spinning LiDAR emitters as Geometrically Approximated Cones or Planes (GACP).

Observation: All rays within a single vertical channel of a spinning LiDAR collectively trace a conic surface around the spin axis (or a horizontal plane at zero elevation).
Implementation: Rather than widening individual rays into volumetric primitives (as in beam tracing), GRCA keeps rays as directed half-lines but tests the GACP surface against triangles. This reduces the problem of finding intersecting rays for a channel to a single GACP-Triangle (GACP-T) surface test.

2.2 Emitter-Centric Filtering and Classification

GRCA utilizes the apparent-area law to classify triangles based on their footprint as seen from the ray origin ( $A_{origin} \propto A_T \cos \phi_{view} / \delta^2$ ).

SAT (Smaller-Appearing Triangles): Triangles with a small apparent area relative to the sensor's angular resolution. These are numerous but contribute fewer hits.
BAT (Bigger-Appearing Triangles): Triangles with a large apparent area. These are fewer in number but dominate the scan output and require precise treatment.

2.3 The Two-Pass Pipeline

The algorithm processes geometry in two passes to balance speed and precision:

Early Pass (Conservative):
- Applies fast origin-centric filters (back-face, range, apparent area).
- Predicts the channel span ( $C_{span}$ ) and ray span ( $R_{span}$ ) for each triangle using inexpensive approximate checks (binary search on GACP-T boolean predicates and vertex projections).
- SAT Handling: Triangles classified as SAT are processed inline with the predicted spans.
- BAT Handling: Triangles classified as BAT are deferred to a second pass.
Late Pass (Precise):
- Processes the deferred BAT list.
- Computes exact GACP-T intersections per channel to determine precise ray span endpoints.
- Resolves azimuthal seam ambiguities (CW vs. CCW arcs) using plane-intersection tests.
- Executes final ray-triangle intersection checks (Möller–Trumbore) only for the predicted spans.

3. Key Contributions

Paradigm Inversion: A novel ray-casting algorithm that scales with scene geometry ( $O(\tau)$ ) rather than ray count, inverting the standard query direction.
Emitter-Centric Model: A closed-form GACP surface approximation that generates per-triangle integer index spans $[C_{from}, C_{to}] \times [R_{from}, R_{to}]$ without scene partitioning.
Two-Pass Pipeline: A design driven by apparent-area classification (SAT/BAT) that achieves GPU-side $O(\tau)$ rejection without CPU round-trips.
Implementations and Benchmarks:
- GRCAGPU (CUDA): Outperforms hardware-accelerated OptiX by up to 7.97×.
- GRCACPU (AVX2/SSE4.1, single-threaded): Outperforms Embree by up to 14.55×.
- Evaluated across 216 unique configurations, six scenes, and five hardware platforms.
Hybrid Pipeline: A demonstration combining GRCA for dynamic geometry with a static BVH for static geometry, achieving up to 19.2× speedup over Embree and 10.5× over OptiX in complex dynamic scenes.

4. Results and Performance

Benchmarks were conducted on scenes ranging from ~1.8M to ~22M triangles, with up to 30 dynamic objects and 8 simultaneous 128×4096-ray LiDARs (approx. 4.2M rays/frame).

Dynamic Scenes: In scenes with scene-wide deformation (SWD), GRCA maintains consistent performance, whereas BVH-based methods (Embree/OptiX) suffer from rebuild costs that scale with displacement. For example, under SWD, Embree degraded ~7× while GRCACPU remained unaffected (<1% variance).
Range Culling: When realistic deployment ranges (10–100 m) are applied, GRCA achieves up to 9.33× speedup over Embree and 7.02× over OptiX.
Accuracy: The algorithm maintains a hit-match rate of ≥98% against OptiX in the vast majority of configurations. Misses (below 98%) are primarily attributed to:
1. Apparent-area discards (triangles smaller than sensor resolution).
2. Binary search initialization errors for oblique triangles.
3. Rounding errors in early-exit predicates.
4. Ambiguities in CW/CCW arc selection for seam-straddling triangles.
Scalability: GRCA's performance is largely independent of the number of ray origins ( $\Omega$ ) for the CPU backend, while the GPU backend scales linearly but remains significantly faster than baselines even at 8 sensors.

5. Significance and Limitations

The paper claims that GRCA eliminates the dominant cost of dynamic LiDAR simulation—BVH construction and traversal—by replacing it with a compute-based, geometry-driven filtering approach. It is particularly significant for high-resolution, multi-sensor, and highly dynamic simulations where traditional acceleration structures fail to amortize costs.

Limitations acknowledged by the authors:

Static Scenes: GRCA offers no advantage over BVH for purely static geometry where rebuild costs are absent.
Noise Constraints: The algorithm supports distance and azimuth noise but does not support per-ray vertical noise (independent elevation offsets per ray within a channel), as the GACP-T predicate evaluates at a single nominal elevation per channel.
Accuracy: While generally high, accuracy can dip below 98% in specific edge cases involving compact scenes with fine tessellation and extreme deformation, though these are attributed to sensor-geometry mismatches rather than algorithmic defects.

The authors conclude that GRCA reduces the brute-force intersection bound by three to seven orders of magnitude in practical dynamic scenarios, offering a vendor-agnostic solution for real-time LiDAR simulation.