Sign in to follow this  
Shael

Nearest Points to Camera

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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this