The ball-pivoting algorithm for surface reconstruction

The Bail-Pivoting Algorithm (BPA) computes a triangle mesh interpolating a given point cloud. Typically, the points are surlace samples acquired with multiple range scans of an object. The principle of the BPA is very simple: Three points form a triangle if a bail of a user-specified radius p touches them without containing any other point. Starting with a seed triangle, the bail 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.