Method and Apparatus for Spatial Binning on a GPU and Global Path Planning to Avoid Spatially Binned Objects

• US 20100141666A1
• Filed: 07/10/2009
• Published: 06/10/2010
• Est. Priority Date: 07/11/2008
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Christopher, Oat, Jeremy, Shopf, Barczak, Joshua D.
• Granted Patent: US 8,810,590 B2
• Time in Patent Office: Days
• US Class Current: 345/520
• CPC Class Codes: G06T 13/20 3D [Three Dimensional] animation
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 9/001 Model-based coding, e.g. wire frame

Abstract

A method and apparatus for sorting data into spatial bins or buckets using a graphics processing unit (GPU). The method takes unsorted point data as input and scatters the points, in sorted order, into a set of bins. This key operation enables construction of a spatial data structure that is useful for applications such as particle simulation or collision detection. The disclosed method achieves better performance scaling than previous methods by exploiting geometry shaders to progressively trim the size of a working set. The method also leverages predicated rendering functionality to allow early termination without CPU/GPU synchronization. Furthermore, unlike previous techniques, the method can guarantee sorted output without requiring sorted input. This allows the method to be used to implement a form of bucket sort using the GPU.

Claims

1. A method carried out by graphics processing circuitry comprising:

computing a bin address for a plurality of item identifiers, said bin address corresponding to a texel space partion of a two-dimensional grid of bins, wherein each bin has a corresponding bin address, wherein said item identifiers are assigned unique item identifiers, assigned to a plurality of graphical image items to create said plurality of item identifiers, wherein said item identifiers are buffered as a depth texture array, said depth texture array sent to said graphics processing circuitry as a buffer of point primitives;

determining that an item identifier, of said plurality of item identifiers, is different than a previous item identifier placed at a bin address; and

streaming out said item identifier to a new working set.

2. The method of claim 1, comprising:

determining, that an item identifier, of said plurality of item identifiers, is identical to a previous item identifier placed at a bin address; and

marking said item identifier for deletion.

3. The method of claim 1, comprising:

selecting an item identifier for a bin address wherein said item identifier corresponds to a lowest depth value; and

associating said item identifier to said bin address.

4. The method of claim 1, comprising:

writing, a pass number to a bin counter contained in a color buffer.

5. The method of claim 4, comprising:

defining said plurality of item identifiers as a working set;

determining that said working set is not empty after writing said pass number; and

binding said working set to said depth texture array and sending to said graphics processing circuitry.

6. Graphics processing circuitry comprising:

programmable shader logic operative to execute programmable instructions that when executed cause the Programmable shader logic to compute a bin address for a plurality of item identifiers, said bin address corresponding to a texel space pardon of a two-dimensional grid of bins, wherein each bin has a corresponding bin address, wherein said item identifiers are assigned unique item identifiers, assigned to a plurality of graphical image items to create said plurality of item identifiers, wherein said item identifiers are buffered as a depth texture array, said depth texture array sent to said graphics processing circuitry as a buffer of point primitives;

determine by said programmable shader logic that an item identifier, of said plurality of item identifiers, is different than a previous item identifier placed at a bin address; and

streaming out said item identifier to a new working set.

7. The graphics processing circuitry of claim 6, wherein said graphics processing circuitry is further operative to:

determine, that an item identifier, of said plurality of item identifiers, is identical to a previous item identifier placed at a bin address; and

mark said item identifier for deletion.

8. The graphics processing circuitry of claim 6, wherein said graphics processing circuitry is further operative to:

select an item identifier for a bin address wherein said item identifier corresponds to a lowest depth value; and

associate said item identifier to said bin address.

9. The graphics processing circuitry of claim 6, wherein said graphics processing circuitry is further operative to:

write a pass number to a bin counter contained in a color buffer.

10. The graphics processing circuitry of claim 6, wherein said graphics processing circuitry is further operative to:

define said plurality of item identifiers as a working set;

determine that said working set is not empty after writing said pass number; and

bind said working set to said depth texture array and sending to said graphics processing circuitry.