The ball-pivoting algorithm for surface reconstruction

Fausto Bernardini, Joshua Mittleman, Holly Rushmeier, Claudio Silva, Gabriel Taubin

Research output: Contribution to journalArticlepeer-review

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 (he 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.

Original languageEnglish (US)
Pages (from-to)349-359
Number of pages11
JournalIEEE Transactions on Visualization and Computer Graphics
Volume5
Issue number4
DOIs
StatePublished - 1999

Keywords

  • 3d scanning
  • Point cloud
  • Range image
  • Shape reconstruction

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition
  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'The ball-pivoting algorithm for surface reconstruction'. Together they form a unique fingerprint.

Cite this