Freehand drawing using increment line tracing algorithms.

This is about programming an incremental line tracing algorithm in the Python language.

Open source code is in my github project.

Definitions of freehand

Freehand in the art world usually means without tools such as rulers or plastic templates.

Freehand in a computer drawing application means the same thing, but the tools are virtual.  It means using a Pencil or Ink tool, not a Line tool or a Rectangle tool.  It means laying down black pixels in the mouse track.

But that can be bitmapped, or in vector graphics.

Line tracing algorithms

Line tracing algorithms create vector graphics, for example SVG, from bitmaps.  Some computer drawing applications have a Trace function that does this.  Many OCR (optical character recognition) application perform line tracing internally.

One open source line tracing algorithm is Potrace by Peter Selinger.  Another is Autotrace.  I started from the Potrace algorithm because the author wrote an understandable technical paper describing how it works.

Incremental line tracing

Many line tracing algorithms are “batch” algorithms: they assume a complete existing bitmap, that is, a 2D plane of pixels.  (A pixmap in color, a pixelel map in grayscale, a bitmap in black and white.)

A freehand drawing tool is incremental: it processes drawing bits as they become available from the mouse (or other graphics device pointer, such as pen or touch.)

The word batch is a relic.  Long ago, you shared a slow computer, and submitted batch jobs for processing.  Nowadays, everyone has their own fast computer.

One concern for an incremental line tracing algorithm is keeping up with the user.  It must be fast enough that the drawn graphics  are smooth and don’t lag behind the cursor as the user draws.  I have found that even an interpreted language such as Python on an average desktop PC can keep up reasonably well.

Using a filter pipeline of coroutines for incremental line tracing

Its a natural fit.  The algorithm is a chain of filters.  Each filter takes small objects from its predecessor, recognizes larger objects, and sends the larger objects to its successor.  Pointer positions are fed into the pipeline, and vector graphics curves (cubic splines) come out the other.

The Python language has “extended generators”, or coroutines,  that can be used to implement such a pipeline of filters.  My project demonstrates using extended generators (but still a toy demonstration?)

Ghosting the head of an incremental line tracing pipeline

A pipeline has lag.  What you put in doesn’t come out until later. In this case, when you put in a pointer position, a curve does not come out until after you have put in several more pointer positions.

But a user wants to see the ink following the drawing tool smoothly.  Its an evolved psychological phenomena.  People are uncomfortable with jumpy graphics, they think it is a lion about to eat them.

So a computer drawing program must draw the results of the incremental line tracing as they are available, and draw a “head” between the end of those results and the pointer.  Currently, I just draw a straight line.  That is less than ideal, because it is also jerky.  Probably the head should be a pixmap graphic (in image of the mouse track) gradually and inconspicuously replaced by vector graphics.

(I call it a head since it looks like the head of a snake.  Computer programmers might by convention call it the tail, since it is the thing that is “last in”.  See “tail” a file.)

Qt

The project includes a rudimentary drawing application that demonstrates the algorithm.  The application uses the Qt framework and the PySide binding from Python to the Qt library.

I only partially succeeded in making the algorithm independent of the framework.  The algorithm relies on basic classes such as QPointF, and less basic classes such as QPainterPath, for storing the resulting vector graphics.

Derivation from Potrace

My project derives from Potrace but omits some of the processing steps of Potrace.  For example, I found that Potrace’s “directions” and “vertex adjustments” and “optimization” are not necessary for reasonable freehand drawing.  To know which omitted steps would best improve freehand drawing requires more study.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s