My primary inspiration for this project is Processing
Images and Video for An Impressionist Effect. In that paper Peter Litwinowicz
explians how to combine a particle system and a Delaunay triangulator to create
a visually consistent video segments in which every frame has a hand painted
look. Particles are used to keep track of brush stroke positions, while a
quality controlled Delaunay triangulation makes sure that those particles
never became to concentrated or diffuse.
Here are a couple of cool pictures showing before and after stills from Litwinowicz's
animations:
»
I particularly like the swirly patterns that come out in the brush strokes
on the mouse pad; they remind me of one of my favorite paintings -
This brings us to the dangerous idea at the foundation of this project.
I want to use Litwinowicz's visual consistency strategies to create animations
that that also possess the sorts of turbulent brush stroke patterns that Van
Gogh is known for. It would be very cool if we could create a system symmetric
to Litwinowicz's: something that would let us turn segments of video into
visually consistent sequences of images, each of which seemed to have been
painted by Van Gogh. However, my goals are somewhat more modest. Given a fluid
simulation, I apply a Litwinowicz like method to render it at every simulation
time step, resulting in animations that look like these:
How it all works:
The fluid simulator that I have used is the one implemented for assignment
3. For more details on its design and construction see the associated webpage.
The NPR rendering is constructed as follows: I start by using Halton pseudo-random
sequences to scatter a number of particles over the image. These particles
represent my brush strokes. Initial stroke color is determined by the density
and color of the underlying dyes, and does not change over time. Like Litwinowicz,
I add a random perturbation to the stroke color, and as well as to the stroke
width. However, unlike Litwinowicz, I do not randomly initialize stroke length,
that value is determined by the velocity field of the fluid simulator, and
does change over time. After every time step of the fluid simulator, I update
each particle's position using the same particle tracing algorithm that my
fluid simulator uses in its advection phase. The strokes are then drawn, those
farther down in the stroke storage vector are draw over the earlier ones.
But there is a problem with is rendering method. Over time the particles bunch
together, leaving large areas of the image empty of brush strokes, and others
in which stroke density is needlessly high. This is the problem that Litwinowicz's
method was designed to overcome.
Litwinowicz's solution is to create a Delaunay triangulation of the updated
particle positions, and then impose a maximal area constraint. This has the
effect of creating new particles whenever one of the triangles has too large
of an area. This takes care of problem created when particles become too spread
out. The problem of particles becoming excessively dense is solved by removing
the lower of any two particles that are within a given distance of each other.
Following Litwinowicz's lead, I have gotten my hands on Shewcuk's triangulator,
and used it to regulate my particle positions.
Here you can see a couple of particles and the associated
triangulation, notice how new particles are added when a triangle's area becomes
too large.
One seemingly minor, yet quite important question is how to determine the
color of new particles that are added due to the maximum area constraint.
Because he is working from video, Litwinowicz has the luxery of just sampling
out of the current video frame. But our circumstances are introduce new difficulties.
One approach would be to interpolate the color of the new stroke from that
of the surrounding strokes. However, this creates the impression that the
fluids moving in the image are not mass conserving. If two brush strokes are
initialized over an area that has a high underlying dye density, and then
move apart, the brush stroke added between them would be colored as if it
represented a high dye density, while a real dye would have diffused over
the expanded area. The opposite approach, initializing new particles using
underlying dye densities, bring in a related problem. Because the dye has
diffused, the added strokes will be much less bright than those around it.
And this leads to areas of the animation in which brush stroke color varies
dramatically between the newly added strokes which represent the faded underlying
dye, and old strokes which were assigned their color back when the dye was
more concentrated.
However, because we are performing a non-photorealistic rendering, I am not
that worried about either physical inaccuracies or color consistency problems
in the stroke colors. If my goal to have properly colored particles, I could
just always color the brushes using the underlying dye densities. But it turns
out that dye density changes enough that doing this sacrifices the visual
consistency between frames, so it is not really a good option. Perhapes implementing
some gradual change in color would work better (we could use the differense
of the underlying color and the dye density to define a delta c for
each stroke).
One of the reasons why applying these methods to real images n order to create
animations such as Litwinowicz's would be hard is that the coloring issues
are even worse if you are initializing new points from a background image
rather than dye densities. With dye densities, at least you know that the
evolution of the dye densities in the fluid simulator is going to in some
sense mirror the evolution of your brush positions. If I had a picture of
a sky cloudy sky that wanted to render using my technique, I could specify
parameters of a fluid simulation bounded to the area of the image representing
the sky, and initialize brush strokes given the pixel values of the sky. But
then when the time came to add in new strokes, getting stroke color from the
underlying image would lead to all sorts of nasty problems.
That said, the next feature that I plan add to my application will initialize
brush colors based on a image bitmap, and add new strokes with a color interpolated
from there neighbors. The argument being that matter conservation is not really
that important, as the real goal is too create aesthetically pleasing images.
Recent Updates:
I've just altered my program to take into account a piece of advice from
Litwinowicz's paper. I now give new particles a random position in the
stroke storage vector, rather than just adding them to the back (Litwinowicz
claims that adding the strokes to the back of the list can create "undesirable
effects").
Links:
My fluid simulator webpage
The fluid simulator / NPR visulizer
application
- Requires IFL
for image printout.
- If you can't / don't want to install IFL,
here is an alternate build of
the binary that removes the IFL dependencies. You won't be able to
use the printing commands, but otherwise the simulator works fine.
Source code
- Distributed as a stripped snapshot of
my dev directory; just about all of the code involved in the simulator
lives in dev/fluids.
Peter Litwinowicz, Processing
Images and Video for An Impressionist Effect.
Jonathan Shewchuk, Triangle:
A Two-Dimensional Quality Mesh Generator and Delaunay Triangulator.
- I had some trouble getting Triangle to
impose the maximal area constraint on my point set. Luckily for me, Shewcuk
has published a paper which gives a quite readable explanation of how
the area constraint works, and his lecture notes include the equations
needed to implement it. Thus my program uses Triangle to perform the basic
triangulation, and then I go through the resulting triangles myself, adding
points at the circumcenter of any triangle that has more that the maximum
allowed area (which is an adequate approximation of Shewcuk's algorithm,
given the limited context in which I want to apply it).
Jonathan Shewchuk, Triangle:
Engineering a 2D Quality Mesh Generator and Delaunay Triangulator.
- The Triangle paper I mentioned.
Jonathan Shewchuk, Geometric Robustness
Lecture Notes,
- A quite detailed description of many equations
for precise computation of geometric terms, referenced by Shewchuk in
his comments for the Triangle code. Calling this 20 page paper "lecture
notes" is perhaps excessively modest.
Here is a link
to the page where I found the implementation of the Halton sequence
generator used to initialize the brush stroke positions. And just for
the heck of it, here is the cool
siggraph paper by Alexander Keller which was responsible for getting
me interested in Halton sequences in the first place.
The "Van
Gogh" Gimp Plugin
-I am certainly not the first person to
try to create Van Gogh-like renderings of images. Here is a link to a
gimp plugin that works by smearing the image according to a vector field
infered from a Guassian blur.
