Work Files Saved Searches
   My Account                                                  Search:   Quick/Number   Boolean   Advanced   Derwent    Help   


 The Delphion Integrated View

  Buy Now:   Buy PDF- 26pp  PDF  |   File History  |   Other choices   
  Tools:  Citation Link  |  Add to Work File:    
  View:  Expand Details   |  INPADOC   |  Jump to: 
  Go to:  Derwent  
 Email this to a friend  Email this to a friend 
       
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

View Images High
Resolution

 Low
 Resolution

 
26 pages

 
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

       
U.S. References: Go to Result Set: All U.S. references   |  Forward references (8)   |   Backward references (3)   |   Citation Link

Buy
PDF
Patent  Pub.Date  Inventor Assignee   Title
Buy PDF- 28pp US5465323  1995-11 Mallet  Association Scientifique pour la Geologie et de ses Applications Method for modelling a surface and device for implementing same
Buy PDF- 60pp US5988862  1999-11 Kacyra et al.  Cyra Technologies, Inc. Integrated system for quickly and accurately imaging and modeling three dimensional objects
Buy PDF- 21pp US6606091  2003-08 Liang et al.  Siemens Corporate Research, Inc. System for interactive 3D object extraction from slice-based medical images
       
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).


  • Inquire Regarding Licensing

    Powered by Verity


    Plaques from Patent Awards      Gallery of Obscure PatentsNominate this for the Gallery...

    Thomson Reuters Copyright © 1997-2010 Thomson Reuters 
    Subscriptions  |  Web Seminars  |  Privacy  |  Terms & Conditions  |  Site Map  |  Contact Us  |  Help