Linjojen rasterointi

Rasteroinnissa linjat on peruskoulun tehtävänä tietokonegrafiikan , jossa linja on piirretty ( rasteroidaan ) pisteen verkkoon on rasterin graafisen tai rasterigrafiikan laitteeseen . Tätä tarkoitusta varten ne pisteet tai pikselit ovat värillisiä, jotka arvioivat ihanteellisen reitin mahdollisimman tarkasti .

Basic algoritmit vain rasteroinut rivit yksi väri. Parempi näyttö, jossa on useita värejä, saadaan edistyneillä menetelmillä, jotka tukevat liimausta (reunan tasoitus).

Koska monimutkaisemmat geometriset luvut, kuten polygonit ja mahdolliset käyrät, koostuvat usein tietokonegrafiikan viivasegmenteistä, viivojen rasterointi muodostaa myös lähtökohdan niiden rasteroinnille. Toinen sovellus, joka vaatii usein suuren määrän rivejä voidaan tehdä on näyttö lankamallikuvana malleja .

Kaksi rasteroitua linjaa. Värilliset pikselit näkyvät ympyröinä. Yllä: yksivärinen rasterointi; alla: Gupta-Sproull antialiasing, ihanteellinen viiva pidetään tässä pintana.

Yksivärinen rasterointi

Yksivärinen rasterointi piirtää viivoja yhdellä etualan värillä taustalla. Se soveltuu laitteille, joissa on yksivärinen näyttö, esimerkiksi lasertulostimille .

Rasteroitavan viivan alku- ja loppupisteet määritetään yleensä kokonaislukukoordinaateina, ts. Ne ovat suoraan rasterin pisteissä. Siksi suurin osa menetelmistä on muotoiltu vain sellaisille alku- ja loppupisteille. Paksujen viivojen rasterointiin on useita vaihtoehtoja, jotka sopivat myös muille käyrille, katso artikkeli Seulonta .

Yksinkertaiset menetelmät

Naiivi seulontamenetelmä pyöristyksen avulla

Yksinkertaisin tapa rasteroida on toteuttaa suoraviiva määrittävä yhtälö suoraan. Jos ( x , y ) on aloituskohta ja ( x _e , y _e ) loppuun linjan pistettä, pisteet linjalla täyttävät suora yhtälö , jossa on kaltevuus . ${\ displaystyle y = m (x-x_ {a}) + y_ {a}}$${\ displaystyle \ textstyle m = {\ frac {\ Delta y} {\ Delta x}} = {\ frac {y_ {e} -y_ {a}} {x_ {e} -x_ {a}}}}$

Rivi piirretään laskemalla vastaava arvo on silmukka kullekin välille ja arvon tämän kaavan mukaisesti, ja pyöristämällä se lähimpään kokonaislukuun. Pikseli ( x , y ) on sitten värillinen. ${\ displaystyle x}$${\ displaystyle x_ {a}}$${\ displaystyle x_ {e}}$${\ displaystyle y}$

Tämä menetelmä on tarpeettoman hidas, koska silmukassa suoritetaan kertolasku, joka useimmissa tietokoneissa vaatii huomattavasti enemmän laskenta-aikaa kuin summaus tai vähennys. Nopeampi menetelmä on ottaa huomioon kahden peräkkäisen vaiheen ero:

${\ displaystyle y_ {i + 1} -y_ {i} \!}$	${\ displaystyle = (m (x_ {i + 1} -x_ {a}) + y_ {a}) - (m (x_ {i} -x_ {a}) + y_ {a}) \!}$
	${\ displaystyle = m (x_ {i + 1} -x_ {i}) \!}$
	${\ displaystyle = m \!}$.

Näin ollen riittää, aloittaa kanssa ( x , y ) ja kasvaa joka kerta, kun silmukka ajetaan läpi . Tämä menetelmä tunnetaan myös nimellä digitaalinen differentiaalianalysaattori (DDA). ${\ displaystyle y}$${\ displaystyle m}$

Koska pyöristys lähimpään kokonaislukuun vastaa pyöristystä , voidaan käyttää myös ylimääräistä säätömuuttujaa , joka alustetaan arvolla 0,5 ja joka lisätään jokaisen silmukan läpäisyn yhteydessä. Aina kun muuttuja saavuttaa tai ylittää 1,0, se kasvaa yhdellä ja vähentää 1,0 muuttujasta. Tämä tarkoittaa, että pyöristämistä ei enää tarvita. Tätä menetelmää voidaan muotoilla uudelleen käyttää vain nopeammin kokonaisluku ja se voidaan tehdä elegantisti toteuttaa sisään kokoonpano kielellä . Alussa tarvitaan kuitenkin edelleen hidas jako ( ), jota lyhyillä linjoilla ei voida kompensoida nopealla silmukalla. ${\ displaystyle y}$${\ displaystyle y + 0 {,} 5}$${\ displaystyle m}$${\ displaystyle y}$ ${\ displaystyle \ Delta y / \ Delta x}$

Yleistäminen mihin tahansa suuntaan

Kaikkien viivojen rasterointi käyttämällä symmetriaominaisuuksia. Alkuperäisen menettelyn sallittu alue on esitetty värillisenä; kolme muutosta algoritmiin avaavat myös muut alueet.

Juuri kuvatut menetelmät toimivat vain viivojen ollessa välillä 0 ja 1, mikä vastaa 0 ° - 45 ° kulmaa vaakatasoon nähden. Viivaa ei piirretä tai piirretä väärin muille rinteille. Riittää kuitenkin kuvaamaan algoritmi vain rinteille, jotka ovat välillä 0 ja 1, koska muut viivat voidaan näyttää oikein käyttämällä symmetrioita. Tämä tapahtuu seuraavilla kolmella muutoksella:

