Surface reconstruction with irregular x and y sampling

I am pretty sure you could use image compression scheme, as a modified jpeg (to handle single-channel images) or wavelet-based algorithm.

Perhaps this would be sledgehammering a nut, but why not treat the grid as completely irregular and use something along the lines of a 2D Bézier or B-spline approach to interpolate the entire surface? From the reconstructed surface, you could perform a complete resample, using some adaptation of minmax to align the new abscissas optimally.

If you need something a bit more powerful, another idea is to iteratively redistribute the nodes according to their proximities. There may be a name for what I'm about to describe, but I've never heard of it.

Treat each node as a charged particle that attracts others according to some norm (I'd suggest an inverse-square-sum on the x and z axes). Have each node impose a 'pull' on its neighbours. Once each node knows its net pull-direction, you could use wavelets/Fourier or finite-differencing to determine the localised gradient along which it should move. You should probably want to fix the boundary nodes in space. Repeating this process until things stagnate, clusters of nearby nodes will tend to unify. It is then your job to tweak the parameters to optimise distribution.

Now a twist on this idea would be to have the nodes repel one-another instead, by simply inverting the sign of the inter-node forces.

Of course, the repulsive method will tend to form a uniformly-spaced grid, which is great, but it won't reduce your resolution at all. Conversely, the attractive method would quickly cut down the working set, but it is unstable, as equilibrium won't be achieved until huge gaps form in the terrain.
The final piece of the puzzle is to use both techniques simultaneously, where the attractive force is strong with a small range, and the repulsive force weaker over a larger range (much like the nuclear forces in the atom).
You have, effectively three independent parameters to get right, but the resulting algorithm should be pretty fast, scalable and you have the bonus of trading off run-time against mesh-homogeneity.

Admiral

Thank you for the replies. Gjaegy: I was hoping for something more specific, but thank you for trying anyways.

Admiral:

Quote:

Original post by TheAdmiral Perhaps this would be sledgehammering a nut, but why not treat the grid as completely irregular and use something along the lines of a 2D Bézier or B-spline approach to interpolate the entire surface? From the reconstructed surface, you could perform a complete resample, using some adaptation of minmax to align the new abscissas optimally.

This one is not a bad idea. I had considered using a B-spline with its knot points being the current samples, then finding the derivative of the entire surface as a function of x,z and then finally resampling appropriately. I may still use this technique...

Quote:

Original post by TheAdmiral If you need something a bit more powerful, another idea is to iteratively redistribute the nodes according to their proximities. There may be a name for what I'm about to describe, but I've never heard of it. Treat each node as a charged particle that attracts others according to some norm (I'd suggest an inverse-square-sum on the x and z axes). Have each node impose a 'pull' on its neighbours. Once each node knows its net pull-direction, you could use wavelets/Fourier or finite-differencing to determine the localised gradient along which it should move. You should probably want to fix the boundary nodes in space. Repeating this process until things stagnate, clusters of nearby nodes will tend to unify. It is then your job to tweak the parameters to optimise distribution. Now a twist on this idea would be to have the nodes repel one-another instead, by simply inverting the sign of the inter-node forces. Of course, the repulsive method will tend to form a uniformly-spaced grid, which is great, but it won't reduce your resolution at all. Conversely, the attractive method would quickly cut down the working set, but it is unstable, as equilibrium won't be achieved until huge gaps form in the terrain. The final piece of the puzzle is to use both techniques simultaneously, where the attractive force is strong with a small range, and the repulsive force weaker over a larger range (much like the nuclear forces in the atom). You have, effectively three independent parameters to get right, but the resulting algorithm should be pretty fast, scalable and you have the bonus of trading off run-time against mesh-homogeneity. Admiral

This sounds quite interesting as well, but I had one question on implementation. When deciding the attractive or repulsive forces, what should be the 'distance' parameter? For example, I don't want to lump together a cluster of nodes based only on their distance from one another - it must be based somehow on the original shape of the mesh. If it was only on distance then any high frequency areas would be lost since the sampling points are very close together.

I suppose that is the tuning that you were talking about [grin][grin]

This has given me a good starting point, thanks again for the help!

You could perform a high-pass filter over the data to determine areas of high-frequency, and then weight nodes in those areas more heavily.

Have you considered normalized convolution? It might be very effective if the irregular samples are picks from regularly sampled data set. Basic idea is

     K * DR = -------     K * Iwhere R is the result array, K is some smoothing kernel (such as gaussian), D is the irregularly sampled data on regularly sampled grid, I is information whether given grid location is valid sample and * is the convolution operator.I[j] = 1, if D[j] is a valid sampleI[j] = 0, otherwiseD[j] = sample[j], if (i,j) is the position of a valid sampleD[j] = 0,            otherwise

I have used two-sided exponential kernel, which can be very efficiently implemented as an IIR-filter, with a success.

Some information about normalized convolution

Zipster, thanks for the suggestion. I am doing something similar now with the dot product method that I mentioned before - it is basically detecting the sharpest gradients and not selecting them for reduction. So your method is very suitable for what I am doing.

Winograd, thanks for the suggestion. However, I think this case is for when you undersampled something (i.e. some info is missing) instead of when you want to downsample or reduce the resolution of something. It is still an interesting technique that I had not heard of before, so it was still helpful! [grin]

I have a basic prototype up and working with my original dot product method. Now I am developing a couple of different methods for determining how much error there is between the original mesh and the reduced mesh. This is another interesting topic since you can have quite different results with error calculations.

For example, when you use the volume difference between the two meshes you get a different error amount than if you compare the sum of the height differences at each of the original sampling points. I plan to use a combination of a few different error calculations - the user will be able to select a different error metric to use if he/she desires.

Thanks for all the help and suggestions!

Ah, I misread your post.

In your case, it is essential to find an error metrics reflecting the subjective quality of the result. Problem is similar to compressing audio or imagery. Lossy algorithms have a model (for example psychoacoustic model) which is used as a part of the error metric. In comparison, your problem is simpler. The data is still stored in the same format, only difference will be in number of samples and the location of the samples (if I understood you correctly).

Perhaps you should consider what is the essence of the good subjective quality of terrain. Should the silhoutte remain more accurate than valleys or features that are viewed at steep angle? Perhaps the angle between adjecent polygons representing the hills should be maintained as close to original as possible? What are the details that take the attention of the viewer and what are left with less attention?

These are some of the questions that are not answered by "blind mathematics", but experience and extensive testing. Then again, you probably already know this, but even so, there is no definite answer one can give here. In comparison, the technical side is trivial to the psycho-visual aspect.

Perhaps, it is easier to help if you give more detailed description of the context and application.

Just to make sure I understand what you're trying to do;

You have a height-map of some kind, and you want to construct an irregular surface mesh from it?

If this is correct, then as Winograd said, you're essentially performing lossy compression on a 2D signal, so you want to come up with metrics for shape preservation.

I didn't understand it on first geist, but TheAdmiral's suggestion seemed very promising.

My suggestion is that once you have found the points that you're going to sample, you use a Delaunay Triangulation (first or second order) to construct the final surface. These have good properties for constructing height-maps from totally irregular samplings.

The TRIANGLE library has an excellent implementation of Delaunay, if you want more info about it email me.