Reducing the number of compositing operations performed in a pixel sequential rendering system

• US 6,961,067 B2
• Filed: 02/20/2004
• Issued: 11/01/2005
• Est. Priority Date: 02/21/2003
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Moore, Kevin John
• Primary Examiner(s): Bella, Matthew C.
• Assistant Examiner(s): RAHMJOO, MANUCHER
• Application Number:
  US10/781,664
• Publication Number:
  US 20040189656A1
• Time in Patent Office: 620 Days
• Field of Search: 345/589, 345/593, 345/597, 345/629, 345/634
• US Class Current: 345/589
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 15/80 Shading

Abstract

Apparatus 20 is disclosed for rendering an object-based image one pixel at a time in scanline order. The apparatus 20 comprises an optimisation module 550 for generating a set of compositing messages during a first pixel in a run of pixels between adjacent edges of one or two objects, and for generating a reduced set of compositing messages from the set during subsequent pixels in the run of pixels. The apparatus 20 further comprises a pixel compositing module 700 which in addition to compositing the first pixel in the run of pixels also stores a result or partial result of the compositing of the first pixel. The pixel compositing module 700 utilises the reduced set of compositing messages and the stored result or partial result to composite pixels in the run subsequent to the first pixel.

Claims

1. An apparatus for rendering an object-based image one pixel at a time in scanline order, the apparatus comprising:

an optimisation module for minimising a number of compositing messages for compositing the object-based image, the optimisation module comprising;

a first unit for setting, for a first pixel in a run of pixels between adjacent edges of objects, first data in one or more compositing messages of a sequence of compositing messages to indicate that a compositing result of the one or more compositing messages is to be stored for use in compositing of each pixel subsequent to the first pixel in the run of pixels; and

a second unit for generating, for each pixel subsequent to the first pixel in the run of pixels, a reduced set of compositing messages from the sequence of compositing messages, the second unit comprising;

a sub-unit for generating, for each pixel subsequent to the first pixel in the run of pixels, the reduced set of compositing messages; and

a sub-unit for setting, for each pixel subsequent to the first pixel in the run of pixels, second data in one or more compositing messages of the reduced set to indicate that the stored compositing result is to be retrieved for use in compositing of each pixel subsequent to the first pixel in the run of pixels; and

a compositing module for generating a resultant color and opacity for a currently scanned pixel in accordance with the compositing messages, wherein the compositing module generates the color and opacity of the first pixel in the run of pixels in accordance with the sequence of compositing operations, and the compositing module generates the color and opacity of each pixel in the run subsequent to the first pixel in accordance with the reduced set and the retrieved compositing result.

2. The apparatus as claimed in claim 1, wherein the compositing module comprises a stack for generating a resultant color and opacity for a currently scanned pixel in accordance with the compositing messages.

3. The apparatus as claimed in claim 2, wherein each compositing message comprises compositing instructions, data representative of the color and opacity of an associated object, and data representative of whether the color and opacity are constant along the scanline.

4. The apparatus as claimed in claim 3, wherein the first unit comprises:

a sub-unit for setting the first data of a current compositing message in the event a predicted stack depth of the stack is of a predetermined depth and the current compositing message and all of the compositing messages having their associated first data set so far are associated with objects that have a constant color and opacity along the scanline.

5. The apparatus as claimed in claim 4, wherein the reduced set of compositing messages comprises the compositing message corresponding to the last compositing message of the first pixel having the first data set and the subsequent compositing messages of the sequence corresponding to the compositing messages having their first data not set.

6. The apparatus as claimed in claim 5, wherein the sub-unit for setting the second data in the one or more compositing messages of the reduced set comprises:

a sub-unit for setting the second data in the compositing message corresponding to a last compositing message of the first pixel having the first data set.

7. The apparatus as claimed in claim 3, wherein the compositing instructions comprise stack operations and color and opacity operators, and wherein the first unit comprises:

a sub-unit for setting the first data of a current compositing message in the event the current compositing message and the compositing messages having their first data set so far are associated with objects that have a constant color and opacity over the scanline and comprise stack operators that are not a predetermined stack operator.

8. The apparatus as claimed in claim 2, wherein the compositing result is a value on the top of the stack.

9. The apparatus as claimed in claim 2, wherein the first data indicates that the state of the stack storing the compositing result is to be stored.

10. The apparatus as claimed in claim 9, wherein the first unit comprises:

a sub-unit for setting the first data of a current compositing message in the event the current compositing message is the first compositing message for the first pixel in the run associated with objects that have a variable color and opacity along the scanline.

11. The apparatus as claimed in claim 10, wherein the reduced set of compositing messages comprises the compositing message corresponding to a last compositing message of the first pixel having the first data set and the subsequent compositing messages of the sequence corresponding to those compositing messages having their first data not set.

12. The apparatus as claimed in claim 11, wherein the sub-unit for setting the second data in the one or more compositing messages of the reduced set comprises:

a sub-unit for setting the second data in the compositing message corresponding to a last compositing message having the first data set.

