Algorytm Bresenhama z niezmienną osią wiodącą

1

Piszę sobie software'ową rasteryzację trójkąta z wykorzystaniem techniki polegającej na podążaniu wzdłuż osi Y z góry na dół, wykrywaniu kolejnych pikseli wschodzących w skład boków trójkąta i łączenie ich poziomą linią (scan line).

Możliwie najprostszym rozwiązaniem jest tutaj algorytm DDA, który jednak z uwagi na wykorzystanie dzielenia liczb zmiennoprzecinkowych i zaokrągleń, nie jest zbyt wydajny. Jego rozwinięciem jest słynny algorytm Bresenhama, który działa podobnie, ale operuje tylko na liczbach całkowitych (a więc jest szybszy), a do tego zapewnia większą dokładność (bo nie wymusza zaokrągleń).

Są też inne algorytmy (np Wu Line czy EFLA), które zapewniają nawet większą wydajność, ale póki co, głównie z uwagi na prostotę, stawiam na Bresenhama. Niestety jego adaptacja do moich potrzeb mnie przerosła...

Pewnie każdy koder o tym algorytmie słyszał, ale raczej nie każdy zagłębiał się w jego działanie, więc pokrótce wyjaśnię.

Mamy 2 punkty w przestrzeni 2D, które chcemy połączyć linią. Weźmy np.

P1 = [1, 1]
P2 = [12, 6]

  1. Liczymy wektor pomiędzy nimi [X2 - X1, Y2 - Y1], czyli [12 - 1, 6 - 1], a więc wektor = [11, 5].
  2. Wyznaczamy oś wiodącą oraz oś uboczną (po co się to robi, wyjaśni się dalej). Osią główną jest zawsze ta dłuższa, uboczną krótsza. U nas wiodącą osią będzie X (bo = 11), uboczną Y( bo = 5).
  3. Wyznaczamy kierunek ruchu na obu osiach, który może przyjąć jedną z 3 wartości: +1, -1 lub 0. U nas obie osie są dodatnie, więc kierunek ruchu na obu osiach również będzie dodatni, czyli X = +1, Y = +1 (ruch będzie się więc odbywać z lewej na prawo i z góry na dół).
  4. Liczymy 3 wartości: Pozytywny (P), Negatywny (N) oraz Czynnik Decyzyjny (D)
  • Pozytywny (P) liczymy ze wzoru: P = 2 x (Wektor Osi Ubocznej - Wektor Osi Wiodącej), a więc 2 x (5 - 11), czyli -12 (Pozytywny zawsze powinien mieć wartość ujemną, co stanie się zrozumiałe później).
  • Negatywny (N) to N = 2 x Wektor Osi Ubocznej, czyli N = 2 x 5 = 10 (ten zawsze powinien być dodatni)
  • Czynnik Decyzyjny (D) liczymy jako Negatywny (N) - Wektor Osi Wiodącej, a więc D = 10 - 11 = -1*
  1. Wyznaczamy wartość początkową X i Y, które zawsze są równe odpowiednio P1.X i P1.Y.
  2. Po zakończeniu tych przygotowań możemy przejść do właściwej pętli wyznaczającej kolejne współrzędne pikseli wchodzących w skład linii. Pętla powinna mieć długość równą długości osi wiodącej. U nas będzie to więc od 0 do 10 (albo jak kto woli, od 1 do 11).

Co robimy w pętli?

A). Ruch na osi wiodącej wykonujemy ZAWSZE. U nas jest to X, więc przy każdym powtórzeniu X = X + KierunekRuchuX, czyli X = X + 1.
B). Ruch na osi ubocznej wykonujemy tylko wtedy, gdy wartość czynnika decyzyjnego (D) jest większa niż 0 (D > 0). Jeżeli tak, wykonujemy 2 czynności:

  • Y = Y + KierunekRuchuY, czyli Y = Y + 1.
  • Modyfikujemy wartość czynnika decyzyjnego (D) przy pomocy obliczonej wcześniej wartości Pozytywny (P), czyli D = D + P. Czynnik decyzyjny (D) jest pozytywny, więc dodajemy do niego Pozytywny modyfikator (teraz to ma sens, prawda? ;s).*
    C). Jeżeli natomiast czynnik decyzyjny jest ujemny lub równy 0 (D <= 0), wtedy wykonujemy tylko jedną czynność, dodajemy do niego Negatywny modyfikator (N), a więc D = D + N.

Ot i cały algorytm, prześledźmy może kawałek na naszym przykładzie:

V = [11, 5]
P = -12
N = 10
D = -1
X = 1 (wiodąca)
Y = 1 (uboczna)

Krok 1:
X = X + 1 = 2 (bo zwiększamy zawsze)
Y = 1 (D < 0, więc nie zwiększamy)
D = D + N = 9 (modyfikujemy czynnik decyzyjny)

Krok 2:
X = 3
Y = 2 (bo D > 0)
D = D + P = -3

Krok 3:
X = 4
Y = 2
D = 7

itd.

Teraz mój właściwy problem. Jak pisałem we wstępie, chcę wykorzystać ten algorytm do wyznaczania boków trójkąta. Rzecz w tym, że przy rysowaniu poprzez scan line, muszę oś Y traktować zawsze jako wiodącą, bo pętla przy każdym powtórzeniu MUSI przeskakiwać o jedną linię do dołu (Y = Y + 1). Generalna zasada jest taka, że na każdy ruch na dłuższej osi przypada jakaś szczątkowa część ruchu na osi krótszej (a więc jeżeli X = X + 1, to Y = np. Y + 0.2). Tyle, że rasteryzacja musi być wykonywana do pełnych pikseli, więc te szczątkowe ruchy, mniejsze niż 0.5, się pomija (przez zaokrąglenie jak w DDA, albo przez kumulowanie tych szczątków w czynniku decyzyjnym, jak u Bresenhama). Jeżeli więc każdy ruch szczątkowy zwielokrotnię jakąś tam ilość razy (by dojść do wartości umożliwiającej wykonanie jednego pełnego ruchu), to taką samą operację muszę wykonać na drugiej osi, czyli X.

Powiedzmy, że ruch szczątkowy na Y wynosi 0.2, na X oczywiście pełne +1. Krok pierwszy, X zwiększamy o 1, Y wynosi 0.2 więc zostawiamy w spokoju. Krok drugi, X znowu zwiększamy o 1, Y to 0.4, więc nadal nie robimy z nim nic. Krok trzeci, X rośnie o 1, Y to już 0.6, więc zwiększamy o 1. Czyli widać wyraźnie, że na każdy 1 ruch na Y, wykonać trzeba 3 ruchy na X. Rozumiejąc tę zależność, jestem w stanie wyliczyć o ile powinno przeskoczyć X, przy każdym ruchu wynoszącym Y + 1.

Niby logiczne, ale nie mam pojęcia jak to zrobić bez dzielenia i wykorzystania pętli while lub repeat. Próbowałem to zrobić z nimi, ale wtedy szybkość spada na tyle, że algorytm zrównuje się z DDA (czyli najbardziej prymitywną i wolną implementacją). Ktoś ma pomysł jak to zrobić inaczej?

Przepraszam za długi post, ale wolałem nie ryzykować, że ktoś potencjalnie pomocny się zniechęci nie znając działania algorytmu Bresenhama.

1

Nie wiem na 100% czy o to Ci chodzi ale przypuszczam, że tak. Jak byłem jeszcze młody 20 lat temu to pisałem takie rzeczy i coś wygrzebałem ( na szczęście jeszcze znalazłem wersje niezoptymalizowane bo te zoptymalizowane już do analizy się nie nadają ):

Niestety nie bardzo rozumiem co chcesz ostatecznie wyliczyć.... Co znaczy wyznaczyć bok trójkąta ? Narysować linię czy co ?

