Visszatekintés:

A már (elég régen) ismertetett algoritmus szerint a poligon széleit ki kell gyűjteni egy tömbbe. Ez a tömb fogja tartalmazni minden Y-ra a kezdeti és végpontot a képernyőn, és a textúrán. Majd a tömbből kiszedve az értékeket minden scanline-ra kiszámoljuk a lépésközt a textúrán, és kirajzoljuk a scanline-t. Ennek a módszernek az előnye, hogy akárhány oldalú is a poligon, a módszer ugyanúgy használható. Hátránya viszont, hogy körülményes. A tömbtöltögetésen kívül minden scanline-ra újraszámoljuk a lépésközöket, pedig az esetek nagy részében ez szükségtelen. (Ahogy a továbbiakban látni fogjuk)

Erre a tömbös dologra egy egyszerű példa:

A példa annyira egyszerűre sikerült, hogy ez csak egy fill rutinhoz lenne elég, mivel csak a scanline két végét tároljuk. Ennek analógiájára a textúrakoordinátákat is el tudja mindenki képzelni. 

Eddig volt a visszatekintés.

Nézzük miért nem jó ez nekünk. A 3d-s objektumok annál szebbek, finomabbak, minél kisebb poligonokból épülnek fel. Egy sokszög pedig akkor a lehető legkisebb, és legegyszerűbb, ha pont 3 szöge van. Ezért van az, hogy a 3d-s szerkesztésre való programok előszeretettel használnak háromszögeket. Pl. a 3D Studio nem is használ más sokszöget.

Arról nem is beszélve, hogy a háromszögeket igen egyszerű kirajzolni.

Lássuk, hogy néz ki egy háromszög, miután megjelent a képzeletünkben, rögtön mondjunk ki két tételt, amit használni fogunk.

  1. Háromszögnek nevezzük azt a sokszöget, melynek két oldalával szemközt mindig egy harmadik található. L 
  2. Három pontot akárhogy összekötve is csak háromszöget kapunk. L

Első hallásra igen bagatellnek tűnnek, mégis ez a felismerés a titka annak, hogy ki tudjuk rajzolni a képernyőre. Mivel mindig scanline(X irányú vonalak) -okkal operálunk, tudnunk kell, hogy hol van a scanline eleje, meg a vége. Az első igen velős megfigyelésből adódik, hogy két eset lehetséges. 

Az első esetben a baloldalon van két oldal, a második esetben a jobb oldalon. 

Tehát az első esetben tudjuk, hogy a scanline-ok elejét először a P1-P2 egyenesen találjuk, majd mikor ez véget ért, akkor a P2-P3-on. A scnline-ok végei minden esetben a P1-P3 egyenesen vannak.

A második esetben pedig pont fordítva. A kezdőpontok mindig a P1-P3-on vannak, míg a végpontok a P1-P2-n, és a P2-P3-on.

Mivel vonalegyenletet tudunk számolni, innen már egy kitöltött háromszög kirajzolható.

Tehát a probléma kulcsa az, hogy az illető háromszög balos-e, vagy jobbos. Ennek eldöntésére lesz segítségünk az ábrán látható kék vonal. Ami az a scanline, ami a töréspontnál helyezkedik el. Egészen szándékosan van itt, hiszen ez a leghosszabb scanline is.

Tehát kiszámoljuk ennek a scanline-nak a hosszát.
Tegyük fel, hogy a háromszög balos. 
Szükségünk lesz egy arányra:

T=(p2.y-p1.y)/(p3.y-p1.y)

Tehát a scanline vége (nevezzük e-nek) a (p3.x-p1.x) T-ed részénél lesz.

E=t*(p3.x-p1.x)

Feltételeztük, hogy balos, ezért p1.x>p2.x
E-hez p1.x-et hozzáadva és p2.x-et levonva megkapjuk a hosszt.

Width=p1.x+ t*(p3.x-p1.x)-p2.x

Ha az eredmény pozitív, a háromszög balos, ha negatív, akkor jobbos.

Tehát már nincs akadálya egy fillezett háromszög kirajzolásának. Csak arra kell vigyázni, hogy ne felejtsük el újraszámolni a vonalegyenletet azon az oldalon, ahol kell.

Most jön a texture mapping. 

Itt is a kék vonal jelzi a leghosszabb scanline-t, az U-k és V-k textúrakoordináták.

Vegyük észre, hogy a lépésköz a textúrán az egész háromszögön belül állandó! Ez nagyon fontos, mert így nem kell minden scanline-ra újból kiszámolni. Ezzel pedig gyorsul a dolog. 

A lépésköz az előbb meghatározott hosszúság segítségével pedig könnyen megadható. Itt is ugyanazt kell csinálni. A scanline által takart rész hosszát kell kiszámolni a textúrán. Ennek megfelelően ugyanaz a képlet, csak az y-okat U-ra, az x-eket V-re cseréljük, majd osztjuk a scanline hosszával, hogy megkapjuk a lépésközt.

