Sorting objects to be rendered by their state

Question

I'm writing a renderer to learn my way around OpenGL and right now I'm trying to understand how to sort the objects to be rendered. As I understand there are a few rules to this:

• Sort to minimize state changes (like glUseProgram)
• Sort solid objects from transparent objects
  • Sort the solid ones front to back, to decrease overdraw
  • Sort transparent ones back to front to make sure the ones in front don't hide the ones in the back.
• Sort by mesh to use instancing (?)
• Sort by materials (which is sorting by state I suppose)

What I have so far works and I get over 100 FPS but I'm not sure my approach is correct. Also, my processor and video card are pretty good, so I don't know how telling the FPS really is.

First I have a few classes that compose the state and material.

struct opengl_state
{
    GLclampf alpha_ref;
    GLenum alpha_func;
    GLenum blend_sfactor;
    GLenum blend_dfactor;
    GLenum cull_mode;
    GLenum depth_func;
    bool alpha;
    bool blend;
    bool cull;
    bool depth;
    opengl_state() = default;
    static opengl_state initial_state();
    bool operator<(const opengl_state& other);
    void set_state() const;
    inline bool transparent()
    {
        return alpha || blend;
    }
};

opengl_state opengl_state::initial_state()
{
    opengl_state state {};
    std::memset(&state, 0, sizeof(opengl_state));

    state.alpha_ref = GL_ALWAYS;
    state.alpha_func = 0;
    state.blend_sfactor = GL_ONE;
    state.blend_dfactor = GL_ZERO;
    state.cull_mode = GL_BACK;
    state.depth_func = GL_LESS;
    state.alpha = false;
    state.blend = false;
    state.cull = true;
    state.depth = true;

    return state;
}

bool opengl_state::operator<(const opengl_state& other)
{
    return std::tie(alpha, blend) < std::tie(other.alpha, other.blend);
}

struct render_pass
{
    opengl_state state = opengl_state::initial_state();
    luck::program* program = nullptr;
    std::unordered_map<std::string, texture*> textures;
    std::unordered_map<std::string, glm::vec2> vec2;
    //Other types (like vec3/mat4/etc are omitted)
    render_pass(luck::program* program) : program(program) {}
    bool operator<(const render_pass& other);
};

bool render_pass::operator<(const render_pass& other)
{
    return state < other.state;
}

struct material
{
    std::vector<render_pass> passes;
    material(render_pass pass1)
    {
        passes.push_back(pass1);
    }
};

They can be sorted, which is something that can be used in the rendering step.

Then I have some structs to help me organize the scene, I can't simply sort the meshs because they can have more than one pass, so I split a single mesh into several passes. And then sort these passes.

struct _Uniforms
{
    luck::entity entity;
    std::unordered_map<std::string, texture*> textures;
    std::unordered_map<std::string, glm::vec2> vec2;
    //Other types (like vec3/mat4/etc are omitted)
};

struct _Meshs
{
    luck::mesh* mesh;
    std::vector<_Uniforms> uniforms;
};

struct _Programs
{
    luck::program* program;
    std::vector<_Meshs> meshs;
};

struct _States
{
    luck::opengl_state state;
    std::vector<_Programs> programs;
};

And this is the render function, run every frame

