smooth surface approximation from unordered (x,y,z)

I'm looking for a method to fit a smooth surface to a point cloud from
a terrestrial laser scanner. The surface will be defined on regular
(xi, yi) mesh. Usually the resolution of the grid will be coarser that
the local density of points, except the no-data regions (holes). The
surface need not go through the points, but in a piecewise local least-
square manner with hole-filling and extrapolation. Non-unique z for
the same (x,y) can be just replaced by their average for now.

There's a function like that for Matlab, but it's not easy to tile the
patches together for a large dataset. I was wondering if a solution
exists in C/C++?

Thanks
Igor

rych:
> I'm looking for a method to fit a smooth surface to a point cloud from
> a terrestrial laser scanner. The surface will be defined on regular
> (xi, yi) mesh. Usually the resolution of the grid will be coarser that
> the local density of points, except the no-data regions (holes). The
> surface need not go through the points, but in a piecewise local least-
> square manner with hole-filling and extrapolation. Non-unique z for
> the same (x,y) can be just replaced by their average for now.
>
> There's a function like that for Matlab, but it's not easy to tile the
> patches together for a large dataset. I was wondering if a solution
> exists in C/C++?
>
> Thanks
> Igor

You should read the previous topis "Contour Plot algorithm for curved
contours", where similar problem is discussed. I prefer tinfoil
method, which actually is developed for relatively small number of
points- less than 1000. But, I think, this method could be enhanced
for any number of points too.

On Aug 25, 8:03*pm, Andrew_M <m...@smartfills.com> wrote:
> rych:
>
> > I'm looking for a method to fit a smooth surface to a point cloud from
> > a terrestrial laser scanner. The surface will be defined on regular
> > (xi, yi) mesh. Usually the resolution of the grid will be coarser that
> > the local density of points, except the no-data regions (holes). The
> > surface need not go through the points, but in a piecewise local least-
> > square manner with hole-filling and extrapolation. Non-unique z for
> > the same (x,y) can be just replaced by their average for now.
>
> > There's a function like that for Matlab, but it's not easy to tile the
> > patches together for a large dataset. I was wondering if a solution
> > exists in C/C++?
>
> > Thanks
> > Igor
>
> You should read the previous topis "Contour Plot algorithm for curved
> contours", where similar problem is discussed. I prefer tinfoil
> method, which actually is developed for relatively small number of
> points- less than 1000. But, I think, this method could be enhanced
> for any number of points too.

I have, Andrew, thanks, and I was tempted to add my question there.
But this one is about a least squared approximant, not an interpolant.
Besides, the number of points that I have is up to 100,000,000.

"rych" <rychphd@gmail.com> wrote in message
news:91038a29-f4c3-4c66-bf4f-f5ba0e7bed11@r35g2000prm.googlegroups.com...
> I have, Andrew, thanks, and I was tempted to add my question there.
> But this one is about a least squared approximant, not an interpolant.
> Besides, the number of points that I have is up to 100,000,000.

You also mentioned that the (x,y) values are on a regular grid, which
is important information. You did not mention in your original post
about want a "least squared approximant". I believe it is straightforward
to choose a B-spline surface with NxM unknown control points and
set up a least-squares error function of the control points using your
gridded data. The gradient of this function is set to zero (to give you
a global minimum), leading to a system of linear equations in the control
points.

I have not yet written up a document on how to do this for surfaces,
but the idea is illustrated for curves:
http://www.geometrictools.com/Sample...tDiscrete.html
At this page there is a PDF link to a document describing the algorithm.

--
Dave Eberly
http://www.geometrictools.com

