Programación en Lenguaje Ensamblador

-El Verdadero Lenguaje de las Máquinas-

Programación Gráfica: Recorte de Lineas de Liang-Barsky

–Como cortar un segmento de linea con un plano de recorte–

En la entrada anterior vimos todo lo necesario para entender lo que es el recorte de un modelo 3D. Que el recorte comienza desde que decidimos si cortamos o no y acaba en la reconstrucción del modelo que acabamos de recortar. En esta entrada vamos a ver un algoritmo de recorte de lineas en el espacio conocido como el Recorte de lineas de Liang-Barsky. Les recuerdo que el recorte es una operación básica en programación gráfica pero que mucha gente que afirma dedicarse a esto de los juegos 3D ignora por completo. Pero primero pasemos con las matemáticas.

En la primera fotografía tenemos las dos únicas cosas involucradas en el recorte de lineas en el espacio 3D: Un segmento de recta definido por sus 2 puntos extremos y un plano de recorte. Piensen en el plano de recorte como una navaja que corta un trozo de alambre muy fino. En la imagen el plano pueden verse 3 puntos del plano y un vector normal (la flecha que sale como un clavo) Para recortar necesitamos como mínimo uno de esos 3 puntos de las orillas del plano y el vector normal. Aunque cualquier punto en el espacio que haga que la ecuación del plano sea cero nos va a funcionar. Otra cosa que deben de recordar es que en una superficie completamente plana el vector normal va a ser siempre el mismo sin importar que punto de la superficie elijamos. Sobra decir que para que el algoritmo de recorte funcione el plano de recorte debe de quedar entre los dos puntos extremos de la linea que queremos cortar. Aunque veremos que el algoritmo de Liang-Barsky también funciona cuando esta condición no se cumple. Ahora veamos el algoritmo en acción.

En la tercera imagen vemos el algoritmo de Liang-Barsky en acción. El plano se ha acomodado de tal forma que solo lo podemos ver desde uno de sus filos. El segmento de linea es partido por el plano de recorte y podemos ver el punto exacto en el que esto sucede. También podemos ver una flecha extra que parte desde el punto naranja del plano. ¡Y que llega directo al punto de recorte!. En resumen, el algoritmo que estamos estudiando toma en cuenta que este vector que señala directo al punto de intersección está en ángulo recto con el vector normal al plano de recorte. Este vector lo vamos a llamar Vector Escoba porque “barre” la linea a todo lo largo hasta que topa con el plano que la va a cortar. Hasta aquí tenemos toda la información visual que necesitamos para aplicar el recorte de linea. Ahora pasemos a lo que todos los enginefags que vienen a este blog nada mas para ver como me burlo de ellos tanto temen: Las matemáticas.

Primero vamos a traducir las dos imágenes anteriores en expresiones matemáticas programables. Para hacer el recorte lo mínimo que necesitamos son una linea y un plano de recorte. Y a partir de ellos obtenemos los siguientes datos:

Vector normal al plano (N): Dependiendo de si hemos definido el plano en forma de ecuación de plano o con 3 vértices el método será diferente. Lo mas directo es tomar 3 vértices no colineales, convertirlos en 2 vectores mediante restas y luego hacer un producto cruz, aunque si el plano de recorte es fijo (como el de una toma de cámara) es mejor tomar los factores A, B y C de la acuación del plano Ax + By + Cz + D = 0 directamente.

Punto en el plano (Ppl).-Es un punto perteneciente al plano de recorte, puede ser cualquier trio XYZ que haga que la ecuación del plano sea igual a cero o si el plano se definió por 3 puntos en el espacio podemos tomar cualquiera de esos 3 puntos. Para que el algoritmo fuera mas sencillo de entender, el punto Ppl y el vector N se encuentran colocados de modo que N tiene a Ppl como base, aunque pudo haberse elegido cualquier otro punto del plano. Recuerden que N es igual en cualquier parte del plano.

Vector Direccional de la linea (D) El vector D se obtiene cuando tomamos las coordenadas del punto final de la linea y les restamos sus respectivas coordenadas xyz del punto inicial. El resultado es un vector que apunta hacia donde se supone se dirige la linea. Se obtiene en notación vectorial como D = p1 – p0.

