Infografía I RecortadoRecortado. 2002 J.C.Dürsteler - UPF- IUA Introducción ObjetivoObjetivo –Asegurar que solo se representan los puntos válidos

© © 2002 J.C.Dürsteler - UPF- IUA2002 J.C.Dürsteler - UPF- IUA

Infografía IInfografía I

RecortadoRecortadoRecortadoRecortado

2002 J.C.Dürsteler - UPF- IUA2002 J.C.Dürsteler - UPF- IUA

IntroducciónIntroducción

• ObjetivoObjetivo

– Asegurar que solo se representan los puntos Asegurar que solo se representan los puntos válidosválidos


Introducción (2D)Introducción (2D)

• El cálculo de las direcciones de memoria de los El cálculo de las direcciones de memoria de los píxeles que caen fuera de la pantalla puede píxeles que caen fuera de la pantalla puede ocasionarocasionar– Leer fuera del mapa de memoria.Leer fuera del mapa de memoria.

– Escribir fuera del mapa de memoria. Escribir fuera del mapa de memoria.

• El direccionamiento incorrecto puedeEl direccionamiento incorrecto puede– Colgar el ordenadorColgar el ordenador

– Sobreescribir direcciones de memoria del propio u Sobreescribir direcciones de memoria del propio u otro programa.otro programa.

– Causar errores intermitentes difíciles de localizar.Causar errores intermitentes difíciles de localizar.


Introducción (3D)Introducción (3D)

• Puede ocurrir que objetos situados detrás del Puede ocurrir que objetos situados detrás del observador y que no debieran verse aparezcanobservador y que no debieran verse aparezcan

– La escena se puede volver confusa.La escena se puede volver confusa.

– Según donde esté el observador puede no verse Según donde esté el observador puede no verse nada.nada.

– La transformación perspectiva utiliza el inverso de La transformación perspectiva utiliza el inverso de la distancia, lo que puede dar lugar a valores la distancia, lo que puede dar lugar a valores infinitos.infinitos.

• El recortado es imprescindible en el proceso de El recortado es imprescindible en el proceso de trazado (rendering)trazado (rendering)


Estrategias 2DEstrategias 2D

• Hay tres formas de realizar el recortadoHay tres formas de realizar el recortado– Pre-cortado. Recortar antes de la fase de muestreo. Pre-cortado. Recortar antes de la fase de muestreo.

Interesante para primitivas sencillas Interesante para primitivas sencillas

– Recortar durante el muestreo. Para figuras más Recortar durante el muestreo. Para figuras más complejascomplejas

– Post-cortado. Recortar después del muestreo. Para Post-cortado. Recortar después del muestreo. Para geometrías muy complejas.geometrías muy complejas.

• Se muestrea el área contra una ventana rectangular más Se muestrea el área contra una ventana rectangular más grande.grande.

• Creando una memoria tampón rectangularCreando una memoria tampón rectangular

• La selección depende del coste computacionalLa selección depende del coste computacional

• Estudiaremos el pre-cortado básicamenteEstudiaremos el pre-cortado básicamente


Recortado de puntosRecortado de puntos

• Basta considerar si las coordenadas del punto Basta considerar si las coordenadas del punto son interiores al rectángulo de recorteson interiores al rectángulo de recorte

maxmin xxx

maxmin yyy

xmin, ymin

xmax, ymax


Recortado de líneasRecortado de líneas

• Recortar segmentos => Recortar segmentos => calcular la intersección con el calcular la intersección con el rectángulo de recorte.rectángulo de recorte.

• Cual es el punto de Cual es el punto de intersección bueno. Puede intersección bueno. Puede haber más de uno.haber más de uno.

• Hay circunstancias en las que Hay circunstancias en las que no es necesario calcular la no es necesario calcular la intersección. intersección.


Algoritmo de Cohen-Algoritmo de Cohen-SutherlandSutherland

• Procede en dos fases:Procede en dos fases:

– Eliminación de los casos triviales en los que no hay Eliminación de los casos triviales en los que no hay que recortarque recortar

• segmentos completamente dentro.segmentos completamente dentro.

• segmentos completamente fuera.segmentos completamente fuera.

– Partición iterativa para encontrar los puntos de Partición iterativa para encontrar los puntos de intersección.intersección.


Cohen SutherlandCohen SutherlandCasos trivialesCasos triviales

• Primer bit a 1: el punto está encima Primer bit a 1: el punto está encima del límite superior. Si y>ydel límite superior. Si y>ymaxmax

• Segundo bit a 1: el punto está por Segundo bit a 1: el punto está por debajo del limite inferior. Si y<ydebajo del limite inferior. Si y<yminmin

• Tercer bit a 1: el punto esta a la Tercer bit a 1: el punto esta a la derecha de la frontera derecha. Si derecha de la frontera derecha. Si x>xx>xmaxmax

