The ball-pivoting algorithm for surface reconstruction

TLDR

Surface reconstruction often relies on point clouds obtained from multiple range scans of an object. The Ball‑Pivoting Algorithm builds a triangle mesh by rolling a ball of user‑specified radius around point‑cloud edges, creating triangles when the ball touches three points without enclosing any others, and iteratively repeating with larger radii to handle uneven sampling. On millions‑point scans of complex 3D objects, the BPA produced high‑quality reconstructions while using less memory and running faster than competing methods.

Abstract

The Ball-Pivoting Algorithm (BPA) computes a triangle mesh interpolating a given point cloud. Typically, the points are surface samples acquired with multiple range scans of an object. The principle of the BPA is very simple: Three points form a triangle if a ball of a user-specified radius p touches them without containing any other point. Starting with a seed triangle, the ball pivots around an edge (i.e., it revolves around the edge while keeping in contact with the edge's endpoints) until it touches another point, forming another triangle. The process continues until all reachable edges have been tried, and then starts from another seed triangle, until all points have been considered. The process can then be repeated with a ball of larger radius to handle uneven sampling densities. We applied the BPA to datasets of millions of points representing actual scans of complex 3D objects. The relatively small amount of memory required by the BPA, its time efficiency, and the quality of the results obtained compare favorably with existing techniques.