1. Kaksi tapausta erotetaan toisistaan ​​sen mukaan, onko (määrän suhteen) vai päinvastoin. Ensimmäisessä tapauksessa silmukka ajetaan läpi kuten aiemmin ja lasketaan silmukan rungossa , muuten se ajetaan läpi ja lasketaan käyttäen.${\ displaystyle \ Delta x> \ Delta y}$${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle y}$${\ displaystyle x}$
2. Silmukan rungossa tai sitä ei lisätä 1: llä, mutta - tai - merkistä riippuen arvo +1 tai −1 lisätään.${\ displaystyle y}$${\ displaystyle x}$${\ displaystyle \ Delta y}$${\ displaystyle \ Delta x}$
3. Jos tai , silmukka on ajettava taaksepäin.${\ displaystyle \ Delta x <0}$${\ displaystyle \ Delta y <0}$

Näitä yleistyksiä soveltamalla voidaan luoda seuraava taulukko paremman yleiskuvan saamiseksi:

Missä i m <= 1 -arvoille välillä 0 ja ja m> 1 -arvoille välillä 0 ja . Tämä taulukko kattaa myös linjat, jotka ovat yhdensuuntaisia ​​X- tai Y-akselin kanssa, eikä niitä tarvitse tarkastella erikseen. Määritetty suunta viittaa oikealla olevaan kuvaan olettaen, että x kasvaa oikealle ja y kasvaa ylöspäin. x1 ja y1 ovat suoran aloituskohdan koordinaatit ja x2 ja y2 ovat loppupisteen koordinaatit. ${\ displaystyle \ Delta x}$${\ displaystyle \ Delta y}$

Lisäksi seuraava pseudokoodi voidaan luoda vain muuttamalla merkkiä, joka kattaa kaikki kahdeksan kuvattua tapausta:

  signX = 1;
  signY = 1;

  if x1 > x2
      signX = -1;

  if y1 > y2
      signY = -1;

  if m <= 1
      for i=0; i <= deltaX; i++
          drawPixel( ceil(x1 + i * signX), ceil(y1 + i * m * signY) )
  else
      for i=0; i<= deltaY; i++
          drawPixel( ceil(x1 + i / m * signX), ceil(y1 + i * signY) )

Missä ce () on funktio pyöristää ylöspäin ja drawPixel voi olla mikä tahansa toiminto pikselin asettamiseksi.

Bresenhamin algoritmi

Vanhimmat julkaistut algoritmit linjojen rasteroimiseksi ovat peräisin 1960-luvun alusta. Niitä käytettiin ohjaamaan digitaalisia piirtureita , joissa kynä pystyi liikkumaan vain vaakasuoraan, pystysuoraan tai vinosti ristikkoon kiintein välein. Tähän sisältyi myös Jack Bresenhamin vuonna 1963 esittämä Bresenham-algoritmi , joka käyttää vain kokonaislukuja. Pitteway antoi vastaavan johdannaisen tälle algoritmille, jolla on etuna Bresenhamin melko geometriseen muotoiluun verrattuna, että sitä voidaan soveltaa myös muihin käyriin kuin viivoihin. Tuloksena oleva algoritmi, jota joskus kutsutaan "keskipistealgoritmiksi", on täsmälleen sama kuin Bresenhamin julkaisussa.

Seuraavan pikselin valinta Bresenham-algoritmissa

Bresenham-algoritmin idea on valita kahden pikselin välillä oikealla ("itä") ja oikeassa yläkulmassa ("koillinen") kussakin vaiheessa piirretystä viimeisestä pikselistä. Pikseli, joka on lähempänä ihanteellista viivaa, valitaan. Voit tehdä tämän katsomalla keskipisteen muotoilun pikselien välistä keskipistettä ja : jos se on ihanteellisen viivan yläpuolella, se on lähempänä, muuten . ${\ displaystyle M}$${\ displaystyle O}$${\ displaystyle EI}$${\ displaystyle M}$${\ displaystyle O}$${\ displaystyle EI}$

Suoran vastakohdan löytämiseksi käytetään toista suoraviivayhtälön muotoa: ${\ displaystyle M}$

${\ displaystyle F (x, \, y) = ax + by + c = \ Delta y \ kertaa x- \ Delta x \ kertaa y + c = 0}$.

F ( x, y ) on 0 viivan pisteille, positiivinen alapisteille ja negatiivinen viivan yläpuolelle. Jos koordinaatit lisätään tähän yhtälöön , saadaan arvo ${\ displaystyle M}$

${\ displaystyle \ textstyle d_ {i} = F (x_ {i} +1, \, y_ {i} + {\ frac {1} {2}}) = \ Delta y (x_ {i} +1) - \ Delta x (y_ {i} + {\ frac {1} {2}}) + c}$.

Tämän kontrollimuuttujan merkistä riippuen pikseli tai valitaan. ${\ displaystyle d_ {i}}$${\ displaystyle O}$${\ displaystyle EI}$

Tehokkaan algoritmin saamiseksi ohjausmuuttuja lasketaan asteittain, ts. Lisätään askel askeleelta. Kuinka vaihdat sitä kahden peräkkäisen vaiheen välillä, riippuu siitä, onko pikseli vai valittu. Harkitse kussakin näistä tapauksista eroa seuraavan muuttujan ja seuraavan pikselin ohjausmuuttujan arvon välillä: ${\ displaystyle O}$${\ displaystyle EI}$

${\ displaystyle {\ begin {tasattu} \ textstyle \ Delta _ {O} & = \ textstyle d_ {i + 1} -d_ {i} = F (x_ {i} +2, \, y_ {i} + { \ frac {1} {2}}) - d_ {i} = \ Delta y \\\ textstyle \ Delta _ {NO} & = \ textstyle d_ {i + 1} -d_ {i} = F (x_ {i } +2, \, y_ {i} + {\ frac {3} {2}}) - d_ {i} = \ Delta y- \ Delta x \\\ end {tasattu}}}$

