2008-10-07

Line Clipping

I was browsing through a book on computer graphics the other day when I came across a section on clipping. The book didn’t really go into any great detail, so I googled it and discovered there are three main 2D line clipping techniques. The first is very simple; draw a line pixel by pixel, and if the pixel to be drawn falls outside the visible region, don’t draw it. Simple, effective, slow.

A better algorithm is the “Cohen-Sutherland” method, which imagines the display as a 3x3 grid of rectangles, uses a bitmask to identify which regions the two points of the line are in, then uses the parametric equation of the line to reduce its length so that it fits within the visible region. Clever. I would explain the routine in detail, but it’s hugely popular in Google already, and it seems that you’re not a Real Programmer unless you implemented it a dozen times before you had breakfast today. Of course, I’d never heard of it before.

The third method is the “Liang-Barsky” algorithm, which I confess to not really looking into. It’s allegedly faster than the Cohen-Sutherland method, but I lost interest as soon as I realised it required floating-point maths to work.

There was another method, which claimed to be several times faster than Liang-Barsky and didn’t need floats, but as that one was patented I lost interest even faster. Software patents are a very bad thing.

Anyhoo, Woopsi’s GraphicsPort class now has a drawLine() routine. It uses the same Bresenham line drawing routine that the SuperBitmap uses, but it’s wrapped inside an implementation of the Cohen-Sutherland clipping routine. I’ve had to modify it a little to replace its use of floats with fixed-point maths, but that doesn’t seem to have impacted its accuracy.

The next thing on my to-do list is to extract the basic functionality of the TextBox class into a separate “Label” class, .NET-style. Read-only textboxes really don’t need to carry around the extra baggage of the new cursor system. Also, I’m thinking of moving the string manipulation code out of the TextBox class and into the Text class, thus separating the presentation of the data from its manipulation. This, of course, means I’m effectively writing my own string class, which is one of the classic mistakes people make with C++ (the STL obviously has a perfectly good implementation) but as the STL is off-limits I think I have a good excuse.