• Cuarto bit a 1: el punto está a la Cuarto bit a 1: el punto está a la izquierda de la frontera izquierda. izquierda de la frontera izquierda. Si x<xSi x<xminmin

• Al contrario si están a 0Al contrario si están a 0

1001 1000 1010

0001Pantalla

00000010

0101 0100 0110


Cohen SutherlandCohen SutherlandCasos trivialesCasos triviales

• Nótese queNótese que

– El bit 1 es el bit del El bit 1 es el bit del signo de ysigno de ymaxmax - y - y

– El bit 2 es el bit del El bit 2 es el bit del signo de y - ysigno de y - yminmin

– El bit 3 es el bit del El bit 3 es el bit del signo de xsigno de xmaxmax - x - x

– El bit 2 es el bit del El bit 2 es el bit del signo de x - xsigno de x - xminmin

• Si los códigos de bits de ambos Si los códigos de bits de ambos puntos son 0000puntos son 0000– La recta esta entera dentro del La recta esta entera dentro del

área de recorte.área de recorte.

• Si ambos puntos tienen el bit a Si ambos puntos tienen el bit a 1 de un mismo semiplano son 1 de un mismo semiplano son rechazablesrechazables– Operando con el Operando con el ANDAND lógico sus lógico sus

códigoscódigos• Si da 1 Podemos rechazar la Si da 1 Podemos rechazar la

recta.recta.• Si da 0 la recta está dentro o Si da 0 la recta está dentro o

corta el áreacorta el área


01

01

xx

yyxy

Cohen SutherlandCohen SutherlandIntersecciónIntersección

• Buscamos uno de los puntos que cae fuera de la Buscamos uno de los puntos que cae fuera de la zona de recorte. zona de recorte.

• Miramos el código binario de este punto para Miramos el código binario de este punto para descubrir cuál o cuáles ejes intersecta.descubrir cuál o cuáles ejes intersecta.

• Buscamos la intersección con cada uno de los ejes Buscamos la intersección con cada uno de los ejes que corta, simplemente sustituyendo en la ecuación que corta, simplemente sustituyendo en la ecuación de la rectade la recta

• el valor xmin, xmax, ymin ó ymax que corresponda al el valor xmin, xmax, ymin ó ymax que corresponda al eje que cruzamos, y calculamos su código binario.eje que cruzamos, y calculamos su código binario.


Cohen SutherlandCohen SutherlandIntersecciónIntersección

• Si el código binario no es 0000 el punto correspondía a Si el código binario no es 0000 el punto correspondía a otra intersección. Procedemos de igual forma con la otra intersección. Procedemos de igual forma con la siguiente intersección. siguiente intersección.

• En caso contrario ya hemos encontrado la intersección En caso contrario ya hemos encontrado la intersección correcta. correcta.

• Si el otro punto del segmento queda fuera le aplicamos Si el otro punto del segmento queda fuera le aplicamos el mismo algoritmo hasta que ambos puntos tengan el mismo algoritmo hasta que ambos puntos tengan código 0000 (o descartemos todos los segmentos de la código 0000 (o descartemos todos los segmentos de la recta).recta).


PolígonosPolígonos

• Dificultad : multiplicidad Dificultad : multiplicidad de casos posibles. de casos posibles.

– Cada lado del polígono Cada lado del polígono se ha de comprobar se ha de comprobar contra cada lado del contra cada lado del área de recortado.área de recortado.

• Reducirlo a múltiples Reducirlo a múltiples casos de recortado no casos de recortado no conserva la información conserva la información de qué líneas de qué líneas pertenecen a que pertenecen a que polígono.polígono.


Algoritmo de Algoritmo de Sutherland HodgmanSutherland Hodgman

• Resuelve el problema Resuelve el problema general de recortar un general de recortar un polígono cualquiera polígono cualquiera contra cualquier otro contra cualquier otro polígono polígono convexoconvexo

• Estrategia reducir el Estrategia reducir el problema general a una problema general a una sucesión de problemas sucesión de problemas elementaleselementales

– recortado del polígono recortado del polígono respecto a una sola respecto a una sola línea infinitalínea infinita

• Entrada: serie de Entrada: serie de vértices del polígono vértices del polígono v1, v2, ..., vn y recta del v1, v2, ..., vn y recta del polígono de recorte. polígono de recorte.

• Salida: serie de vértices Salida: serie de vértices transformados del transformados del polígono. polígono.

• La lista se realimenta La lista se realimenta en el propio algoritmo en el propio algoritmo contra la siguiente líneacontra la siguiente línea



• 1) Antes de recortar1) Antes de recortar

• 2) recortado contra la línea 1 2) recortado contra la línea 1

• ……

• 5) Recortado contra la línea 4 5) Recortado contra la línea 4



• En el cálculo de las intersecciones de cada lado del En el cálculo de las intersecciones de cada lado del polígono con la arista de recorte se añaden 0, 1 ó 2 polígono con la arista de recorte se añaden 0, 1 ó 2 vértices a la lista.vértices a la lista.

