Re: How to find closest point(s) around a specific point in point cloud?
- From: "cr88192" <cr88192@xxxxxxxxxxx>
- Date: Mon, 31 Mar 2008 07:42:18 +1000
"robert" <robert.kj.karlsson@xxxxxxxxx> wrote in message news:41d03ff0-b3a2-4f54-8c80-1fc93ba227f0@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
I can't find any site with information about the simplest way to
locate the n number of closest points adjacent to a point in a 3d
point cloud with scattered data.
Basically, I've got an array, call it V, with a couple of hundred
positions [x,y,z] and a value (eg [0-100).
Let's say I wanted to pick the 5 closest points around a specific
point, call it P, with a value like [x,y,z] = [10,20,30]
I'm going to have to write functions in different languages, so some
generic pseudo code would be great.
the simplest way, is likely a linear search.
one scans the cloud, calculating the distance to each point, and keeping track of the closest matches.
one can do this in multiple passes, using an array to avoid re-including previous points (this basically amounts to a special case of selection sort).
slightly more efficient, is to use a sort function (qsort, for example, with the comparrison being the distance from the point, and analogous functions in other languages, or one can roll their own). then, one then just grabs the first N points in the sorted output.
this may infact be the best approach if one is doing a "one-off" query (aka: there is little intention of repeating the query numerous times, raw performance is not all that important, or the following options are just too complicated).
potentially more efficient (especially if the cloud may be used numerous times, for example, it represents a 3D model or similar, or one is looking for the closest points from a decent number of potential locations), is to make use of a binary tree (such as a KD or BSP tree).
finding the closest point is really easy, but n-closest is a little harder (different possibilities exist with differing levels of accuracy and complexity).
simple example:
one walks the tree (top down), finding the closest points on each side of the partition;
the N closest points are within this set if (n<log2(m)) (where m is the total size of the cloud).
should be about O(log2(m)^2).
otherwise, one can mark each exhausted node (a leaf is marked exhausted and not considered on the next run, and a node is exhausted if both subnodes have been exhausted).
this process is repeated until a sufficient number of points has been located.
should be about O((n/log2(m))*log2(m)^2)
alternatively, one can do a bottom-up search, but this may not necessarily return the closest points (if near a larger dividing plane, for example, but may be very fast).
a spherical query is also possible, but is problematic (the size of the sphere is very important, but may not be known prior to the query, which would require iteration).
such sphere queries, however, are very useful in the case of physics simulation or in a particle engine, where such a sphere can represent the range of possible collisions or interferences (objects outside the sphere are assumed, simply, to not exist...).
for example, an object has exploded, do a radius query to find any other objects damaged, or to apply said explosive forces to the objects (or, in actual scenes, using linechecking or volume tracing to figure out which objects are effected and how, ...).
and so on...
Robert Karlsson
.
- Follow-Ups:
- References:
- Prev by Date: Re: How to find closest point(s) around a specific point in point cloud?
- Next by Date: Re: Question concerning object-oriented programming
- Previous by thread: Re: How to find closest point(s) around a specific point in point cloud?
- Next by thread: Re: How to find closest point(s) around a specific point in point cloud?
- Index(es):
Relevant Pages
|
