Sign in to follow this  
all_names_taken

Find closest triangle to a position

Recommended Posts

Which space partioning structure is most suitable for a "find closest triangle" query? The world is static and 2D. Should I go for bounding volume hierarchies, kdtrees or quadtrees? How would they compare in terms of lookup speed, space consumption and construction cost?

Share this post


Link to post
Share on other sites
EJH    315
For 2D, a uniform grid is very fast for proximity queries and fairly easy to implement. You have a grid, a 2D object index, and a function that associates an object with a particular grid cell or cells (if object is on a boundary).

- putting N objects into the index is O(n) (static objects only once at level load)
- proximity query ("what objects are near me?") is O(1) by simply looking in the adjacent cells in the object index

Note that 2D frustum culling, collision detection, AI sensor range, picking, sound radius, etc. are all basically this same query of "what is near me?" so use the same grid data structure to optimize all of them.

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