c++ - Creando OOBB desde puntos
graphics geometry (3)
¿Cómo puedo crear un OOBB mínimo para los puntos dados? Crear AABB o una esfera es muy fácil, pero tengo problemas para crear un OOBB mínimo.
[editar]
La primera respuesta no me dio buenos resultados. No tengo gran nube de puntos. Tengo poca cantidad de puntos. Estoy haciendo generación de geometría de colisión. Por ejemplo, el cubo tiene 36 puntos (6 lados, 2 triángulos cada uno, 3 puntos por cada triángulo). Y el algoritmo del primer post dio malos resultados para el cubo. Ejemplo de puntos para el cubo: http://nopaste.dk/download/3382 (debe devolver el eje de identidad)
El método PCA / covariance / eigenvector esencialmente encuentra los ejes de un elipsoide que se aproxima a los vértices de su objeto. Debería funcionar para objetos aleatorios, pero dará malos resultados para objetos simétricos como el cubo. Esto se debe a que el elipsoide aproximado para un cubo es una esfera y una esfera no tiene ejes bien definidos. Así que no estás obteniendo los ejes estándar que esperas.
Quizás si sabe de antemano que un objeto es, por ejemplo, un cubo, puede usar un método especializado y usar PCA para todo lo demás.
Por otro lado, si desea calcular el verdadero OBB, existen implementaciones existentes que puede utilizar, por ejemplo, http://www.geometrictools.com/LibMathematics/Containment/Containment.html (específicamente http://www.geometrictools.com/LibMathematics/Containment/Wm5ContMinBox3.cpp ). Creo que esto implementa el algoritmo aludido en los comentarios a su pregunta.
Citando de esa página:
Los archivos ContMinBox3 implementan un algoritmo para calcular el cuadro de volumen mínimo que contiene los puntos. Este método calcula el casco convexo de los puntos, un poliedro convexo. La caja de volumen mínimo tiene una cara coincidente con una cara del poliedro convexo o tiene direcciones de eje dadas por tres bordes mutuamente perpendiculares del poliedro convexo. Cada cara del poliedro convexo se procesa proyectando el poliedro al plano de la cara, calculando el rectángulo de área mínima que contiene las proyecciones, y calculando el intervalo de longitud mínima que contiene las proyecciones en la perpendicular de la cara. El rectángulo de área mínima y el intervalo de longitud mínima se combinan para formar un cuadro candidato. Luego se procesan todos los triples de bordes del poliedro convexo. Si algún triple tiene bordes perpendiculares entre sí, se calcula la caja más pequeña con ejes en las direcciones de los bordes. De todos estos cuadros, el que tiene el volumen más pequeño es el cuadro de volumen mínimo que contiene el conjunto de puntos original.
Si, como usted dice, sus objetos no tienen una gran cantidad de vértices, el tiempo de ejecución debe ser aceptable.
En una discusión en http://www.gamedev.net/topic/320675-how-to-create-oriented-bounding-box/ el autor de la biblioteca anterior arroja más luz sobre el tema:
El enfoque de Gottschalk para la construcción OBB es calcular una matriz de covarianza para el conjunto de puntos. Los vectores propios de esta matriz son los ejes OBB. El promedio de los puntos es el centro OBB. No se garantiza que el OBB tenga el volumen mínimo de todas las cajas que contienen. Un árbol OBB se construye dividiendo recursivamente la malla de triángulo cuyos vértices son el conjunto de puntos. Se mencionan un par de heurísticas para la división.
El cuadro de volumen mínimo (MVB) que contiene un conjunto de puntos es el cuadro de volumen mínimo que contiene el casco convexo de los puntos. El casco es un poliedro convexo. Basado en un resultado de Joe O''Rourke, el MVB está apoyado por una cara del poliedro o por tres bordes perpendiculares del poliedro. "Soportado por una cara" significa que el MVB tiene una cara coincidente con una cara de poliedro. "Apoyado por tres bordes perpendiculares" significa que tres bordes perpendiculares de la MVB coinciden con los bordes del poliedro.
Como indica jyk, las implementaciones de cualquiera de estos algoritmos no son triviales. Sin embargo, nunca deje que eso lo desanime a intentarlo :) Una AABB puede ser una buena opción, pero también puede ser una muy mala opción. Considere un cilindro "delgado" con puntos finales en (0,0,0) y (1,1,1) [imagine que el cilindro es el segmento de línea que conecta los puntos]. El AABB es 0 <= x <= 1, 0 <= y <= 1, y 0 <= z <= 1, con un volumen de 1. El MVB tiene el centro (1,1,1) / 2, un eje (1,1,1) / sqrt (3), y una extensión para este eje de sqrt (3) / 2. También tiene dos ejes adicionales perpendiculares al primer eje, pero las extensiones son 0. El volumen de este cuadro es 0. Si le da al segmento de línea un poco de grosor, el MVB se vuelve un poco más grande, pero aún tiene un volumen mucho más pequeño La de la AABB.
El tipo de caja que elija dependerá de los datos de su propia aplicación.
Las implementaciones de todo esto se encuentran en mi sitio web www.geometrictools.com. Utilizo la heurística de división mediana para los árboles de volumen delimitador. La construcción de MVB requiere un buscador de cascos convexos en 2D, un buscador de cascos convexos en 3D y un método para calcular el área de área mínima que contiene un conjunto de puntos planos.
Hay una nueva biblioteca ApproxMVBB en C ++ en línea que calcula una aproximación para el cuadro de límite de volumen mínimo . Su lanzamiento bajo licencias MPL 2.0, y escrito por mí.
Si tiene tiempo, consulte: gabyx.github.io/ApproxMVBB
La biblioteca es compatible con C ++ 11 y solo necesita Eigen http://eigen.tuxfamily.org . Las pruebas muestran que una aproximación de 140 millones de puntos en 3D se puede calcular en un tiempo razonable (de 5 a 7 segundos) dependiendo de la configuración de la aproximación.
Primero tienes que calcular el centroide de los puntos, en pseudcode
mu = sum(0..N, x[i]) / N
entonces tienes que calcular la matriz de covarianza
C = sum(0..N, mult(x[i]-mu, transpose(x[i]-mu)));
Tenga en cuenta que el mult realiza una multiplicación de matriz (3x1) por la multiplicación de matriz (1x3), y el resultado es una matriz de 3x3.
Los vectores propios de la matriz C definen los tres ejes del OBB.