Fast rendering of dynamic scenes with natural illumination, all-frequency shadows and spatially varying reflections is important but challenging. One main difficulty brought by moving objects is that the runtime visibility update of dynamic occlusion is usually time-consuming and slow. In this paper, we present a new visibility sampling technique and show that efficient all-frequency rendering of dynamic scenes can be achieved by sampling visibility of dynamic objects in an adaptive and parallel way. First, we propose a two-level adaptive sampling scheme to distribute sample points spatially and compute visibility maps angularly on each sample point. Then, we present a parallel hemispherical distance transform to convert these visibility maps into spherical signed distance fields. Finally, using such a distance-based visibility representation, we integrate our visibility sampling algorithm in the all-frequency rendering framework for scenes with spatially varying BRDFs. With an entire GPU-based implementation, our algorithm enables interactive all-frequency rendering of moderate dynamic scenes with environment lighting and spatially varying reflectance.