Spatial binning of particles on a GPU
View Patent ↗A method of performing spatial binning of particles is described which can be performed on a graphics processing unit. A stencil buffer is primed with a pattern which controls the writing of data to a framebuffer. A first shader is used to calculate the co-ordinates of the bin in which a particle is located and a second shader is used to write the particle's ID to a location representative of that bin in the framebuffer. The pattern in the stencil buffer ensures that particle data within a bin is not overwritten and the stencil buffer also maintains a record of the number of entries within each bin.
1. A method of spatial binning of particles comprising:
priming a stencil buffer with a repeating pattern of values;
in a first shader, calculating the co-ordinates of a bin for a first particle;
in said first shader, emitting an identifier of said first particle to a second shader;
in said second shader, writing said identifier to a framebuffer based on said co-ordinates;
updating an element in said framebuffer with said identifier if a comparison with a corresponding value in said stencil buffer satisfies specified criteria; and
incrementing each value in said stencil buffer which corresponds to said bin.
2. The method according to claim 1 , further comprising:
repeating said calculating, emitting, writing, updating and incrementing steps for each of a plurality of particles.
3. The method according to claim 2 , further comprising:
writing data from said framebuffer to a first texture; and
writing data from said stencil buffer to a second texture.
4. The method according to claim 1 , wherein said first shader comprises a vertex shader.
5. The method according to claim 1 , wherein said second shader comprises a pixel shader.
6. The method according to claim 1 , further comprising:
in said second shader, emitting position data for said first particle to a secondary render target.
7. The method according to claim 6 , further comprising:
writing data from said framebuffer to a first texture;
writing data from said stencil buffer to a second texture; and
writing data from said secondary render target to a third texture.
8. The method according to claim 1 , further comprising:
creating a buffer having a horizontal dimension corresponding to a total number of bins;
dividing said bins into a plurality of batches;
for each batch:
rendering a quadrilateral according to a number of bins in said batch;
in said second shader, generating a co-ordinate for each bin in said batch, fetching a number of entries in each said bin using said co-ordinate, and for each bin, emitting a running total of entries to said framebuffer; and
writing data in said framebuffer to a texture;
creating an index buffer; and
for each index:
determining a corresponding bin and in-bin location;
fetching said number of entries in said corresponding bin; and
if said in-bin location is valid, reading said running total for said bin from said texture, generating an index, fetching a particle ID for said in-bin location and writing said particle ID to an indirection table.
9. One or more device-readable storage media with device-executable instructions that, when executed by a computing system, direct the computing system to perform steps comprising:
priming a stencil buffer with a repeating pattern of values;
in a first shader, calculating the co-ordinates of a bin for a first particle;
in said first shader, emitting an identifier of said first particle to a second shader;
in said second shader, writing said identifier to a framebuffer based on said co-ordinates;
updating an element in said framebuffer with said identifier if a comparison with a corresponding value in said stencil buffer satisfies specified criteria; and
incrementing each value in said stencil buffer which corresponds to said bin.
10. A graphical processing unit comprising:
a stencil buffer;
a first shader;
a second shader;
a framebuffer; and
a plurality of textures,
wherein said first shader is arranged to:
calculate the co-ordinates of a bin for a first particle; and
emit an identifier of said first particle to said second shader;
wherein said second shader is arranged to:
write said identifier to said framebuffer based on said co-ordinates;
and wherein said graphical processing unit is arranged to:
cause an element in said framebuffer to be updated with said identifier if a comparison with a corresponding value in a repeating value stored in said stencil buffer satisfies specified criteria; and
increment each value in said stencil buffer which corresponds to said bin.
11. The graphical processing unit according to claim 10 , wherein said first shader comprises a vertex shader.
12. The graphical processing unit according to claim 10 , wherein said second shader comprises a pixel shader.