UStep=(U1+T*(U3-U1)-U2)/width
VStep=(V1+T*(V3-V1)-V2)/width

Ez az egy lépésköz használható végig. 

Mivel a lépésköz adott, minden scanline-ra csak a kezdőpontot kell tudni a textúrán.
Az ábrákon nem véletlenül az egyes pont volt legfelül, a kettes középen, a hármas meg legalul. Hiszen a képletek csak így működnek. Mindegyikben feltételeztük ezt az ideális esetet. Ez a valóságban egyáltalán nem garantált. De gondoljunk bele. Három pontból akármilyen sorrendben is vannak megadva, akármelyiket kötjük össze akármelyikel mindig csak ugyanazt a háromszöget fogjuk megkapni. Szóval most felhasználjuk a második örök tanulságot, amit a háromszögekről megtudtunk.

Ha a pontok nincsenek Y szerint sorrendbe téve, hát tegyük őket sorrendbe, abból is ugyanaz a háromszög lesz. Három pont sorbarendezése pedig három összehasonlítással kényelmesen megoldható.

Akkor most rakjuk egybe a dolgokat.

Valami ilyesmi lenne amolyan Pascalos C-s assembly-s keverék pszeudókódban

Texturetriangle proc  p1,p2,p3 : pontra mutato pointerek:
Var T : arányossági tényező Width : leghosszab scanline hossza Ustep : U lépésköz Vstep : V lépésköz UL,VL,XL : bal oldali értékek XR :  jobb oldali érték Y,yend : a kirajzolo loop-nak kell,hogy mettől meddig
menjen
{sorbarendezés} If  p1.y>p2.y then csere(p1,p2) If  p1.y>p3.y then csere(p1,p3) If  p2.y>p3.y then csere(p2,p3) {kostans lépésköz} T=(p2.y-p1.y)/(p3.y-p1.y) Width=p1.x+ T*(p3.x-p1.x)-p2.x UStep=(p1.U+T*(p3.U-p1.U)-p2.U)/width VStep=(p1.V+T*(p3.V-p1.V)-p2.V)/width {kezdőértékek beállítása} XL=p1.x XR=p1.x VL=p1.u UL=p1.V Y=p1.y Yend=p2.y If width<0 then goto jobbos Balos: {a háromszög balos, tehát a jobb oldalon végig ugyanaz az x lépésköz a képernyőn 1. és 3. Pont között} XRStep=(p3.x-p1.x)/(p3.y-p1.y) {A bal oldalon először az 1. ponttól megyünk a 2. Felé} XLStep=(p2.x-p1.x)/(p2.y-p1.y) ULStep=(p2.u-p1.u)/(p2.y-p1.y) VLStep=(p2.v-p1.v)/(p2.y-p1.y) {Az ertekek megvannak, mar csak ki kell rajzolni} Call loop {a háromszög egyik fele megvan, most vagyunk a töréspontnál} {a bal oldalon új vonalon kell tovább menni. 2. Ponttól a 3. ig} XL=p2.x UL=p2.U VL=p2.V ULStep=(p3.u-p2.u)/(p3.y-p2.y) VLStep=(p3.v-p2.v)/(p3.v-p2.v) XLStep=(p3.x-p2.x)/(p3.x-p2.x) Yend=p3.y Call loop Goto ki {a  jobbos rész} Jobbos: {a bal oldalon vegig jók lesznek ezek a lépésközök 1. És 3. Pont között} XLStep=(p3.x-p1.x)/(p3.y-p1.y) ULStep=(p3.u-p1.u)/(p3.y-p1.y) VLStep=(p3.v-p1.v)/(p3.y-p1.y) {a jobb oldalon egy p2.y-ig jó :} XRStep=(p2.x-p1.x)/(p2.y-p1.y) Call loop {csak a jobb oldali értékeket kell újraszámolni, azokból meg csak egy van} XRStep=(p3.x-p2.x)/(p3.y-p2.y) Yend=p3.y Call loop Goto ki
 
{A tényleges kirajzolás és lépkedés} Loop: U=UL V=VL egy scanline kirajzolása} For c=XL to XR do Begin Putpixel(Y,c,texture[U,V]) {a textura u,v pontját
kirakjuk}
U+=Ustep {lépésközök hozzáadása} V+=VStep end {a háromszög szélén külön lépésközök} UL+=ULStep VL+=VLStep XL+=XLStep XR+=XRStep Y++ If  Y<=Yend then goto loop RetKi: Return
Texturetriangle endproc

Na a valóságban azért nem ilyen egyszerű a helyzet. Azt is figyelni kell, hogy a két felső pont nincs-e egy magasságban, mert ekkor a háromszög egy nekifutásból is kirajzolható, ugyanúgy, mintha az alsó kettő lenne egyenlő. Azt is figyelni kell, nem írunk-e a képernyőn kívülre.

A progi Pascal-ban és assembly-ben sikerült.