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

Benxu Tang; Yixi Cai; Fanze Kong; Longji Yin; Fu Zhang

cs.ROApr 14, 2026

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

Authors: Benxu Tang, Yixi Cai, Fanze Kong, Longji Yin, Fu Zhang

Organizations: Mechatronics and Robotic Systems (MaRS) Laboratory, Department of Mechanical Engineering, The University of Hong Kong · Department of Robotics, Perception, and Learning, KTH Royal Institute of Technology

Abstract

Efficient and scalable 3D occupancy mapping is essential for autonomous robot applications in unknown environments. However, traditional occupancy grid representations suffer from two fundamental limitations. First, explicitly storing all voxels in three-dimensional space leads to prohibitive memory consumption. Second, exhaustive ray casting incurs high update latency. A recent representation alleviate memory demands by maintaining only the voxels on the two-dimensional boundary, yet they still rely on full ray casting updates. This work advances the boundary-based framework with a highly efficient update scheme. We introduce a truncated ray casting strategy that restricts voxel traversal to the exterior of the boundary, which dramatically reduces the number of updated voxels. In addition, we propose a direct boundary update mechanism that removes the need for an auxiliary local 3D occupancy grid, further reducing memory usage and simplifying the map update pipeline. We name our framework as D-BDM. Extensive evaluations on public datasets demonstrate that our approach achieves significantly lower update time and reduced memory consumption compared with the baseline methods, as well as the prior boundary-based approach.

Figures & tables

Fig. 1: (a) Illustration of the proposed update scheme. Ray traversal is limited to segments outside the boundary, avoiding full-ray processing. (b) Visualization of the experiment in kitti_00 sequence, showing the boundary voxels (transparent blue) and the traversed voxels (green) of the proposed method. Occupied voxels are highlighted in grey. (c) Comparison with classical full ray casting, demonstrating that the proposed method greatly reduces the number of traversed voxels (i.e., down to 1.98%).

Fig. 2: (a) An uniform occupancy grid with free, unknown, and occupied regions, represented by green, blue, and grey, respectively. (b) The boundary surface layer is highlighted in dark blue, which separates the free regions from the adjacent occupied or unknown regions. The boundary map only represents voxels neighboring the boundary surface layer, which includes boundary interior voxels and boundary exterior voxels. (c) Detailed voxel-level view of (b). The boundary interior voxel having an occupancy state of free. The boundary exterior voxel is further classified as boundary exterior (unknown) voxel and boundary exterior (occupied) voxel, whose occupancy states are unknown and occupied, respectively. (d) Truncated ray casting process, where the ray traversal is only preformed at ray segments that located at the exterior of boundary surface layer. Such segments are highlighted in red. (e) A detailed voxel-level view of the truncated ray casting process of ray no.3. The intersection point of the ray and boundary surface layer is marked by red cross symbol. The boundary voxels that intersected with the ray are also highlighted. (f) Voxels traversed by these exterior ray segments are updated to free state.

Fig. 3: The motivation for applying the slab method after the initial determination by depth-image rasterization. In this example, the ray intersects the circumscribed circles of boundary voxels no.1 and no.2, but does not actually pass through the voxels themselves.

Fig. 4: (a) The boundary map before the update, where voxels with free, unknown and occupied state are colored as green, blue and grey, respectively. (b) Preform the truncated ray casting process, updating the voxels outside the boundary to free state. (c) Illustration of the update space, where voxels occupancy states change. (d) The inflated updated space, which is computed by the updated space by one voxel inflation. Voxels in the inflated updated space may have changes in their boundary voxel status. (e) Compute new boundary voxel status for all voxels in the inflated updated space. Remove outdated boundary voxels from and add new boundary voxels to the boundary map. (f) Illustration of the final updated boundary map.

Sequence	Environment Scale	Traveled	Sensor Type
	(Bounding Box) ( $\displaystyle\mathrm{m}^{3}$ )	Distance ( $\displaystyle\mathrm{m}$ )
KAIST_04	$\displaystyle\mathrm{1,547\times 1,275\times 103}$	6,346	128-lines LiDAR
Town_03	$\displaystyle\mathrm{1,379\times 1,741\times 111}$	8,900	128-lines LiDAR
Roundabout_01	$\displaystyle\mathrm{1,702\times 1,691\times 135}$	9,035	128-lines LiDAR
kitti_00	$\displaystyle\mathrm{653\times 586\times 58}$	3,724	64-lines LiDAR
kitti_02	$\displaystyle\mathrm{1,035\times 688\times 94}$	5,067	64-lines LiDAR

TABLE I: Details of datasets used in the benchmark experiments.

Resolution (m)	0.5	0.3	0.2	0.1	0.5	0.3	0.2	0.1	0.5	0.3	0.2	0.1
	KAIST_04				Town_03				Roundabout_01
Uniform Grid	40.76	63.21	$\displaystyle\times$	$\displaystyle\times$	35.38	55.03	$\displaystyle\times$	$\displaystyle\times$	42.20	$\displaystyle\times$	$\displaystyle\times$	$\displaystyle\times$
OctoMap	318.05	521.19	766.74	1561.84	289.03	492.12	687.59	1399.87	325.85	547.45	813.13	1754.65
D-Map	11.15	17.59	37.47	143.51	11.75	19.40	47.48	211.82	10.84	19.38	31.80	138.65
BoundaryMap	42.28	71.22	113.70	406.04	36.56	60.40	92.11	306.60	44.20	74.93	122.32	382.98
Ours	10.80	17.35	27.78	92.24	10.30	15.74	26.18	76.72	10.85	16.67	26.41	78.10

