WuLines in Forth
Tim Trussell
by Timothy Trussell
---[ Where We Are ]--------------------------------------------------
Learning to work with new-old toys.
I've been going back through some of the code from Michael Abrash's
columns in Dr. Dobbs Journal, and came upon his implementation of
Xiaolin Wu's antialiasing line drawing algorithm.
Rather than try to explain it myself, here is a short extract from
the column:
---[ Fast Antialiased Lines Using Wu's Algorithm ]-------------------
Author: Michael Abrash
Source: DDJ, Feb 1992
Antialiasing is the process of smoothing lines and edges so that
they appear less jagged. Antialiasing is partly an aesthetic issue,
because it makes it possible to position and draw images with
effectively more precision than the resolution of the display.
It's also a necessity, to avoid the horrible, crawling, jagged edges
of temporal aliasing when performing animation.
The basic premise of Wu antialiasing is almost ridiculously simple:
As the algorithm steps one pixel unit at a time along the major
(longer) axis of a line, it draws the two pixels bracketing the line
along the minor axis at each point. Each of the two bracketing pixels
is drawn with a weighted fraction of the full intensity of the
drawing color, with the weighting for each pixel equal to one minus
the pixel's distance along the minor axis from the ideal line.
The intensities of the two pixels that bracket the line are selected
so that they always sum exactly 1; that is, to the intensity of one
fully illuminated pixel of the drawing color. The presence of
aggregate full-pixel intensity means that at each step, the line has
the same brightness it would have if a single pixel were drawn at
precisely the correct location. Moreover, thanks to the distribution
of the intensity weighting, that brightness is centered at the ideal
line. Not coincidentally, a line drawn with pixel pairs of aggregate
single-pixel intensity, centered on the ideal line, is perceived by
the eye not as a jagged collection of pixel pairs, but as a smooth
line centered on the ideal line. Thus, by weighting the bracketing
pixels properly at each step, we can readily produce what looks like
a smooth line at precisely the right locatin, rather than the jagged
pattern of line segments that non-aliased line drawing algorithms
such as Bresenham's trace out.
Horizontal, vertical and diagonal lines do not require antialiasing
because they pass through the center of every pixel they meet; such
lines can be drawn with fast, special-case code. For all other cases
Wu lines are traced out one step at a time along the major axis by
means of a simple, fixed-point algorithm. The move along the minor
axis with respect to a one-pixel move along the major axis (the slope
for lines with slopes less than 1, 1/slope for lines with slopes
greater than 1) is calculated with a single integer divide. This
value, called the 'error adjust,' is stored as a fixed-point fraction
in 0.16 format (that is, all bits are fractional, and the decimal
point is just to the left of bit 15). An error accumulator, also in
0.16 format, is initialized to 0. Then the first pixel is drawn; no
weighting is needed, because the line intersects it's endpoints
exactly.
Now the error adjust is added to the error accumulator. The error
accumulator indicates how far between pixels the line has progressed
along the minor axis at any given step; when the error accumulator
turns over, the major axis coordinate advances by one pixel. The two
bracketing pixels to draw are simply the two pixels nearest the line
along the minor axis. For instance, if X is the current major-axis
coordinate and Y is the current minor-axis coordinate, the two pixels
to be drawn are (X,Y) and (X,Y+1). In short, the derivation of the
pixels at which to draw involves nothing more complicated than
advancing one pixel along the major axis, adding the error adjust to
the error accumulator, and advancing one pixel along the minor axis
when the error accumulator turns over.
We know which pair of pixels to draw at each step along the line, but
we also need to generate the two proper intensities, which must be
inversely proportional to distance from the ideal line and sum to 1,
and that's a potentially time-consuming operation. Let's assume,
however, taht the number of possible intensity levels to be used for
weighting is the value NumLevels=2~n for some integer n, with the
minimum weighting (0% intensity) being the value 2~n-1, and the
maximum weighting (100% intensity) being the value 0. Given that, the
most significant n bits of the error accumulator select the proper
intensity value for one element of the pixel pair. Better yet, 2~n-1
minus the intensity of the first pixel selects the intensity of the
other pixel in the pair, because the intensities of the two pixels
must sum to 1; as it happens, this result can be obtained simply by
flipping the n least-significant bits of the first pixel's value.
All this works because what the error accumulator accumulates is
precisely the ideal lines current distance between the two bracketing
pixels.
The intensity calculations take longer to describe than they do to
perform. All that's involved is a shift of the error accumulator to
right-justify the desired intensity weighting bits, and then an XOR
to flip the least-significant n bits of the first pixel's value in
order to generate the second pixel's value.
Make no mistake about it, Wu antialiasing is fast.
-----------------------------------------------------[End Extract]---
Sounds simple, doesn't it. It is.
The Code Addendum breaks down into three sections:
1. Library Includes
2. Wu Demo
3. Wireframe Cube Demo
The Library Includes section is comprised of the various modules that
make my programming life easier.
The Wu Demo Code section consists of the following routines:
: PutPixel ( &buf x y c -- )
: WuYMajor ( -- )
: WuXMajor ( -- )
: WuLine ( &buf X0 Y0 X1 Y1 c #lvls ibits -- )
: Line ( &buf x1 y1 x2 y2 c -- )
: SetWuPalette ( -- )
: Wu1 ( -- )
: Wu2 ( -- )
: Wu3 ( -- )
: Wu4 ( -- )
: Bres1 ( -- )
: Bres2 ( -- )
: Bres3 ( -- )
: Bres4 ( -- )
: WuTest ( -- )
: SeeWu ( -- )
: SeeBres ( -- )
And the final section, the Wireframe Cube Demo:
: CreateLookupTables ( -- )
: SetObject ( x y z obj# -- )
: InitCube ( -- )
: RotateVectors ( -- )
: DrawCube ( -- )
: Cube ( -- )
which is code that I have posted before. The only actual change to it
is the WuLine call additions in the DrawCube routine:
: DrawCube ( -- )
RotateVectors
12 0 do
VBuffer \ draw image to buffer
CSegs[] i cseg-ndx >R
temp[] R@ .pa @ cube-ndx dup .cX @ swap .cY @
temp[] R> .pb @ cube-ndx dup .cX @ swap .cY @
--> WuColors[] WU_Blue wucolor-ndx .BaseColor @
--> WuColors[] WU_Blue wucolor-ndx .NumLevels @
--> WuColors[] WU_Blue wucolor-ndx .IntensityBits @
--> WuLine
loop
VBuffer BlitBuffer \ display buffer data
VBuffer BufferSize 0 fill \ erase display buffer
;
The WuLine code follows the outline of what Michael describes in his
column - as it should, since this is a straightforward conversion of
his code to 32Forth. Therefore, I'm not going to attempt an in-depth
theory of operation description of how and why things get done. I
think what is in the extract above is sufficient to get a working
idea on what is going on in the program flow.
When viewing the code, you might think that I seem to love VALUEs.
Well, this is partially true. The main reason for using them in
such profusion was to make following the flow of the code easier to
see. Stack thrashing wasn't worth the 'savings', so I used LOTS of
VALUEs to store the variable data in.
The routines Wu1, Wu2, Wu3 and Wu4 draw the test pattern using the
WuLine algorithm.
The routines Bres1, Bres2, Bres3 and Bres4 draw the same pattern, but
use a regular Bresenham algorithm.
WuTest draws first with the Wu1~4 code, and then after a delay with
the Bres1~4 code, and then alternates back and forth to let you see
the difference in the line styles. Press ESC to exit this routine.
The SeeWu and SeeBres draw the corresponding demo display to the
screen, and wait for a keypress to exit. These are just to let you
study each at your leisure, if you so choose.
The Cube routine draws a rotating wireframe cube using the WuLine
routine. There is no flipping back and forth like with WuTest.
If the display is too fast, increase the count in the call to the
VRDelay routine, which uses the WaitRetrace routine to introduce a
vertical retrace based time delay into the program flow.
---[ Playing with the code ]-----------------------------------------
Areas of interest, for those who want to explore this more, would
have to include the SetWuPalette function. In this code, you will
find the definitions for how the intensities are calculated:
create WuColors[]
192 , 32 , 5 , 0 , 0 , 63 , \ blue
224 , 32 , 5 , 63 , 63 , 63 , \ white
Remembering that each palette entry consists of three bytes (for red,
green and blue values), each of these color intensity structures are
96 bytes (32*3) in size. This means that these two definitions take
up 25% of the available palette space (64 of 256 palette entries).
This presents a limitation on the use of the Wu algorithm in code
that you want to do something with - a much smaller number of colors
that you can use in your display. Not insurmountable, but it will
require you to know exactly what is going on in your palette.
You could define up to seven different Wu intensity banks, and this
will still leave you 32 palette entries for the rest of your code to
work with (as a possibility).
If you want to try different colors, modify the final three bytes to
get a new intensity table created and sent to the VGA palette.
Instead of a blue image, change
192 , 32 , 5 , 0 , 0 , 63 , \ blue
+----+----+
to
192 , 32 , 5 , 0 , 63 , 0 , \ green
+----+---+
or to
192 , 32 , 5 , 63 , 0 , 0 , \ red
+----+---+
Note that the range limit on these three entries is [0..63].
You can freely mix these three bytes with different values to get
up to the full range of possible colors, but remember that the max
value for any of the three bytes is 63.
(I would suggest leaving the first three entries alone, though.)
Try commenting out the SetWuPalette line in the source of Cube to see
what the basic palette data looks like. It still looks better than
the jagged lines that the Bresenham Algorithm draws, but the color is
a bit strange (kind of a grayish-green, sprinkled with red pimentos).
---[ Wrapping Up ]---------------------------------------------------
If you are working with line drawing functions, this has the ability
to give your display a much-improved look. I have plans to see how
(or if) this will improve the edges of the filled polygons that I
am working with.
That's it for this one - for now. I'll probably do an update on this
(a small one) after I see what happens when I use the code in my
VESA library. The WuLines should look awesome in 1024x768 mode.
Oh, if anyone has cause to email Michael, ask him if he still enjoys
fried, stewed chicken.
------------------------------------------------------[End WuLine]---
w_a_x_man
> The Library Includes section is comprised of the various modules that
> make my programming life easier.
You don't understand what "comprised" means.
Correct:
The Library Includes section comprises the various modules
or
The Library Includes section is composed of the various modules
Jerry Avins
> ---[ WuLines in Forth ]-------------------------------[11/11/2009]---
>
> by Timothy Trussell
...
> The WuLines should look awesome in 1024x768 mode.
...
It stands to reason that the higher the screen resolution, the less
improvement anti-aliasing makes. My display is 1920 pixels wide by 1200
high. I can easily read type small enough to fit 80 lines on the screen.
That's 15 pixels line of text. My eye alone anti-aliases very well at
that size. Perhaps this is a solution to yesterday's problem?
Jerry
--
Engineering is the art of making what you want from things you can get.
�����������������������������������������������������������������������