Cohen–Sutherland algoritm

Inom datorgrafik är Cohen –Sutherland-algoritmen en algoritm som används för linjeklippning . Algoritmen delar upp ett tvådimensionellt utrymme i 9 regioner och bestämmer sedan effektivt linjerna och delarna av linjerna som är synliga i den centrala regionen av intresse (vyporten ) .

Algoritmen utvecklades 1967 under flygsimulatorarbete av Danny Cohen och Ivan Sutherland .

Algoritmen

Algoritmen inkluderar, exkluderar eller inkluderar delvis raden baserat på om:

Båda ändpunkterna är i visningsområdet (bitvis ELLER för ändpunkter = 0000): trivial accept .
Båda ändpunkterna delar minst en icke-synlig region, vilket innebär att linjen inte korsar det synliga området. (bitvis OCH av endpoints ≠ 0000): trivialt avvisande .
Båda ändpunkterna finns i olika regioner: i denna icke-triviala situation hittar algoritmen en av de två punkter som är utanför visningsområdet (det kommer att finnas minst en punkt utanför). Skärningspunkten mellan gränsen för utgångspunkten och den utökade siktporten beräknas sedan (dvs. med den parametriska ekvationen för linjen), och denna nya punkt ersätter utgångspunkten. Algoritmen upprepas tills ett trivialt acceptera eller avvisa inträffar.

Siffrorna i figuren nedan kallas utkoder . En utkod beräknas för var och en av de två punkterna på linjen. Utkoden kommer att ha 4 bitar för tvådimensionell klippning, eller 6 bitar i det tredimensionella fallet. Den första biten sätts till 1 om punkten är ovanför viewporten. Bitarna i 2D-utkoden representerar: topp, botten, höger, vänster. Till exempel representerar utkoden 1010 en punkt som är uppe till höger i visningsporten.

	vänster	central	höger
topp	1001	1000	1010
central	0001	0000	0010
botten	0101	0100	0110

Observera att utkoderna för ändpunkter måste beräknas om vid varje iteration efter att klippningen inträffar.

Cohen–Sutherland-algoritmen kan endast användas på ett rektangulärt klippfönster .

Exempel C/C++ implementering

  

    0 
       
      
     
        






    

	     

	              
		  
	          
		  
	              
		  
	          
		  

	 





        

	
	    
	    
	   

	  
		    
			
			  
			
		      
			
			
			
		  
			
			
			  

			
			         

			
			
			
			
			
			
			
			               
				              
				  
			       
				              
				  
			        
				              
				  
			         
				              
				  
			

			
			
			    
				  
				  
				   
			  
				  
				  
				   
			
		
	
	 
 typedef  int  OutCode  ;  const  int  INSIDE  =  ;  // 0000  const  int  LEFT  =  1  ;  // 0001  const  int  RIGHT  =  2  ;  // 0010  const  int  BOTTOM  =  4  ;  // 0100  const  int  TOP  =  8  ;  // 1000  // Beräkna bitkoden för en punkt (x, y) med hjälp av klipprektangeln  // avgränsad diagonalt av (xmin, ymin) och (xmax, ymax)  // ANTA ATT xmax, xmin, ymax och ymin är globala konstanter.  OutCode  ComputeOutCode  (  dubbel  x  ,  dubbel  y  )  {  OutCode  code  =  INSIDE  ;  // initierad som inuti klippfönstret  om  (  x  <  xmin  )  // till vänster om klippfönstrets  kod  |=  VÄNSTER  ;  else  if  (  x  >  xmax  )  // till höger om klippfönstrets  kod  |=  RIGHT  ;  if  (  y  <  ymin  )  // under klippfönstrets  kod  |=  BOTTOM  ;  else  if  (  y  >  ymax  )  // ovanför klippfönstrets  kod  |=  TOP  ;  returkod  ;  _  }  // Cohen–Sutherlands urklippsalgoritm klipper en linje från  // P0 = (x0, y0) till P1 = (x1, y1) mot en rektangel med  // diagonal från (xmin, ymin) till (xmax, ymax).  bool  CohenSutherlandLineClip  (  double  &  x0  ,  double  &  y0  ,  double  &  x1  ,  double  &  y1  )  {  // beräkna utkoder för P0, P1 och vilken punkt som helst som ligger utanför klipprektangeln  OutCode  outcode0  =  ComputeOutCode  (  x0  ,  y0  );  OutCode  outcode1  =  ComputeOutCode  (  x1  ,  y1  );  bool  acceptera  =  falskt  ;  while  (  true  )  {  if  (  !  (  outcode0  |  outcode1  ))  {  // bitvis OR är 0: båda punkterna inuti fönstret; trivialt acceptera och avsluta loop   acceptera  =  sant  ;  bryta  ;  }  else  if  (  outcode0  &  outcode1  )  {  // bitvis AND är inte 0: båda punkterna delar en yttre zon (LEFT, RIGHT, TOP,  // eller BOTTOM), så båda måste vara utanför fönstret; exit loop (acceptera är falskt)   break  ;  }  else  {  // misslyckades båda testerna, så beräkna linjesegmentet för att klippa  // från en yttre punkt till en skärning med klippkanten  dubbel  x  ,  y  ;  // Minst en ändpunkt är utanför klipprektangeln; Välj den.   OutCode  outcodeOut  =  outcode1  >  outcode0  ?  outcode1  :  outcode0  ;  // Hitta nu skärningspunkten;  // använd formler:  // lutning = (y1 - y0) / (x1 - x0)  // x = x0 + (1 / lutning) * (ym - y0), där ym är ymin eller ymax  // y = y0 + lutning * (xm - x0), där xm är xmin eller xmax  // Du behöver inte oroa dig för att dividera med noll eftersom //  outcode-biten som testas i varje fall garanterar att nämnaren inte är noll  om  (  outcodeOut  &  TOP  )  {  // punkten är ovanför klippfönstret  x  =  x0  +  (  x1  -  x0  )  *  (  ymax  -  y0  )  /  (  y1  -  y0  );  y  =  ymax  ;  }  else  if  (  outcodeOut  &  BOTTOM  )  {  // punkten är under klippfönstret  x  =  x0  +  (  x1  -  x0  )  *  (  ymin  -  y0  )  /  (  y1  -  y0  );  y  =  ymin  ;  }  else  if  (  outcodeOut  &  RIGHT  )  {  // punkten är till höger om klippfönstret  y  =  y0  +  (  y1  -  y0  )  *  (  xmax  -  x0  )  /  (  x1  -  x0  );  x  =  xmax  ;  }  else  if  (  outcodeOut  &  LEFT  )  {  // punkten är till vänster om klippfönstret  y  =  y0  +  (  y1  -  y0  )  *  (  xmin  -  x0  )  /  (  x1  -  x0  );  x  =  xmin  ;  }  // Nu flyttar vi utanför punkten till skärningspunkten för att klippa  // och gör oss redo för nästa pass.  if  (  outcodeOut  ==  outcode0  )  {  x0  =  x  ;  y0  =  y  ;  outcode0  =  ComputeOutCode  (  x0  ,  y0  );  }  annat  {  x1  =  x  ;  yl  =  y  ;  outcode1  =  ComputeOutCode  (  x1  ,  y1  );  }  }  }  returnera  acceptera  ;  }

Anteckningar

Se även

Algoritmer som används för samma ändamål:

James D. Foley. Datorgrafik: principer och praxis . Addison-Wesley Professional, 1996. sid. 113.

externa länkar