Jokaisessa vaiheessa ohjausmuuttujaa lisätään valitusta pikselistä tai riippuen siitä . Jos , on sitten suoran viivan yläpuolella, minkä vuoksi se on valittu, muuten . ${\ displaystyle \ Delta _ {O}}$${\ displaystyle \ Delta _ {NO}}$${\ displaystyle d_ {i} \ leq 0}$${\ displaystyle M}$${\ displaystyle O}$${\ displaystyle EI}$

Ohjausmuuttujan alkuarvo voidaan myös laskea tehokkaasti, jos viivan alkupiste on tarkalleen pikselillä: ${\ displaystyle d}$${\ displaystyle F (x_ {a}, \, y_ {a}) = 0}$

${\ displaystyle \ textstyle d_ {0} = F \ vasen (x_ {a} +1, \, y_ {a} + {\ frac {1} {2}} \ oikea) = \ \ alatuki {\ Delta y \ cdot x_ {a} - \ Delta x \ cdot y_ {a} + c} _ {= F (x_ {a}, \, y_ {a}) = 0} \, + \, \ Delta y - {\ frac {\ Delta x} {2}} = \ Delta y - {\ frac {\ Delta x} {2}}}$

Jaon eliminoimiseksi 2: lla kaikki kontrollimuuttujan arvot kaksinkertaistetaan; ratkaiseva merkki säilyy. Bresenham-algoritmi linjoille, joiden kaltevuus on 0 ja 1, voidaan siten ilmaista seuraavalla pseudokoodilla . Algoritmi tarvitsee vain lisäyksiä silmukassa; silmukan ulkopuolella olevat yksinkertaiset kertolaskut voidaan toteuttaa myös lisäämällä.

Muutos Bresenham-algoritmin ohjausmuuttujassa

d = 2×Δy – Δx
ΔO = 2×Δy
ΔNO = 2×(Δy − Δx)
y = ya
Pixel (xa, ya) einfärben
Für jedes x von xa+1 bis xeWenn d ≤ 0
        d = d + ΔO
    ansonsten
        d = d + ΔNO
        y = y + 1
    Pixel (x, y) einfärben

Algoritmin toinen tulkinta olettaa, että rasteroitu viiva sisältää vaaka- ja lävistäjäaskeleita. Näiden kahden vaihetyypin "sekoittamiseksi" kukin vaihe joko vähennetään ohjausmuuttujasta tai lisätään. Vastaava vaihetyyppi suoritetaan, jolloin tuloksena oleva kontrollimuuttujan määrä on pienempi. Tämä käy selvästi ilmi myös yllä olevasta kuvasta, jossa ohjausmuuttuja on aina mahdollisimman lähellä nolla-akselia. Thompson kuvasi tähän formulaatioon perustuvaa algoritmia vuonna 1964, mutta ei keskustellut oikean alkuarvon valitsemisesta kontrollimuuttujalle. Ennen Bresenhamia Fred Stockton julkaisi vuonna 1963 algoritmin viivojen rasteroimiseksi, joka käyttää myös vain kokonaislukulaskelmia, mutta on tarpeettoman monimutkainen.${\ displaystyle m = \ Delta x- \ Delta y}$${\ displaystyle n = \ Delta y}$${\ displaystyle m}$${\ displaystyle n}$

Rivit, joiden loppupisteet annetaan ei-kokonaislukukoordinaateilla, voidaan myös rasteroida Bresenham-algoritmilla. Tätä varten ohjausmuuttujan alkuarvo on laskettava sen alkuperäisen määritelmän mukaisesti; yleiset yksinkertaistukset eivät ole mahdollisia. Loput algoritmista pysyvät voimassa.

Pikselirivit

Vaikka Bresenham-algoritmi on melko tehokas, se piirtää vain yhden pikselin iteraatiota kohti ja tarvitsee siihen lisäyksen. Reggiori kehitti ensimmäisen kerran menetelmän, joka piirtää kaikki pikselit "riviin" - eli pikselit, joilla on sama y- koordinaatti - kerralla. Rivejä, joissa on vain yksi pikseli, käsiteltiin erikseen. Bresenham esitti myöhemmin yleisemmän algoritmin, joka onnistui ilman testejä tälle erityistapaukselle.

Bresenhamin pikselirivialgoritmilla sitä ei lisätä vähitellen, mutta . Nykyisen rivin loppu lasketaan kullekin . Tämä tehdään katsomalla pisteitä, joissa ihanteellinen viiva leikkaa keskipisteen läpi kulkevan vaakatason kahden pystysuoraan vierekkäisen pikselin välillä. Pikselirivin loppu on tämän leikkauspisteen x- koordinaatin pyöristetty arvo : ${\ displaystyle x}$${\ displaystyle y}$${\ displaystyle y}$

Pikselirivien päätepistekoordinaatit voidaan myös laskea asteittain. Koska jotkut pisteet voidaan laskea väärin tietyillä rinteillä, algoritmi käyttää symmetriaa kaltevuuden ½ suoralle.

Bresenhamin uuden algoritmin sisimmässä silmukassa ei tarvita lisäyksiä, koska kaikki rivin pikselit ovat värillisiä kerralla. Alustaminen edellyttää kuitenkin jakoa. Fung korvasi sen hakuprosessilla ja teki joitain lisäoptimointeja.

N- vaihe menetelmä

Neljä mahdollista pikselikuviota kaksivaiheisessa menetelmässä

Toinen tapa rasteroida, jonka Wu ja Rokne esittivät ensin, on ottaa useita pikseleitä x- akselia pitkin ja värittää kaikki välissä olevan viivan pikselit kerralla. Tätä varten valitaan useiden mahdollisten "pikselikuvioiden" välillä. Bresenhamin algoritmi voidaan nähdä tämän menetelmän erityistapauksena, jossa tehdään vain yhden pikselin vaiheet ja jossa valitaan vain kaksi “kuviota” (pikseliä oikealla tai ylhäällä oikealla).

