Programowanie 3D cz. III

Ściany w przestrzeni tworzymy za pomocą wielokątów wypełnionych, najprostszym z nich jest trójkąt, ale ostatnio w modzie są czworokąty. Dla każdej ściany mamy możliwość użycia jednej z wielu metod wyświetlania takich jak jednokolorowe wypełnienie(FLAT SHADED) cieniowane przejście (GOURAUND SHADED) i najpopularniejsza metoda teksturowana. Tą ostatnią często łączy się z GOURAUND SHADED, dodaje mip-mapowanie, i wiele innych bajerów.

1. FLAT SHADED

Zaczniemy od najprostszej z nich czyli rysowaniu trójkąta jednokolorowego. Rysujemy ją od wierzchołka znajdującego się na samej górze i schodzimy powoli do dołu rysując poziome linie, szerokość tych linii ustalamy na podstawie specjalnych współczynników które ustalamy na początku. Rysowanie dokonujemy w dwóch fazach. Najpierw cześć górną od Y1 do Y2 następnie od Y2 do Y3;

           X1, Y1,
             / \               |
           /    \              |     Faza pierwsza 

X2,Y2 / \ V
? \ |
? \ | Faza druga
? \ |
? V
X3, Y3

Jak widać z rysunku współrzędne muszą być posortowane Y1 < Y2 < Y3 ( na ekranie punkt najwyższy ma najmniejszą wartość Y). Jak łatwo się domyślić będziemy podążać po współrzędnej Y, dlaczego?? Ponieważ wiemy ile przebiegów potrzebujemy na każdą fazę, dla pierwszej fazy Y2-Y1, a dla drugiej (Y3-Y2). Z tego wynika że jeśli Y1=Y2 to nie ma pierwszej fazy!!, podobnie jest gdy Y3=Y2 ale wtedy odpada nam faza druga. Jak łatwo się teraz domyślić gdy Y1=Y2=Y3 to nie ma żadnej fazy czyli nie rysujemy trójkąta. Wiemy już jak wyznaczyć Y naszej poziomej linii , przyszła kolej na X. Jak wspominałem potrzebne nam będą specjalne współczynniki. Nasz trójkąt ograniczony jest przez linie przyjrzyjmy się jednej z nich :

         X1, Y1
            / |             |                              ?|?
          /   |             |   Faza pierwsza        |
     P *---+ S1        |                               |    B=(Y2-Y1) 
      /       |             |                               |
    /------Sn            V                             ,|,

X2, Y2

   A=(X2-X1)
   |--------|

Wpisaliśmy linię w trójkąt, S1 to jakaś współrzędne Y wyznaczona przez krok fazy rysowania ( jest z przedziału od Y1 do Y2 ) Sn jest to ostatni krok fazy czyli Sn wynosi Y2. Naszym zadaniem jest wyznaczyć punkt P, jak widać punkt P jest prostopadły do S1, czyli ma taką samą współrzędną Y!! Jak widać mamy tu do czynienia z trójkątami podobnymi, czyli stosując odpowiednią skale możemy wyliczyć każdy punkt.
Za pomocą Talesa wyznaczymy punkt P, (X2-X1)/(Y2-Y1) = ( P.X - S1.X) / (S1.Y-Y1);
Każdy punkt wyznaczymy za pomocą tego wzoru, jak widać wartość (X2-X1)/(Y2-Y1) jest stała!! Wyliczamy ją tylko raz, to właśnie nasz współczynnik.
WSP = (X2-X1)/(Y2-Y1) ;
WSP = ( P.X - S1.X) / (S1.Y-Y1);
Chcemy mieć wzór na P.X czyli musimy dokonać przekształcenia.
WSP * (S1.Y-Y1) = P.X - S1.X
WSP * (S1.Y-Y1) +S1.X = P.X; to już gotowy wzór na P.X
Wartość w nawiasie (S1.Y-Y1) nie będzie trudno wyliczyć, bo S1.Y mamy, co natomiast z S.X?? czy je też mamy?? Jeśli się dobrze przyjrzeć to za uwarzymy że S1.X = X1 !!! czyli
P.X = X1 + wsp * (S1.Y-Y1);
Ten wzór użyjemy dla pozostałych linii( mamy je aż trzy :] ). Należy pamiętać że linia od Y1 do Y3 (ta najdłuższa ) przechodzi do obydwóch FAZ!!!
Wszystkie wzory wyglądają tak :