Trójkąt wypełniony:


Procedure FilledTriangle(x1,y1,z1,x2,y2,z2,x3,y3,z3:double);
Var
z,dx12,dx13,dx23,x,y,xl1,xl2,xl3:double;
Begin


     y1:=trunc(y1);y2:=trunc(y2);y3:=trunc(y3);

     if (y1>y2) then Begin
			 z:=x1;x1:=x2;x2:=z;
			 z:=y1;y1:=y2;y2:=z;
                 End;
     if (y2>y3) then Begin
			 z:=x2;x2:=x3;x3:=z;
			 z:=y2;y2:=y3;y3:=z;
                 End;
     if (y1>y2) then Begin
			 z:=x1;x1:=x2;x2:=z;
			 z:=y1;y1:=y2;y2:=z;
                 End;

     if (y2<>y1) then dx12:=(x2-x1)/(y2-y1);
     if (y3<>y1) then dx13:=(x3-x1)/(y3-y1);
     if (y3<>y2) then dx23:=(x3-x2)/(y3-y2);

     y:=y1;x:=x1;xl1:=x;xl2:=x;
     while (y<y2)do
     Begin
       line(trunc(xl1),trunc(y),trunc(xl2),trunc(y));   // <----  TUTAJ pary ( xl1,y ), (xl2, y ) WYZNACZAJĄ BOKI TRÓJKĄTA Y jest stały rysujemy tylko pixele w poziomie
       y:=y+1;
       xl1:=xl1+dx12;
       xl2:=xl2+dx13;
     End;

     y:=y2;xl1:=x2;
     while(y<y3)do
     Begin
       line(trunc(xl1),trunc(y),trunc(xl2),trunc(y)); // <-- Y jest stały rysujemy tylko pixele w poziomie
       y:=y+1;
       xl1:=xl1+dx23;
       xl2:=xl2+dx13;
     End;
End;

(o znalazłem też w c++)

void filledtriangle(double x1,double y1,double x2,double y2,
		    double x3,double y3,char kol)
{
    double z,dx12,dx13,dx23,x,y,xl1,xl2,xl3;
     y1=trunc(y1);y2=trunc(y2);y3=trunc(y3);

     if (y1>y2)  {
			 z=x1;x1=x2;x2=z;
			 z=y1;y1=y2;y2=z;
		   }
     if (y2>y3)  {
			 z=x2;x2=x3;x3=z;
			 z=y2;y2=y3;y3=z;
		   }
     if (y1>y2)  {
			 z=x1;x1=x2;x2=z;
			 z=y1;y1=y2;y2=z;
		   }

     if (y2!=y1) dx12=(x2-x1)/(y2-y1);
     if (y3!=y1) dx13=(x3-x1)/(y3-y1);
     if (y3!=y2) dx23=(x3-x2)/(y3-y2);

     y=y1;x=x1;xl1=x;xl2=x;
     while (y<y2)
     {
       line(trunc(xl1),trunc(y),trunc(xl2),kol); // <-- Linia tylko w poziomie 
       y++;
       xl1=xl1+dx12;
       xl2=xl2+dx13;
     }

     y=y2;xl1=x2;
     while(y<y3)
     {
       line(trunc(xl1),trunc(y),trunc(xl2),kol); // <-- Linia tylko w poziomie 
       y++;
       xl1=xl1+dx23;
       xl2=xl2+dx13;
     }
}

0

Dzięki za odpowiedź!

Nie wątpię, że twój algorytm działa i robi co ma robić, ale już na oko widać, że zawiera on wszystko to, czego wydajny raster mieć nie powinien :). Liczby zmiennoprzecinkowe, dzielenie (to angażuje FPU i synchronizację między nim a CPU), dużo sprawdzeń warunków logicznych. Bo generalnie napisanie JAKIEGOŚ algorytmu rasteryzującego to pestka (są dziesiątki różnych implementacji). Napisanie szybkiego, to już trudniejsza sztuka, ale właśnie to mnie interesuje (bo całość jest częścią software'owego silnika 3D i każda klatka na sekundę jest na wagę złota).

0
Crow napisał(a):

Dzięki za odpowiedź!

Nie wątpię, że twój algorytm działa i robi co ma robić, ale już na oko widać, że zawiera on wszystko to, czego wydajny raster mieć nie powinien :). Liczby zmiennoprzecinkowe, dzielenie (to angażuje FPU i synchronizację między nim a CPU), dużo sprawdzeń warunków logicznych. Bo generalnie napisanie JAKIEGOŚ algorytmu rasteryzującego to pestka (są dziesiątki różnych implementacji). Napisanie szybkiego, to już trudniejsza sztuka, ale właśnie to mnie interesuje (bo całość jest częścią software'owego silnika 3D i każda klatka na sekundę jest na wagę złota).

Jak napisałem to kod niezoptymalizowany gdybym go przysłał w asm po optymalizacji do liczb całkowitych to nic by z niego nie wynikało.
Dałem to jako przykład żebyś mógł się do niego odnieść zamiast Twojego średnio zgrabnego opisu..

Jeszcze raz proszę napisz co dokładnie chcesz wyznaczyć bo ciężko wywnioskować o co Ci chodz... czyli co wg Ciebie oznacza "wyznaczyć boki trójkąta". Narysować linię czy co ?

0

Mam trójkąt opisany jako trzy dwuwymiarowe wierzchołki (X, Y). Sortuję je względem osi Y (od wartości najmniejszej do największej), dzięki czemu P1.Y < P2.Y < P3.Y. Póki co uprośmy sytuację do rysowania trójkątów o płaskiej podstawie, gdzie zawsze P2.X = P3.X. Żeby narysować taki trójkąt muszę wyznaczyć linie tworzące boki P1 -> P2 oraz P1 -> P3, tj. odczytać współrzędne wszystkich pikseli wchodzących w skład tych boków.

/\ /=\ /==\ /===\ /====\ /=====\ /======\

Slashe na powyższym schemacie, to te szukanie współrzędne pikseli (interesuje mnie tylko współrzędna X, bo Y jest znana i zawsze wynosi P1.Y + 1 dla danej linii). Wiem jak wyznaczyć ich współrzędne. Nie wiem natomiast, jak to zrobić bez używania dzielenia, zaokrągleń i operacji na liczbach zmiennoprzecinkowych (bo to są największe pożeracze wydajności). Bresenham sobie z tym radzi, ale on w czystej postaci nie nadaje się do synchronicznego szukania punktów na dwóch liniach, gdzie ruch zawsze jest stały i wynosi Y + 1 w każdej pętli, niezależnie od faktycznej osi wiodącej.

0

Jeszcze raz żebym dobrze zrozumiał...

Problem 1: jak to zrobić bez używania dzielenia, zaokrągleń i operacji na liczbach zmiennoprzecinkowych. Banał jeśli potwierdzisz to wygrzebię przykład lub przypomnę sobie i napiszę od nowa ( wybacz, że nie napiszę z głowy ale ostatnio robiłem to ponad 20 lat temu ).

Problem 2(finalny): Jak narysować 2 boki trójkąta ( płaskiego od dołu czyli "połowy" ) nie używając dzielenia i liczb zmiennoprzecinkowych. Tak ?

Tak czy siak problem sprowadza się do rysowania krawędzi trójkąta powyższym algorytmem nie używając liczb float... Tak ?

0

Tutaj masz prawdopodobnie algorytm, którego szukasz. Oczywiście dotyczy tylko linii ale jak łatwo się domyślić bez trudu można go przerobić tak by obie krawędzie trójkąta rysował w jednej pętli.
Jednak UWAGA: ten algorytm wcale nie musi być szybszy od jego wersji podstawowej. Wszystko zależy od tego jak ostatecznie zoptymalizowane są pętle i instrukcje skoku.
Zauważ, że w każdym przebiegu masz teraz 2 instrukcje warunkowe.
W pewnych przypadkach szybszy jest algorytm klasyczny bo jest tylko jeden warunek pętli. Trzeba jednak rzutować typy zmiennych ( co w językach kompilowanych czy ASM nie jest najmniejszym problemem ).


void bresenham(int x1, int y1, int x2, int y2) 
{ 
   int m_new = 2 * (y2 - y1); 
   int slope_error_new = m_new - (x2 - x1); 
   for (int x = x1, y = y1; x <= x2; x++) 
   { 
      cout << "(" << x << "," << y << ")\n"; 
  
      // Add slope to increment angle formed 
      slope_error_new += m_new; 
  
      // Slope error reached limit, time to 
      // increment y and update slope error. 
      if (slope_error_new >= 0) 
      { 
         y++; 
         slope_error_new  -= 2 * (x2 - x1); 
      } 
   } 
} 

1

Dobry schemat nie jest zły :].

