-•- Texture mapping -•-

           Hráli  jste   někdy  Wolfenstein  3D   nebo  jeho  méně   známé
     pokračování  Spear  of  Destiny  ?  To  je  ale  blbá  otázka,  vždyť
     Wolfensteina pařil každý až do  skonání fyzických sil. Jeho tvůrci ID
     software sklidili  tenkrát veliký úspěch a  obdiv. Starej dobrej Wolf
     se totiž docela obstojně hejbal i na  obyčejný 286ce a to se fakt jen
     tak nevidí. Asi si kladete  otázku, jak je  to možné. Celý  3D engine
     Wolfensteina  stojí na  tzv. DDA  wolf-mappingu. Pro  začátek se  vám
     pokusím vysvětlit jeho princip.
           Aby  lidský  mozek  dostal  pocit,  že  se  pohybuje  v nějakém
     virtuálním  prostoru,  je  třeba   jeho  oči  omámit  velikým  počtem
     různobarevných  bodů.  Na  počítači  dosáhneme  realistického  pohybu
     texturovaných ploch  při rychlosti alespoň 25  obrázků za sekundu. Na
     pomalých  počítačích se  takovéto rychlosti  i u  čistých vektorových
     objektů  dosahuje velmi  špatně, a  to ani  nemluvím o texturách. Ale
     Wolf se  skutečně přibližoval k  20 obrázkům za  sekundu i na  286ce.
     Celé   tajemství   této   ďábelské    rychlosti   se   dá   odůvodnit
     minimalizováním zobrazovaných textur za jeden frámeček. Ve Wolfovi se
     vykreslují  pouze  zdi,  podlaha  a  strop  jsou  vyplněny konstantní
     barvou. Wolf-mapping není náročný, jak  na výpočet, tak na pochopení,
     a proto si  ho můžete zkusit naprogramovat  sami. Základní rutinou je
     DDA algoritmus, který se mimo jiné používá například na kreslení čar.
     Princip je jednoduchý:

                                 /[x2,y2]
                                /
                               /
                              /
                             /
                            /
                     [x1,y1]


        tato úsečka se dá vyjádřit matematicky tímto způsobem:

                             y = kx + b

                           y2-y1              x2y1-x1y2
             kde k je k = ------- a b je b = ------------
                           x2-x1                x2-x1


     V praxi si předpočítáme k a b. Následuje cyklus podobný tomuto:

         for x:=x1 to x2 do
           begin
            y:=round(k*x+b);
            putpixel(x,y);
           end;

     na obrazovce by se měla objevit čára z bodu [x1;y1] do bodu [x2;y2]

     Nyní si představte texturu:

            [x1;y1]
             |-----------|
             | . . . . . |
             | . . . . . |
             | . . . . . |
             | . . . . . |
             | . . . . . |
             |-----------|
                       [x2;y2]

     a potřebujete ji rotovat například podle osy z, použijete tedy stejný
     způsob,  jaký  jsem  načrtl  v  mém  minulém  příspěvku  ve Výhni #1.
     Výpočtem  získáte  souřadnice  čtyř  bodů  a  co  teď  ? Jednoduše si
     představte horní a dolní okraj textury jako čáry a podle výše uvedené
     rutiny vytvořte tento magický cyklus:

          [x1;y1]
            ---
            |. ---
            |.. . ---
            |.. . .  ---  [x2;y2]
            |.. . . . ..|
            |.. . . . ..|
            |.. . . . ..|
            |.. . .  ---  [x2;y4]
            |.. . ---
            |. ---
            ---
          [x1;y3]

          k1:=(y2-y1)/(x2-x1)
          b1:=(x2y2-x1y2)/(x2-x1)
          k2:=(y4-y3)/(x2-x1)
          b2:=(x2y3-x1y4)/(x2-x1)

          repeat
            y1:=round(k1*x1+b1);
            y3:=round(k2*x1+b2);
            inc(x1);
            textureline(x1,y1,y3);
          until x1=x2

     Kdyby jste  měli procedůrku textureline,  tak by to  všechno fachalo,
     tak jak má,  ale vy ji asi nemáte,  a tak mi nezbývá nic  jiného, než
     vám její princip také osvětlit. Pro názornost další ansi obrázek:

       1.    =-=-=-=-=-=-=-=-=-=-=-=-=
       2.          ============

     takhle  bude  asi  vypadat  první  a  poslední sloupec pixelů textury
     otočený o 90  stupňů. My ho potřebujeme smrštit  z původní délky tak,
     aby se nám  vešel mezi souřadnice y1 a y3.  Jak už jistě tušíte, zase
     přichází na řadu algoritmus pro kreslení čáry:

               y3-y1
         k = ---------  kde h je  výška textury
                 h

     pro tentokrát to bude trochu složitější, ale magie to není:

       k:=h/(y3-y1);
       for y:=y1 to y3 do
        begin
         testY:=k*y;
         if frac(testY)=0 then
          putpixel(x1,testY,texture[xc,y-y1])
        end;

     huu ...:-)  hned podám vysvětlení ...  na začátku spočtu k  a začínám
     cyklus od pozice y1, do proměnné  testY  uložím  současný  stav  k*y,
     a pokud se jedná o celé číslo, vykreslím na souřadnice [x1;testY] bod
     z textury (xc - sloupec textury  - závisí na předchozím cyklu). Pokud
     by  nastala  situace,  kdy  (x2-x1)  je  větší  nebo  menší než délka
     textury, stačí pouze přepsat  cyklus textureline pro x-ové souřadnice
     a místo výstupu  bodu na obrazovku, přiřadit  do proměnné xc aktuální
     sloupec  textury. Takhle to celé vypadá přibližně v praxi:

           Procedure TextureLine(X,Y1,Y2:Integer;
                                 Texture:Pointer;
                                 THeight:Word);

           { --- viz výše --- }

           Procedure DrawTexture(X1,Y1,Y2,X2,Y3,Y4,TX,TY:Word);
            var X,deltaX,deltaHiY,deltaLoY : Integer;
                koefLoY,koefHiY,koefX      : Real;
           begin
            deltaX:=X2-X1-1;
            if deltaX=0 then deltaX:=1;
            deltaHiY:=Y1-Y3;
            deltaLoY:=Y4-Y2;
            koefLoY:=deltaLoY/deltaX;
            koefHiY:=deltaHiY/deltaX;
            koefX:=TY/deltaX;
            X:=0;
            repeat
             TextureLine(X+X1,Y1-Round(koefHiY*X),Y2+Round(koefLoY*X),
                         Texture+(TX*Round(X*koefX)),TX);
             if deltaX>0 then Inc(X) else Dec(X);
            until X=deltaX;
           end;


           Výsledek můžete  shlédnout stejně jako  v minulém čísle  Výhně,
     pokud spustíte intro3.exe. Zcela analogicky  se dá vytvořit i textura
     podlahy. Tak teď je to snad každému jasné. Ohledně Wolfenstenia 3D se
     dá  ještě podotknout  to, že  kromě  principu   nemá  jeho algoritmus
     s uvedenými  příklady   nic  společného.  Je   kompletně  přepsán  do
     assembleru  a  využívá  mnoha  předpočítaných  tabulek  pro  dosažení
     maximální  rychlosti. Doufám,  že se  pokusíte něco  udělat. Pokud by
     jste  měli  ňáké  problémy  nebo  vás  zajímá  obecný texture-mapping
     polygonů (v  podstatě jde o  propojení horizontálního a  vertikálního
     algoritmu), můžete  se obrátit na  mě, já se  pokusím případné dotazy
     zodpovědět.

                                                     ReDox

       P.S.: Po dohodě mohu poskytnout assembleroidní zdrojáky
             k procedůrce textureline.


            výheň