Volumen delimitador

En gráficos por 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 del conjunto. Los volúmenes delimitadores se utilizan para mejorar la eficiencia de las operaciones geométricas, por ejemplo, mediante el uso de regiones simples y métodos más sencillos para comprobar la superposición .

Un volumen delimitador para un conjunto de objetos es también un volumen delimitador para el objeto único que resulta de su unión, y viceversa. Por lo tanto, es posible limitar la descripción al caso de un solo objeto, que se supone no vacío y 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 las pruebas de intersección de rayos , y en muchos algoritmos de renderizado , se utilizan para las pruebas del frustum de visualización . Si el rayo o el frustum de visualización no intersecan el volumen delimitador, no pueden intersecar el objeto que contiene, lo que permite un rechazo trivial . Del mismo modo, 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 ser "mostrados" (renderizados; rasterizados ).

En la detección de colisiones , cuando dos volúmenes delimitadores no se intersecan, los objetos contenidos no pueden colisionar.

Las pruebas realizadas con un volumen delimitador suelen ser mucho más rápidas que las realizadas con el objeto en sí, debido a la geometría más simple del volumen delimitador. Esto se debe a que un «objeto» generalmente se compone de polígonos o estructuras de datos que se reducen a aproximaciones poligonales. En cualquier caso, resulta computacionalmente ineficiente probar cada polígono con el volumen de visualización si el objeto no es visible. (Los objetos en pantalla deben «recortarse» a la pantalla, independientemente de si sus superficies son visibles o no).

Para obtener volúmenes delimitadores de objetos complejos, una forma común es descomponer los objetos/la escena utilizando un grafo de escena o, más específicamente, una jerarquía de volúmenes delimitadores , como por ejemplo los árboles OBB . La idea básica es organizar una escena en una estructura arbórea donde la raíz comprende toda la escena y cada hoja contiene una subparte más pequeña. ^{[ 1 ]}

En la visión estéreo por computadora , un volumen delimitador reconstruido a partir de las siluetas de un objeto se conoce como " envoltura visual ". ^{[ 2 ]}

La elección del tipo de volumen delimitador para una aplicación determinada depende de varios factores: el coste computacional de calcular un volumen delimitador para un objeto, el coste de actualizarlo en aplicaciones donde los objetos pueden moverse o cambiar de forma o tamaño, el coste de determinar las 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 que no está asociado con el objeto delimitado, denominado espacio vacío . Los volúmenes delimitadores más sofisticados generalmente permiten menos espacio vacío, pero son computacionalmente más costosos. Es común utilizar 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.

Los tipos aquí tratados proporcionan volúmenes delimitadores convexos . Si se sabe que el objeto delimitador es convexo, esto no supone una restricción. Si se requieren volúmenes delimitadores no convexos, una alternativa es representarlos como la 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 volúmenes delimitadores se vuelven más complejos.

Un cuadro delimitador o cuadro delimitador mínimo ( MBB , por sus siglas en inglés) es un cuboide , o en 2D un rectángulo , que contiene el objeto. En la simulación dinámica , se prefieren los cuadros delimitadores a otras formas de volumen delimitador, como esferas o cilindros, para objetos con forma aproximadamente cúbica cuando la prueba de intersección debe ser bastante precisa. La ventaja es obvia, por ejemplo, para objetos que se apoyan unos sobre otros, como un coche sobre el suelo: una esfera delimitadora mostraría que el coche podría intersecar con el suelo, lo que requeriría una prueba más costosa del modelo real del coche; un cuadro delimitador muestra inmediatamente que el coche no interseca con el suelo, ahorrando la prueba más costosa.

Un rectángulo delimitador mínimo ( MBR ), el AABB más pequeño en 2D, se usa frecuentemente en la descripción de elementos de datos geográficos (o "geoespaciales"), sirviendo como una aproximación simplificada de la extensión espacial de un conjunto de datos (véase metadatos geoespaciales ) para la búsqueda de datos (incluidas las consultas espaciales, según corresponda) y su visualización. También es un componente básico del método de indexación espacial R-tree .

En muchas aplicaciones, el cuadro delimitador se alinea con los ejes del sistema de coordenadas, y entonces se conoce como cuadro delimitador alineado con los ejes (AABB ). Para distinguir el caso general de un AABB, a veces se denomina cuadro delimitadororientado a un cuadro delimitador(OBB ), o unOOBB se utiliza cuando se emplea el sistema de coordenadas localde un objeto existente. Las AABB son mucho más fáciles de comprobar para detectar intersecciones que las OBB, pero tienen la desventaja de que, al rotar el modelo, no se pueden rotar con él, sino que es necesario recalcularlas.

AUna cápsula delimitadora es unaesfera barrida(es decir, el volumen que ocupa una esfera al moverse a lo largo de un segmento de línea recta) que contiene el objeto. Las cápsulas se pueden representar mediante el radio de la esfera barrida y el segmento que recorre. Tiene características similares a las de un cilindro, pero es más fácil de usar, ya que la prueba de intersección es más sencilla. 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 se cumple para cápsulas rotadas arbitrariamente, razón por la cual resultan 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 alrededor de un eje vertical, pero no alrededor de otros ejes, y que, de otro modo, están restringidos a moverse únicamente mediante traslación. Dos cilindros alineados con el eje vertical se intersecan cuando, simultáneamente, sus proyecciones sobre el eje vertical (dos segmentos de línea) y sus proyecciones sobre el plano horizontal (dos discos circulares) también se intersecan. Ambas intersecciones son fáciles de comprobar. En losvideojuegos, los cilindros delimitadores se utilizan a menudo como volúmenes delimitadores para personas de pie.