void renderable_system::render(luck::entity current_camera)
{
    auto& c_spatial = current_camera.getComponent<spatial_component>();

    glm::mat4 mat_projection = camera_system::calculate_projection(current_camera);
    glm::mat4 mat_view = camera_system::calculate_view(current_camera);

    //Query for objects inside the frustum, this returns every object with a spatial_component
    auto entities = _spatial_system->_tree.query_frustum(mat_projection * mat_view);

    //Remove objects without the mesh component
    entities.erase(std::remove_if(entities.begin(), entities.end(),
    [](luck::entity e)
    {
        return !e.hasComponent<mesh_component>();
    }), entities.end());
    //sort by the first pass, shader and mesh (implementation bellow)
    std::sort(entities.begin(), entities.end(), sort_renderables);

    std::vector<_States> states;
    if(entities.size()) //push the first state/program/mesh and uniform to the list
    {
        auto e = entities[0];

        auto& e_mesh = e.getComponent<mesh_component>().mesh;
        auto& e_pass = e.getComponent<mesh_component>().material.passes[0];

        states.push_back(_States {});
        states.back().state = e_pass.state;

        auto& state = states.back();
        state.programs.push_back(_Programs {});
        state.programs.back().program = e_pass.program;

        auto& program = state.programs.back();
        program.meshs.push_back(_Meshs {});
        program.meshs.back().mesh = e_mesh;

        auto& mesh = program.meshs.back();
        mesh.uniforms.push_back(_Uniforms {});
        mesh.uniforms.back().textures = e_pass.textures;
        mesh.uniforms.back().vec2 = e_pass.vec2;
        mesh.uniforms.back().entity = e;
    }

    //Add every object to a tree structure. It can be traversed 
    //and we can be sure that if a group of entites has the same state, 
    //the state won't change between then.
    for(auto & e : entities)
    {
        auto& e_mesh = e.getComponent<mesh_component>().mesh;
        //auto& e_material = e.getComponent<mesh_component>().material;
        auto& e_pass = e.getComponent<mesh_component>().material.passes[0];

        auto& state = states.back();
        auto& program = state.programs.back();
        auto& mesh = program.meshs.back();
        //He we are guaranteed to have at least one base state to start from, we can compare and fill the other entities now

        if(!(e_pass.state < state.state) && !(state.state < e_pass.state)) //we have the same state, check the program
        {
            if(e_pass.program == program.program) //we have the same program, check the mesh
            {
                if(e_mesh == mesh.mesh) //we have the same mesh, just add our uniforms to the list
                {
                    mesh.uniforms.push_back(_Uniforms {});
                    mesh.uniforms.back().textures = e_pass.textures;
                    mesh.uniforms.back().vec2 = e_pass.vec2;
                    mesh.uniforms.back().entity = e;
                }
                else //different meshs, lets add another one under this program
                {
                    program.meshs.push_back(_Meshs {});
                    program.meshs.back().mesh = e_mesh;
                    program.meshs.back().uniforms.push_back(_Uniforms {});
                    program.meshs.back().uniforms.back().textures = e_pass.textures;
                    program.meshs.back().uniforms.back().vec2 = e_pass.vec2;
                    program.meshs.back().uniforms.back().entity = e;
                }
            }
            else //different program, lets add another one under this state
            {
                state.programs.push_back(_Programs {});
                state.programs.back().program = e_pass.program;
                state.programs.back().meshs.push_back(_Meshs {});
                state.programs.back().meshs.back().mesh = e_mesh;
                state.programs.back().meshs.back().uniforms.push_back(_Uniforms {});
                state.programs.back().meshs.back().uniforms.back().textures = e_pass.textures;
                state.programs.back().meshs.back().uniforms.back().vec2 = e_pass.vec2;
                state.programs.back().meshs.back().uniforms.back().entity = e;
            }
        }
        else //finally, we have a new state
        {
            states.push_back(_States {});
            states.back().state = e_pass.state;
            states.back().programs.push_back(_Programs {});
            states.back().programs.back().program = e_pass.program;
            states.back().programs.back().meshs.push_back(_Meshs {});
            states.back().programs.back().meshs.back().mesh = e_mesh;
            states.back().programs.back().meshs.back().uniforms.push_back(_Uniforms {});
            states.back().programs.back().meshs.back().uniforms.back().textures = e_pass.textures;
            states.back().programs.back().meshs.back().uniforms.back().vec2 = e_pass.vec2;
            states.back().programs.back().meshs.back().uniforms.back().entity = e;
        }

    }

    glPushAttrib(GL_ENABLE_BIT);

    //after all that, just loop through everything and render
    for(auto & state : states)
    {
        state.state.set_state();

        for(auto & program : state.programs)
        {
            auto program_id = program.program->id;

            glUseProgram(program_id);
            glUniformMatrix4fv(glGetUniformLocation(program_id, "view"), 1, GL_FALSE, glm::value_ptr(mat_view));
            glUniformMatrix4fv(glGetUniformLocation(program_id, "projection"), 1, GL_FALSE, glm::value_ptr(mat_projection));
            glUniform3fv(glGetUniformLocation(program_id, "camera_position"), 1, glm::value_ptr(c_spatial.position));

            for(auto & meshs : program.meshs)
            {
                auto mesh = meshs.mesh;

                glEnableVertexAttribArray(glGetAttribLocation(program_id, "position"));
                glBindBuffer(GL_ARRAY_BUFFER, mesh->buffers[luck::mesh::buffer_type::VERTEX]);
                glVertexAttribPointer(glGetAttribLocation(program_id, "position"), 3, GL_FLOAT, GL_FALSE, sizeof(mesh_data_resource::vertex), (void*)offsetof(mesh_data_resource::vertex, x));

                glEnableVertexAttribArray(glGetAttribLocation(program_id, "texcoord"));
                glBindBuffer(GL_ARRAY_BUFFER, mesh->buffers[luck::mesh::buffer_type::VERTEX]);
                glVertexAttribPointer(glGetAttribLocation(program_id, "texcoord"), 2, GL_FLOAT, GL_FALSE, sizeof(mesh_data_resource::vertex), (void*)offsetof(mesh_data_resource::vertex, u));

                //sort_renderables2 sorts entities by their distance to the camera (implementation later)
                std::sort(meshs.uniforms.begin(), meshs.uniforms.end(), sort_renderables2(c_spatial.position, state.state.transparent()));

                for(auto & uniforms : meshs.uniforms)
                {
                    auto e = uniforms.entity;

                    auto& spatial = e.getComponent<spatial_component>();
                    glm::mat4 mat_model(1.f);
                    mat_model = glm::translate(mat_model, spatial.position);
                    mat_model = mat_model * glm::toMat4(spatial.rotation);
                    mat_model = glm::scale(mat_model, spatial.scale);

                    glUniformMatrix4fv(glGetUniformLocation(program_id, "model"), 1, GL_FALSE, glm::value_ptr(mat_model));

                    auto gl = GL_TEXTURE0;
                    for(auto texture : uniforms.textures)
                    {
                        glActiveTexture(gl++);
                        glBindTexture(GL_TEXTURE_2D, texture.second->id);
                    }

                    for(auto vec2 : uniforms.vec2)
                    {
                        glUniform2f(glGetUniformLocation(program_id, vec2.first.c_str()), vec2.second.x, vec2.second.y);
                    }

                    glUniform1f(glGetUniformLocation(program_id, "time"), glfwGetTime());

                    glBindBuffer(GL_ELEMENT_ARRAY_BUFFER, mesh->buffers[luck::mesh::buffer_type::ELEMENT]);
                    glDrawElements(GL_TRIANGLES, mesh->element_number, GL_UNSIGNED_INT, (void*)0);
                }
            }
        }
    }

    glPopAttrib();

    return;
}

