Sign in to follow this  
Desperado

Fast proximity testing

Recommended Posts

Hello folks, I have the following problem: I have a list of static vertex coordinates in a cartesian coordinate space. Then I have another list of vertex coordinates that changes dynamically. What I want to do is to test for every vertex in the dynamic list the closest vertex in the static list. The naive way to do this would obviously be a 2 level for-loop that walks through all the dynamic entries and testing against every entry in the stati c list for the minimum spatial distance. My question is, is there a common method to speed this process up, for example by dividing the static list into different intervals along the x/y/z axis so I can reduce the possible testing candidates for each vertex fast? Thank you in advance

Share this post


Link to post
Share on other sites
Check out Voronoi diagrams.

Quote:
Wikipedia
For any (topologically) discrete set S of points in Euclidean space and for almost any point x, there is one point of S closest to x. The word "almost" is occasioned by the fact that a point x may be equally close to two or more points of S.

If S contains only two points, a and b, then the set of all points equidistant from a and b is a hyperplane - an affine subspace of codimension 1. That hyperplane is the boundary between the set of all points closer to a than to b, and the set of all points closer to b than to a. It is the perpendicular bisector of the line segment from a and b.

In general, the set of all points closer to a point c of S than to any other point of S is the interior of a (in some cases unbounded) convex polytope called the Dirichlet domain or Voronoi cell for c. The set of such polytopes tessellates the whole space, and is the Voronoi tessellation corresponding to the set S. If the dimension of the space is only 2, then it is easy to draw pictures of Voronoi tessellations, and in that case they are sometimes called Voronoi diagrams.

Share this post


Link to post
Share on other sites
Quote:
Original post by Desperado
By the way: What if the static list was also dynamic? I heard about binary Space partitioning, would it work?

I've never tried it, but maintaining a Voronoi diagram on a dynamic set sounds like a logistical nightmare. You'll certainly benefit from some kind of spacial partitioning (Voronoi is an example) but I imagine you could do better than BSP.

The topic has come up a few times in the past, so you may want to search the forums. I think the conclusion we landed at for large data sets was to set up an imaginary orthogonal-rectilinear partition of the space into equally-sized n-cubes (squares for 2D, cubes for 3D and so on). Keeping track of which points are in which subset is trivial, and proximity tests become localised:
If a point is in subset A (suppose we are working in two or three dimensions) and A contains more than one element, then you need only test against the points in A. If A is a singleton, then the domain extends into a the surrounding eight squares (or twenty-six cubes), and so on. Provided the points are distributed somewhat uniformly and that the mesh resolution is of an appropriate size, this can cut your working set down drastically.

Admiral

Share this post


Link to post
Share on other sites
Quote:
Original post by TheAdmiral
I've never tried it, but maintaining a Voronoi diagram on a dynamic set sounds like a logistical nightmare.


Not really. If points stay around in the same area regularly, then the simplest and fastest is to rebuild the diagram every time something moves. This is because you can use the previous Delaunay triangulation as an excellent starting point for computing the new Delaunay triangulation, so you'll do a very low number of Delaunay flips before reaching the new triangulation. The update in itself is extremely quick, and the only change in the algorithm is starting with the previous triangulation instead of an arbitrary one (so it's only an initialization change for the original algorithm).

Share this post


Link to post
Share on other sites
You could try some type of Approximate Nearest Neighbour package like ANN which is designed for solving exactly this type of problem using a couple of alternative spatial partitioning algorithms.

If you need exact solutions set the error tolerance to zero

Share this post


Link to post
Share on other sites
Voronoi diagrams are highly accurate but extremely inefficient in space - the figure O(n^3) sticks in my mind but I don't know for sure if that's correct off the top of my head. In practical terms, this means that a Voronoi-based solution will cost a ridiculous amount of memory for large numbers of points.

I did something very, very similar once upon a time when doing some photon-mapping voodoo. The best solutions I found were the canonical kd-tree method and homogenous spatial partitioning. For the kd-tree approach, store one list of points in a balanced kd-tree and iterate through the second list one point at a time, using the kd-tree to find the nearest points from the first list.

The second approach is basically what TheAdmiral describes. It can be an order of magnitude more efficient in both space and time for certain classes of problems and certain sampling patterns. If optimal behaviour is important, I would recommend trying several approaches and profiling each to find one that best suits your particular needs.

Share this post


