   Nearest lights in outdoor scene.
  Hello,I have a problem with outdoor environment: I need to find lights affecting particular objects. How would I do that with quadtree/octree? Or maybe there are some more suitable structures?The obvious solution is to store visible quad/oct nodes in light objects. And to find lights affecting object just traverse the tree up to the root and collect lights connected to tree nodes (with additional light planes testing against object bounding box if the tree node is only partially visible by light) - but I'm afraid this would be too much overhead.I would appreciate any ideas   
  I'm pretty certian you're going to want a heuristic based search over the quad-tree. Now I've never done this, but here's what I suggest. First, get the bearing of the center of the cell you are in, to the center of the cell for each light. Now by doing this, we can give our search.For example, let's say that our light is bearing 45° from our quad node. This means that the light is either in the top-right, or bottom-left node. Now, we can just traverse from our location in the tree, up and only search the 2nd and 3rd nodes (assuming the coroespond to the top left/bottom right nodes). This elimites half of the searching.I don't know if that's at all what you want, but I'm just shouting out what came into my head.You might also want to look at A* with mulitple exit points, and A* will choose the quickest route. Remember, A* is just a way of traversing a graph, doesn't necessarily have to be a games map.Hope something in that help.   ;  I'm not finished with the lighting system in my engine, so this is highly theoretical.  It seems like there are a lot of factors that would affect what solution would be best.  First, how many objects are we talking about, and how many lights.  Second, are you applying the light list to the entire frustum, to each quad/oct, or are you building a seperate light list for each object.  Personally, I just keep my lights in a list and for each object (or quad or frustum) build a light list made on certain heuristics (cromacity, intensity, distance).  I like this because each object then gets lit by whatever lights affect it most, and if you don't have that many lights in your scene, it's not that bad.  I suppose the other way to do it would be to start with all lights in the same node as the object, and then work your way out untill you fill your list.  This would probably require that any given node have pointer to it's siblings and parent.  The thing I don't like so much about that is that light is not necessarily a spacial problem.  For instance, your lighting system only allows one or two lights per object.  Your character has two or three glowing fireflies around him.  In the near distance, there is a bright red magical explosion, and in sky there is the moon.  A spatial system that stops after finding the first few lights would only light the character with the firefly, where the explosion and moon should have more weight.  That's why I prefer to traverse the entire list.  What I think would make for an interesting system, however, would be some kind of occlusion query, That way you don't bother turning on a light if it's on the other side of a hill or covered by forest.  Has anyone tried anything like this?   