Wsp12 = (X2-X1)/(Y2-Y1) ;
Wsp13 = (X3-X1)/(Y3-Y1) ;
Wsp23 = (X3-X2)/(Y3-Y2) ;
P12 = x1 + wsp12 * (S1.Y- Y1)
P13 = x1 + wsp13 * (S1.Y- Y1)
P23 = x2 + wsp12 * (S1.Y- Y2) // tu należy pamiętać że punkt początku nie jest X1,Y1 tylko X2, Y2

Teraz pobawimy się już w rysowanie, na początek procka w Pascalu do rysowania poziomej linii. Nie musisz tego rozumieć, jak jesteś zainteresowany to poczytaj o asemblerze.

procedure Hline(x1, y1, x2: integer; c:byte); assembler;
 asm
  mov ax, 0A000h
  mov es, ax
  mov di, x1
  mov cx, x2
  cmp di, cx
  jl @ok
   xchg di, cx
  @ok:
  cmp di, 319
  jg @koniec
  cmp cx, 0
  jl @koniec
  cmp di, 0
  jge @ok2
   xor di,di
  @ok2:
  cmp cx, 320
  jl @ok3
   mov cx,319;
  @ok3:
  mov ax, y1
  sub cx, di
  shl ax, 6
  add di, ax
  shl ax, 2
  add di, ax
  mov al, c
  inc cx
  rep stosb
  @koniec:
 end;

Procedura poprawia tylko współrzędną X która powinna być z przedziału 0..319 ( rozdzielczość ekranu ), czyli gdy wypada z którejś strony to ją przytnie, i jeśli podamy X1 > X2 to zamieni je miejscami. Nie sprawdza natomiast czy linia znajduje się na ekranie względem wysokości, Y powinien być z przedziału 0..199(rozdzielczość ekranu ) w innym wypadku nie rysujemy jej, ponieważ rysowanie trójkąta będzie to korygować, na początku zrobimy to prostym sposobem, tzn. będziemy sprawdzać każdą rysowaną linie, później pokaże wam jak usprawnić tą czynność. Kolejna przydatna procka :

procedure xchg(var a,b,c,d:integer);
var p1:integer;
 begin
  p1:=a;
  a:=b;
  b:=p1;

  p1:=c;
  c:=d;
  d:=p1;
 end;

Zamienia wartości zmiennych A z B, oraz C z D... po co na to?? Zaraz zobaczycie, teraz już piszemy rysowanie trójkąta

procedure Trojkat(x1, y1,
                  x2, y2,
                  x3, y3 : integer;  col : byte);
var
 r,l       : real;
 i         : integer;
begin
{ te trzy linijki sortują Y rosnąco (Y1<Y2<Y3) i należy pamiętać o zmianie również X!! }
 if (y1>y2) then xchg(y1,y2,x1,x2);
 if (y2>y3) then xchg(y2,y3,x2,x3); 
 if (y1>y2) then xchg(y1,y2,x1,x2);

 
 if (y1=y2)and(y2=y3) then exit;     { Jeśli Y1 = Y2 = Y3 <- to koniec }

 l:=0;
 r:=0;        { to są nasze współczynniki  R liczy odcinek Y1=>Y2; L natomiast Y1=>Y3}

{ Trzeba sprawdzić czy nie dzielimy przez zero!! Jeśli tak to współczynnik wynosi 0 }
 if (y3<>y1) then l:=(x3-x1)/(y3-y1);
 if (y2<>y1) then r:=(x2-x1)/(y2-y1);

{ pierwsza faza : }
 for i:= y1 to y2-1 do      { to nasza pętla od Y1=>Y2;  dlaczego y2-1?? Bo następna faza zaczyna się w y2
                                           i nie ma sensu rysować 2 razy jedną linie  }
  begin
   if (i>=0) and (i<200) then  { sprawdzamy czy nie wypada za ekran  }

  { i rysujemy linie, wyliczamy punkty X ze wzorów :) y = i, no i ostatni parametr to kolor }
   hline(round(x1+l*(i-y1)),i, round(x1+r*(i-y1)), col); 
end;

{ R liczyło odcinek Y1=>Y2; teraz będzie liczyć Y2=>Y3, a  L zostaje bez zmian }
 r:=0;
 if (y3<>y2) then r:=(x3-x2)/(y3-y2);     

{ wykonujemy drugą faze wszystko tak samo jak w pierwszej tylko jedne wzór zmieniamy }
 for i:= y2 to y3 do
  begin
   if (i>=0) and (i<200) then
   hline(round(x1+l*(i-y1)),i, round(x2+r*(i-y2)), col);
  end;
end;

Nie było takie trudne co?? :] teraz przyśpieszymy naszą procedurę, zamiast wykonywać Y3-Y1*2 mnożeń wykonamy tyle samo dodawań :D przyjrzyjmy się pojedynczej fazie.