Neljän mahdollisen kuvion erottamiseksi kaksivaiheisessa menetelmässä tutkitaan ensin kuvion viimeinen pikselisarake. Jos rasteroitava pikseli on ala- tai yläosassa, kuviot 1 tai 4 voidaan päätellä triviaalilla tavalla. Jos toisaalta pikseli on keskellä, keskimmäisen sarakkeen lisätesti on tarpeen, jotta voidaan valita kuvioiden 2 ja 3 välillä.

Näitä testejä yksinkertaistaa se, että kaltevuudella  ei voi esiintyä m  ½ kuviota 4 ja m ½ kuviota 1. Samoin kuin Bresenham-algoritmi, testien kontrollimuuttuja voidaan laskea myös asteittain kaksivaiheisella menetelmällä. Loppujen lopuksi algoritmi sujuu vain lisäämällä ja yksinkertainen kertolasku, joka voidaan toteuttaa nopealla bittisiirrolla .

Myös kolmen ja neljän vaiheen algoritmeja on kehitetty, jotka toimivat samalla periaatteella, mutta ovat huomattavasti monimutkaisempia ja pidempiä. Toinen nelivaiheinen algoritmi käyttää hiukan erilaista formulaatiota, joka tutkii järjestelmällisesti olosuhteita, joissa tietty malli esiintyy ja jotka voidaan yleistää mihin tahansa vaiheeseen.

Kaksisuuntainen seulonta

Yllä: Rivi rasteroitu vasemmalta oikealle Bresenham-algoritmilla; alla: kaksisuuntainen seulonta. Ontot ympyrät ilmaisevat pikselit, jotka värjäytyvät, kun toinen pikseli valitaan kohdassa d = 0.

Rasteroinnin nopeuden lisäämiseksi on järkevää piirtää viiva kaksisuuntaisesti, eli samaan aikaan alku- ja loppupisteestä keskipisteeseen. Tässä silmukka kulkee vain yli puolet linjasta; kussakin vaiheessa kaksi mukana olevaa pikseliä on värjätty viivan kummallekin puolelle. Sekä Bresenhamin algoritmia että muita menetelmiä voidaan muuttaa tällä tavalla.

On kuitenkin huomattava, että normaaleilla menetelmillä rasteroitu viiva ei ole välttämättä sinänsä symmetrinen . Tämä johtuu siitä, että rasteroinnissa on epäselviä tilanteita, joissa ihanteellinen viiva kulkee täsmälleen kahden pystysuorasti vierekkäisen pikselin keskustan läpi, joiden välillä voit vapaasti valita. Esimerkiksi edellä lueteltu Bresenham-algoritmi valitsee aina pikselin, jolla on pienempi y- koordinaatti , tällaisissa tapauksissa ( ) . Oikealta vasemmalle piirrettäessä toisaalta pikseli, jolla on suurempi y- koordinaatti, valitaan symmetrian käytön vuoksi . Jos viiva piirretään kaksisuuntaisesti tai oikealta vasemmalle, ulkonäkö voi siis muuttua verrattuna normaaliin algoritmiin, edellyttäen että epäselviä tapauksia ei testata erikseen. ${\ displaystyle d = 0}$

Muut tekniikat

jaksoittaisuus

Voidaan osoittaa, että arvot säätösuureen on Bresenham algoritmi toistaa kertaa, jossa a on suurin yhteinen tekijä on ja . Tämä tarkoittaa, että ohjausmuuttujan arvot on laskettava vain osalle viivaa ja voidaan sitten soveltaa muihin osiin. Tätä varten on kuitenkin laskettava GCD. Tämä menetelmä voidaan yhdistää myös kaksisuuntaiseen seulontaan. ${\ displaystyle \ Delta x}$${\ displaystyle \ Delta y}$

Ensimmäisen, toisen ja kolmannen pikselin rivit

Hierarkkiset pikselirivit

Rasteroidun viivan pikselirivien pituus noudattaa tiettyä mallia. Rosenfeld osoitti, että kaikkien pikselirivien pituus, paitsi ensimmäinen ja viimeinen, eroavat enintään yhdellä pikselillä. Hän havaitsi myös, että itse pikselirivisekvenssillä on tämä rakenne, samoin kuin näiden sekvenssien sekvenssillä jne. Rasteroidut linjat on jäsennelty hierarkkisesti n: n asteen riveistä , joista kukin voi ottaa vain tietyt pituudet. Stephenson kuvasi toimivia algoritmeja, jotka voivat piirtää viivan minkä tahansa korkean asteen riveistä, sekä rekursiivisen algoritmin, joka alkaa korkeimmasta mahdollisesta järjestyksestä. Tämä yleistää sekä Bresenham-algoritmin että pikselirivin algoritmin. "Zeroth-järjestyksen" rivien algoritmi, jossa pikselirivit jätetään huomiotta, vastaa tavallista Bresenham-algoritmia.

Rakenteelliset algoritmit

Rasterointia varten on ehdotettu muita algoritmeja, mutta ne eivät toimi vähitellen, mutta käyttävät suoraan rasteroitujen linjojen rakenteellisia ominaisuuksia. Ne perustuvat kuvankäsittelyn tai digitaalisen geometrian näkökohtiin, eivätkä käytännössä saavuta tavanomaisten menetelmien nopeutta, koska ne manipuloivat merkkijonoja tai vaativat muita hitaita toimintoja.

Esimerkiksi Bronsin algoritmi edustaa rasteroitua viivaa nollan ja ykkönen merkkijonolla, jossa 0 tarkoittaa vaakatasoa ja 1 diagonaalista askelta. Algoritmi olettaa merkkijonon, joka edustaa rivin ensimmäistä likiarvoa, yhdistää nollasekvenssit ja sekvenssit ja jakaa ne tasaisesti. Samaa prosessia sovelletaan tuloksena olevaan sekvenssiin. Tätä toistetaan, kunnes parannuksia ei voida saavuttaa. Tällä tavalla rasteroitu linja ei kuitenkaan ole optimaalinen; jotta saat saman linjan kuin Bresenham-algoritmilla, tarvitaan lisäasetuksia.