title

Chodzi o to, żebym w jednym obrocie pętli mógł wyznaczyć współrzędne obu punktów oznaczonych tym samym kolorem. A więc w pierwszym wyznaczam obie współrzędne żółte, w drugim fioletowe, w trzecim zielone itd. Bez zaokrągleń, dzielenia i liczb zmiennoprzecinkowych.

0

Daj mi trochę. Muszę sięgnąć pamięcią do "dzieciństwa" i niebawem wypluję wynik... Moim zdaniem i z tego co pamiętam lepsza była wersja klasyczna z optymalizacją liczb zmiennoprzecinkowych niż ten drugi algorytm, który dałem wyżej. Dlatego zaimplementuję to co uważam za szybsze ( może się mylę bo jak pisałem minęło 20 lat ).

p.s.

Może być Delphi ? Bo tak na szybko to nie mam pojęcia jak w c++ zainicjować grafikę i jakiś bufor ekranu.

0

No to mamy...
Jeśli się nigdzie nie trzasnąłem to powinno być .. Jak to mówią wstępnie u mnie działa ( nie wykluczam, że są jeszcze błędy ) ...

screenshot-20200126194805.png


type
  TVirtualFloat = record
    floatPart : int16 ;
    intPart : int16 ;
  end ;
  // w zależności od architektury CPU big endian / little endian może być wymagana odwrotna kolejność zmiennych w strukturze.

function TriangleFilledFast ( x1,y1,x2,y2,x3,y3:int32 ) : integer ;

var
  z, dx12, dx13, dx23, x, y, xl1, xl2 : int32 ;
  _xl1  : TVirtualFloat absolute xl1 ; // zmienna _x11 jest umiejscowiona pod tym samym adresem co x11
  _xl2  : TVirtualFloat absolute xl2 ; // zmienna _x12 jest umiejscowiona pod tym samym adresem co x12

begin

  //
  // Sortowanie wierzchołków po osi Y
  //
  if ( y1 > y2 ) then begin
    z:=x1; x1:=x2; x2:=z;
    z:=y1; y1:=y2; y2:=z;
  end;

  if ( y2 > y3 ) then begin
    z:=x2; x2:=x3; x3:=z;
    z:=y2; y2:=y3; y3:=z;
  end;

  if ( y1 > y2 ) then begin
    z:=x1; x1:=x2; x2:=z;
    z:=y1; y1:=y2; y2:=z;
  end;


  //
  // Wyliczanie współczynników dla wszystkich trzech boków trójkąta
  //
  if ( y2<>y1 ) then dx12 := ( ( x2 - x1 ) shl 16 ) div ( y2 - y1 ) ;
  if ( y3<>y1 ) then dx13 := ( ( x3 - x1 ) shl 16 ) div ( y3 - y1 ) ;
  if ( y3<>y2 ) then dx23 := ( ( x3 - x2 ) shl 16 ) div ( y3 - y2 ) ;

  y := y1;
  x := x1;
  xl1 := x shl 16; // bo xl1 i xl2 jest pseudo-zmiennoprzecinkowe
  xl2 := xl1 ;
  //
  // rysujemy pierwszą górną część trójkąta ( jeśli jest )
  //
  while ( y < y2 ) do
  Begin
    line ( _xl1.intPart, y, _xl2.intPart, y );
    y := y + 1 ;
    xl1 := xl1 + dx12 ;
    xl2 := xl2 + dx13 ;
  End;

  y := y2;
  xl1 := x2 shl 16; // bo xl1 jest pseudo-zmiennoprzecinkowe
  //
  // rysujemy drugą dolną część trójkąta ( jeśli jest )
  //
  while ( y < y3 ) do
  Begin
    line( _xl1.intPart, y, _xl2.intPart, y ) ;
    y := y + 1 ;
    xl1 := xl1 + dx23 ;
    xl2 := xl2 + dx13 ;
  End;

End;

I teraz tak... Pisząc to uświadomiłem sobie, że twoja metoda wyznaczania boków trójkąta jest bez sensy z 2 powodów...

  1. Nie będziesz miał każdego piksela w obu liniach ( w sensie lewej i prawej ) bo to działa tylko gdy mamy trójkąt wypełniony ;

screenshot-20200126205326.png

  1. Oszczędność będzie znikoma nawet jeśli będziesz leciał po dłuższej krawędzi bo będziesz rysował na krótkiej po kilka pikseli w tym samym miejscu ...
  2. Lepiej rysuj 3 linie. Statystycznie czasowo wyjdzie lepiej.

Generalnie powyższy algorytm jest dopiero wstępem do rozpoczęcia optymalizacji.

Załącznik z projektem w Delphi do pobrania ...

0
katakrowa napisał(a):
  1. Nie będziesz miał każdego piksela w obu liniach ( w sensie lewej i prawej ) bo to działa tylko gdy mamy trójkąt wypełniony ;

Nic podobnego. Co ma wyznaczenie współrzędnej X piksela wchodzącego w skład linii, będącej bokiem trójkąta, do wypełnienia tego trójkąta? Szczerze, nie dostrzegam związku.

  1. Oszczędność będzie znikoma nawet jeśli będziesz leciał po dłuższej krawędzi bo będziesz rysował na krótkiej po kilka pikseli w tym samym miejscu ...

Nie będę. Cały algorytm polega na wyznaczeniu początku i końca horyzontalnej linii (X początkowe i końcowe) a potem narysowanie tej linii. Nic na siebie nie zachodzi, każdy piksel malowany jest tylko raz.

  1. Lepiej rysuj 3 linie. Statystycznie czasowo wyjdzie lepiej.

Nie rozumiem. A gdzie miałaby być ta 3 linia?

Dodatkowo JAKIEKOLWIEK dzielenie odpada. Gdy trzeba wyrenderować obiekty na które składa się sumarycznie 30 tysięcy trójkątów 60 razy na sekundę, oznacza to w ch... bardzo dużo zapytań do FPU. Na tyle dużo, że cała przewaga korzystania tylko z liczb całkowitych, zostaje zniwelowana. Wiem, bo testowałem.

0

Przecież przedstawiłem Ci algorytm co FPU nie używa wszystko jest na liczbach całkowitych typu INT.

Obawiam się, że nie wiem o czym piszesz lub pokaż ten algorytm co rysuje 2 linie jednocześnie bo jakoś tego nie widzę.
Może być z z dzieleniem i liczbami float bo jak widać na przykładzie, który podałem każdego float'a można zamienić na całkowite tym samym eliminując wszelki operacje FPU.

Lepiej będzie jak będziesz rysował każdy z trzech boków trójkąta osobno.
Nie oszczędzisz jak podzielisz go na dwie części ( po 2 odcinki każda ).

