Assignments for parallel rasterization

• US 7,719,538 B1
• Filed: 04/04/2008
• Issued: 05/18/2010
• Est. Priority Date: 10/08/2002
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Chen, Paul, Sandman, James G.
• Primary Examiner(s): Amini; Javid A
• Application Number:
  US12/098,211
• Time in Patent Office: 774 Days
• Field of Search: 345/505
• US Class Current: 345/505
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining

Abstract

Methods and apparatus, including computer program products, to rasterize an image by generating assignments and allocating the assignments among multiple processor threads such that no two processor threads are rasterizing concurrently into overlapping regions of a pixel array. Multiple assignments are generated. Each assignment specifies one or more graphics objects and a region of the pixel array into which the specified graphics objects are to be rasterized. Multiple processes are established for rasterizing objects into a pixel array. Each process is operable to receive an assignment and to rasterize the objects of the assignment into the region of the assignment. Assignments are selected for concurrent execution by processes so that no two selected assignments have overlapping regions. The selected assignments are concurrently executed by separate processes to rasterize the respective objects of the assignments into their respective regions.

Claims

1. A computer-implemented method for rasterizing an image into a pixel array, the method comprising:

generating, by a computer, a plurality of assignments, each assignment specifying one or more graphics objects and a region of the pixel array into which the specified graphics objects are to be rasterized, wherein assignments are generated based on an estimated workload for each region;

establishing, by the computer, a plurality of processes for rasterizing objects into the pixel array, each process being operable to receive an assignment and to rasterize the objects of the assignment into the region of the assignment;

selecting assignments for concurrent execution by the processes, the assignments being selected so that no two concurrently executing assignments have overlapping regions; and

concurrently executing the selected assignments by separate processes to rasterize the respective objects of the assignments into their respective regions; and

wherein generating a plurality of assignments includes generating an assignment queue; and

the assignments are ordered in the assignment queue based at least in part on a paint order of objects specified in the assignments.

2. The method of claim 1 wherein the plurality of assignments includes a first assignment specifying a first region of the pixel array and a second assignment specifying a second region of the pixel array, the first region including one or more pixels included in the second region.

3. The method of claim 2 wherein the first assignment and the second assignment specify a common region of the pixel array.

4. The method of claim 1 wherein selecting assignments includes selecting a first assignment and a second assignment for concurrent execution by a first process and a second process, respectively, the method further comprising:

after the first process has completed execution of the first assignment, selecting a third assignment for execution by the first process.

5. The method of claim 1 wherein generating a plurality of assignments includes generating an assignment queue;

and the assignments are ordered in the assignment queue based at least in part on the determination of whether concurrent execution of the assignments would require rasterization into overlapping regions.

6. The method of claim 1 wherein generating a plurality of assignments further comprises determining a workload estimate for a region based on a number, an area, a color, or a complexity of graphics objects in a region.

7. A computer program product, encoded on a computer-readable storage device, operable to cause data processing apparatus to perform operations comprising:

generating a plurality of assignments, each assignment specifying one or more graphics objects and a region of the pixel array into which the specified graphics objects are to be rasterized, wherein assignments are generated based on an estimated workload for each region;

establishing a plurality of processes for rasterizing objects into the pixel array, each process being operable to receive an assignment and to rasterize the objects of the assignment into the region of the assignment;

selecting assignments for concurrent execution by the processes, the assignments being selected so that no two concurrently executing assignments have overlapping regions;

concurrently executing the selected assignments by separate processes to rasterize the respective objects of the assignments into their respective regions; and

wherein generating a plurality of assignments includes generating an assignment queue; and

the assignments are ordered in the assignment queue based at least in part on a paint order of objects specified in the assignments.

8. The program product of claim 7 wherein the plurality of assignments includes a first assignment specifying a first region of the pixel array and a second assignment specifying a second region of the pixel array, the first region including one or more pixels included in the second region.

9. The program product of claim 8 wherein the first assignment and the second assignment specify a common region of the pixel array.

10. The program product of claim 7 wherein selecting assignments includes selecting a first assignment and a second assignment for concurrent execution by a first process and a second process, respectively, the operations further comprising:

after the first process has completed execution of the first assignment, selecting a third assignment for execution by the first process.

11. The program product of claim 7 wherein generating a plurality of assignments includes generating an assignment queue;

and the assignments are ordered in the assignment queue based at least in part on the determination of whether concurrent execution of the assignments would require rasterization into overlapping regions.

12. The program product of claim 7 wherein generating a plurality of assignments further comprises determining a workload estimate for a region based on a number, an area, a color, or a complexity of graphics objects in a region.

13. A system comprising:

a display device;

a computer readable medium including a program product; and

one or more processors configured to interact with the display device, execute the program product and perform operations comprising;

generating a plurality of assignments, each assignment specifying one or more graphics objects and a region of the pixel array into which the specified graphics objects are to be rasterized, wherein assignments are generated based on an estimated workload for each region;

establishing a plurality of processes for rasterizing objects into the pixel array, each process being operable to receive an assignment and to rasterize the objects of the assignment into the region of the assignment;

selecting assignments for concurrent execution by the processes, the assignments being selected so that no two concurrently executing assignments have overlapping regions;

concurrently executing the selected assignments by separate processes to rasterize the respective objects of the assignments into their respective regions; and

wherein generating a plurality of assignments includes generating an assignment queue; and

the assignments are ordered in the assignment queue based at least in part on a paint order of objects specified in the assignments.

14. The system of claim 13 wherein the plurality of assignments includes a first assignment specifying a first region of the pixel array and a second assignment specifying a second region of the pixel array, the first region including one or more pixels included in the second region.

15. The system of claim 14 wherein the first assignment and the second assignment specify a common region of the pixel array.

16. The system of claim 13 wherein selecting assignments includes selecting a first assignment and a second assignment for concurrent execution by a first process and a second process, respectively, the operations further comprising:

after the first process has completed execution of the first assignment, selecting a third assignment for execution by the first process.

17. The system of claim 13 wherein generating a plurality of assignments includes generating an assignment queue;

and the assignments are ordered in the assignment queue based at least in part on the determination of whether concurrent execution of the assignments would require rasterization into overlapping regions.

18. The system of claim 13 wherein generating a plurality of assignments further comprises determining a workload estimate for a region based on a number, an area, a color, or a complexity of graphics objects in a region.