Environment maps are a popular method of reproducing complex natural lighting. However, current methods for hardware environment map shadows depend on significant pre-computation and cannot support dynamic objects. This work presents a pre-process that decomposes an environment map into two components: a set of area lights and an ambient map. Once the map is split into these components, each is rendered with an appropriate mechanism. The area lights are rendered using an existing hardware-accelerated soft-shadow algorithm; for our implementation we use penumbra wedges. The ambient region is rendered using pre-integrated irradiance mapping. Using an NVidia 6800 on a standard desktop, we demonstrate high-quality environment map shadows for dynamic scenes at interactive rates.