Benchmarking 3D Coverage Path Planning (CPP)

A unified, modular, and extensible benchmarking platform for 3D Surface Coverage Path Planning (CPP) algorithms.

Please Note: The authors are still actively improving this evaluation platform, and the codebase may be subject to significant changes.

⚠️ EXPERIMENTAL FEATURE: The Three-Space Formulation (T-space/S-space/R-space mappings, robot model integration, and kinematic planning features) is currently experimental, not sufficiently tested, and not ready for production use. APIs in the three_space/ directory may change significantly without backward compatibility guarantees. Use these features at your own risk and report any issues you encounter.

Background

In robotics, particularly for tasks like cleaning, painting, and inspection on 3D surfaces, Coverage Path Planning (CPP) is critical. However, the lack of a unified evaluation standard makes it difficult to fairly compare the performance of different algorithms. This platform aims to address this challenge by providing a standardized environment to evaluate and compare various 3D CPP algorithms.

Features

Stable Features (Ready for Use)

• 🌐 Diverse target surfaces — Import STL, PCD and other common 3D model formats as coverage targets.
• 🧩 Modular algorithm framework — A small, well-documented API makes it easy to plug in and compare different CPP algorithms.
• 🤖 Configurable effector models — Swap sensing/coverage models (circular tool, line-lidar, etc.).
  • Parallel tool (polygonal footprint): support for a polygonal XY footprint with a depth limit; a surface point is covered when its XY projection lies inside the footprint, the depth is within the tool range, and the point is not occluded by the mesh.
  • CPU/GPU parity: the parallel tool and other checks run on the GPU when CUDA is available; otherwise the evaluator falls back to the CPU implementation.
• ⚙️ Standardized pre-processing & remeshing — Hooks for preprocessing; optional CGAL-based isotropic remeshing is available via alg_tools::isotropicRemeshCGAL (built only if CGAL remeshing headers are present; otherwise a safe stub is compiled). The remesher is exposed through the server/client API so callers can request remeshing on demand.
• ⚡ Performance & extensibility — CUDA kernels are refactored into small device helper functions (circular / parallel / line-lidar), enabling easier extension and higher throughput on supported hardware. The CPU evaluator performs safe occlusion checks and requires a scene mesh when occlusion is enabled.

Experimental Features (Not Ready for Production)

• 🔬 Three-Space Framework — A mathematical framework for robot-aware coverage path planning with mappings between T-space (surface points), S-space (effector poses), and R-space (robot joint configurations).
  • Status: Experimental, incomplete, and not thoroughly tested
  • Location: benchmarking_3dcpp/three_space/ directory
  • Includes: Robot model integration (KDL), forward/inverse kinematics mappings, and support for algorithms that output in different spaces
  • See: docs/three_space_framework_usage.md for usage details and current limitations

The stable features listed above are well-tested and suitable for benchmarking evaluations. Experimental features are provided for research purposes and should be used with caution.

Dependencies

Required

• ROS 2 (Humble)

• Open3D 0.18.0 (C++ version)

  • Important: Please do not use pip install open3d. You must compile the C++ library from source.

• Eigen3

  sudo apt-get install libeigen3-dev

• GLFW3

  sudo apt install libglfw3 libglfw3-dev

• TBB

  sudo apt-get install libtbb-dev

• CGAL

  # Recommended CGAL + dependencies (enables isotropic remeshing feature)
  sudo apt-get install libcgal-dev libgmp-dev libmpfr-dev libboost-all-dev

  Note: the repository's remeshing helper looks for the CGAL PMP remeshing headers (for example CGAL/Polygon_mesh_processing/remesh.h). If those headers are not found at build time the project will still compile, but the CGAL remeshing API will be a no-op stub and remeshing requests will return failure. Installing the packages above enables the full isotropic remeshing implementation.

Recommended

• CUDA (e.g., 11.8) for accelerated computation.

Other / system libraries