Ominaisuudet ja vertailu

Vaikka on löydetty lukuisia algoritmeja, jotka ovat vähemmän monimutkaisia kuin Bresenham-algoritmi, niiden käytännön nopeusetu on pieni. Tämä johtuu siitä, että ohjeet pikselien värittämiseen nykypäivän laitteistossa ovat hyvin hitaita verrattuna itse rasterointialgoritmin suorittamiseen. Kuitenkin jotkut näytönohjaimet tarjoavat hieman nopeammin toiminnot värjäämiseen useita pikseleitä kerralla, kuten rectwrite toiminnon SGI järjestelmiä. Tämä on etu pikselirivialgoritmeille, jotka voivat piirtää tällaisen rivin nopeasti kerralla.

Eri algoritmien suorittamisen nopeus riippuu rasteroitavan linjan pituudesta. Algoritmit, joiden sisäinen silmukka on nopea, mutta joiden alustus vaatii paljon aikaa, voivat saavuttaa nopeusetu vain pitkillä viivoilla. Siksi ehdotettiin, että kussakin tapauksessa valitaan tehokkain algoritmi linjan pituuden funktiona. Tilastollinen analyysi linjapituuksista eri sovelluksissa, kuten lankakehysmallien, käyräsegmenttien ja merkkien näyttämisessä, johti siihen, että lähes kolme neljäsosaa kaikista rasteroiduista viivoista oli alle kymmenen pikseliä pitkiä. Siksi kannattaa optimoida lyhyiden linjojen erityistapausta varten. Pitkien viivojen rasterointiin edullisemmat algoritmit soveltuvat paremmin lähtölaitteille, joiden resoluutio on suurempi kuin näytöillä ja siten keskimäärin pidemmillä viivoilla, kuten lasertulostimille. Joillakin algoritmeilla nopeus riippuu myös viivan kaltevuudesta - esimerkiksi pikselirivialgoritmit ovat vähemmän tehokkaita diagonaalilinjoilla, koska tähän voidaan piirtää vain yksi pikseli riviä kohden.

Toinen tekijä algoritmin valinnassa on ohjelman pituus. Grafiikkaprosessorien valmistajat, jotka toteuttavat rasteroinnin suoraan laitteistotasolla ja tarvitsevat siksi tilaa säästää, suosivat lyhyitä algoritmeja, kuten Bresenham-algoritmia. Ohjelmistototeutuksissa tämä tekijä on vähemmän kriittinen.

Ongelmia

Eri kirkkaudet kaltevuudesta riippuen

Kaikki yksiväriset seulontaalgoritmit voivat aiheuttaa ongelmia tietyissä tilanteissa:

Eri kirkkaus

Kun rasteroidaan samanpituisia, mutta eri kaltevuuksia viivoja, sama määrä pikseleitä ei välttämättä ole värillisiä. Vastakkaisessa esimerkissä lävistäjä on pidempi kuin vaakasuora, mutta molemmissa tapauksissa sama määrä pikseleitä on värillisiä. Tämän seurauksena nämä kaksi viivaa näyttävät eri valossa lähtölaitteessa. Tätä ongelmaa ei voida kiertää yksivärisillä laitteilla.

Viivatyylit

Symmetrian käyttäminen viivojen rasteroimiseksi millä tahansa aloitus- ja loppupisteellä voi aiheuttaa ei-toivottuja vaikutuksia, jos käytetään tiettyjä viivatyylejä. Jos katkoviivoja tai katkoviivoja on tarkoitus piirtää, vastaava kuvio alkaa viivan aloituspisteestä. Tällaiset viivat piirretään eri tavalla, jos alku- ja loppupisteet vaihdetaan. Jos viivatyylin viivat määrittelee tietty määrä väritettäviä pikseleitä, myös todellinen viivan pituus vaihtelee kaltevuuden mukaan.

Leikkaus

Tämä leikkaus on toiminto, joka rajoittaa seulonnan tietylle, yleensä suorakulmaiselle alueelle. Tämä tapahtuu siirtämällä rasteroitavan viivan alku- ja loppupisteet suorakulmaisen alueen reunoille, jos ne työntyvät esiin. Yleensä tämä tarkoittaa, että näiden pisteiden koordinaatit eivät ole enää kokonaislukuja. Jos nämä koordinaatit pyöristetään joka tapauksessa, tuloksena on viiva, jolla on erilainen kaltevuus ja siten mahdollisesti erilainen ulkonäkö. Tämän välttämiseksi lisätestit ovat tarpeen leikkaamisen jälkeen. Bresenham-algoritmi voidaan myös yhdistää leikkausalgoritmin kanssa.

Antialiasing

Suurin ongelma yksivärisissä rasteroiduissa viivoissa on niiden yleensä "portaiden kaltainen" ulkonäkö, joka tunnetaan myös nimellä portaikon vaikutus . Tätä vaikutusta voidaan torjua antialiaseilla grafiikkalaitteissa, jotka pystyvät näyttämään useita kirkkaustasoja . Rasteroitavaa viivaa ei yleensä katsota enää yksiulotteiseksi viivaksi, vaan kaksiulotteiseksi muodoksi, yksinkertaisimmassa tapauksessa suorakaiteeksi, jolla on haluttu paksuus. Rasterointia varten on määritettävä suorakulmion läheisyydessä olevien pikselien väriarvot.

Gupta- ja Sproull-menetelmä

Kuva kartiomaisesta tasoitusytimestä. Pikselin voimakkuus on verrannollinen tilavuuteen V.

Antialiasing-toiminnolla pikselin väri-arvo voidaan määrittää asettamalla ns. Tasoitusydin tai rekonstruointisuodatin pikselin päälle. Gupta ja Sproull ehdottivat kartiota , jonka säde oli yksi pikseli tasoitussydämeksi . Pikselin väri-arvo on verrannollinen sen kartion osan tilavuuteen, joka menee päällekkäin rasteroitavan linjan kanssa (tässä tapauksessa rasteroitavan suorakulmion kanssa). Tämä äänenvoimakkuus puolestaan ​​riippuu suorakulmion keskiviivan ja pikselin välisestä etäisyydestä . ${\ displaystyle D}$

