We study the effect of an inhomogeneous gas density on positive streamer discharges in air using a 3D fluid model with stochastic photoionization, generalizing earlier work with a 2D axisymmetric model by Starikovskiy and Aleksandrov (2019 Plasma Sources Sci. Technol. 28 095022). We consider various types of planar and (hemi)spherical gas density gradients. Streamers propagate from a region of density n0 towards a region of higher or lower gas density n1, where n0 corresponds to 300 K and 1 bar. We observe that streamers can always propagate into a region with a lower gas density. When streamers enter a region with a higher gas density, branching can occur at the density gradient, with branches growing in a flower-like pattern over the gradient surface. Depending on the gas density ratio, the gradient width and other factors, narrow branches are able to propagate into the higher-density gas. In a planar geometry, we find that such propagation is possible up to a gas density slope of 3.5n0/mm, although this value depends on a number of conditions, such as the gradient angle. Surprisingly, a higher applied voltage makes it more difficult for streamers to penetrate into the high-density region, due to an increase of the primary streamer's radius.