Accurate calculation of the three dimensional shape of an object is one of the classic research areas of computer vision. Many of the existing methods are based on surface normal estimation, and subsequent integration of surface gradients. In general, these methods do not produce valid surface due to violation of surface integrability. We introduce a new method for shape reconstruction by integration of valid surface gradient maps. The essence of the new approach is in the strict enforcement of the surface integrability via belief propagation across graphical model. The graphical model is selected in such a way to extract information from underlying, possibly noisy, surface gradient estimators, utilize the surface integrability constraint, and produce the maximum a-posteriori estimate of a valid surface. We demonstrate the algorithm for two classic shape reconstruction techniques; shape-from-shading and photo-metric stereo. On a set of real and synthetic examples the new approach is shown to be fast and accurate, in the sense that shape can be rendered even in the presence of high levels of noise and sharp occlusion boundaries.