US5726896A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and system for spline interpolation, and their use in CNC
Assignee: University of Utah
•
Filing: 1996-08-29
•
Granted: 1998-03-10
•
Expires: 2016-08-29
Abstract
Abstract An iterative spline interpolation method for a numerically-controlled machine tool device is disclosed. The non-uniform rational B-spline (NURBS) curve inputted to the numerically-controlled machine tool is interpolated with a constant step size providing the ability to maintain a controlled velocity to within a specified tolerance. In addition, the distance left to travel on the curve is obtained by a unique spline node-based approximation method providing accurate acceleration and deceleration control. The rational spline interpolation method provides significant reduction in the amount of data required to produce smoothly machined pieces while providing accurate machining of conic sections not possible by previous spline interpolation methods.
Inventors
- 👤 Ji Jia
- 👤 Elaine Cohen
- 👤 Samuel H. Drake
- 👤 Russell D. Fish
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 09:07
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/20; G06T11/23; G05; G05B; G05B2219/00; G05B2219/30; G05B2219/34; G05B2219/34141
Claims Analysis
Total Claims: 20
Claim 1
Independent Claim
314 words
A method for controlling the movement of a cutting tool on a numerically-controlled device, running on a digital computer controlling said cutting tool, said method comprising: inputting to said digital computer: a plurality of codes defining a NURBS curve through which said cutter head will travel, said codes comprising: codes to specify an initial position of said cutting tool, codes to specify the order of said NURBS curve, codes to specify the number of control points in the control polygon of said NURBS curve, codes to specify the knot vector of said NURBS curve, and codes to define other positions defining said control polygon of said NURBS curve through which said cutting tool will travel; and a code specifying a desired feed rate; determining a curve length distance from said codes defining said NURBS curve through which said cutting tool will travel; determining an initial curve length step size from said desired feed rate and a value which represents the amount of time required to compute one step; determining a parametric step size with a node-based approximation of the derivative at said initial position on said NURBS curve through which said cutting tool will travel; determining distance traveled in step to be the euclidean distance traveled during said parametric step size; determining curve length difference to be the difference between said initial curve length step size and said distance traveled in step; modifying said parametric step sized based on an error measure of said curve length difference; computing a distance left for said cutting tool to travel for said cutting tool; determining an output position by evaluation of the parametric equations defined by said order, knot vector, and control points for said NURBS curve where a next parameter t is the sum of the current value of t and said parametric step size; and moving said cutting tool in accordance with said output positions.
Claim 2
Independent Claim
314 words
A method for controlling the movement of a cutting tool on a numerically-controlled device, running on a digital computer controlling said cutting tool, said method comprising: inputting to said digital computer: a plurality of codes defining a NURBS curve through which said cutter head will travel, said codes comprising: codes to specify an initial position of said cutting tool, codes to specify the order of said NURBS curve, codes to specify the number of control points in the control polygon of said NURBS curve, codes to specify the knot vector of said NURBS curve, and codes to define other positions defining said control polygon of said NURBS curve through which said cutting tool will travel; and a code specifying a desired feed rate; determining a curve length distance from said codes defining said NURBS curve through which said cutting tool will travel; determining an initial curve length step size from said desired feed rate and a value which represents the amount of time required to compute one step; determining a parametric step size with a node-based approximation of the derivative at said initial position on said NURBS curve through which said cutting tool will travel; determining distance traveled in step to be the euclidean distance traveled during said parametric step size; determining curve length difference to be the difference between said initial curve length step size and said distance traveled in step; modifying said parametric step sized based on an error measure of said curve length difference; computing a distance left for said cutting tool to travel for said cutting tool; determining an output position by evaluation of the parametric equations defined by said order, knot vector, and control points for said NURBS curve where a next parameter t is the sum of the current value of t and said parametric step size; and moving said cutting tool in accordance with said output positions.
Claim 3
Dependent Claim
45 words
The method of claim 1, wherein modification of said parametric step size based on an error measure of said curve length difference uses a bisection method where a previous substep size is multiplied by a substep size factor, α, to obtain a next substep size.
Claim 4
Dependent Claim
16 words
The method of claim 2, wherein said substep size factor, α, is equal to one half.
Claim 5
Dependent Claim
43 words
The method of claim 1, wherein said curve length distance is approximated by a linear combination of the node points and said control points of said NURBS curve weighted by said current parametric value t and the parametric values of said node points.
Claim 6
Dependent Claim
59 words
The method of claim 1, wherein said curve length difference is decreased by an acceleration rate if said distance required to stop said cutting tool is less than the distance left for said cutting tool to travel, and said curve length difference is increased by said acceleration rate if the current velocity is less than said desired feed rate.
Claim 7
Dependent Claim
11 words
A digital computer, programmed to perform the method of claim 1.
Claim 8
Dependent Claim
17 words
The digital computer of claim 6, where said digital computer is a component of a numerically-controlled device.
Claim 9
Dependent Claim
13 words
A computer-readable medium, storing a program that performs the method of claim 1.
Claim 10
Dependent Claim
14 words
The computer-readable medium of claim 8, where said computer-readable medium is a floppy disk.
Claim 11
Independent Claim
291 words
A method for controlling the movement of a cutting tool having a cutter head on a numerically-controlled device, running on a digital computer controlling said cutting tool, said method comprising: inputting to said digital computer: a plurality of codes defining a cubic Bezier curve through which the cutter head will travel, said codes comprising: codes to specify an initial position of said cutting tool, and codes to define the three other positions defining said control polygon of said cubic Bezier curve through which said cutting tool will travel; and a code specifying a desired feed rate; determining a curve length distance from said codes defining said cubic Bezier curve through which said cutting tool will travel; determining an initial curve length step size from said desired feed rate and a value which represents the amount of time required to compute one step; determining a parametric step size with a node-based approximation of the derivative at said initial position on said cubic Bezier curve through which said cutting tool will travel; determining distance traveled in step to be the euclidean distance traveled during said parametric step size; determining curve length difference to be the difference between said initial curve length step size and said distance traveled in step; modifying said parametric step sized based on an error measure of said curve length difference; computing a distance left for said cutting tool to travel based on deceleration parameters for said cutting tool; determining an output position by evaluation of the parametric equations of said cubic Bezier curve utilizing the Bernstein basis functions, where a next parameter t is the sum of the current value of t and said parametric step size; and moving said cutting tool in accordance with said computed output positions.
Claim 12
Independent Claim
291 words
A method for controlling the movement of a cutting tool having a cutter head on a numerically-controlled device, running on a digital computer controlling said cutting tool, said method comprising: inputting to said digital computer: a plurality of codes defining a cubic Bezier curve through which the cutter head will travel, said codes comprising: codes to specify an initial position of said cutting tool, and codes to define the three other positions defining said control polygon of said cubic Bezier curve through which said cutting tool will travel; and a code specifying a desired feed rate; determining a curve length distance from said codes defining said cubic Bezier curve through which said cutting tool will travel; determining an initial curve length step size from said desired feed rate and a value which represents the amount of time required to compute one step; determining a parametric step size with a node-based approximation of the derivative at said initial position on said cubic Bezier curve through which said cutting tool will travel; determining distance traveled in step to be the euclidean distance traveled during said parametric step size; determining curve length difference to be the difference between said initial curve length step size and said distance traveled in step; modifying said parametric step sized based on an error measure of said curve length difference; computing a distance left for said cutting tool to travel based on deceleration parameters for said cutting tool; determining an output position by evaluation of the parametric equations of said cubic Bezier curve utilizing the Bernstein basis functions, where a next parameter t is the sum of the current value of t and said parametric step size; and moving said cutting tool in accordance with said computed output positions.
Claim 13
Dependent Claim
45 words
The method of claim 10, wherein modification of said parametric step size based on said error measure of said curve length difference uses a bisection method where a previous substep size is multiplied by a substep size factor, α, to obtain a next substep size.
Claim 14
Dependent Claim
16 words
The method of claim 11, wherein said substep size factor, α, is equal to one half.
Claim 15
Dependent Claim
42 words
The method of claim 10, wherein said curve length is approximated by a linear combination of said node and said control points of said cubic Bezier curve weighted by said current parametric value t and said parametric values of said node points.
Claim 16
Dependent Claim
59 words
The method of claim 10, wherein said curve length difference is decreased by an acceleration rate if said distance required to stop said cutting tool is less than said distance left for said cutting tool to travel, and said curve length difference is increased by said acceleration rate if the current velocity is less than said desired feed rate.
Claim 17
Dependent Claim
11 words
A digital computer, programmed to perform the method of claim 10.
Claim 18
Dependent Claim
17 words
The digital computer of claim 15, where said digital computer is a component of a numerically-controlled device.
Claim 19
Dependent Claim
13 words
A computer-readable medium, storing a program that performs the method of claim 10.
Claim 20
Dependent Claim
14 words
The computer-readable medium of claim 17, where said computer-readable medium is a floppy disk.
References Cited (Backward Citations)
US3609319A
Cited
US3727191A
Cited
US4031369A
Cited
US4086522A
Cited
US4453221A
Cited
US5014230A
Cited
US4794540A
Cited
US5140236A
Cited
US5028855A
Cited
US5119309A
Cited
US5227978A
Cited
US5321623A
Cited
US5412300A
Cited
US5500927A
Cited
US5510995A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2001-03-09 | 2001-09-08 | 2002-03-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2005-03-09 | 2005-09-08 | 2006-03-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2009-03-09 | 2009-09-08 | 2010-03-10 | $7700.00 | Window Closed / Lapsed |