These are the sorting functions:

bool renderable_system::sort_renderables(const luck::entity& a, const luck::entity& b)
{
    return std::tie(a.getComponent<mesh_component>().material.passes[0], a.getComponent<mesh_component>().material.passes[0].program, a.getComponent<mesh_component>().mesh)
           <
           std::tie(b.getComponent<mesh_component>().material.passes[0], b.getComponent<mesh_component>().material.passes[0].program, b.getComponent<mesh_component>().mesh);
}

//auto as a return type issues a warning in gcc with c++11,
//but works with c++1y. I don't know how else to return a lambda
//without using std::function.
auto sort_renderables2(glm::vec3 camera_position, bool transparent)
{
    return [camera_position, transparent](const _Uniforms & ua, const _Uniforms & ub) -> bool
    {
        auto a = ua.entity;
        auto b = ub.entity;
        if(transparent)
        {
            return glm::distance(camera_position, a.getComponent<spatial_component>().position) > glm::distance(camera_position, b.getComponent<spatial_component>().position);
        }
        return glm::distance(camera_position, a.getComponent<spatial_component>().position) < glm::distance(camera_position, b.getComponent<spatial_component>().position);
    };
}

Two other things:

1. I'm just rendering the first pass right now because I wasn't sure how to handle other passes (I'm not even sure if it's going to work).

