Graficas x computadora · 2017. 5. 8. · ALGORITMO DE COHEN-SUTHERLAND Uno de los procedimientos...
Transcript of Graficas x computadora · 2017. 5. 8. · ALGORITMO DE COHEN-SUTHERLAND Uno de los procedimientos...
Graficas x computadora
TRANSFORMACIONES AFINES Y OTROS PROCEDIMIENTOS 2D
Composición de transformacionesSe pueden aplicar sucesivas transformaciones
a un punto.Al resultado de la primera transformación:
M1 · P se aplica una segunda transformación:
M2 ·[ M1 · P] = [M2 · M1 ] · P
La composición de transformaciones se realiza mediante el producto de matrices
M = Mn ·Mn-1 ·… ·M2 · M1
Transformaciones geométricaslas transformaciones geométricas son la o las
operaciones geométricas que permiten crear una nueva figura a partir de una previamente dada. la nueva figura se llamará "homólogo" de la original.
directa: el homólogo conserva el sentido del original en el plano cartesiano
Su inversa
Transformacionesisométricas: el homólogo conserva las
dimensiones y ángulos. También se llaman "movimientos", éstos son simetría axial y puntual, rotación y traslación.
isomórficas: el homólogo conserva la forma y los ángulos. existe proporcionalidad entre las dimensiones del homólogo con el original. una de ellas es la homotecia.
anamórficas: cambia la forma de la figura original. Una de ellas es la inversión.
La traslación Las traslaciones son movimientos directos, es
decir, mantienen la forma y el tamaño de las figuras, a las cuales deslizan según el vector T.
Vector T
La traslación
La rotación
El EscalamientoIsométricoNo-isométricoCizallaAfilamiento
Escalamiento
Recortes en 2dCohen- SutherlandLiang-BarskyLee-nichollAtherton-Willer
Cohen-SutherlandZonas de recorte
Zona “0” cliente
0100
0001001
0
1000
RECORTE DE PUNTOS BIDIMENSIONALES
YmáxYmín
XmáxXmín
≤≤≤≤
Y
X
Para que un punto P=(x,y) , se encuentre dentro de un rectángulo de recorte y por lo tanto pueda ser visualizado, tiene que cumplir con los siguientes requisitos:
P=(x,y)
Rectángulo de Recorte
RECORTE DE LINEAS
Primero, determinar si un segmento de línea dado cae por completo dentro de la ventana de recorte.
Si no es así, determinar si cae por completo fuera de la ventana.
Por último, si no podemos identificar una línea que se localice por completo dentro o fuera, debemos realizar cálculos de intersección con una o más fronteras de recorte.
RECORTE DE LINEAS BIDIMENSIONALES
Formulación paramétrica de la ecuación de la recta cuyos puntos extremos son
( )( )
1t0
Y t Y
XtX
010
010
≤≤−+=−+=
YY
XX
( )00 ,YX ( )11,YXy
Antes del Recorte Después del Recorte
RECORTE DE LÍNEAS
ALGORITMO DE RECORTE DE LINEAS DE COHEN-SUTHERLAND
ALGORITMO DE COHEN-SUTHERLANDUno de los procedimientos
de recorte de líneas más antiguo y común.
Éste método acelera el procesamiento de segmentos de líneas al realizar pruebas iniciales que reducen el número de intersecciones que se debe calcular.
A todos los extremos de línea de una imagen se asigna un código binario de cuatro dígitos, conocido como código de región o de frontera, el cual identifica la localización del punto con respecto de las fronteras del rectángulo de recorte.
0000
10011000
0100
0001
0101 0110
1010
0010
Rectángulo de recorte
Código de Región
bit 1
bit 3
bit 2 bit
4
Superior
Inferior
Derecha
Izquierda
Posiciones de los bits en el codigo de región de los puntos extremos
ALGORITMO DE COHEN-SUTHERLAND
ALGORITMO DE COHEN-SUTHERLAND
Para determinar una intersección de un segmento de línea con la frontera, podemos utilizar la forma punto-pendiente de la ecuación de la línea. Para una línea con coordenadas en sus puntos extremos (X0,Y0) y (X1,Y1)
Punto de intersección:
Con el borde Vertical:Con el borde Horizontal:
Y = Y0 + m (X - X0)
X = X0 + (Y – Y0)
m
ALGORITMO DE COHEN-SUTHERLANDEn Resumen:1. Operamos en mundo real 2. Input: dos puntos P1, P2 3. Output: dos puntos o ninguno 4. Código LRBT asociado a punto P:
a. L=left bit: 0 si punto a la derecha de borde izquierdo de ventana (in) (x >= wL)1 en caso contrario (out)
b. R=right bit: 0 si punto a la izquierda de borde derecho de ventana (in) (x <= wR)1 en caso contrario (out)
c. B=bottom bit: 0 si punto encima de borde inferior de ventana (in) (y >= wB)1 en caso contrario (out)
d. T=top bit: 0 si punto debajo de borde superior de ventana (in) (y <= wT)1 en caso contrario (out)
ALGORITMO DE COHEN-SUTHERLAND VENTAJAS
Una ventaja del algoritmo de Cohen-Sutherland es que se obtiene en forma directa una extensión al volumen de la vista ortográfica tridimensional.
DESVENTAJAS
La desventaja que presenta este algoritmo, debido a que las pruebas y los recortes se llevan a cabo siguiendo un orden fijo, es que realiza recortes innecesarios; esto es, cuando la intersección con la arista no cae en la frontera del rectángulo de recorte.
ALGORITMO DE RECORTE DE LINEAS DE NICHOLL-LEE NICHOLL
ALGORITMO DE NICHOLL-LEE-NICHOLL
Evita los múltiples de los cálculos de las intersecciones de la línea.
Evita cortes innecesarios cuando la intersección con la arista del rectángulo es una intersección externa
Comparado con los algoritmos de Cohen-Sutherland y de Liang-Barsky, el algoritmo Nicholl-Lee-Nicholl lleva acabo menos comparaciones y divisiones.
Se aplica solo al recorte bidimensionalPara una línea con extremos P1 y P2, primero se
determina la posición del punto P1 para las nueve regiones posibles relativas al rectángulo de recorte.
ALGORITMO DE NICHOLL-LEE-NICHOLL
Solo es necesario considerar las regiones que se muestran en lasiguiente figura:
P1 en la ventana
P1 en la región de
arista
P1 en la región de esquina
Si P1 se encuentra en cualquier otra de las seis regiones, se le puede mover a una de las tres regiones de la figura anterior utilizando una transformación de simetría.
ALGORITMO DE NICHOLL-LEE-NICHOLLPara determinar la posición de P2 con respecto a P1 creamos algunas regiones nuevas en el plano, dependiendo de la ubicación de P1.
Si P1 se halla adentro de la ventana de recorte y P2 se encuentra afuera, establecemos las cuatro regiones que se muestran en la siguiente figura: Si P2 se encuentra en una de las
regiones T, L, TR, TB, LR o LB, determina una arista única de recorte de ventana para los cálculos de las intersecciones.
De otra manera, se rechaza la línea completa.
ALGORITMO DE NICHOLL-LEE-NICHOLL VENTAJAS
Evita los múltiples de los cálculos de las intersecciones de la línea.
Evita cortes innecesarios cuando la intersección con la arista del rectángulo es una intersección externa
DESVENTAJAS
Solo se puede realizar en 2 dimensiones
ALGORITMO DE RECORTE PARAMETRICO DE LINEAS
• ¿Cómo se calculan las intersecciones?• En coordenadas explícitas es complicado,
porque aparte de calcular el punto, debemosaveriguar si pertenece al interior del
segmento o no• Es mucho más simple si usamos la ecuación
paramétrica de la recta
ALGORITMO DE RECORTE PARAMETRICO DE LINEASEl algoritmo de línea paramétrica,
encuentra el valor del parámetro u en la representación paramétrica del segmento de línea para el punto donde el segmento intersecta la línea infinita del arista de recorte.
Como todas las aristas de recorte son, en general, intersectadas por la línea, cuatro valores de u se calculan.
ALGORITMO DE RECORTE PARAMETRICO DE LINEAS
Una serie de comparaciones sencillas se usan para determinar cual (si alguno) de los cuatro valores de u corresponde a las intersecciones actuales.
Solo entonces se calculan los valores (x,y) para una o dos intersecciones reales.
ALGORITMO DE RECORTE DE CYRUS Y BECK, LIANG-BARSKY
ALGORITMO DE RECORTE DE CYRUS Y BECK, LIANG-BARSKY
ALGORITMO DE CYRUS Y BECK
El algoritmo se basa en la formulación de la intersección entre dos líneas
El algoritmo de Cyrus-Beck es válido para recortar segmentos de línea recta sobre cualquier polígono convexo, no únicamente sobre una ventana rectangular.
ALGORITMO DE CYRUS Y BECK
Se puede utilizar para recortar una línea de 2D contra un rectángulo o un polígono convexo arbitrario en un plano, o una línea de 3D contra un poliedro convexo arbitrario en 3D , ya que evita el ciclo repetitivo necesario para recortar sobre múltiples aristas.
ALGORITMO DE LIANG-BARSKYEl algoritmo de Liang-Barsky usa la
ecuación paramétrica de la línea y desigualdades describiendo el rango del área de recorte para determinar las intersecciones entre la línea y el area de recorte. Con estas intersecciones se sabe qué porción de la línea debería ser dibujada.
ALGORITMO DE LIANG-BARSKYP(t)=P0+t( P1 -P0)
P0 :Punto inicial
P1 :Punto final
Se elige un punto arbitrario PEi en la arista Ei y considere tres vectores.
Podemos determinar en que región se encuentra un punto, observando el valor del producto Punto:
ALGORITMO DE LIANG-BARSKY
Ahora se puede resolver el valor de t en la intersección de la arista:
Primero se sustituye :
Después se agrupan términos y se distribuye el producto punto:
Sea el vector de a y despejando t
la normal no debe ser cero.
0])([ =−•i
PtPNi ε
10 PP
0])([ 010 =−−+•i
PPPtPN i ε)(tP
0][][ 010 =−•+−• PPtNPPN ii iε
)( 01 PPD −=[ ]
DN
PPN
i
Eii i
−−
=
0≠iN
0≠D
0≠• DNila arista y la línea no son paralelas.
ALGORITMO DE LIANG-BARSKYDados los valores de t se determinan cuales de ellos indican
intersecciones interiores del segmento con las aristas.
Eliminamos cualquier valor de t fuera del intervalo [0,1] después determinamos si la intersección se halla en una frontera de recorte.
Se clasifican las intersecciones:
* Potencialmente entrantes (PE):
* Potencialmente salientes (PS):
ALGORITMO DE LIANG-BARSKY
ALGORITMO DE LIANG-BARSKY
Consideramos el segmento de línea : P1 = (2,5), P2 = (12,15)Se sabe que: D = (12-2,15-5) = (10,10)
Xmin= 4 Xmax = 11
Ymax = 11
Ymin = 6
P1 (2,5)
P2 (12,15)
PE = (4,7)
PE = (3,6)
PS= (8,11)
PS = (11,14)
x = x1+ t (x2-x1)y = y1+ t (y2-y1)
ALGORITMO DE LIANG-BARSKY
ALGORITMO DE LIANG-BARSKYRESUMEN:El recorte paramétrico es mas conveniente cuando hay que
recortar varios segmentos.Ahorra tiempo, además los cálculos de parámetros son
más sencillos
Transformaciones en 3 dimensionesLa expresión general de una transformación
en tres dimensiones en coordenadas homogéneas es:
x´ a11 a12 a13 a14 xy´ a21 a22 a23 a24 yz´ a31 a32 a33 a34 z1 0 0 0 1 1
Matriz de transformación M44Describe todas las transformaciones:
traslación, escalado, rotación, deformación.La composición de transformaciones se
realiza mediante el producto de matricesSe pueden obtener los valores de la
transformación a partir de la matriz: desplazamiento, escala y giro.
3D: Traslación
x´ 1 0 0 tx xy´ 0 1 0 ty yz´ 0 0 1 tz z1 0 0 0 1 1
x´ = x + txy´ = y + tyz´ = z + tz
3D: Escalado
x´ sx 0 0 0 xy´ 0 sy 0 0 yz´ 0 0 sz 0 z1 0 0 0 1 1
x´ = sx ·xy´ = sy ·yz´ = sz ·z
3D: Escalado no homogéneo
sx sy sz
3D: Rotación
3D: Matrices de rotaciónx´ 1 0 0 0 xy´ 0 cos θ-sin θ0 yz´ 0 sin θcos θ 0 z1 0 0 0 1 1
Rotación en x
x´ cos θ 0 sin θ 0 xy´ 0 1 0 0 yz´ -sin θ 0 cos θ 0 z1 0 0 0 1 1
Rotación en y
x´ cos θ-sin θ 0 0 xy´ sin θcos θ 0 0 yz´ 0 0 1 0 z1 0 0 0 1 1
Rotación en z
Otras transformaciones
x´ 1 0 a 0 xy´ 0 1 b 0 yz´ 0 0 1 0 z1 0 0 0 1 1
Oblicua en xy (z invariante)
x´ 1 0 0 0 xy´ 0 1 0 0 yz´ 0 0 -1 0 z1 0 0 0 1 1
Reflexión plano xy
La composición de transfor-maciones no es conmutativa
Estructura jerárquicaUn objeto se sitúa respecto a su sistema de
coordenadas.Todo el conjunto se puede situar en un
sistema de coordenadas distinto y así sucesivamente.
Las coordenadas en el sistema final se obtienen por composición de transformaciones.
Rotación alrededor de un pivotSi el eje de rotación no pasa por el origen, son
necesarias las siguientes operacionesTrasladar el punto de rotación Q, al origenRealizar la rotaciónDeshacer la traslación
La composición de transformaciones es: MRQ (θ) = M3 · M2 · M1 MRQ (θ) = MT (qx, qy, qz) ·MR (θ) · MT (-qx, -qy, -qz)
El escalado se realiza análogamente
x
y
z
θ
Q
R
O
r
Rotación alrededor de un ejeEl eje define por un punto “Q” y un vector
unitario “r”. Se realiza una rotación de un ángulo θ.
Se resuelve mediante composición de transformacionesSe enuncian las transformacionesSe determina el cálculo de cada una de ellasSe explica como evaluar los ángulos requeridos
Rotación alrededor de un eje:composición de transformaciones
Rotación-β en x
x
y
z
Q
Rr
x
y
z Q’
R’
x
y
z Q’
R´´
Rotación- α en z
Traslación-QO
Posición inicial
x
y
z
Q
Rr
x
y
z Q’
R’
x
y
z Q’
R´´
x
y
z Q’
R´´´
Traslación QO
Rotaciónα en z
Rotaciónβ en x
Rotaciónθ en y
x
y
z Q’
R´´´
Posición inicial
M1 M2 M3 M4
M5 M6 M7
Rotación alrededor de un eje:relación de transformacionesLa matriz de transformación es:
M(Q,r) (θ) = M7 · M6 · M5 · M4 · M3 · M2 · M1 M1 : traslación QO M2 : rotación α en z M3 : rotación β en x M4 : rotación θ en y M5 : rotación -β en x M6 : rotación -α en z M7 : traslación -QO
x
y
z
θ
Q
R
O
r
x
y
zQ’
R’
Rotación alrededor de un eje: M1 - traslación QO
Sea R tal que OR = OQ + rLa traslación que lleva Q al origen es:
M1 = MT (-qx, -qy, -qz)
M1
R´´
x
y rxy
z
Q’
R’
α
R´´
x
y rxy
z
Q’
R’
α
Rotación alrededor de un eje:M2 - rotación α en zCalcular el ángulo α entre los planos YZ y
el plano definido por el eje z y OR’ rxy es la proyección ortogonal de r sobre XY R’’ es el resultado del giro alrededor de z α es el ángulo entre rxy y j (vector unitario
de y) tener en cuenta el sentido de giro positivo k
M2 es la matriz de rotación alrededor del eje z: M2 = MRz (α)
Rotación alrededor de un eje:M3 - rotación β en x
Aplicando M2 a R’ se obtiene R’’ R’’ está en el plano YZ r’’ lo define OR’’
Calcular el ángulo β entre r’’ y j tener en cuenta el sentido de giro positivo i
M3 es la matriz de rotación alrededor del eje x: M3 = MRx (β)
x
y
zQ’
R´´´
R´´
β
Rotación alrededor de un eje:M4 - rotación θ en y
Aplicando M3 a R’’ se obtiene R’’’ R’’’ está en el eje y
Se realiza el giro θ en el eje yM4 es la matriz de rotación alrededor del eje
y: M4 = MRy (θ)
x
y
z Q’
R´´´
Rotación alrededor de un eje:M5, M6, M7 - inversas
Una vez calculado el giro θ alrededor del eje transformado, habrá que invertir el proceso de transformación y para ello se calculan las matrices inversas M5 = MRx (-β) M6 = MRz (-α) M7 = MT(qx, qy, qz)
La matriz de transformación compuesta es:M(Q,r) (θ) = M7 · M6 · M5 · M4 · M3 · M2 · M1
α = acos ( ry / (rx2 + ry2 )1/2 )y si rx < 0 ⇒ α = - α α
y
z x
α rxy
jrxy
R´´
x
y rxy
z
Q’
R’
α
Rotación alrededor de un eje:ángulo αCálculo del ángulo α
rxy es la proyección ortogonal de r sobre el plano XY: (rx, ry, 0)
cos α = j · rxy / | rxy | = = ( (0, 1, 0) · (rx, ry, 0) ) / (rx2 +
ry2 )1/2 cos α = ry / (rx2 + ry2 )1/2 Como cos α = cos (–α) , entonces
si rx < 0 entonces el ángulo debe ser (2π- α) ⇒ α = - α
β = acos ( ry´´ / (ry´´2 + rz´´2 )1/2 )y si rz´´ > 0 ⇒ β = - β
x
y
zQ’
R´´´
R´´
β
β
β r´´
jr´´
z x
y
Rotación alrededor de un eje:ángulo βCálculo del ángulo β
R’’ y r’’ están en el plano YZ cos β = j · r´´ / | r´´| = = ( (0, 1, 0) · (0, ry´´, rz´´) ) / (ry´´2 + rz
´´2 )1/2 cos β = ry´´ / (ry´´2 + rz´´2 )1/2 Como cos β = cos (–β) , entonces
si rz ´´ > 0 entonces el ángulo debe ser (2π- β) ⇒ β = - β