Currently-available brachytherapy dose computation algorithms ignore heterogeneities such as tissue-air interfaces, shielded gynecological colpostats, and tissue-composition variations in 125I implants despite dose computation errors as large as 40%. To calculate dose in the presence of tissue and applicator heterogeneities, a computer code has been developed that describes scatter dose as a 3-D spatial integral which convolves primary photon fluence with a dose-spread array. The dose-spread array describes the distribution of dose due to multiple scattering about a single primary interaction site and is precomputed by the Monte Carlo method. To correct for heterogeneities traversed by the primary photons, the dose-spread array is renormalized to reflect the density and composition of the element, and the distance to the point of interest is scaled by the pathlength of the intervening medium. Convolution calculations for 125I and 137Cs point sources in the presence of finite phantoms, air voids and high-density shields have been compared to the corresponding Monte Carlo calculations. The convolution code absolute and relative dose rate predictions are shown to agree with Monte Carlo calculations within 3%. Direct evaluation of the 3-D spatial convolution integral using 1-D adaptive integration reveals efficiency gains of 20–50 relative to Monte Carlo photon-transport calculations.