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.