Method and apparatus for reconstructing a surface using a ball-pivoting algorithm
US6968299B1 · kind B1 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 14, 2000 |
| Grant date | Nov 22, 2005 |
| Priority date | — |
| Expiry date | Apr 14, 2020 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06V10/46
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and apparatus are disclosed for finding a triangle mesh that interpolates a set of points obtained from a scanning system. A ball-pivoting algorithm computes a triangle mesh interpolating a given point cloud. The disclosed ball-pivoting algorithm triangulates a set of points by “rolling” a ball of radius r on the point cloud. The points are surface samples acquired with multiple range scans of an object. The ball-pivoting algorithm starts with a seed triangle, and pivots the ball of a given radius, r, around an edge of the triangle. During the pivoting operation, the ball revolves around the edge while keeping in contact with the edge's endpoints. The ball pivots until it touches another scan point, forming another triangle. The ball-pivoting operation continues until all reachable edges have been tried, and then starts from another seed triangle, until all scan points have been considered.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.