US7091969B2
Expired / Lapsed
US
⏱️ 0.0 years remaining
Frontier advancing polygonization
Assignee: National University of Singapore
•
Filing: 2001-10-02
•
Granted: 2006-08-15
•
Expires: 2021-10-02
Abstract
Abstract A method of polygonizing an object calculates indicators that points within a set (Q) of points within three space representing the object likely lie near a surface discontinuity of the object. A global mesh is formed around a point that likely does not lie near a surface discontinuity (i.e. a reliable point). Local meshes are formed about reliable points on the frontier of this global mesh. Each local mesh is combined with the global mesh, thereby adding to the global mesh and advancing the frontier. Once a local mesh has been formed about each reliable point on the frontier and added to the global mesh, a local mesh may be formed about a point on the frontier that is more likely to lie near a surface discontinuity. The formation of local meshes can be repeated until no frontiers are left, or until all points have been added to the global mesh.
Inventors
- 👤 Wee K Leow
- 👤 Zhiyong Huang
- 👤 Luping Zhou
- 👤 Indriyati Atmosukarto
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 09:59
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20
Claims Analysis
Total Claims: 21
Claim 1
Independent Claim
118 words
A method of polygonizing an object, said object represented by a set Q of points in three space, said method comprising: a. for each of said points, calculating an indicator of the likelihood that said each of said point lies near a surface discontinuity of said object; b. constructing a global mesh having a frontier around one of said points having a low likelihood of lying near a surface discontinuity; c. constructing a local mesh about one of said points having a low likelihood of lying near a surface discontinuity, and on said frontier; d. combining said local mesh with said global mesh thereby adding points within said local mesh to said global mesh and advancing said frontier.
Claim 2
Independent Claim
118 words
A method of polygonizing an object, said object represented by a set Q of points in three space, said method comprising: a. for each of said points, calculating an indicator of the likelihood that said each of said point lies near a surface discontinuity of said object; b. constructing a global mesh having a frontier around one of said points having a low likelihood of lying near a surface discontinuity; c. constructing a local mesh about one of said points having a low likelihood of lying near a surface discontinuity, and on said frontier; d. combining said local mesh with said global mesh thereby adding points within said local mesh to said global mesh and advancing said frontier.
Claim 3
Dependent Claim
39 words
The method of claim 1 , further comprising repeating said constructing a local mesh and said combining said local mesh for another one of said points on said frontier having a low likelihood of lying near a surface discontinuity.
Claim 4
Dependent Claim
39 words
The method of claim 2 , further comprising repeating said constructing and said combining until a local mesh has been constructed about each of said points on said frontier having a low likelihood of lying near a surface discontinuity.
Claim 5
Dependent Claim
89 words
The method of claim 3 , constructing a further local mesh about a point on said frontier not having a low likelihood of lying near a surface discontinuity; combining said further local mesh with said global mesh thereby adding points within said local mesh to said global mesh and advancing said frontier; repeating said constructing a local mesh and said combining said local mesh until a local mesh has been constructed about each of said points on said frontier having a low likelihood of lying near a surface discontinuity.
Claim 6
Dependent Claim
28 words
The method of claim 3 , wherein each said indicator of a likelihood that each point lies near a surface discontinuity is computed using Principle Component Analysis (PCA).
Claim 7
Dependent Claim
59 words
The method of claim 5 , wherein each said indicator of a likelihood that each said point lies near a surface discontinuity is computed by calculating a quotient of the smallest eigenvalue of a Hottelling tranform matrix of a collection of points within Q including said each sample point, divided by the largest eigenvalue of said Hotteling Transform matrix.
Claim 8
Dependent Claim
33 words
The method of claim 6 , wherein said Hotteling Transform matrix for a point of interest within Q is calculated using a selected number of points within Q about said point of interest.
Claim 9
Dependent Claim
31 words
The method of claim 6 , wherein said Hotteling Transform matrix for a point of interest is calculated using points within Q within a selected distance of said point of interest.
Claim 10
Dependent Claim
30 words
The method of claim 6 , wherein said points having a low likelihood of lying near a surface discontinuity have an associated quotient of less than or equal to 0.05.
Claim 11
Dependent Claim
17 words
The method of claim 1 , wherein said global mesh and said local mesh are interpolating meshes.
Claim 12
Dependent Claim
17 words
The method of claim 1 , wherein said global mesh and said local mesh are approximating meshes.
Claim 13
Dependent Claim
186 words
The method of claim 1 , wherein said constructing a local mesh about said frontier point comprises: finding the nearest neighbor p 0 to said frontier point; finding a point p 1 within Q so that the distance between an intersection at v 1 of a perpendicular bisector of a line joining said frontier point and p 1 and a perpendicular bisector of a line joining said frontier point and p 0 , and a mid-point between said frontier point and p 0 is a minimum; for i=1, finding another point p i+1 within Q so that the distance between an intersection at v i+1 of a perpendicular bisector of a line joining said frontier point and p i+1 and a line joining said frontier point and p i , and v i is a minimum; repeating said finding another point, for integers i=2, 3, . . . until p i coincides with p 0 ; using each point p 0 , p 1 , p 2 , . . . p i and said frontier point to form a closed mesh around said frontier point.
Claim 14
Dependent Claim
80 words
The method of claim 10 , wherein said intersection v i+1 is computed as an intersection of (i) a tangent plane at said frontier point, (ii) a plane at a mid point between said frontier point and p i with a normal pointing from said point on said frontier to p i , and (iii) a plane at a mid point between said frontier point and p i+1 with a normal pointing from said frontier point to p i+1 .
Claim 15
Dependent Claim
180 words
The method of claim 1 , wherein said constructing a local mesh about said frontier point comprises: finding the nearest neighbor p 0 to a corresponding point in Q corresponding to said frontier point; finding a point p 1 within Q so that the distance between an intersection at w 1 of a tangent plane at said corresponding point, a tangent plane at p 0 and a tangent plane at p 1 , and a line joining said corresponding point and p 0 is a minimum; for i=1, finding another point p i+1 within Q so that the distance between an intersection at w i+1 of a tangent plane at said corresponding point; a tangent plane at p i , and a tangent plane at p i+1 and w i is a minimum; repeating said finding another point, for integers i=2, 3, . . . until p i+1 coincides with p 0 ; using w 1 , w 2 , . . . w i+1 to form a closed mesh around said corresponding point, and thereby about said frontier point.
Claim 16
Dependent Claim
25 words
The method of claim 14 wherein a normal of a tangent plane at each point is computed along with an associated one of said indicators.
Claim 17
Dependent Claim
24 words
The method of claim 15 , wherein said normals are calculated as eigenvectors of an associated Hottelling Transform matrix for each of said points.
Claim 18
Dependent Claim
129 words
A computing device, comprising: a processor; computer readable memory in communication with said processor, storing processor executable instruction that adapt said computing device to polygonize an object represented by a set Q of points within three space, by calculating an indicator of the likelihood that said each point lies near a surface discontinuity of said object, for each of said points; constructing a global mesh having a frontier around one of said points having a low likelihood of lying near a surface discontinuity; constructing a local mesh about one of said points having a low likelihood of lying near a surface discontinuity, and on said frontier; combining said local mesh with said global mesh thereby adding points within said local mesh to said global mesh and advancing said frontier.
Claim 19
Dependent Claim
129 words
A computing device, comprising: a processor; computer readable memory in communication with said processor, storing processor executable instruction that adapt said computing device to polygonize an object represented by a set Q of points within three space, by calculating an indicator of the likelihood that said each point lies near a surface discontinuity of said object, for each of said points; constructing a global mesh having a frontier around one of said points having a low likelihood of lying near a surface discontinuity; constructing a local mesh about one of said points having a low likelihood of lying near a surface discontinuity, and on said frontier; combining said local mesh with said global mesh thereby adding points within said local mesh to said global mesh and advancing said frontier.
Claim 20
Dependent Claim
123 words
Computer readable medium storing processor executable instruction that, when loaded at a computing device adapt said computing to polygonize an object represented by a set Q of points within three space, by calculating an indicator of the likelihood that said each point lies near a surface discontinuity of said object, for each of said points; constructing a global mesh having a frontier around one of said points having a low likelihood of lying near a surface discontinuity; constructing a local mesh about one of said points having a low likelihood of lying near a surface discontinuity, and on said frontier; combining said local mesh with said global mesh thereby adding points within said local mesh to said global mesh and advancing said frontier.
Claim 21
Dependent Claim
123 words
Computer readable medium storing processor executable instruction that, when loaded at a computing device adapt said computing to polygonize an object represented by a set Q of points within three space, by calculating an indicator of the likelihood that said each point lies near a surface discontinuity of said object, for each of said points; constructing a global mesh having a frontier around one of said points having a low likelihood of lying near a surface discontinuity; constructing a local mesh about one of said points having a low likelihood of lying near a surface discontinuity, and on said frontier; combining said local mesh with said global mesh thereby adding points within said local mesh to said global mesh and advancing said frontier.
References Cited (Backward Citations)
US5428726A
Cited
US5677846A
Cited
JPH07219977A
Cited
US5880977A
Cited
US5886702A
Cited
US5945996A
Cited
US6075541A
Cited
JP2000076486A
Cited
US6806874B2
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2009-08-14 | 2010-02-13 | 2010-08-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2013-08-14 | 2014-02-13 | 2014-08-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2017-08-14 | 2018-02-13 | 2018-08-15 | $7700.00 | Window Closed / Lapsed |