Algorithm to draw particles in correct order?

Question

For a game I'm making as a hobbyist project, I need to be able to draw smoke on the screen. I am doing this by setting up a particle system. The problem is I need all the particles drawn in order from farthest to nearest to the camera (because the particles do have a bit of transparency, and the entire texture transparency increases over time in the particles) and I cannot figure out a way to successfully do it. Here is the code that draws each of the particles, along with the code that that is supposed to determine what order to draw them in so that it draws them from furthest from the camera to nearest to it:

    void drawSmoke( Camera cam ) {

      int drawOrder [50];

    bool particleChecked [50] = {false};

    for ( int a = 0; a < 50; a++ ) {

    int furthest;
    float furthestDistance = 0;

        for( int check = 0; check < 50; check++){

                if ( !particleChecked [check] ) {

                float aSquared = ( cam.getPosition().x - smokeParticles[check].position.x ) * ( cam.getPosition().x - smokeParticles[check].position.x );
                float bSquared = ( cam.getPosition().z - smokeParticles[check].position.z ) * ( cam.getPosition().z - smokeParticles[check].position.z );
                float cSquared = aSquared + bSquared;

                float distanceFromCamera = sqrt ( cSquared );

                        if ( distanceFromCamera > furthestDistance ) {
                        furthest = check;
                        furthestDistance = distanceFromCamera;
                        }

                }

        }

        drawOrder [a] = furthest;

    }


GLuint transformLocation = glGetUniformLocation ( particleProgram, "transform" );
GLuint alphaLocation = glGetUniformLocation ( particleProgram, "alpha" );

for( int particle = 0; particle < 50; particle++ ) {
glm::mat4 model;
glm::mat4 view;
glm::mat4 projection;

int particleToDraw = drawOrder [particle];


model = glm::translate( model, glm::vec3 ( smokeParticles [particleToDraw].position.x, smokeParticles [particleToDraw].position.y + 10.0f, smokeParticles [particleToDraw].position.z ) );
model = glm::scale(model, glm::vec3 ( smokeParticles [particleToDraw].scaleFactor ) );
glm::vec3 diff = glm::normalize ( smokeParticles[particleToDraw].position - cam.getPosition() );
float angle = atan2 ( -diff.x, -diff.z );
model = glm::rotate ( model, smokeParticles[particleToDraw].rotation , glm::rotate ( glm::vec3(0.0f, 0.0f, 1.0f), angle, glm::vec3(0.0f, 1.0f, 0.0f) ) );

//rotating particle to face camera
model = glm::rotate(model, angle, glm::vec3(0.0f, 1.0f, 0.0f));

view = glm::lookAt(cam.getPosition(), cam.getTarget(), glm::vec3(0.0f, 1.0f, 0.0f));

projection = glm::perspective( 45.0f, (float)800/(float)600, 0.1f, 5000.0f );

glm::mat4 transform = projection * view * model;

glActiveTexture( GL_TEXTURE0 );
glBindTexture( GL_TEXTURE_2D, smokeTexture );
glUseProgram( particleProgram );
glUniformMatrix4fv( transformLocation, 1, false, glm::value_ptr(transform) );
glUniform1f( alphaLocation, smokeParticles[particleToDraw].alpha );
glBindVertexArray( smokeVAO );
glDrawArrays( GL_TRIANGLES, 0, 6 );
glBindVertexArray(0);
    }

What it looks like is on each frame every element of drawOrder is the same value. But I cannot figure out why. How can I fix this?

Answer 1

Although I'm not fluent in C++ or OpenGL, there are a number of issues with this code from what I can tell. I'll describe them on a high level, and leave this answer as a community wiki, in case anyone with more specific expertise would like to refine it with specific code suggestions.

1. Your sort function, even if implemented correctly, would be O(n^2). Because you never assign the particleChecked[] flags though, it ends up assigning the single furthest particle to the drawOrder array 50 times - so it does not sort the list of particles.

   For a common task like this, I'd recommend using a standard library sorting function, which should give you a battle-tested O(n log n) solution, rather than trying to re-invent the wheel.

2. You compute distances, complete with square roots, 2500 times. To cut down on repeated work, you can store just 50 depths - each in a tuple with its particle/index, or in a parallel array - before you start sorting.

   Since you only need a relative order, not a precise distance, you can skip the square roots. Or you could replace the distance calculation with a dot product of the particle's position with the camera's forward vector, which is better-suited to billboarded particles.

3. As mentioned in a comment above, you're issuing a separate draw instruction for each particle. To scale up to large volumes of particles, you'll likely want to build a vertex buffer containing all of the particles in your sorted order, and draw them as a single batch. You can use vertex colours to control the alpha of each particle so you don't need to change uniforms for every particle.