How can I test if a point lies within a 3d shape with its surface defined by a point cloud?

views:

172

answers:

+9 Q:

How can I test if a point lies within a 3d shape with its surface defined by a point cloud?

I have a collection of points which describe the surface of a shape that should be roughly spherical, and I need a method with which to determine if any other given point lies within this shape. I've previously been approximating the shape as an exact sphere, but this has proven too inaccurate and I need a more accurate method. Simplicity and speed is favourable over complete accuracy, a good approximation will suffice.

I've come across techniques for converting a point cloud to a 3d mesh, but most things I have found have been very complicated, and I am looking for something as simple as possible.

Any ideas?

Many thanks, Ben.

+10 A:

What if you computed the centroid of the cloud, and converted its coordinates to a polar system whose origin is that centroid.

Then, convert the point you want to examine to the same coordinate system.

Assuming the surface is representable by a Delaunay triangulation, determine the three points with the smallest difference in angle from the point you're examining.

Project the point you're examining onto the triangle determined by those three points, and see if the distance of the projected point from the centroid is larger than the distance of the actual point.

Essentially, you're constructing a triangular mesh of the convex hull, but as-needed one triangle at a time. If execution speed really matters, you might cache the resulting triangles as you go.

Steven Sudit has also suggested a useful optimization that I'd recommend if you go down this path.

Bill Carey 2010-06-16 14:42:26

This sounds like a good idea, many thanks! I will give it a try now and see if it works.I already have lists of neighboring points for each point for optimisation of another algorithm, which I could perhaps recycle to speed this up too.

Ben 2010-06-16 14:57:17

I thought about it a bit and I suspect that three ought to always be enough. This is based on the idea that the surface can be defined in terms of the triangles. So long as the point is on the side of the triangular plane that is closer to the centroid, then it is within bounds. Of course, if this assumption is wrong -- if there can be hollows and overhangs -- then none of this holds. Then again, I don't know what does; adding more points will not, on its own, suffice.

Steven Sudit 2010-06-16 15:08:39

Or, in correct terminology, I'm assuming it's a convex hull definable in terms of Delaunay triangles.

Steven Sudit 2010-06-16 15:32:40

You guys rock, thanks!

Ben 2010-06-18 19:10:26

+6 A:

I think Bill Carey's method is on the right track, but I do want to suggest a possible optimization.

Since the shape is roughly spherical, you can pre-calculate the radius of the sphere bound by it and of the sphere that bounds it. This way, if the distance of the point is within the smaller sphere, it's a definite hit and if it's outside the outer sphere, it's a definite miss.

This ought to let you resolve the easy cases very quickly. For the harder ones, Carey's method takes over.

Steven Sudit 2010-06-16 14:53:55

That's definitely a good optimization. Can I add an attributed reference to this to my answer?

Bill Carey 2010-06-16 14:57:06

@Bill, I think you just did. :)

Steven Sudit 2010-06-16 15:01:14

@Bill: See the "link" link at the bottom left of each answer? You can use that plus either markup or html to make "See Steven's nice optimization." type of link in you post... That's how I usualy manage these things.

dmckee 2010-06-16 15:42:11

It occurs to me that, with the points stored as polar coordinates, the inner and outer bounding spheres are just the min and max values for the radiuses of the points!

Steven Sudit 2010-06-16 20:19:16

Use a kd-tree.

http://en.wikipedia.org/wiki/Kd-tree

The article provides a good explanation.

I can clear up any further misunderstandings.

bearrito 2010-06-16 14:58:15

A kd-tree is relevant to the part about finding the nearest three points, though it sounds like Ben has other methods for accomplishing this.

Steven Sudit 2010-06-16 15:05:16

Can you construct a kd tree in a polar coordinate system? I haven't worked with them enough to know. If so, it might be useful.

Bill Carey 2010-06-16 15:15:08

@Bill: As far as I know, kd-trees are for Cartesian coordinates. If so, you can always convert. If not, then I'd be curious to see how they handle the problem of mixed units (angles vs. distance).

Steven Sudit 2010-06-16 15:40:12

Hmm, the other issue I'd wonder about is how they handle the problem of adjacency where an angle wraps at 360°. Cartesian coordinates have the advantage of being unique and contiguous.

Steven Sudit 2010-06-16 20:24:45

ansaurus

tags:

views:

answers:

How can I test if a point lies within a 3d shape with its surface defined by a point cloud?

related questions