3D Path Planning

Path planning on 3D surfaces is a fundamental problem in robotics, computer graphics, and geospatial analysis, among other fields. Whether it’s navigating a drone along the contours of a hilly landscape or optimizing the movement of a robot over a complex structure, finding efficient, collision-free paths on curved surfaces is essential across many industries.

A particularly interesting and challenging case is when the goal is not just to find a path, but to generate a complete coverage of the surface with a path of a fixed width. This scenario arises in tasks like:

• Precision agriculture, where sprayers or seeders must cover hilly or terraced farmland uniformly.
• Surface cleaning or painting robots, which need to ensure full surface coverage without overlaps or gaps.
• 3D scanning and inspection, where a sensor or camera must follow a path that guarantees complete data capture.

Why Is This Problem Hard?

Despite its importance, planning such paths on 3D surfaces is far from trivial. Unlike flat surfaces, curved geometries introduce several challenges:

• Irregular topology: Surfaces may have holes, folds, or non-trivial curvature, complicating standard grid or raster-based approaches.
• No canonical orientation: Unlike planar spaces where directions like "up" and "right" are well-defined, on curved surfaces there is no universal frame of reference.
• Projection and distortion: Mapping a 3D surface to 2D for planning purposes often introduces distortions, which can lead to inefficient or invalid paths when mapped back.
• Continuity constraints: Smooth transitions between path segments are necessary, especially when the system executing the path has limited maneuverability.

Furthermore, there is no one-size-fits-all algorithm. The “best” path depends heavily on the application, the surface geometry, and even physical constraints of the device following the path.

Our Solution

The specific challenge we addressed in a recent project was to generate a continuous path that uniformly covers a selected body part—such as a leg, back, etc.—with a given path width as a user-defined parameter. This functionality is useful in a range of applications, from medical scanning to cosmetic or therapeutic treatments, where consistent surface coverage is crucial.

The input to our system is a point cloud representing the 3D surface, and the output is a path (ordered set of points with additonal metadata) that traverses this surface while adhering to the specified width. The first challenge was selecting the optimal starting point, which we solved by developing a custom algorithm. Before the actual path generation, we also converted the point cloud into a polygon mesh. This conversion is essential for making surface calculations and traversal feasible, as it allows us to work with a structured representation of the 3D geometry.

Path generation is then performed by utilizing surface normals to maintain alignment with the local geometry, and by employing quaternion-based computations to ensure smooth orientation changes along the 3D surface. This mathematical approach ensures robust handling of curvature without introducing abrupt changes in direction or orientation.

Additionally, our system supports partial surface coverage. For instance, when only the back or one side of a limb needs to be covered, we apply a custom filtering algorithm specifically designed for concave geometries. This ensures that the resulting path remains well-behaved and efficient, avoiding unnecessary coverage or erratic path fragments.

Above is a short video demonstrating our solution in action.