Bresenhams algorithminn

Þið kannist líklegast flest við það að ætla að teikna línu eða jafnvel hring í gluggaforritinu ykkar, og uppgötva að það er aðeins meira en bara að segja það. Það sem ég ætla að tala um hér er s.s. einn frægasti og jafnframt fljótasti algorithmi í heiminum til að teikna línur.
Formúlan fyrir beina línu er y=kx+m þar sem k er hallatalan og m er fasti. Vandamálið við það að ætla að nota þessa formúlu beint er það að við getum bara verið takmarkað nákvæm. Ef nákvæm útkoma lendir mitt á milli 2 pixla hvar verður hún þá teiknuð? Beinar línur verða ekki neitt sérstaklega beinar og enda flestar með því að líta einhvernmeginn svona út:

XX——————–
—–XXX————–
———–XXX——–
—————–XXX–

Fyrir utan náttúrulega lá- og lóðréttar línur.

Til að þessi aðferð virki þurfum við að vita tvo punkta á línuni, köllum þá (x0,y0) og (x1,y1). Við getum þá reiknað út hallatöluna með formúlunni:
k=abs (y1 - y0) / abs(x1 – x0)
abs stendur fyrir algilid sem þíðir að við klippum formerki tölunar af t.d. abs(1) = 1
og abs(-1) = 1. K - gildið sem við vorum að reikna út skulum við kalla skekkju.

Það sem við gerum er að við setjum upp eina myndarlega for lykkju (hægt að nota aðrar ef maður vill) þar sem við prófum hvert einasta heiltölugildi á x-ásnum frá x0 til x1.


Það sem er í rauninni að gerast er það að fyrst teiknast upp punkturinn (x0,y0)
Síðan komum við að næsta punkti og þá höfum við tvo möguleika, annarsvegar punktinn (x0 + 1, y0) eða (x0 + 1, y0 + 1). Þannig að í hvert einasta skipti sem við höfum teiknað einn punkt þá leggjum við skekkju við (hallatala) og þegar skekkjan er orðin 0,5 eða hærri. Þá er línan nær því að vera y+1 heldur en bara y. Þegar við erum búinn að leggja 1 við y þá drögum við 1 frá heildar skekkju, því hún táknar þá hversu langt frá nýja y staðnum línan raunverulega er.



En sem komið er getur þetta fall ekki teiknað línur nema þær sem stefna frá efra vinstra horni skjásins til neðra hægri hornsins og er ekki með hærri halla tölu en 1. Við verðum að muna að efra vinstra hornið er (0,0) þar sem x ásin hækkar til hægri en y ásin hækkar niður á við.
Það sem við getum gert til að teikna línu sem hefur hærri hallatölu en 1 er að nýta okkur þá staðreind að ef við speglum þeim um ásin y = x þá fáum við út línu sem er með lægri halla tölu en 1.
Þannig að það sem við þurfum að gera er að finna út hvort að þessi lína sem við erum með sé með hærri hallatölu en 1 og síðan að spegla henni. En það eina sem þarf til þess er að í stað þess að nota Plot(x,y) þá notum við Plot(y,x)
Breyttur kóði lítur svona út:


Bool meiraeneinn;

Int y = y0, x = x0;
float heildarskekkja= 0 , skekkja = abs (y1 - y0) / abs(x1 – x0);
if(skekkja>1)
meiraeneinn=1;
else
meiraeneinn=0;

if(meiraeneinn)
{
swap(x0 , y0);
swap(x1 , y1);
}

for(x = x0; x<=x1; x++)
{

if( heildarskekkja >= 0.5 )
{
y++;
heildarskekkja = heildarskekkja – 1;
}
if(heildarskekkja)
Plot(y,x);
Else
Plot (x,y); //plot () er einhvað fall sem teiknar punkt.

Heildarskekkja = heildarskekkja + skekkja;
}

