Algoritme de Cohen-Sutherland

El algoritme de Cohen-Sutherland és un algoritme de retallada de llínees usat en gràfics per computadora. Va ser desenrollat per Danny Cohen i Ivan Sutherland en 1967.

Introducció

Este algoritme resol la retallada de llínees que queden fòra d'un rectàngul alineat en els eixos. Per a això dividix l'espai 2D en una matriu de 9 regions, de les quals l'única visible és la part central (el viewport). El viewport, és la pantalla o pla de proyecció.

Dit d'un atre modo, les llínees que delimiten el viewport són prolongades en abdós extrems dels seus 4 llínees formant aixina 9 plans perfectament separats, a on els seus punts d'intersecció queden perfectament delimitats i són iguals a les coordenades que descriuen el viewport.

       |          |
       |          |
       |          |
-------+----------+-------
       |          |
       |          |
       | Viewport |
       |          |
       |          |
-------+----------+-------
       |          |
       |          |
       |          |

Funcionament

solament les porcions de les llínees dins de l'àrea verda (coloreadas de blava) necessiten ser dibuixades

Cada punt té assignats uns còdics de frontera que indiquen la posició d'eixe punt respecte al viewport. Cada còdic de frontera es compon de 4 bits.

L'algoritme inclou, exclou, o inclou parcialment, la llínea (segment) basat en on estan els seus punts extrems:

• Abdós punts estan en el viewport (l'operació bitwise OR dels seus punts extrems és igual a zero): acceptació trivial.
• Abdós punts estan en la mateixa regió no visible (l'operació bitwise AND dels seus punts extrems no és igual a zero): rebuig trivial.
• Abdós punts estan en regions distintes: En cas d'esta situació no trivial l'algoritme troba un dels 2 punts que està fòra del viewport (hi ha a lo manco un punt fora). L'intersecció del punt exterior en la frontera estesa és llavors calculada (és dir, en l'equació paramètrica de la llínea) i este nou punt reemplaça al punt exterior. L'algoritme es repetix fins que ocorre un èxit o rebuig trivial.

Pot vore's en el dibuix un eixemple per a cada cas. Note's com solament les porcions de les llínees dins de l'àrea verda (coloreadas de blava) necessiten ser dibuixades.

Còdics de frontera

Els números en la figura inferior es diuen còdics de frontera. Un còdic de frontera és calculat per a cada u dels dos punts extrems de la llínea (tant per al punt inicial com el punt final de la llínea). El primer bit és assignat a 1 si el punt esta per damunt del viewport. Els bits del còdic de frontera representen: Dalt, Avall, Dreta, Esquerra. Per eixemple el còdic de frontera 1010 representa un punt que està dalt i a la dreta del viewport. Note que els punts de frontera tenen que ser recalculados en cada iteración en acabant de que el tall ocorre.

1001	1000	1010
0001	0000	0010
0101	0100	0110

Analisant els valors i passant-los a decimal (que resulta més comprensible a qualsevol audiència), pot analisar-se que horisontalment, hi ha una separació d'1 unitat entre el valor central i el de la seua esquerra i entre est i el valor de la dreta (8,9,10 - 0,1,2 - 4,5,6). I de modo equivalent hi ha una separació verticalment de 4 unitats entre un valor de la fila central i el de la fila inferior i entre est i el de la fila superior (1,5,9 - 0,4,8 - 2,6,10.

09	08	10
01	00	02
05	04	06

Vore també

• Cyrus-Beck, algoritme per a retallada de llínees.
• Liang-Barsky, algoritme per a retallada de llínees.
• Fast-Clipping, algoritme per a retallada de llínees.
• Nicholl-Lee-Nicholl, algoritme per a retallada de llínees.
• Sutherland-Hodgman, algoritme per a retallada de llínees i polígons.
• Weiler-Atherton, algoritme per a retallada de llínees i polígons.