Surface Edge Explorer (SEE): Planning Next Best Views Directly from 3D Observations

Rowan Border, Jonathan D. Gammell, Paul Newman

Abstract

Surveying 3D scenes is a common task in robotics. Systems can do so autonomously by iteratively obtaining measurements. This process of planning observations to improve the model of a scene is called Next Best View (NBV) planning. NBV planning approaches often use either volumetric (e.g., voxel grids) or surface (e.g., triangulated meshes) representations. Volumetric approaches generalise well between scenes as they do not depend on surface geometry but do not scale to high-resolution models of large scenes. Surface representations can obtain high-resolution models at any scale but often require tuning of unintuitive parameters or multiple survey stages. This paper presents a scene-model-free NBV planning approach with a density representation. The Surface Edge Explorer (SEE) uses the density of current measurements to detect and explore observed surface boundaries. This approach is shown experimentally to provide better surface coverage in lower computation time than the evaluated state-of-the-art volumetric approaches while moving equivalent distances.

Introduction

Building high-resolution 3D models of unknown environments requires a robot to autonomously determine its next sensor pose—a challenge known as Next Best View (NBV) planning. Traditional methods typically rely on volumetric representations, such as voxel grids, which are reliable but scale poorly to large environments due to memory and computational overhead. Alternatively, surface-based approaches offer better scalability but often necessitate complex parameter tuning or multi-stage scanning processes. This paper introduces the Surface Edge Explorer (SEE), a "scene-model-free" NBV planner that leverages point cloud density to identify exploration frontiers, combining the scalability of surface methods with the simplicity of volumetric approaches.

Methodology

The core innovation of SEE is its use of measurement density rather than a fixed spatial grid. The algorithm employs a modified DBSCAN clustering technique to classify points in a 3D scan. Points are categorized as "core" (sufficiently dense neighbors), "outlier" (isolated), or "frontier" (located at the boundary of observed space).

DBSCAN-based classification of points into core, frontier, and outlier categories.

For each frontier point, SEE performs an eigendecomposition (Principal Component Analysis) of its neighborhood to estimate the local surface normal and the direction of the unobserved "gap." To handle self-occlusions and complex geometries, the system uses a Local View Adjustment strategy, iteratively refining the sensor's pose to "peer around" obstacles. Global efficiency is maintained by selecting views that minimize travel distance relative to both the starting and current positions.

Experimental Evaluation

SEE was evaluated in simulation against seven state-of-the-art volumetric NBV metrics, including Average Entropy (AE) and Area Factor. Testing involved standard CAD models (e.g., Stanford Bunny) and a large-scale 40m model of the Radcliffe Camera in Oxford to test scalability.

The results demonstrated that SEE achieves superior surface coverage compared to volumetric methods. On the Radcliffe Camera model, SEE reached 99% coverage, whereas the best volumetric competitor (AE) only achieved 79% within the same number of views.

Comparison of surface coverage between SEE (a) and the Average Entropy (AE) volumetric approach (b) on the Radcliffe Camera model.

Furthermore, SEE's computational complexity scales with the number of measurements rather than the scene's volume, leading to significantly faster planning times in large-scale environments. The performance was found to be logarithmically better than volumetric approaches; as scene complexity increased, SEE's planning time remained low while volumetric methods slowed significantly.

Conclusion

The Surface Edge Explorer provides an efficient, scalable solution for autonomous 3D mapping. By focusing on measurement density and local geometry, it avoids the pitfalls of volumetric scaling while maintaining high coverage. Future work will focus on deploying SEE on physical platforms, such as autonomous aerial vehicles, for real-world infrastructure inspection.

Summary updated

Abstract

Surveying 3D scenes is a common task in robotics. Systems can do so autonomously by iteratively obtaining measurements. This process of planning observations to improve the model of a scene is called Next Best View (NBV) planning. NBV planning approaches often use either volumetric (e.g., voxel grids) or surface (e.g., triangulated meshes) representations. Volumetric approaches generalise well between scenes as they do not depend on surface geometry but do not scale to high-resolution models of large scenes. Surface representations can obtain high-resolution models at any scale but often require tuning of unintuitive parameters or multiple survey stages. This paper presents a scene-model-free NBV planning approach with a density representation. The Surface Edge Explorer (SEE) uses the density of current measurements to detect and explore observed surface boundaries. This approach is shown experimentally to provide better surface coverage in lower computation time than the evaluated state-of-the-art volumetric approaches while moving equivalent distances.
BibTeX
@inproceedings{border2018surface,
  author = {Rowan Border and Jonathan D. Gammell and Paul Newman},
  title = {{Surface Edge Explorer (SEE): Planning Next Best Views Directly from 3D Observations}},
  booktitle = {IEEE International Conference on Robotics and Automation},
  year = {2018},
  url = {https://openreview.net/forum?id=vuxO1l_dYr},
}

Loading related content...

Figure