for i:= y1 to y2 do     
 hline(round(x1+l*(i-y1)),i, round(x1+r*(i-y1)), col); 

Jak widać wyciąłem sprawdzanie czy linia jest na ekranie, żeby łatwiej było analizować kod. Przyjrzyjmy się czy naprawdę trzeba za każdym razem mnożyć współczynnik przez (i-y1) ??,
I = Y1 => x1 + l*(i-y1) = x1 + l (Y1 ? Y1) = x1
I = Y1+1 => x1 + l(i-y1) = x1 + l ((Y1+1) ? Y1) = x1+l
I = Y1+2 => x1 + l(i-y1) = x1 + l ((Y1+2) ? Y1) = x1+2l itd.
Jak widać X w każdej następnej pętli jest większy o wsp od poprzedniej. Czyli wystarczy że przed rozpoczęciem kolejnej pętli zwiększymy X1 o wsp. Nowy kod rysujący pierwszą fazę wyglądać będzie tak :

 cl:=x1;
 cr:=x1;                       { ustawiamy cl i cr na wartości początkowe. }
 for i:= y1 to y2-1 do      { rozpoczynamy pętle }
  begin
   if (i>=0) and (i<200) then
   hline(round(cl),i, round(cr), col);    { rysujemy linie od cl do cr }
   cr:=cr+r;                                           { i zwiększamy nasze zmienne o wartość współczynnika }
   cl:=cl+l;
  end;

Co z drugą fazą ?? cle zostawiamy bez zmiany , natomiast cr będzie równy X2, ponieważ druga linia zaczyna się w tym miejscu. Może podam jeszcze całą procedurę, żeby nie było wątpliwości.

procedure Trojkat(x1, y1,
                  x2, y2,
                  x3, y3 : integer;  col : byte);
var
 r,l       : real;
 i         : integer;
 cl, cr    : real;
begin
 if (y1>y2) then xchg(y1,y2,x1,x2);
 if (y2>y3) then xchg(y2,y3,x2,x3);
 if (y1>y2) then xchg(y1,y2,x1,x2);
 if (y1=y2)and(y2=y3) then exit;
 l:=0;
 r:=0;
 if (y3<>y1) then l:=(x3-x1)/(y3-y1);
 if (y2<>y1) then r:=(x2-x1)/(y2-y1);

 cl:=x1;
 cr:=x1;
 for i:= y1 to y2-1 do
  begin
   if (i>=0) and (i<200) then
   hline(round(cl),i, round(cr), col);
   cr:=cr+r;
   cl:=cl+l;
  end;
 r:=0;
 cr:=x2;
 if (y3<>y2) then r:=(x3-x2)/(y3-y2);
 for i:= y2 to y3 do
  begin
   if (i>=0) and (i<200) then
   hline(round(cl),i, round(cr), col);
   cr:=cr+r;
   cl:=cl+l;
  end;
end;

2. Cliping 2D.

Teraz dokonamy ostatniej zmiany, będziemy korygować wejście do każdej fazy =D, teraz w jakim sensie?? Należy zauważyć że każda faza ma trzy przypadki może być w całości na ekranie(rysujemy ją jakby nigdy nic), w całości za ekranem(nie rysujemy jej), kolejny przypadek jest wtedy gdy jej pewna część wypada za ekran( początek jest mniejszy od zera, lub koniec jest większy od 199, może wystąpić również kombinacja tych dwóch przypadków!! ). Pierwszy i drugi przypadek to żaden problem... rozpatrzymy tą trzecią możliwość.
Wszystko na podstawie fazy pierwszej, drugą się robi bardzo podobnie.

a) Początek fazy jest za ekranem
?Y1
/ |
+--------* * -----+ Y= 0
| Y2 / | |
| ? | |
| ?| |
| |
+-------------------+

b) Koniec Fazy wypada za ekran

+-------------------+
| |
| |
| ? Y1 | -
| / | | | a
+-----/ |---------+ Y= 199 -
Y2 / |
? |
? |
?

c) mix a i b.

             Y1
                , 

+---------* *---------+ Y0=0 -
| / | | |
| / | | |
| / | | | a
| / | | |

• ---/ |----+ Y199 = 199 -
  / |
  Y2 / |
  ? , |

