# How does one avoid hundreds of copies into a vertex buffer each frame?

Assume a Direct3D9-based 2D game, high resolution, very busy. Performance critical.

A particle system has 2,000 particles. They are scattered throughout the world with only a subset visible on screen at any time. Thus the global array of particles contains a lot of particles that won't be rendered this frame.

Obviously they should be rendered in one call in a vertex buffer. I use an index buffer as well.

The slow bit is in the copying all of the vertex data to the buffer. I actually do this twice: once to a big buffer, then as a single copy from the big buffer to the locked vertex buffer. Regardless, I'm looking at 2,000 iterations and maybe 200-500 memcpy() calls that shuffle 4 vertices at a time.

There must be a better way. Maybe copying them all, and changing the index buffer instead? Or just rendering them all and let the off-screen ones get clipped (I'm not sure this is scalable though)?

How do people normally handle this?

• Have you profiled your code and established how much time this is taking and that it's really a performance bottleneck? Because if it isn't, then the answer is "don't worry about it". :) – Nathan Reed Nov 7 '11 at 21:51
• Definitely what Nathan said; in a particle system fillrate is far more likely to be your bottleneck than vertex buffer filling. I am curious about why you needed that second vertex buffer though... could you not have used a regular system memory array (or an std::vector) instead? – Maximus Minimus Nov 8 '11 at 0:24
• My comment was misleading. its not actually a second vertex buffer, just a memory buffer. I use it (possibly wrongly?) because I figrued it made sense to do all the scattered-through-the-code copies into a single array, and then quickly lock->copy->unlock the actual VB. Is that a good idea or a waste of time? – Cliff Harris Nov 8 '11 at 10:46
• Depends. It's an extra memory copy for sure and probably indicates that you're due some code-cleanup, but it may or may not have any measurable performance impact and you'll need to profile in order to find out. – Maximus Minimus Nov 8 '11 at 11:11

It might be worth considering using the geometry shader (or point sprites) to construct the quad. That would cut it down to one vertex per particle.

You could also consider doing a GPU based particle update, where position is simply a function of time and a few constants which you can set up once and store in the vertex when the particle is created.

A third option is to have more particle systems with less particles each that are closer together to improve frustum culling.

You could also move most of your particle system work to a separate CPU thread, and have the main thread only do lock(); memcpy(); unlock();

Which combination of the above options you want (if any) is difficult to guess without more information. For example is your game mostly GPU bound or CPU bound? What proportion of frame time is spent processing particles?

• the game seems to be CPU bound, but thats on my system, I haven't run it yet on lower spec machines. Multithreading is a good diea, but I'm not very experienced with multiple threads for stuff like this and I would fear introducing weird bugs or synchronisation issues. – Cliff Harris Nov 8 '11 at 10:44

Don't shuffle vertices around. Shuffle pointers to vertices.

You say that you have a vector in which to store raw vertex data and memory, so go along with that, and keep a second vector that contains pointers to elements in your vector of vertices (your memory buffer). Incidentally, this is the same way I figured out how to cull hardware-instanced meshes individually in the same draw call.

In short:

1. Update all the particles' positions
2. Cull the non-visible particles
3. Assign pointers to visible particles to the beginning of a vector
4. Copy vertex data referenced by the pointers to the vertex buffer
5. Draw vertex buffer with no. of visible particles as no. of vertices

class ParticleSystem
{
std::vector<ParticleVertexInfo> particleData;
std::vector<ParticleVertexInfo*> visibleParticles;

const int maxParticles = 2000;
int visibleCount;

}


particleData and visibleParticles are of the same length, defined by maxParticles. Initially, populate visibleParticles with pointers to all of particlesData just to avoid null data. visibleParticles will be partially overwritten in each frame anyways.

After updating the position of each particle, cull every vertex in particleData, and keep two numbers to increment. The first is visibleCount which will be reset to zero each frame before culling begins. A second number is inside the loop to increment by one for each vertex. For every vertex that is in view, assign a pointer to particleData.at(i) to visibleParticles.at(visibleCount), then increment visibleCount by 1.

Here's a trimmed down example of how a culling procedure might look for rearranging visible particles:

visibleCount = 0;

for (int i = 0; i < maxParticles; i++)
{
if (visible(particleData.at(i))
{
visibleParticles.at(visibleCount) = &particleData.at(i);
visibleCount++
}
}


Keep in mind that I am describing a brute-force culling method with linear time. If you are using quad-tree or other spatial culling algorithm, you would need to give a unique number identifier to each particle and use that to in place of i when assigning pointers.

Now, visibleParticles is at least partially updated with different pointers, but when it's time to render, you'll only be using the ones from the start of the vector to visibleCount. Still, you'll be able to copy the entire thing into the buffer.

Lock the vertex buffer, memcpy the visibleParticles vector into the buffer, and unlock. You now have all the updated vertices updated with one memcpy call. memcpy should be okay here, since you're guaranteed not to change the number of maximum particle elements in the vector.

Finally, draw the particles by using the value of visibleCount for the numVertices parameter in DrawIndexedPrimitive.