Vector Escoba (E).-Este es el mas dificil. Se trata de un vector que tiene su origen en un punto del plano y su punta en algún punto dentro de la linea que queremos cortar. El problema es que no tenemos las coordenadas de ese punto, así que aquí es donde trataremos de obtenerlas. Ahora vamos a ver como crear la fórmula de recorte de lineas desde cero.

Explicación de las Ecuaciones

Lo primero que sabemos es que debe de haber un ángulo recto entre los vectores N y E. Y esto solo puede suceder si el producto escalar entre los vectores N y E es igual a cero.

N . E = 0

El problema es que como el punto al que señala el vector E no es una coordenada fija en el espacio sino que barre cual escoba toda la longitud de la linea, hay que definir esa coordenada como una función paramétrica. Entonces E sería igual a cualquier punto dentro de la linea a cortar menos el punto en el plano Ppl:

E = P(t) – Ppl

Entonces como el producto escalar entre los vectores N y E debe de ser igual a cero, si sustituimos E por la expresión anterior nos queda:

N . [P(t) – Ppl] = 0

Ahora sustituimos P(t) por su forma paramétrica p0 + (p1 – p0) * t

N . [p0 + (p1 – p0) * t – Ppl] = 0

El siguiente paso es engañoso. Hay que agrupar lo que está entre los paréntesis cuadrados en dos partes. Una es p0 – Ppl y la otra es (p1-p0) * t. Como se trata de coordenadas espaciales xyz, el resultado de este par de restas son dos vectores que ya conocemos. Si a eso le agregamos que t es un escalar que multiplica un vector podemos hacer un par de productos punto como indica la siguiente expresión:

N . [p0 – Ppl] + N . [p1-p0] * t = 0

Finalmente aplicamos un poco de álgebra para despejar t. Primero restamos a ambos lados de la ecuación N . [P0 – Ppl] y luego dividimos ambos lados por N . [p1 – p0] y el resultado es:

t = -N . [p0 – Ppl]/(N . [p1 – p0])

Ahora bien, si nos fijamos [p1 – p0] es el vector D que indica la dirección en la que va la linea que cortamos y [p0 – Ppl] es uno de los vectores escoba. Si profundizamos mas en las matemáticas que hacen funcionar el algoritmo de Liang-Barsky nos damos cuenta de que el parámetro t es en realidad el resultado del producto punto entre ese vector escoba y el vector D que se forma de la diferencia entre las coordenadas iniciales y finales del segmento de linea que estamos cortando. De hecho si el punto final de la linea p1 perteneciera al plano de recorte [p0-Ppl] seria igual a D multiplicada por -1, el parámetro t se eliminaria haciendose igual a uno y nos quedaría la igualdad N.D = N.D. Ahora veamos algunos casos especiales de la aplicación de este interesante algoritmo.

Casos especiales y Validaciones

Antes de simplemente aplicar la fórmula es necesario hacer algunas validaciones muy básicas. Para empezar tenemos que asegurarnos de que el denominador de la fórmula no sea igual a cero y esto solo puede ocurrir en los siguientes casos:

N = 0 Esto solo puede ocurrir si no hay plano de recorte. Ningun plano tiene una normal igual a cero

D = 0 Esto solo puede ocurrir si las coordenadas inicial y final de la linea que queremos cortar son las mismas, esto aunque es raro no es imposible. Sobre todo si la linea es demasiado pequeña o ha sufrido demasiados cortes. Es necesario validar y no cortar este tipo de lineas punto.

El Producto escalar N.D es igual a cero. Si esto sucede es porque la linea que queremos recortar es paralela al plano de recorte (lo que no necesariamente implica que esté contenida en el plano). Si de inicio se valida que los extremos opuestos de la linea estén cada uno a cada lado del plano de recorte esto no debería de pasar.

Una vez que nos hemos asegurado que no vamos a causar una de esas temibles divisiones entre cero ya hemos hecho las suficientes validaciones para asegurarnos que la linea es recortable. Lo siguiente es calcular el vector escoba [p0 – Pp1] y calcular el producto escalar de este con la normal al plano de recorte. Luego esta cantidad la dividimos por lo obtenido en el paso anterior y el resultado va a ser un número entre cero y uno que indica en que parte de la linea se dio el corte. Con este simple número podemos hacer muchas cosas que ahora veremos.

