# Random Contour Faces

I’ve been implementing an alternative CPU algorithm to draw contours last week. It was pitched by Markosian et. al, and I based my implementation on this Siggraph 2008 class by D. Decarlo.

Instead of testing all faces of a mesh for contours, I only test a configurable amount of random faces. When a contour is found, it is followed as far as possible. The algorithm in its pure form would only deliver good results at large sets of selected faces.

What’s interesting is to keep the *seeds* (the faces where you found the start of a contour line) of the previous frame. Using this in the next frame render, a high consistency can be achieved, and nearly all contour lines are found in the next frames.

I tested my contour implementation with a couple of settings. I’m using the Triceratops object, which has 22460 faces.

**Factor = 0.00001**.

So only 1 in ten thousand faces is used to find contours. This number is too low to have good contour coverage over a few frames. Which is normal, since we’re only using 2 random faces out of 22460 to find a contour.

**Factor = 0.001**.

So only 1 in thousand faces is used to find contours. We’re using 22 out of 22460 faces.

As expected, this number is still a bit too low: it takes 15/16 frames in a stationary viewpoint to draw a reasonable amount of contours. I’m expecting this would work reasonably well for slow moving meshes: 16 frames to reach full contour is not much when running at a decent framerate.

**Factor = 0.01**.

So only 1 in hundred faces is used to compute contours. We’re using 224 out of 22460 faces.

This is a lot better: after 2 or 3 frames in a stationary viewpoint: all contours are found. I don’t have a movie yet, but the temporal coherence is pretty good too: some contours “flicker” when the seed they use gets destroyed, but reappear again in the next frame.

**Factor = 0.1**.

So only 1 in 10 faces gets used.

This result is visually equivalent to using all faces, with only minimal overhead. Impressive!

I’m going to implement suggestive contours now, let’s see what performance boost this can bring!

## Leave a Reply