Sem stendur þá er þessi kóði ekki sérstaklega hraðvirkur, þar sem tölvan tekur sér góðan tíma í að meðhöndla kommutölur (floating point). Til að leysa það vandamál þá skilgreinum við nýjar breytur:

Deltax = abs(x1-x0);
Deltay = abs(y1-y0);

Gamla heildarskekkja var í raun Deltay / Dealtax.
Til að losa okkur við kommu tölur þá margföldum við allar kommu tölur sem komu fyrir í kóðanum hér fyrir framan með Deltax ((Deltay / Deltax)*Deltax=Deltay, sem að er heiltala). Þá komum við að þessu vandamáli:

if( heildarskekkja >= 0.5 )

En það leysum við svona:

if( 2 * heildarskekkja >= Deltax )

og einnig breytum við þá því hvað dregst frá heildarskekkja í bara Deltax, svona:


heildarskekkja = heildarskekkja – 1;

Breyta þessu í:

heildarskekkja = heildarskekkja – Deltax;

Nú er farin að koma einhver mynd á þetta. Ástæðan fyrir því að þetta er hraðvirkasti algorithmin til að teikna línur er sú að hann vinnur eingöngu með heiltölur.

Allavegana, til að klára dæmið, þá getum við ekki sem stendur teiknað línur nema sem stefna frá vinstri ofan til hægri neðan. Við notum sama kóða í grunnin en skiptum á x1 og x0 og/eða stillum hvort y hækkar eða lækkar. Svona:


if(x1<x0)
swap(x1,x0);

Deltax = abs(x1-x0);
Deltay = abs(y1-y0);
Ystep = -1;
Bool meiraeneinn;

Int y = y0, x = x0;
float heildarskekkja= 0 , skekkja = Deltay

if(y1 < y0){
Ystep = 1;

if(skekkja>1)
meiraeneinn=1;
else
meiraeneinn=0;

if(meiraeneinn)
{
swap(x0 , y0);
swap(x1 , y1);
}

for(x = x0; x<=x1; x++)
{

if( 2 * heildarskekkja >= Deltax )
{
y = y + Ystep; // fer annað hvort upp eða niður
heildarskekkja = heildarskekkja – Deltax;
}
if(heildarskekkja)
Plot(y,x);
Else
Plot (x,y); //plot () er einhvað fall sem teiknar punkt.

Heildarskekkja = heildarskekkja + skekkja;
}

Núna er algorithminn tilbúinn, hann getur teiknað línur sem stefna í hvaða átt sem er, en hægt væri að láta hann vinna en hraðar með því að í staðin fyrir að marfalda með tveimur þá getum við notað << “operatorinn” og þannig knúið fram meiri hraða. Það myndi líta svona út:
if( ( heildarskekkja << 1) >= Deltax )
í stað
if( 2 * heildarskekkja >= Deltax )

Fleirri dæmi um að kreysta fram meiri hraða væri að láta hann byrja að teikna á báðum endum línunar í einu og svo mætast í miðjuni, en ég ætla ekki að skrifa hvernig það er gert hér, orðin nógu löng grein fyrir.
Ég vona að þið hafið haft gagn og gaman af þessu rausi mínu, en þetta er skyldulesning fyrir alla þá sem ætla að verða eitthvað meira en bara console forritari. ( þótt að það sé ekki neitt ómerkilegra )
Ef þessi grein fær góðar viðtökur þá get ég líka útskýrt fyrir ykkur hvernig á að teikna hring með Bresenhams algorithmanum. Einnig gæti ég skrifað um anti-aliasing (og þá hraðvirkasta algorithman til að teikna línur og hringi ).

Í augnablikinu er ég að vinna í því að búa til library í assembly, sem myndi vera hægt að nota í C/C++ , sem mun innihalda þennan algorithma, hringja-versionið, antialiasing hringi og línur og síðast en ekki síðst bogadregnar línur, kem til með að posta því þegar það er full gert
Takk fyrir, Budingur.



p.s. Þetta er fyrsta greinin mín :D