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.

Comments

Jeff on 2008-10-07 at 23:45 said:

Actually, I think the assertion that the STL has a perfectly good one may be being a bit generous. There isn’t one STL, there are a number of them of varying qualities, all with the same name.

The real issue I have with smart text classes is that they can force the rest of your app to go down that path, by only providing api’s that take the smart class as input. Your application which also includes Unicode strings, or its own lex/yacc parsers, etc each of which also mandate their own string data types (or at least, use base data types) is forced to upcast to the “smarter” string type whenever it calls into some other framework, fragmenting memory and usually causing “transliteration” problems at the interface due to subtleties in the data.

By all means use smart strings internally, but think very carefully about defining your EXTERNAL api’s in those terms…

ant on 2008-10-08 at 06:51 said:

Yeah, I’m keeping standard chars and char arrays as the data types exposed by the API. They’ll get passed into the new string class for storage and manipulation.