We address multiple-view reconstruction under an optimization approach based on belief propagation. A novel formulation of belief propagation that operates in 3-D is proposed to facilitate a true multi-image processing scheme that takes visibility into account and thus is applicable to scenes that contain significant occlusions. Visibility is not approximated but is estimated and used in a modified plane sweep stereo scheme. Optimization is performed in a simplified belief propagation framework in which messages are passed in 3-D, instead of 2-D, neighborhoods utilizing information from all available images. The information propagated from a point to one of its neighbors factors in the distance between the two points in 3-D, their difference in color. In contrast to traditional belief propagation, the observation is updated at each iteration to incorporate changes in visibility. The proposed approach is capable of enforcing smoothness on the evolving 3-D surfaces without being limited to a coarse resolution due to a volumetric representation. Moreover, our approach is applicable to both open and closed surfaces with no need for a priori knowledge of the type. We present dense reconstructions of publicly available image sets.