Kolme mahdollista pikseliä, jotka on värjätty yhden pikselin viivan paksuudella

Gupta-Sproull-algoritmi perustuu Bresenham-algoritmiin, mutta se laskee myös jokaiselle pikselille, jonka tasoitusydin menee päällekkäin viivan kanssa. Kun viivan leveys on yksi pikseli, tämä on enintään kolme pikseliä per sarake. Tehokkuussyistä etäisyyksiä ei lasketa tarkasti, vaan otetaan huomioon vain 24 mahdollista etäisyyttä. Näitä etäisyyksiä vastaavat intensiteettiarvot laskettiin etukäteen ja tallennettiin taulukkoon ( hakutaulukko ), jotta ne voidaan kutsua nopeasti. ${\ displaystyle D}$

Viivan päät on käsiteltävä erikseen, koska mukana on enemmän kuin kolme pikseliä, yhteensä enintään kuusi pikseliä. Näiden pikselien intensiteetit riippuvat viivan kaltevuudesta. Ne lasketaan etukäteen joillekin kaltevuuksille ja tallennetaan myös tähän taulukkoon. Myös muut viivan päiden muodot ovat mahdollisia, esimerkiksi pyöristetyt päätepisteet; mukana olevien pikselien intensiteetit muuttuvat vastaavasti.

Gupta-Sproull-algoritmi soveltuu linjoille, joilla on mikä tahansa viivan paksuus, vaikka myös hakutaulukko muuttuu. Jos viivan leveys on suurempi kuin yksi pikseli, on huomattava, että yli kolmen pikselin tasoitusytimet voivat olla linjan päällekkäisiä.

Gupta-Sproull-algoritmin ongelmana on, että seulotut viivat näyttävät usein olevan eri vaaleita eri paikoissa. Tämä "köysimainen" ulkonäkö johtuu pääasiassa kartion riittämättömyydestä tasoitusytimeksi.

Menetelmä Wu

Intensiteettien laskeminen Wu-antiaseissa

Wu käytti erilaista lähestymistapaa antialiaseihin, joka ei perustunut tietyn tasoitusytimen käyttöön, vaan virhemittaukseen. Perusmuodossa menetelmää voidaan käyttää vain ihanteellisilla, äärettömän ohuilla viivoilla.

Bresenham-algoritmi yrittää arvioida ihanteellisen viivan minimoimalla "virheen" eli ihanteellisen viivan ja kahden mahdollisen pikselin välisen etäisyyden. Wu ehdotti toista virhemittausta, jota voidaan soveltaa mihin tahansa käyrään. Tämän virhemittauksen mukainen virhe voidaan eliminoida kokonaan, jos väriarvot sallitaan. Tätä varten kahden ihanteellisen viivan ylä- ja alapuolella olevan pikselin on otettava väriarvot, jotka ovat verrannollisia pystysuoraan etäisyyteen ihanteelliseen viivaan.

Wu antoi erityisen nopean algoritmin linjoille. Älykkäiden kokonaislukuoperaatioiden ansiosta hän tarvitsee vain yhden kontrollimuuttujan, jota muutetaan askel askeleelta ja joka määrittää sekä kahden sarakepikselin sijainnin että niiden voimakkuuden.

Muut tekniikat

Erilaisia ​​anti-aliasing -menetelmiä käyttäen esimerkkinä CAD- lankaverkkomallia. Vasemmalta oikealle: Ei antialiasia (Bresenham), Gupta-Sproull, painottamaton alueiden skannaus ja Wu.

Toinen antialiasian mahdollisuus on painottamaton pinta-alan näytteenotto . Pikselin väriarvo vastaa viivan pinta-alaa neliössä, jonka reunan pituus on yksi pikseli kyseisen pikselin ympärillä, joten tasoitussydän on tässä tapauksessa kuutio. Tätä menetelmää varten on kehitetty nopeita algoritmeja. Painottamattoman alueen skannauksen haittana on viivojen epäselvä ulkonäkö.

Kuten yksivärisessä seulonnassa, pikselirivien rakennetta voidaan käyttää seulonnan nopeuden lisäämiseksi.

Erityisesti linjoille optimoitujen anti-aliasing-prosessien lisäksi voidaan käyttää myös yleisiä prosesseja, kuten Whittedin menetelmää, jossa korkean resoluution rasterigrafiikkaa siirretään "harjana" linjaa pitkin.

Erityiset optimoinnit

Linjojen rasterointi voidaan tehostaa entisestään lähentämismenetelmien, laitteiston käytön tai suoran toteutuksen avulla ja rinnakkaistamisella . Tämä on tarpeen, kun erittäin suuri määrä radoja on rasteroitava reaaliajassa .

Lähentämismenetelmä

Boyer ja Bourdin esittivät approksimointimenetelmän, joka värittää pikselit aina ihanteellisen viivan alapuolelle. Tällaisella rasteroidulla linjalla on joitain erityisominaisuuksia, joita voidaan hyödyntää. Esimerkiksi tässä tapauksessa paitsi Bresenham-kontrollimuuttuja, myös linjasegmentit ovat jaksollisia. Yhdessä muiden optimointien kanssa tämä johtaa algoritmiin, joka on huomattavasti nopeampi kuin tarkka menetelmä, erityisesti pidemmillä viivoilla. Laadun heikkeneminen on havaittavissa linjoilla, joilla on hyvin pieni kaltevuus.

Rinnakkaisuus