On 26 Ago, 13:10, rych <rych...@gmail.com> wrote:
> On Aug 25, 8:03*pm, Andrew_M <m...@smartfills.com> wrote:
>
>
>
> > rych:
>
> > > I'm looking for a method to fit a smooth surface to a point cloud from
> > > a terrestrial laser scanner. The surface will be defined on regular
> > > (xi, yi) mesh. Usually the resolution of the grid will be coarser that
> > > the local density of points, except the no-data regions (holes). The
> > > surface need not go through the points, but in a piecewise local least-
> > > square manner with hole-filling and extrapolation. Non-unique z for
> > > the same (x,y) can be just replaced by their average for now.
>
> > > There's a function like that for Matlab, but it's not easy to tile the
> > > patches together for a large dataset. I was wondering if a solution
> > > exists in C/C++?
>
> > > Thanks
> > > Igor
>
> > You should read the previous topis "Contour Plot algorithm for curved
> > contours", where similar problem is discussed. I prefer tinfoil
> > method, which actually is developed for relatively small number of
> > points- less than 1000. But, I think, this method could be enhanced
> > for any number of points too.
>
> I have, Andrew, thanks, and I was tempted to add my question there.
> But this one is about a least squared approximant, not an interpolant.
> Besides, the number of points that I have is up to 100,000,000.

I suggest to google for "moving least squares". This method (or better
family of methods) is useful for very large data set, as computation
is performed only locally. It assumes the data set is dense and this
is not your case, as you speak of holes. Anyway there are also
variants which can deal with holes.

bite:
> On 26 Ago, 13:10, rych <rych...@gmail.com> wrote:
> I suggest to google for "moving least squares". This method (or better
> family of methods) is useful for very large data set, as computation
> is performed only locally. It assumes the data set is dense and this
> is not your case, as you speak of holes. Anyway there are also
> variants which can deal with holes.

Course, "moving least squares" is the only way to fight with huge
nember of points. On the other hand, I think, biharmonic functions are
the best way to fill holes (may be harmonics, but htey do not
guarantee smooth approximation). And method what I was talking about
can be used not only for interpolation but for approximation as well.
The only problem is to make some practical approach to full procedure.
This is interesting task, and I'm currently working with. One small
snapshot may be downloaded from http://www.smartfills.com/Html/images/isohypses.png
..

"Andrew_M" <mats@smartfills.com> wrote in message
news:1e55623c-e7b9-417f-988b-6ed2551dd29d@f63g2000hsf.googlegroups.com...
> Course, "moving least squares" is the only way to fight with huge
> nember of points. On the other hand, I think, biharmonic functions are
> the best way to fill holes (may be harmonics, but htey do not
> guarantee smooth approximation). And method what I was talking about
> can be used not only for interpolation but for approximation as well.
> The only problem is to make some practical approach to full procedure.
> This is interesting task, and I'm currently working with. One small
> snapshot may be downloaded from
> http://www.smartfills.com/Html/images/isohypses.png

If all you have is a hammer, everything looks like a nail.

--
Dave Eberly
http://www.geometrictools.com

Dave Eberly:

> If all you have is a hammer, everything looks like a nail.
>
> --
> Dave Eberly
> http://www.geometrictools.com

I'm using math, what fits better to task to be solved. Each problem
requires its own math, savvy? Large numbers of methods are used mostly
because people don't know how to to it in the best way. For 1D event
splines are the best instrument out of questions, but for the 2D no.
Therefore, I can compare splines with a hammer. What I'm actually
using is much more flexible thing. BTW, I've just realised method for
large numers of points, which needn't huge matrix and for which
required time is proportional number of points. I think, within few
days I'll send a message to this topic and put draft to my site, so
people will be able to test it and realize, if it is as efficient as I
think

Andrew_M wrote:
> Dave Eberly:
>
>> If all you have is a hammer, everything looks like a nail.
>>
>> --
>> Dave Eberly
>> http://www.geometrictools.com
>
> I'm using math, what fits better to task to be solved. Each problem
> requires its own math, savvy?

yes. Dave - I really think you ought to consider using math.


--
Kenneth Sloan KennethRSloan@gmail.com
Computer and Information Sciences +1-205-932-2213
University of Alabama at Birmingham FAX +1-205-934-5473
Birmingham, AL 35294-1170 http://KennethRSloan.com/