3
$\begingroup$

I am looking for an algorithm which would smoothly interpolate triangles of a mesh (computed by Delaunay triangulation) where each vertex has some value (elevation in my case). I need it for PDAL where I want to try to implement it. Its current implementation uses linear interpolation which makes the result not so pleasant:

enter image description here

(image is already post-processed to display the result as hill-shading)

Is there some public algorithm which would interpolate it smoothly, without sharp edges? Result should be a raster (rectangular grid of points).

Improve this question
$\endgroup$
7
  • $\begingroup$ en.m.wikipedia.org/wiki/Phong_shading $\endgroup$
    – lightxbulb
    Commented Apr 11, 2022 at 18:55
  • $\begingroup$ @lightxbulb I actually need just to interpolate elevations, not to directly produce visual shading and playing with light direction $\endgroup$
    – Martin Ždila
    Commented Apr 12, 2022 at 5:57
  • 1
    $\begingroup$ You can try this: en.m.wikipedia.org/wiki/Point-normal_triangle Also if the result is supposed to be on a raster grid and you have sparse data, is there a reason you compute the Delaunay triangulation instead of applying interpolation directly on the sparse data? $\endgroup$
    – lightxbulb
    Commented Apr 12, 2022 at 8:36
  • $\begingroup$ @lightxbulb thanks! I will take a look on PN triangle. And actually you are right - I have sparse points and want them to produce a smooth surface. Can you recommend me a method which could do it? $\endgroup$
    – Martin Ždila
    Commented Apr 12, 2022 at 8:58
  • $\begingroup$ I am assuming those are irregularly distributed? If that is the case you can solve the harmonic or biharmonic equation with Dirichlet boundary conditions defined by the point values. I admit that this may be harder though if you lack the mathematical background. You can also look into literature on radial basis functions for interpolation. $\endgroup$
    – lightxbulb
    Commented Apr 12, 2022 at 9:03

1 Answer 1

Reset to default
3
$\begingroup$

You may be able to eliminate the triangular artifacts by using Natural Neighbor Interpolation. You can find a description of the technique and an associated description of the algorithm at An Introduction to Natural Neighbor Interpolation. I've got an open-source implementation in Java. And while it won't solve your problem (since you're working in C/C++), you could run your data through the Tinfour Viewer demonstration application to see how it looks under Natural Neighbor Interpolation. That would, at least, tell you if it was worth further consideration. If you're interested, you can find more information at the Tinfour Project.

It looks like your input data is from a Lidar source. So here's a picture of some Lidar data taken over Bear Mountain in Salisbury, CT, USA. Interpolation was performed using NNI. NNI works fine when your data represents a coherent surface. For Lidar, that means sticking to all ground points or all first returns. If you start mixing in things like tree branches and other vegetation, you'd be better served by something like an Inverse Distance Weighting solution.

Lidar sample over Bear Mountain

Improve this answer
$\endgroup$
4
  • $\begingroup$ If you are familiar with the code in the linked article could you link the specific part of the code that computes the weights based on the Delaunay triangulation? As I understood it it is supposed to compute the overlapping areas if a point were to be introduced, though I am not certain on the details of that. They mention the Bowyer-Watson tessellation algorithm, and as I understand it, one would have to recompute the Delaunay triangulation change (in terms of 1-ring neighbours) for each pixel. $\endgroup$
    – lightxbulb
    Commented Apr 27, 2022 at 12:48
  • $\begingroup$ Sure. If you click on the link marked "Implementation Notes" at the top of the article I cited, you'll find an article describing the algorithm in detail. It also explains how it is possible to perform a Natural Neighbor Interpolation without modifying the Delaunay triangulation (an important part of making the thing run fast). You can find it at gwlucastrig.github.io/TinfourDocs/… . Also, if you download the code from Github, there is a Java class called NaturalNeighborInterpolator that implements the algorithm. $\endgroup$
    – Gary Lucas
    Commented Apr 27, 2022 at 14:40
  • $\begingroup$ Also, you may find it useful to look at Liang and Hale's algorithm. Although the algorithm I use is largely my own, their earlier work used a lot of the same ideas I applied. You may find their approach more to your liking (in either case, I will be interested in hearing more about what you do). See citeseerx.ist.psu.edu/viewdoc/… $\endgroup$
    – Gary Lucas
    Commented Apr 27, 2022 at 14:49
  • $\begingroup$ Thank you. I have found this too: alexbeutel.com/papers/tsas-terranni.pdf but it seems fairly involved. What I do is sparse data interpolation, and I have been using some PDEs for that, but I realize that generalized barycentric coordinates based approaches can be faster, and have other properties. I was interested in case I ever get to implementing it, but it's currently not high up on my priority queue. $\endgroup$
    – lightxbulb
    Commented Apr 27, 2022 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.