# Zabot's Diary

## Multi-Light Rendering and Voronoi Diagrams

Posted by Zabot on 29 June 2016 in English (English).

I spoke with B4sti and Tordanik last week about how to best attack shading with multiple light sources. As it stands, OSM2World can only handle a single light source, the sun. Adding any individual light source is not so much of a problem, some tweaks to what information is passed to the graphics card and now you have another light source. The problem is one of scalability. OpenGL breaks the faces of shapes to be rendered up into fragments. Each fragment must have its color calculated individually, based upon several factors, including the lighting. To add a second light source would require every fragment to consider both light sources. As you keep adding lights, each fragment must consider every light. This may not seem so bad, but there may be hundreds of thousands of fragments in a single frame. If each fragment has to consider 10 lights, thats one million calculations, and it only gets worse from there. But one could easily imagine a city scene with more then 10 lights, even just a highway with street lights would have more than that.

We can makes things a little bit easier on ourselves by only considering the closest light to each fragment. While this means we only have to do the lighting calculations for a single light source at each fragment, we still need to test the distance to every light source to find the shortest. We need some method to precompute the closest lighting source to each fragment so we can avoid the timing consuming process of calculating it. Unfortunately, we have no way of knowing where a fragment is ahead of time.

The solution we came up with is similar to the concept of a Voronoi Diagram. A Voronoi diagram is a mapping of points on a continuous plane to a finite set of seed points such that each point is mapped to the closest possible seed point.

(Each colored region would be affected by the lighting source closest to the vertex in that region)

If we imagine each seed point to be a vertex in our world geometry, then each vertex could be assigned a precomputed closest light source, and every point in the region belonging to that vertex would use that light source for its calculations. Typically, if we were to assign an ID to each vertex, OpenGL would use those values to interpolate the value for a fragment between those vertices. But by tweaking the behavior of this interpolation, we can make a fragment take the value from the closest vertex without interpolating it, and without performing any additional calculations. If we know already know which light is the closest, the calculation no longer depends on how many lights are in the scene, and the number of lights could be much greater.