US 8,089,481 B2 · Updating frame divisions based on ray tracing image processing system performance

Abstract

An image processing system may perform various tasks in an effort to evenly distribute workload amongst workload managers. According to one embodiment of the invention, the image processing system may divide a frame of pixels into different regions and assign responsibility for the regions to different workload managers in order to evenly distribute workload. The workload managers may be responsible for performing operations relating to determining or maintaining the color of the pixel within the region or regions which they are responsible. According to another embodiment of the invention, the image processing system may re-divide the frame into new regions based on relative workloads experienced by the processing elements to evenly distribute workload. Furthermore, according to another embodiment of the invention, the image processing system may re-partition a spatial index based on relative workloads experienced by the processing elements to evenly distribute workload amongst workload managers.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims25

Dependent claims

A method for distributing workload in a ray tracing image processing system, the method comprising:

dividing a two-dimensional frame of pixels into at least a first region of pixels and a second region of pixels, wherein the two-dimensional frame of pixels represents an image rendered from a three-dimensional scene;
partitioning a spatial index, wherein the spatial index represents the three-dimensional scene;
assigning to a first processing element a responsibility for initiating ray tracing for rays that traverse through the first region of pixels;
assigning to a second processing element a responsibility for initiating ray tracing for rays that traverse through the second region of pixels;
performing ray tracing with the first processing element and the second processing element to determine colors of pixels in the two-dimensional frame of pixels;
monitoring at least one of a workload experienced by the first processing element and a workload experienced by the second processing element;
re-dividing the two-dimensional frame of pixels into at least a new first region of pixels and a new second region of pixels based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element;
and
re-partitioning the spatial index based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element.

6 more elements

A non-transitory computer readable storage medium containing a program which, when executed, performs operations comprising:

dividing a two-dimensional frame of pixels into at least a first region of pixels and a second region of pixels, wherein the two-dimensional frame of pixels represents an image rendered from a three-dimensional scene;
partitioning a spatial index, wherein the spatial index represents the three-dimensional scene;
assigning to a first processing element a responsibility for initiating ray tracing for rays that traverse through the first region of pixels;
assigning to a second processing element a responsibility for initiating ray tracing for rays that traverse through the second region of pixels;
performing ray tracing with the first processing element and the second processing element to determine colors of pixels in the two-dimensional frame of pixels;
monitoring at least one of a workload experienced by the first processing element and a workload experienced by the second processing element;
re-dividing the two-dimensional frame of pixels into at least a new first region of pixels and a new second region of pixels based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element;
and
re-partitioning the spatial index based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element.

6 more elements

An image processing system comprising:

a first processing element;
and
a second processing element,
wherein the image processing system is configured to:
divide a two-dimensional frame of pixels into at least a first region of pixels and a second region of pixels, wherein the two-dimensional frame of pixels represents an image rendered from a three-dimensional scene,
partition a spatial index, wherein the spatial index represents the three-dimensional scene,
assign to the first processing element a responsibility for initiating ray tracing for rays that traverse through the first region of pixels,
assign to the second processing element a responsibility for initiating ray tracing for rays that traverse through the second region of pixels,
perform ray tracing with the first processing element and the second processing element to determine colors of pixels in the two-dimensional frame of pixels,
monitor at least one of a workload experienced by the first processing element and a workload experienced by the second processing element,
re-divide the two-dimensional frame of pixels into at least a new first region of pixels and a new second region of pixels based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element, and
re-partition the spatial index based on at least one of the workload experienced by the first processing element and the workload experienced by the second processing element.

9 more elements

Dependencies are inferred from the claim text.

Description15,167 words

Summary1,313 words

#1. Field of the Invention

#Embodiments of the invention generally relate to the field of computer processing.

#2. Description of the Related Art

Brief description of the drawings10 figures

#FIG. 1 illustrates a multiple core processing element, according to one embodiment of the invention.

#FIGS. 2 and 6 illustrate multiple core processing element networks, according to embodiments of the invention.

#FIG. 3 is an exemplary three dimensional scene to be rendered by an image processing system, according to one embodiment of the invention.

Detailed description13,622 words

#Embodiments of the invention provide systems and methods for distributing workload in a ray tracing image processing system. Evenly distributed workload in a ray tracing image processing system may result in faster and more efficient image processing.

#Some embodiments of the invention may evenly distribute workload by dividing a frame of pixels to be rendered into a plurality of regions, and assigning responsibility for each region to different processing elements. Each processing element may be responsible for performing a multitude of tasks for the pixels within their corresponding region, and these tasks may ultimately result in determining the color of those pixels. Furthermore, processing elements may be assigned responsibility to the regions of the frame based on the portions of a spatial index which they are responsible for traversing rays through.

#Some embodiments of the invention may re-distribute workload amongst processing elements by re-dividing the frame into new regions based on relative workloads experienced by the processing elements. By re-dividing the frame, processing elements which may have been experiencing a relatively high workload may be responsible for a smaller region of the frame than before, and processing elements which may have been experiencing a relatively low workload may be responsible for a larger region of the frame than before.

Facts

Application

11/536,179Filed 28 Sep 2006

Published

US 2008/0079734 A13 Apr 2008

Granted

3 Jan 2012

Term ends

14 Sep 2028

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 717 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification3 codes

G06T 15/06
Three-dimensional [3D] image rendering: ray-tracing
G06T 2210/52
Indexing scheme for image generation or computer graphics: parallel processing
G06T
Image data processing or generation, in general

Timeline

28 Sep 2006Application filedUS 11/536,179
28 Sep 2006Assigned to International Business Machines Corporationassignment of assignor's interest
3 Apr 2008PublishedUS 2008/0079734 A1
3 Jan 2012GrantedUS 8,089,481 B2
28 Feb 2013Assigned to Activision Publishing, Inc.assignment of assignor's interest
11 Feb 2014Assigned to Bank of America, N.A.security agreement
17 Oct 2016Assigned to Activision Blizzard Inc., Activision Publishing, Inc., Activision Entertainment Holdings, Inc., Blizzard Entertainment, Inc.release of security interest
12 Oct 2026TodayWithin its term
14 Sep 2028Term endsEstimated, includes 717 days of adjustment

Updating frame divisions based on ray tracing image processing system performance

Life of this patent

Updating frame divisions based on ray tracing image processing system performance

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims25

Description15,167 words

Drawings

Classification3 codes

Life of this patent

Description15,167 words