Jeszcze raz obrazek z posta wyżej ( efekt rysowania 2 linii w jednej pętli poruszając się po Y ).
screenshot-20200126205705.png

0

Oto kod. Bardzo prosty, napisany w 20 minut (dlatego prymitywny, na canvasie).

//Swap to procedura pomocnicza do zamiany punktów miejscami

procedure Swap(var AP1, AP2: TPoint); inline;
var
  Temp: TPoint;
begin
  Temp := AP1;
  AP1 := AP2;
  AP2 := Temp;
end;

procedure DrawTriangle(AP1, AP2, AP3: TPoint);
var
  V1, V2: TPoint;
  SlopeLeft, SlopeRight: Single;
  Y, Start, Over: NativeInt;
begin
  {Sortowanie wierzchołków w osi Y}

  if AP1.Y > AP3.Y then Swap(AP1, AP3);
  if AP1.Y > AP2.Y then Swap(AP1, AP2);
  if AP2.Y > AP3.Y then Swap(AP2, AP3);

{Wyznaczanie wektorów}

  V1 := Point(AP3.X - AP1.X, AP3.Y - AP1.Y); //Oblicza wektor pierwszego boku (P1 --> P3)
  V2 := Point(AP2.X - AP1.X, AP2.Y - AP1.Y); //Oblicza wektor drugiego boku (P1 --> P2)

//Poniższy kod sprawdza który bok jest lewy, a który prawy, dzięki czemu będzie wiadomo co jest początkiem, a co końcem linii. 
//Gdy to ustali, wylicza nachylenie linii (slope), które określa wartość przesunięcia przy każdym kroku na osi X, przypisując je 
//do odpowiednich zmiennych.

  if V1.X < V2.X then //Wektor 1 wyznacza lewy bok trójkąta
    begin
      if V1.Y <> 0 then SlopeLeft := V1.X / V1.Y else SlopeLeft := 0;
      if V2.Y <> 0 then SlopeRight := V2.X / V2.Y else SlopeRight := 0;
    end else
    begin //Wektor 2 wyznacza lewy bok trójkąta
      if V2.Y <> 0 then SlopeLeft := V2.X / V2.Y else SlopeLeft := 0;
      if V1.Y <> 0 then SlopeRight := V1.X / V1.Y else SlopeRight := 0;
    end;

//Pętla właściwa

  for Y := AP1.Y to AP3.Y - 1 do
    begin
      Start := Round(AP1.X + ((Y - AP1.Y) * SlopeLeft)); //Wyznacza początek linii
      Over := Round(AP1.X + ((Y - AP1.Y) * SlopeRight)); //Wyznacza koniec linii
      Form1.Canvas.MoveTo(Start, Y); //Rysowanie linii
      Form1.Canvas.LineTo(Over, Y); //Rysowanie linii
    end;
end;
0

No nie bardzo...To co pokazałeś działa ale z punktu widzenia optymalizacji jest skrajnie bez sensu i przeczy wszystkiemu co sam wcześniej napisałeś.

Przyczyną jest użycie w pętli głównej tego : Form1.Canvas.LineTo(Over, Y); //Rysowanie linii

Jak chcesz mieć algorytm optymalny to musisz go rysować pixel po pixelu a nie używać funkcji rysowania linii w głównej pętli.
Generalnie w algorytmie, który Ci przesłałem masz już wszystko łopatologicznie wyłożone. Nie ma w nim dzielenia ani liczb zmiennoprzecinkowych.
Musisz jedynie dodać obsługę przypadków tak by rysował linie także po osi X a nie tylko Y.

0

Ja we "właściwym" kodzie nie używam w ogóle żadnego dzielenia, ale po prostu nadal nie jestem zadowolony z wydajności, stąd ciągle szukam lepszych rozwiązań. Kod nie jest też jeszcze odpowiednio zoptymalizowany ani skończony (nie rysuje innych trójkątów niż te o płaskiej podstawie, od tego zawsze zaczynam bo to najprostsze, a do testów wydajności wystarczy). Resztę mam zamiar dopisać dopiero wtedy, gdy będę miał opracowaną właściwą bazę algorytmu, a do tego jeszcze nie doszedłem. To poniżej to zmodyfikowany przeze mnie Bresenham, który niestety jest tylko niewiele szybszy od algorytmu z dzieleniem przez floaty (czyli klasycznego algorytmu DDA).


TLine = record
  strict private
    type TUpdateX = procedure of Object;
    procedure UpdateXSingle; inline;
    procedure UpdateXMulti; inline;
  public
    P1, P2, Vector, VectorABS: TPoint;
    Step, Positive, Negative, D: NativeInt;
    X: NativeUInt;
    UpdateX: TUpdateX;
    procedure Analyse(const AStart, AEnd: TPoint); inline;
  end;

{Line - Update X Single}

procedure TLine.UpdateXSingle;
begin
  if D > 0 then
    begin
      Inc(X, Step);
      Inc(D, Positive);
    end else
      Inc(D, Negative);
end;

{Line - Update X Multi}

procedure TLine.UpdateXMulti;
begin
  Inc(X, Step);
  while D <= 0 do
    begin
      Inc(X, Step);
      Inc(D, Negative);
    end;
  Inc(D, Positive);
end;

{Line - Analyse}

procedure TLine.Analyse;
begin
  P1 := AStart;
  P2 := AEnd;
  X := P1.X;
  Vector := Point(P2.X - P1.X, P2.Y - P1.Y);
  VectorABS := Point(ABS(Vector.X), ABS(Vector.Y));
  if Vector.X > 0 then Step := 1 else
  if Vector.X < 0 then Step := -1 else
  Step := 0;

  if VectorABS.X > VectorABS.Y then
    begin
      Positive := (VectorABS.Y - VectorABS.X) * 2;
      Negative := VectorABS.Y * 2;
      D := Negative - VectorABS.X;
      UpdateX := UpdateXMulti;
      while D <= 0 do
        begin
          Inc(X, Step);
          Inc(D, Negative);
        end;
      Inc(D, Positive);
    end else
    begin
      Positive := (VectorABS.X - VectorABS.Y) * 2;
      Negative := VectorABS.X * 2;
      D := Negative - VectorABS.Y;
      UpdateX := UpdateXSingle;
    end;
end;

{Display - Draw Triangle}

procedure TDisplay.DrawTriangle;
var
  Left, Right: TLine;
  Y, X: NativeInt;
  P: ^Integer;

begin
  if AP1.Y > AP3.Y then Swap(AP1, AP3);
  if AP1.Y > AP2.Y then Swap(AP1, AP2);
  if AP2.Y > AP3.Y then Swap(AP2, AP3);

  if (AP1.Y < Resolution.Render.Height) and (AP3.Y >= 0) then
    begin
      {Flat Bottom}

      if (AP3.X - AP1.X) < (AP2.X - AP1.X) then
        begin //Long < Short
          Left.Analyse(AP1, AP3); //Left = Long
          Right.Analyse(AP1, AP2); //Right = Short
        end else
        begin //Short < Long
          Left.Analyse(AP1, AP2); //Left = Short
          Right.Analyse(AP1, AP3); //Right = Long
        end;

      {Proceed - Part 1}

      ThreadGate.Acquire;

      for Y := AP1.Y to AP3.Y - 1 do
        begin
          P := @Buffer.Color[(Y * Resolution.Render.Width) + Left.X];
          for X := Left.X to Right.X do
            begin
              P^ := AColor;
              Inc(P, 1);
            end;
          Left.UpdateX;
          Right.UpdateX;
        end;

      ThreadGate.Release;
    end;
0

