 |
 |
|
|
|
|
Title: |
US6968299:
Method and apparatus for reconstructing a surface using a ball-pivoting algorithm
[ Derwent Title ]
>> View Certificate of Correction for this publication

|
Country: |
US United States of America

|
| |
Inventor: |
Bernardini, Fausto; Hartsdale, NY, United States of America
Mittleman, Joshua David; Croton-on-Hudson, NY, United States of America
Rushmeier, Holly E.; Mount Kisco, NY, United States of America
Silva, Claudio T.; Mahwah, NJ, United States of America
Taubin, Gabriel; Hartsdale, NY, United States of America

|
Assignee: |
International Business Machines Corporation, Armonk, NY, United States of America
other patents from INTERNATIONAL BUSINESS MACHINES CORPORATION (280070) (approx. 44,393)
News, Profiles, Stocks and More about this company

|
Published / Filed: |
2005-11-22
/ 2000-04-14

|
Application Number: |
US2000000549432

|
IPC Code: |
Advanced:
G06F 17/10;
G06F 17/17;
G06T 17/20;
Core:
more...
IPC-7:
G06F 17/10;

|
ECLA Code: |
G06K9/48; G06F17/17M; G06T17/20;

|
U.S. Class: |
703/002;
703/001;
703/006;
345/424;
345/475;

|
Field of Search: |
703/001,2,6
345/424,475

|
Priority Number: |
| 2000-04-14 |
US2000000549432 |

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

|
Attorney, Agent or Firm: |
Ryan, Mason & Lewis, LLP ;
Karra, Esq., Satheesh K. ;

|
Primary / Asst. Examiners: |
Phan, Thai; Day, Herng-der

|
Maintenance Status: |
CC Certificate of Correction issued View Certificate of Correction

|
INPADOC Legal Status: |
Show legal status actions

|
Family: |
None

|
First Claim:
Show all 30 claims |
1. A computer implemented method for reconstructing a surface of an object, said method comprising the steps of: obtaining multiple sets of three-dimensional scan data of said object; finding a seed triangle in said scan data to form a triangulated mesh; pivoting a ball around an edge of said triangulated mesh until a new point in said scan data is hit by said ball, wherein said edge and said new point define a new triangle; adding said new triangle to said triangulated mesh; selecting a new edge of said triangulated mesh and repeating said finding, pivoting and adding steps until all points in said scan data have been used or a valid seed triangle cannot be formed.

|
Background / Summary: |
Show background / summary

|
Drawing Descriptions: |
Show drawing descriptions

|
Description: |
Show description

|
Forward References: |
Show 8 U.S. patent(s) that reference this one

|
 |
 |
|
|
|
|
Foreign References: |
None

|
Other References: |
Boissonnat, “Geometric Structure for Three-Dimensional Shape Representation”, ACM Transactions on Graphics, vol. 3, Issue 4, Oct. 1984, pp. 266-286.
(21 pages)
Cited by 3 patents
Hoppe et al., “Surface Reconstruction from Unorganized points”, Computer Graphics (SIGGRAPH '92 Proceedings), Jul. 1992, pp. 71-78.
Pulli et al., “Robust meshes from multiple range maps”, Proceedings of International of Conference on Recent Advances in 3-D Digital Imaging and Modeling, May 1997, pp. 205-211.
Crossno et al., “Spiraling Edge: Fast Surface Reconstruction from Partially Organized Sample Points”, Proceedings of Visualization '99, Oct. 1999, pp. 317-324.
Bernardini et al., “Sampling and Reconstructing Manifolds Using Alpha-shapes,” in Proc. of the Ninth Canadian Conference on Computational Geometry, pp. 193-198, (Aug. 1997).

|


|
Nominate this for the Gallery...

|
|