Efficient Rendering for multiple light sources

Question

I'm building a 3D rendering engine using C++ and OpenGL.

Right now, I've added support for multiple light sources in my GLSL shaders, but I've hit a bit of a bump for my rendering methods.

I'm worried about my engines performance if it has to render a lot of objects for a lot of light sources.

The straight-forward approach would be something like this:

for every object to be rendered
    closestLights []

    for every light in the scene
        if (light closer than all lights in closestLights)
            swap furthest light from closestLights with current light

    loadLightSourcesToShader(closestLights)

    renderObject(object)

However, I'm afraid the performance of this rendering-loop will degrade quickly since when either the amount of lights or the amount of objects increases, the amount of calculations will rise even quicker.

1) Is there any way to circumvent this?

2) How is this implemented in 'real' engines?

3) How can I find the closest K lightsources to an object efficiently?

I've heard about kd-trees and octrees, but I feel like building a tree everytime I render is probably worse than what I'm thinking about doing right now.

4) I could keep an octree and a kd-tree for every object (which keeps track of all other objects), which when using (smart) pointers, could be quite efficient in terms of time (but not space?).

Is this a good approach?

I know the saying 'Premature optimization is the root of all evil', but I'm pretty sure this WILL become a problem when a game/program reaches a certain complexity/size.

Answer 1

There are, broadly speaking, two common ways to handle lots of light sources.

1. Deferred techniques involve rendering some or all the information you need about your scene for lighting to render targets. For example, you may need normals, position (calculated usually from depth) and colour, each with their own render target. Then each light is drawn as a simple shape encompassing the light's range, and in the shader it uses the corresponding colour, normals, position from those render targets to add its influence to the rendered scene. This has been popular for a long time as it makes it easy and efficient to have a lot of lights in view, but doesn't easily support transparent objects or anti-aliasing. It also gets more difficult or expensive to support more material properties.
2. Forward shading is the more traditional rendering, where an object's shader determines how it looks on screen, rather than outputting properties to a variety of render targets as in deferred shading. Different materials can handle lights differently, and transparency and anti-aliasing are straightforward. But handling an arbitrary number of lights is more difficult. Recent techniques include Forward+ and Clustered Shading, which are variations on the idea that a low-resolution texture can be prepared each frame, containing information about which lights might affect the corresponding section of the screen. Shaders can access this information by looking up the fragment's screen coordinates in a texture or two, and looping through the lights that affect that portion of the screen.

Forward+ and Clustered Shading are increasingly popular, with games like DOOM (2016) and Just Cause 3 using the latter to great effect.

I name those two games specifically, because they both have excellent resources available online detailing their lighting.