I nie będziesz zadowolony :-)
Bo o algorytmach rysowania linii się prace magisterskie pisze, dostosowuje się je do rozdzielczości, głębi bitowej. Zamiast dzielenia stosuje się tablice z gotowymi wynikami ( precalculated table ).
Wówczas zamiast dzielenia wyciągasz dane z tabeli np.:

  dx := wynikiDzielenia [ dzielna, dzienik ]

Taka operacja zajmuje wówczas kilka taktów CPU i nie musisz używać ani DIV ani FDIV.

Kolejna sprawa, że takie rzeczy raczej pisze się w ASM a nie Delphi. Delphi nie zawsze dobrze zoptymalizuje warunki i pętle, które w ASM można ogarnąć jednym skokiem warunkowym.

0

I tak, i nie. Jak sobie robię testy rysowania linii (i tylko linii) to wtedy implementacja czystego Bresenhama daje poprawę wydajności nawet o 40% względem klasycznego DDA (czyli nawet w Delphi daje radę to osiągnąć). Niestety implementacja czystego Bresenhama nie nadaje się (moim zdaniem) do rysowania trójkątów, bo wtedy, tak jak opisałem w pierwszym poście, ruch musi następować zawsze w jednym kierunku Y + 1, a w czystym Bresenhamie kierunek jest zmienny, zależny od kąta nachylenia linii. Ja go zmodyfikowałem tak, że oś Y zawsze traktowana jest jako wiodąca, udało mi się też uniknąć w nim dzielenia, floatów i zaokrągleń... a mimo wszystko kod stracił większość swojej przewagi nad DDA (dobre 90%!). Próbowałem też napisać wersję, w której nie korzystam z dodatkowych struktur (rekord TLine) ani metod, tylko wszystko jest w kodzie głównej procedury, ale nic to nie dało (może jakieś 0.03% różnicy). Jeszcze nie jestem tego na 100% pewien, ale wstępne testy mi pokazały, że problem leży w tej części kodu, która wykorzystuje pętle while (patrz UpdateXMulti). Sądzę tak dlatego, że trójkąt, który obie osie Y ma naturalnie wiodące (a nie wymuszone przeze mnie) rysowany jest dużo szybciej (a on korzysta z UpdateXSingle). Zadziwia mnie to jednak, bo w tej części kodu nie ma według mnie niczego, co mogłoby ten efekt powodować, chyba za wyjątkiem pętli while, która jednak nie powinna kompilatorowi robić aż takiej różnicy.

0

Pomijając już wszystko wciąż nie kumam czy Ty chcesz narysować trójkąt wypełniony czy tylko krawędzie?
Kod, który dałeś rysuje trójkąt wypełniony.

Za dużo filozofujesz a kod masz na zdecydowanie zbyt wysokim poziomie abstrakcji.
Nie wiem w jaki sposób robisz testy ale w mojej ocenie większe obciążenie generuje wywoływanie funkcji i poruszanie się po abstrakcyjnych strukturach "jałowe skakanie" po kodzie niż efektywny algorytm. Pewnie coś czasem działa szybciej a coś wolniej jednak finalnie pewnie sam nie wiesz co porównujesz i czego czasy mierzysz. Włącz sobie w Debug'u podgląd CPU i zobacz ile syfu jest poza właściwym kodem, który rzeczywiście coś robi 60% to jałowe MOV'y pomiędzy rejestrami i adresami.

Zaimplementowałem algorytm samej linii. Bez float'ów i dzielenia - choć z tym dzieleniem zrobiłem też buforowane i prawie nic to nie zmienia. Zresztą to dzielenie w tym algorytmie to i tak pomijalna rzecz przy jego całej złożoności ono i tak wykonuje się raz na całą linię niezależnie od tego jak ją rysujesz. Dlatego nie rozumiem co się tak tego dzielenia uczepiłeś :-)
Zrobiłem trochę pomiarów getTickCountem i najwięcej czasu zajmuje wyliczenie adresu pamięci piksela i wstawianie jego wartości do bufora
( to 70% czasu całego algorytmu ).
Chodzi o wiersz:

  _PMScrD^[ x + si.widt * _d.intPart ]:= _ActiveColor ; // ( gdzie _PMScrD to pointer na bufor obrazu 32bit RGBA, si.width szerokość screen ).

Pod DOS używałem funkcji, która zwracała ilość taktów wykonanych przez CPU. Niestety pow Windows wcinają się inne procesy i dla tego samego kodu mogą wychodzić różne wyniki więc trzeba i tak operować przybliżeniami.

Z powyższego wynika, że szczypanie się o rysowanie 2 linii jednocześnie może by miało sens ale tylko wówczas gdybyś optymalnie zaimplementował w assemblerze główną pętlę rysującą. Wówczas być może zyskałbyś kolejne 5%-10% czasu ale wg. mnie to i tak nie ma większego sensu.

Krótki test algorytmu - wyniki:

rozdzielczość 320x200 / rysujemy 1 000 000 trójkątów / czas 0.9 sekundy - co daje ledwo 37 000 trójkątów na klatkę przy 25 klatek/s.
rozdzielczość 800x600 / rysujemy 1 000 000 trójkątów / czas 6.0 sekund

na procesorze i3-6100 3.7GHz

Trójkąty rysowane z wykorzystaniem poniższego algorytmu. Generowane są na obrazie z losowo zadanymi wierzchołkami w zakresie obszaru rysowania.
Wynik jak widać jest dramatyczny w porównaniu z GPU, które robi takich trójkątów w tym samym czasie pewnie miliard albo więcej ( czyli jest 1000 razy szybsze).
Przypuszczam, że przepisanie wszystkiego do czystego Assemblera, optymalnie przenosząc wszystkie operacje by wykonywały się na rejestrach, być może przyspieszyłoby algorytm 5-10 razy.
Taka zmiana i tak nie zmieni tego, że w porównaniu z GPU jesteśmy w głębokiej d... Myślę, że dalsze rozgryzanie tego tematu w dzisiejszych czasach raczej całkowicie mija się z celem chyba, że wciąż chcesz pisać demka na Amigę, 80x86 albo projektujesz nowy GPU ale to też się robi inaczej. Zresztą te wszystkie algorytmy w optymalnej postaci zostały już napisane prawie 30 lat temu i wystarczy je wyszukać w sieci.

screenshot-20200127004819.png


const
  _maxX = 1920 ;
  _maxY = 1200 ;

Type
  TScreen = array [ 0 .. _maxX*_maxY ] of Dword ;

Type
  // w zależności od architektury CPU big endian / little endian może być wymagana odwrotna kolejność zmiennych w strukturze.
  TVirtualFloat = record
    floatPart : int16 ;
    intPart : int16 ;
  end ;

Var
  Si : record 
    width:int32;
    height:int32;
  end ; // curr screen size

procedure FastTriangle(x1,y1,x2,y2,x3,y3:int32);
Begin
   FastLine(x1,y1,x2,y2);
   FastLine(x2,y2,x3,y3);
   FastLine(x3,y3,x1,y1);
End;

procedure FastLine(x1,y1,x2,y2:int32) ;
var
  b : int32;
  dx, dy, d, delta : int32 ;
  _d : TVirtualFloat absolute d ;
   x, y : int32 ;