13. The apparatus as claimed in claim 3, wherein the first unit comprises:

a sub-unit for setting the first data of a current compositing message in the event the current compositing message is associated with a predicted stack depth of a predetermined value and is one of a sub-sequence of compositing messages that have a constant color and opacity along the scanline and comprise a color and alpha operator of a predetermined type.

14. The apparatus as claimed in claim 13, wherein the color and alpha operator of a predetermined type is associative.

15. The apparatus as claimed in claim 14, wherein the sub-unit for setting the first data in addition sets the first data of a current compositing message in the event the current compositing message is associated with a predicted stack depth of a predetermined value and has a stack operator, and color and alpha operators of a predetermined type.

16. The apparatus as claimed in claim 14, wherein the reduced set of compositing messages comprises:

the compositing messages of the sequence that are not members of the sub-sequence and correspond to those compositing messages of the first pixel having their first data not set; and

the compositing message corresponding to a last compositing message of the first pixel having the first data set.

17. The apparatus as claimed in claim 13, wherein the sub-unit for setting the second data in the one or more compositing messages of the reduced set comprises:

a sub-unit for setting the second data in the compositing message corresponding to a last compositing message having the first data set.

18. The apparatus as claimed in claim 3, wherein the first unit comprises:

a sub-unit for setting the first data of a current compositing message in the event the current compositing message is associated with a predicted stack depth of a predetermined value and is one of a sub-sequence of compositing messages that have a constant color and opacity along the scanline and are part of a valid branch of an expression tree.

19. The apparatus as claimed in claim 18, wherein the reduced set of compositing messages comprises;

the compositing message corresponding to a last compositing message having the first data set, for each predicted stack depth for which first data has been set for at least one compositing message; and

the compositing messages of the sequence corresponding to those compositing messages having their first data not set and subsequent to the last compositing message having the first data set.

20. The apparatus as claimed in claim 18, wherein the sub-unit for setting the second data in the one or more compositing messages of the reduced set comprises:

a sub-unit for setting the second data in the compositing message corresponding to a last compositing message having the first data set, for each stack depth for which first data has been set for at least one compositing message.

21. A method for rendering an object-based image one pixel at a time in scanline order, the method comprising the steps of:

an optimisation step for minimising a number of compositing messages for compositing the object-based image, the optimisation step comprising the sub-steps;

a setting step for setting, for a first pixel in a run of pixels between adjacent edges of objects, first data in one or more compositing messages of a sequence of compositing messages to indicate that a compositing result of these one or more compositing messages is to be stored for use in compositing of each pixel subsequent to the first pixel in the run of pixels; and

a generating step for generating, for each pixel subsequent to the first pixel in the run of pixels, a reduced set of compositing messages from the sequence of compositing messages, the generating step comprising;

a generating sub-step for generating, for each pixel subsequent to the first pixel in the run of pixels, the reduced set of compositing messages; and

a setting sub-step for setting, for each pixel subsequent to the first pixel in the run of pixels, second data in one or more compositing messages of the reduced set to indicate that the stored compositing result is to be retrieved for use in compositing of each pixel subsequent to the first pixel in the run of pixels; and

a compositing step for generating a resultant color and opacity for a currently scanned pixel in accordance with the compositing messages, wherein the compositing module generates the color and opacity of the first pixel in the run of pixels in accordance with the sequence of compositing operations, and the compositing module generates the color and opacity of each pixel in the run subsequent to the first pixel in accordance with the reduced set and the retrieved compositing result.

22. A computer program product comprising machine-readable program code recorded on a machine-readable recording medium, for controlling the operation of a data processing apparatus on which the program code executes to perform a method for rendering an object-based image one pixel at a time in scanline order, the method comprising:

an optimisation step for minimising a number of compositing messages for compositing the object-based image, the optimisation step comprising the sub-steps;

a setting step for setting, for a first pixel in a run of pixels between adjacent edges of objects, first data in one or more compositing messages of a sequence of compositing messages to indicate that a compositing result of these one or more compositing messages is to be stored for use in compositing of each pixel subsequent to the first pixel in the run of pixels; and

a generating step for generating, for each pixel subsequent to the first pixel in the run of pixels, a reduced set of compositing messages from the sequence of compositing messages, the generating step comprising;

a generating sub-step for generating, for each pixel subsequent to the first pixel in the run of pixels, the reduced set of compositing messages; and

a setting sub-step for setting, for each pixel subsequent to the first pixel in the run of pixels, second data in one or more compositing messages of the reduced set to indicate that the stored compositing result is to be retrieved for use in compositing of each pixel subsequent to the first pixel in the run of pixels; and

a compositing step for generating a resultant color and opacity for a currently scanned pixel in accordance with the compositing messages, wherein the compositing module generates the color and opacity of the first pixel in the run of pixels in accordance with the sequence of compositing operations, and the compositing module generates the color and opacity of each pixel in the run subsequent to the first pixel in accordance with the reduced set and the retrieved compositing result.