Yo, this is Solid here. I'm in a bit of a bind here.

I was wondering what method to people generally use to determine which dynamic lights can affect which objects?

For instance, I have a lighting shader that supports only up to 8 lights. I have over 20 dynamic lights in my scene, and over a hundred objects with only around 6-7 lights within range of them. I want the objects to know which lights affect them, and the lights to know which objects it will use to generate shadow maps.

How do I go about determining which lights belong to which objects, in an efficient way?

I already wrote a collision test that loops through every light and then through every mesh to check for collision with sphere vs sphere tests, and it works just fine, except it is rather slow, and takes up around 3-4 ms on my laptop, and 0.8 - 1.0 ms on my computer. It is a tad slow, and I want to speed it up some more. Also I use frustum culling to cull lights that are out of view.

I came up with the idea of using an octree, to separate all the static objects on the first frame, and then each frame add and remove the dynamic objects/lights. Each node has an std::vector for storing objects as well as their rendering/lighting/physics/ components, if it has one.

Then after, I am planning to do a sweep and prune for every separate node in the quadtree on the x and z axis, and then store the light vs object collision pairs in an std::vector.

And then last but not least, I can just iterate through every collision pair and push the meshes that collide into an std::vector inside of the lighting component it collides with for shadow map rendering, as well as add data from the lighting component into the mesh component so that it knows which light it gets affected by.

Although this may sound like a good idea, I fear that it might actually be slower. I mean, I am using a lot of std::vectors, and creating them every frame in the octree (for dynamic objects), and constantly filling/flushing vectors in the lighting components.

I was wondering if there is a more efficient method, or is this as good as it can get? What other methods are other people using for this sort of thing? I'm guessing I may have to just tone down the number of dynamic lights ultimately, since they are very expensive in general. I can do the collision test only once for static lights.

What are your recommendations?

Maybe this link will help:

http://gamedev.stackexchange.com/questions/64492/how-to-opitimize-shadows-in-unity-3d

Twenty lights and a couple hundred objects? Brute force sphere-sphere testing should be nearly instant in this case. You're doing something wrong there.

I was going to echo what Promit said.

even 500 objects against 20 lights would only be 10,000 checks - which isn't ideal but should still be pretty fast.

I guess the issue comes from how you do your prioritising, do you choose the 1st 8 lights you find or do you also check each light against the current light list to ensure only the 8 closest ones are used? You might get away with just picking the 1st 8, then there is no swapping or rejecting etc...

You could do a sweep and prune type thing if you wanted in 1 or 2 dimensions and that should reduce the number of checks you do by quite a bit.

Also anything that is static and predictable should be handled separately if you can - but this won't work if your situation means everything is dynamic.

I want the objects to know which lights affect them, and the lights to know which objects it will use to generate shadow maps ... Also I use frustum culling to cull lights that are out of view.

You can't do that for shadow mapping as off-screen lights can cast shadows into the view volume.

No they can't. If you want to have finite bounding volume for light this also mean you need to modify falloff function to go zero when at max range. so shadows can't cast outside of light range.

edit: Assuming frustum vs bounding sphere culling.

Yes, that is what i'm doing. I did a test with a small bias of 0.1f offset and the lights shadows still appear just before the bias is breached. The frustum culling is working. Might I add that I am also checking for 6 frustum cullings around the point lights, to check which sides of the shadow maps get which meshes.

Twenty lights and a couple hundred objects? Brute force sphere-sphere testing should be nearly instant in this case. You're doing something wrong there.

I forgot to add, I am doing 6 frustum cullings per light since they are point lights that use shadow cube maps. This is only done for dynamic lights though.