• HDF5 (C/C++ dev) — used for writing evaluation results (.h5). The project locates HDF5 via CMake (HDF5::HDF5).
• libglfw3-dev, libeigen3-dev, libtbb-dev — see above.

Installation & Quick Start

The following steps show how to install dependencies, create a workspace, build the project and prepare a surface for evaluation.

Create workspace, Clone, and Build

mkdir -p ~/benchmark_ws/src
cd ~/benchmark_ws/src
git clone https://github.com/ZJUTongYang/benchmarking_3dcpp.git
cd ~/benchmark_ws
colcon build
source install/setup.bash

Prepare the Surfaces

Copy the STL or PCD file you wish to evaluate into the benchmarking_3dcpp/scene/ directory. We currently provide an example file, remeshed_saddle.stl.

Register the Surfaces and Algorithms

Open the benchmarking_3dcpp/config/config.yaml and modify it according to the instructions inside the file.

Configuration format for scenes:

Each scene must specify its own point_density for surface sampling. This allows different surfaces to use different sampling densities based on their complexity:

scenes:
  - name: "remeshed_saddle"
    filename: "remeshed_saddle.stl"
    frame_id: "remeshed_saddle"
    point_density: 50000.0  # points per unit area
  - name: "seabed_dunes"
    filename: "seabed_dunes.stl"
    frame_id: "seabed_dunes"
    point_density: 100000.0  # higher density for complex surfaces

The point_density value determines how many surface points are sampled per unit area. Higher values provide more detailed coverage evaluation but require more computation.

Algorithm instances:

Algorithms can have multiple instances with different parameter configurations:

algorithms:
  - name: "Choset1998Coverage"
    instances:
      - id: "choset_default"
        params:
          projection_direction_vector: [0, 0, 1]
          sweep_line_spacing: 0.10
      - id: "choset_fine"
        params:
          projection_direction_vector: [0, 0, 1]
          sweep_line_spacing: 0.05  # Finer spacing

Explicit test combinations:

Tests are explicitly specified by the user. Each test has a unique id and references an effector, scene, algorithm, and a required algorithm instance:

tests:
  - id: 1
    effector: "circular_0_05m"
    scene: "remeshed_saddle"
    algorithm: "Yang2023Template"
    algorithm_id: "yang_basic"

  - id: 2
    effector: "circular_0_05m"
    scene: "remeshed_saddle"
    algorithm: "Choset1998Coverage"
    algorithm_id: "choset_coarse"

The algorithm_id field is required and must reference one of the instances defined under the algorithm configuration.

Rebuild after changes

Whenever you modify the config file, the code, or add new surfaces, re-compile:

cd ~/benchmark_ws
colcon build

Usage

Run benchmark

Use the following command:

ros2 launch benchmarking_3dcpp eval.launch.py

After a while, you will get results like:

[INFO] [benchmarking_3dcpp]: Finished scheduling 3 tests.
We create task 1, effector: circular_0_05m, scene: remeshed_saddle, algorithm: Yang2023Template, instance: yang_basic
We create task 2, effector: circular_0_05m, scene: remeshed_saddle, algorithm: Choset1998Coverage, instance: choset_coarse
We create task 3, effector: circular_0_05m, scene: remeshed_saddle, algorithm: Choset1998Coverage, instance: choset_fine
[INFO] [benchmarking_3dcpp]: We start executing Yang2023Template
[INFO] [benchmarking_3dcpp]: Finish executing Yang2023Template with computation time 0.0154297s.
[INFO] [benchmarking_3dcpp]: Coverage evaluation time: 0.00314577s
[INFO] [benchmarking_3dcpp]: Coverage statistics:
[INFO] [benchmarking_3dcpp]:   Coverage ratio: 81.4042%
[INFO] [benchmarking_3dcpp]:   Max coverage count: 8
[INFO] [benchmarking_3dcpp]:   Average coverage count: 1.60658
[INFO] [benchmarking_3dcpp]: Saved to /home/yt/icpp_ws/install/benchmarking_3dcpp/share/benchmarking_3dcpp/output/circular_0_05m_remeshed_saddle_Yang2023Template_cpu.h5
[INFO] [benchmarking_3dcpp]: All scheduled tests finished.

