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

Question

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?

Answer 1

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?

Answer 2

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

You will add the following items to your particle system:

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

    const int maxParticles = 2000;
    int visibleCount;

// your other ParticleSystem components...
}

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.