# Nearest Points to Camera

This topic is 3172 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I'm implementing shadow mapping and I want to minimize the amount of lights that cast shadows. So I figured the best option would be to get the lights that affect the current viewing frustum and then from that get the 3-4 nearest lights to the camera. Does anyone know of an efficient algorithm for working out N nearest points to another point. Cheers.

##### Share on other sites
Just how many lights do you have in your scene? If its less than 100 I can't really imagine you need anything fancy, nearest point calculation is pretty inexpensive.

If for some reason you have thousands of lights in your scene and you really need to speed up the distance checking, then you probably want some kind of spatial partitioning system. Like for example if you divide the level into a 10x10 grid, then only compare distances with the cell the camera is in + 8 neighbors. Or you can use some kind of tree partitioning, but that's a bit more difficult to implement.

For speeding up distance calculation itself, only thing I can recommend is to find the minimum distance-squared, instead of distance. Gives the same result but saves having to perform the square root.

##### Share on other sites
What karwosts said is probably the best practice and I would suggest that. However, to elaborate on an exact function to find the nearest light:
Once every second{    Create new array    For each light    {        Place into new array    }    For each light in the array    {        Get distance between light position and player position    }    Sort array by distance    Set shader parameters (light 0 = array index 0, light 1 = array index 1, etc)}

If you do some spatial partitioning, do it right before you create the array.

##### Share on other sites
Thats basically the answer I was looking for. Thanks guys.

1. 1
2. 2
Rutin
19
3. 3
4. 4
5. 5

• 9
• 9
• 9
• 14
• 12
• ### Forum Statistics

• Total Topics
633294
• Total Posts
3011242
• ### Who's Online (See full list)

There are no registered users currently online

×