---

Using BenchmarkingAPI as a Library

The benchmarking_3dcpp package can also be used as a pure C++ library in your own algorithms. Simply link against benchmarking_3dcpp and use the BenchmarkingAPI class.

Recommendation: For most use cases, implement your algorithm as a CoverageAlgorithm subclass that outputs SENSOR_SPACE (effector poses). Use the stable evaluation APIs like getCoverablePointsForEachWaypoint() to assess coverage. The Three-Space Framework features (robot models, kinematic mappings) are experimental and should only be used if you specifically need robot-aware planning capabilities.

Example

#include <benchmarking_3dcpp/api/benchmarking_api.hpp>
#include <Eigen/Geometry>
#include <iostream>

int main() {
    // Create API from config file
    auto api = benchmarking_3dcpp::BenchmarkingAPI::create("path/to/config.yaml");

    // Get surface point count
    int64_t count = api->getSurfacePointCount("remeshed_saddle");
    std::cout << "Surface points: " << count << std::endl;

    // Random sampling
    auto points = api->getRandomSurfacePoints("remeshed_saddle", 10);
    std::cout << "Sampled " << points.size() << " points" << std::endl;

    // Evaluate coverage for a path
    std::vector<Eigen::Vector3d> positions = {
        Eigen::Vector3d(0.1, 0.1, 0.5),
        Eigen::Vector3d(0.2, 0.1, 0.5)
    };
    std::vector<Eigen::Quaterniond> orientations = {
        Eigen::Quaterniond::Identity(),
        Eigen::Quaterniond::Identity()
    };

    auto covered = api->getCoverablePointsForEachWaypoint(
        "circular_0_05m", "remeshed_saddle", positions, orientations);

    std::cout << "Coverage evaluation complete" << std::endl;

    // Save results
    bool saved = api->saveAsTestCase(
        "circular_0_05m", "remeshed_saddle", "MyAlgorithm",
        positions, orientations);
    std::cout << "Results saved: " << (saved ? "yes" : "no") << std::endl;

    return 0;
}

CMakeLists.txt for Your Package

cmake_minimum_required(VERSION 3.8)
project(my_algorithm)

find_package(benchmarking_3dcpp REQUIRED)

add_executable(my_algo src/main.cpp)
target_link_libraries(my_algo benchmarking_3dcpp)

# No ROS2 dependencies required when using BenchmarkingAPI

Note: When using BenchmarkingAPI as a library, you do not need ROS2 dependencies. The benchmarking node still uses ROS2 for launch configuration and visualization.

---

Examples

Visualize the result

Now the evaulation hdf5 file has been store in the shared folder of the benchmarking platform. Launch a viz node and provide it with the file name.

ros2 launch benchmarking_3dcpp viz.launch.py # rviz2 will be also launched here
ros2 topic pub -1 /load_and_visualize_h5 std_msgs/msg/String "'data': 'circular_remeshed_saddle_Yang2023Template.h5' "

Ensure that the Fixed Frame in Rviz2 is set to world. Then, add the display topics "/path_visualization" and "surface_pointcloud". You should see visualizations in Rviz2 like:

Citation

If you use our benchmarking platform in your research, please consider citing our related paper:

@article{Yang2023Template,
title={Template-Free Nonrevisiting Uniform Coverage Path Planning on Curved Surfaces},
author={Yang, Tong and Miro, Jaime Valls and Nguyen, Minh and Wang, Yue and Xiong, Rong},
journal={IEEE/ASME Transactions on Mechatronics},
year={2023},
volume={28},
number={4},
pages={1853--1861},
publisher={IEEE}
}