• Advertisement
Sign in to follow this  

Find closest triangle to a position

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

If you intended to correct an error in the post then please contact us.

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
Advertisement
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
Sign in to follow this  

  • Advertisement