Yksinkertainen menetelmä yksivärisen rasteroinnin rinnakkaistamiseksi sallii eri algoritmien suorittamisen rinnakkain, jotka - kukin siirtyivät hieman - piirtävät useita pikseleitä tietyin välein. Toinen mahdollisuus on jakaa linja useisiin suunnilleen yhtä suuriin osiin, joista kukin on osoitettu prosessorille rasterointia varten. Jokainen osa renderöidään Bresenham-algoritmilla; Pääongelma on muuttujien oikeiden alkuarvojen laskeminen. On myös mahdollista, että useat prosessorit laskevat rivien päätepistekoordinaatit Bresenhamin pikselirivialgoritmilla. Algoritmeja esitettiin myös vektoritietokoneille, jotka toimivat massiivisesti yli 1000 prosessorin kanssa. Jokainen rasterigrafiikan pikseli on osoitettu prosessorille, joka päättää, pitäisikö tämän pikselin olla värillinen vai ei.

Hitaiden muistihakemusten nopeuttamiseksi rasteroinnin aikana on kehitetty erityisiä muistiarkkitehtuureja, esimerkiksi sellaisia, joissa muisti on jaettu soluihin, joihin osa linjasta voidaan piirtää toisistaan ​​riippumatta. Antialiasing-seulontaa voidaan tukea myös laitteistolla.

Liittyvät ongelmat

4-linkitetty ruudukko. 8-liitetyn ruudukon lisäksi valitut neliöt näytetään viistosti.

Linjat eivät voi olla vain 8-kytkettyjä, kuten normaalisti, mutta myös 4-kytkettyjä (4-kytkettyjä) . Tämä tarkoittaa, että ei diagonaalisia askelia, vaan vain vaaka- ja pystysuorat askeleet ovat sallittuja. Jos ajattelet pisteiden ruudukon jaettuna ruutuihin, valitaan kaikki rivillä päällekkäiset neliöt. Tämän tekniikan yleistämistä kolmelle ulottuvuudelle käytetään vokseliritilässä , joka on säteiden jäljityksen kiihdytystekniikka . Sitä käytetään määrittämään vokselit, joiden läpi säde kulkee säteen jäljityksen aikana.

Rasteroitujen viivojen kohdalla diagonaaliset pikselivaiheet jakautuvat mahdollisimman tasaisesti. Siksi viivojen rasterointia koskevia algoritmeja voidaan käyttää myös jakamaan kokonaislukukoordinaateilla varustetut pisteet tasaisesti tietyllä aikavälillä . Mahdollisia sovelluksia ovat lineaarinen interpolointi tai alinäytteenotto signaalinkäsittelyssä. Euclidealaiseen algoritmiin , Farey-sarjaan ja joihinkin muihin matemaattisiin rakenteisiin liittyy muita rinnakkaisuuksia .

kirjallisuus

• James D. Foley, muun muassa: Tietokonegrafiikka: periaatteet ja käytäntö C: ssä . Addison-Wesley, Reading (Massachusetts) 1995, ISBN 978-0-201-84840-3 . (Kattaa Bresenhamin algoritmin, rasterointiongelmat ja Gupta-Sproullin antialiasingin) 

Yksittäiset artikkelit:

Tämä luettelo on valinta; yksityiskohtainen bibliografia sisältyy Stephensonin väitöskirjaan.

