Today we will do some things vital to most programs: lines and circles.

DENTHOR, coder for ...
_____   _____   ____   __   __  ___  ___ ___  ___  __   _____
/  _  \ /  ___> |  _ \ |  |_|  | \  \/  / \  \/  / |  | /  _  \
|  _  | \___  \ |  __/ |   _   |  \    /   >    <  |  | |  _  |
\_/ \_/ <_____/ |__|   |__| |__|   |__|   /__/\__\ |__| \_/ \_/
smith9@batis.bis.und.ac.za
The great South African Demo Team! Contact us for info/code exchange!  

Grant Smith, alias Denthor of Asphyxia, wrote up several articles on the creation of demo effects in the 90s. I reproduce them here, as they offer so much insight into the demo scene of the time.

These articles apply some formatting to Denthor's original ASCII files, plus a few typo fixes.

Circle Algorithim

You all know what a circle looks like. But how do you draw one on the computer?

You probably know circles drawn with the degrees at these points:

Anyway, Pascal doesn’t work that way… it works with radians instead of degrees (you can convert radians to degrees, but I’m not going to go into that now). Note though that in Pascal, the circle goes like this:

Even so, we can still use the famous equations to draw our circle. (You derive the following by using the theorem of our good friend Pythagoras.)

Sin (deg) = Y/R
Cos (deg) = X/R

(This is standard 8(?) maths … if you haven’t reached that level yet, take this to your dad, or if you get stuck leave me a message and I’ll do a bit of basic Trig with you. I aim to please ;-))

Where Y = your Y-coord
      X = your X-coord
      R = your radius (the size of your circle)
      deg = the degree

To simplify matters, we rewrite the equation to get our X and Y values:

Y = R*Sin(deg)
X = R*Cos(deg)

This obviously is perfect for us, because it gives us our X and Y coordinates to put into our putpixel routine (see part 1). Because the Sin and Cos functions return a Real value, we use the round function to transform it into an Integer.

Procedure Circle (oX,oY,rad:integer;Col:Byte);
VAR deg:real;
    X,Y:integer;
BEGIN
  deg:=0;
  repeat
    X:=round(rad*COS (deg));
    Y:=round(rad*sin (deg));
    putpixel (x+ox,y+oy,Col);
    deg:=deg+0.005;
  until (deg>6.4);
END;

In the above example, the smaller the amount that deg is increased by, the closer the pixels in the circle will be, but the slower the procedure. 0.005 seem to be best for the 320x200 screen. Note: ASPHYXIA does not use this particular circle algorithm, ours is in assembly language, but this one should be fast enough for most.

Line algorithms

There are many ways to draw a line on the computer. I will describe one and give you two. (The second one you can figure out for yourselves; it is based on the first one but is faster)

The first thing you need to do is pass what you want the line to look like to your line procedure. What I have done is said that x1, y1 is the first point on the screen, and x2, y2 is the second point. We also pass the color to the procedure. (Remember the screen’s top left-hand corner is (0,0); see part 1)

To find the length of the line, we say the following:

XLength = Abs(x1-x2)
YLength = Abs(y1-y2)

The Abs function means that whatever the result, it will give you an absolute, or positive, answer. At this stage I set a variable stating whether the difference between the two x’s are negative, zero or positive. (I do the same for the y’s) If the difference is zero, I just use a loop keeping the two with the zero difference positive, then exit.

If neither the x’s or y’s have a zero difference, I calculate the X and Y slopes, using the following two equations:

Xslope = Xlength / Ylength
Yslope = Ylength / Xlength

As you can see, the slopes are real numbers. NOTE: XSlope = 1 / YSlope

Now, there are two ways of drawing the lines:

X = XSlope * Y
Y = YSlope * X

The question is, which one to use? If you use the wrong one, your line will look like this:

Instead of this:

Well, the solution is as follows:

If the slope angle is in the green area, then use the first equation, if it is in the other, blue section, then use the second one. What you do is you calculate the variable on the left hand side by putting the variable on the right hand side in a loop and solving. Below is our finished line routine:

Procedure Line (x1,y1,x2,y2:integer;col:byte);
VAR x,y,xlength,ylength,dx,dy:integer;
    xslope,yslope:real;
BEGIN
  xlength:=abs (x1-x2);
  if (x1-x2)<0 then dx:=-1;
  if (x1-x2)=0 then dx:=0;
  if (x1-x2)>0 then dx:=+1;
  ylength:=abs (y1-y2);
  if (y1-y2)<0 then dy:=-1;
  if (y1-y2)=0 then dy:=0;
  if (y1-y2)>0 then dy:=+1;
  if (dy=0) then BEGIN
    if dx<0 then for x:=x1 to x2 do
      putpixel (x,y1,col);
    if dx>0 then for x:=x2 to x1 do
      putpixel (x,y1,col);
    exit;
  END;
  if (dx=0) then BEGIN
    if dy<0 then for y:=y1 to y2 do
      putpixel (x1,y,col);
    if dy>0 then for y:=y2 to y1 do
      putpixel (x1,y,col);
    exit;
  END;
  xslope:=xlength/ylength;
  yslope:=ylength/xlength;
  if (yslope/xslope<1) and (yslope/xslope>-1) then BEGIN
    if dx<0 then for x:=x1 to x2 do BEGIN
                   y:= round (yslope*x);
                   putpixel (x,y,col);
                 END;
    if dx>0 then for x:=x2 to x1 do BEGIN
                   y:= round (yslope*x);
                   putpixel (x,y,col);
                 END;
  END
  ELSE
  BEGIN
    if dy<0 then for y:=y1 to y2 do BEGIN
                   x:= round (xslope*y);
                   putpixel (x,y,col);
                 END;
    if dy>0 then for y:=y2 to y1 do BEGIN
                   x:= round (xslope*y);
                   putpixel (x,y,col);
                 END;
  END;
END;

Quite big, isn’t it? Here is a much shorter way of doing much the same thing:

function sgn(a:real):integer;
begin
     if a>0 then sgn:=+1;
     if a<0 then sgn:=-1;
     if a=0 then sgn:=0;
end;

procedure line(a,b,c,d,col:integer);
var u,s,v,d1x,d1y,d2x,d2y,m,n:real;
    i:integer;
begin
     u:= c - a;
     v:= d - b;
     d1x:= SGN(u);
     d1y:= SGN(v);
     d2x:= SGN(u);
     d2y:= 0;
     m:= ABS(u);
     n := ABS(v);
     IF NOT (M>N) then
     BEGIN
          d2x := 0 ;
          d2y := SGN(v);
          m := ABS(v);
          n := ABS(u);
     END;
     s := INT(m / 2);
     FOR i := 0 TO round(m) DO
     BEGIN
          putpixel(a,b,col);
          s := s + n;
          IF not (s<m) THEN
          BEGIN
               s := s - m;
               a:= a +round(d1x);
               b := b + round(d1y);
          END
          ELSE
          BEGIN
               a := a + round(d2x);
               b := b + round(d2y);
          END;
     end;
END;

This routine is very fast, and should meet almost all of your requirements (ASPHYXIA used it for quite a while before we made our new one.) In the end program, both the new line routine and the circle routine are tested. A few of the procedures of the first parts are also used.

Line and circle routines may seem like fairly trivial things, but they are a vital component of many programs, and you may like to look up other methods of drawing them in books in the library.

A good line routine to look out for is the Bresenham’s line routine. There is a Bresenham circle routine too. I have documentaton for them if anybody is interested. They are by far some of the fastest routines you will use.