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

• US 7,483,036 B2
• Filed: 07/15/2005
• Issued: 01/27/2009
• Est. Priority Date: 02/21/2003
• Status: Expired due to Fees

• 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, MANUCHEHR
• Application Number:
  US11/181,974
• Publication Number:
  US 20060114263A1
• Time in Patent Office: 1,292 Days
• Field of Search: 345/589, 345/619, 345/582, 345/581, 345/629
• US Class Current: 345/589
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 15/80 Shading

Abstract

An apparatus for recording an object-based image one pixel at a time in scanline order includes an optimization module for generating a set of compositing messages corresponding to a first pixel and generating a reduced set of compositing messages from the set of compositing messages, and a pixel compositing module which, in addition to compositing the first pixel using the set of compositing messages, stores a result or partial result of the compositing of the first pixel. The pixel compositing module utilizes the reduced set of compositing messages and the stored result or partial result to composite at least one subsequent pixel, and the first pixel and the at least one subsequent pixel form part of a run of pixels along a scanline of the image between adjacent edges of objects in the object-based image.

Claims

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

an optimization module for generating a set of compositing messages corresponding to a first pixel and generating a reduced set of compositing messages from the set of compositing messages; and

a pixel compositing module comprising a stack for generating a resultant color and opacity for a current pixel in accordance with the compositing messages, said pixel compositing module, in addition to compositing the first pixel using the set of compositing messages, stores a result or partial result of the compositing of the first pixel, wherein said pixel compositing module utilizes the reduced set of compositing messages and the stored result or partial result to composite at least one subsequent pixel, wherein

the first pixel and the at least one subsequent pixel form part of a run of pixels along a scanline of the image between adjacent edges of objects in the object-based image,

said optimization module sets first data in one or more of the compositing messages in the set to indicate that a compositing result of the one or more compositing messages is to be used in compositing the at least one subsequent pixel, and

said optimization module sets the first data of a current compositing message if 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 are associated with objects that have a constant color and opacity along the scanline.

2. An apparatus according to claim 1, wherein the reduced set of compositing messages comprises the compositing message corresponding to the last compositing message of the first pixel having the associated first data set and subsequent compositing messages of the sequence corresponding to the compositing messages having their associated first data not set.

3. An apparatus according to claim 1, wherein the compositing messages include stack operations and color and opacity operators, and wherein said optimization module sets the first data of a current compositing message if the current compositing message and previous compositing messages having their first data set 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.

4. An apparatus according to claim 1, wherein the first data indicates that the state of the stack storing the compositing result is to be stored.

5. An apparatus according to claim 4, wherein said optimization module sets the first data of a current compositing message if 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.

6. An apparatus according to claim 5, wherein the reduced set of compositing messages comprises the compositing message corresponding to a last compositing message of the first pixel having the associated first data set and the subsequent compositing messages of the sequence corresponding to those compositing messages having their associated first data not set.

7. An apparatus according to claim 1, wherein said optimization module sets the first data of a current compositing message if the current compositing message is associated with a predicted stack depth of a predetermined value and the current compositing message is one of a sub-sequence of compositing messages having a constant color and opacity along the scanline and comprising a color and alpha operator of a predetermined type.

8. An apparatus according to claim 7, wherein the predetermined type is associative.

9. An apparatus according to claim 8, 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.

10. An apparatus according to claim 1, wherein said optimization module sets the first data of a current compositing message if 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.

11. An apparatus according to claim 10, 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 messages; 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.

12. An apparatus according to claim 1, wherein said optimization module sets second data in one or more compositing messages of the reduced set to indicate that the compositing result is retrieved for use in compositing of the at least one subsequent pixel.

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

generating a set of compositing messages corresponding to a first pixel, wherein the first pixel and at least one subsequent pixel form part of a run of pixels along a scanline of the image between adjacent edges of objects in the object-based image, said generating step comprising setting first data in one or more of the compositing messages in the set to indicate that a compositing result of the one or more compositing messages is to be used in compositing the at least one subsequent pixel, and setting the first data of a current compositing message if 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 are associated with objects that have a constant color and opacity along the scanline;

generating a reduced set of compositing messages from the set of compositing messages;

compositing the first pixel using the set of compositing messages and a stack for generating a resultant color and opacity for the first pixel in accordance with the compositing messages;

storing a result or partial result of said compositing of the first pixel; and

rendering the image by compositing the at least one subsequent pixel using the reduced set of compositing messages and the stored result or partial result wherein each of the steps is computer implemented.

14. A computer readable memory device encoded with a computer program recorded for controlling the operation of a data processing apparatus on which the program code executes to render an object-based image one pixel at a time in scanline order, said program comprising:

code for generating a set of compositing messages corresponding to a first pixel, wherein the first pixel and at least one subsequent pixel form part of a run of pixels along a scanline of the image between adjacent edges of objects in the object-based image, said generating code comprising setting first data in one or more of the compositing messages is to be used in compositing the at least one subsequent pixel, and setting the first data of a current compositing message if 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 are associated with objects that have a constant order and opacity along the scanline;

code for generating a reduced set of compositing messages from the set of compositing messages;

code for compositing the first pixel using the set of compositing messages and a stack for generating a resultant color and opacity for the first pixel in accordance with the compositing messages;

code for storing a result or partial result of said compositing of the first pixel; and

code for rendering the image by compositing the at least one subsequent pixel using the reduced set of compositing messages and the stored result or partial result, wherein the first pixel and the at least one subsequent pixel form part of a run of pixels along a scanline of the image between adjacent edges of objects in the object-based image.