Algorytm Cohena-Sutherlanda

W grafice komputerowej algorytm Cohena -Sutherlanda jest algorytmem używanym do obcinania linii . Algorytm dzieli dwuwymiarową przestrzeń na 9 regionów, a następnie efektywnie określa linie i fragmenty linii, które są widoczne w centralnym obszarze zainteresowania (rzutnia ) .

Algorytm został opracowany w 1967 roku podczas pracy na symulatorze lotu przez Danny'ego Cohena i Ivana Sutherlanda .

Algorytm

Algorytm obejmuje, wyklucza lub częściowo uwzględnia linię na podstawie tego, czy:

Oba punkty końcowe znajdują się w obszarze rzutni (bitowe LUB punktów końcowych = 0000): akceptacja trywialna .
Oba punkty końcowe mają co najmniej jeden niewidoczny region, co oznacza, że linia nie przecina widocznego obszaru. (bitowe ORAZ punktów końcowych ≠ 0000): trywialne odrzucenie .
Oba punkty końcowe znajdują się w różnych regionach: w przypadku tej nietrywialnej sytuacji algorytm znajduje jeden z dwóch punktów, który znajduje się poza obszarem rzutni (będzie co najmniej jeden punkt na zewnątrz). Następnie obliczane jest przecięcie punktu końcowego i rozszerzonej granicy rzutni (tj. za pomocą równania parametrycznego dla linii) i ten nowy punkt zastępuje punkt końcowy. Algorytm powtarza się, dopóki nie nastąpi trywialna akceptacja lub odrzucenie.

Liczby na poniższym rysunku nazywane są outcodes . Outcode jest obliczany dla każdego z dwóch punktów w linii. Outcode będzie miał 4 bity dla obcinania dwuwymiarowego lub 6 bitów w przypadku trójwymiarowego. Pierwszy bit jest ustawiony na 1, jeśli punkt znajduje się nad rzutnią. Bity w kodzie wyjściowym 2D reprezentują: górę, dół, prawą, lewą stronę. Na przykład kod wyjściowy 1010 reprezentuje punkt znajdujący się w prawym górnym rogu rzutni.

	lewy	centralny	Prawidłowy
szczyt	1001	1000	1010
centralny	0001	0000	0010
spód	0101	0100	0110

Należy pamiętać, że kody wyjściowe dla punktów końcowych muszą być ponownie obliczane w każdej iteracji po wystąpieniu obcinania.

Algorytm Cohena-Sutherlanda można zastosować tylko w przypadku prostokątnego okna klipu .

