US5638503A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method and apparatus for generating bitmaps from outlines containing bezier curves
Assignee: Adobe Inc
•
Filing: 1994-07-07
•
Granted: 1997-06-10
•
Expires: 2014-07-07
Abstract
Abstract A rendering device for converting input information into a bit map including a Bezier subdivision processor responsive to Bezier curve information describing a Bezier curve of an image. The Bezier subdivision processor performs at least one subdivision on the Bezier curve if the Bezier curve is greater than a desired resolution of a bit map to produce subdivided Bezier curves until all subdivided Bezier curves are at about the resolution of the bit map. The Bezier subdivision processor produces cross information from each Bezier curve which makes one crossing of a grid having the resolution of the bit map. The rendering device also includes a digital processor responsive to the cross information and operative to produce a bit map of the image from the cross information. A method for producing cross positions of Bezier curves with a grid of the present invention includes receiving a Bezier curve, sequentially subdividing the Bezier curve into a plurality of subdivided Bezier curves until each Bezier curve crosses less than a plurality of times with cell boundaries of a grid of a desired resolution, and developing the Cartesian coordinates and direction of each of the crosses of a Bezier curve with a boundary.
Inventors
- 👤 Jeffrey H. Hoel
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-31 01:23
CPC Classifications
G; G06; G06F; G06F7/00; G06F7/76; G06F7/78; G06F7/785; G06F5/00; G06F5/06; G06F5/10; G06T; G06T11/00; G06T11/20; G06T11/23
Claims Analysis
Total Claims: 50
Claim 1
Independent Claim
153 words
A system for generating a multi-dimensional image on an output device from an image description comprising: a digital processor which receives an image description describing a multi-dimensional image and produces image rendering information from said image description, said image rendering information being associated with Bezier curve information describing at least one Bezier curve of said image; a rendering device coupled to said digital processor to develop image information, said rendering device being capable of performing at least one subdivision on said Bezier curve of said image to produce a plurality of subdivided Bezier curves until all subdivided Bezier curves cross no more than one boundary between cells of a pixel grid, said rendering device developing said image information from said image rendering information, said associated Bezier curve information and said subdivided Bezier curves; and the output device being coupled to said rendering device to create said multi-dimensional image derived from said image information.
Claim 2
Independent Claim
153 words
A system for generating a multi-dimensional image on an output device from an image description comprising: a digital processor which receives an image description describing a multi-dimensional image and produces image rendering information from said image description, said image rendering information being associated with Bezier curve information describing at least one Bezier curve of said image; a rendering device coupled to said digital processor to develop image information, said rendering device being capable of performing at least one subdivision on said Bezier curve of said image to produce a plurality of subdivided Bezier curves until all subdivided Bezier curves cross no more than one boundary between cells of a pixel grid, said rendering device developing said image information from said image rendering information, said associated Bezier curve information and said subdivided Bezier curves; and the output device being coupled to said rendering device to create said multi-dimensional image derived from said image information.
Claim 3
Dependent Claim
13 words
A system as recited in claim 1 wherein said multi-dimensional image is 2-dimensional.
Claim 4
Dependent Claim
22 words
A system as recited in claim 2 wherein said image rendering information includes a reference to information specified in an outline format.
Claim 5
Dependent Claim
35 words
A system as recited in claim 3 wherein said multi-dimensional image is an image including at least one character, and wherein said output device is one of a 2-dimensional display, a printer, and a plotter.
Claim 6
Dependent Claim
41 words
A system as recited in claim 1 wherein said rendering device includes a Bezier subdivision processor for (1) subdividing said Bezier curves and (2) identifying crosses for each of said Bezier curves, said crosses being used to develop said image information.
Claim 7
Dependent Claim
24 words
A system as recited in claim 5 wherein said rendering device includes a microcontroller for providing said Bezier curves to said Bezier subdivision processor.
Claim 8
Dependent Claim
39 words
A system as recited in claim 1 wherein said digital processor creates a pixel map using said image information and inputs said pixel map to said output device, said output device creating said desired image from said pixel map.
Claim 9
Dependent Claim
107 words
A rendering device for converting input information to a bit map comprising: a Bezier subdivision processor which receives Bezier curve information describing a Bezier curve of an image, said Bezier subdivision processor performing at least one subdivision on said Bezier curve to produce subdivided Bezier curves until all subdivided Bezier curves cross no more than one boundary between cells of a pixel grid, said Bezier subdivision processor producing cross information from each of said Bezier curves which makes one crossing of a grid having said resolution; and a digital processor which receives said cross information and produces a bit map of said image from said cross information.
Claim 10
Dependent Claim
107 words
A rendering device for converting input information to a bit map comprising: a Bezier subdivision processor which receives Bezier curve information describing a Bezier curve of an image, said Bezier subdivision processor performing at least one subdivision on said Bezier curve to produce subdivided Bezier curves until all subdivided Bezier curves cross no more than one boundary between cells of a pixel grid, said Bezier subdivision processor producing cross information from each of said Bezier curves which makes one crossing of a grid having said resolution; and a digital processor which receives said cross information and produces a bit map of said image from said cross information.
Claim 11
Dependent Claim
22 words
A rendering device as recited in claim 8 wherein said Bezier subdivision processor includes a memory unit for storing subdivided Bezier curves.
Claim 12
Dependent Claim
23 words
A rendering device as recited in claim 9 wherein said memory unit includes a stack memory structure for storing said subdivided Bezier curves.
Claim 13
Dependent Claim
22 words
A rendering device as recited in claim 10 wherein said memory unit includes a FIFO memory structure for storing received Bezier curves.
Claim 14
Dependent Claim
32 words
A rendering device as recited in claim 9 wherein said Bezier subdivision processor includes a boundary crossings detector for determining the number of crossings of said grid made by said Bezier curve.
Claim 15
Dependent Claim
34 words
A rendering device as recited in claim 12 wherein said Bezier subdivision processor includes a cross formatter for providing a cross specification when a Bezier curve is found to cross said grid only once.
Claim 16
Dependent Claim
41 words
A rendering device as recited in claim 8 wherein said Bezier subdivision processor includes a control unit operative to control the operation of said Bezier subdivision processor to receive said Bezier curve information, perform said subdivision, and provide said cross information.
Claim 17
Dependent Claim
37 words
A rendering device as recited in claim 8 wherein said Bezier subdivision processor includes an input register operative to store said Bezier curve information until sufficient Bezier curve information to describe said Bezier curve has been received.
Claim 18
Dependent Claim
57 words
A Bezier subdivision processor comprising: a boundary crossings detector for detecting crossings of Bezier curves with a grid having cells of a predetermined resolution, said grid defining the boundaries of said cells; and a Bezier subdivision unit producing a plurality of subdivided Bezier curves for each Bezier curve that has a plurality of crossings of cell boundaries.
Claim 19
Dependent Claim
57 words
A Bezier subdivision processor comprising: a boundary crossings detector for detecting crossings of Bezier curves with a grid having cells of a predetermined resolution, said grid defining the boundaries of said cells; and a Bezier subdivision unit producing a plurality of subdivided Bezier curves for each Bezier curve that has a plurality of crossings of cell boundaries.
Claim 20
Dependent Claim
62 words
A Bezier subdivision processor as recited in claim 16 further comprising: a cross formatter for producing cross information for each Bezier curve having a single crossing of a cell boundary; and a register having inputs coupled to said Bezier subdivision unit and said memory unit, and having outputs coupled to said Bezier subdivision unit, said boundary crossings detector, and said cross formatter.
Claim 21
Dependent Claim
51 words
A Bezier subdivision processor as recited in claim 17 wherein said memory unit comprises a stack, and wherein said subdivided Bezier curves are pushed onto said stack and popped from said stack such that said Bezier subdivision unit recursively subdivides said Bezier curves on said stack until said stack is empty.
Claim 22
Dependent Claim
25 words
A Bezier subdivision processor as recited in claim 18 further comprising a control unit coupled to said input register, said memory unit, and said register.
Claim 23
Dependent Claim
22 words
A Bezier subdivision processor as recited in claim 18 wherein said memory unit further includes a FIFO for storing received Bezier curves.
Claim 24
Dependent Claim
43 words
A Bezier subdivision processor as recited in claim 20 wherein said FIFO and said stack are contiguous in said memory unit such that when said stack is empty and a curve is popped from said stack, a curve is read from said FIFO.
Claim 25
Dependent Claim
35 words
A Bezier subdivision processor as recited in claim 20 wherein said memory unit includes: read/write memory; a FIFO-in up counter coupled to said read/write memory; and a stack up/down counter coupled to said read/write memory.
Claim 26
Dependent Claim
19 words
A Bezier subdivision processor as recited in claim 22 wherein said memory unit further comprises a FIFO full output.
Claim 27
Dependent Claim
54 words
A Bezier subdivision processor as recited in claim 23 wherein said memory unit further comprises: a FIFO-out up counter; and logic having inputs coupled to said FIFO-in up counter, said FIFO-out up counter, and said stack up/down counter, said logic having said FIFO full output, a FIFO empty output, and a stack empty output.
Claim 28
Dependent Claim
30 words
A Bezier subdivision processor as recited in claim 18 wherein said crossings detector includes combinatorial logic for determining whether a Bezier curve makes at least one crossing of cell boundaries.
Claim 29
Dependent Claim
36 words
A Bezier subdivision processor as recited in claim 18 wherein said crossings detector detects whether zero, one, or a plurality of said boundaries are crossed by a line segment connecting the endpoints of said Bezier curve.
Claim 30
Dependent Claim
57 words
A Bezier subdivision processor as recited in claim 26 wherein said crossings detector includes a horizontal comparing portion for comparing horizontal coordinates of said endpoints of said Bezier curve and a vertical comparing portion for comparing the vertical coordinates of said endpoints to determine whether said Bezier curve crosses zero, one, or a plurality of said boundaries.
Claim 31
Dependent Claim
57 words
A Bezier subdivision processor as recited in claim 26 wherein said crossings detector includes a tree of logic blocks which processes the coordinates of a first endpoint of said Bezier curve and corresponding coordinates of a second endpoint of said Bezier curve to determine whether said line segment crosses zero, one, or a plurality of said boundaries.
Claim 32
Dependent Claim
43 words
A Bezier subdivision processor as recited in claim 18 wherein said Bezier curve includes a plurality of control points, and wherein said crossings detector detects whether zero, one, or a plurality of said boundaries are crossed by line segments connecting said control points.
Claim 33
Dependent Claim
47 words
A Bezier subdivision processor as recited in claim 29 wherein said control points have an order, and wherein said crossings detector detects whether zero, one, or a plurality of said boundaries are crossed by the piecewise linear path connecting said plurality of control points in said order.
Claim 34
Dependent Claim
23 words
A Bezier subdivision processor as recited in claim 18 wherein said Bezier subdivision unit includes a single-axis subdivision unit for each coordinate axis.
Claim 35
Dependent Claim
39 words
A Bezier subdivision processor as recited in claim 31 wherein each of said single-axis subdivision units includes a plurality of averagers combinatorially connected to produce coordinates of the control points of a subdivided Bezier curve in said coordinate axis.
Claim 36
Dependent Claim
31 words
A Bezier subdivision processor as recited in claim 32 wherein said Bezier subdivision unit further includes means for generating carry-in functions for said averagers to preclude the possibility of degenerate subdivision.
Claim 37
Dependent Claim
35 words
A Bezier subdivision processor as recited in claim 18 wherein said cross formatter includes a plurality of multiplexers combined to receive information from said crossings detector and to generate coordinates included in said cross information.
Claim 38
Independent Claim
81 words
A method for determining crossings of Bezier curves with a grid, the method comprising: receiving a Bezier curve; sequentially subdividing said Bezier curve into a plurality of subdivided Bezier curves until each received or subdivided Bezier curve crosses less than a plurality of times with cell boundaries of a grid of a desired resolution; and developing a cross associated with each of said received or subdivided Bezier curves which crosses one of said boundaries, said cross including Cartesian coordinates and direction.
Claim 39
Independent Claim
81 words
A method for determining crossings of Bezier curves with a grid, the method comprising: receiving a Bezier curve; sequentially subdividing said Bezier curve into a plurality of subdivided Bezier curves until each received or subdivided Bezier curve crosses less than a plurality of times with cell boundaries of a grid of a desired resolution; and developing a cross associated with each of said received or subdivided Bezier curves which crosses one of said boundaries, said cross including Cartesian coordinates and direction.
Claim 40
Dependent Claim
18 words
A method as recited in claim 35 wherein said step of sequentially subdividing is a recursive subdivision step.
Claim 41
Dependent Claim
20 words
A method as recited in claim 36 further comprising a step of utilizing said crosses to control an output device.
Claim 42
Dependent Claim
38 words
A method as recited in claim 36 wherein said step of receiving a Bezier curve includes receiving a Bezier curve of degree one and converting said Bezier curve of degree one to a Bezier curve of higher degree.
Claim 43
Dependent Claim
34 words
A method as recited in claim 36 wherein said step of receiving a Bezier curve includes storing said received Bezier curve in a FIFO memory structure until it is subdivided in said subdividing step.
Claim 44
Dependent Claim
32 words
A method as recited in claim 36 wherein said step of sequentially subdividing includes storing some of said subdivided curves on said stack to be retrieved and subdivided at a later time.
Claim 45
Dependent Claim
39 words
A method as recited in claim 36 wherein said step of developing the Cartesian coordinates and direction of said cross includes taking minimum coordinate values of endpoints in each coordinate axis of said Bezier curve associated with said cross.
Claim 46
Dependent Claim
40 words
A method as recited in claim 35 wherein said step of sequentially subdividing said Bezier curve includes subdividing an examined Bezier curve into two pieces and picking the first of said two pieces as a next Bezier curve to examine.
Claim 47
Dependent Claim
40 words
A method as recited in claim 42 wherein said step of sequentially subdividing said Bezier curve includes picking said second piece of said two pieces to examine after said picked first piece has been subdivided and developed into said crosses.
Claim 48
Dependent Claim
27 words
A method as recited in claim 42 wherein said step of sequentially subdividing said Bezier curve includes ignoring curves which do not cross any of said boundaries.
Claim 49
Dependent Claim
51 words
A method as recited in claim 42 wherein said step of sequentially subdividing said Bezier curve until each Bezier curve crosses less than a plurality of times includes detecting whether zero, one, or a plurality of said boundaries are crossed by a line segment connecting the endpoints of said Bezier curve.
Claim 50
Dependent Claim
82 words
A method as recited in claim 42 wherein said Bezier curves include control points described by a number of bits, and wherein said step of sequentially subdividing said Bezier curve until each Bezier curve crosses less than a plurality of times includes comparing corresponding bits of two of said control points to produce a resulting string of bits, wherein adjacent bits of said resulting string of bits are compared to determine if said Bezier curve crosses less than a plurality of times.
References Cited (Backward Citations)
US4674058A
Cited
US5200740A
Cited
EP0463574A2
Cited
EP0481463A2
Cited
US5317650A
Cited
EP0534622A2
Cited
US5301267A
Cited
US5428728A
Cited
US5381521A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2000-06-09 | 2000-12-09 | 2001-06-10 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2004-06-09 | 2004-12-09 | 2005-06-10 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2008-06-09 | 2008-12-09 | 2009-06-10 | $7700.00 | Window Closed / Lapsed |