Obtener una coordenada espacial XYZ.-Esto es lo mas básico. Para obtenerla solo sustituimos el valor de t en la ecuación paramétrica de la linea, la cual para los que no la recuerden es p(t) = p0 + (p1-p0) * t. No se les olviden que estas son ecuaciones tridimensionales, así que tienen que repetir el cálculo para X, Y y para Z.

Definir dos nuevas lineas a partir de la linea cortada.-Una vez que obtenemos la coordena del espacio del ejemplo anterior que llamaremos p_corte tomamos el punto inicial p0 de la linea original y definimos como punto final p_corte. La segunda linea tendrá p_corte como su coordenada inicial de modo que una linea [p0, p1] pasa a convertirse en dos [p0, p_corte] y [p_corte, p1].

Ver si un objeto está o no dentro de una distancia.Existe un truculento algoritmo para ver si dos objetos se encuentran dentro de cierta distacia al que llamo “método de contacto por pinchazo”. Imaginen que tienen que hacer que un monstruo lance una mordida al personaje del jugador si este se le acerca a una distacia mínima. Pueden definir una linea invisible entre las fauces del monstruo y el punto mínimo al que va a atacar. Si quitan la validación de que ambos puntos se encuentren en lados opuestos del plano el algoritmo devolverá un valor de t fuera de las fronteras de cero y uno. Sabrán cuando esta linea entre en contacto con la caja de contacto de otro personaje cuando el algoritmo retorne un valor entre cero y uno. Y no solo eso, sino que el valor entre cero y uno dará mas información de cuanto penetró este alfiler en el objeto. Y todo eso sin tener que usar raices cuadradas ni recalcular posiciones en cada comparación. Pues estos alfileres pueden moverse junto con los modelos 3d del juego. Una aplicación mas obvia de esto son los detectores laser que aparecen en los videojuegos de espias o de acción stealth.

Existen otras aplicaciones del algoritmo de recorte como por ejemplo determinar si algo está dentro de una linea de vista o si se puede eliminar de la vista sin peligro de que se vea la toma alterada. Esa es la eliminación da partes ocultas que veremos muy pero muy en el futuro. Por ahora es mejor dejar esto del recorte como está porque ya vimos suficientes matemáticas por hoy.

En realidad este tema del recorte debimos de haberlo visto hace mucho, mucho antes de que entráramos a la generación de vista en 3D. La razón por la que lo discutimos hasta ahora fue porque es hasta que se genera una vista en primera persona que los algoritmos de recorte se vuelven verdaderamente imprescindibles. Otra razón de esto es porque el algoritmo de Liang-Barsky es mucho mas sencillo de entender en 3 dimensiones. De hecho en los libros que lo mencionan lo explican en dos. El problema es que en dos dimensiones los planos quedan como lineas rectas y el recorte parece estarse haciendo entre dos lineas rectas.

En las siguientes entradas vamos a ver como se genera el volumen de vista y como cortamos una porcion del mundo para proyectarlo en una pantalla de computadora. De momento no voy a hacer un ejemplo de recorte porque la fórmula anterior es lo bastante sencilla para que la intenten ustedes por su cuenta. En cuanto termine las entradas sobre volumen de vista vamos a hacer una práctica donde se pondrán en práctica tanto la aplicación de las Coordenadas de Referencia Visual (o cámara para que me entiendan los grafistas), el recorte en el espacio y el volumen de vista en una misma toma en 3D. Nota aparte, sin contar unos pocos comentarios en las entradas de programación gráfica, llevo casi 4 meses sin insultar. Y aunque me dan ganas de seguir así hay tantas cosas “lulzosas” que me gustaría contar. Pero creo que mejor los dejo como comentarios al margen y llevo estas entradas de programación gráfica al menos hasta el detalle de superficies y eliminación de partes ocultas.

Anuncios

marzo 29, 2012 - Posted by | Uncategorized | , ,

Aún no hay comentarios.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s

A %d blogueros les gusta esto: