Abstract: We develop a progressive refinement algorithm that generates an approximate image quickly, then gradually refines it towards the final result. Our algorithm can reconstruct a high-quality image after evaluating only a small percentage of the pixels. For a typical scene, evaluating only 6% of the pixels yields an approximate image that is visually hard to distinguish from an image with all the pixels evaluated. At this low sampling rate, previous techniques such as adaptive stochastic sampling suffer from artifacts including heavily jagged edges, missing object parts, and missing high-frequency details. A key ingredient of our algorithm is the directional coherence map (DCM), a new technique for handling general radiance discontinuities in a progressive ray tracing framework. Essentially an encoding of the directional coherence in image space, the DCM performs well on discontinuities that are usually considered extremely difficult, e.g. those involving non-polygonal geometry or caused by secondary light sources. Incorporating the DCM into a ray tracing system incurs only a negligible amount of additional computation. More importantly, the DCM uses little memory and thus it preserves the strengths of ray tracing systems in dealing with complex scenes. We have implemented our algorithm on top of RADIANCE. Our enhanced system can produce high-quality images significantly faster than RADIANCE - sometimes by orders of magnitude. Moreover, when the baseline system becomes less effective as its Monte Carlo components are challenged by difficult lighting configurations, our system will still produce high quality images by redistributing computation to the small percentage of pixels as dictated by the DCM.