Interpolation is a good way to fill holes. We all know method like Bezier, Lagrange, B-Splines, Nurbs methods. But other method exist and I want mention them here :
Surface reconstruction algorithm gives us a much better feel for the data. There are Kriging that perform this task, but Kriging can be slower on large data sets. I purpose you to read the master thesis of Mike Thiesen. A FAST LAYERED ALTERNATIVE TO KRIGING.