Begin

  //
  // linia pionowa nic nie liczymy
  if x1 = x2 then
  begin
     if y1>y2 then begin b:=y2;y2:=y1;y1:=b;end;
     for y := y1 to y2 do
       _PMScrD^ [ x1 + si.width * y ] := _ActiveColor ;
     exit;
  end;

  //
  // linia pozioma nic nie liczymy
  if y1 = y2 then
  begin
     if x1>x2 then begin b:=x2;x2:=x1;x1:=b;end;
     for x := x1 to x2 do
       _PMScrD^ [ x + si.width * y1 ] := _ActiveColor ;
     exit;
  end;

  //
  // wyliczamy długość i wysokość linii
  dx := x2 - x1 ;
  dy := y2 - y1 ;

  if ( abs ( dx ) < abs ( dy ) ) then begin // jeśli wyższa niż dłuższa
    //
    // układamy punkty tak by y1 był u góry
    // zamianę można zastąpić dwoma przypadkami pętli z odwróconą równością
    // i dekrementacją zamiast inkrementacji 6 taktów zysku
    if ( y1 > y2 ) then begin
      b := x1; x1 := x2; x2 := b;
      b := y1; y1 := y2; y2 := b;
    end;

    if ( y2<>y1 ) then delta := divArray [ dx , dy ] ;
    //if ( y2<>y1 ) then delta := ( dx shl 16 ) div dy ;

    y := y1;
    d := x1 shl 16;
    while ( y < y2 ) do
    begin
      _PMScrD^[ _d.intPart + si.width * y ]:= _ActiveColor ;
      inc ( y ) ;
      d := d + delta ;
    end;

  end else begin // jeśli dłuższa niż wyższa

    //
    // układamy punkty tak by y1 był u góry
    // zamianę można zastąpić dwoma przypadkami pętli z odwróconą równością
    // i dekrementacją zamiast inkrementacji 6 taktów zysku
    if ( x1 > x2 ) then begin
      b := x1; x1 := x2; x2 := b;
      b := y1; y1 := y2; y2 := b;
    end;

    if ( x2<>x1 ) then delta := divArray [ dy, dx ] ;
    //if ( y2<>y1 ) then delta := ( dy shl 16 ) div dx ;

    x := x1;
    d := y1 shl 16 ;
    while ( x < x2 ) do
    begin
      _PMScrD^[ x + si.width * _d.intPart ]:= _ActiveColor ;
      inc ( x );
      d := d + delta ;
    end;

  end;

End;

Do poczytania:

http://www.edepot.com/algorithm.html
https://mikro.naprvyraz.sk/docs/Coding/1/NEWLINE.TXT

0

A jeszcze odnosząc się do Twojego kodu. Może i dzielenia zlikwidowałeś ale kod ma straszną złożoność zbędna pętla w pętli a z każdą pętlą wiąże się instrukcja warunkowa. Spójrz na fragment odpowiadający już za rysowanie:

     for Y := AP1.Y to AP3.Y - 1 do // pętla główna i warunek.
        begin
          P := @Buffer.Color[(Y * Resolution.Render.Width) + Left.X];
          for X := Left.X to Right.X do // pętla rysowania linii musi być więc można warunek olać ... 
            begin
              P^ := AColor;
              Inc(P, 1);
            end;
          Left.UpdateX; // implementacja tej funkcji zawiera pętlę i warunek
          Right.UpdateX; // implementacja tej funkcji także zawiera pętlę i warunek
        end;

W głównej pętli wykonujesz dwukrotnie funkcje UpdateX oraz UpdateY, w których w środku są kolejne pętle. Porażka.
Spójrz na mój kod odpowiadający za tą samą czynność:

  while ( y < y3 ) do
  Begin
    line( _xl1.intPart, y, _xl2.intPart, y ) ; // wewnątrz pętla rysowania linii musi być więc można warunek olać ... 
                                               // W dobrej optymalizacji rysowanie linii poziomej jest bez pętli
                                               // i polega na kopiowaniu obszaru pamięci co jest bardzo opłacalne przy rysowaniu dużych obszarów.


    y := y + 1 ;
    xl1 := xl1 + dx23 ;
    xl2 := xl2 + dx13 ;
  End;

Jest jedynie dodawanie liczb całkowitych i jeden warunek pętli, który docelowo w ASM optymalizujemy do skoku JZ ( jeśli zero ).

0

Odnosząc się do algorytmu rysowania trójkąta i wyznaczania jego krawędzi ma znaczenie czy rysujesz trójkąt wypełniony czy jedynie jego krawędzie.

Tylko w przypadku gdy rysujesz trójkąt wypełniony metoda o której pisałeś wczoraj o godz.17:30 znajdzie zastosowanie.
Jeśli chcesz narysować tylko krawędzie trójkąta to ten algorytm już nie zadziała.

Swoją drogą to pytanie, które zadaję Ci od pierwszego posta a Ty ciągle nie udzieliłeś na nie odpowiedzi. I nie wiem czy Twoim celem jest narysować trójkąt wypełniony czy tylko jego krawędzie.

Jeśli celem jest narysowanie trójkąta wypełnionego to optymalny algorytm i dużo szybszy od twojej propozycji - zamieściłem wczoraj jako post z godz. 19:17.

Czyli ten:
Zawiera po góra dwa dzielenia całkowite na cały trójkąt. Optymalizacje, które należałby zastosować to:

  • Zamiana rysowania lnii na najlepiej assembler'owe wypełnianie bufora obrazu. Ty robisz to for'em i przesuwasz pointer - od biedy może tak być jednak wypełnianie z poziomu ASM byłoby szybsze. np:
;Procedura rysujace pozioma linie
Linia	PROC
	mov	ax,y		;\
	xchg	ah,al		; \
	mov	y,ax		;  >mnozenie wspolrzednej
	shr	ax,2		;  >y przez 320
	add	y,ax		; /
	mov	cx,xl2		;/
	sub	cx,xl1		;oblicz dlugosc linii
	mov	di,y
	add	di,xl1		;oblicz offset poczatku linii
	mov	ax,color
	cld
	rep	stosb		;rysuj linie
	ret
Linia	ENDP
  • Można jeszcze zamienić dzielenie na pre-kalkulowaną tablicę jaką zastosowałem w algorytmie rysowania krawędzi trójkąta/linii czyli :
    if ( x2<>x1 ) then delta := divArray [ dy, dx ] ; // odczyt z gotowej tablicy z wynikami
    // zamiast dzielenia if ( y2<>y1 ) then delta := ( dy shl 16 ) div dx ;

Jednak jak już wcześniej napisałem w ogólnym czasie wykonywania całego algorytmu ma to mały sens. Chyba, że będziesz się koncentrował na rysowaniu wielu bardzo małych trójkątów a nie statystycznie losowych - wówczas warto to rozważyć.


type
  TVirtualFloat = record
    floatPart : int16 ;
    intPart : int16 ;
  end ;
  // w zależności od architektury CPU big endian / little endian może być wymagana odwrotna kolejność zmiennych w strukturze.

function TriangleFilledFast ( x1,y1,x2,y2,x3,y3:int32 ) : integer ;

var
  z, dx12, dx13, dx23, x, y, xl1, xl2 : int32 ;
  _xl1  : TVirtualFloat absolute xl1 ; // zmienna _x11 jest umiejscowiona pod tym samym adresem co x11
  _xl2  : TVirtualFloat absolute xl2 ; // zmienna _x12 jest umiejscowiona pod tym samym adresem co x12

