En gráficos de computadora y geometría computacional , un volumen delimitador (o región delimitadora ) para un conjunto de objetos es una región cerrada que contiene completamente la unión de los objetos en el conjunto. Los volúmenes delimitadores se utilizan para mejorar la eficiencia de las operaciones geométricas, como por ejemplo mediante el uso de regiones simples, que tienen formas más simples de probar la superposición .
Un volumen delimitador para un conjunto de objetos es también un volumen delimitador para el objeto único que consiste en su unión, y viceversa. Por lo tanto, es posible limitar la descripción al caso de un único objeto, que se supone que no está vacío y es acotado (finito).
Los volúmenes delimitadores se utilizan con mayor frecuencia para acelerar ciertos tipos de pruebas.
En el trazado de rayos , los volúmenes delimitadores se utilizan en pruebas de intersección de rayos y, en muchos algoritmos de renderizado , se utilizan para pruebas de frustum de visualización . Si el rayo o frustum de visualización no interseca el volumen delimitador, no puede intersecar el objeto contenido en su interior, lo que permite un rechazo trivial . De manera similar, si el frustum contiene la totalidad del volumen delimitador, el contenido puede aceptarse trivialmente sin más pruebas. Estas pruebas de intersección producen una lista de objetos que deben "mostrarse" (renderizarse; rasterizarse ).
En la detección de colisiones , cuando dos volúmenes delimitadores no se intersecan, los objetos contenidos no pueden colisionar.
Las pruebas con un volumen delimitador suelen ser mucho más rápidas que las pruebas con el objeto en sí, debido a la geometría más simple del volumen delimitador. Esto se debe a que un "objeto" suele estar compuesto de polígonos o estructuras de datos que se reducen a aproximaciones poligonales. En cualquier caso, es un desperdicio computacional probar cada polígono con el volumen de visualización si el objeto no es visible. (Los objetos en pantalla deben estar "recortados" a la pantalla, independientemente de si sus superficies son realmente visibles).
Para obtener volúmenes delimitadores de objetos complejos, una forma habitual es dividir los objetos/escenas mediante un gráfico de escena o, más específicamente, una jerarquía de volúmenes delimitadores , como, por ejemplo, los árboles OBB . La idea básica detrás de esto es organizar una escena en una estructura similar a un árbol donde la raíz comprende toda la escena y cada hoja contiene una subparte más pequeña. [1]
En la visión estereoscópica por computadora , un volumen delimitador reconstruido a partir de siluetas de un objeto se conoce como " casco visual ". [2]
La elección del tipo de volumen delimitador para una aplicación determinada está determinada por una variedad de factores: el coste computacional de calcular un volumen delimitador para un objeto, el coste de actualizarlo en aplicaciones en las que los objetos pueden moverse o cambiar de forma o tamaño, el coste de determinar intersecciones y la precisión deseada de la prueba de intersección. La precisión de la prueba de intersección está relacionada con la cantidad de espacio dentro del volumen delimitador no asociado con el objeto delimitado, llamado espacio vacío . Los volúmenes delimitadores sofisticados generalmente permiten menos espacio vacío pero son más costosos computacionalmente. Es común usar varios tipos en conjunto, como uno económico para una prueba rápida pero aproximada junto con un tipo más preciso pero también más costoso.
Todos los tipos tratados aquí dan volúmenes delimitadores convexos . Si se sabe que el objeto que se delimita es convexo, esto no es una restricción. Si se requieren volúmenes delimitadores no convexos, un enfoque es representarlos como una unión de varios volúmenes delimitadores convexos. Desafortunadamente, las pruebas de intersección se vuelven rápidamente más costosas a medida que los cuadros delimitadores se vuelven más sofisticados.
Un cuadro delimitador o cuadro delimitador mínimo ( MBB ) es un cuboide , o en 2-D un rectángulo , que contiene el objeto. En la simulación dinámica , los cuadros delimitadores se prefieren a otras formas de volumen delimitador, como esferas o cilindros delimitadores para objetos que tienen una forma aproximadamente cuboide cuando la prueba de intersección debe ser bastante precisa. El beneficio es obvio, por ejemplo, para objetos que descansan sobre otros, como un automóvil apoyado en el suelo: una esfera delimitadora mostraría que el automóvil posiblemente se intersecta con el suelo, lo que luego debería rechazarse mediante una prueba más costosa del modelo real del automóvil; un cuadro delimitador muestra inmediatamente que el automóvil no se intersecta con el suelo, lo que ahorra la prueba más costosa.
Un rectángulo delimitador mínimo ( MBR , por sus siglas en inglés) –el AABB mínimo en 2-D– se utiliza con frecuencia en la descripción de elementos de datos geográficos (o "geoespaciales"), y sirve como un proxy simplificado de la extensión espacial de un conjunto de datos (consulte metadatos geoespaciales ) con el propósito de buscar datos (incluidas las consultas espaciales, según corresponda) y visualizarlos. También es un componente básico del método de árbol R de indexación espacial .
En muchas aplicaciones, el cuadro delimitador está alineado con los ejes del sistema de coordenadas y, en ese caso, se lo conoce como cuadro delimitador alineado con el eje (AABB ). Para distinguir el caso general de un AABB, a un cuadro delimitador arbitrario a veces se le denominacuadro delimitador orientado(OBB ), o unOOBB cuando se utiliza el sistema de coordenadas localde un objeto existente. Las AABB son mucho más sencillas de probar para detectar la intersección que las OBB, pero tienen la desventaja de que cuando se rota el modelo no se pueden rotar simplemente con él, sino que se deben volver a calcular.
ALa cápsula delimitadora es una esfera barrida (es decir, el volumen que toma una esfera a medida que se mueve a lo largo de un segmento de línea recta) que contiene el objeto. Las cápsulas se pueden representar por el radio de la esfera barrida y el segmento que recorre la esfera). Tiene características similares a un cilindro, pero es más fácil de usar, porque la prueba de intersección es más simple. Una cápsula y otro objeto se intersecan si la distancia entre el segmento que define la cápsula y alguna característica del otro objeto es menor que el radio de la cápsula. Por ejemplo, dos cápsulas se intersecan si la distancia entre los segmentos de las cápsulas es menor que la suma de sus radios. Esto es válido para las cápsulas rotadas arbitrariamente, por lo que son más atractivas que los cilindros en la práctica.
AUn cilindro delimitador es uncilindroque contiene el objeto. En la mayoría de las aplicaciones, el eje del cilindro está alineado con la dirección vertical de la escena. Los cilindros son apropiados para objetos 3D que solo pueden rotar sobre un eje vertical pero no sobre otros ejes, y que de otra manera están restringidos a moverse solo por traslación. Dos cilindros alineados con el eje vertical se intersecan cuando, simultáneamente, se intersecan sus proyecciones sobre el eje vertical (que son dos segmentos de línea) y sus proyecciones sobre el plano horizontal (dos discos circulares). Ambos son fáciles de probar. En losvideojuegos, los cilindros delimitadores se usan a menudo como volúmenes delimitadores para personas de pie.
AEl elipsoide delimitador es unelipsoideque contiene el objeto. Los elipsoides suelen proporcionar un ajuste más ajustado que una esfera. Las intersecciones con elipsoides se realizan escalando el otro objeto a lo largo de losejes principalesdel elipsoide en una cantidad igual alinverso multiplicativode los radios del elipsoide, reduciendo así el problema a la intersección del objeto escalado con unaesfera unitaria. Se debe tener cuidado para evitar problemas si el escalado aplicado introduce sesgo. El sesgo puede hacer que el uso de elipsoides sea poco práctico en ciertos casos, por ejemplo, la colisión entre dos elipsoides arbitrarios.
Una esfera delimitadora es una esfera que contiene el objeto. En gráficos 2D, esto es un círculo . Las esferas delimitadoras se representan por el centro y el radio. Son muy fáciles de comprobar para detectar colisiones entre sí: dos esferas se intersecan cuando la distancia entre sus centros no supera la suma de sus radios. Esto hace que las esferas delimitadoras sean adecuadas para objetos que pueden moverse en cualquier número de dimensiones.
ALa losa delimitadora es el volumen que se proyecta en una extensión sobre un eje y se puede considerar como lalosadelimitada entre dos planos. Un cuadro delimitador es la intersección de losas delimitadoras orientadas ortogonalmente. Las losas delimitadoras se han utilizado para acelerarel trazado de rayos[3].
AEl triángulo delimitador en 2D es muy útil para acelerar la prueba de recorte o visibilidad de una curva B-Spline. Consulte"Algoritmos de recorte de círculos y B-Splines"en el tema Recorte (gráficos por computadora) para ver un ejemplo de uso.
Una envoltura convexa es el volumen convexo más pequeño que contiene el objeto. Si el objeto es la unión de un conjunto finito de puntos, su envoltura convexa es un politopo.
AUn politopo orientado discreto (DOP) generaliza el cuadro delimitador. Un k-DOP es la intersección booleana de extensiones a lo largokdirecciones. Por lo tanto, unk-DOP es la intersección booleana deklosas delimitadoras y es unpolitopoque contiene el objeto (en 2-D unpolígono; en 3-D unpoliedro). Un rectángulo 2-D es un caso especial de un 2-DOP, y una caja 3-D es un caso especial de un 3-DOP. En general, los ejes de un DOP no tienen que ser ortogonales, y puede haber más ejes que dimensiones del espacio. Por ejemplo, una caja 3-D que esté biselada en todos los bordes y esquinas se puede construir como un 13-DOP. El número real de caras puede ser menor que 2 vecesksi algunas caras se degeneran, se encogen a un borde o un vértice.
Para algunos tipos de volumen delimitador (OBB y poliedros convexos), una comprobación eficaz es la del teorema del eje separador . La idea aquí es que, si existe un eje por el cual los objetos no se superponen, entonces los objetos no se intersecan. Por lo general, los ejes que se comprueban son los ejes básicos para los volúmenes (los ejes unitarios en el caso de un AABB, o los 3 ejes base de cada OBB en el caso de los OBB). A menudo, esto va seguido de la comprobación de los productos cruzados de los ejes anteriores (un eje de cada objeto).
En el caso de una AABB, esta prueba se convierte en un simple conjunto de pruebas de superposición en términos de los ejes unitarios. Para una AABB definida por M , N contra una definida por O , P no se intersecan si ( M x > P x ) o ( O x > N x ) o ( M y > P y ) o ( O y > N y ) o ( M z > P z ) o ( O z > N z ).
Una AABB también se puede proyectar a lo largo de un eje, por ejemplo, si tiene aristas de longitud L y está centrada en C , y se proyecta a lo largo del eje N: , y o , y
donde m y n son las extensiones mínima y máxima.
Un OBB es similar en este sentido, pero es un poco más complicado. Para un OBB con L y C como el anterior, y con I , J y K como ejes base del OBB, entonces:
Para los rangos m , n y o , p se puede decir que no se intersecan si m > p o o > n . Por lo tanto, al proyectar los rangos de 2 OBB a lo largo de los ejes I, J y K de cada OBB y verificar la no intersección, es posible detectar la no intersección. Al verificar adicionalmente a lo largo de los productos vectoriales de estos ejes (I 0 × I 1 , I 0 × J 1 , ...) uno puede estar más seguro de que la intersección es imposible.
Este concepto de determinar la no intersección mediante el uso de la proyección de ejes también se extiende a los poliedros convexos, pero se utilizan las normales de cada cara poliédrica en lugar de los ejes base y las extensiones se basan en los productos escalares mínimo y máximo de cada vértice con respecto a los ejes. Tenga en cuenta que esta descripción supone que las comprobaciones se realizan en el espacio mundial.
La intersección de dos k -DOP se puede calcular de forma muy similar a las AABB: para cada orientación, simplemente se comprueban los dos intervalos correspondientes de los dos DOP. Por lo tanto, al igual que los DOP son una generalización de las AABB, la prueba de intersección es una generalización de la prueba de superposición de las AABB. La complejidad de la prueba de superposición de dos DOP está en O( k ) . Sin embargo, esto supone que ambos DOP se dan con respecto al mismo conjunto de orientaciones. Si uno de ellos está rotado, esto ya no es cierto. En ese caso, una forma relativamente fácil de comprobar la intersección de los dos DOP es encerrar el rotado, , por otro DOP envolvente más pequeño que esté orientado con respecto a las orientaciones del primer DOP . El procedimiento para eso es un poco más complejo, pero finalmente equivale a una multiplicación de vectores de matriz de complejidad O( k ) . [4]
