Here is bresenhem's Line and Circle Algorithm

[663 <663@nu.edu.pk>]

 <<BRES.TXT>> 
I thought it would be helpful to you all there studying graphics

	----------
	From:  Kamel Serend [SMTP:kserend@twowaytv.co.uk]
	Sent:  Friday, July 07, 2000 5:37 PM
	To:  gameprogrammer@gameprogrammer.com
	Subject:  RE: Drawing a circle

	Hi,

	Just a little question...
	Why nobody is using the Bresenham algorithm as applied to circles ?
	I thought it is the simpliest and fastest way to do the things, but
I must
	be wrong...
	Any body ?

	Kamel

	> -----Original Message-----
	> From:	Paul Robson [SMTP:probson@powerup.com.au]
	> Sent:	Friday, July 07, 2000 12:44 PM
	> To:	gameprogrammer@gameprogrammer.com
	> Subject:	RE: Drawing a circle
	> 
	> you could always do it using the circle formula.  It's a lot more
reliable
	> anyway, you don't get extra pixels being drawn on top of each
other for
	> small circles or have large gaps for big circles (ie circles with
a radius
	> >
	> 360)
	> 
	> the circle formula is r^2 = x^2 + y^2
	> this can be rearranged to be:  y = (plus-or-minus)sqrt(r^2-x^2)
	> 
	> So, to implement this.. you would have something like this:
	> 
	> void drawline(x1, y1, x2, y2);
	> 
	> void drawcircle (x, y, r)
	> {
	>   int r2 = r*r;
	>   for (int i = x-r; i < x+r-1; i+=2)
	>   {
	>     j = i+1;
	>     drawline( i, sqrt( r2 - (i-x)*(i-x), j, sqrt( r2 - (j-x)*(j-x)
);
	>     drawline( i, -sqrt( r2 - (i-x)*(i-x), j, -sqrt( r2 -
(j-x)*(j-x) );
	>   }
	> }
	> 
	> I think that should work.. i haven't actually typed it in or
anything so
	> there's bound to be typos :)
	> 
	> Paul Robson
	> 
	> > -----Original Message-----
	> > From: gameprogrammer-owner@gameprogrammer.com
	> > [mailto:gameprogrammer-owner@gameprogrammer.com]On Behalf Of
Kevin Shea
	> > Sent: Friday, 7 July 2000 7:08 PM
	> > To: gameprogrammer@gameprogrammer.com
	> > Subject: Re: Drawing a circle
	> >
	> >
	> > On this whole subject of drawing circles, you simply don't want
	> > anything to do with sin()/cos() if you can avoid it.
	> >
	> > Since the original question was for c++/assembler, check out
Michael
	> > Abrash's "Black Book of Graphics Programming" (something like
that) -
	> > it has circle-drawing routines in C and assembly for (I think)
various
	> > VGA modes.
	> >
	> > Kev
	> >
	> > Kevin Wolfskill wrote:
	> > >
	> >
	> > Lots cut out.
	> >
	> > > >----- Original Message -----
	> > > >From: Lionel Pinkhard <lionelpi@mweb.co.za>
	> > > >To: <gameprogrammer@gameprogrammer.com>
	> > > >Sent: Saturday, July 05, 1980 3:04 AM
	> > > >Subject: Drawing a circle
	> > > >
	> > > >
	> > > > > Hi,
	> > > > >
	> > > > > Can somebody please tell me how to draw a circle in
C++/Assembler
	> > > >without
	> > > >using any graphics libraries (so far my game's not using
any)?
	> > (under DOS).
	> > > > >
	> > > > > Kind regards,
	> > > > >
	> > > > > Lionel Pinkhard
	> > > > >
=================================================================
	> > > > > The GameProgrammer.Com mailing list is for the open
discussion
	> > > > > of any topic related to the art, science, and business of
	> > > > > programming games. This list is especially tolerant of
beginners.
	> > > > > We were all beginners once
	> > > > >
	> > > > > To SUBSCRIBE or UNSUBSCRIBE please visit:
	> > > > > http://gameprogrammer.com/mailinglist.html
	> > > >
	> > >
>=================================================================
	> > > >The GameProgrammer.Com mailing list is for the open
discussion
	> > > >of any topic related to the art, science, and business of
	> > > >programming games. This list is especially tolerant of
beginners.
	> > > >We were all beginners once
	> > > >
	> > > >To SUBSCRIBE or UNSUBSCRIBE please visit:
	> > > >http://gameprogrammer.com/mailinglist.html
	> > >
	> > >
	>
________________________________________________________________________
	> > > Get Your Private, Free E-mail from MSN Hotmail at
	> http://www.hotmail.com
	> > >
	> > >
=================================================================
	> > > The GameProgrammer.Com mailing list is for the open discussion
	> > > of any topic related to the art, science, and business of
	> > > programming games. This list is especially tolerant of
beginners.
	> > > We were all beginners once
	> > >
	> > > To SUBSCRIBE or UNSUBSCRIBE please visit:
	> > > http://gameprogrammer.com/mailinglist.html
	> > >
=================================================================
	> > > The GameProgrammer.Com mailing list is for the open discussion
	> > > of any topic related to the art, science, and business of
	> > > programming games. This list is especially tolerant of
beginners.
	> > > We were all beginners once
	> > >
	> > > To SUBSCRIBE or UNSUBSCRIBE please visit:
	> > > http://gameprogrammer.com/mailinglist.html
	> >
=================================================================
	> > The GameProgrammer.Com mailing list is for the open discussion
	> > of any topic related to the art, science, and business of
	> > programming games. This list is especially tolerant of
beginners.
	> > We were all beginners once
	> >
	> > To SUBSCRIBE or UNSUBSCRIBE please visit:
	> > http://gameprogrammer.com/mailinglist.html
	> >
	> 
	> =================================================================
	> The GameProgrammer.Com mailing list is for the open discussion
	> of any topic related to the art, science, and business of
	> programming games. This list is especially tolerant of beginners.
	> We were all beginners once
	> 
	> To SUBSCRIBE or UNSUBSCRIBE please visit:
	> http://gameprogrammer.com/mailinglist.html
	=================================================================
	The GameProgrammer.Com mailing list is for the open discussion
	of any topic related to the art, science, and business of
	programming games. This list is especially tolerant of beginners.
	We were all beginners once

	To SUBSCRIBE or UNSUBSCRIBE please visit:
	http://gameprogrammer.com/mailinglist.html
           
                 Bresenham's Line and Circle Algorithms 
		========================================

                 Written for the PC-GPE by Mark Feldman
                   e-mail address : pcgpe@ix.netcom.com
                             
-----------------------------------------------------------------------------

NOTICE: This file is included with permission from the author and is 
	part of the PC-GPE collection. This document may not be
	distributed separately from here.

	The entire PC-GPE collection may be downloaded from:
	ftp://x2ftp.oulu.fi/pub/msdos/programming/gpe/pcgpe10.zip

-----------------------------------------------------------------------------
           

=============================================================================
 Disclaimer 
============

I assume no responsibility whatsoever for any effect that this file, the
information contained therein or the use thereof has on you, your sanity,
computer, spouse, children, pets or anything else related to you or your
existance. No warranty is provided nor implied with this information.

=============================================================================
 Introduction 
==============

Bresenham is a pretty smart cookie (note the use of the word "is", last I
heard he was still working for IBM). This file contains the algorithms he
developped for drawing lines and circles on a pixelated display system
such as the VGA.

=============================================================================
 Line Algorithm 
================

The basic algorithm works for lines which look like this:


      o-------                         |
     p1       --------                 | deltay
                      -------      p2  |
                             -------o  |

      ----------------------------------
                  deltax

where p1 = (x1,y1),
      p2 = (x2, y2),
      x and y are both increasing from p1 to p2,
      deltax = x2 - x1,
      deltay = y2 - y1 and
      deltax >= deltay.

All other types of lines can be derived from this type. I'll get to this
bit later.

First you need to perform the following intialisation:

x = x1
y = y1
d = (2 * deltay) - deltax

x is the current x location, you will add 1 to this variable after every
pixel you draw until all pixels have been drawn.
y is the current y location. The decision variable is used to determine
when to add 1 to this value. d is the decision variable which will be used
to keep a track of what to do.

Now you loop across the screen from x1 to x2 and for each loop perform the
following operations for each pixel :

PutPixel(x, y);  { Draw a pixel at the current point }
if d < 0 then
    d := d + (2 * deltay)
else
  begin
    d := d + 2 * (deltay - deltax);
    y := y + 1;
  end;
x := x + 1;

It's that simple!

=============================================================================
 Speeding Up The Line Algorithm 
================================

There are several useful techniques for speeding up Bresenhams line
algorithm.

For starters, notice that all multiplications are by 2. This can be
performed with a simple shift left instruction (Shl in Pascal, << in C).

Next notice that the values you add to the decision variable do not change
throughout the loop, so they can be precalculated beforehand.

One property of lines is that they are symetrical about their mid-points,
and we can use this property to speed up the algorithm. Store two x and y
values, (xa, ya) and (xb, yb). Have each pair start on either end of the
line. For each pass through the loop you draw the pixel at both points, add
1 to xa and subtract one from xb. When d >= 0 add 1 to ya and subtract one
from yb. You then only need to loop until xa = xb.

It's also obvious that if the decision variable becomes the same value
it was when it was initialised, then the rest of the line is just
copies of the line you have already drawn up to that point. You might be
able to speed the algorithm up by keeping an array of how y has been
modified and then use this array if the line starts repeating itself. If
you are using the Intel registers to store all values then you probably
wouldn't get much of a speed increase (in fact it could slow it down), but
it would probably be useful for thing like linear texture mapping (discussed
below). I've never actually tried implementing this technique, and I would
like to hear the results if anyone does.

Above all remember that these optimisations will only significantly speed
up the line drawing algorithm if the whole thing is done in assembly. A
profile of the example program at the end of this file showed that 40% of
CPU time was spent in the slow PutPixel routine I was using, the loop
mechanics and testing the sign of the decision variable.

=============================================================================
 Other Uses for the Line Algorithm 
===================================

A line can be represented by the equation y = mx + c, where
m = deltay / deltax. Note that this is a version of the standard linear
equation ax + bx + c = 0. There are many algorithms which use this equation.

One good use for the bresenham line algorithm is for quickly drawing filled
concave polygons (eg triangles). You can set up an array of minimum and
maximum x values for every horizontal line on the screen. You then use
bresenham's algorithm to loop along each of the polygon's sides, find where
it's x value is on every line and adjust the min and max values accordingly.
When you've done it for every line you simply loop down the screen drawing
horizontal lines between the min and max values for each line.

Another area is in linear texture mapping (see the PC-GPE article on texture
mapping). This method involves taking a string of bitmap pixels and
stretching them out (or squashing them in) to a line of pixels on the screen.
Typically you would draw a vertical line down the screen and use Bresenhams
to calculate which bitmap pixel should be drawn at each screen pixel.

=============================================================================
 Circle Algorithm 
==================

Circles have the property of being highly symetrical, which is handy
when it comes to drawing them on a display screen.

      |y          (This diagram is supposed to be a circle, try viewing
      |           it in 50 line mode).
  \ ..... /
   .  |  .        We know that there are 360 degrees in a circle. First we
  . \ | / .       see that a circle is symetrical about the x axis, so
  .  \|/  .       only the first 180 degrees need to be calculated. Next
--.---+---.--     we see that it's also symetrical about the y axis, so now
  .  /|\  . x     we only need to calculate the first 90 degrees. Finally
  . / | \ .       we see that the circle is also symetrical about the 45
   .  |  .        degree diagonal axis, so we only need to calculate the
  / ..... \       first 45 degrees.
      |
      |

Bresenhams circle algorithm calculates the locations of the pixels in the
first 45 degrees. It assumes that the circle is centered on the origin. So
for every pixel (x,y) it calculates we draw a pixel in each of the 8 octants
of the circle :

PutPixel(CenterX + X, Center Y + Y)
PutPixel(CenterX + X, Center Y - Y)
PutPixel(CenterX - X, Center Y + Y)
PutPixel(CenterX - X, Center Y - Y)
PutPixel(CenterX + Y, Center Y + X)
PutPixel(CenterX + Y, Center Y - X)
PutPixel(CenterX - Y, Center Y + X)
PutPixel(CenterX - Y, Center Y - X)

So let's get into the actual algorithm. Given a radius for the circle
we perform this initialisation:

d := 3 - (2 * RADIUS)
x := 0
y := RADIUS
Now for each pixel we do the following operations:

Draw the 8 circle pixels
if d < 0 then
    d := d + (4 * x) + 6
else
  begin
    d := d + 4 * (x - y) + 10
    y := y - 1;
  end;

And we keep doing this until x = y. Note that the values added to the
decision variable in this algorithm (x and y) are constantly changing, so
we cannot precalculate them. The muliplications however are by 4, and we
can accomplish this by shifting left twice.

=============================================================================
 A Pascal General Line Procedure 
=================================

The basic bresenham line algorithm can be modified to handle all types of
lines. In this section assume that deltax = abs(x2 - x1) and
deltay = abs(y2 - y1).

First let's take lines where deltax >= deltay. Now if x1 > x2 then you will
need to subtract 1 from x for every pass through the loop. Similarly if y1 >
y2 then you will be also need to subtract 1 from y for every pass through the
loop where d < 0.

Lines where deltax < deltay can be handled the same way, you just swap all
the deltax's and deltay's around.

The fastest method of handling all cases is to write a custom routine for
each of the 8 line types:

1) x1 <= x2, y1 <= y2, deltax >= deltay
2) x1 <= x2, y1 <= y2, deltax <  deltay
3) x1 <= x2, y1 >  y2, deltax >= deltay
4) x1 <= x2, y1 >  y2, deltax <  deltay
5) x1 >  x2, y1 <= y2, deltax >= deltay
6) x1 >  x2, y1 <= y2, deltax <  deltay
7) x1 >  x2, y1 >  y2, deltax >= deltay
8) x1 >  x2, y1 >  y2, deltax <  deltay

