Method and apparatus for generating bitmaps from outlines containing bezier curves

• US 5,638,503 A
• Filed: 07/07/1994
• Issued: 06/10/1997
• Est. Priority Date: 07/07/1994
• Status: Expired due to Term

• Current Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Hoel, Jeffrey H.
• Primary Examiner(s): Jankus, Almis R.
• Application Number:
  US08/271,864
• Time in Patent Office: 1,069 Days
• Field of Search: 395/118, 395/126, 395/127, 395/128, 395/129-132, 395/133, 395/135, 395/139, 395/141-143, 395/155, 395/161
• US Class Current: 345/442
• CPC Class Codes: G06F 5/10 having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using random access memory G06F5/065 takes precedence
• CPC Class Codes: G06F 7/785 having a sequence of storage locations each being individually accessible for both enqueue and dequeue operations, e.g. using a RAM
• CPC Class Codes: G06T 11/203 Drawing of straight lines or curves

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.

Claims

1. 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.

2. A system as recited in claim 1 wherein said multi-dimensional image is 2-dimensional.

3. A system as recited in claim 2 wherein said image rendering information includes a reference to information specified in an outline format.

4. 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.

5. 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.

6. A system as recited in claim 5 wherein said rendering device includes a microcontroller for providing said Bezier curves to said Bezier subdivision processor.

7. 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.

8. 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.

9. A rendering device as recited in claim 8 wherein said Bezier subdivision processor includes a memory unit for storing subdivided Bezier curves.

10. A rendering device as recited in claim 9 wherein said memory unit includes a stack memory structure for storing said subdivided Bezier curves.

11. A rendering device as recited in claim 10 wherein said memory unit includes a FIFO memory structure for storing received Bezier curves.

12. 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.

13. 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.

14. 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.

15. 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.

16. 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.

17. 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.

18. 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.

19. 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.

20. A Bezier subdivision processor as recited in claim 18 wherein said memory unit further includes a FIFO for storing received Bezier curves.

21. 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.

22. 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.

23. A Bezier subdivision processor as recited in claim 22 wherein said memory unit further comprises a FIFO full output.

24. 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.

25. 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.

26. 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.

27. 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.

28. 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.

29. 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.

30. 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.

31. A Bezier subdivision processor as recited in claim 18 wherein said Bezier subdivision unit includes a single-axis subdivision unit for each coordinate axis.

32. 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.

33. 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.

34. 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.

35. 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.

36. A method as recited in claim 35 wherein said step of sequentially subdividing is a recursive subdivision step.

37. A method as recited in claim 36 further comprising a step of utilizing said crosses to control an output device.

38. 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.

39. 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.

40. 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.

41. 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.

42. 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.

43. 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.

44. 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.

45. 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.

46. 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.