US5471573A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Optimized scan conversion of outlines for generating raster images
Assignee: Apple Inc
•
Filing: 1993-09-27
•
Granted: 1995-11-28
•
Expires: 2013-09-27
Abstract
Abstract An arbitrary curve formulated as a quadratic B-spline with a plurality of second order Bezier curves is approximated. Applying a forward differencing to the parametric equation of the second degree Bezier curves, a second order difference coefficient is derived. By defining the error from approximating the curve with forward differencing as the distance between the approximated point on the curve and the midpoint between the end points of the curve, the second order differential coefficient is directly proportional to the error. Additionally, the error resulting from increasing the number of parametric intervals for the forward differencing is proportional to the original error. It follows from the relationship established for the second order differential coefficient, the number of parametric intervals, and the error threshold that the user specifies, the number of parametric intervals is determined. Knowing the number of required forward differencing steps allows the user to minimize the scan conversion overhead. The formulation of integer-based parametric intervals for the forward differencing obviates any multiplication or division instructions in approximating an arbitrary curve. Thus overall performance of the graphic display system is enhanced.
Inventors
- 👤 Sampo Kaasila
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-05 20:56
CPC Classifications
G; G06; G06T; G06T11/00; G06T11/20; G06T11/23
Claims Analysis
Total Claims: 37
Claim 1
Independent Claim
185 words
A method for minimizing scan conversion processing in displaying an outline image on a display device from a resulting bitmap of a graphic display system, comprising the steps of: approximating said outline image with recursive subdivision to represent said outline image as a plurality of segments; fitting each segment of said plurality of segments of said outline image with forward differencing within an error threshold, said forward differencing producing a plurality of intervals, wherein said error threshold includes a distance between a point on each of said plurality of intervals and a point representing said outline image; comparing said error threshold with a predetermined maximum error threshold, said maximum error threshold relating to a size of said resulting bitmap; determining an optimum number of said plurality of intervals required to ensure that said error threshold is less than said maximum error threshold; and generating said optimum number of said plurality of intervals to store data representative of pixels in a refresh buffer to thereby provide said resulting bitmap to activate pixels on said display device according to said resulting bitmap of said graphic display system.
Claim 2
Independent Claim
185 words
A method for minimizing scan conversion processing in displaying an outline image on a display device from a resulting bitmap of a graphic display system, comprising the steps of: approximating said outline image with recursive subdivision to represent said outline image as a plurality of segments; fitting each segment of said plurality of segments of said outline image with forward differencing within an error threshold, said forward differencing producing a plurality of intervals, wherein said error threshold includes a distance between a point on each of said plurality of intervals and a point representing said outline image; comparing said error threshold with a predetermined maximum error threshold, said maximum error threshold relating to a size of said resulting bitmap; determining an optimum number of said plurality of intervals required to ensure that said error threshold is less than said maximum error threshold; and generating said optimum number of said plurality of intervals to store data representative of pixels in a refresh buffer to thereby provide said resulting bitmap to activate pixels on said display device according to said resulting bitmap of said graphic display system.
Claim 3
Dependent Claim
25 words
The method as defined by claim 1, wherein said outline image is defined parametrically, said outline image further being described by second order Bezier curves.
Claim 4
Dependent Claim
33 words
The method as defined by claim 1, wherein said recursive subdivision switches to said forward differencing when said each segment of said plurality of segments is within said size of said resulting bitmap.
Claim 5
Dependent Claim
26 words
The method as defined by claim 1, wherein said error threshold is directly proportional to a second order forward differencing coefficient of said forward differencing method.
Claim 6
Dependent Claim
26 words
The method as defined by claim 4, wherein said second order forward differencing coefficient is directly proportional to the optimum number of said plurality of intervals.
Claim 7
Dependent Claim
31 words
The method as defined by claim 4, wherein said error threshold is directly proportional to a new error threshold, said new error threshold resulting from increasing said number of said intervals.
Claim 8
Independent Claim
218 words
A method for minimizing scan conversion processing in displaying an outline image on a display device from a refresh buffer containing a resulting bitmap of a graphic display system, comprising the steps of: approximating said outline image with recursive subdivision to represent said outline image as a plurality of segments using a reformulated equation, wherein said reformulated equation is expressed in terms of a number of intervals; fitting each segment of said plurality of segments of said outline image with forward differencing within an error threshold, said forward differencing producing a said number of said intervals, wherein said error threshold includes a distance between a point on each of said number of intervals and a point representing said outline image; comparing said error threshold with a predetermined maximum error threshold, said maximum error threshold relating to a size of said resulting bitmap; determining an optimum number of said number of said intervals required to ensure that said error threshold is less than said maximum error threshold; and generating said optimum number of said number of said intervals to store data representative of said resulting bitmap in said refresh buffer of said graphic display system, said refresh buffer thereby being used to activate pixels on said display of said system from said resulting bitmap of said graphic display system.
Claim 9
Independent Claim
218 words
A method for minimizing scan conversion processing in displaying an outline image on a display device from a refresh buffer containing a resulting bitmap of a graphic display system, comprising the steps of: approximating said outline image with recursive subdivision to represent said outline image as a plurality of segments using a reformulated equation, wherein said reformulated equation is expressed in terms of a number of intervals; fitting each segment of said plurality of segments of said outline image with forward differencing within an error threshold, said forward differencing producing a said number of said intervals, wherein said error threshold includes a distance between a point on each of said number of intervals and a point representing said outline image; comparing said error threshold with a predetermined maximum error threshold, said maximum error threshold relating to a size of said resulting bitmap; determining an optimum number of said number of said intervals required to ensure that said error threshold is less than said maximum error threshold; and generating said optimum number of said number of said intervals to store data representative of said resulting bitmap in said refresh buffer of said graphic display system, said refresh buffer thereby being used to activate pixels on said display of said system from said resulting bitmap of said graphic display system.
Claim 10
Dependent Claim
24 words
The method as defined by claim 7, wherein said outline image is defined parametrically, said outline image further being described by second Bezier curves.
Claim 11
Dependent Claim
72 words
The method as defined by claim 7, wherein said recursive subdivision switches to said forward differencing when the reformulated equation representing each of said plurality of segments is equal to or greater than the square of said, number of said intervals of a parametric equation representing said each segment of said plurality of segments and when said each segment of said plurality of segments is within said size of said resulting bitmap.
Claim 12
Dependent Claim
69 words
The method as defined by claim 7, wherein said forward differencing fits a plurality of straight lines to form an outline of said outline image, said plurality of straight lines adjoining each other, said outline having two end points, said outline further having a common control point not on said outline and which comprises an intersection mint of the tangent vectors associated with said end points of said outline.
Claim 13
Dependent Claim
68 words
The method as defined by claim 10, wherein said error threshold comprises a distance on said resulting bitmap between a midpoint of a first line segment joining said end points of said outline image and a point on said outline which is the intersection of said outline and a second line segment joining midpoints of segments joining said end points of said outline with said common control point.
Claim 14
Dependent Claim
31 words
The method as defined by claim 11, wherein said error threshold is directly proportional to a new error threshold, said new error threshold resulting from increasing said number of said intervals.
Claim 15
Dependent Claim
26 words
The method as defined by claim 7, wherein said error threshold is directly proportional to a second order forward differencing coefficient of said forward differencing method.
Claim 16
Dependent Claim
26 words
The method as defined by claim 13, wherein said second order forward differencing coefficient is directly proportional to the optimum number of said plurality of intervals.
Claim 17
Independent Claim
168 words
A method for minimizing the scan conversion processing to display an outline of an image on a resulting bitmap of a graphic display system, said graphic display system including a display, and a refresh buffer for storing said resulting bitmap and controlling said display, comprising the steps of: determining an optimum number of intervals required to satisfy an error threshold for performing forward differencing to approximate said outline wherein said error threshold includes a distance between a point on each of said plurality of intervals and a point representing said outline image; approximating said outline with recursive subdivision to represent said outline image as a plurality of segments; fitting each segment of said plurality of segments of said outline with forward differencing, said forward differencing producing said optimum number of intervals; and using said optimum number of intervals to store data representative of said resulting bitmap in said refresh buffer in order to activate pixels on said display according to said resulting bitmap of said graphic display system.
Claim 18
Independent Claim
168 words
A method for minimizing the scan conversion processing to display an outline of an image on a resulting bitmap of a graphic display system, said graphic display system including a display, and a refresh buffer for storing said resulting bitmap and controlling said display, comprising the steps of: determining an optimum number of intervals required to satisfy an error threshold for performing forward differencing to approximate said outline wherein said error threshold includes a distance between a point on each of said plurality of intervals and a point representing said outline image; approximating said outline with recursive subdivision to represent said outline image as a plurality of segments; fitting each segment of said plurality of segments of said outline with forward differencing, said forward differencing producing said optimum number of intervals; and using said optimum number of intervals to store data representative of said resulting bitmap in said refresh buffer in order to activate pixels on said display according to said resulting bitmap of said graphic display system.
Claim 19
Dependent Claim
18 words
The method as defined by claim 15, wherein said outline is defined parametrically by second order Bezier curves.
Claim 20
Dependent Claim
31 words
The method as defined by claim 15, wherein said recursive subdivision switches to said forward differencing when said each segment of said plurality of segments is within a second error threshold.
Claim 21
Dependent Claim
24 words
The method as defined by claim 17, wherein said second error threshold is proportional to second order forward differencing coefficients of said forward differencing.
Claim 22
Dependent Claim
25 words
The method as defined by claim 18, wherein said second order forward differencing coefficients are proportional to the optimum number of said plurality of intervals.
Claim 23
Dependent Claim
31 words
The method as defined by claim 18, wherein said error threshold is proportional to a third error threshold, said third error threshold resulting from increasing said optimum number of said intervals.
Claim 24
Independent Claim
159 words
A method of displaying an outline of an image on a resulting bitmap stored in a refresh buffer and used for controlling a display of a graphic display system which minimizes scan conversion processing comprising the steps of: determining a first number of segments required to approximate said outline using recursive subdivision in order for forward differencing to converge upon a result within a first error threshold, wherein said first error threshold includes a distance between a point on each of said plurality of intervals and a point representing said outline image; approximating said outline with recursive subdivision to represent said outline as said first number of segments; and fitting each of said first number of segments of said outline with forward differencing in order to store data representative of said resulting bitmap in said refresh buffer, said resulting bitmap in said refresh buffer then being used to display said outline on said display of said graphic display system.
Claim 25
Independent Claim
159 words
A method of displaying an outline of an image on a resulting bitmap stored in a refresh buffer and used for controlling a display of a graphic display system which minimizes scan conversion processing comprising the steps of: determining a first number of segments required to approximate said outline using recursive subdivision in order for forward differencing to converge upon a result within a first error threshold, wherein said first error threshold includes a distance between a point on each of said plurality of intervals and a point representing said outline image; approximating said outline with recursive subdivision to represent said outline as said first number of segments; and fitting each of said first number of segments of said outline with forward differencing in order to store data representative of said resulting bitmap in said refresh buffer, said resulting bitmap in said refresh buffer then being used to display said outline on said display of said graphic display system.
Claim 26
Dependent Claim
18 words
The method as defined by claim 21, wherein said outline is defined parametrically by second order Bezier curves.
Claim 27
Independent Claim
187 words
A method for minimizing scan conversion processing in displaying an outline image on a display device from a resulting bitmap of a graphic display system, comprising the steps of: approximating said outline image with recursive subdivision to represent said outline image as a plurality of segments wherein said recursive subdivision switches to forward differencing when said each segment of said plurality of segments is within a size of said resulting bitmap; fitting each segment of said plurality of segments of said outline image with said forward differencing within an error threshold, said forward differencing producing a plurality of intervals; comparing said error threshold with a predetermined maximum error threshold, said maximum error threshold relating to a size of said resulting bitmap; determining an optimum number of said plurality of intervals required to ensure that said error threshold is less than said maximum error threshold; and generating said optimum number of said plurality of intervals to store data representative of pixels in a refresh buffer to thereby provide said resulting bitmap to activate pixels on said display device according to said resulting bitmap of said graphic display system.
Claim 28
Independent Claim
187 words
A method for minimizing scan conversion processing in displaying an outline image on a display device from a resulting bitmap of a graphic display system, comprising the steps of: approximating said outline image with recursive subdivision to represent said outline image as a plurality of segments wherein said recursive subdivision switches to forward differencing when said each segment of said plurality of segments is within a size of said resulting bitmap; fitting each segment of said plurality of segments of said outline image with said forward differencing within an error threshold, said forward differencing producing a plurality of intervals; comparing said error threshold with a predetermined maximum error threshold, said maximum error threshold relating to a size of said resulting bitmap; determining an optimum number of said plurality of intervals required to ensure that said error threshold is less than said maximum error threshold; and generating said optimum number of said plurality of intervals to store data representative of pixels in a refresh buffer to thereby provide said resulting bitmap to activate pixels on said display device according to said resulting bitmap of said graphic display system.
Claim 29
Independent Claim
177 words
A method for minimizing scan conversion processing in displaying an outline image on a display device from a resulting bitmap of a graphic display system, comprising the steps of: approximating said outline image with recursive subdivision to represent said outline image as a plurality of segments; fitting each segment of said plurality of segments of said outline image with forward differencing within an error threshold, said forward differencing producing a plurality of intervals, wherein said error threshold is directly proportional to a second order coefficient of said forward differencing; comparing said error threshold with a predetermined maximum error threshold, said maximum error threshold relating to a size of said resulting bitmap; determining an optimum number of said plurality of intervals required to ensure that said error threshold is less than said maximum error threshold; and generating said optimum number of said plurality of intervals to store data representative of pixels in a refresh buffer to thereby provide said resulting bitmap to activate pixels on said display device according to said resulting bitmap of said graphic display system.
Claim 30
Independent Claim
177 words
A method for minimizing scan conversion processing in displaying an outline image on a display device from a resulting bitmap of a graphic display system, comprising the steps of: approximating said outline image with recursive subdivision to represent said outline image as a plurality of segments; fitting each segment of said plurality of segments of said outline image with forward differencing within an error threshold, said forward differencing producing a plurality of intervals, wherein said error threshold is directly proportional to a second order coefficient of said forward differencing; comparing said error threshold with a predetermined maximum error threshold, said maximum error threshold relating to a size of said resulting bitmap; determining an optimum number of said plurality of intervals required to ensure that said error threshold is less than said maximum error threshold; and generating said optimum number of said plurality of intervals to store data representative of pixels in a refresh buffer to thereby provide said resulting bitmap to activate pixels on said display device according to said resulting bitmap of said graphic display system.
Claim 31
Dependent Claim
26 words
The method as defined by claim 24, wherein said second order forward differencing coefficient is directly proportional to the optimum number of said plurality of intervals.
Claim 32
Dependent Claim
31 words
The method as defined by claim 24, wherein said error threshold is directly proportional to a new error threshold, said new error threshold resulting from increasing said number of said intervals.
Claim 33
Independent Claim
169 words
A method for minimizing the scan conversion processing to display an outline of an image on a resulting bitmap of a graphic display system, said graphic display system including a display, and a refresh buffer for storing said resulting bitmap and controlling said display, comprising the steps of: determining an optimum number of intervals required to satisfy an error threshold for performing forward differencing to approximate said outline; approximating said outline with recursive subdivision to represent said outline image as a plurality of segments, wherein said recursive subdivision switches to said forward differencing when said each segment of said plurality of segments is within a second error threshold; fitting each segment of said plurality of segments of said outline with said forward differencing, said forward differencing producing said optimum number of intervals; and using said optimum number of intervals to store data representative of said resulting bitmap in said refresh buffer in order to activate pixels on said display according to said resulting bitmap of said graphic display system.
Claim 34
Independent Claim
169 words
A method for minimizing the scan conversion processing to display an outline of an image on a resulting bitmap of a graphic display system, said graphic display system including a display, and a refresh buffer for storing said resulting bitmap and controlling said display, comprising the steps of: determining an optimum number of intervals required to satisfy an error threshold for performing forward differencing to approximate said outline; approximating said outline with recursive subdivision to represent said outline image as a plurality of segments, wherein said recursive subdivision switches to said forward differencing when said each segment of said plurality of segments is within a second error threshold; fitting each segment of said plurality of segments of said outline with said forward differencing, said forward differencing producing said optimum number of intervals; and using said optimum number of intervals to store data representative of said resulting bitmap in said refresh buffer in order to activate pixels on said display according to said resulting bitmap of said graphic display system.
Claim 35
Dependent Claim
22 words
The method of claim 27 wherein said second error threshold is proportional to second order forward differencing coefficients of said forward differencing.
Claim 36
Dependent Claim
23 words
The method of claim 28, wherein said second order forward differencing coefficients are proportional to the optimum number of said plurality of intervals.
Claim 37
Dependent Claim
31 words
The method as defined by claim 27, wherein said error threshold is proportional to a third error threshold, said third error threshold resulting from increasing said optimum number of said intervals.
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) | 1998-11-27 | 1999-05-29 | 1999-11-28 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2002-11-27 | 2003-05-29 | 2003-11-28 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2006-11-27 | 2007-05-29 | 2007-11-28 | $7700.00 | Window Closed / Lapsed |