Link to post
Share on other sites
Seem like the only suggestions so far is to maintain an acceleration structure for ALL vertices (or the dynamic?).
The OP wanted to test a set of dynamic against a set of static, not dynamic against dynamic AND static.
A simple solution would be to build a static acceleration structure (BSP, BVH etc) for the static vertices once at load time (or precompute and store on disc depending on the application).
This algorithm should be O(n) where n is the number of dynamic vertices, O(n log m) if you count the static vertices (but hey they are static, the number can't change?).

Edit: missed the
Quote:
By the way: What if the static list was also dynamic? I heard about binary Space partitioning, would it work?
so please ignore my rant above...

Edit: Space partition structures doesn't work that well with highly dynamic content IMO, you're more likely to get good performance using bounding volume hierarchies.
Especially look into BIH (Bounding interval hierarchy), a technique that the realtime raytracing guys are hyping up recently.
Since you have two sets, choose to build and maintain an acceleration structure for the LARGEST set, then test every vertex in the smaller set against the accelerator structure.

Share this post


Link to post
Share on other sites
Bounding Volumes won't exactly work for me. What I'm basically doing is implementing a surface-fitting algorithm with b-splines. The surface where the spline is fit has comparatively many points while the spline has comparatively few points. The algorithm continously updates the spline's control point set, calculates the error and refines the set again. To measure the error I need a minimum distance check for all surface points against all the sppline points.

Share this post


Link to post
Share on other sites
Do you need a minimum distance to the surface points (i.e. vertices of a mesh) or to the surface itself, i.e. to polygons between those vertices? Those are very different problems.

If all you need to check is distance to the vertices/point cloud, then store the surface points in a balanced kd-tree and query against the tree using your spline control points. That will perform quite well assuming your point cloud does not change often (and therefore the cost of constructing the kd-tree is relatively low vs. the number of queries).

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ
Voronoi diagrams are highly accurate but extremely inefficient in space - the figure O(n^3) sticks in my mind but I don't know for sure if that's correct off the top of my head. In practical terms, this means that a Voronoi-based solution will cost a ridiculous amount of memory for large numbers of points.


Are you certain? Seems to me that Euler's relationship would only yield a linear number of triangles in a triangulation, and thus a linear number of edges. So, it would only be a question of storing a linear-space search tree for the Delaunay triangulation, find the containing triangle in log-time, and then test the three vertices for proximity...

Share this post


Link to post
Share on other sites
My mistake - Voronoi diagrams are O(n^2) in 3-space. This is still a highly expensive growth curve for any significant number of sample points. However, the query for the m closest points (not necessarily closest points of approach, mind) among a set of n points should average O(m log n) time, which is quite efficient, but not necessarily more efficient than the use of a balanced kd-tree. Notably, a kd-tree can easily be stored on O(n) space and queried in O(m + log n) time.

(See specifically Aurenhammer 1991, "Voronoi diagrams - a survey of a fundamental geometric data structure" and related findings and continued work by Jensen et. al., especially the use of kd-trees for similar calculations, as collected in Jensen 2001, "Realistic Image Synthesis Using Photon Mapping".)

Share this post


Link to post
Share on other sites
Quote:
Original post by ApochPiQ
(See specifically Aurenhammer 1991, "Voronoi diagrams - a survey of a fundamental geometric data structure" and related findings and continued work by Jensen et. al., especially the use of kd-trees for similar calculations, as collected in Jensen 2001, "Realistic Image Synthesis Using Photon Mapping".)
I've mentioned this on gamedev in the past, but it's worth a repeat. The code in Jensen's book for finding nearest neighbors in a k-d tree is suboptimal; a better approach is to use the nearest neighbor search (on k-d trees) as described in one of the original reports on k-d trees:

Friedman, Jerome. Jon Bentley. Raphael Finkel. "An Algorithm for Finding Best Matches in Logarithmic Expected Time." ACM Transactions on Mathematical Software, vol. 3, no. 3, pp. 209-226, September 1977. See also: ftp://reports.stanford.edu/pub/cstr/reports/cs/tr/75/482/CS-TR-75-482.pdf

It's the "ball within bounds" stuff that they talk about in that report. Unfortunately their description of the algorithm is rather densely explained. There are other papers on the net that explain it better, but I don't have a reference off the top of my head. I give a clear explanation in my book also (pp 320-321).

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