Kolmion rasterointi

Kuvan mukaisen kolmion täyttäminen yhdellä värillä ei ole niin helppoa miltä se kuulostaa. Toki Flash tarjoaa tähän valmiin funktion, mutta se funktio ei kelpaa meille enää siinä vaiheessa kun haluamme täyttää polygonin tekstuurilla perspektiivikorjattuna. Tästä syystä meidän on kirjoitettava oma poly filleri, jota voimme kehittää eteenpäin.
Tähän on monia tapoja, mutta tässä esittelen tavallisemman tavan, jossa polygoni täytetään vetämällä polygonin reunasta reunaan vaakaviivoja (scanline). En oikeastaan tiedä millä nimellä tätä algoritmia kutsutaan, mutta sanon sitä nyt vaikka scanline rasteriksi.
Eli kolmio on muoto jossa on kolme sivua (edge) ja kolme kärkipistettä (vertex).



Homma toimii siten, että interpoloimme A->B välin jolloin saamme AB reunan ja interpoloimme A->C välin jolloin saamme AC reunan ja interpoloimme B->C ja saadaan BC reuna. Sitten vedellään vaakaviivoja AB ja AC reunojen välille ja saadaan täytetty yläosa.



Sama BC ja AC välille ja saadaan myös fillattu alaosa. Näin koko kolmio on täytetty.



Tämän toiminnallisuuden kirjoittaminen koodilla ei ole aivan triviaalia, mutta se ennemminkin hiukan työlästä ja ikävää kuin vaikeaa.
Kolmio siis rasteroidaan kahdessa osassa. Tämä siksi että haluamme kolmion yhden sivun olevan suora, joka helpottaa vaakaviivojen piirtoa ja ennen kaikkea nopeuttaa niiden piirtoa. Vaakaviivahan on hyvin helppo piirtää. Meidän pitää vain kasvattaa X arvoa yhdellä kunnes ollaan loppupisteessä. Tämä on siis yksinkertainen plus lasku.
Eli aloitetaan kolmion halkaisusta. Tässä ei oikeastaan ole mitään hankalaa. Meidän pitää vain varmistaa, että verteksit ovat y suunnassa laskevassa järjestyksessä eli A on ylin piste ja C alin piste. Itse halkaisu käy ikään kuin itsestään.

var t:Point = null;
if (A.y > B.y)
{
 t = A;
 A = B;
 B = t;
}

if (B.y > C.y)
{
 t = B;
 B = C;
 C = t;
}

if (A.y > C.y)
{
 t = A;
 A = C;
 C = t;
}   

Kun tiedämme, että pisteet ovat oikeassa järjestyksessä voimme laskea polyn yläosan.

if (t.A.y != t.B.y)
{
 var aex:Number = t.A.x;
 var aed:Point = new Point(t.B.x - t.A.x, t.B.y - t.A.y);
 var aes:Number = aed.x / aed.y;
 
 for (var i:int = t.A.y; i < t.B.y; i++)
 {
  aex += aes;
  cex += ces;
  
  var x1:int = aex;
  var x2:int = cex;
  drawScanline(new Point(x1, i), new Point(x2, i), _bmp);
 }
}

Loogisesti jatkamme tästä piirtämällä myös alaosan.

if (t.B.y != t.C.y)
{
 var bex:Number = t.B.x;
 var bed:Point = new Point(t.C.x - t.B.x, t.C.y - t.B.y);
 var bes:Number = bed.x / bed.y;
 
 for (i = t.B.y; i < t.C.y; i++)
 {
  bex += bes;
  cex += ces;
  
  x1 = bex;
  x2 = cex;
  drawScanline(new Point(x1, i), new Point(x2, i), _bmp);
 }
}

Ja tässä koko koodi, joka näyttää kaikki tarpeelliset yksityiskohdat.

Lataa lähdekoodi