The patent badge is an abbreviated version of the USPTO patent document. The patent badge does contain a link to the full patent document.
The patent badge is an abbreviated version of the USPTO patent document. The patent badge covers the following: Patent number, Date patent was issued, Date patent was filed, Title of the patent, Applicant, Inventor, Assignee, Attorney firm, Primary examiner, Assistant examiner, CPCs, and Abstract. The patent badge does contain a link to the full patent document (in Adobe Acrobat format, aka pdf). To download or print any patent click here.
Patent No.:
Date of Patent:
Aug. 19, 2014
Filed:
Jul. 10, 2009
Christopher Oat, Cambridge, MA (US);
Shopf Jeremy, Stewartstown, PA (US);
Joshua D. Barczak, Timonium, MD (US);
Christopher Oat, Cambridge, MA (US);
Shopf Jeremy, Stewartstown, PA (US);
Joshua D. Barczak, Timonium, MD (US);
Advanced Micro Devices, Inc., Sunnyvale, CA (US);
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.