A drone builds a 3-D map of its surroundings as it flies, and the standard mapping library, OctoMap, stores that map in a tree so deep that updating one small cube of space costs up to 32 memory accesses — and the same cubes are updated over and over because consecutive scans overlap — so OctoCache puts a flat hash table in front of the tree that absorbs more than 95 percent of updates, hands the survivors to the tree in the one order that is provably fastest, and moves the tree work to a second CPU core, making map construction 46 to 88 percent faster and cutting drone mission time by up to 28 percent.
The argument in one glance
-
Problem
The map update sits on the critical path, and it is slow
A drone senses, updates its 3-D map, queries the map to plan a collision-free path, and steers. The query cannot run until the update finishes. OctoMap, the dominant mapping library, stores the map in an octree, and every voxel update walks from the root to a leaf and back, up to 32 memory accesses in a 16-level tree. On an NVIDIA Jetson TX2 the octree update is 86 to 96 percent of OctoMap time and up to 72 percent of the whole navigation loop, so the drone slows down to keep up.
-
What people did
Hardware accelerators, faster ray tracing, or index structures
OMU builds a dedicated accelerator for ray tracing and octree updates. NanoMap, OctoMap-RT and GPU OctoMap speed up ray tracing on GPUs. VoxelCache adds an index for finding voxels faster. Skimap replaces the octree with a tree plus linked lists.
-
Why it fell short
Special hardware is not portable, and none of the software fixes attacks the real bottleneck
An accelerator only helps on the chip that has it. Faster ray tracing barely matters when the octree update dominates; with ray tracing accelerated, the update becomes 99 percent of runtime. VoxelCache still performs a full octree traversal per update, and queries still wait for every update to finish. Skimap trades the octree's memory efficiency away, which edge devices cannot afford.
-
This paper's idea
Cache the voxels, evict them in Morton order, and update the tree on another core
Two profiling facts drive the design. Ray tracing emits each voxel 2.8 to 31 times per scan, and 40 to 80 percent of a scan's voxels appeared in the previous three scans. OctoCache therefore inserts every voxel into a flat hash table of buckets, indexed by the Morton code of its coordinates, that holds the accumulated occupancy value exactly as the tree would. More than 95 percent of updates hit the cache and never touch the tree, and queries are answered from the cache as soon as insertion finishes. When a bucket exceeds a threshold, the oldest entries are evicted, and because buckets are Morton-indexed the evicted stream arrives at the octree in Morton order, which the paper proves is an optimal order for tree locality. Finally the octree update runs on a second thread, overlapped with the next scan's ray tracing. Construction of a 3-D map is 45.6 to 88.0 percent faster, a simulated drone runs up to 3.02 times faster end to end, and mission time falls by up to 28 percent.
Why this problem is worth solving
A quadrotor flying through a factory at a few metres per second sees the world through a depth camera at 50 frames per second. Each frame is a point cloud
A set of 3-D points sampled from obstacle surfaces by a depth camera or LiDAR. occupancy map
A 3-D grid of voxels, each holding the probability that the cube of space it represents contains an obstacle.
The catch is the ordering of work. As the paper’s Figure 3 lays out, the planner queries the map only after the map has absorbed the current scan, because the query must reflect the newest obstacles. If the update takes too long, the planner waits, the drone reacts late, and the safe flight speed, which is computed from how quickly the vehicle can perceive and respond, drops. A slower drone finishes its mission later and spends more battery, since about 95 percent of a UAV’s energy goes to the rotors. Using the MAVBench simulator and a Jetson TX2, the authors measure OctoMap at up to 72 percent of the end-to-end navigation loop. That is the cost the paper attacks.
What people did before, and where it broke
- OctoMap itself. Each scan is ray-traced into a batch of free and occupied voxels, and each voxel is pushed into the octree with a root-to-leaf traversal, an update of the leaf, and a walk back up so every ancestor holds the maximum of its children. Where it broke. Profiling on three public datasets shows the octree update is more than 86 percent of runtime, rising to 93 to 96 percent at 0.1 metre resolution. Two reasons: the same voxel is updated many times, and each update is a long chain of dependent memory accesses. Because query and update share the path from the root, they cannot run in parallel without data races.
- Hardware accelerators such as OMU. Parallel ray tracing and octree updates in custom silicon. Where it broke. It needs that silicon, and robots run on whatever compute they carry.
- GPU ray tracing: NanoMap, OctoMap-RT, GPU OctoMap. Where it broke. Ray tracing is the smaller part. Once it is fast, the octree update is 99 percent of the remaining time.
- VoxelCache. An index structure for locating voxels quickly. Where it broke. Every update still traverses the octree, and queries still wait for the whole batch of updates.
- Skimap and other replacement structures. Where it broke. Much higher memory use, which defeats the reason OctoMap is chosen for edge devices.
- The gap. No software solution both removed the duplicated tree work and let queries proceed before the tree was updated, while keeping OctoMap’s memory footprint and query semantics.
Where OctoCache sits
One mapping cycle, before and after
-
Sensor
A point cloud arrives at 50 Hz.
-
Ray tracing
Casts a ray to each point; every voxel on the ray is free, the last is occupied. Unchanged.
-
OctoCache new
Flat, Morton-indexed hash table that accumulates occupancy per voxel; serves queries immediately; evicts old entries in Morton order.
-
Octree update (thread 2) new
Applies only the evicted voxels to the octree, overlapped with the next cycle's ray tracing and cache work.
-
Path planner
Queries voxel occupancy; hits the cache first and the octree on a miss.
The idea
Where the duplication comes from. Ray tracing shoots a ray from the sensor to each point in the cloud, marking every voxel along it free and the last one occupied. The rays fan out from one origin, so they cross the same near-sensor voxels again and again, and because the point cloud is much denser than the voxel grid, many points land in the same occupied voxel. The paper measures 2.78 to 31.32 times duplication inside one scan. Across scans, a drone keeps scanning as it moves, so consecutive scans cover mostly the same space: on two of three datasets, more than 80 percent of a scan’s voxels appeared in the previous three scans; on the Freiburg campus dataset, 40 percent.
A cache that is a mini octree, not a mirror of recent values. The cache is an array of w buckets, w a power of two. Each bucket is a vector of cells, and each cell holds a voxel’s three coordinates as bytes and one float, the accumulated occupancy value
A voxel's log-odds probability of being occupied, raised by a fixed step for each occupied observation and lowered for each free one, clamped to a minimum and maximum. query consistency
The guarantee that a query returns the same occupancy value, through the same API, as unmodified OctoMap would.
Bounded memory through eviction. A threshold tau caps how many cells a bucket may keep after eviction. During a scan a bucket may grow beyond tau, but the cache never exceeds one scan’s worth of new voxels. After the scan is inserted and queried, every bucket above tau evicts its oldest cells until it is back at tau, and the evicted cells form the batch that goes to the octree. The paper finds tau between 2 and 4 is best, and uses 4 with a cache of 512K buckets, 14 megabytes, for the drone experiments.
Morton order is the fastest order for the tree. The Morton code
A single integer formed by interleaving the bits of a voxel's x, y and z coordinates, so that nearby cubes in space get nearby numbers.
A second thread for the octree. Even with far fewer voxels reaching the tree, the tree update remained on the critical path. The parallel design keeps ray tracing, cache insertion, queries and cache eviction on thread 1 and moves the octree update to thread 2, with a single-producer single-consumer queue between them. One mutex separates octree reads (cache misses on thread 1) from octree writes (thread 2), so there are no races; ray tracing and eviction never touch the tree and run freely alongside it. Enqueue and dequeue cost well under a second even on the largest dataset, against hundreds of seconds of octree work.
Tracing one scan through OctoCache
A drone scan enters the cache, is queried, and is evicted
A small illustrative cache with w = 8 buckets and tau = 2. Occupancy values use OctoMap's log-odds steps; concrete numbers are for illustration and the paper's examples use w = 5, tau = 2 in its Figure 12.
Step 1 of 6
Ray tracing emits a batch
One scan produces about 200,000 voxel observations. Because rays fan out from the sensor and many points share a voxel, only about 15,000 of them are distinct, and most of those were also in the last few scans.
observations: 200,000 | distinct voxels: 15,000 | seen in previous 3 scans: about 80 percent
Why it works
- Duplication makes a cache effective. Because each scan repeats voxels 2.8 to 31 times and consecutive scans overlap by 40 to 80 percent, a cache sized at 3 to 4 times the distinct voxels per scan absorbs more than 93 percent of updates, on one dataset with a cache only 0.23 percent the size of the octree. Therefore the octree sees an order of magnitude fewer updates.
- A flat table beats a deep tree per access. A cache insertion is one hash and a short bucket scan; an octree update is up to 32 dependent memory accesses. So even the misses that do reach the tree are outnumbered by cheap hits, and cache insertion runs 2.6 to 5.9 times faster than octree update.
- Accumulating in the cache preserves semantics. Because a cell holds the same accumulated log-odds the leaf would hold, and misses seed the cell from the tree, a query gets the same answer from either place. The API does not change.
- Morton order turns eviction into a locality optimization. The proof shows Morton order minimizes the summed tree distance between consecutive updates, and the measurement shows 1.34 to 1.38 times faster insertion than OctoMap’s order. Indexing buckets by Morton code gets this ordering without a sort.
- The second thread removes the tree from the critical path. Queries need only the cache. Because octree writes never overlap octree reads, the update can run concurrently with the next scan’s ray tracing and eviction, hiding it entirely when its time is below the sum of the other two.
What it costs
- One extra CPU core and up to tens of megabytes. The drone experiments use a 14 megabyte cache; the Freiburg campus dataset at 0.1 metre resolution uses 28 megabytes against a 2.5 gigabyte octree. The Jetson TX2 has 6 cores and 8 gigabytes, so both fit, but they are not zero.
- Thread 1 can still wait for thread 2. Cache insertion of the next scan must wait until the previous octree update has finished, to avoid races. If the octree update is longer than ray tracing plus eviction, thread 1 idles. The paper bounds the parallel gain by the smaller of those two times and shows a best case above 30 percent; a larger cache shrinks the gap by sending fewer voxels to the tree.
- Cache shape must be tuned. Too small a tau forces early evictions and hash-collision misses; too large a tau makes every insertion scan more cells. The paper settles on tau = 4 with w near the number of distinct voxels per scan.
- Gains depend on resolution and range. At coarse resolution and short range the octree is shallow and small, and OctoCache is close to break-even: 1.02 times at 2 metre range and 0.15 metre resolution, and 0.85 times, a slowdown, at 3 metre range and 0.1 metre resolution in one drone setting. The wins are at fine resolution and long range, where the tree is deep.
- Compute is not always the bottleneck. On the lightweight DJI Spark in the Openland and Factory scenarios, mission time did not improve, because rotor power, not perception latency, limited flight speed.
The evaluation
All experiments run on an NVIDIA Jetson TX2 at 15 watts. Drone navigation uses MAVBench, a closed-loop simulator in Unreal Engine on a laptop, with the full perception, planning and control stack on the TX2, two UAV models (AscTec Pelican, 1.9 kilograms; DJI Spark, 350 grams), and four environments: Openland, Farm, Room and Factory. Map construction uses three public OctoMap datasets, FR-079 corridor, Freiburg campus and New College, at nine resolutions from 0.1 to 0.9 metres. Each system is also paired with OctoMap-RT’s duplicate-removing ray tracer, reimplemented on the TX2 CPU, to show the gains survive a better front end.
OctoMap versus OctoCache on the Jetson TX2
| Property | OctoMap | OctoCache |
|---|---|---|
| End-to-end navigation runtime, AscTec, four scenarios | 1.0 | |
| Mission completion time, AscTec | Baseline | |
| High resolution, long range (3 m, 0.1 m) | 1.0 | |
| 3-D map construction, three datasets, nine resolutions | 1.0 | |
| Cache insertion versus octree update | 1.0 | |
| Cache hit rate | — | |
| Inter-thread queue overhead, largest dataset | — |
Check yourself
Check your understanding
1. Why is updating one voxel in OctoMap so expensive?
2. What guarantees that a query answered from the cache matches what OctoMap would return?
3. Predict what happens if the cache used an ordinary hash of the coordinates as the bucket index instead of the Morton code.
4. Why did the DJI Spark show no mission-time improvement in the Openland and Factory scenarios?
5. The parallel design puts the octree update on a second thread. What limits the extra speedup it can deliver?
Sources
The paper is “OctoCache: Caching Voxels for Accelerating 3D Occupancy Mapping in Autonomous Systems” by Peiqing Chen, Minghao Li, Zishen Wan, Yu-Shun Hsiao, Minlan Yu, Vijay Janapa Reddi and Zaoxing Liu, University of Maryland, Harvard and Georgia Tech, published at ASPLOS 2025, Volume 2, DOI 10.1145/3676641.3716263. It is gold open access under a Creative Commons Attribution licence; this explainer was written from the full text of the copy in the NSF Public Access Repository. The code is open source at github.com/KaiserV2/OctoCache.