Load balanced image generation

• US 6,108,460 A
• Filed: 06/10/1996
• Issued: 08/22/2000
• Est. Priority Date: 01/02/1996
• Status: Expired due to Term

• Current Assignee: Rambus Inc.
• Original Assignee: Pixelfusion Limited
• Inventors: Rich, Henry H.
• Primary Examiner(s): Tran, Phuoc
• Assistant Examiner(s): Mariam, Daniel G.
• Application Number:
  US08/661,028
• Time in Patent Office: 1,534 Days
• Field of Search: 382/302, 382/276, 382/304, 358/448, 358/515, 395/675, 345/153, 345/418, 345/430, 345/431, 345/505, 345/509, 345/514
• US Class Current: 382/304
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining

Abstract

Methods, apparatus and program products provide load balancing in a paralell processing image generation system. In an image generation system for generating pixel values of a pixel array which corresponds to a group of geometric primitives which define a computer generated image where the image generation system includes a plurality of processing elements which are assigned to a specified pixel of the pixel array. The specification of pixels to processing elements is carried out to balance the processing load of the plurality of processing elements. Regions of the pixel array may be associated with subsets of the plurality of processing elements. A linear expression evaluator then provides region specific coefficients to the subsets of the plurality of processing elements. The plurality of processing elements may also be divided into a plurality of panels. The pixels are then associated with one of the plurality of panels and the linear expression evaluator provides region specific coefficients to the processing elements of the panel associated with the region. The regions may be further divided into a plurality of subregions with at least one pixel from each of the plurality of subregions assigned to each of the processing elements.

Claims

1. An image generation system for generating pixel values of a pixel array which corresponds to a group of geometric primitives which define a computer generated image, the image generation system comprising:

a plurality of processing elements for evaluating mathematical expressions which define said geometric primitives to generate a contribution value for pixels of said pixel array, wherein each of said plurality of processing elements corresponds to a specified pixel of said pixel array and wherein the specified pixel of a processing element in the plurality of processing elements is any pixel of said pixel array; and

load balancing assignment means for dispersing the assignments of pixels to said processing elements of said plurality of processing elements to establish the correspondence of said specified pixels of said pixel array with said processing elements, wherein the dispersion of assignments of processing elements to said specified pixels disperses the assignments of adjacent processing elements among non-adjacent pixels.

2. An image generation system according to claim 1, wherein said load balancing assignment means associates a pixel of said pixel array with one of said plurality of processing elements for each of said primitives in said group of primitives.

3. An image generation system according to claim 1, wherein said mathematical expressions comprise linear expressions, said image generation system further comprising a linear expression evaluator operably associated with said plurality of processing elements for providing coefficients of said linear expressions to said plurality of processing elements.

4. An image generation system according to claim 1, wherein said mathematical expressions comprise linear expressions, said image generation system further comprising a linear expression evaluator operably associated with said plurality of processing elements for evaluating said linear expressions and providing the results of said evaluation to said plurality of processing elements.

5. An image generation system according to claim 4, wherein said load balancing assignment means further comprises means for associating regions of said pixel array to said plurality of processing elements and wherein said linear expression evaluator provides region specific coefficients to said plurality of processing elements.

6. An image generation system according to claim 5, wherein said plurality of processing elements is divided into a plurality of panels;

and

wherein said linear expression evaluator further provides panel specific coefficients to said processing elements of one of said panels.

7. An image generation system according to claim 5, wherein said plurality of processing elements is divided into a plurality of panels;

and

wherein said load balancing assignment means further comprises means for associating pixels of one of said regions to a respective one of said plurality of panels; and

wherein said linear expression evaluator further provides panel specific coefficients to said processing elements of said respective one of said panel associated with said region.

8. An image generation system according to claim 7, wherein said regions are further divided into a plurality of subregions and wherein said load balancing assignment means further comprises means for assigning at least one pixel from each of said plurality of subregions to each of said processing elements.

9. An image generation system according to claim 7, wherein said linear expression evaluator evaluates the mathematical expression for a region base value for said regions and further provides said calculated region base value to said processing elements associated with said region.

10. A method of generating a computer image utilizing a plurality of processing elements in a processing element array, wherein the computer image defines a screen having a plurality of pixels and wherein the image displayed on the screen is defined by a plurality of geometric primitives, said method comprising the steps of:

assigning home pixel addresses to the processing elements of the processing array;

determining which home pixel addresses of the processing elements correspond to pixels of the screen which are inside a region defined by one of said geometric primitives which define the image such that a contribution value for the geometric primitive will result for the home pixels which are within the geometric primitives; and

then

distributing the contributions which said determining step determines correspond to home pixels for which a contribution value for the geometric primitive will result, to the processing elements of the processing element array such that each of the processing elements provides one contribution value for a home pixel based on the assigned contribution and wherein at least one contribution for a home pixel is assigned to a processing element other than the processing element associated with the home pixel of the at least one contribution.

11. The method of claim 10 wherein said determining and said distributing steps are repeated until one of a condition selected from a group comprising a condition of a contribution being distributed to each of the processing elements in the processing element array and a condition of at least one processing element in the processing element array being unable to accept a further contribution is satisfied.

12. The method of claim 10, further comprising the steps of:

determining the contribution values for each home pixel based upon the contributions;

then

returning the contribution values for each home pixel to the processing element associated with the home pixel; and

then

generating a final contribution value for each home pixel from the contribution values returned for the home pixel.

13. The method of claim 10, wherein said assigning step is followed by the step of discarding contributions if a contribution for a home pixel associated with a geometric primitive will be obscured by a nearer geometric primitive.

14. The method of claim 10 wherein said assigning step comprises assigning a plurality of home pixels to each of the processing elements such that the home pixels of each processing element correspond to non-adjacent pixels of the screen.

