💻 computer science

PolyMerge: Compressing 3D Gaussian Splats with Polytope Coverings for Provably Safe Resource-Constrained Navigation

The paper proposes PolyMerge, a method that compresses memory-intensive 3D Gaussian Splatting models into lightweight convex polytope representations to enable provably safe, real-time obstacle avoidance and path planning on resource-constrained drones.

Original authors: Jihoon Hong, Chih-Yuan Chiu, Sara Fridovich-Keil, Glen Chou

Published 2026-06-16

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Jihoon Hong, Chih-Yuan Chiu, Sara Fridovich-Keil, Glen Chou

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 fly a tiny, battery-powered drone through a room full of furniture. To fly safely, the drone needs to know exactly where the chairs and tables are.

The Problem: Too Much Detail, Too Little Brainpower
Recently, a new technology called "3D Gaussian Splatting" (3DGS) has emerged. Think of 3DGS as a way to recreate a room using millions of tiny, glowing, fuzzy balloons (ellipsoids). If you look at the room through this method, it looks incredibly realistic and photorealistic.

However, there's a catch: A standard drone is like a tiny ant with a very small brain. It cannot hold a map made of millions of balloons in its memory, nor can it do the math to avoid them in real-time. It's like trying to navigate a city using a map that lists every single brick in every building—it's too heavy and too slow to use while running.

Other methods try to simplify this by turning the balloons into a wireframe mesh (like a digital spiderweb), but these often have holes in them. If the drone thinks a hole is a safe path but it's actually a wall, it crashes. Safety is non-negotiable.

The Solution: PolyMerge (The "Bubble Wrap" Approach)
The authors of this paper propose a new method called PolyMerge. Instead of trying to keep the millions of tiny balloons or the imperfect wireframes, PolyMerge turns the obstacles into convex polytopes.

To understand a "convex polytope," imagine wrapping a piece of furniture in a tight, rigid, transparent box made of flat panels.

The Box: It completely surrounds the object (the chair, the table, the hoop).
The Safety: Because the box is a solid shape with flat sides, the drone's computer can easily calculate if it will hit the box.
The Guarantee: The box is always slightly bigger than the object inside it. This means the drone will never think it can squeeze through a gap that is actually too small. It might take a slightly wider path than necessary, but it will never crash.

How It Works: The "Merging" Game
PolyMerge works in three simple steps:

Scanning: It looks at the millions of 3D balloons and figures out which parts of the room are "occupied." It turns this into a grid of tiny cubes (voxels), like a 3D version of a pixelated image.
Grouping: It groups these cubes together.
Merging: This is the magic part. The algorithm takes two groups of cubes and smushes them together into a single, larger box. It keeps doing this, merging boxes until it has a manageable number of them (say, 10 or 150 boxes) that fit in the drone's memory.

The authors show that you can control this process. If you have a lot of memory, you can use many small boxes (very precise, less conservative). If you have very little memory (like on a tiny drone), you can merge them into fewer, larger boxes. The drone might have to take a slightly wider detour around a chair because the "box" around the chair is a bit bigger than the chair itself, but it guarantees the drone stays safe.

The Results: Flying the Crazyflie
The team tested this on a Crazyflie, which is a very small, lightweight drone with extremely limited computing power.

The Test: They put the drone in a room with hoops and obstacles.
The Outcome: Using PolyMerge, the drone could calculate a safe path and fly through the hoops in real-time.
Comparison: When they tried to use the original "millions of balloons" method, the drone's computer couldn't handle it. When they tried other simplified methods, the drone sometimes crashed because the map wasn't safe enough. PolyMerge was the only one that was both fast enough for the drone and safe enough to prevent crashes.

In Summary
PolyMerge is a tool that takes a super-detailed, heavy 3D map of a room and compresses it into a few simple, safe "boxes." It allows tiny, weak robots to navigate complex environments safely by trading a little bit of path efficiency (taking a slightly wider turn) for a massive gain in safety and speed. It ensures the robot never thinks a wall is a door.

Technical Summary: PolyMerge: Compressing 3D Gaussian Splats with Polytope Coverings for Provably Safe Resource-Constrained Navigation

