Creating a mesh from scattered x,y,z points

Hi,

How can I create a close or open surface which passes through some (x,y,z) points (scattered points)in space?

When I use mesh(x,y,z) MATLAB thinks that z is the value of a function at x and y.

x, y, and z are column vectors.

Answer 1

[Walter Roberson]

There is no unique solution unless you add a bunch of constraints.

Suppose you have the finite cloud of points and you create an arbitrary plane passing through the cloud. If you treat the points as infinitesimal and you choose the plane at random, the probability that the plane will exactly pass through any of the points approaches 0, so you should be able to easily find a plane that partitions the cloud in to two pieces. Now, generate your hypothetical surface following the "outside" of the cloud, but indenting far enough into the cloud to nearly cut it in half but then flowing out again along the "top" and "bottom" of the two partitions.

Now, there is nothing in the cloud that inherently disproves this indented surface as being "the right" surface. And there are a quite large number of different possible partitions of the cloud in to two subsets. You can't disprove it, and there are lots of ways it could happen. Especially if you let the indent be smaller and smaller until it is only "incorrectly" going in one or two points: whether any particular indentation is "incorrect" or not becomes completely arbitrary and undecidable.

Unless, that is, you impose some serious constraints.

===

I seem to recall that John d'Errico mentioned having done some work based upon convex hulls and alpha shapes.

[John D'Errico]

I've got a general n-dimensional alpha shape code, but it is not always a good scheme for recovering a surface when the surface is not fully closed. (I did put together the beginnings of a tool based on a totally different idea, but it was only an outline, and lies unfinished as yet.) Anyway, in general I might look at established schemes like CRUST. Luigi Giacarri has done work on surface reconstruction from scattered data. I'd start there.