AUn elipsoide delimitador es unelipsoideque contiene el objeto. Los elipsoides suelen ofrecer un ajuste más preciso 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 intersecar el objeto escalado con unaesfera unitaria. Se debe tener cuidado para evitar problemas si el escalado aplicado introducedistorsión. La distorsión 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, se trata de un círculo . Las esferas delimitadoras se representan mediante su centro y radio. Permiten detectar colisiones de forma muy rápida: 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 cierta medida sobre un eje y puede considerarse como lalosadelimitada entre dos planos. Una caja delimitadora 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 resulta muy útil para acelerar el recorte o la prueba de visibilidad de una curva B-Spline. Consulte«Algoritmos de recorte de círculos y B-Splines»en el apartado «Recorte (gráficos por ordenador)» para ver un ejemplo de uso.

La 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.

AEl politopo orientado discreto (DOP) generaliza la caja delimitadora. Un k-DOP es la intersección booleana de extensiones a lo largo dekdirecciones. Por lo tanto, unk-DOP es la intersección booleana deklosas delimitadoras y es unpolitopoque contiene el objeto (en 2D unpolígono; en 3D unpoliedro). Un rectángulo 2D es un caso especial de un 2-DOP, y una caja 3D es un caso especial de un 3-DOP. En general, los ejes de un DOP no tienen por qué ser ortogonales, y puede haber más ejes que dimensiones del espacio. Por ejemplo, una caja 3D 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, es decir, se reducen a un borde o un vértice.

Para algunos tipos de volúmenes delimitadores (OBB y poliedros convexos), una comprobación eficaz es la del teorema del eje separador . La idea es que, si existe un eje por el cual los objetos no se superponen, entonces no se intersecan. Generalmente, los ejes que se comprueban son los ejes básicos de los volúmenes (los ejes unitarios en el caso de un AABB, o los 3 ejes base de cada OBB en el caso de OBB). A menudo, esto se complementa con la comprobación de los productos vectoriales de los ejes anteriores (un eje de cada objeto).

En el caso de un AABB, esta prueba se convierte en un conjunto simple de pruebas de superposición en términos de los ejes unitarios. Para un AABB definido por M , N contra uno definido 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 ).           

Un AABB también puede proyectarse a lo largo de un eje, por ejemplo, si tiene aristas de longitud L y está centrado en C , y se proyecta a lo largo del eje N: ${\displaystyle r=0.5L_{x}|N_{x}|+0.5L_{y}|N_{y}|+0.5L_{z}|N_{z}|\,}$, y${\displaystyle b=C*N\,}$o${\displaystyle b=C_{x}N_{x}+C_{y}N_{y}+C_{z}N_{z}\,}$, y${\displaystyle m=br,n=b+r\,}$ donde m y n son las extensiones mínima y máxima.

Un OBB es similar en este aspecto, pero es un poco más complicado. Para un OBB con L y C como se indicó anteriormente, y con I , J y K como ejes base del OBB, entonces:

${\displaystyle r=0.5L_{x}|N*I|+0.5L_{y}|N*J|+0.5L_{z}|N*K|\,}$

${\displaystyle m=C*Nr{\mbox{ y }}n=C*N+r\,}$

Para los rangos m , n y o , p, se puede afirmar que no se intersecan si m  > p o o > n . Por lo tanto, al proyectar los rangos de dos OBB a lo largo de los ejes I, J y K de cada OBB y comprobar si no se intersecan, es posible detectar la no intersección. Al comprobar adicionalmente los productos vectoriales de estos ejes (I₀ _× I₁ _, I₀ _× J₁ _, ...), se puede tener mayor certeza de que la intersección es imposible.   

Este concepto de determinar la no intersección mediante la proyección de ejes también se aplica a poliedros convexos, aunque en este caso 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. Cabe destacar que esta descripción presupone que las comprobaciones se realizan en el espacio global.

La intersección de dos k -DOP se puede calcular de forma muy similar a los AABB: para cada orientación, simplemente se comprueban los dos intervalos correspondientes de los dos DOP. Así pues, al igual que los DOP son una generalización de los AABB, la prueba de intersección es una generalización de la prueba de superposición de AABB. La complejidad de la prueba de superposición de dos DOP es de 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 sencilla de comprobar los dos DOP es${\displaystyle D^{1},D^{2}}$para la intersección es encerrar la rotada,${\displaystyle D^{2}}$, por otro DOP envolvente más pequeño${\displaystyle {\tilde {D}}^{2}}$que está orientado con respecto a las orientaciones del primer DOP${\displaystyle D^{1}}$El procedimiento para ello es un poco más complejo, pero finalmente equivale a una multiplicación de matriz por vector de complejidad O( k ) . ^{[ 4 ]}

• Algoritmos de envolvente convexa
• Índice espacial
• Hitbox

• Ilustración de varios DOP para el mismo modelo, de epicgames.com