Problem Statement
Recent advances in radiance field reconstruction, particularly 3D Gaussian Splatting (3DGS), offer high-fidelity scene modeling capable of precisely identifying obstacle geometry. However, these models are computationally and memory-intensive, often containing hundreds of thousands to millions of ellipsoids that exceed the storage and processing capabilities of resource-constrained robotic hardware (e.g., small drones like the Crazyflie). Furthermore, existing methods that compress 3DGS models for visual tasks often fail to provide geometric over-approximations of occupied space, rendering them unsafe for motion planning. While some approaches attempt safe navigation using Control Barrier Functions (CBFs) on 3DGS data, they remain too heavy for on-board deployment. The core challenge is to compress a photorealistic 3DGS scene into a lightweight representation that guarantees obstacle over-approximation while satisfying strict hardware constraints.

Methodology: PolyMerge
The authors propose PolyMerge, a framework that converts a 3DGS model into a set of convex polytopes whose union provably over-approximates all obstacles. The method operates in three primary stages:

Occupancy Voxelization: The 3DGS model (a collection of ellipsoids) is converted into a sparse voxel occupancy grid ( $V^+$ ). The algorithm determines which voxels intersect with any ellipsoid in the scene, effectively discretizing the continuous Gaussian representation into a binary occupancy map.
Local Subcover Construction: To reduce the cardinality of the voxel grid, the algorithm groups neighboring occupied voxels into clusters. It then applies a weighted set cover algorithm to select a minimal sub-collection of these clusters that covers all occupied voxels. The weight function is designed to minimize the volume of unoccupied space included in the convex hull of each cluster, thereby reducing conservativeness.
Iterative Merging: To meet specific hardware budgets (a maximum number of polytopes, $B$ ), the algorithm iteratively merges pairs of convex hulls. It selects pairs whose union results in the minimal increase in unoccupied volume (conservativeness). This process continues until the number of polytopes satisfies the constraint.

The resulting set of convex polytopes is integrated with a CBF-based safety filter. The polytope representation allows for the efficient construction of a barrier function $\psi(p)$ , which is smoothed using soft-min and soft-max functions to ensure differentiability. This barrier function is used to filter nominal control inputs (generated by a Control Lyapunov Function controller), guaranteeing forward invariance of the safe set and collision-free navigation.

Key Contributions

Scene Compression Algorithm: The paper introduces PolyMerge, an algorithm that constructs and merges polytope set covers to compute guaranteed over-approximations of 3D obstacles from 3DGS environments.
Resource-Conservativeness Trade-off: The method demonstrates the ability to modulate the number of geometric primitives (polytopes) to satisfy strict resource constraints. Users can trade off computational cost against the degree of conservativeness in the obstacle over-approximation.
On-Board Deployment: Through simulations and hardware experiments on Crazyflie drones, the authors show that PolyMerge outperforms existing baselines (SaferSplat, SuGaR+CoACD) in generating safe trajectories. Unlike baselines that either cannot run on the hardware or fail to guarantee safety, PolyMerge enables real-time, safe navigation under severe onboard compute constraints.

Experimental Results

Memory Efficiency: In simulation across nine scenes from the mip-NeRF360 dataset, PolyMerge achieved up to a 10 $\times$ reduction in memory footprint compared to storing raw 3DGS ellipsoids. While PolyMerge used more memory than the SuGaR+CoACD baseline (due to more half-planes per polytope), it provided a provable over-approximation of all occupied voxels, whereas SuGaR+CoACD failed to cover all occupied space, compromising safety.
Computation Speed: On an NVIDIA RTX A6000 GPU, polytope-based representations (including PolyMerge) achieved approximately a 100 $\times$ speed-up in average simulation runtime compared to methods using dense ellipsoid clouds.
Navigation Performance: PolyMerge demonstrated higher success rates in reaching goals compared to baselines. The over-approximation provided by the polytopes appeared to regularize the unsafe set, preventing agents from getting trapped in local minima common in complex obstacle geometries.
Hardware Validation: Experiments on a Crazyflie 2.1+ drone confirmed that the method could run on-board. The drone successfully navigated through hoop obstacles using 150 polytopes. When the number of polytopes was reduced to 10 (increasing conservativeness), the drone took detours or failed to navigate, illustrating the trade-off between resource usage and path efficiency.

Significance and Claims
The paper claims that PolyMerge bridges the gap between high-fidelity scene reconstruction and real-time, safe motion planning on resource-constrained platforms. By ensuring that obstacles are provably over-approximated, the method guarantees safety for CBF-based controllers. The authors position this work as a step toward integrating state-of-the-art photorealistic modeling with onboard perception, allowing small robots to navigate complex environments safely without relying on heavy external compute or simplified geometric assumptions. The method is presented as a practical solution that balances hardware limitations with the need for rigorous safety guarantees, though the authors note limitations regarding dynamic scenes and onboard localization, which are identified as areas for future work.

More like this