15. The method of claim 10 wherein said assigning step is followed by the step of determining texturing contribution values for the contributions.

16. An apparatus for generating a computer image wherein the computer image defines a screen having a plurality of pixels and wherein the image displayed on the screen is defined by a plurality of geometric primitives comprising:

a plurality of processing elements in a processing element array,

means for assigning home pixel addresses to said processing elements of said processing array;

means for determining which home pixel addresses of the processing elements correspond to pixels of the screen which are inside a region defined by one of said geometric primitives which define the image such that a contribution value for the geometric primitive will result for the home pixels within said geometric primitives; and

means for distributing the contributions which said means for determining determines correspond to home pixels for which a contribution value for the geometric primitive will result to the processing elements of the processing element array such that each of the processing elements provides one contribution value for a home pixel based on the assigned contribution and wherein at least one contribution for a home pixel is assigned to a processing element other than the processing element associated with the home pixel of the at least one contribution.

17. The apparatus of claim 16 wherein said means for determining and said means for distributing steps further comprise means for repeatedly determining which home pixel addresses of the processing elements correspond to pixels of the screen which are inside a region defined by a geometric primitive which define the image such that a contribution value for the geometric primitive will result for the home pixels within said geometric primitives and distributing the contributions which said determining step determines correspond to home pixels for which a contribution value for the geometric primitive will result to the processing elements of the processing element array such that each of the processing elements provides one contribution value for a home pixel based on the assigned contribution until one of the conditions selected from the group comprising the condition of a geometric primitive being distributed to each of the processing elements in the processing element array and the condition of at least one processing element in the processing element array being unable to accept a further primitive is satisfied.

18. The apparatus of claim 16, further comprising:

means for determining the contribution values for each home pixel based upon said contributions;

means for returning the contribution values for each home pixel to the processing element associated with the home pixel; and

means for generating a final contribution value for each home pixel from the contribution values returned for the home pixel.

19. The apparatus of claim 16, further comprising means for discarding contributions if a contribution for a home pixel associated with a geometric primitive will be obscured by a nearer geometric primitive.

20. The apparatus of claim 16 wherein said means for assigning comprises means for assigning a plurality of home pixels to each of said processing elements such that the home pixels of any specific processing element correspond to non-adjacent pixels of the screen.

21. The apparatus of claim 16 further comprising means for determining texturing contribution values for the home pixels.

22. A computer program product for generating a computer image utilizing a plurality of processing elements in a processing element array, wherein the computer image defines a screen having a plurality of pixels and wherein the image displayed on the screen is defined by a plurality of geometric primitives comprising:

A computer-readable storage medium having computer-readable program code means embodied in said medium, said computer-readable program code means comprising;

computer readable program code means for assigning home pixel addresses to said processing elements of said processing array;

computer readable program code means for determining which home pixel addresses of the processing elements correspond to pixels of the screen which are inside a region defined by one of said geometric primitives which define the image such that a contribution value for the geometric primitive will result for the home pixels within said geometric primitives; and

computer readable program code means for distributing the contributions which said computer readable program code means for determining determines correspond to home pixels for which a contribution value for the geometric primitive will result to the processing elements of the processing element array such that each of the processing elements provides one contribution value for a home pixel based on the assigned contribution and wherein at least one contribution for a home pixel is assigned to a processing element other than the processing element associated with the home pixel of the at least one contribution.

23. The computer program product of claim 22 wherein said computer readable program code means for determining and said computer readable program code means for distributing steps further comprise computer readable program code means for repeatedly determining which home pixel addresses of the processing elements correspond to pixels of the screen which are inside a region defined by a geometric primitive which define the image such that a contribution value for the geometric primitive will result for the home pixels within said geometric primitives and distributing the contributions which said computer readable program code means for determining determines correspond to home pixels for which a contribution value for the geometric primitive will result to the processing elements of the processing element array such that each of the processing elements provides one contribution value for a home pixel based on the assigned contribution until one of the conditions selected from the group comprising the condition of a geometric primitive being distributed to each of the processing elements in the processing element array and the condition of at least one processing element in the processing element array being unable to accept a further primitive is satisfied.

24. The computer program product of claim 22, further comprising:

computer readable program code means for determining the contribution values for each home pixel based upon said contributions;

computer readable program code means for returning the contribution values for each home pixel to the processing element associated with the home pixel; and

computer readable program code means for generating a final contribution value for each home pixel from the contribution values returned for the home pixel.

25. The computer program product of claim 22, further comprising computer readable program code means for discarding contributions if a contribution value for a home pixel associated with a geometric primitive will be obscured by a nearer geometric primitive.

26. The computer program product of claim 22 wherein said computer readable program code means for assigning comprises computer readable program code means for assigning a plurality of home pixels to each of said processing elements such that the home pixels of any specific processing element correspond to non-adjacent pixels of the screen.

27. The computer program product of claim 22 further comprising computer readable program code means for determining texturing contribution values for the home pixels.

28. A method of generating pixel values of a pixel array utilizing a plurality of processing elements in a processing element array, wherein the pixel array corresponds to a group of geometric primitives which define a computer generated image, the method comprising the steps of:

evaluation mathematical expressions which define said geometric primitives to generate a contribution value for pixels of said pixel array, wherein each processing element of the plurality of processing elements corresponds to a specified pixel of said pixel array and wherein the specified pixel of a processing element in the plurality of processing elements is any pixel of said pixel array; and

dispersing the assignments of pixels to said processing elements of said plurality of processing elements to establish the correspondence of said specified pixels of said pixel array with said processing elements, wherein the dispersion of assignments of processing elements to said specified pixels disperses the assignments of adjacent processing elements among non-adjacent pixels.