Subliminal Extacy #03
01 апреля 2001

Draw Routine with Bresenham Algorithms

Draw Routine with Bresenham Algorithms
             Draw Routine with Bresenham Algorithms
                       Written by Mikezt

             This article is dedicated to baze/Зsc.

One of the most basic graphic routines is a line draw. When  you
try to write a draw routine  you may find it a bit  complicated.
Don't worry, here's one of way of doing it.

Bresenham algorithms have an advantage over methods because they
work with  integer numbers.  So they  can be  easily written  in
machine code.  Before we  start, get  ready for  some mathematic
expressions. I'll write lower indexes in [].

Abscissa is defined with two  points (x1, y1)  and  (x2, y2) and
can be written in the expression:

                           y = kx + q

where k is the direction and q is the shift on the y axis.

Direction  k   indicates  inclination   of  the line  and divide  
coordination  system  to  eight parts  (see  pic. 1).  We  get a  
situation  where k is positive  and less than 1.  Let's  presume
that point  (x[i], y[i])  was drawn.  For each  pixel we have to 
compute  the  differences  from the  ideal  course  of  abscissa 
(pic. 2).

Difference of both possible points are:
            D1 = y - y[i] = k * (x[i] + 1) + q - y[i]
        D2 = y[i] + 1 - y = y[i] + 1 - k * (x[i] + 1) - q
Difference of these two values is equal to:
     D = D1 - D2 = 2 * k * (x[i] + 1) - 2 * y[i] + 2 * q - 1

Along this  difference we can choose the right point. It's clear 
that  the factor of decision is it's sign. A negative value will
select the point (x[i] + 1, y[i] + 1),  and a positive  one will 
select  (x[i] + 1, y[i]).  The disadvantage is real character of 
values. We can remove this disadvantage  by  multiply difference
expression  by  (x2 - x1) and  we  get the  expression  which is 
called decision:

d[i]=D*(x2-x1)=2*(y2-y1)*(x[i]+1)-2*y[i]*(x2-x1)+(2*q-1)*(x2-x1)

and after a slight adjustment:

  d[i]=2*(y2-y1)*x[i]-2*y[i]*(x2-x1)+2*(y2-y1)+(2*q-1)*(x2-x1)

Expression 2*(y2-y1)+(2*q-1)*(x2-x1) is constant and we indicate
it with c. so:

     d[i] = 2 * (y2 - y1) * x[i] - 2 * y[i] * (x2 - x1) + c

Now this is an integer value, but it's quite complicated. If  we
express  decision for the  next point we can  write a  recursive
relation. Here is decision for the next point:

    d[i+1] = 2*(y2 - y1)*(x[i] + 1) - 2*y[i+1]*(x2 - x1) + c

After  substracting  these  two  decisions we  can  express  the
decision value in a recursive form:

 d[i+1] = d[i] + 2 * (y2 - y1) - 2 * (x2 - x1) * (y[i+1] - y[i])

Expression (y[i+1] - y[i]) can only store values 0 and 1 and  we
can write modified expressions to compute decision:

  d[i] < 0   =>  d[i+1] = d[i] + 2 * (y2 - y1)
  d[ ] >= 0  =>  d[i+1] = d[i] + 2 * (y2 - y1) - 2 * (x2 - x1)

Last thing you  need to know is the decision  for the first step
and here is:

                d[1] = 2 * (y2 - y1) - (x2 - x1)

So all  you must do  is check the  decision for  it's sign, if's
negative, move  the y coordinate, compute decision  for the next
step and test if you've drawn the  last point. If not, do it all
again. For  the other direction  that 0 x1  (or any other one  and choose  variants with
  this comparison)  and if it's true  then there's no  change at
  the start and end points.
- decision equations should be  divided by 4 (two  rotations) so
  you can store it in an 8bit register, and no precision's lost.

Uf, that's all. My routine is available (I hope) on the HighTech
project (http://hightech.da.ru). I hope you understand what I've
tryed to say here. If not feel free to write to me. Bye!

                                                     mike/zt/ctl
                                                 jurica@sknet.sk



Другие статьи номера:

One more boring text from Yerzmyey

23 Things Which You Can Do If A Program Crashes

Again TRDOS TuRDOS TRDOS!

Alternatives to LOL

The Spectrum SE - Andy Owen Interview

Are You A Communist?

Assholes Speak Russian

Beginners Guide to Russian

brief information about CC1

Can You Say Dezign?

Cheat's Guide To TR-DOS Cracking: An Incomprehensible Techy

Chocasutra - A Chocoholics Guide To Sex

Circulation Of Warez On Today's Scene

Compatibility: An open letter to the Russian scene

Complex 99, And The East/West Divide

Project: Describe Your Disk Interface

Devious and Lethal Cocktails

Demo Parties: Breaking The Mould

Draw Routine with Bresenham Algorithms

DRUNKENNESS

Editorial

How To Become The Best PC Swapper In The World ... EVER!

How To Contribute To Subliminal Extacy

How to use Subliminal Extacy... and more

How Demos Are REALLY Made

IMPORTANT!

Independent Films

Interview with K-0s / Raww Arse

Is C64 Better Than Speccy?

Just Intonation: Making music come to life

Party report: ZX Party 2000; Wroclaw, Poland; 25-27 August 2000

Questions that Still Remain Unanswered (Well, not anymore)

Some Stupid Shitty Rubbish From Yerzmyey

Squernookle!

News From Ukraine: Still Enough Haxxors In Smash!

The Art of Spectrum Coding - Chapter I

The Prince Of 4096 Bytes Conquers New Lands

The Smallest Article in the World

Timex in Portugal

Tips - OLD telephone directories make ideal personal address books.

What A Shame!

Whopping Great Big Lists: A discussion

Your Stars

Your Horoscopes by Mystic Bogie

Zilog: Dep Is Ugly But I Am More

Zm_Polyhedron - Speccy of the future


Темы: Игры, Программное обеспечение, Пресса, Аппаратное обеспечение, Сеть, Демосцена, Люди, Программирование

Похожие статьи:
Наезды - Scorpion, GMX и Зонов.
Юмор - Анекдоты.
Что нового - О новинках в Минске.
Авторское описание - Описание MMD v2.21
События - новогодний сисопник ZXNet.

В этот день...   15 октября