US5506947A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Curve and surface smoothing without shrinkage
Assignee: International Business Machines Corp
•
Filing: 1994-09-22
•
Granted: 1996-04-09
•
Expires: 2014-09-22
Abstract
Abstract The present invention smooths piece-wise linear shapes by defining neighborhoods of vertices around vertices of the shape. One or more vectors is defined between the vertex and each of its neighbors. Vector sums are alternately multiplied by one of two scale factors. The scale factors are opposite in sign with the negative scale factor of larger magnitude. The vertices of the shape are displaced by the multiplied vector sums to attain new positions. The process is repeated with the vertices moving back and forth approximately through their final position until the shape is smoothed without shrinkage.
Inventors
- 👤 Gabriel Taubin
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 21:09
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/20
Claims Analysis
Total Claims: 23
Claim 1
Independent Claim
312 words
A computer implemented method for smoothing a piece-wise linear shape represented on a computer as a set of vertices, comprising the computer implemented steps of: a. determining a neighborhood associated with each vertex, each neighborhood comprising a subset of zero or more neighbor vertices from the set of vertices such that the vertex is not included in its neighborhood; b. describing a first and a second scale factor of opposite signs, the negative scale factor being of greater magnitude than the positive scale factor; c. determining a first vector displacement for each vertex, the first vector displacement being the first scale factor times a first vector average, the first vector average being the average of all of the zero or more neighbor vectors, each neighbor vector being a vector from the vertex to each of its neighbor vertices, all the vertices being at a respective current position; d. determining a first position of each vertex, the first position being the position of the vertices moved by their first vector displacement from their current position, respectively; e. determining a second vector displacement for each vertex, the second vector displacement being the second scale factor times a second vector average, the second vector average being of the average of all of zero or more second neighbor vectors, each second neighbor vector being a vector from the vertex to each of the neighbor vertices, all vertices being at their respective first position, respectively; f. determining a second position of each vertex, the second position being the position of the vertices moved by their respective second vector displacement from their first position, respectively; g. establishing the current position of each vertex as its respective second position; and h. if the shape defined by the vertices in their second position does not meet a smoothness criteria, repeating steps c through h until the smoothness criteria is met.
Claim 2
Dependent Claim
312 words
A computer implemented method for smoothing a piece-wise linear shape represented on a computer as a set of vertices, comprising the computer implemented steps of: a. determining a neighborhood associated with each vertex, each neighborhood comprising a subset of zero or more neighbor vertices from the set of vertices such that the vertex is not included in its neighborhood; b. describing a first and a second scale factor of opposite signs, the negative scale factor being of greater magnitude than the positive scale factor; c. determining a first vector displacement for each vertex, the first vector displacement being the first scale factor times a first vector average, the first vector average being the average of all of the zero or more neighbor vectors, each neighbor vector being a vector from the vertex to each of its neighbor vertices, all the vertices being at a respective current position; d. determining a first position of each vertex, the first position being the position of the vertices moved by their first vector displacement from their current position, respectively; e. determining a second vector displacement for each vertex, the second vector displacement being the second scale factor times a second vector average, the second vector average being of the average of all of zero or more second neighbor vectors, each second neighbor vector being a vector from the vertex to each of the neighbor vertices, all vertices being at their respective first position, respectively; f. determining a second position of each vertex, the second position being the position of the vertices moved by their respective second vector displacement from their first position, respectively; g. establishing the current position of each vertex as its respective second position; and h. if the shape defined by the vertices in their second position does not meet a smoothness criteria, repeating steps c through h until the smoothness criteria is met.
Claim 3
Dependent Claim
35 words
A method, as in claim 1, where the neighborhood vectors are in the direction from the neighbor vertices to the vertex and the positive scale factor is greater in magnitude than the negative scale factor.
Claim 4
Dependent Claim
14 words
A method for smoothing, as in claim 1, where the shape is a curve.
Claim 5
Dependent Claim
13 words
A method for smoothing, as in claim 1, where the shape is surface.
Claim 6
Dependent Claim
15 words
A method for smoothing, as in claim 1, where the vector average is vector sum.
Claim 7
Dependent Claim
12 words
A method, as in claim 1, where the scale factors are iteration-dependent.
Claim 8
Dependent Claim
12 words
A method, as in claim 1, where the scale factors are vertex-dependent.
Claim 9
Dependent Claim
14 words
A method, as in claim 1, where the scale factors are iteration-dependent and vertex-dependent.
Claim 10
Dependent Claim
325 words
A computer implemented method for smoothing a piece-wise linear shape modeled by a computer as a set of vertices, comprising the computer implemented steps of: a. determining a neighborhood associated with each vertex, each neighborhood comprising a subset of zero or more neighbor vertices from the set of vertices such that the vertex is not included in its neighborhood; b. describing a first and a second scale factor of opposite signs, the negative scale factor being of greater magnitude than the positive scale factor; c. determining a first vector displacement for each vertex, the first vector displacement being the first scale factor times a first vector average, the first vector average being the weighted average of all of zero or more neighbor vectors, each neighbor vector being a vector from the vertex to each of its neighbor vertices and weighted by its respective neighbor weight, all the vertices being at a respective current position; d. determining a first position of each vertex, the first position being the position of the vertex moved by its first vector displacement from its current position, respectively; e. determining a second vector displacement for each vertex, the second vector displacement being the second scale factor times a second vector average, the second vector average being the weighted average of all of the zero or more second neighbor vectors, each second neighbor vector being a vector from the vertex to each of the neighbor vertices and weighted by its respective neighbor weight, all vertices being at their respective first position, respectively; f. determining a second position of each vertex, the second position being the position of the vertex moved by the second vector displacement from its first position, respectively; g. if the shape defined by the vertices in their second position does not meet a smoothness criteria, establishing the current position of each vertex as its respective second position and repeating steps c through g until the smoothness criteria is met.
Claim 11
Dependent Claim
325 words
A computer implemented method for smoothing a piece-wise linear shape modeled by a computer as a set of vertices, comprising the computer implemented steps of: a. determining a neighborhood associated with each vertex, each neighborhood comprising a subset of zero or more neighbor vertices from the set of vertices such that the vertex is not included in its neighborhood; b. describing a first and a second scale factor of opposite signs, the negative scale factor being of greater magnitude than the positive scale factor; c. determining a first vector displacement for each vertex, the first vector displacement being the first scale factor times a first vector average, the first vector average being the weighted average of all of zero or more neighbor vectors, each neighbor vector being a vector from the vertex to each of its neighbor vertices and weighted by its respective neighbor weight, all the vertices being at a respective current position; d. determining a first position of each vertex, the first position being the position of the vertex moved by its first vector displacement from its current position, respectively; e. determining a second vector displacement for each vertex, the second vector displacement being the second scale factor times a second vector average, the second vector average being the weighted average of all of the zero or more second neighbor vectors, each second neighbor vector being a vector from the vertex to each of the neighbor vertices and weighted by its respective neighbor weight, all vertices being at their respective first position, respectively; f. determining a second position of each vertex, the second position being the position of the vertex moved by the second vector displacement from its first position, respectively; g. if the shape defined by the vertices in their second position does not meet a smoothness criteria, establishing the current position of each vertex as its respective second position and repeating steps c through g until the smoothness criteria is met.
Claim 12
Dependent Claim
29 words
A method of smoothing, as in claim 9, where all the neighbor weights are positive numbers with all the neighbor weights in each neighborhood summing to the value one.
Claim 13
Dependent Claim
29 words
A method of smoothing, as in claim 9, where the vertices meeting the smoothness criteria define an image of a smoothed shape that is displayed on a graphical interface.
Claim 14
Dependent Claim
17 words
A method, as in claim 9, where the piece-wise linear shape is a polytope of arbitrary dimension.
Claim 15
Dependent Claim
19 words
A method, as in claim 9, where the weights are pre-specified and are kept unchanged throughout all the steps.
Claim 16
Dependent Claim
15 words
A method, as in claim 9, where the weights change during one or more iterations.
Claim 17
Dependent Claim
13 words
A method, as in claim 9, where the weighted average is a sum.
Claim 18
Dependent Claim
320 words
A computer implemented method for smoothing a piece-wise linear shape comprising the steps of: a. determining a set of a plurality of vertices describing the shape; b. determining a neighborhood associated with each vertex, each neighborhood comprising a subset of zero or more neighbor vertices from the set of vertices such that the vertex is not included in its neighborhood; c. describing a first and a second scale factor of opposite signs, the negative scale factor being of greater magnitude than the positive scale factor; d. describing a number of iterations; e. determining a first vector displacement for each vertex, the first vector displacement being the first scale factor times a first vector average, the first vector average being the average of all of zero or more neighbor vectors, each neighbor vector being a vector from the vertex to each of its neighbor vertices, all the vertices being at a respective current position; f. determining a first position of each vertex, the first position being the position of the vertices moved by their first vector displacement from their current position, respectively; g. determining a second vector displacement for each vertex, the second vector displacement being the second scale factor times a second vector average, the second vector average being of the average of all of zero or more second neighbor vectors, each second neighbor vector being a vector from the vertex to each of the neighbor vertices, all vertices being at their respective first positions; h. determining a second position of each vertex, the second position being the position of the vertices moved by their respective second vector displacement from their first position, respectively; i. establishing the current position of each vertex as its respective second position; and j. if the number of times that steps e to i have been executed is less than the number of iterations, repeating steps d through i until the smoothness criteria is met.
Claim 19
Dependent Claim
320 words
A computer implemented method for smoothing a piece-wise linear shape comprising the steps of: a. determining a set of a plurality of vertices describing the shape; b. determining a neighborhood associated with each vertex, each neighborhood comprising a subset of zero or more neighbor vertices from the set of vertices such that the vertex is not included in its neighborhood; c. describing a first and a second scale factor of opposite signs, the negative scale factor being of greater magnitude than the positive scale factor; d. describing a number of iterations; e. determining a first vector displacement for each vertex, the first vector displacement being the first scale factor times a first vector average, the first vector average being the average of all of zero or more neighbor vectors, each neighbor vector being a vector from the vertex to each of its neighbor vertices, all the vertices being at a respective current position; f. determining a first position of each vertex, the first position being the position of the vertices moved by their first vector displacement from their current position, respectively; g. determining a second vector displacement for each vertex, the second vector displacement being the second scale factor times a second vector average, the second vector average being of the average of all of zero or more second neighbor vectors, each second neighbor vector being a vector from the vertex to each of the neighbor vertices, all vertices being at their respective first positions; h. determining a second position of each vertex, the second position being the position of the vertices moved by their respective second vector displacement from their first position, respectively; i. establishing the current position of each vertex as its respective second position; and j. if the number of times that steps e to i have been executed is less than the number of iterations, repeating steps d through i until the smoothness criteria is met.
Claim 20
Dependent Claim
371 words
A computer implemented method for smoothing a piece-wise linear shape comprising the steps of: a. determining a set of a plurality of vertices describing the shape; b. determining a neighborhood associated with each vertex, each neighborhood comprising a subset of zero or more neighbor vertices from the set of vertices such that the vertex is not included in its neighborhood; c. describing a pass-band curvature κ PB , a pass-band ripple δ PB , a stop-band curvature κ SB , and a stop-band ripple δ SB , such that 0<κ PB <κ SB , 0<δ PB , and 0<δ SB ; d. computing the first scale factor λ, the second scale factor μ, and the number of iterations N by solving the following system of equations and inequalities; ##EQU4## If this system admits more than one solution, the solution corresponding to the minimum value of N is chosen; e. determining a first vector displacement for each vertex, the first vector displacement being the first scale factor times a first vector average, the first vector average being the average of all of zero or more neighbor vectors, each neighbor vector being a vector from the vertex to each of its neighbor vertices, all the vertices being at a respective current position; f. determining a first position of each vertex, the first position being the position of the vertices moved by their first vector displacement from their current position, respectively; g. determining a second vector displacement for each vertex, the second vector displacement being the second scale factor times a second vector average, the second vector average being of the average of all of zero or more second neighbor vectors, each second neighbor vector being a vector from the vertex to each of the neighbor vertices, all vertices being at their respective first positions; h. determining a second position of each vertex, the second position being the position of the vertices moved by their respective second vector displacement from their first position, respectively; i. establishing the current position of each vertex as its respective second position; and j. if the number of times that steps e to i have been executed is less than the number of iterations, repeating steps e through j.
Claim 21
Dependent Claim
371 words
A computer implemented method for smoothing a piece-wise linear shape comprising the steps of: a. determining a set of a plurality of vertices describing the shape; b. determining a neighborhood associated with each vertex, each neighborhood comprising a subset of zero or more neighbor vertices from the set of vertices such that the vertex is not included in its neighborhood; c. describing a pass-band curvature κ PB , a pass-band ripple δ PB , a stop-band curvature κ SB , and a stop-band ripple δ SB , such that 0<κ PB <κ SB , 0<δ PB , and 0<δ SB ; d. computing the first scale factor λ, the second scale factor μ, and the number of iterations N by solving the following system of equations and inequalities; ##EQU4## If this system admits more than one solution, the solution corresponding to the minimum value of N is chosen; e. determining a first vector displacement for each vertex, the first vector displacement being the first scale factor times a first vector average, the first vector average being the average of all of zero or more neighbor vectors, each neighbor vector being a vector from the vertex to each of its neighbor vertices, all the vertices being at a respective current position; f. determining a first position of each vertex, the first position being the position of the vertices moved by their first vector displacement from their current position, respectively; g. determining a second vector displacement for each vertex, the second vector displacement being the second scale factor times a second vector average, the second vector average being of the average of all of zero or more second neighbor vectors, each second neighbor vector being a vector from the vertex to each of the neighbor vertices, all vertices being at their respective first positions; h. determining a second position of each vertex, the second position being the position of the vertices moved by their respective second vector displacement from their first position, respectively; i. establishing the current position of each vertex as its respective second position; and j. if the number of times that steps e to i have been executed is less than the number of iterations, repeating steps e through j.
Claim 22
Independent Claim
357 words
A system for smoothing a piece-wise linear shape comprising: A. a computer with an operating system, memory, and a central processing unit and graphical interface; B. an application program executed by the central processing unit for smoothing a piecewise linear shape represented on the computer as a set of vertices, comprising the computer implemented steps of: a. determining a neighborhood associated with each vertex, each neighborhood comprising a subset of zero or more neighbor vertices from the set of vertices such that the vertex is not included in its neighborhood; b. describing a first and a second scale factor of opposite signs, the negative scale factor being of greater magnitude than the positive scale factor; c. determining a first vector displacement for each vertex, the first vector displacement being the first scale factor times a first vector average, the first vector average being the average of all of zero or more neighbor vectors, each neighbor vector being a vector from the vertex to each of its neighbor vertices, all the vertices being at a respective current position; d. determining a first position of each vertex, the first position being the position of the vertices moved by their first vector displacement from their current position, respectively; e. determining a second vector displacement for each vertex, the second vector displacement being the second scale factor times a second vector average, the second vector average being of the average of all of zero or more second neighbor vectors, each second neighbor vector being a vector from the vertex to each of the neighbor vertices, all vertices being at their respective first positions; f. determining a second position of each vertex, the second position being the position of the vertices moved by their respective second vector displacement from their first position, respectively; g. establishing the current position of each vertex as its respective second position; and h. if the shape defined by the vertices in their second position does not meet a smoothness criteria, repeating steps c through h until the smoothness criteria is satisfied, whereby the shape with the vertices in the current position is rendered on the graphical interface.
Claim 23
Independent Claim
357 words
A system for smoothing a piece-wise linear shape comprising: A. a computer with an operating system, memory, and a central processing unit and graphical interface; B. an application program executed by the central processing unit for smoothing a piecewise linear shape represented on the computer as a set of vertices, comprising the computer implemented steps of: a. determining a neighborhood associated with each vertex, each neighborhood comprising a subset of zero or more neighbor vertices from the set of vertices such that the vertex is not included in its neighborhood; b. describing a first and a second scale factor of opposite signs, the negative scale factor being of greater magnitude than the positive scale factor; c. determining a first vector displacement for each vertex, the first vector displacement being the first scale factor times a first vector average, the first vector average being the average of all of zero or more neighbor vectors, each neighbor vector being a vector from the vertex to each of its neighbor vertices, all the vertices being at a respective current position; d. determining a first position of each vertex, the first position being the position of the vertices moved by their first vector displacement from their current position, respectively; e. determining a second vector displacement for each vertex, the second vector displacement being the second scale factor times a second vector average, the second vector average being of the average of all of zero or more second neighbor vectors, each second neighbor vector being a vector from the vertex to each of the neighbor vertices, all vertices being at their respective first positions; f. determining a second position of each vertex, the second position being the position of the vertices moved by their respective second vector displacement from their first position, respectively; g. establishing the current position of each vertex as its respective second position; and h. if the shape defined by the vertices in their second position does not meet a smoothness criteria, repeating steps c through h until the smoothness criteria is satisfied, whereby the shape with the vertices in the current position is rendered on the graphical interface.
References Cited (Backward Citations)
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-04-09 | 1999-10-09 | 2000-04-09 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-04-09 | 2003-10-09 | 2004-04-09 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-04-09 | 2007-10-09 | 2008-04-09 | $7700.00 | Window Closed / Lapsed |