Probabilistically placing primitives

Non-photorealistic rendering often requires placing drawing primitives onto a 2D canvas in such a way that the resulting tone approximates that of a greyscale reference image. Several iterative methods have been used where each stroke is tentatively placed on the canvas and the resulting tone is evaluated with respect to the reference image. [Salisbury et al. 1994; Salisbury et al. 1997; Praun et al. 2001] If the stroke over-darkens the output image it is rejected, otherwise it is accepted. While this back-and-forth iteration between the output and the reference image is capable of producing high-quality results, it is extremely costly in terms of computation and memory references. However, if we view the reference image as a 2D probability density function (PDF), we can generate a set of primitive locations according to the PDF which will preserve tone a priori. Rendering then consists of taking a sequence of precomputed, uniformly distributed points in 2D and redistributing them according to the PDF. The derivation of the PDF from an image can be done rapidly to enable interactive frame rates. [Secord et al. 2002].