begin

  //
  // Sortowanie wierzchołków po osi Y
  //
  if ( y1 > y2 ) then begin
    z:=x1; x1:=x2; x2:=z;
    z:=y1; y1:=y2; y2:=z;
  end;

  if ( y2 > y3 ) then begin
    z:=x2; x2:=x3; x3:=z;
    z:=y2; y2:=y3; y3:=z;
  end;

  if ( y1 > y2 ) then begin
    z:=x1; x1:=x2; x2:=z;
    z:=y1; y1:=y2; y2:=z;
  end;


  //
  // Wyliczanie współczynników dla wszystkich trzech boków trójkąta
  //
  if ( y2<>y1 ) then dx12 := ( ( x2 - x1 ) shl 16 ) div ( y2 - y1 ) ;
  if ( y3<>y1 ) then dx13 := ( ( x3 - x1 ) shl 16 ) div ( y3 - y1 ) ;
  if ( y3<>y2 ) then dx23 := ( ( x3 - x2 ) shl 16 ) div ( y3 - y2 ) ;

  y := y1;
  x := x1;
  xl1 := x shl 16; // bo xl1 i xl2 jest pseudo-zmiennoprzecinkowe
  xl2 := xl1 ;
  //
  // rysujemy pierwszą górną część trójkąta ( jeśli jest )
  //
  while ( y < y2 ) do
  Begin
    line ( _xl1.intPart, y, _xl2.intPart, y );
    y := y + 1 ;
    xl1 := xl1 + dx12 ;
    xl2 := xl2 + dx13 ;
  End;

  y := y2;
  xl1 := x2 shl 16; // bo xl1 jest pseudo-zmiennoprzecinkowe
  //
  // rysujemy drugą dolną część trójkąta ( jeśli jest )
  //
  while ( y < y3 ) do
  Begin
    line( _xl1.intPart, y, _xl2.intPart, y ) ;
    y := y + 1 ;
    xl1 := xl1 + dx23 ;
    xl2 := xl2 + dx13 ;
  End;

End;

0
katakrowa napisał(a):

Odnosząc się do algorytmu rysowania trójkąta i wyznaczania jego krawędzi ma znaczenie czy rysujesz trójkąt wypełniony czy jedynie jego krawędzie.

Jeśli chcesz narysować tylko krawędzie trójkąta to ten algorytm już nie zadziała.

Wiem, ale ja się zajmuję rasteryzacją, same krawędzie mnie nie interesują (od tego mam inne algorytmy).

Swoją drogą to pytanie, które zadaję Ci od pierwszego posta a Ty ciągle nie udzieliłeś na nie odpowiedzi. I nie wiem czy Twoim celem jest narysować trójkąt wypełniony czy tylko jego krawędzie.

Napisałem w pierwszym poście, że piszę software'ową rasteryzację trójkąta, co powinno stanowić odpowiedź samą w sobie.

  • Zamiana rysowania lnii na najlepiej assembler'owe wypełnianie bufora obrazu. Ty robisz to for'em i przesuwasz pointer - od biedy może tak być jednak wypełnianie z poziomu ASM byłoby szybsze.

Zapewne, ale jak już pisałem, nie znam ASM i w godzinę się go nie nauczę. Póki co, chcę skończyć to co robię.

Chyba, że będziesz się koncentrował na rysowaniu wielu bardzo małych trójkątów a nie statystycznie losowych - wówczas warto to rozważyć.

Nie wiadomo, to jest silnik 3D i będzie rysować to, czego dana scena akurat będzie wymagać.

1
Crow napisał(a):

Nie wiadomo, to jest silnik 3D i będzie rysować to, czego dana scena akurat będzie wymagać.

Właśnie dlatego warto mieć w ramach silnika zaimplementowane różne algorytmy i w zależności od tego co rysujesz użyć odpowiedniego.
Nie ma jednego super optymalnego algorytmu rysującego trójkąty wypełnione, teksturowane, z cieniowaniem Gourauda, uwzględniające oświetlenie itp..itd ...
Do każdego jest inny algorytm.
Zabieranie się za pisanie software'owego silnika 3D bez assebler'a nie idzie w parze z optymalnym efektem końcowym.

p.s.
W załączniku praca magisterska od kolegi ze studiów na temat grafiki 3D oraz powiązane z nią przykłady w C++.
Na etapie początku zabawy z pisaniem własnego silnika 3D ma bardzo przejrzyste przykłady i świetnie omówioną teorię.

0

I jeszcze taka "rada" skoro z jakiegoś powodu nie chcesz użyć gotowych istniejących w sieci rozwiązań to olej na chwilę czytanie cudzych algorytmów, weź kartkę długopis i linijkę i wiedząc już to co wiesz ( a naczytałeś się już wg mnie wystarczająco ) spróbuj napisać taki algorytm po swojemu. Matematyka jest jedna więc nowego koła nie wymyślisz a pomoże Ci to lepiej zrozumieć problem. Bo teraz tak skaczesz z punktu do punktu bez wyraźnego celu. Jak jak pisałem bawiłem się tym ponad 20 lat temu i dzisiaj już nawet nieszczególnie chce mi się to wszystko od nowa analizować.

0

Kod do optymalizacji pozbawiony problemu "połówek pixeli"


function FilledTriangle(x1,y1,x2,y2,x3,y3:double):integer;
Var
  z,dx12,dx13,dx23,x,y,xl1,xl2,xl3:double;
  a,xb1,xb2,xx,yy:word;
Begin
     y1:=trunc(y1);y2:=trunc(y2);y3:=trunc(y3);
     if (y1>y2) then Begin
                         z:=x1;x1:=x2;x2:=z;
                         z:=y1;y1:=y2;y2:=z;
                 End;
     if (y2>y3) then Begin
                         z:=x2;x2:=x3;x3:=z;
                         z:=y2;y2:=y3;y3:=z;
                 End;
     if (y1>y2) then Begin
                         z:=x1;x1:=x2;x2:=z;
                         z:=y1;y1:=y2;y2:=z;
                 End;
     if (y2<>y1) then dx12:=(x2-x1)/(y2-y1);
     if (y3<>y1) then dx13:=(x3-x1)/(y3-y1);
     if (y3<>y2) then dx23:=(x3-x2)/(y3-y2);
     y:=y1;x:=x1;xl1:=x;xl2:=x;
     while (y<y2)do
     Begin
       xb1:=trunc(xl1+0.5);
       xb2:=trunc(xl2+0.5);
       if xb1>xb2 then
        begin
         a:=xb2;
         xb2:=xb1;
         xb1:=a;
        end;
       if xb2>si.Width then xb2:=si.Width-1;
       if xb1<0 then xb2:=0;
       if (y>=0)and(y<si.height)then
       for xx:=xb1 to xb2 do
       begin
          _PMScrD^[xx+si.width*(si.height-trunc(y+0.5))]:=_ActiveColor;
       end;
       y:=y+1;
       xl1:=xl1+dx12;
       xl2:=xl2+dx13;
     End;
     y:=y2;xl1:=x2;
     while(y<y3)do
     Begin
       xb1:=trunc(xl1+0.5);
       xb2:=trunc(xl2+0.5);
       if xb1>xb2 then
        begin
         a:=xb2;
         xb2:=xb1;
         xb1:=a;
        end;
       if xb2>si.Width then xb2:=si.Width-1;
       if xb1<0 then xb2:=0;
       if (y>=0)and(y<si.height)then
       for xx:=xb1 to xb2 do
       begin
          _PMScrD^[xx+si.width*(si.height-trunc(y+0.5))]:=_ActiveColor;
       end;
       y:=y+1;
       xl1:=xl1+dx23;
       xl2:=xl2+dx13;
     End;

End;

0

Niedokładność w algorytmie bez float'ów wynika z uproszczonego zaokrąglania liczb liczb zmiennoprzecinkowych emulowanych na integer'ach.
Używam trunc() zamiast round().
Natomiast na potrzeby grafiki można wyjść z założenia, że round ( x ) = trunc ( x + 0.5 )
Uwaga: nie można wyjść z takiego założenia w programach księgowych. w grafice to także może przełożyć się na pojedyncze błędy w przypadku gdy ktoś będzie łączył algorytmy używające różne metody zaokrąglania.

Chodzi o ten fragment:


Type
  // w zależności od architektury CPU big endian / little endian może być wymagana odwrotna kolejność zmiennych w strukturze.
  TVirtualFloat = record
    floatPart : int16 ;
    intPart : int16 ;
  end ;

...

