Belief propagation (BP) have emerged as powerful tools in the realm of dense stereo computation. However the underlying brightness constancy (BC) assumption of existing methods severely limit the range of their applications. Augmenting BC with gradient constancy (GC) assumption has lead to a more accurate algorithm for optical flow computation. In this paper, these constraints are utilized in the frameworks of BP to broaden the application of stereo vision for 3D reconstruction. Results from experiments with semi-synthetic and real data illustrate that an algorithm incorporating these models generally yields better estimates, where the BC assumption is violated.