a) W tym przypadku musimy znaleźć punkt zaznaczone jako *, czyli zacząć rysowanie już od pewnego momentu. Będziemy korzystać z tych wzorów co wcześniej czyli P.X = X1 + wsp * (S1.Y-Y1);
Nasz S1 wynosi zero po podstawieniu mamy P.X = X1 + wsp * (-Y1); i tak oto mamy wzór na nasze pozycje początkowe. Teraz nasz nowy Y1 wyniesie 0 :] czyli ilość kroków dla fazy pierwszej wyniesie Y2-Y1 czyli po prostu Y2;

b) W tym wypadku sprawa jest banalna jedynie zmianie ulega ilość kroków w fazie, kończymy ją wcześniej ilość kroków do wykonania będzie równa 200-Y1. Druga faza rysowania trójkąta nie istnieje.

c) To przypadek bardzo ciekawy :] należy najpierw wyliczyć punkty startowe jak w przypadku A, następnie wykonać 199 kroków.
Należy pamiętać że DRUGA FAZA MA TAKIE SAME PRZYPADKI!!!!. Żeby uniknąć niejasności jak zwykle kod źródłowy w Pascalu...

procedure Trojkat(x1, y1,
                  x2, y2,
                  x3, y3 : integer;  col : byte);
var
 r,l       : real;
 i         : integer;
 cl, cr    : real;
 size      : integer;
begin
 if (y1>y2) then xchg(y1,y2,x1,x2);
 if (y2>y3) then xchg(y2,y3,x2,x3);
 if (y1>y2) then xchg(y1,y2,x1,x2);

 if (y1=y2)and(y2=y3) then exit;

 if y3<0 then exit;    { gdy y3 wypada na górze to nie ma trójkąta }
 if y1>199 then exit; {podobnie gdy y1 wypada na dole }

 l:=0;
 r:=0;
 if (y3<>y1) then l:=(x3-x1)/(y3-y1);
 if (y2<>y1) then r:=(x2-x1)/(y2-y1);

 cl:=x1;
 cr:=x1;

if y2>=0 then      { y2>=0 <- istnieje faza pierwsza }
begin
 if y1<0 then    { wiemy że faza istnieje ale może zaczynać się poza ekranem =>  y1<0 }
   begin             { korygujemy początki  ( przypadek a )  }
    cl:=cl-l*y1;
    cr:=cr-r*y1;
    y1:=0;
   end;

  if y2<201 then size:=y2-1 else size:=199;   { faza również może się kończyć poza ekranem( przypadek b ) }                                                                         

 for i:= y1 to size do                         { teraz mamy pętle od y1 => size }
  begin
   hline(round(cl),i, round(cr), col);
   cr:=cr+r;
   cl:=cl+l;
  end;

  if size=199 then exit; { faza 1 była ostatnia :P }
end; 

{ jak tutaj dojdziemy to znaczy że faza 2 musi istnieć }
 r:=0;
 cr:=x2;
 if (y3<>y2) then r:=(x3-x2)/(y3-y2);

 if y2<0 then        { ale może zaczynać się poza ekranem ( przypadek a) }
  begin
   cr:=cr-r*y2;
   cl:=cl-l*y1;
   y2:=0;
  end;

 if y3>199 then y3:=199;     { lub kończyć poza ekranem }
 for i:= y2 to y3 do
  begin
   hline(round(cl),i, round(cr), col);
   cr:=cr+r;
   cl:=cl+l;
  end;
end;

Już mamy pełne rysowanie trójkąta FLAT_SHADED, dość optymalna wersja to oczywiście ta ostatnia. Nie wykonujemy w niej żadnych niepotrzebnych obliczeń, zaczynamy rysować trójkąt nie od miejsca gdzie się zaczyna ale od miejsca w którym staje się widoczny na ekranie, i kończymy w momencie gdy przestaje byś widoczny(CLIPING 2D ), nie używamy do tego każdorazowego sprawdzania czy linia wypada gdzieś poza ekran !! =D. Jeśli chcesz to ZNACZNIE przyśpieszyć to zamiast definicji zmiennych typu REAL, zmień je na SINGLE. Jeśli zmienisz na single to nie zapomnij nad całym programem umieścić {$N+,G+} <= bez żadnych spacji itp.

3. GOURAUND SHADED

Ta technika daje nieco ciekawsze efekty niż wymieniona wyżej. Ponieważ w odróżnieniu od poprzedniej nie rysuje jednokolorowego trójkąta ale przechodzącego w różne odcienie. Do procedury rysującej dojdą zatem dwa parametry. Cała zasada rysowania trójkąta jest taka sama musimy tylko dodać interpolacje koloru, która wygląda dokładnie tak samo jak dla X!!. Musimy jeszcze napisać procedurę rysującą linie poziomą przechodzącą płynnie z jednego koloru w drugi.

  (X1, Y1, C1)  ----------------------- (X2, Y1, C2); 

