[fractallyte]

Possibly the finest painting software currently available is Synthetik's Studio Artist (http://synthetik.com/). Compared to Adobe's powerhouse software, it's relatively unknown, but that doesn't make it any less innovative.

It uses an algorithmic 'paint synthesizer' to generate brushes (with hundreds of presets) and auto-paint canvases, and is designed for animation (rotoscoping) as well as static artwork. The output can be reminiscent of the style of the movie 'A Scanner Darkly', but the software is hugely flexible. Here are a couple of rather amazing examples: http://studioartist.ning.com/video/auto-rotoscoped-dancers and http://studioartist.ning.com/video/dance-styles-animation-re...

Also, unlike most other 'painterly' software, the graphics are resolution independent - meaning that they can be scaled up to any size without loss of detail.