Límite de volumen - Bounding volume
En gráficos por computadora y geometría computacional , un volumen delimitador para un conjunto de objetos es un volumen cerrado 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 mediante el uso de volúmenes simples para contener objetos más complejos. Normalmente, los volúmenes más simples 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 al revés. Por lo tanto, es posible limitar la descripción al caso de un solo objeto, que se supone no vacío y limitado (finito).
Usos
Los volúmenes de límite 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 ver las pruebas frustum . Si el rayo o el tronco visual no se cruza con el volumen delimitador, no se puede cruzar con el objeto contenido dentro, lo que permite un rechazo trivial . De manera similar, si el tronco 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" (renderizados; rasterizados ).
En la detección de colisiones , cuando dos volúmenes delimitadores no se cruzan, los objetos contenidos no pueden colisionar.
La prueba con un volumen delimitador suele ser mucho más rápida que la prueba 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, computacionalmente es un desperdicio comparar cada polígono con el volumen de la vista si el objeto no es visible. (Los objetos en pantalla deben 'recortarse' en la pantalla, independientemente de si sus superficies son realmente visibles).
Para obtener volúmenes delimitadores de objetos complejos, una forma común es dividir los objetos / escena usando un gráfico de escena o más específicamente una jerarquía de volumen delimitador , como por ejemplo árboles OBB . La idea básica detrás de esto es organizar una escena en una estructura en forma de árbol donde la raíz comprende toda la escena y cada hoja contiene una subparte más pequeña.
Tipos comunes
La elección del tipo de volumen límite para una aplicación dada está determinada por una variedad de factores: el costo computacional de calcular un volumen límite para un objeto, el costo de actualizarlo en aplicaciones en las que los objetos pueden moverse o cambiar de forma o tamaño , el costo 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 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 utilizar varios tipos en conjunto, como uno barato para una prueba rápida pero aproximada junto con un tipo más preciso pero también más caro.
Todos los tipos tratados aquí dan volúmenes delimitadores convexos . Si se sabe que el objeto delimitado 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 caras a medida que los cuadros delimitadores se vuelven más sofisticados.
Un cuadro delimitador 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 los objetos que se apoyan sobre otros, como un automóvil apoyado en el suelo: una esfera delimitadora mostraría que el automóvil posiblemente se cruza con el suelo, que luego debería ser rechazado por una prueba más costosa. del modelo real del automóvil; un cuadro delimitador muestra inmediatamente que el automóvil no se cruza con el suelo, lo que ahorra la prueba más costosa.
En muchas aplicaciones, el cuadro delimitador está alineado con los ejes del sistema de coordenadas, y entonces se conoce como una caja de eje alineados de delimitación ( AABB ). Para distinguir el caso general de un AABB, un cuadro delimitador arbitrario a veces se denomina cuadro delimitador orientado ( OBB ) o un OOBB cuando se utiliza el sistema de coordenadas local de un objeto existente . Los AABB son mucho más sencillos de probar la intersección que los OBB, pero tienen la desventaja de que cuando se gira el modelo, no se pueden rotar simplemente con él, sino que se deben volver a calcular.
Una cápsula delimitadora es una esfera barrida (es decir, el volumen que toma una esfera cuando 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 por el que se barre 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 cruzan 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 cruzan si la distancia entre los segmentos de las cápsulas es menor que la suma de sus radios. Esto se aplica a las cápsulas giradas arbitrariamente, por lo que en la práctica son más atractivas que los cilindros.
Un cilindro delimitador es un cilindro que 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 3-D que solo pueden girar alrededor de un eje vertical pero no alrededor de otros ejes, y por lo demás están limitados a moverse solo por traslación. Dos cilindros alineados con el eje vertical se cruzan cuando, simultáneamente, sus proyecciones en el eje vertical se cruzan, que son dos segmentos de línea, así como sus proyecciones en el plano horizontal, dos discos circulares. Ambos son fáciles de probar. En los videojuegos , los cilindros delimitadores se utilizan a menudo como volúmenes delimitadores para personas de pie.
Un elipsoide delimitador es un elipsoide que 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 los ejes principales del elipsoide en una cantidad igual al inverso multiplicativo de los radios del elipsoide, reduciendo así el problema a la intersección del objeto escalado con una esfera unitaria . Se debe tener cuidado para evitar problemas si la escala aplicada introduce sesgo . La inclinación puede hacer que el uso de elipsoides no sea 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 2-D, esto es un círculo . Las esferas delimitadas están representadas por el centro y el radio. Son muy rápidos para probar la colisión entre sí: dos esferas se cruzan cuando la distancia entre sus centros no excede la suma de sus radios. Esto hace que las esferas delimitadas sean apropiadas para objetos que pueden moverse en cualquier número de dimensiones.
Una losa delimitante es el volumen que se proyecta hasta cierto punto sobre un eje y se puede considerar como la losa delimitada entre dos planos. Un cuadro delimitador es la intersección de losas delimitadoras orientadas ortogonalmente. Se han utilizado losas de delimitación para acelerar el trazado de rayos
Un triángulo delimitador en 2-D es bastante útil para acelerar la prueba de visibilidad o recorte 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.
Un casco convexo 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 casco convexo es un politopo.
Un politopo de orientación discreta ( DOP ) generaliza el cuadro delimitador. Un k-DOP es la intersección booleana de extensiones a lo largo de k direcciones. Por lo tanto, un k -DOP es la intersección booleana de k losas delimitantes y es un politopo convexo que contiene el objeto (en 2-D un polígono ; en 3-D un poliedro ). Un rectángulo 2-D es un caso especial de 2-DOP, y una caja 3-D es un caso especial de 3-DOP. En general, los ejes de un DOP no tienen por qué ser ortogonales y puede haber más ejes que dimensiones de espacio. Por ejemplo, una caja 3-D que está biselada en todos los bordes y esquinas se puede construir como 13-DOP. El número real de caras puede ser inferior a 2 veces k si algunas caras se degeneran, se reducen a un borde o un vértice.
Un rectángulo delimitador mínimo o MBR , el mínimo AABB en 2-D, se usa con frecuencia en la descripción de elementos de datos geográficos (o "geoespaciales"), y sirve como un proxy simplificado para la extensión espacial de un conjunto de datos (ver metadatos geoespaciales ) para este propósito. de búsqueda de datos (incluidas las consultas espaciales, según corresponda) y visualización. También es un componente básico del método R-tree de indexación espacial .
Comprobaciones básicas de intersecciones
Para algunos tipos de volumen delimitador (OBB y poliedros convexos), una comprobación eficaz es la del teorema del eje de separación . La idea aquí es que, si existe un eje por el cual los objetos no se superponen, entonces los objetos no se cruzan. Normalmente, los ejes controlados son los de los ejes básicos para los volúmenes (los ejes unitarios en el caso de un AABB, o los 3 ejes básicos de cada OBB en el caso de los OBB). A menudo, a esto le sigue también la verificación de los productos cruzados de los ejes anteriores (un eje de cada objeto).
En el caso de un AABB, estas pruebas se convierten en un simple conjunto de pruebas de superposición en términos de ejes unitarios. Para un AABB definido por M , N contra uno definido por O , P no se cruzan 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 se puede proyectar a lo largo de un eje, por ejemplo, si tiene bordes de longitud L y está centrado en C , y se proyecta a lo largo del eje N: y o , y
donde myn son las extensiones mínima y máxima. .
Un OBB es similar a este respecto, pero es un poco más complicado. Para un OBB con L y C como arriba, 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 cruzan, 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 al verificar la no intersección, es posible detectar la no intersección. Comprobando adicionalmente a lo largo de los productos cruzados 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 del eje también se extiende a los poliedros convexos, sin embargo, se utilizan las normales de cada cara poliédrica en lugar de los ejes base, y las extensiones se basan en los productos punto mínimo y máximo de cada vértice. contra los ejes. Tenga en cuenta que esta descripción asume que las comprobaciones se realizan en el espacio mundial.
La intersección de dos k- DOP se puede calcular de manera muy similar a los AABB: para cada orientación, simplemente verifica los dos intervalos correspondientes de los dos DOP. Entonces, al igual que DOP es una generalización de las AABB, la prueba de intersección es una generalización de la prueba de superposición AABB. La complejidad de la prueba de superposición de dos DOP está en O ( k ) . Esto supone, sin embargo, que ambas DOP se dan con respecto al mismo conjunto de orientaciones. Si se gira uno de ellos, esto ya no es cierto. En ese caso, una manera relativamente fácil de verificar la intersección de los dos DOP es encerrar el girado , con otro DOP de cierre 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 eventualmente equivale a una multiplicación vectorial matricial de complejidad O ( k ) también.
Ver también
- Esfera delimitadora
- Algoritmos de casco convexo
- Cuadro delimitador mínimo
- Rectángulo delimitador mínimo
- Índice espacial