x1, y1, x2 <- nie wymagają chyba komentarza.
C1 <- to kolor w punkcie X1,Y1
C2 <- to kolor w punkcie X2, Y1

Należy pamiętać że przed rysowaniem linii musimy sprawdzić:
? Czy X1 = X2 => jeśli tak nie rysujemy linii;
? Czy X1 < X2 => jeśli nie zamieniamy je wartościami; należy pamiętać o zamianie również kolorów!!
? Czy X2 < 0 => jeśli tak to nie rysujemy linii
? Czy X1 > 319 => jeśli tak to nie rysujemy linii

Najlepiej jest sprawdzać w tej właśnie kolejności;

Aby narysować linie musimy postawić X2-X1 punktów( jest to ilość kroków w interpolacji).
Nasze zadanie to ustalić kolor każdego z nich, w tym celu musimy dodawać (X2-X1) razy jakąś wartość, do koloru C1, tak żeby na końcu (w kroku X2-X1) otrzymać kolor C2; przekładając to na język matematyki wygląda to tak:
C1 + wsp * (X2-X1) = C2
Przekształcamy i otrzymujemy wzór na wsp : wsp = (C2-C1) / (X2-X1);

Teraz musimy skorygować wymiary linii, jeśli X2 wypada za ekran po prawej stronie to nadajemy mu wartość 319; W wypadku gdy X1<0 wtedy sprawa się komplikuje :] ponieważ PRZED przypisaniem X1 wartości 0, musimy ominąć (-X1) kroków interpolacji dla koloru, czyli ustawić kolor początkowy na
COLOR = C1 - wsp*x1; <= czyli tak jak to robiliśmy dla wysokości.

procedure HGline(x1, y1, x2: integer; c1:byte; c2:byte);
var c:single;
 adc:single;
 pom:integer;
 i:integer;
 adr:word;
 begin

   { tutaj sprawdzamy przypadki w których nie rysujemy linii }
  if x1=x2 then exit;    
  if x1>x2 then         { przed sprawdzaniem kolejnych musimy mieć pewność że X1<X2 }
   begin
    pom:=x1;
    x1:=x2;
    x2:=pom;

    { pamiętać o zamianie kolorów!! }
    pom:=c1;            
    c1:=c2;
    c2:=pom;
   end;

  if x1>319 then exit;
  if x2<0 then exit;
  adc:=(c2-c1)/(x2-x1);
  c:=c1;

  if x1<0 then       { tutaj musimy ?przyciąć? interpolacje o X1 kroków }
   begin
    c:=c-adc*x1;
     x1:=0;
   end;

 adr:=x1+y1*320;     { tak się liczy adres pixela w karcie graficznej }
  if x2>319 then x2:=319;

  for i:=x1 to x2 do     { wykonujemy X2-X1 kroków; całą interpolacje }
   begin
    mem[$A000:adr]:=byte(round(c));   { to przesyła pixel o kolorze c w odpowiednie miejsce pamięci }
    adr:=adr+1;                                        { przechodzimy do pixela obok }
    c:=c+adc;                                           { interpolujemy kolor }
   end;
 end;

Teraz możecie pobawić się w przełożenie tego na kod asemblerowy =P, żeby przyśpieszyć działanie hyhy.
Nie będę zamieszczać tutaj całego kodu rysowania gouraund. Ponieważ wszystko odbywa się identycznie jak przy flat.

             X1, Y1, C1
                     / \               |
                   /    \              |     Faza pierwsza 

X2,Y2, C2 / \ V
? \ |
? \ | Faza druga
? \ |
? V
X3, Y3, C3

Z kolorem będziemy obchodzić się jak ze współrzędną X( co można było wywnioskować z rysunku). Czyli jeśli liczymy
P12 = x1 + wsp12 * (S1.Y- Y1) to kolor policzymy C12 = c1 + wspC12 * (S1.Y- Y1);
Jedyne czym się różnią to współczynnikami, współczynnik dla X liczyliśmy ze wzoru Wsp12 = (X2-X1)/(Y2-Y1) ; to dla koloru policzymy WspC12 = (C2-C1)/(Y2-Y1) ; analogie widać !! =D To samo tyczy się clipingu 2D np. Jeśli zrozumiałeś artykuł to powinieneś poradzić sobie z napisaniem tej procedury, ale nie martw się jeśli ci nie wychodzi, w załączniku znajduje sie program prezentujący metode gouraund.

Ostatniej metody tzn. Teksturowania nie omówię w tym artykule, musicie jeszcze trochę poczekać.