2. I'm not sure if it's clear, but I'm using an entity/component framework (anax), if any of the systems or components are unclear just by their names (or the name of their methods) let me know.

Answer 1

Tips on coding style:

Names starting with an underscore _ are reserved for use by the C++ implementation and should definitely be avoided. I believe that you have defined the types _Uniforms, _Meshs, _Programs and _States with an underscore in the name to make them internal/private to your library. If this is the case, then remove the starting _ and place them inside a namespace named something like internal, priv or detail. Preferably, place all code from your library inside a namespace an place private library detail inside a child namespace of your library's main namespace.

---

You use some very long lines. Long lines are a common source of bugs. Take this one for example:

glVertexAttribPointer(glGetAttribLocation(program_id, "texcoord"), 2, GL_FLOAT, GL_FALSE, sizeof(mesh_data_resource::vertex), (void*)offsetof(mesh_data_resource::vertex, u));

It would be far more readable to break it:

glVertexAttribPointer(
    /* index      = */ glGetAttribLocation(program_id, "texcoord"), 
    /* size       = */ 2,  
    /* type       = */ GL_FLOAT, 
    /* normalized = */ GL_FALSE, 
    /* stride     = */ sizeof(mesh_data_resource::vertex), 
    /* pointer    = */ (void*)offsetof(mesh_data_resource::vertex, u));

Notice that I've also added a comment to name the function parameters. This can be very helpful to people unfamiliar with some of the libraries used in the project, in this case, OpenGL.

---

The method renderable_system::render() is massive! You can break it into quite a few more specific subroutines. This will make it a LOT more readable and less intimidating. To name a few, you could separate it into the tasks: compute_transforms, sort_objects, build_state_list, do_render. You can probably break it even further, these are just a few of the helper functions you can introduce.

---

I like to align similar assignment statements, such as initialization of several variables. On opengl_state::initial_state(), I suggest that you reformat to:

opengl_state opengl_state::initial_state()
{
    opengl_state state {};
    std::memset(&state, 0, sizeof(opengl_state));

    state.alpha_ref     = GL_ALWAYS;
    state.alpha_func    = 0;
    state.blend_sfactor = GL_ONE;
    state.blend_dfactor = GL_ZERO;
    state.cull_mode     = GL_BACK;
    state.depth_func    = GL_LESS;
    state.alpha         = false;
    state.blend         = false;
    state.cull          = true;
    state.depth         = true;

    return state;
}

---

inline is not necessary when the method is defined directly inside the body of the class declaration:

inline bool transparent()
{
    return alpha || blend;
}

From opengl_state can be just:

bool transparent()
{
    return alpha || blend;
}

Also, is_transparent() would be a better, more descriptive name, for the method above.

At the end of renderable_system::render(), there is a superfluous return;. Your should remove it.

---

A few tips on performance and OpenGL:

You are calling glGetAttribLocation() and glGetUniformLocation() inside renderable_system::render(). This is a waste since the values never change and the strings passed are constants. You should query the locations on startup and cache the values inside named variables. E.g:

GLint viewLocation = glGetUniformLocation(program_id, "view");
// and store 'viewLocation' somewhere. Probably inside a ShaderProgram class...

---

You can speed rendering quite a bit by using VAOs. It is very likely that your video card supports VAOs, since you are already using shaders.

While you are at it, switch to core profile OpenGL and ditch those calls to glPushAttrib.

As to sorting, I suggest that you completely separate solid from translucent objects and render them on separate passes. Sort the translucent ones back-to-front as you do now.

I'm not sure if there is going to be any gain by sorting the solid ones in front-to-back order. The level of overdraw is usually not that big on most scenes. You will have to profile to find that out.

When defining your sorting predicates, refer to this "hot-cold" list of OpenGL states.