Przykładowa implementacja C/C++

  

    0 
       
      
     
        






    

	     

	              
		  
	          
		  
	              
		  
	          
		  

	 





        

	
	    
	    
	   

	  
		    
			
			  
			
		      
			
			
			
		  
			
			
			  

			
			         

			
			
			
			
			
			
			
			               
				              
				  
			       
				              
				  
			        
				              
				  
			         
				              
				  
			

			
			
			    
				  
				  
				   
			  
				  
				  
				   
			
		
	
	 
 typedef  int  OutCode  ;  const  int  WEWNĄTRZ  =  ;  // 0000  const  int  LEFT  =  1  ;  // 0001  const  int  PRAWY  =  2  ;  // 0010  const  int  BOTTOM  =  4  ;  // 0100  const  int  TOP  =  8  ;  // 1000  // Oblicz kod bitowy dla punktu (x, y) używając prostokąta klipu  // ograniczonego po przekątnej przez (xmin, ymin) i (xmax, ymax)  // ZAKŁADAJ, ŻE xmax, xmin, ymax i ymin są stałe globalne.  OutCode  Oblicz OutCode  (  podwójne  x  ,  podwójne  y  )  {  OutCode  code  =  WEWNĄTRZ  ;  // inicjalizowany jako znajdujący się wewnątrz okna klipu  if  (  x  <  xmin  )  // na lewo od  kodu okna klipu   |=  LEWO  ;  else  if  (  x  >  xmax  )  // na prawo od  kodu okna klipu   |=  PRAWO  ;  if  (  y  <  ymin  ) // poniżej   kodu  okna klipu  |=  BOTTOM  ;  else  if  (  y  >  ymax  ) // nad   kodem  okna klipu  |=  TOP  ;  kod  powrotu  ;  }  // Algorytm obcinania Cohena-Sutherlanda przycina linię od  // P0 = (x0, y0) do P1 = (x1, y1) do prostokąta o przekątnej  // od (xmin, ymin) do (xmax, ymax).  bool  CohenSutherlandLineClip  (  double  &  x0  ,  double  &  y0  ,  double  &  x1  ,  double  &  y1  )  {  // oblicz kody wyjściowe dla P0, P1 i dowolnego punktu leżącego poza prostokątem klipu  OutCode  outcode0  =  ComputeOutCode  (  x0  ,  y0  );  OutCode  outcode1  =  ComputeOutCode  (  x1  ,  y1  );  bool  zaakceptuj  =  fałsz  ;  while  (  true  )  {  if  (  !  (  outcode0  |  outcode1  ))  {  // bitowe OR wynosi 0: oba punkty wewnątrz okna; trywialnie zaakceptuj i wyjdź z pętli   accept  =  true  ;  przerwa  ;  }  else  if  (  outcode0  &  outcode1  )  {  // bitowe AND nie jest równe 0: oba punkty dzielą strefę zewnętrzną (LEWĄ, PRAWĄ, GÓRNĄ,  // lub DOLNĄ), więc oba muszą znajdować się na zewnątrz okna; pętla wyjściowa (accept jest fałszywy)   break  ;  }  else  {  // obydwa testy nie powiodły się, więc oblicz segment linii do przycięcia  // od punktu zewnętrznego do przecięcia z krawędzią przycięcia  double  x  ,  y  ;  // Przynajmniej jeden punkt końcowy znajduje się poza prostokątem klipu; Weź to.   OutCode  outcodeOut  =  outcode1  >  outcode0  ?  outcode1  :  outcode0  ;  // Teraz znajdź punkt przecięcia;  // użyj wzorów:  // nachylenie = (y1 - y0) / (x1 - x0)  // x = x0 + (1 / nachylenie) * (ym - y0), gdzie ym to ymin lub ymax  // y = y0 + nachylenie * (xm - x0), gdzie xm to xmin lub xmax  // Nie trzeba się martwić dzieleniem przez zero, ponieważ w każdym przypadku //  testowany bit outcode gwarantuje, że mianownik jest niezerowy,  jeśli  (  outcodeOut  &  TOP  )  {  // punkt znajduje się nad oknem klipu  x  =  x0  +  (  x1  -  x0  )  *  (  ymax  -  y0  )  /  (  y1  -  y0  );  y  =  ymaks  ;  }  else  if  (  outcodeOut  &  BOTTOM  )  {  // punkt znajduje się poniżej okna klipu  x  =  x0  +  (  x1  -  x0  )  *  (  ymin  -  y0  )  /  (  y1  -  y0  );  y  =  ymin  ;  }  else  if  (  outcodeOut  &  RIGHT  )  {  // punkt znajduje się na prawo od okna klipu  y  =  y0  +  (  y1  -  y0  )  *  (  xmax  -  x0  )  /  (  x1  -  x0  );  x  =  xmaks  ;  }  else  if  (  outcodeOut  &  LEFT  )  {  // punkt znajduje się na lewo od okna klipu  y  =  y0  +  (  y1  -  y0  )  *  (  xmin  -  x0  )  /  (  x1  -  x0  );  x  =  x min  ;  }  // Teraz przesuwamy się od punktu zewnętrznego do punktu przecięcia,  // aby przyciąć i przygotować się do następnego podania.  if  (  outcodeOut  ==  outcode0  )  {  x0  =  x  ;  y0  =  y  ;  outcode0  =  ComputeOutCode  (  x0  ,  y0  );  }  jeszcze  {  x1  =  x  ;  y1  =  y  ;  outcode1  =  ComputeOutCode  (  x1  ,  y1  );  }  }  }  powrót  zaakceptuj  ;  }

Notatki

Zobacz też

Algorytmy używane w tym samym celu:

Jamesa D. Foleya. Grafika komputerowa: zasady i praktyka . Addison-Wesley Professional, 1996. s. 113.

Linki zewnętrzne