This paper developed prior work which incrementally completes a sparse depth map based on inter-image statistics information. In that prior work, we have observed that pixel ordering of the incremental recovery is critical to the quality of the final results. In this paper we demonstrate improved performance using an information-driven recovery policy to determine this ordering. We have also observed that the reconstruction across depth discontinuities was often problematic as there was comparatively little constraint for probabilistic inference at those locations. Further, such locations are often identified with edges in both the range and intensity maps. We address this problem by deferring the reconstruction of voxels close to intensity or depth discontinuities, leading to improved results. We also show that color information can improve reconstruction quality. Experimental results are presented to demonstrate the quality of the recover and to illustrate some new application domains such as deblurring and underwater scattering compensation.