1. ↑ Katso esimerkkikoodi osoitteesta http://www.crbond.com/papers/newline.pdf (250 kt)
2. ^ Algoritmi digitaalisen piirturin tietokoneohjaukseen. IBM Systems Journal 4, 1 (1965): 25-30, ISSN  0018-8670 ( PDF, 220 kt ). Esitettiin jo elokuussa 1963 luentona ACM: n kansallisessa konferenssissa Denverissä.
3. ↑ Mike LV Pitteway: Ellipsien tai hyperbolien piirtämisen algoritmi digitaalisella piirturilla. The Computer Journal 10, 3 (marraskuu 1967): 282-289, ISSN  0010-4620
4. ^ JR Thompson: Kirjeenvaihto: Suorat viivat ja kuvaajat. The Computer Journal 7, 3 (elokuu 1964): 227
5. ↑ Fred G. Stockton: Algoritmi 162: XYmove-piirtäminen. Viestintä ACM 6: sta 4 (huhtikuu 1963): 161, ISSN  0001-0782
6. ↑ Giovanni B.Reggiori: digitaalisen tietokoneen muunnokset epäsäännöllisille viivapiirroksille. Tekninen raportti 403-22, New York University, New York, huhtikuu 1972
7. ^ Jack E. Bresenham et ai .: Suorituspituuden viipaleet inkrementaaliviivoille. IBM Technical Disclosure Bulletin 22-8B (1980): 3744-3747, ISSN  0018-8689
8. ↑ ^{a b} Khun Yee Fung: Run-length Slice Line Drawing Algorithm ilman jako-operaatioita. Computer Graphics Forum 11, 3 (1992): 267-277 , ISSN  0167-7055
9. Olin Xiaolin Wu, Jon G. Rokne: Kaksivaiheinen viivojen ja ympyröiden inkrementaalinen generointi. Tietokonenäkö, grafiikka ja kuvankäsittely 37,3 (maaliskuu 1987): 331-344, ISSN  0734-189X
10. ↑ Phil Graham, S. Sitharama Iyengar: Kahden- ja kolmivaiheinen inkrementaalinen linjojen sukupolvi. Julkaisussa ACM CSC '93 Proceedings: 384-389. ACM Press, Indianapolis 1993, ISBN 0-89791-558-5
11. ^ Paul Bao, Jon G. Rokne: Neliportainen linjasukupolvi . Computers & Graphics 13, 4 (1989): 461 - 469, ISSN  0097 - 8493
12. ^ Graeme W. Gill: N-vaiheen inkrementaaliset suoraviivat. IEEE-tietokonegrafiikka ja sovellukset 14, 3 (toukokuu 1994): 66-72, ISSN  0272-1716
13. B ^{a b} Giulio Casciola: Peruskäsitteet linja-algoritmien nopeuttamiseksi. Computers & Graphics 12, 3/4 (1988): 489-502
14. ^ Azriel Rosenfeld: Digitaaliset suorat segmentit. IEEE-tapahtumat tietokoneilla C-23, 12 (joulukuu 1974): 1264-1269, ISSN  0018-9340
15. ^ ^{A b} Peter Stephenson: Digitoidun linjan rakenne: Viivapiirrossa ja säteiden jäljityksessä tietokoneella. PhD Thesis, James Cook University of North Queensland, Australia, 1998 ( Online ( Memento 5. syyskuuta 2007 Internet-arkistossa ))
16. ^ Reyer Brons: Kielelliset menetelmät suoran viivan kuvaamiseksi ruudukossa. Tietokonegrafiikka ja kuvankäsittely 3 (1974): 48-62, ISSN  0146-664X
17. ^ Jim X. Chen: Linjajakauman analyysi ja tilastot. IEEE-tietokonegrafiikka ja -sovellukset 22, 6 (marraskuu / joulukuu 2002): 100-107
18. ^ Yevgeny P.Kuzmin: Bresenhamin linjanluontialgoritmi sisäänrakennetulla leikkauksella. Computer Graphics Forum 14, 5 (1995): 275 - 280
19. ↑ Satish Gupta, Robert F.Sproull: Reunojen suodattaminen harmaasävyisissä näytöissä. Vuonna ACM SIGGRAPH '81 Proceedings: 1-5. ACM Press, Dallas 1981, ISBN 0-89791-045-1
20. ^ AR Forrest: Antialiasing käytännössä. Julkaisussa RA Earnshaw (toim.): Tietokonegrafiikan perusalgoritmit (= NATO ASI -sarja F.17): 113-134. Springer, Berliini 1985, ISBN 3-540-13920-6
21. ↑ Xiaolin Wu: Tehokas antialiasing-tekniikka. Julkaisussa ACM SIGGRAPH '91 Proceedings: 143-152. ACM Press, New York 1991, ISBN 0-89791-436-8
22. ↑ Katso esimerkiksi Vincent Boyer, Jean-Jacques Bourdin: Diskreetti analyysi antialiased-viivoille. Lyhyt esitys, Eurographics 2000 ( PDF, 230 kB )
23. ↑ Nicholas A.Diakopoulos, Peter D.Stephenson: Anti-Aliased Lines Using Run-Masks. Computer Graphics Forum 24, 2 (kesäkuu 2005): 165-172
24. ^ Turner Whitted: Anti-alias viivapiirros harjalla puristamalla. Julkaisussa ACM SIGGRAPH '83 Proceedings: 151-156. ACM Press, Detroit 1983, ISBN 0-89791-109-1
25. ↑ Vincent Boyer, Jean-Jacques Bourdin: Fast Lines: Span by Span Method. Computer Graphics Forum 18, 3 (1999): 377–384 ( PDF, 400 kt )
26. ^ Robert F. Sproull: Ohjelmamuunnosten käyttäminen linjapiirtoalgoritmien johtamiseen . ACM Transactions on Graphics 1,4 (lokakuu 1982): 259-273, ISSN  0730-0301
27. ^ William E. Wright: Bresenhamin viiva- ja ympyräalgoritmien rinnakkaisuus. IEEE-tietokonegrafiikka ja sovellukset 10, 5 (syyskuu 1990): 60-67
28. ↑ Ivo Považan, Tomáš Hrúz: Rinnakkaisviiva: yhtenäinen ratkaisu. Vuonna WSCG '97 Proceedings: 60-67. Länsi-Böömin yliopisto, Pilsen 1997, ISBN 80-7082306-2 ( online )
29. ↑ Alex T. Pang: Viivapiirustusalgoritmit rinnakkaisille koneille. IEEE-tietokonegrafiikka ja sovellukset 10, 5 (syyskuu 1990): 54-59
30. ↑ Katso esimerkiksi Pere Marès Martí, Antonio B.Martínez Velasco: Muistiarkkitehtuuri rinnakkaisviivapiirustukseen, joka perustuu ei-inkrementaaliseen algoritmiin. Julkaisussa: Euromicro 2000 Proceedings: Vuosikerta 1, 266-273. IEEE Computer Society Press, Los Alamitos 2000, ISBN 0-7695-0780-8
31. ↑ Katso esimerkiksi Robert McNamara et ai: Esisuodatetut antialiased-viivat puolitasotasoisten toimintojen avulla. Julkaisussa HWWS 2000 Proceedings: 77-85. ACM Press, New York 2000, ISBN 1-58113-257-3
32. ↑ Chengfu Yao, Jon G. Rokne: Integraalinen lineaarinen interpolaatiotapa inkrementaalisten linja-algoritmien suunnitteluun. Journal of Computational and Applied Mathematics 102, 1 (helmikuu 1999): 3-19, ISSN  0377-0427
33. ^ Mitchell A.Harris, Edward M.Reingold: Viivapiirros, karkausvuodet ja Euclid. ACM Computing Surveys 36, 1 (maaliskuu 2004): 68–80, ISSN  0360-0300 ( PDF, 270 kt ( Memento 16. joulukuuta 2006 Internet-arkistossa ))

nettilinkit

• Bresenhamin algoritmi (NIST Dictionary of Algorithms and Data Structures) - Bresenham-algoritmin tausta, alkuperäisellä lähdekoodilla
• Viivojen, ympyröiden, ellipsien rasterointi (Magdeburgin yliopisto, Simulaatio- ja grafiikkainstituutti) - Java-sovelma Bresenham-algoritmin ymmärtämiseen
• Projekti: Linjatilastot (George Mason University Computer Graphics Lab) - Linjapituuksien ja kaltevuuksien jakauman tutkimus
• Bresenhamin algoritmin kauneus - yksinkertainen toteutus viivojen, ympyröiden, ellipsien ja Bézier-käyrien piirtämiseen

Tämä artikkeli lisättiin loistavien artikkelien luetteloon 4. toukokuuta 2007 tässä versiossa .