Graphic Algorhythms

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)

Procedure Fill(X%,Y%)
     While Point(X%,Y%)=0
          Plot X%,Y%
          @Fill(X%-1,Y%)
          @Fill(X%+1,Y%)
          @Fill(X%,Y%-1)
          @Fill(X%,Y%+1)
     Wend
Return

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 
the screen.

Procedure Line(X0%,Y0%,X1%,Y1%)
     If X0%>X1%                    ! make sure the line is drawn 
          Swap X0%,X1%             ! left-right and top-bottom
     Endif
     If Y0%>Y1%
          Swap Y0%,Y1%
     Endif
     Dx%=X1%-X0%                   ! horizontal distance to cross
     Dy%=Y1%-Y0%                   ! vertical distance
     Dy2%=2*Dy%                    ! 2*Dy for speed reasons
     E%=2*Dx%-Dy%         
     X%=X0%
     Y%=Y0%
     For C%=1 To Dx%
          If E%>0
               Inc Y%
               Add E%,2*(Dy%-Dx%)
          Else
               Add E%,Dy2%
          Endif
          Inc X%    
          Plot X%,Y%
     Next C%
Return

Here follows the routine to draw a circle

Procedure Circle(Mx%,My%,R%)
     X%=0
     Y%=R%
     E%=3-2*R%
     While X%<=Y%
          Plot Mx%+X%,My%+Y%
          Plot Mx%+X%,My%-Y%  
          Plot Mx%-X%,My%+Y%
          Plot Mx%-X%,My%-Y%
          Plot Mx%+Y%,My%+X%
          Plot Mx%+Y%,My%-X%
          Plot Mx%-Y%,My%+X%
          Plot Mx%-Y%,My%-X%
          ' 8 points are plotted from X%,Y%
          If E%>0
               Add E%,4*(X%-Y%)+10
               Dec Y%
          Else
               Add E%,4*X%+6
          Endif
          Inc X%
     Wend
Return

If you want to draw filled circles, use this routine:
Procedure Pcircle(Mx%,My%,R%)
     X%=0
     Y%=R%
     E%=3-2*R%
     While X%<=Y%
          Line Mx%-X%,My%+Y%,Mx%+X%,My%+Y%
          Line Mx%-X%,My%-Y%,Mx%+X%,My%-Y%
          Line Mx%-Y%,My%+X%,Mx%+Y%,My%+X%
          Line Mx%-Y%,My%-X%,Mx%+Y%,My%-X%
          If E%>0
               Add E%,4*(X%-Y%)+10
               Dec Y%
          Else
               Add E%,4*X%+6
          Endif
          Inc X%
     Wend
Return   

'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.

Machine-code programming.
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?
Consider this:
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 
for you!

Plotting pixels.
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)
          rts         

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:

Procedure Hline(X0,X1,Y)
     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
Return

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:

Procedure Vline(X,Y0,Y1)
     Adress = ScreenAdress + X/8 + Y0*80     
     Bitnr  = X AND 7
     Length = Y1-Y0 
Loop      
     Bset Bitnr,Adress
     Adress = Adress + 80    
     Dbra Length, Loop
Return

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 
routines.
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!