Cyfrowy analizator różnicowy (algorytm graficzny)

W grafice komputerowej cyfrowy analizator różnicowy ( DDA ) to sprzęt lub oprogramowanie używane do interpolacji zmiennych w przedziale między punktem początkowym a końcowym. DDA służą do rasteryzacji linii, trójkątów i wielokątów. Można je rozszerzyć na funkcje nieliniowe, takie jak mapowanie tekstur z poprawną perspektywą , krzywe kwadratowe i woksele przechodzące .

W swojej najprostszej implementacji dla przypadków liniowych, takich jak linie , algorytm DDA interpoluje wartości w przedziale, obliczając dla każdego x _i równania x _i = x _i−1 + 1, y _i = y _i−1 + m, gdzie m jest nachylenie linii. Nachylenie to można wyrazić w DDA w następujący sposób:

Displaystyle m = {\ Frac {y_ {\ rm {koniec}} -y _ {\ rm {początek}} }{x_{\rm {koniec}}-x_{\rm {początek}}}}}

W rzeczywistości dowolne dwa kolejne punkty leżące na tym odcinku powinny spełniać równanie.

Wydajność

Metodę DDA można zaimplementować za pomocą arytmetyki zmiennoprzecinkowej lub liczb całkowitych . Natywna implementacja zmiennoprzecinkowa wymaga jednej operacji dodawania i zaokrąglania dla każdej interpolowanej wartości (np. współrzędnej x, y, głębokości, składowej koloru itp.) i wyniku wyjściowego. Ten proces jest wydajny tylko wtedy, gdy dostępny będzie FPU z szybkim dodawaniem i operacjami zaokrąglania.

Operacja stałoprzecinkowa na liczbach całkowitych wymaga dwóch dodań na cykl wyjściowy, aw przypadku przepełnienia części ułamkowej jednego dodatkowego przyrostu i odejmowania. Prawdopodobieństwo przepełnienia części ułamkowych jest proporcjonalne do stosunku m interpolowanych wartości początkowych/końcowych.

DDA dobrze nadają się do implementacji sprzętowej i mogą być przesyłane potokowo w celu zmaksymalizowania przepustowości.

Algorytm

Liniowy DDA zaczyna się od obliczenia mniejszego z dy lub dx dla przyrostu jednostki drugiego. Linia jest następnie próbkowana w odstępach jednostkowych w jednej współrzędnej, a odpowiednie wartości całkowite najbliższe ścieżce linii są określane dla drugiej współrzędnej.

Biorąc pod uwagę linię o dodatnim nachyleniu, jeśli nachylenie jest mniejsze lub równe 1, próbkujemy w odstępach jednostkowych x (dx=1) i obliczamy kolejne wartości y jako

{\ Displaystyle y_ {k + 1} = y_ {k} + m}

{\ Displaystyle x_ {k + 1} = x_ {k} + 1}

Indeks dolny k przyjmuje wartości całkowite, zaczynając od 0, dla pierwszego punktu i wzrasta o 1, aż do osiągnięcia punktu końcowego. Wartość y jest zaokrąglana do najbliższej liczby całkowitej, aby odpowiadała pikselowi ekranu.

Dla linii o nachyleniu większym niż 1 odwracamy rolę x i y tj. pobieramy próbkę przy dy=1 i obliczamy kolejne wartości x jako

{\ Displaystyle x_ {k + 1} = x_ {k} + {\ Frac {1} {m}}}

{\ Displaystyle y_ { k+1}=y_{k}+1}

Podobne obliczenia są przeprowadzane w celu określenia pozycji pikseli wzdłuż linii o ujemnym nachyleniu. Tak więc, jeśli wartość bezwzględna nachylenia jest mniejsza niż 1, ustawiamy dx = 1, jeśli ${\ Displaystyle x _ {\ rm {początek} <x_ {\ rm {koniec} }}$ tzn. skrajny punkt początkowy znajduje się po lewej stronie.

Program

Algorytm DDA Program w Turbo C++:

 
 
 
 
 

  

   
   
    
       
       
    
  
    
      
    
      
  
      
      
     
      
  
      
      
      
    
    
    
      
      
        
        
        
    
  
  
  
 #include  <grafika.h>  #include  <iostream.h>  #include  <math.h>  #include  <dos.h>  #include  <conio.h>  void  main  (  )  {  float  x  ,  float  y  ,  float  x1  ,  y1  ,  float  x2  ,  y2  ,  dx  ,  dy  ,  krok  ;  int  ja  ,  gd  =  WYKRYJ  ,  gm  ;  initgraph  (  &  gd  ,  &  gm  ,  "C:  \\  TURBOC3  \\  BGI"  );  cout  <<  "Podaj wartosc x1 i y1: "  ;  cin  >>  x1  >>  y1  ;  cout  <<  "Podaj wartosc x2 i y2: "  ;  cin  >>  x2  >>  y2  ;  dx  =  (  x2  -  x1  );  dy  =  (  y2  -  y1  );  if  (  abs  (  dx  )  >=  abs  (  dy  ))  krok  =  abs  (  dx  );  inaczej  krok  =  abs  (  dy  );  dx  =  dx  /  krok  ;  dy  =  dy  /  krok  ;  x  =  x1  ;  y  =  y1  ;  ja  =  1  ;  while  (  i  <=  krok  )  {  putpixel  (  x  ,  y  ,  5  );  x  =  x  +  d x  ;  y  =  y  +  dy  ;  ja  =  ja  +  1  ;  opóźnienie  (  100  );  }  pobierz  ();  wykres zamknięty  ();  }

Zobacz też

Algorytm linii Bresenhama to algorytm renderowania linii.
Algorytm błędu przyrostowego
Algorytm liniowy Xiaolin Wu jest algorytmem antyaliasingu liniowego

http://www.museth.org/Ken/Publications_files/Museth_SIG14.pdf

Alan Watt: Grafika komputerowa 3D , wydanie 3 2000, s. 184 (Rasteryzacja krawędzi). ISBN 0-201-39855-9