line ( _xl1.intPart, y, _xl2.intPart, y ); // to powinna być funkcja round a nie trunc jak jest obecnie

aby uzyskać round(), kosztem czasu można by zrobić tak



var bufx1 =  ;
     _bufx1 :TVirtualFloat absolute bufx1 ;


begin
  (...)
  bufx1 := xl1 + 32767 ; ( odpowiednik x1 +0.5 na floatach )
  line ( **_bufx1.intPart**, y, _xl2.intPart, y ); // to powinna być funkcja round a nie trunc jak jest obecnie

0

I jeszcze tak podsumowując całokształt działań do których dążysz i na które zapewne za chwilę się natkniesz podczas "robienia" szeroko rozumianego silnika 3D.
Chodzi o zdefiniowanie ogólnych założeń przed rozpoczęciem prac programistycznych. Zignorowanie tego etapu zawsze odbija się podczas późniejszego implementowania rozwiązań.

Takie najważniejsze elementy ( o których pamiętam to ):

  • konsekwentne budowanie modeli lewo lub prawo-skrętnych by później nie mieć kłopot z wyznaczaniem kierunku ściany ( wektora normalnego ) ;
  • w ramach całego projektu używanie tych samych funkcji trygonometrycznych ( sin, cos, tan itp... ) ;
  • dobrze jest ustalić jedną metodę zaokrąglania liczb ( różne biblioteki mogą to robić różnie );
  • czasem opłaca się bufor ekranu trzymać jako 24 bitowy(RGB) zamiast 32 (choć przy dzisiejszych procesorach >32bit to nie ma już sensu). W kodzie pod DOS miało to jednak znaczenie;
  • przy animacjach ruszamy światem a nie latamy kamerą po świecie ( bo przy dużych odległościach od środka układu zaczynają się kończyć możliwości floatów );
  • programowanie teksturowania bez korekcji perspektywy właściwie mija się z celem ;
  • przyjąć wspólną podstawę dla wszystkich algorytmów określającą czy obliczenia robimy względem środka pixela czy któregoś z jego rogów ( innymi słowy czy współrzędna 0,0 to lewy górny róg ekranu czy środek pierwszego piksel czy być może prawy dolny róg pierwszego pixela ). Bez tego założenia, definicji zaokrągleń mamy spore szanse, ze na łączeniu trójkątów będą pokazywały się "szczeliny".

Pewnie jeszcze kilka by się znalazło ale już nie pamiętam.

0

To nie tak, że ja nie chcę korzystać z gotowych rozwiązań. A w sieci owszem, można poczytać o algorytmach, które do rasteryzacji stosowano dawniej, a także o tych, których używa się obecnie, ale większość robi to poglądowo i bardzo skrótowo, na zasadzie: dziś to wszystko robi to za nas GPU, więc nie warto się w to specjalnie zagłębiać. A jak na ironię gotowych implementacji nie podaje nikt albo podają te stosowanie przez GPU, które dla CPU się nie nadają (np. z wykorzystaniem współrzędnych barycentrycznych i funkcji krawędziowej, bardzo dokładny i łatwy w implementacji algorytm, ale dla CPU za wolny).

Chyba w 5 różnych źródłach wyczytałem, że do software'owej rasteryzacji trójkąta najlepiej użyć Bresenhama (co według autorów jest banalne...), ale cholera jakoś nikt nie przedstawia tego w formie gotowego kodu albo chociaż pseudo-kodu! Bresenham to nic innego, jak zmodyfikowana wersja funkcji liniowej. Pozwala na dokładne i szybkie wyliczanie współrzędnych piksela, ale tylko dla tej dłuższej osi. Jeżeli np. X > Y, to wtedy obliczenie Y jest łatwe, bo dla każdego X istnieje dokładnie jedno rozwiązanie i jeden Y. Gdyby natomiast chcieć w takiej sytuacji liczyć X, to funkcja liniowa się wysypie, bo dla jednego Y istnieje potencjalnie kilka różnych X.

Oczywiście można zrobić tak, że najpierw analizujemy w pętli pierwszą linię, potem drugą, a gdy już obie mamy zmapowane, lecimy wzdłuż nich i rysujemy trójkąt. No ale to jest koszmarnie nieefektywne (trzeba tworzyć mapy pikseli, a zamiast 1 pętli, mamy 3).

0
Crow napisał(a):

A w sieci owszem, można poczytać o algorytmach, które do rasteryzacji stosowano dawniej, a także o tych, których używa się obecnie, ale większość robi to poglądowo i bardzo skrótowo, na zasadzie: dziś to wszystko robi to za nas GPU, więc nie warto się w to specjalnie zagłębiać.

Hmm... myślę, że nie przyłożyłeś się do poszukiwań a zamiast rzeczywiście sięgnąć po twardą teorię i zrozumieć temat "ślizgasz" się powierzchownie w poszukiwaniu Złotego Grall'a.

http://math.hws.edu/eck/cs424/downloads/graphicsbook-linked.pdf
http://read.pudn.com/downloads151/ebook/655333/3DGameEngineArchitecture.pdf
http://www.sunshine2k.de/coding/java/TriangleRasterization/TriangleRasterization.html
https://www.scratchapixel.com/lessons/3d-basic-rendering/rasterization-practical-implementation/rasterization-stage
https://www.digipen.edu/sites/default/files/public/docs/theses/salem-haykal-digipen-master-of-science-in-computer-science-thesis-an-optimized-triangle-rasterizer.pdf
https://www.uni-obuda.hu/journal/Mileff_Nehez_Dudra_63.pdf
https://fgiesen.wordpress.com/2013/02/10/optimizing-the-basic-rasterizer/
https://github.com/scheff173/NoGL3dDemo
http://www.hugi.scene.org/online/coding/hugi%2017%20-%20cotriang.htm
http://www.cs.mun.ca/av/old/teaching/cg/notes/raster_poly.pdf
http://0x80.pl/articles/fillpolygon.html
https://docplayer.pl/4809088-Grafika-komputerowa-i-przemyslaw-kiciak-przemek-mimuw-edu-pl-http-www-mimuw-edu-pl-przemek.html

https://amigasourcecodepreservation.gitlab.io/amiga-real-time-3d-graphics/

Nie wspomnę o tym, że możesz bez trudu przeanalizować kod jednych z najlepszych na świecie w tej dziedzinie pobierając kod DOOM'a czy QUAKE'a
albo https://github.com/collections/game-engines

0
Crow napisał(a):

Fajnie, że linkujesz mi źródła, z których od dawna sam korzystam. Teraz bądź tak dobry i posługując się tymi linkami, wklej mi kod albo pseudo-kod algorytmu, o którym cały czas tutaj piszę. Nie ma? Oj, czy to znaczy, że tylko pobieżnie przeleciałeś się po tych linkach, ale nawet nie zadałeś sobie trudu by przeczytać, co jest w nich napisane?

Czytając Twoje wypowiedzi szczerze wątpię, że wystarczająco zapoznałeś się z tematyką bo gdybyś to zrobił to byś potrafił to samodzielnie napisać.
Co do napisania kodu, wszystko masz jak na dłoni wystarczy wyciągnąć wnioski i po swojemu do swoich potrzeb zaimplementować.
Odpowiedzi na wszystkie pytania niezbędne do togo co chcesz zrobić masz w tym wątku dostępne.

Jeśli jednak bardzo chcesz bym to napisał proszę dokładne informacje jakie są dokładnie wymagania dla tej funkcji ( co na wejściu, czym jest bufor, w którym rysujemy ) na jakiej platformie ma działać i w ostatecznie w jakim języku ma być napisane. Przeanalizuję i prześlę ofertę na napisanie takiego programu.

1 użytkowników online, w tym zalogowanych: 0, gości: 1