SOME NAFTY GRAPHICS ALGORITHMS by Stefan Posthuma
Believe it or not, but I just cleaned up my room. For some people
this is a simple task, toss some papers in a drawer, and it's
done. But for me it's an Adventure. Armed with an exceptionally
large dustbin and a vacuum cleaner, accompanied by the new album
of the Art of Noise (which is extremely weird. Even my goldfish,
which is normally not influenced by the violent outbursts of
electronic music coming from my stereo was cleary annoyed) I
struggled with immense heaps of computer-printouts, a full
library of books (ranging from "Playboy's book of forbidden
words" to "The floppy and harddisk book Atari ST") and much more
stuff that comes from years of dedicated computing.
While raging though a mass of papers in one of my drawers, I
stumbled across a tiny little paper which contained some stuff I
used while writing graphics programs some 3 years ago on the good
old commodore 64. It contained some very interesting graphic
routines. After completing my Task, feeding my goldfish (he looks
very happy while I'm playing his favorite music, Jean Michel
Jarre's "Zoolook") some two hours and two filled garbage-bags
later I sat down behind my ST and tried some of those routines.
First of all, there was the smallest fill-routine I have ever
seen in my life. This proves how you can program complicated
tasks very compact using recursive programming (GfA of course)
That's it! It is extremely small and simple. But it is not so
fast and cannot fill with patterns. (But this shouldn't be so
difficult to program. Just adjust the plot routine a little)
Next, there is the routine to draw a line between two points on
If X0%>X1% ! make sure the line is drawn
Swap X0%,X1% ! left-right and top-bottom
Dx%=X1%-X0% ! horizontal distance to cross
Dy%=Y1%-Y0% ! vertical distance
Dy2%=2*Dy% ! 2*Dy for speed reasons
For C%=1 To Dx%
Here follows the routine to draw a circle
' 8 points are plotted from X%,Y%
If you want to draw filled circles, use this routine:
'Great', you might think. But why all the fuzz about these
routines while they're already sitting there in GEM, just waiting
for you to be called? (in this case through GfA). Also these
routines support luxury things like fill-patterns, line-styles,
line widths ect. Sure, when you just want to draw a line, the
Line command of GfA is perfect and much, much faster.
But what if you want to write a routine that can fold a block of
the screen (GET/PUT) like I do it in The ArtiST? You'll need a
line algorithm! Just draw a line according to the way the block
should be folded. But instead of plotting pixels, you BITBLT
columns or rows of the block, and the block is folded. You can
also resize a block to any size using the line routine. (How?
find it out yourself! A nice programming puzzle, think about it.
It almost busted my brains!)
In the ArtiST, when I want to draw a circle in Zoom-mode, I use
the exact circle algorithm as mentioned above. You can think of
many more applications for these algorithms.
I have always been a machine-code freak, for one reason only:
speed. Back on the Commodore 64 (and even further back on the
VIC-20), it was nessecary to program in machine code to produce
interesting programs because Basic on those machines was a piece
of ...... When I moved to the ST, I was delighted with the
fantastic 68000-possibilities. You can call the GEM-routines from
machine code. So why bother?
A GEM routine has to cope with things like Clipping, Fill
patterns, Line patterns and widths and lots more. This inevitably
slowes the routines down. Some of these things are also available
in Line-A, but still....
The routines above are all easy to program in machine code,
because they all use integer variables (including the circle
routine!) and simple multiplications which can be achieved by
left shifts. Also the circle routine is extremely fast because it
draws only one-eight of the circle and mirrors the rest of the
points around the centrepoint. So if you want to write super-fast
line routines for real-time 3D-applications or other animated
applications involving straightforward lines, these are the ones
A very important factor of speed is the pixel-plotting routine.
If you draw a long line or a big circle, you have to plot a
considerable amount of pixels. If you have a superfast line-
routine but a slow pixel-plot routine, you achieve nothing. So we
have to think of the fastest way possible to plot a pixel on any
given X and Y coordinate. This time we will do it in assembler:
* Routine to plot a pixel
* D0 contains X-coordinate (word value)
* D1 contains Y-coordinate (word value)
* A0 contains adress of screen
* these values are not affected
* registers affected: A1,D2,D3
* works in monochrome only
plot: move.l A0,A1 * save screen adress
move.w D0,D2 * X
lsr.w #3,D2 * X/8 = horizontal byte involved
add.w D2,A1 * screen + horizontal byte
move.w D1,D2 * Y
lsl.w #6,D2 * Y*64
add.w D2,A1 * screen + Y*64
move.w D1,D2 * Y
lsl.w #4,D2 * Y*16
add.w D2,A1 * screen + Y*16 -> screen + Y*80
move.w D0,D2 * get X
and.b #$07,D2 * X and 7 = bit involved
bset D2,(A1) * set the bit (erase with BCLR)
While we're talking speed, take a look at the circle algorithm.
You will see that it only needs to draw horizontal lines. Think
about a horizontal line and you might find out that when the
computer draws a horizontal line, most of the time it is busy
filling bytes with $FF values. So instead of using the normal
line routine, you create a simple loop which fills the line with
$FF. Only the start and the end of the line which do not fall
exactly within byte boundaries have to be shifted around a
little. I will give you the algorithm:
LeftAdress = Screenadress + X0/8 + Y*80
RightAdress = Screenadress + X1/8 + Y*80
LeftMask = 255 shiftr (X0 and 7)
RightMask = not (255 shiftr (X0 and 7))
LeftAdress = Leftadress OR LeftMask
Fill LeftAdress + 1 to RightAdress - 1 with 255 ($FF)
RightAdress = RightAdress OR RightMask
The divisions and multiplications can be subsituted by right and
left shifts of course. But be careful, this routine only works
when the length of the line is greater than 16. Use the normal
routine for smaller lines.
Of course, the vertical line can be programmed even more simple:
Adress = ScreenAdress + X/8 + Y0*80
Bitnr = X AND 7
Length = Y1-Y0
Adress = Adress + 80
Dbra Length, Loop
This routine is mind-bogglingly fast, because the main part of it
is just a simple loop. Now you can write mind-mangling fast pbox
The last two examples were written in a sort of pseudo-code,
because I didn't want to spoil you with all the machine code, get
those brains in gear and those assemblers working!
When discussing the fill routine, I mentioned fill-patterns. Most
people think that fill-patterns are difficult to implement. But
in fact it is not so dufficult after all if you let your brains
handle the problems for a while. Consider this:
Create a fill-patterns of let's say 16*16 pixels, tucked away in
some tiny buffer inside the cavernous memory of your ST. Treat
this pattern as being a very small screen of just 16*16 pixels.
Now adapt the plot routine a little. Before plotting a pixel at
X,Y perform a logical AND with 16 on X and Y. Now check the fill-
pattern for a pixel on the new X and Y coordinates. If there is a
pixel, plot one in the real screen, if there isn't, delete the
pixel in the real screen and your fill pattern will appear!
Well, that's about it! Maybe these routines are useful to you and
you can do some nice programming with them.
Many greetings from Stefan.
P.S. Fans of science-fiction / action films: pay attention!
Visit your local cinema and check out if RoboCop is playing. If
it is not: beg, bribe, cheat, kiss, flatter or patronize the
manager until he decides to play it. It is certainly (together
with James Camerons 'Aliens') the best sf/action film I have ever
had the enormous pleasure of watching! great! dazzling! thril
ling! (sometimes a little violent) (maybe very violent) but
superbly filmed by Paul Verhoeven, a Dutch filmmaker (filmed in
the USA, so no funny robot talking Dutch)
No! There is no more!
This is definately the last page!
The text of the articles is identical to the originals like they appeared in old ST NEWS issues. Please take into consideration that the author(s) was (were) a lot younger and less responsible back then. So bad jokes, bad English, youthful arrogance, insults, bravura, over-crediting and tastelessness should be taken with at least a grain of salt. Any contact and/or payment information, as well as deadlines/release dates of any kind should be regarded as outdated. Due to the fact that these pages are not actually contained in an Atari executable here, references to scroll texts, featured demo screens and hidden articles may also be irrelevant.