TABLE II: Comparison of map update time (ms) at different resolutions.

Resolution (m)	0.5	0.3	0.2	0.1	0.5	0.3	0.2	0.1	0.5	0.3	0.2	0.1
	KAIST_04				Town_03				Roundabout_01
Uniform Grid	6199.9	28703.4	$\displaystyle\times$	$\displaystyle\times$	8132.7	37651.5	$\displaystyle\times$	$\displaystyle\times$	11857.3	$\displaystyle\times$	$\displaystyle\times$	$\displaystyle\times$
OctoMap	96.5	549.3	1741.5	12588.1	147.2	712.8	2180.1	15300.6	150.6	869.3	2717.9	19752.5
D-Map	295.8	804.3	2353.2	10610.0	398.4	1329.0	3199.7	14831.7	323.5	979.5	2427.4	10428.9
BoundaryMap	40.5	135.4	316.3	1523.0	64.1	173.0	407.0	1935.5	67.2	180.6	422.8	1997.1
Ours	38.9	127.3	288.2	1290.3	62.5	165.0	379.3	1706.9	65.6	172.6	394.6	1764.2

TABLE III: Comparison of memory consumption (MB) at different resolutions.

Scan No.	1	2	3	5	20
Ours $\displaystyle(N_{p})$	9,668,163	203,297	168,653	135,871	129,369
Classical $\displaystyle(N_{r})$	9,668,163	9,588,663	9,488,954	9,461,390	9,180,961
Ratio $\displaystyle({N_{p}}/{N_{r}})$	100%	2.12%	1.78%	1.43%	1.41%

TABLE IV: Comparison of the traversed voxels of our method and classical ray casting at different scans.

Uniform Grid	OctoMap	D-Map	BoundaryMap	Ours
23.95	106.19	28.88	22.04	15.58

TABLE V: Map update time (ms) on the real-world task

Fig. 5: (a) An illustration of the long-range navigation task in a multi-level building. (b) The Micro Aerial Vehicle (MAV) platform conducting the real-world flight.

Occupancy Grid Mapping

See all 17 papers

Memory-Efficient Boundary Map for Large-Scale Occupancy Grid Mapping
Mar 23, 2026Benxu Tang, Yunfan Ren, Yixi Cai +6Occupancy Grid Mapping Simultaneous Localization and Mapping
Mechatronics and Robotic Systems (MaRS) Laboratory, Department of Mechanical Engineering, The University of Hong Kong, Hong Kong SAR, China. · Department of Robotics, Perception, and Learning, KTH Royal Institute of Technology, Stockholm, Sweden.
SOCC-ICP: Semantics-Assisted Odometry based on Occupancy Grids and ICP
May 14, 2026Johannes Scherer, Sebastian Hirt, Henri MeeßLiDAR Odometry Semantic Occupancy Mapping
Fraunhofer IVI, 85049 Ingolstadt, Germany · Technische Hochschule Ingolstadt, 85049 Ingolstadt, Germany · Ancud IT-Beratung GmbH, 90478 Nürnberg, Germany
IndoorBEV: A Lightweight Real-Time LiDAR BEV Perception System for Indoor Mobile Robots
Sep 30, 2026Haichuan LiRobotic Perception Bird's-Eye-View Representation
University of Turku

Mar 23, 2026J/K move · Enter open · S save

Memory-Efficient Boundary Map for Large-Scale Occupancy Grid Mapping

Benxu Tang, Yunfan Ren, Yixi Cai, Fanze Kong+5

Mechatronics and Robotic Systems (MaRS) Laboratory, Department of Mechanical Engineering, The University of Hong Kong, Hong Kong SAR, China. · Department of Robotics, Perception, and Learning, KTH Royal Institute of Technology, Stockholm, Sweden.

Occupancy Grid Mapping Simultaneous Localization and Mapping

Open paper AskPDF arXiv

Determining the occupancy status of locations in the environment is a fundamental task for safety-critical robotic applications. Traditional occupancy grid mapping methods subdivide the environment into a grid of voxels, each associated with one of three occupancy states: free, occupied, or unknown. These methods explicitly maintain all voxels within the mapped volume and determine the occupancy state of a location by directly querying the corresponding voxel that the location falls within. However, maintaining all grid voxels in high-resolution and large-scale scenarios requires substantial memory resources. In this paper, we introduce a novel representation that only maintains the boundary of the mapped volume. Specifically, we explicitly represent the boundary voxels, such as the occupied voxels and frontier voxels, while free and unknown voxels are automatically represented by volumes within or outside the boundary, respectively. As our representation maintains only a closed surface in two-dimensional (2D) space, instead of the entire volume in three-dimensional (3D) space, it significantly reduces memory consumption. Then, based on this 2D representation, we propose a method to determine the occupancy state of arbitrary locations in the 3D environment. We term this method as boundary map. Besides, we design a novel data structure for maintaining the boundary map, supporting efficient occupancy state queries. Theoretical analyses of the occupancy state query algorithm are also provided. Furthermore, to enable efficient construction and updates of the boundary map from the real-time sensor measurements, we propose a global-local mapping framework and corresponding update algorithms. Finally, we will make our implementation of the boundary map open-source on GitHub to benefit the community:https://github.com/hku-mars/BDM.

Abstract

Occupancy Grid Mapping

Explore similar work

Memory-Efficient Boundary Map for Large-Scale Occupancy Grid Mapping

SOCC-ICP: Semantics-Assisted Odometry based on Occupancy Grids and ICP

IndoorBEV: A Lightweight Real-Time LiDAR BEV Perception System for Indoor Mobile Robots