Teoría Informática Gráfica Tema 6-11 (PDF)

Tema – 6 Texturizado Nuño Basurto Hornillos [email protected] Informática Gráfica Grado en Diseño de Videojuegos –...

Tema – 6 Texturizado Nuño Basurto Hornillos [email protected] Informática Gráfica Grado en Diseño de Videojuegos – Curso 2024 - 2025 Área de Ciencia de la Computación e Inteligencia Artificial – Departamento de Digitalización Características superficiales › Hay una gran variedad de acabados superficiales que otorgar a las figuras. › Todas las diferentes posibilidades de acabados, debemos ser capaces de imitarlos a través del uso de la computación gráfica. › Para ello debemos tener en cuenta que las figuras poseen diferentes propiedades que debemos tener la capacidad de reproducir. 2 Características superficiales II › Las características, son la siguientes, muchas de ellas las estudiamos en el tema anterior. – Color: Es una de las características que más fácilmente percibimos a través de nuestros ojos. El color tiene más de una variable que lo maneja, como por ejemplo la dispersión, o difusión, que nos da la capacidad que tiene una figura para controlar la cantidad y el color que es capaz de dispersar un objeto. Por otro lado, también está el color ambiente que controla la sensibilidad de la figura a la luz ambiente. 3 Características superficiales III – Especularidad: Controla los brillos de la figura, a más especularidad más brillantez y por otro lado a menor, mayor apariencia de color mate. – Reflectividad: Control de los reflejos en el entorno de la figura. Realmente cuando miramos un objeto percibimos el color que refleja, no el que tiene. – Transparencia: A mayor valor de dicha característica, mayor capacidad tendremos de observar el otro lado de la figura, así mismo, nosotros distinguimos por nuestra vista los reflejos, destellos y deformaciones que se producen. – Refracción: Aquella deformación resultada de una interacción. Por ejemplo, lo que hay debajo de una lupa aumenta de tamaño. Índice de refracción. 4 Características superficiales IV › Las comentadas anteriormente son las características principales, pero hay más como la luminancia y la causticidad. › Si modelamos perfectamente un objeto, este puede perder cierto realismo si no tenemos en cuenta las características superficiales. › Otra característica para tener muy en cuenta, pero que posee una mayor importancia a las aquí expuestas, es la textura. 5 Texturizado › Algunos objetos pueden ser modelados simplemente teniendo en cuenta lo comentado hasta ahora. › Pero esto, no ocurre con la inmensa mayoría de las cosas que nos encontramos a nuestro alrededor, véase una silla de cuero donde queremos otorgarle esa característica, por ejemplo. › Definimos texturizado de la siguiente manera: “Es el proceso que toma una superficie y modifica su apariencia a partir de imágenes, funciones u otros tipos de datos.” 6 Texturizado II › Las texturas también se emplean para almacenar una gran cantidad de datos que luego se envían a los shaders. › Permiten agregar detalles sin la necesidad de agregar más polígonos a las figuras. › El texturizado funciona modificando los valores utilizados en la ecuación de shading, un ejemplo de ecuación de shading la vimos en el tema anterior con el modelo de Phong. › Esos valores son modificados basándose en la posición de la superficie. 7 Texturizado III › Cada uno de los valores de las texturas cambia el resultado de la ecuación de shading. › Cada pixel que se utiliza en la imagen de la textura se denomina texel. 8 Texturizado IV › El resumen de la imagen anterior sería el siguiente: 1. Se establece una posición en el espacio que se considera como el punto inicial del texturizado. 2. A este punto se le aplica una función proyector para obtener un conjunto de números llamados “coordenadas de textura”, estos se utilizarán para acceder a la textura. Este proceso es denominado mapping. 9 Texturizado V 3. Antes de acceder a los valores que dicen dónde está la textura, se aplican las corresponder functions, que permiten transformar las coordenadas de la textura a texture-space o espacio de textura. 4. Las posiciones texture-space son utilizadas para obtener valores de la textura. 5. Los valores obtenidos se pueden transformar nuevamente con una value transform function y son utilizados para modificar alguna propiedad de la superficie, como el material o la shading. 10 Texturizado VI 11 Texturizado VII 1. Se encuentra la posición (x,y,z) en el marco de referencia del objeto. 2. Se aplica la función proyector, la cual realiza la proyección del punto en el espacio (3 dimensiones) a texture coordinate space (2 dimensiones). Este punto en la superficie puede ser transformado en un par de valores dentro de un rango 0 a 1. 12 Texturizado VIII 3. Estas coordenadas de textura son usadas para encontrar el color de la imagen en esa posición. La corresponder function transforma esos valores según la resolución de la imagen (ejemplo anterior 256x256, multiplica (u,v) por 256). 4. Tras encontrar el píxel en la imagen de la textura, se obtiene el color de este. 13 Función Proyector › Las coordenadas de textura, que son obtenidos tras la aplicación de la función proyector, pueden ser generadas mediante diferentes tipos de parámetros, tales como la dirección de la vista, la temperatura de la superficie o cualquiera otro. › Para modelos más complejos, las coordenadas de textura se pueden asignar de forma semiautomática al desenvolver la malla en una cuadrícula 2D en un software de modelado 3D como, por ejemplo: Blender. 14 Función Proyector II › En los proyectos de tiempo-real, las funciones de proyección generalmente se aplican en la etapa de modelado, y los resultados se almacenan en los vértices. › A veces es ventajoso aplicar la función de proyección en el vertex- shader o pixel-shader. De este modo se puede aumentar la precisión y ayuda a la implementación de diferentes efectos, como la animación. 15 Corresponder Function › Corresponder functions convierten las coordenadas de texturas a posiciones en el espacio de textura. › Proveen de flexibilidad en la aplicación de texturas a superficies. › Un tipo de estas funciones realizan una transformación matricial que puede ser aplicada en el vertex o pixel shader y permite la traslación, rotación, escalamiento o proyección de la textura en la superficie. 16 Texturizado de imágenes › Hay diferentes técnicas que podemos aplicar dependiendo del tamaño de la imagen y de la textura: – Magnificación, se realiza cuando muchos píxeles representan un texel. – Minimización, o minificación se da cuando muchos texels se encuentran dentro de un píxel. 17 Texturizado de imágenes II 18 Texturizado de imágenes III › Las técnicas de filtrado más comunes cuando se lleva a cabo una magnificación son: – nearest neighbor: Genera pixelation ya que el método se basa en tomar el valor del texel más cercano al centro del píxel. – bilinear interpolation: Para cada píxel, este tipo de filtrado encuentra los cuatro texels adyacentes e interpola linealmente en dos dimensiones para encontrar un valor combinado para el píxel. › En el segundo método obtenemos una imagen más borrosa, y gran parte de la irregularidad de utilizar el primero desaparece. 19 Texturizado de imágenes IV › Se amplía una imagen de 48 x 48 a 320 x 320. La imagen de la izquierda usa nearest neighbor, la del centro bilinear interpolation, por último, la de la derecha cubic interpolation. 20 Texturizado de imágenes V › En cuanto a la minimización, hay que tener en cuenta lo costoso que puede resultar obtener el color correcto, mediante la integración del efecto de todos los texels que influencian un pixel. Para ello se utilizan los mismos métodos vistos anteriormente: – nearest neighbor: por ejemplo: selecciona el texel visible en el centro de la celda del píxel. Causa problemas de aliasing. – bilinear interpolation: Fusiona cuatro texels en lugar de usar solo uno, pero cuando un píxel está influenciado por más de cuatro texels, el filtro falla rápidamente y produce aliasing. 21 MipMapping › Teniendo en cuenta estos problemas resultantes de la minimización como es el aliasing, hay diferentes técnicas que se utilizan. › Una de las más populares en el texturizado es el MipMapping. › Se genera una colección de imágenes de texturas, donde cada textura subsiguiente es un cuarto del área del anterior. › Además, cada cierta distancia desde el observador, se utilizará una textura de mipmap diferente que mejor se adapte a la distancia al objeto. 22 MipMapping II MipMapping 23 MipMapping III › Cada valor de texel es calculado como un promedio de los 4 texel vecinos, es decir, utiliza interpolación. › La reducción se realiza constantemente hasta que cada una de las dimensiones de la textura equivale a un texel. › Se computa el nivel de detalle de la textura “d”, posteriormente los valores (u,v,d), son utilizados para acceder al mipmap. › El objetivo es encontrar la textura que mejor se aproxime a la proporción de píxeles-texel de 1:1, si no, obtener las dos texturas que se encuentran por encima y debajo de “d”. 24 MipMapping IV › La posición (u,v) se utiliza para obtener una interpolación bilinear de cada uno de estos niveles. Este resultado es posteriormente interpolado linealmente. Proceso que se llama interpolación trilinear. › Uno de los problemas del MipMapping es que produce Overblurring: – “Pérdida de detalle, como líneas finas o patrones haciendo que la superficie se vea plana y poco realista” , diríamos que vendría de un desenfoque. › Este se da cuando un pixel cubre una gran cantidad de texels en una dirección, pero muy pocos en la otra. 25 MipMapping V › Cabe la posibilidad que necesitemos realizar minimización a lo largo de un eje de la textura y magnificación en el otro. › Cuando accedemos al mipmap, únicamente se obtienen área cuadradas de la textura, no pudiendo recuperar las rectangulares. › Para evitar el aliasing, elegimos la medida más grande de la cobertura aproximada de la celda del píxel en la textura. Produciendo una muestra relativamente borrosa. 26 MipMapping VI › Por ejemplo, si la textura principal tiene un tamaño de 256 por 256 píxeles (típicamente las texturas son cuadradas y el largo de sus lados es un múltiplo de dos). › El conjunto de mipmaps asociados podría ser de ocho imágenes, cada una de un cuarto del tamaño de la anterior: 128×128 pixels, 64×64, 32×32, 16×16, 8×8, 4×4, 2×2, 1×1 (un único píxel). › Si la escena renderiza esta textura en un espacio de 40×40 píxeles, se usaría una interpolación entre los mipmaps de 64×64 y 32×32. La manera más simple de generar la textura es por promedios sucesivos, pero pueden emplearse algoritmos más sofisticados (basados en el procesamiento de señales y las transformadas de Fourier). 27 MipMapping VII 28 Summed-Area Table › Se trata de un método que trata de evitar el Overblurring. › Para ello se crea un array del tamaño de la textura con una mayor cantidad de bits de precisión para el color a guardar. › En cada posición de este array, se debe calcular y guardar la suma de todos los texels de la textura correspondientes al rectángulo formado por esta posición y el texel (0,0). 29 Summed-Area Table II › Posteriormente se accede a este array para determinar el color promedio del rectángulo, que luego es pasado como el color de la textura en el píxel. 30 Summed-Area Table III › La imagen anterior, representa la fase durante el texturizado, donde el píxel es proyectado en la textura. › Luego se accede a la tabla para determinar el color promedio del rectángulo. Este promedio se calcula utilizando las coordenadas de textura del rectángulo y los valores de la tabla. › Es un algoritmo de los denominados anisotropic filtering. Estos tratan de obtener los valores de los texels en áreas que no son cuadradas. 31 Summed-Area Table IV › En el ejemplo mostrado las líneas que van hacia el horizonte son más nítidas cerca del borde derecho, pero las líneas que se cruzan diagonalmente en el centro aún están borrosas. › El problema es que cuando se ve una textura a lo largo de su diagonal, se genera un gran rectángulo, con muchos de los texels situados lejos del píxel que se calcula. 32 Filtrado Anisotrópico › El filtrado anisotrópico difiere de la configuración de calidad de la textura. En lugar de cambiar una textura por una versión de mayor resolución, modifica la apariencia de la textura para tener en cuenta el ángulo de visión. › Mejora la apariencia de las texturas vistas en ángulos oblicuos, en lugar de rectos. › Para las tarjetas gráficas actuales, el método más común para mejorar el filtrado de texturas es reutilizar el hardware existente para mipmap. › A diferencia de otras, que tratan las texturas como si fueran perpendiculares a la cámara, el filtrado anisotrópico modifica las texturas para tener en cuenta la perspectiva 33 Filtrado Anisotrópico II › Los téxels no se obtienen a partir de una forma simétrica, sino mediante el uso de un patrón irregular ajustado a la perspectiva (forma anisotrópica). › La forma no está estandarizada, sin embargo, se utilizan patrones rectangulares o trapezoidales o paralelogramos, cuyas formas dependen del ángulo de la superficie. 34 Filtrado Anisotrópico III Para más información, echad un vistazo a este video: What Is Anisotropic Filtering? - PC Graphics Settings Explainer 35 Volume Textures › Proporcionan datos de imagen en tres dimensiones, siendo usados principalmente para imágenes médicas. › Presentan algunas desventajas como unos requisitos de almacenamiento altos y su filtrado es más costoso computacionalmente. › Por otro lado, se evita proceso de encontrar buena parametrización bidimensional para la malla tridimensional, las posiciones tridimensionales pueden usar directamente como coordenadas de textura. 36 Volume Textures II - Izquierda: una textura 3D sólida de ruido aleatorio. - Derecha: la textura tras la convolución integral de líneas. (PDF) Recent Advances in Visualizing 3D Flow with LIC 37 Cube Maps › Consta de seis texturas cuadradas, cada una asociada a una cara de un cubo. › El entorno se proyecta en los lados de un cubo y se almacena como seis texturas cuadradas, o se despliega en seis regiones de una sola textura. › El cubemap se genera renderizando primero la escena seis veces desde un punto de vista, con las vistas definidas por un frustum (tronco) de 90 grados representando cada cara del cubo. › Utilizados comúnmente para environmental mapping. 38 Cube Maps II 39 Procedural Texturing › Las funciones toman uno o varios parámetros como entrada y producen un escalar o un vector como salida. › Los parámetros de entrada pueden ser coordenadas de textura, vectores normales o posiciones de vértices. › Son calculadas en un instante por la GPU mediante la evaluación de una función que describe el patrón de interés. 40 Procedural Texturing II › La ventaja de este enfoque es el bajo coste de almacenamiento y la resolución ilimitada de la textura. › Se utilizan a menudo para modelar superficies de elementos naturales como madera, mármol, granito, metal, piedra y otros. › Se pueden producir patrones de aspecto aleatorio o irregular con funciones de ruido (noise functions) más complejas. 41 Procedural Texturing III Reddit link. 42 Texture Animation › Parte del principio por el cual la imagen que se aplique a una superficie no tiene por qué ser estática. › Un video puede ser utilizado como una textura que cambia de frame a frame. › Las coordenadas de las texturas tampoco tienen que ser estáticas. 43 Texture Animation II › Ejemplo: Textura de agua cayendo en una cascada, para hacer que el agua se mueva, se resta una cantidad de la coordenada correspondiente al flujo de agua. Esto genera el efecto de que la textura se mueve. › Otros efectos más elaborados se pueden obtener aplicando una matriz a las coordenadas de la textura. 44 Material Mapping › Un uso habitual de las texturas es modificar alguna propiedad de un material afectando la ecuación de shading. Los objetos del mundo real tienen propiedades que varían sobre la superficie. › El píxel shader puede leer valores desde las texturas y usarlos para modificar los parámetros del material. › El color de la superficie es el parámetro que más se modifica. Esta textura se conoce como albedo color map o diffuse color map. 45 Material Mapping II Nos encontramos con un nudo metálico, a su derecha las texturas por superficie de color, textura albedo, textura rugosa y textura con campo de altura. 46 Material Mapping III › Dos o más materiales con diferentes ecuaciones de shading y parámetros podrían aplicarse a una misma superficie, teniendo una textura que especifique que áreas de la superficie tienen cada material. Ello provoca que se ejecute un código diferente para cada una. › Como ejemplo, una superficie metálica con algunas regiones oxidadas puede usar una textura para indicar dónde se ubica el óxido y las partes del metal brillante. 47 Alpha Mapping › En vez de representar objetos como árboles como superficies sólidas, se puede utilizar un conjunto de rectángulos con texturas semitransparentes para crear una ilusión de objetos 3D. › Tienen el problema que, si giramos alrededor, la ilusión falla. Una forma es agregar una copia del rectángulo del arbusto rotado unos 90° (“cross tree”). › Combinando alpha maps y texture animation se pueden producir convincentes efectos especiales como antorchas parpadeantes, explosiones, y efectos atmosféricos. 48 Bump Mapping › Métodos generalmente implementados mediante la modificación de la rutina de shading por cada píxel. › Brindan una apariencia más tridimensional que utilizando solo texture mapping, sin agregar geometría adicional. › Esto se logra cambiando las normales de superficie del objeto y utilizando la normal modificada durante los cálculos de iluminación. › El resultado es una superficie aparentemente desigual en lugar de una superficie lisa. 49 Bump Mapping II › La idea es que, en lugar de utilizar una textura para cambiar un componente del color en la ecuación de iluminación, accedemos a una textura para modificar la normal de la superficie. › La normal geométrica de la superficie permanece igual, simplemente se modifica la normal utilizada en la ecuación de iluminación. 50 Bump Mapping III › Del mismo modo que teniendo una normal por vértice da la ilusión de que la superficie es lisa entre triángulos, modificando la normal por píxel cambia la percepción de la superficie del triángulo en sí, sin modificar su geometría. › La normal debe cambiar de dirección con respecto a algún marco de referencia. › Necesitamos definir un sistema de coordenadas local para cada vértice y desplazar la normal en ese sistema de coordenadas. 51 Bump Mapping IV › El sistema de coordenadas utilizado para bump mapping se denomina espacio tangente. › Método de Blinn: El método original guarda dos valores bu y bv en cada texel de la textura. Estos valores corresponden a la cantidad que se debe variar la normal a lo largo de eje u y v. › Estos son luego sumados a la normal para cambiar su dirección. › Este tipo de mapa de texturas es llamado offset vector bump map u offset map. 52 Bump Mapping V › Otra forma de representar introducida por Blinn, es el uso del heightfield (campo de altura). › Cada valor monocromático de la textura representa una altura, por lo que en la textura, el blanco es un área alta y el negro una baja (o viceversa). › El campo de altura es utilizado para derivar los valores de u y v similares a los utilizados en el método anterior. Esto se hace tomando las diferencias entre las columnas vecinas para obtener las pendientes para u, y entre las filas vecinas para v. 53 Bump Mapping VI 54 Normal Mapping › Un método común para bump mapping es directamente guardar un normal map (mapa de normales). › Algoritmos y resultados son matemáticamente idénticos a los métodos de Blinn, sólo el formato de guardado y los cálculos en el pixel shaders cambian. › El mapa codifica (x,y,z) a valores [-1,1], entonces por ejemplo en una textura de 8-bits si en el eje x se tiene un valor de 0, representa -1.0 y 255 dando un valor de → 1.0. 55 Normal Mapping II x: -1 a +1 : Rojo: 0 a 255 y: -1 a +1 : Verde: 0 a 255 z: 0 a 1 : Azul: 128 a 255 › El color [128,128,255], un azul claro, representaría una superficie plana, por ejemplo una normal de [0,0,1] 56 Normal Mapping III Aplicación de Bump Mapping con un normal map, cada canal de color es una coordenada normal de la superficie. La imagen de la derecha es producida por el uso de un normal map. 57 Bibliografía › Melisa Techera – Computación gráfica Avanzada. › A framework for developing and benchmarking sampling and denoising algorithms for Monte Carlo rendering - Jonas Deyson Brito dos Santos 58  Tema – 7 Vistas en 3D Nuño Basurto Hornillos [email protected] Informática Gráfica Grado en Diseño de Videojuegos – Curso 2024 - 2025 Área de Ciencia de la Computación e Inteligencia Artificial – Departamento de Digitalización Introducción › La proyección es una transformación que convierte la representación tridimensional de una escena, sobre un plano bidimensional, es decir, la pantalla. › Debemos proyectar toda nuestra escena 3D sobre un plano, para convertirlo en un dibujo 2D. › Finalmente, este dibujo plano se traslada a la pantalla. 2 Introducción II 3 Teoría de las proyecciones › La proyección de un punto viene definida por la intersección entre el plano de proyección y el rayo que une dicho punto con el centro de proyección. Para dibujar la línea usaremos Bresenham. 4 Tipos de proyecciones › La proyección más usada es la proyección geométrica planar. – Se llama geométrica cuando los rayos de proyección son rectos – Se llama planar cuando la superficie de proyección es un plano › Existe otro tipo de proyecciones: https://www.thetruesize.com 5 Tipos de proyecciones II › La proyección geométrica planar es de dos tipos: – Paralela: la distancia es infinita, sólo se especifica la dirección de vista, por ende, todos los rayos son paralelos. – Perspectiva: la distancia del centro de proyección al plano es finita. 6 Proyección paralela › El caso más sencillo es la proyección paralela ortográfica. – El plano de proyección es uno de los planos principales (ejemplo plano XY). – La dirección de proyección es el eje perpendicular (ejemplo eje Z). › Solamente hay que eliminar la componente Z. 7 Proyección paralela II › Se pierde información sobre la profundidad. › Las líneas paralelas permanecen paralelas. › Los ángulos sólo se mantienen en las caras paralelas al plano de proyección. 8 Proyección paralela III › Es inmediata de calcular. › Se utiliza en programas de modelado, donde se muestran tres vistas simultáneas del objeto. 9 Proyección perspectiva › Simula el comportamiento de una cámara o del ojo humano. › Aumenta el realismo de la imagen, al dar sensación de profundidad › El tamaño de un objeto varía de forma inversamente proporcional a la distancia del objeto al plano de proyección, › No es útil para reconocer formar ni medir longitudes: – Las distancias son falsas – Los ángulos no se mantienen – Las líneas paralelas dejan de serlo 10 Proyección perspectiva II 11 Paralela vs perspectiva 12 Cálculo de las expresiones › Generalmente se usa un sistema de mano izquierda, donde – El eje Z representa la dirección de vista – El eje Y representa la vertical del observador – El eje X representa la horizontal del observador 13 Cálculo de las expresiones II › Sea Q=(x,y,z) un punto 3D que se proyecta sobre el punto Q’=(x’,y’) o también Q’=(u,v). Es decir, de 3D a 2D. › Queremos calcular las coordenadas de Q’ a partir de Q. › La distancia D al plano de proyección se supone conocida. 14 Cálculo de las expresiones III › Se resuelve por la regla de los triángulos semejantes: 15 Cálculo de las expresiones III › Los objetos más alejados, (mayor valor de z) tienen componentes más pequeñas. › La expresión es válida también para puntos detrás del plano y del ojo. 16 Obtención de la matriz de perspectiva › La expresión final para la perspectiva es: › ¿Cómo pasarlo a forma matricial? › Inicialmente parece imposible, pues no es una expresión lineal. › Necesitaremos usar la componente homogénea. 17 Obtención de la matriz de perspectiva II › De esta forma la matriz queda: 18 Obtención del resultado › Después de aplicar la matriz el resultado queda: › Para obtener las coordenadas 2D del punto proyectado, dividimos x e y por la componente homogénea. 19 Obtención del resultado II › Es aconsejable seguir utilizando coordenadas homogéneas, como hemos ido viendo hasta el momento con todo lo relacionado con las transformaciones: – Código más sencillo y eficaz. – Permiten recuperar el punto original a partir del proyectado. 20 Transformación de vista › En un caso general, el ojo puede estar en cualquier posición, mirando en cualquier dirección (por ejemplo, un modelo cargado en Unity). › La transformación de vista consiste en cambiar el sistema de coordenadas global de toda la escena a otro sistema centrado en el ojo. › El paso final será realizar la proyección perspectiva en el nuevo sistema para obtener la proyección final. 21 Transformación de vista II 22 Transformación de vista III › El plano de proyección suele venir definido por un punto del plano (VRP) y un vector normal perpendicular (VPN). › También hace falta un vector que indique la verticalidad del observador (VUP). › La posición del ojo también ha de ser conocida (COP). › El punto COP será el origen del sistema de referencia 3D para hacer la perspectiva. 23 Transformación de vista IV › Normalmente el observador no puede ver la escena completa. 24 Transformación de vista V › Hay que definir una ventana rectangular en el interior del plano de proyección para delimitar la foto. › La ventana y el ojo forman una pirámide, volumen/amplitud de vista. › La línea entre el ojo y el centro de la ventana (C) indica la dirección de vista. › La pirámide de vista suele truncarse por dos planos de recorte. › El objetivo es evitar objetos muy lejanos o excesivamente cercanos. En Unity, podréis establecer una distancia focal de la cámara. 25 Transformación de vista VI Ventana rectangular 26 Obtención de los vectores del nuevo sistema › Lo primero es obtener los 3 vectores del sistema de referencia del ojo (u,v,w), que equivaldrían a (x,y,z). › El vector w siempre coincide con el vector normal al plano, VPN. w = VPN › El vector v suele ser VUP, excepto cuando VUP no pertenece al plano de proyección. 27 Obtención de los vectores del nuevo sistema II › En ese caso hay que proyectarlo (proyección de vector sobre plano): v = VUP - (VPN ⋅ VUP) VPN › El vector u es perpendicular a los dos anteriores, apuntando a la derecha del observador: u = VPN · v 28 Construcción de la matriz de vista › A continuación, hay que hacer un cambio de sistema de referencia para pasar del sistema de coordenadas global al sistema del ojo. › Para ello se usa la fórmula para el cambio de sistema de referencia: – Trasladar el sistema nuevo al viejo. – Rotar la cámara para hacer coincidir los sistemas. M = T(-ox, -oy, -oz) · R 29 Construcción de la matriz de vista II › Los vectores (u,v,w) deben estar normalizados. 30 Construcción de la matriz de vista III › Cuando la dirección de vista (línea roja discontinua) no coincida con el eje Z, habrá que realizar un afilamiento para que coincidan. › Mediante las ecuaciones paramétricas de la recta que une el ojo (0,0,0) y el centro de la ventana C. 31 Construcción de la matriz de vista IV › La recta que se quiere afilar es: › La expresión para el afilamiento es: 32 Construcción de la matriz de vista V › La matriz es: › Quedando la matriz final, M de la siguiente forma: M = T(-ox, -oy, -oz) · R · A 33 Etapas de creación de la imagen 34 Recorte 3D › Antes de proyectar la imagen debemos recortar la escena frente al volumen de visualización. 35 Recorte 3D II › Básicamente se trata de un problema de intersección de rectas y planos. › Las rectas son las aristas de los polígonos. › Los planos son las 6 caras del volumen de visualización. 36 Algoritmo de Cohen-Sutherland 3D › Se ejecuta primero un test inicial para reducir el número de intersecciones a calcular. › A cada extremo de la línea le asignamos un código de 6 bits. › Cada bit indica si el punto está a un lado o a otro de cada cara. › Esta técnica permite determinar qué partes de un segmento de línea están dentro de un volumen específico 37 Algoritmo de Cohen-Sutherland 3D II › Caja de Recorte (o Volumen de Vista): – Se define por seis planos que forman un cubo en 3D. – Estos planos son: › Frente y detrás (planos near y far). › Superior e inferior (planos top y bottom). › Izquierda y derecha (planos left y right). › Códigos de Región: Cada punto en el espacio 3D se asocia con un código binario de 6 bits que representa la posición del punto con respecto a los seis planos de la caja de recorte. 38 Algoritmo de Cohen-Sutherland 3D III – Bit 1: a la izquierda del plano izquierdo. – Bit 2: a la derecha del plano derecho. – Bit 3: por debajo del plano inferior. – Bit 4: por encima del plano superior. – Bit 5: detrás del plano far. – Bit 6: delante del plano near. – Por ejemplo, un código 000000 significa que el punto está dentro del volumen de recorte. 39 Algoritmo de Cohen-Sutherland 3D IV › Cuando se usa proyección paralela, el volumen de vista es un cubo, como se comentaba con anterioridad. › En ese caso, los bits del código se calculan con simples restas (y-ymax). 40 Algoritmo de Cohen-Sutherland 3D V › Evaluación de los posibles casos: – Caso de aceptación: Si los códigos de región de ambos puntos son 000000, el segmento de línea está completamente dentro del volumen de recorte y se acepta. – Posible caso de rechazo: Si los códigos de región de ambos puntos tienen al menos un bit en común, el segmento de línea está completamente fuera del volumen de recorte y se rechaza. – Caso de rechazo: Si ninguno de los casos anteriores se aplica, el segmento de línea cruza uno o más planos del volumen de recorte, y se necesita recortarlo. 41 Algoritmo de Cyrus-Beck 3D › Es un método de recorte de líneas en gráficos por computadora que se utiliza para recortar segmentos de línea contra un poliedro convexo en un espacio tridimensional (3D). › A diferencia del algoritmo de Cohen-Sutherland, que solo puede manejar cajas de recorte rectangulares, el algoritmo de Cyrus-Beck es más general y puede manejar cualquier volumen de recorte convexo. 42 Algoritmo de Cyrus-Beck 3D II › Se elige un punto F arbitrario para cada cara. Un segmento en línea 3D se representa bajo la siguiente ecuación paramétrica. › Sea P(t) un punto sobre el segmento, t en [0,1]: P(t) = P0 + t (P1 − P0) – P0 es el punto de inicio del segmento. – P1 es el punto final del segmento. – 𝑡𝑡 es un parámetro que varía entre 0 y 1 para definir puntos en el segmento de línea. 43 Algoritmo de Cyrus-Beck 3D III › Sea v(t) el vector desde F hasta un punto cualquiera del segmento: v(t) = P(t) − F › Sea el producto escalar: Ni· v(t) › También podemos dos tipos de planos: – Plano de entrada: Si el segmento de línea está entrando al poliedro al cruzar el plano (esto ocurre cuando el denominador de la fórmula de 𝑡𝑡 es negativo). – Plano de salida: Si el segmento está saliendo del poliedro al cruzar el plano (denominador positivo). 44 Algoritmo de Cyrus-Beck 3D IV › El valor de 𝑡𝑡 puede ser negativo o mayor que 1 al calcular la intersección con el plano. Sin embargo, al definir los puntos del segmento, el algoritmo solo considera los valores de 𝑡𝑡 dentro de [0,1]. Los valores fuera de este rango se descartan porque representan intersecciones fuera del segmento de línea original. Estos valores son lo que se tienen en cuenta para los planos. › Desarrollando y despejando t obtenemos la formula (cuidado con que no llegue a 0 el denominador): 45 Algoritmo de Cyrus-Beck 3D V › Aplicando la fórmula obtenemos los 6 valores de t que indican las intersecciones de la línea con las 6 caras del poliedro. › Los valores de t fuera del rango (0,1) se descartan. › Cada valor de t se etiqueta como entrante (tE) o saliente (tS), según entre o salga con respecto al volumen. 46 Algoritmo de Cyrus-Beck 3D VI › Para saber el valor de t, miraremos el signo de Ni · (P1 - P0) : – Si es positivo es un punto entrante – Si es negativo es un punto saliente › La solución viene dada por el tramo de línea entre el PE más alto y el PS más bajo. › Si tE > tS → la línea no se dibuja. 47 Resumen 48  Tema – 8 Representación de sólidos Nuño Basurto Hornillos [email protected] Informática Gráfica Grado en Diseño de Videojuegos – Curso 2024 - 2025 Área de Ciencia de la Computación e Inteligencia Artificial – Departamento de Digitalización Introducción › Numerosas aplicaciones (como CAD/CAM) requieren trabajar con elementos tridimensionales que permitan calcular propiedades. › Tales como el volumen, dimensiones, tensiones, temperaturas, y realizar operaciones como unir objetos, calcular intersecciones y detectar colisiones entre elementos (por ejemplo, un robot y un objeto). 2 Introducción II › En otros casos, el objeto diseñado debe fabricarse mediante algún proceso automático, por lo que es esencial asegurar que represente un sólido real. › El modelado de sólidos es el conjunto de teorías, técnicas y sistemas dedicados a la representación "completa en cuanto a información" de sólidos. › Esta representación debe permitir, al menos en teoría, calcular automáticamente cualquier propiedad bien conocida de cualquier sólido almacenado. 3 Introducción III › Con los sólidos representados, además de visualizarlos y editarlos, es necesario calcular sus propiedades físicas (como su peso o su centro de gravedad) y simular en ellos procesos físicos, como la transmisión de calor en su interior. 4 Introducción IV › Antes de abordar el proceso de representación, es fundamental definir con precisión los objetos que deseamos representar. › Esto implica establecer una comprensión clara de lo que se considerará como un “sólido” en el contexto del modelado. › Formalizar el concepto de sólido permite crear un marco consistente que guíe las técnicas de modelado y las propiedades físicas que se pueden asociar a estos objetos. 5 Introducción V › Hay dos enfoques distintos para abordar el problema: – El primero caracteriza a un sólido como un modelo topológico o un conjunto de puntos en el espacio. – El segundo define matemáticamente a un sólido a partir de la superficie que lo delimita, es decir, su piel o frontera, se denomina modelo algebraico. › De esta manera, se establece un sistema de representación compuesto por tres niveles: sólidos físicos, modelos matemáticos de sólidos y sus representaciones. 6 Modelo topológico › Los sólidos están definidos en el espacio Euclídeo (E3) ocupando una determinada porción del espacio. Podemos por tanto considerar un sólido como un conjunto de E3. › No todos los subconjuntos encontrados dentro de E3 son sólidos, como puede ser el cado de una recta apartada. › Para que un conjunto de puntos represente un sólido en un nivel abstracto, es necesario que cumpla con ciertas condiciones específicas. 7 Modelo topológico II › Las condiciones que satisfacer son tres: – Es cerrado y acotado. Esto es contener su frontera y ocupar una porción finita del espacio. – Es rígido. Los sólidos no se deforman al trasladarlos o rotarlos. O lo que es lo mismo, dos sólidos que se diferencian tan solo en una transformación rígida son realmente el mismo sólido. – Homogeneidad tridimensional. El sólido debe ser tridimensional en todos sus puntos, es decir, en cualquier punto de él debe ser posible en tres direcciones ortogonales › Esta última propiedad se suele caracterizar mediante el concepto topológico de regularización, donde la regularización de un sólido se define como la clausura de su interior: r(S) = c(i(S)) 8 Modelo topológico III › El interior de un conjunto es el subconjunto de sus puntos que no están en su frontera. › La clausura de un conjunto es el conjunto formado por todos sus puntos y todos sus puntos adherentes, es decir, aquellos que están es su frontera. › Se dice que un conjunto es regular si es igual a su regularización. S = r(S) 9 Modelo topológico IV › Es fácil comprobar que cualquier punto o plano aislado no estará en la regularización del conjunto, es decir, ser regular es equivalente a ser tridimensional en todos sus puntos. › Un conjunto regular acotado se denomina un r-set. Este objeto no es regular por tener elementos 2D y 1D 10 Modelo algebraico › El modelo algebraico describe un sólido a partir de su frontera (conjunto de superficies que separa el sólido de la parte del espacio no ocupada por él). › La frontera se puede ver como la piel del sólido. Obviamente cualquier superficie no determina un sólido. › Para que un conjunto de superficies describa un sólido deben satisfacer una propiedad. 11 Modelo algebraico II › Encierra un volumen. La “piel” es cerrada, orientada y completa. Que la piel sea cerrada y esté orientada permite determinar si un punto está dentro del sólido, y por tanto obtener el modelo topológico. › Los dos modelos son equivalentes, con determinadas restricciones. 12 Modelo algebraico III › Para que el sólido sea representable se suele imponer una condición adicional de suavidad en su frontera, más concretamente se suele exigir que la frontera sea algebraica, es decir, debe ser representable por un polinomio de grado finito. › Este modelo nos permite utilizar representaciones de los sólidos basadas en el almacenamiento de la frontera, que es una entidad bidimensional. 13 Modelo algebraico IV › Para facilitar la representación se suele exigir, además que la frontera sea 2-manifold, esto es, cada punto de la frontera es homeomorfo a un disco en E2. Dos pirámides unidas por un vértice no son 2-manifold. 14 Modelo algebraico V › Se dice que la frontera de un sólido es un 2-manifold, cuando implica que cada punto de la superficie del sólido tiene un entorno que se comporta como una porción de un plano bidimensional, o en términos más formales, como un espacio localmente euclidiano de dos dimensiones. › Se consta de un entorno localmente plano, que no tiene agujeros o auto intersecciones y que posee una consistencia geométrica. 15 Propiedades de representación › Un método de representación de sólidos establece una relación entre sólidos y descripciones de estos. Las representaciones de sólidos tienen los siguientes atributos y propiedades formales: – Dominio: El dominio del método de representación es el conjunto de objetos representables por él. Idealmente será el conjunto de sólidos. – Validez. Una representación es invalida si no corresponde a ningún sólido real. Es importante que el método de representación asegure de por sí la validez de todas las representaciones que se pueden crear o que existan procedimientos automáticos para comprobar la validez de las representaciones. 16 Propiedades de representación II – No ambigüedad: Un método es no-ambiguo si cada representación se corresponde con un único objeto real. Es deseable que el método no sea ambiguo. – Unicidad: Se dice que existe unicidad en el método de representación si cada objeto real tiene, a lo sumo, una posible representación. Si el método no asegura la unicidad no es posible comprobar la igualdad de objetos. › Otras propiedades interesantes de las representaciones son: – Ocupación de memoria. – Facilidad de creación y edición. – Facilidad de visualización y cálculo. 17 Propiedades de representación III › Ambigüedad del uso del modelo de alambres. 18 Operaciones regularizadas › Una de las formas más usuales, y naturales, de editar sólidos es combinarlos usando operaciones booleanas, unión, intersección y diferencia (se usa la diferencia en lugar del complemento dado que el complemento produciría un objeto no acotado). › No obstante, las operaciones booleanas, tal como se definen habitualmente, no son internas al conjunto de sólidos. › Es decir, pueden producir, como resultado, objetos que no sean sólidos 19 Operaciones regularizadas II › Para resolver este problema se utilizan operaciones booleanas regularizadas. › Las operaciones regularizadas se definen como la regularización del resultado de la operación, y se denotan con un asterisco. 20 Operaciones regularizadas III › El conjunto de sólidos con las operaciones regularizadas constituye un álgebra de Boole. 21 Operaciones regularizadas IV AyB A∪B A∩B A– B B– A 22 Métodos de representación › Se han propuesto un gran número de esquemas de representación para sólidos. En esta sección se hace una breve introducción a algunos de estos métodos. › En el resto del tema se verán con más detalle tres de estos métodos. 23 Métodos de representación II › Instanciación de primitivas. El modelo se representa como un conjunto de primitivas que se instancian en el espacio. Para poder realizar cálculos es necesario que las diferentes instancias no se solapen en el espacio. El dominio depende del repertorio de primitivas. 24 Métodos de representación III › Barrido (sweep). Se puede ver como una generalización de los métodos de desarrollo de superficies a partir de curvas. El elemento a desplazar es ahora una superficie, que describe un volumen al desplazarse a lo largo de una trayectoria o al rotarse. 25 Métodos de representación IV › Descomposición. El sólido se describe en base a una descomposición del espacio en una colección de elementos simples disjuntos, celdas (por ejemplo, tetraedros o cubos). La representación de un sólido es el conjunto de celdas que ocupa. Ejemplo de una enumeración espacial 26 Métodos de representación V › Fronteras. El sólido se representa mediante un conjunto de caras que describen su frontera. La mayor parte de los sistemas utilizan representaciones de fronteras, con caras poligonales. 27 Métodos de representación VI › CSG. Se almacena una expresión booleana que construye el sólido a partir de primitivas simples. 28 Métodos de representación VII › ASM. El modelado analítico de sólidos describe los sólidos a partir de mallas 3D de puntos de control, combinados usando funciones mezcla, generalizando los métodos de diseño de superficies. 29 Representación de fronteras › El método de representación de fronteras (b-rep, de “boundary representation”) se basa en la descripción algebraica de los sólidos, asumiendo que están delimitados por un conjunto de caras, que pertenecen a superficies orientables y cerradas. › La orientación implica que es posible distinguir la cara exterior de la interior al sólido. La orientación suele estar indicada por el vector normal a la superficie. 30 Representación de fronteras II › El método surge a partir de los modelos poliédricos usados para la representación de objetos con eliminación de líneas y caras ocultas. Se puede ver como una mejora de modelo para poder describir sólidos incluyendo toda la información de la superficie. › En él los sólidos se describen dando la geometría de su superficie (frontera), normalmente formada por un conjunto de caras planas, y las relaciones topológicas existentes. 31 Representación de fronteras III › Para ello se distingue entre entidades geométricas (puntos, curvas, superficies) y topológicas (vértices, aristas y caras). › La superficie de una cara es el plano que sustenta la cara. › Las relaciones topológicas incluyen relaciones de vecindad y de pertenencia, de varias formas. 32 Representación de fronteras IV › Las caras están delimitadas por aristas. › Las aristas están delimitadas por dos vértices. › Cada arista es compartida por dos caras. › En cada vértice confluyen varias aristas (al menos tres) › Vecindad entre caras. 33 Representación de fronteras V › Cuando las caras permitidas por el sistema son polígonos el conjunto de objetos representable es el conjunto de poliedros. › En este caso, las caras deben ser polígonos cualesquiera, incluyendo polígonos cóncavos y con agujeros (de otro modo el conjunto de presentaciones no sería cerrado bajo operaciones booleanas). › Por este mismo motivo se suele considerar como un único sólido un conjunto de poliedros separados. 34 Representación de fronteras VI › Existen diversas representaciones que permiten almacenar modelos de fronteras. Su complejidad varía en función de las relaciones topológicas almacenadas. › La opción más simple es no almacenar ningún tipo de relación, con lo que la representación puede ser una simple lista de caras. › No obstante, esta aparente simplicidad en la estructura de datos da lugar a procesos complejos para realizar cualquier operación con el modelo, desde la comprobación de validez hasta la edición o cálculo. 35 Representación de fronteras VII › A modo de ejemplo, supongamos que deseamos comprobar que la frontera es cerrada (condición indispensable para que la representación sea válida). › Tendremos que comprobar que en cada arista confluyen dos caras con la misma orientación. › Para ello tendremos que comparar cada par de puntos consecutivos de cada cara con los pares de puntos consecutivos del resto de las caras. Este proceso es complejo (depende del cuadrado del número de caras) e impreciso, la comparación de puntos puede generar errores numéricos. 36 Representación de fronteras VIII › Obsérvese que esta es la estructura habitualmente usada en los sistemas que dibujan poliedros, cuando no interesa editar el objeto como un sólido, ni que represente un sólido válido, ni calcularle propiedades. › Por otra parte, esta estructura es muy redundante, los puntos asociados a cada vértice se almacenan en la lista de puntos de cada cara que comparte el vértice. › La existencia de información redundante conlleva la utilización de un mayor espacio, y puede ser origen de inconsistencias. 37 Ejemplo › La siguiente tabla muestra la representación de las dos caras visibles del poliedro de la figura. 38 Ejemplo II › Una alternativa simple es almacenar el modelo en una estructura jerárquica heterogénea, en la que la información asociada a cada cara sea una lista de aristas, y la normal a la cara. › De cada arista se almacenen los dos vértices que la delimitan, y para cada vértice el punto en el que se encuentra. › La estructura se puede completar con relaciones hacia arriba (de vértices a aristas, y de estas a caras). 39 Ejemplo III › De este modo se eliminan las redundancias y se almacenan parte de las relaciones topológicas. Las superficies de las caras y las líneas de las aristas se pueden calcular cuando sea necesario a partir de los puntos que las delimitan. 40 Ejemplo IV 41 Ejemplo V › Para poder utilizar caras con agujeros es necesario complicar la estructura, almacenando para cada cara una secuencia de ciclos de aristas, de los que el primero es el perímetro exterior, y el resto agujeros practicados en él. › Otra alternativa es utilizar falsas aristas, o aristas puente, para unir los perímetros interiores al exterior. 42 Aristas con Alas › La estructura de datos más popular para almacenar un modelo de fronteras es la de aristas aladas (“winged-edge”). › Esta estructura incorpora más relaciones topológicas y organiza la jerarquía partiendo de las aristas, lo que simplifica el tratamiento de caras con agujeros. › El elemento central de estructura es la arista, en lugar de la cara. 43 Aristas con Alas II › Cada arista almacena información de sus relaciones de vecindad con aristas y caras. Concretamente, cada arista contiene, además de su identificador: – Sus dos vértices – Las dos caras que comparten arista – Las cuatro aristas que parten de ella, en las caras que la comparten 44 Aristas con Alas III › Las dos caras de la arista se etiquetan en función de como se recorra la cara cuando se va del vértice inicial al final de la arista, en clockwise y counterclockwise. La figura anterior muestra la información asociada a cada arista. › El recorrido de los vértices se realiza en sentido anti-horario. 45 Aristas con Alas IV › Las tablas siguientes muestran parte de la información almacenada para el sólido de la figura. 46 Aristas con Alas V 47 Aristas con Alas VI › Obsérvese que esta estructura no se puede utilizar para poliedros no-manifold, ya que en ellos una arista podría tener más de dos caras vecinas. › La alternativa para tratar este tipo de sólidos con estas representaciones es modificar el sólido para eliminar la singularidad, bien convirtiendo la arista en una unión sólida o desdoblándola 48 Aristas con Alas VII › El sólido no-manifold de la izquierda se puede convertir para obtener un sólido 2-manifold. 49 Edición › La edición directa, moviendo puntos de control, aunque es factible cuando se restringe el método para utilizar caras triangulares, no es aconsejable, pues es demasiado laborioso. › Los métodos de edición usuales en modeladores que trabajan con modelos de fronteras son: – La combinación de instanciación de primitivas prediseñadas con operaciones de barrido sobre las caras. 50 Edición II – Las operaciones booleanas – La modificación local del modelo por biselado de las aristas o vértices. › Hablaremos brevemente de cada una de estas opciones. Las operaciones booleanas usadas son la unión, la intersección y la diferencia. No se usa el complemento, ya que produce sólidos no válidos. › Para realizar una operación boolena entre dos sólidos se sigue el siguiente proceso: 51 Edición III – Clasificación de caras: 1. Calcular todas las líneas de intersección de las caras de A con las caras del sólido B y viceversa. 2. Dividir las caras que están partidas por estas lineas. Para ello se unen las aristas consecutivas entre si para formar nuevas caras. 3. Clasificar las caras de cada sólido respecto al otro sólido en externas e internas. – Selección de caras: 4. En función de la operación a realizar se clasifican las caras eligiendo las que forman parte del sólido resultado. 52 Edición IV – Crear representación: 5. Reconstruir relaciones entre elementos: 53 Edición V › Se debe tener un cuidado especial al tratar las caras coplanarias, realizando la clasificación de las caras teniendo en cuenta la orientación de las dos caras. › La figura anterior muestra el resultado que se obtendría con dos sólidos a los que coincide una cara si esto no se tiene en consideración, y como se deben clasificar dos caras coplanarias con la misma y distinta orientación en cada uno de las operaciones. 54 Edición VI › El biselado consiste en sustituir una arista o un vértice por una cara. Aplicando reiteradas veces se puede obtener un sólido con perfil redondeado. › El sistema modifica la representación del sólido creando las nuevas caras y modificando las relaciones de vecindad. 55 Barrido › Una operación de barrido define un sólido por el volumen del espacio ocupado por una superficie cuando se desplaza a lo largo de una trayectoria, de un modo análogo a la construcción de una superficie por desplazamiento de una curva › La construcción más simple es realizar traslaciones o revoluciones, pero se pueden igualmente construir sólidos realizando un barrido generalizado, escalando y rotando la superficie mientras se desplaza a lo largo de una trayectoria arbitraria. 56 Barrido II › Como método de representación está muy limitado. › No obstante, es muy útil como método de modificación local de un modelo de fronteras, permitiendo su edición. › De este modo se puede añadir materia a una cara del modelo realizando una extrusión a partir de la cara, o realizar una perforación haciendo una intrusión en la cara. 57 Barrido III › En cualquier caso, el usuario dibuja la superficie a desplazar sobre la cara del sólido e indica el vector de desplazamiento. › A partir de esta información el sistema puede generar automáticamente la información de las caras creadas. Véase la figura: 58 Métodos de descomposición › Representan objetos sólidos mediante la unión de un conjunto de celdas disjuntas sin agujeros. S= ∪ Ci › La representación del sólido es la lista de celdas o píxeles que ocupa, que se puede codificar como un bit de ocupación por cada celda (Ci), si la geometría de las celdas es fija, o como la lista de parámetros de las celdas ocupadas. › Los métodos que utilizan celdas de geometría fija suelen utilizarse para realizar representaciones aproximadas. 59 Métodos de descomposición II › Estos métodos se pueden utilizar para representar sólidos heterogéneos, añadiendo simplemente el valor de propiedad de cada celda. › Los métodos de descomposición pueden estructurar las celdas en una estructura jerárquica, lo que ayuda a localizar información y a compactar la representación del modelo, este es el caso de los árboles octales (o de octantes, octrees), y de los árboles de partición binaria del espacio (BSP). › Cuando la representación no es jerárquica se dice que el método de representación es una enumeración de celdas. 60 Métodos de descomposición III › Primero vamos a abordar la enumeración espacial: – El espacio donde reside el sólido se divide en cubos de igual tamaño, que conforman una rejilla 3D. Por cada cubo (voxel), se almacena la información de ocupación del sólido, esto es, si el voxel pertenece o no al sólido. – En la mayor parte de los casos es necesario realizar una aproximación ya que el voxel no estará ni totalmente dentro ni totalmente fuera del sólido. – La estructura de almacenamiento es simplemente un array 3D de booleanos. En cierto modo, la representación es semejante a una imagen 3D del sólido. – El principal inconveniente de la representación, además de ser aproximada, es que no es concisa (ocupa mucho espacio). 61 Métodos de descomposición IV › Octrees: – Un octree describe, dentro de un cubo inicial, y recursivamente los octantes ocupados por el sólido. – Dado un cubo que encierra al sólido, se divide en ocho octantes, que podrán estar totalmente ocupados por el sólido, vacíos o parcialmente ocupados. Para los octantes que están parcialmente ocupados se repite el mismo proceso. Así hasta alcanzar un nivel de precisión prefijado. – La representación puede verse como una compactación de una enumeración espacial. 62 Métodos de descomposición V 63 Métodos de descomposición VI Esquema de la estructura de datos octree y su serialización. Los nodos del árbol que encapsulan puntos están marcados como ocupados (1 binario). Estos son los únicos nodos que tienen hijos. En el nivel más fino, el proceso de división se detiene y los nodos que encapsulan puntos se marcan como ocupados. 64 Almacenamiento › Ahora vamos a abordar el almacenamiento de los octrees. › De forma natural la representación se puede almacenar como un árbol octal, en el que cada nodo interno representa un cubo parcialmente ocupado, y los nodos terminales puede estar ocupados o vacíos. › Los ocho hijos de cada nodo interno representan los ocho subcubos en que se divide el cubo. 65 Almacenamiento II › Esta representación permite localizar de forma rápida la información de un nodo, pero requiere un espacio adicional para alojar los punteros a los hijos. › Cuando no se va a operar con sólido, por ejemplo, para almacenarlo en un fichero, suele ser preferible una codificación lineal, obtenida mediante un recorrido del árbol (por ejemplo, en orden central). 66 Almacenamiento III 67 Búsqueda › La localización de un punto del espacio en el árbol, que es necesaria para la mayor parte de las operaciones, y en concreto para saber si el punto está dentro del sólido se puede realizar de forma rápida si se ha realizado el etiquetado de los nodos de forma adecuada. › Concretamente se puede hacer que el índice del nodo hijo se obtenga por yuxtaposición de su posición relativa en las tres direcciones (véase figura de la siguiente diapositiva). 68 Búsqueda II › Asumiendo una resolución máxima conocida, esto es un tamaño conocido, d, del voxel de más pequeño a usar, podemos calcular los índices de un voxel dado en coordenadas enteras, en el rango 0 a 2n, siendo n la máxima profundidad del árbol. 69 Búsqueda III 70 Operaciones booleanas › La forma más simple de editar un octree es realizando operaciones booleanas. › Dados dos octrees con la misma caja englobante, las operaciones booleanas se pueden calcular nodo a nodo, realizando un descenso sincronizado en los dos operandos. › Las siguientes tablas muestran el procesamiento de las operaciones booleanas, representando por □ un nodo vacío, por uno lleno, y por ☒ un nodo interno. 71 Operaciones booleanas II 72 Operaciones booleanas III 73 Bibliografía › Foley J.D.; van Dam A.; Feiner S.K.; Hughes J.F.: "Computer Graphics. Theory and Practice". Addison-Wesley 1990. › Brunet, P.; "Modelado geométrico de volúmenes" Cursos del CEIG'93 › Mantyla, M.; "An introduction to solid modeling". Computer Science Press 1988 › Bronsvoort W.; "Geometric Modeling" Tutorial EG'87 › Mantyla M.; "Avanced Topics in Solid Modeling". Tutorial EG'89 74  Tema – 9 Estructuras Espaciales y de Aceleración Nuño Basurto Hornillos [email protected] Informática Gráfica Grado en Diseño de Videojuegos – Curso 2024 - 2025 Área de Ciencia de la Computación e Inteligencia Artificial – Departamento de Digitalización Introducción › Las estructuras de datos espaciales organizan la geometría en 2D, 3D o más dimensiones. › El objetivo principal es alcanzar un procesamiento más rápido. › Necesarias en la mayoría de las “técnicas de aceleración”: – Aceleran rendering en tiempo real. – Aceleran los test de intersección. – Aceleran la detección de colisiones. – Aceleran ray tracing e iluminación global. 2 Introducción II › El objetivo básico es organizar jerárquicamente la geometría en dos espacios básicos: 2D Estructura de datos 3 División geométrica Bounding Volume › Son las formas que encierran uno o más objetos. Estas formas tratan de “ajustarse” lo máximo posible al conjunto de objetos. › La dificultad aparece cuando muchos vértices forman las figuras, así mismo, el cálculo de la posición del objeto dentro de la forma es costosa de calcular. › Estos pueden generar diferentes cuadros dependiendo de la forma escogida. 5 Bounding Volume II 6 Bounding Volume III › Cuando se calcula la intersección de un par de superficies, es importante calcular de una forma robusta las líneas de intersección. › Hay algunas muy sencillas en las que la velocidad de cálculo es muy rápida y nos puede ayudar a reducir el coste computacional, véase Sphere o AABB. › Para mejorar la eficiencia se puede optar por una hibridación de los espacios del objeto y del área. 7 Bounding Volumes Hierachies › Las Bounding Volumes Hierachies (BVHs) son un enfoque para la intersección de aceleración de rayos, basadas en una subdivisión de primitivas. › Las primitivas se encuentran divididas en una jerarquía de conjuntos independientes. › Las primitivas se almacenan en las hojas de un “árbol”, donde cada nodo almacena un cuadro delimitador, de los nodos situados bajo este. 8 Bounding Volumes Hierachies II › La estructura es un árbol k-ario: – Las hojas tienen la geometría – Los nodos internos tienen a lo más k hijos – Los nodos internos tienen BVs que encierran toda la geometría de su subárbol › Cuando el “rayo” atraviesa el árbol y no se encuentran los límites de un nodo, se libra de tener en cuenta los subnodos. 9 Bounding Volumes Hierachies III › Respecto a la imagen anterior en la parte superior (a), se observa una pequeña colección de primitivas con recuadros delimitadores (bounding), con líneas discontinuas. Las primitivas se juntan dependiendo de su proximidad, es por ello por lo que el triángulo y la esfera se juntan en un nuevo cuadro delimitador. › Por otro lado, en (b) se observa la jerarquía completa, donde el nodo superior comprende toda la escena, y posee dos hijos, el triángulo de la derecha y otro nodo con las dos primitivas. 10 Bounding Volumes Hierarchies IV › Una de las propiedades de la subdivisión de primitivas, es que estas aparecen en el árbol jerárquico en una sola ocasión. › Por contrapartida, las primitivas pueden solapar varias regiones espaciales, ello conlleva a que puede comprobarse su intersección varias veces a medida que el rayo las atraviesa. › Así mismo, esta propiedad da lugar a que la cantidad de memoria necesitaría para representar esta jerarquía está limitada. 11 Bounding Volumes Hierarchies V › Si tratamos con una jerarquía binaria, se va a almacenar una única primitiva en cada hoja, por lo que el número total de nodos es: 2n - 1, donde n será el número de primitivas. › Habrá n nodos hoja y n-1 nodos interiores. Si las hojas almacenan varias primitivas se necesitan menos nodos. › Un árbol binario (k=2), como el visto en el ejemplo anterior es el más simple, pero se suele trabajar con k=4 y k=8. 12  Bounding Volumes Hierarchies VI › Una de las formas de crear BVH es hallando la caja mínima y separar por el eje más largo: Separamos Hallamos por el eje cajas X mínimas Hallamos cajas Separamos mínimas por el eje Y Separamos por el eje X 13 Grafos de escena › Comúnmente se utiliza BVH, dada su simpleza de comprensión y un código relativamente sencillo. › Pero estos solo almacenan la geometría y cuando se lleva a cabo el renderizado son necesarios más elementos allá de esta, como por ejemplo luces, texturas, transformaciones etc. › Los grafos de escena contienen, por un lado, descripciones de bajo nivel de la geometría y apariencia visual de los objetos. 14 Grafos de escena II › Por otro lado, poseen descripciones de alto nivel a cerca de la organización espacial de la escena, datos específicos o transformaciones. › Estos grafos contienen nodos que almacenan la información geométrica, así como otros nodos que aplican modificaciones a los segmentos de la jerarquía. 15 Grafos de escena III › Hay 5 tipos básicos de nodos: – Nodo de Geometría. Almacenan la información poligonal de los objetos, también almacenan informaciones referentes a su apariencia, tales como material, textura, etc. Usualmente actúan como nodos hoja. – Nodo Grupo. Se emplean para agrupar varios nodos hijos, bien sea a nivel meramente organizativo, o para facilitar el proceso de culling jerárquico. – Nodo Nivel de Detalle. Seleccionan uno de sus hijos, basándose en la distancia entre el objeto con múltiples niveles de detalle y el punto de vista. – Nodo de Transformación Afín. Permite aplicar una matriz de transformación que afectara a ubicación espacial de sus nodos hijos. – Nodo de Switch. Permiten realizar una selección entre sus nodos hijos. 16 Grafos de escena IV 17 Volúmenes de inclusión › Hemos podido observar las diferencias de cada técnica a la hora de incluir la geometría en los nodos, vamos a diferenciar cuatro tipos de volúmenes de inclusión: 18 Volúmenes de inclusión II › Las cajas orientadas tienen la problemática de encontrar la orientación exacta que se ajuste mejor al modelo. › Idealmente, lo más deseado, es optimizar al mínimo la presencia de volumen en la caja, llegando a adaptarse lo mejor posible al elemento, lo cual puede resultar muy costoso. › Por este motivo se recurre a los métodos estadísticos: – Muestrear los puntos de la geometría. – Encontrar la media y la matriz de covarianza de los puntos. 19 Volúmenes de inclusión III – La media será el centro de la caja. – Los vectores de la matriz de covarianzas son las principales direcciones y se utilizan como ejes de la caja. – La dirección principal tiende a alinearse con el eje más largo, luego con el segundo eje perpendicular y finalmente con el tercer eje ortogonal. 20 División espacial Binary Space Partitioning Trees › La partición espacial binaria en árboles o BSP Trees son de dos tipos diferentes: – Alineados a los ejes (Este es el que vamos a tratar) – Alineados a los polígonos › Tienen como idea general la división del espacio con un plano, para ello realizan ordenación geométrica dentro del espacio al que pertenecen. Esto lo hacen siempre de forma recursiva. 22 Binary Space Partitioning Trees II › Si lo árboles son recorridos de cierta forma se puede ordenar la geometría a lo largo de un eje de dos formas: – Exacta, cuando se alinea con los polígonos. – Aproximado cuando es alineado a los ejes. › Solo pueden existir planos separadores respecto a ejes x, y o z. División a lo largo del plano 23 Binary Space Partitioning Trees III División a lo largo del plano Plano 2 Plano 1b 24 Binary Space Partitioning Trees IV › Cada nodo interno contiene un plano separador (p.e. 1a). 0 › Las hojas contienen la geometría. 1a 1b › Diferencias fundamentales con BVH: – BSP Trees encierran todo el espacio y A B C 2 proveen de ordenamiento. – La BVHs pueden ser construidas de cualquier forma (sin orden) D E – BVHs pueden utilizar cualquier tipo deseable de BV. 25 kd-trees › Fueron inventados en la década de los 70 por Jon Bentley. › La k indicaba originalmente el número de dimensiones. › Hoy en día se comentan de la siguiente forma: – kd-tree de dimensión d. › Únicamente permite tener dos hijos en cada nodo. › Los kd-trees se pueden usar para realizar la subdivisión espacial de una escena de forma recursiva, creando un árbol binario. 26 kd-trees II › Cada nivel tiene una dimensión de corte. › Recorre las diferentes dimensiones mientras se va descendiendo por el árbol. › Cada nodo tiene un punto: P = (x, y) › Para encontrar el punto (x’, y’), únicamente se comparan las coordenadas desde la dimensión de corte. › En la siguiente diapositiva se muestra un ejemplo desde el punto de vista. › El eje de coordenadas está situado en el límite inferior izquierdo. 27 kd-trees III 28 kd-trees IV › El resumen de lo anterior sería: – El primer nodo se establece como nodo raíz, el siguiente nodo compara el valor de x con el nodo raíz, si es mayor o igual a la derecha, menor a la izquierda. – El siguiente nodo (10, 12), compara de nuevo la x con la raíz (30, 40), al ser menor va a la izquierda, ahora compara su y (12) con el nodo (5,25), al ser menor se sitúa a su izquierda. – El nodo (70, 70) tiene una x mayor a la de la raíz por lo que se sitúa a su derecha. Así sucesivamente. 29 kd-trees V › Otro ejemplo, esta vez el insert es: (3, 6), (17, 15), (13, 15), (6, 12), (9, 1), (2, 7), (10, 19) 30 kd-trees VI › Más allá de la inserción también se pueden realizar búsquedas dentro de un kd-tree. › La idea fundamental de ellos es la de recorrer de forma recursiva el árbol. › De manera similar a su construcción, recorremos el árbol, partiendo siempre del nodo raíz, donde comparamos la x a buscar con ella, ahí nos desplazamos a la derecha si es mayor o igual o a la izquierda si es menor. 31 kd-trees VII › Eliminación de nodos, para ello se pueden contemplar tres escenarios, el primero de ellos establece que el nodo a borrar no tiene hijos, de ser así simplemente lo eliminamos y ya está. Supongamos en la imagen inferior, que queremos quitar el nodo (2,7), sería eliminado y ya está. › En el segundo, imaginemos que el nodo tiene un hijo a la derecha. 32 kd-trees VIII › Por ejemplo, deseamos borrar el nodo (12,3), que está en una posición bastante arriba dentro del árbol. 33 kd-trees IX › En este punto buscaremos en su nodo derecho, donde aparece el nodo (10, 19), aquí buscaremos al nodo cuya y (dado que está en el nivel y) sea menor, que sea hijo a la derecha de este, en el ejemplo (15,7). 34 kd-trees X › Este valor (15, 7), los sustituimos por el nodo (12,3) que deseábamos borrar. › Un tercer caso, sería que tuviese únicamente hijo a la izquierda, en tal caso, se haría lo mismo, pero hacia la izquierda, buscando el valor (x o y) dependiendo del nivel correspondiente. 35 kd-trees XI › Si lo que deseamos es realizar la búsqueda del valor mínimo. › Siempre empezaremos buscando hacia la izquierda de forma iterativa hasta encontrar el último nodo hoja. › Aquel último nodo, que no posea ningún hijo a la izquierda, aunque sí que lo tenga a la derecha diremos que será aquel que tenga un valor mínimo. 36 kd-trees XII 37 Comparativa › Las BVHs son más eficientes que construir kd-trees, aunque estás por lo general reparten los rayos de intersección de forma más rápida, pero son más costosas de construir. › Por otro lado, las BVHs, son en general más robustas numéricamente y menos propensas a fallar intersecciones debido a errores de redondeo. 38 Comparativa II › Ahora vamos a realizar una comparativa respecto a la técnica de renderizado ray-tracing: › Lo primero es dejar claro que BVH es un método de subdivisión de objetos y, por otro lado, kd-tree de subdivisión de espacios. › Los primeros bridan la posibilidad de ajustarse de forma recursiva a la geometría en partes más pequeñas, envolviendo estas en un volumen normalmente ajustado. › Las segundas dividen el espacio sin tener en cuenta la geometría incrustada en dicho espacio. 39 Comparativa III › En lo referente a espacios, los subespacios no se solapan, permitiendo atravesar la estructura de delante a atrás o viceversa más fácilmente. Cuando los rayos atraviesan una estructura de este tipo al tocar la superficie detenemos el recorrido. Permitiendo esquemas más rápidos. › Por otro lado, la subdivisión espacial puede ser más complicada de implementar y los árboles anteriormente observados pueden tener una mayor profundidad. Implementando peor la geometría dinámica. 40 Comparativa IV › Las características de la subdivisión de objetos son diferentes. Al subdividir un objeto con volúmenes, estos se solapan y hacen el recorrido más lento. › Pueden ser más fáciles de implementar al no tener que dividir las partes de un objeto con planos. El punto más interesante de estos es que son más amigables con la geometría dinámica. Permitiéndonos ajustar localmente el tamaño y posición del volumen delimitador de un objeto cuya geometría varíe. › A partir de las BVH tradicionales han surgido otras, como las SBVH, que son híbridas con subdivisión de objetos y espacial, pero por el contrario aumentan el consumo de memoria un 30%. Las Nvidia RTX soportan las BVHs y las SBVH. 41 Técnicas de reducción de complejidad Backface Culling › Técnica simple que elimina aquellos polígonos que no miran hacia el espectador. › Son usados en: – Superficies cerradas (esfera, cubo, toro) – Cuando sabemos que las backfaces no van a ser vistas (ejemplo: paredes en una habitación) › Si el ángulo rebota hacia atrás no lo tendremos en cuenta. › Benefician las etapas de rasterización y de vista. 43 Backface Culling II › Para determinar si una cara se debe renderizar vamos a partir de utilizar el vector normal de cada cara. 44 Backface Culling III › Si el ángulo formado entre el rayo de la cámara y el vector normal es menor de 90º consideraremos que la cara es visible por la cámara y la renderizaremos, en caso contrario será invisible y la desecharemos (culling). › En el siguiente ejemplo veremos cómo trabaja el algoritmo de culling, enumerando los pasos para determinar si dibujar o no una cara formada por los vértices A, B, C. 45 Backface Culling IV 1. Buscar los vectores (B-A) y (C-A). 2. Hacer su producto vectorial y buscar la perpendicular normal N. 3. Buscar el rayo de la cámara sustrayendo la posición de la cámara del punto A. 4. Hacer el producto escalar entre la normal N y el rayo de la cámara. 5. Si el producto escalar es menor que cero no se renderiza la cara. 46 LoDs › Son las sigas de Level of Deatil o nivel de detalle en castellano. › Se usan para determinar el nivel de detalle de un modelo en nuestra escena. › Esto permite que al alejarnos de un modelo en la escena este se vaya simplificando cada vez más y con la geometría de la malla. › Permite una mayor optimización en el juego. 47 LoDs II 48 LoDs III › Para ajustar cada LoD en nuestra malla 3D, habrá que ir realizando un ajusta gradual e ir creando una escalera que disminuya la calidad. › Si en el LOD 0 teníamos el 100% de los triángulos en el LOD 1 tendremos un 50%. › Cuando ajustamos LOD puede que este posea una baja resolución, provocando un cambio muy notable. › Para ello tendremos que cambiar su Screen Size, permitiendo que un LOD reducido de muestre cuando el objeto está más lejos del espectador. 49 LoDs IV › Por lo tanto, a mayor valor de x en LoDX menor será el detalle. › Por ejemplo, Unreal Engine permite hasta un total de 8 niveles de detalle. La idea es que si lo has configurado correctamente el programa vaya realizando las variaciones automáticamente. › LoD no solo reduce el número de triángulos si no que reduce también el número de materiales o les puede cambiar por otro menos costosos. En personajes puede eliminar las morfologías y los huesos. 50 LoDs V Ejemplo del uso de LoD en Unity. 51  Tema – 10 Renderizado Nuño Basurto Hornillos [email protected] Informática Gráfica Grado en Diseño de Videojuegos – Curso 2024 - 2025 Área de Ciencia de la Computación e Inteligencia Artificial – Departamento de Digitalización Introducción › El renderizado se puede definir como el proceso que genera imágenes digitales desde modelos tridimensionales mediante el uso de software específico. › Estas imágenes tratan de simular proyecciones 3D con espacio fotorrealistas, materiales, luces y objetos. › El renderizado ayuda a reducir los costos del diseño, así como aumentar la eficiencia. 2 Introducción II › Hay dos categorías de renderizado: – Renderizado en tiempo real: Las imágenes se calculan a tal velocidad que parece que están sucediendo en tiempo real. Es un tipo de renderizado muy utilizado en videojuegos y gráficos interactivos. – Renderización offline: Aquí carece de importancia esa velocidad de elaboración tan alta. La complejidad visual es muy alta, aunque carece de capacidad de improvisación como es el otro renderizado. 3 Introducción III 4 Renderizado en tiempo real › Este renderizado, se centra en el análisis y producción de imágenes (renders) en tiempo real, permitiendo la interactuación de los usuarios con ellos. › Se utiliza fundamentalmente en entornos 3D interactivos, así como en videojuegos 3D. › Está creciendo enormemente en su uso. › Programas como AutoCAD o Maya, pueden hacer uso de este tipo de renderizado. 5 Renderizado en tiempo real II › Dentro de los motores en tiempo real se encuentran los motores gráficos. Estos están pensados en el desarrollo de videojuegos, que además de renderizar en tiempo real, ofrecen distintas herramientas para su creación. › Dentro de estos motores, destacan OpenGL, DirectX o Vulkan. › Processing cuando usa el renderizador P2D o P3D usa OpenGL. › Hay dos tipos de algoritmos Forward Shading y Deferred Shading. 6 Forward Shading › Se trata de una técnica de renderizado en tiempo real, en el cual cada objeto de la escena se sombreado de manera individual. › Durante el sombreado se evalúa la contribución de las diferentes luces de la escena, teniendo en cuenta las componentes de luz, como la difusa y la especular. › Tiene como inconveniente principal el mal escalado que tiene con las luces y los objetos de la escena. 7 Forward Shading II Fuente: Una introducción a los algoritmos de renderizado eficientes y al sombreado agrupado. 8 Deferred Shading › Divide el proceso de renderizado en dos etapas, la primera almacena los datos geométricos y la segunda realiza cálculos de iluminación. Esto permite una mejor gestión de los cálculos de iluminación y mejora el rendimiento en escenas complejas › A continuación, se van a explicar cada una de las etapas: – Almacenamiento de datos geométricos (G-Buffer): Se almacena información referente a la geometría de los objetos, como la posición o el vector normal, con las direcciones de la superficie. 9 Deferred Shading II – Cálculo de la iluminación: En esta segunda etapa, la iluminación se calcula en base a esos G-Buffers, afectando únicamente a los píxeles visibles. › Esto lleva a que haya una mejor escalabilidad dado que la escena se renderiza una única vez, independientemente del número de luces de la escena. Esto también permite un mejor trabajo paralelo en las GPUs. › Por contrapartida, el uso de los G-Buffers provoca que haya un mayor gasto de memoria en la GPU. › A partir de esta técnica han salido nuevas, como el Tiled Deferred Shading o el Cluster Deferred Shading. 10 Deferred Shading III Fuente: Una introducción a los algoritmos de renderizado eficientes y al sombreado agrupado. 11 Renderización Offline › Este tipo de renderizado está más extendido, permite la transformación de objetos para su visualización en cualquier momento, en él se prioriza la calidad visual por encima de la velocidad de cálculo. › Se utiliza en casos como la animación o los efectos especiales, utilizándose al final del proceso creativo. › Hay varios programas de renderizado, siendo muchos de estas extensiones de programas de modelado. 12 Comparativa › Para este análisis se va a hacer una comparativa desde el punto de vista de unos del software de modelado más utilizados como es Blender. › Hay que partir desde el punto de vista, que Blender no es un motor de renderizado, si no un software que permite el modelado o la edición de videos. › Este mismo programa incluye dos motores de renderizado, uno offline (Cycles) y otro en tiempo real (Eevee). › Cycles logra resultados mucho más realistas , simulando la física de la luz, mediante Path Tracing, aunque es muy lento. 13 Comparativa II › Por otro lado, Eevee, obtiene resultados menos realistas, pese a ello los resultados de los motores en tiempo real son cada vez mejores, con ciertos retoques fotográficos pueden llegar a “sustituir” a los offline. 14 Fuente: Blendernation Motores en tiempo real › Como se comentaba anteriormente los motores en tiempo real son herramientas que nos ayudan a componer escenas, animar, dotar d