This will give you the fastest results, but will also make your code 8
times larger! Alternatively you can declare a few extra variables and
use a common inner loop for all lines:

numpixels = number of pixels to draw
          = deltax if deltax >= deltay or
          = deltay if deltax < deltay
dinc1 = the amount to add to d when d < 0
dinc2 = the amount to add to d when d >= 0
xinc1 = the amount to add to x when d < 0
xinc2 = the amount to add to x when d >= 0
yinc1 = the amount to add to y when d < 0
yinc2 = the amount to add to y when d >= 0

The following is a simple example program which uses this technique:


=============================================================================

{

BRESLINE.PAS - A general line drawing procedure.
               By Mark Feldman

This is a very simple implementation of bresenhams' line algorithm with
no optimisations. It can draw about 6000 random lines a second in mode 13h
on my 486SX33 with sloooooow Paradise Extended VGA.

}

procedure Line(x1, y1, x2, y2 : integer; color : byte);
var i, deltax, deltay, numpixels,
    d, dinc1, dinc2,
    x, xinc1, xinc2,
    y, yinc1, yinc2 : integer;
begin

  { Calculate deltax and deltay for initialisation }
  deltax := abs(x2 - x1);
  deltay := abs(y2 - y1);

  { Initialize all vars based on which is the independent variable }
  if deltax >= deltay then
    begin

      { x is independent variable }
      numpixels := deltax + 1;
      d := (2 * deltay) - deltax;
      dinc1 := deltay Shl 1;
      dinc2 := (deltay - deltax) shl 1;
      xinc1 := 1;
      xinc2 := 1;
      yinc1 := 0;
      yinc2 := 1;
    end
  else
    begin

      { y is independent variable }
      numpixels := deltay + 1;
      d := (2 * deltax) - deltay;
      dinc1 := deltax Shl 1;
      dinc2 := (deltax - deltay) shl 1;
      xinc1 := 0;
      xinc2 := 1;
      yinc1 := 1;
      yinc2 := 1;
    end;

  { Make sure x and y move in the right directions }
  if x1 > x2 then
    begin
      xinc1 := - xinc1;
      xinc2 := - xinc2;
    end;
  if y1 > y2 then
    begin
      yinc1 := - yinc1;
      yinc2 := - yinc2;
    end;

  { Start drawing at <x1, y1> }
  x := x1;
  y := y1;

  { Draw the pixels }
  for i := 1 to numpixels do
    begin
      PutPixel(x, y, color);
      if d < 0 then
        begin
          d := d + dinc1;
          x := x + xinc1;
          y := y + yinc1;
        end
      else
        begin
          d := d + dinc2;
          x := x + xinc2;
          y := y + yinc2;
        end;
    end;
end;

=============================================================================

Note that if you are writing a line routine for mode 13h (for example) you
can speed it up by converting the inner loop to assembly and including
mode 13h specific code. This portion of the above routine works the same but
the <x, y> values are stored in a single variable (screen) which holds the
memory address of the current pixel, screeninc1 and screeninc2 are the
update values for screen.

=============================================================================

var screen : word;
    screeninc1, screeninc2 : integer;
     .
     .
     .
  { Start drawing at <x1, y1> }
  screen := word(y1) * 320 + x1;
  screeninc1 := yinc1 * 320 + xinc1;
  screeninc2 := yinc2 * 320 + xinc2;

  { Draw the pixels }
  asm

    { Use as many registers as are available }
    push $A000
    pop es
    mov di, screen
    mov dx, d
    mov al, color
    mov cx, numpixels
    mov bx, dinc1

    @bres1:

    { Draw the current pixel and compare the decision variable to 0 }
    mov es:[di], al
    cmp dx, 0
    jnl @bres2

    { D < 0 }
    add dx, bx { bx = dinc1 }
    add di, screeninc1
    jmp @bres3

    @bres2:

    { D >= 0 }
    add dx, dinc2
    add di, screeninc2

    @bres3:

    loop @bres1
  end;

=============================================================================