Fast proximity testing
Author
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
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.
Author
Interesting. I might consider it. Thanks.
By the way: What if the static list was also dynamic? I heard about binary Space partitioning, would it work?
By the way: What if the static list was also dynamic? I heard about binary Space partitioning, would it work?
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
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).
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
If you need exact solutions set the error tolerance to zero
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.
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.
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
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.
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.
Author
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.
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).
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).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