Vamos del punto i(nicio) al f(inal). Como ambos están fuera no añadimos ningún punto a la lista de vértices.

Cruzamos la frontera. añadimos el punto de intersección p1 y el f.(2 puntos)

Tanto i como f están dentro, pero i lo hemos añadido en el caso anterior. Añadimos sólo f. (1 punto)

De nuevo cortamos. El punto i lo añadimos antes. Ahora añadimos p2. (1 punto)


AlgoritmoAlgoritmo

• Función dentro(x,y, arista) Función dentro(x,y, arista) – devuelve 1 si el vértice está dentro del área de devuelve 1 si el vértice está dentro del área de

recortado y 0 si norecortado y 0 si no

– ““dentro” significa a la izquierda de la frontera dentro” significa a la izquierda de la frontera yendo del primer al segundo vértice yendo del primer al segundo vértice

• Corresponde a una numeración de vértices en sentido Corresponde a una numeración de vértices en sentido antihorarioantihorario

– Si es un rectángulo basta mirar el signo de la Si es un rectángulo basta mirar el signo de la distancia en vertical u horizontal hasta la fronteradistancia en vertical u horizontal hasta la frontera

– Si no, se puede consultar el signo del producto Si no, se puede consultar el signo del producto vectorial de la normal a la frontera con la arista vectorial de la normal a la frontera con la arista del polígono del polígono


AlgoritmoAlgoritmo

• Subrutina intersecta()Subrutina intersecta()

– Calcula la intersección de la arista que va del Calcula la intersección de la arista que va del vértice i al vértice f con la fronteravértice i al vértice f con la frontera

– La frontera está definida por dos vértices.La frontera está definida por dos vértices.

• Subrutina salida()Subrutina salida()

– Añade los vértices nuevos al vector que contiene Añade los vértices nuevos al vector que contiene el polígonoel polígono

– Actualiza el numero de entradas del mismo.Actualiza el numero de entradas del mismo.


AlgoritmoAlgoritmo

• Atención éste no es un algoritmo operativo, consideradlo Atención éste no es un algoritmo operativo, consideradlo seudocódigoseudocódigo

• SutherlandHodgman(VerticesIn, longIn, VerticesOut){SutherlandHodgman(VerticesIn, longIn, VerticesOut){

int longOut=0;int longOut=0;

int j;int j;

vertice, i, ini, fin;vertice, i, ini, fin; /* Estructura i.x e i.y *//* Estructura i.x e i.y */

ini=VerticesIn(longIn);ini=VerticesIn(longIn); /*Empezamos por el final *//*Empezamos por el final */

for j=0; j<longIn;j++){for j=0; j<longIn;j++){

fin=VerticesIn(j);fin=VerticesIn(j);

if (dentro(fin, frontera)){if (dentro(fin, frontera)){ /* Casos 2 y 3 *//* Casos 2 y 3 */

if (dentro(ini,frontera)) salida(fin,longOut,VerticesOut); /* 3 */if (dentro(ini,frontera)) salida(fin,longOut,VerticesOut); /* 3 */

else{else{ /* 2 *//* 2 */

Intersecta (ini, fin, frontera, i);Intersecta (ini, fin, frontera, i);

salida(i,longOut,VerticesOut);salida(i,longOut,VerticesOut);

salida(fin,longOut,VerticesOut)salida(fin,longOut,VerticesOut)

}}


AlgoritmoAlgoritmo

• Atención este no es un algoritmo operativo, considerarlo Atención este no es un algoritmo operativo, considerarlo seudocódigoseudocódigo

else {else { /* 4 y 1 *//* 4 y 1 */

if (dentro(ini,frontera)) {if (dentro(ini,frontera)) { /* 4 *//* 4 */

Intersecta (ini, fin, frontera, i);Intersecta (ini, fin, frontera, i);

salida(ini,longOut,VerticesOut);salida(ini,longOut,VerticesOut);

}} /* 1 nada *//* 1 nada */

ini=finini=fin

} /* fin del for */} /* fin del for */

}}


Cohen SutherlandCohen Sutherland

• El algoritmo de Cohen Sutherland es válido para El algoritmo de Cohen Sutherland es válido para recortar polígonos cóncavos o convexos contra recortar polígonos cóncavos o convexos contra cualquier área de recortado poligonal cualquier área de recortado poligonal convexaconvexa..

• Se puede extender a 3D y permite recortar Se puede extender a 3D y permite recortar contra volúmenes poliédricos convexos cuyas contra volúmenes poliédricos convexos cuyas caras sean planas.caras sean planas.

Documents

Infografía I RecortadoRecortado. 2002 J.C.Dürsteler - UPF- IUA Introducción ObjetivoObjetivo –Asegurar que solo se representan los puntos válidos