D-BDM: A Direct and Efficient Boundary-Based Occupancy Grid Mapping Framework for LiDARs

D-BDM: Direct and Efficient Boundary-Based Occupancy Grid Mapping for LiDARs

Introduction

Three-dimensional occupancy grid mapping is a cornerstone technology for autonomous robotic navigation in unknown and unstructured environments. The main challenge with traditional occupancy grid mapping lies in the trade-off between accuracy, scalability, computational efficiency, and memory consumption—challenges that are intensified for high-resolution, real-time LiDAR-based robotic tasks in large-scale domains.

"D-BDM: A Direct and Efficient Boundary-Based Occupancy Grid Mapping Framework for LiDARs" (2604.12436) provides a significant advance by introducing a novel method—D-BDM—that combines boundary map representations with a truncated ray casting update mechanism. This achieves substantial reductions in both computational cost and memory usage compared to prior approaches while maintaining high accuracy and real-time performance.

Boundary-based Occupancy Representation

The fundamental innovation in D-BDM is the extension and refinement of the boundary map paradigm. Instead of maintaining the full set of 3D volumetric voxels (free, occupied, unknown), the approach encodes the occupancy state by directly maintaining a thin 2D layer of boundary voxels (the boundary surface) in 3-space. The state of any query location is resolved by its relation to this boundary surface.

Figure 1: Boundary voxel definitions and truncated ray casting process, highlighting the separation of free and non-free space and efficient update regions.

The method distinguishes between three classes of boundary voxels:

• Boundary interior voxels (free voxels neighboring non-free states),
• Boundary exterior (unknown) voxels, and
• Boundary exterior (occupied) voxels. By storing only this set and updating discrete occupancy states rather than probabilities, the framework achieves high fidelity mapping with markedly lower memory consumption. This discrete-state update (instead of a full Bayesian/probabilistic update) is enabled by LiDAR's high measurement accuracy and the need for dynamic environment support.

Truncated Ray Casting for Efficient Updates

A critical bottleneck in prior grid-based and boundary-based methods is the cost of exhaustive ray casting: each LiDAR measurement necessitates traversing and updating all voxels along a sensor-to-return ray, resulting in $\mathcal{O}(pR/d)$ complexity per scan ($p$ points, range $R$, resolution $d$).

D-BDM introduces a truncated ray casting algorithm, whereby rays are only processed for those segments that are outside the boundary surface, i.e., in the unexplored/unknown region. This leads to a dramatic reduction in the number of voxel updates per scan, especially after the initial mapping phase.

Figure 2: Visualization of truncated ray casting, showing limited segments traversed (green) compared to full classical ray casting and resulting voxel update reduction to approximately 2% of the original.

The implementation involves projecting boundary voxels via depth-image rasterization (matching LiDAR angular resolution), determining ray-voxel intersection candidates, and then refining intersections using the slab algorithm for correct boundary crossings. Only voxels along segments between boundary crossings are traversed and updated, as illustrated in Figure 1(d-e), leading to a lower amortized cost after the initial scans.

Figure 3: Necessity of geometric refinement—depth-image rasterization overestimates candidate intersections, which are precisely culled via the slab method.

Direct and Incremental Boundary Update Scheme

To further reduce memory and speed up updates, D-BDM eliminates the legacy local 3D occupancy subgrid required by previous boundary map schemes. It utilizes a hash-based, dynamically updated 2D grid for storing boundary voxel pointers (projected along a major axis), allowing efficient incremental extraction, removal, and update of boundary voxels in the sensor field of view.

The update cycle involves identifying the "inflated update space" (all modified voxels and their neighbors), removing outdated boundary voxels, and recomputing the boundary status for just the affected subset. This data structure and incremental update approach decouples update cost from the size of the full environment or map, scaling only with the size of the local FoV and LiDAR return set.

Figure 4: Sequence of the direct boundary update scheme—before update, truncated casting and modification, update region inflation, boundary status computation, and post-update boundary map.

Empirical Results and Claims

The proposed framework is empirically validated on a suite of challenging public datasets, including KAIST_04, Town_03, Roundabout_01 (from HeLiPR), standard urban sequences (KITTI), and a handheld pedestrian sequence (Newer College). Across these domains, D-BDM is compared to strong baselines: Uniform Grid, OctoMap, D-Map, and the original BoundaryMap.

Key quantitative results:

• Update time: D-BDM achieves speedups of 2.8x over D-Map, 4.0x over BoundaryMap, and 18.2x over OctoMap at high-resolution (0.1m) mapping in large dynamic sequences, even when the Uniform Grid method exceeds memory capacity.
• Memory consumption: At 0.1m resolution, D-BDM achieves memory reductions of 89.7% and 87.8% compared to OctoMap and D-Map, and up to 38.6% compared to BoundaryMap.
• Voxel traversals: D-BDM traverses as little as $1.4\%$ the number of voxels required by classical full ray casting after initial scans, with this fraction quickly stabilizing after map boundary formation.

  Figure 5: D-BDM deployed in a real-world long-range indoor navigation task on a MAV, confirming real-time performance.

Live real-world experiments with a MAV navigating a multi-level building confirm that D-BDM enables stable, high-frequency mapping and perception pipeline operation under severe memory and latency constraints, outperforming all baselines in update time.

Practical and Theoretical Implications

The proposed framework directly advances the state-of-the-art for resource-constrained, large-scale, high-resolution LiDAR occupancy mapping. By leveraging boundary-encoded environment geometry and efficient local updates, it enables truly real-time execution on platforms with severe computational and memory limitations. The discrete-state, non-probabilistic update policy is robust to typical LiDAR sensor noise and provides native dynamic environment support, in contrast to D-Map and many probabilistic grid schemes.

Theoretically, this approach represents a further step towards sublinear-in-volume occupancy mapping by restricting both storage and computation to the true anti-aliasing boundary of observed free/occupied regions, suggesting future development of hybrid continuous-discrete environmental encodings for future neurosymbolic or learning-based planners.

Practically, the technique is ready to be deployed on embedded hardware for aerial, ground, or handheld mapping platforms, with immediate application to search-and-rescue, infrastructure inspection, or real-time SLAM and planning stacks for quadrotors and autonomous vehicles.

Conclusion

D-BDM redefines the efficiency envelope of boundary-based occupancy grid mapping under high-dynamic, large-scale, and high-resolution robotic perception demands. By introducing truncated ray casting and eliminating in-memory volumetric local grids, the method achieves significant reductions in computation and memory while supporting robust, dynamic mapping. Empirical validation substantiates its efficacy over rigorous baselines. Future work might integrate probabilistic semantic or learning-based layers atop the boundary skeleton, or explore further compression and acceleration, pushing towards even broader applicability in long-term autonomy contexts.