python c++ math 3d collision-detection

python - ¿Detectar si un cubo y un cono se cruzan?



c++ math (4)

Considera dos objetos geométricos en 3D:

  • un cubo alineado con los ejes y definido por la posición de su centro y su extensión (longitud del borde)
  • un cono no alineado con los ejes y definido por la posición de su vértice, la posición del centro de su base y el medio ángulo en el vértice

Aquí hay un pequeño código para definir estos objetos en C ++:

// Preprocessor #include <iostream> #include <cmath> #include <array> // 3D cube from the position of its center and the side extent class cube { public: cube(const std::array<double, 3>& pos, const double ext) : _position(pos), _extent(ext) {;} double center(const unsigned int idim) {return _position[idim];} double min(const unsigned int idim) {return _position[idim]-_extent/2;} double max(const unsigned int idim) {return _position[idim]+_extent/2;} double extent() {return _extent;} double volume() {return std::pow(_extent, 3);} protected: std::array<double, 3> _position; double _extent; }; // 3d cone from the position of its vertex, the base center, and the angle class cone { public: cone(const std::array<double, 3>& vert, const std::array<double, 3>& bas, const double ang) : _vertex(vert), _base(bas), _angle(ang) {;} double vertex(const unsigned int idim) {return _vertex[idim];} double base(const unsigned int idim) {return _base[idim];} double angle() {return _angle;} double height() {return std::sqrt(std::pow(_vertex[0]-_base[0], 2)+std::pow( _vertex[1]-_base[1], 2)+std::pow(_vertex[2]-_base[2], 2));} double radius() {return std::tan(_angle)*height();} double circle() {return 4*std::atan(1)*std::pow(radius(), 2);} double volume() {return circle()*height()/3;} protected: std::array<double, 3> _vertex; std::array<double, 3> _base; double _angle; };

Me gustaría escribir una función para detectar si la intersección de un cubo y un cono está vacía o no:

// Detect whether the intersection between a 3d cube and a 3d cone is not null bool intersection(const cube& x, const cone& y) { // Function that returns false if the intersection of x and y is empty // and true otherwise }

Aquí hay una ilustración del problema (la ilustración está en 2D, pero mi problema está en 3D):

¿Cómo hacerlo de manera eficiente (estoy buscando un algoritmo, por lo que la respuesta puede ser en C, C ++ o Python)?

Nota: Aquí la intersección se define como: existe un volumen 3D no nulo que está en el cubo y en el cono (si el cubo está dentro del cono, o si el cono está dentro del cubo, se cruzan).

Para el código

Esta respuesta será un poco más general que tu problema (considero una caja en lugar de un cubo, por ejemplo). Adaptarse a su caso debe ser realmente sencillo.

Algunas definiciones

/* Here is the cone in cone space: + ^ /|/ | /*| / | H / | / | / / | +---------+ v * = alpha (angle from edge to axis) */ struct Cone // In cone space (important) { double H; double alpha; }; /* A 3d plane v ^----------+ | | | | +----------> u P */ struct Plane { double u; double v; Vector3D P; }; // Now, a box. // It is assumed that the values are coherent (that''s only for this answer). // On each plane, the coordinates are between 0 and 1 to be inside the face. struct Box { Plane faces[6]; };

Línea - intersección del cono

Ahora, calculemos la intersección entre un segmento y nuestro cono. Tenga en cuenta que haré cálculos en el espacio del cono. Tenga en cuenta también que tomo el eje Z para que sea el vertical. Cambiarlo a Y se deja como un ejercicio para el lector. La línea se supone que está en el espacio del cono. La dirección del segmento no está normalizada; en cambio, el segmento es de la longitud del vector de dirección, y comienza en el punto P :

/* The segment is points M where PM = P + t * dir, and 0 <= t <= 1 For the cone, we have 0 <= Z <= cone.H */ bool intersect(Cone cone, Vector3D dir, Vector3D P) { // Beware, indigest formulaes ! double sqTA = tan(cone.alpha) * tan(cone.alpha); double A = dir.X * dir.X + dir.Y * dir.Y - dir.Z * dir.Z * sqTA; double B = 2 * P.X * dir.X +2 * P.Y * dir.Y - 2 * (cone.H - P.Z) * dir.Z * sqTA; double C = P.X * P.X + P.Y * P.Y - (cone.H - P.Z) * (cone.H - P.Z) * sqTA; // Now, we solve the polynom At² + Bt + C = 0 double delta = B * B - 4 * A * C; if(delta < 0) return false; // No intersection between the cone and the line else if(A != 0) { // Check the two solutions (there might be only one, but that does not change a lot of things) double t1 = (-B + sqrt(delta)) / (2 * A); double z1 = P.Z + t1 * dir.Z; bool t1_intersect = (t1 >= 0 && t1 <= 1 && z1 >= 0 && z1 <= cone.H); double t2 = (-B - sqrt(delta)) / (2 * A); double z2 = P.Z + t2 * dir.Z; bool t2_intersect = (t2 >= 0 && t2 <= 1 && z2 >= 0 && z2 <= cone.H); return t1_intersect || t2_intersect; } else if(B != 0) { double t = -C / B; double z = P.Z + t * dir.Z; return t >= 0 && t <= 1 && z >= 0 && z <= cone.H; } else return C == 0; }

Rect - intersección del cono

Ahora, podemos verificar si una parte rectangular de un plan intersecta el cono (esto se usará para verificar si una cara del cubo se cruza con el cono). Todavía en el espacio del cono. El plan se pasa de una manera que nos ayudará: 2 vectores y un punto. Los vectores no están normalizados, para simplificar los cálculos.

/* A point M in the plan ''rect'' is defined by: M = rect.P + a * rect.u + b * rect.v, where (a, b) are in [0;1]² */ bool intersect(Cone cone, Plane rect) { bool intersection = intersect(cone, rect.u, rect.P) || intersect(cone, rect.u, rect.P + rect.v) || intersect(cone, rect.v, rect.P) || intersect(cone, rect.v, rect.P + rect.u); if(!intersection) { // It is possible that either the part of the plan lie // entirely in the cone, or the inverse. We need to check. Vector3D center = P + (u + v) / 2; // Is the face inside the cone (<=> center is inside the cone) ? if(center.Z >= 0 && center.Z <= cone.H) { double r = (H - center.Z) * tan(cone.alpha); if(center.X * center.X + center.Y * center.Y <= r) intersection = true; } // Is the cone inside the face (this one is more tricky) ? // It can be resolved by finding whether the axis of the cone crosses the face. // First, find the plane coefficient (descartes equation) Vector3D n = rect.u.crossProduct(rect.v); double d = -(rect.P.X * n.X + rect.P.Y * n.Y + rect.P.Z * n.Z); // Now, being in the face (ie, coordinates in (u, v) are between 0 and 1) // can be verified through scalar product if(n.Z != 0) { Vector3D M(0, 0, -d/n.Z); Vector3D MP = M - rect.P; if(MP.scalar(rect.u) >= 0 || MP.scalar(rect.u) <= 1 || MP.scalar(rect.v) >= 0 || MP.scalar(rect.v) <= 1) intersection = true; } } return intersection; }

Caja - intersección de cono

Ahora, la parte final: todo el cubo:

bool intersect(Cone cone, Box box) { return intersect(cone, box.faces[0]) || intersect(cone, box.faces[1]) || intersect(cone, box.faces[2]) || intersect(cone, box.faces[3]) || intersect(cone, box.faces[4]) || intersect(cone, box.faces[5]); }

Para las matemáticas

Todavía en el espacio del cono, las ecuaciones del cono son:

// 0 is the base, the vertex is at z = H x² + y² = (H - z)² * tan²(alpha) 0 <= z <= H

Ahora, la ecuación paramétrica de una línea en 3D es:

x = u + at y = v + bt z = w + ct

El vector de dirección es (a, b, c), y el punto (u, v, w) se encuentra en la línea.

Ahora, pongamos las ecuaciones juntas:

(u + at)² + (v + bt)² = (H - w - ct)² * tan²(alpha)

Luego, después de desarrollar y volver a factorizar esta ecuación, obtenemos lo siguiente:

At² + Bt + C = 0

donde A, B y C se muestran en la primera función de intersección. Simplemente resuelva esto y verifique las condiciones de contorno en z y t.

  1. imaginar 2 líneas infinitas

    • eje de un cono
    • línea que pasa por un punto P (centro del cubo para los principiantes) que es perpendicular al eje del cono.

    El cono es conocido por ti, así que es fácil, la segunda línea se define como

    P+t*(perpendicular vector to cone axis)

    Este vector se puede obtener mediante el producto cruzado del vector del eje del cono y el vector perpendicular a su imagen (asumiendo el eje Z). El t es el parámetro de valor escalar ...

  2. calcular la intersección de estas 2 líneas / ejes

    si no sabes las ecuaciones, descárgalas o googlealas. Deje que el punto de intersección sea Q

  3. si el punto de intersección Q no se encuentra dentro del cono

    (entre el vértice y la base), entonces el punto P no está cruzando el cono. De las ecuaciones de intersección obtendrás los parámetros t1 y t2

    • deje t1 ser para la línea del eje P
    • y t2 para la línea del eje del cono

    si el vector de dirección de la línea del eje es también la longitud del cono, entonces la intersección está dentro del cono si t2 = <0,1>

  4. si P no está dentro del triángulo (cono cortado al plano generado por esos 2 ejes)

    esto también es fácil de conocer la posición de Q dentro del cono ( t2 ) para que sepa que el cono está en el eje P de Q a la distancia de R*t2 donde R es el radio de la base del cono. Entonces puede calcular |PQ| y compruebe si es <=R*t2 o use directamente t1 (si el vector de dirección del eje P es la unidad).

    si la distancia es más grande, entonces el punto R*t2 no intersecta con el cono.

  5. si # 3 y # 4 son positivos, entonces P intersecta el cono

    • Espero que no te importe esta es tu imagen con algunas cosas añadidas para mayor claridad

[notas]

Ahora la parte más difícil es la de los bordes cuando ningún vértice del cubo se cruza con el cono, pero el cubo se está intersectando de todos modos. Esto puede ocurrir cuando ||PQ|-R*t2| = <0,half cube size> ||PQ|-R*t2| = <0,half cube size> En este caso, debe verificar más puntos y luego solo los vértices del cubo a lo largo de la cara del cubo más cercano.

Otro enfoque es:

  1. crear una matriz de transformación para el cono

    Dónde:

    • su vértice como origen
    • su eje como +Z eje +Z
    • y el plano XY es paralelo a su base

    entonces cualquier punto está dentro del cono si

    • Z = <0,h>
    • X*X + Y*Y <= (R*Z/h)^2 o X*X + Y*Y <= (R*Z*tan(angle))^2

  2. convertir vértices de cubos en espacio de cono

    y compruebe si hay algún vértice dentro del cono; también puede verificar todas las líneas de borde del cubo con las condiciones del n. ° 1 (algebraicamente) o usar más puntos a lo largo de las caras del cubo como en el método anterior.

Discusión de chat: http://chat..com/rooms/48756/discussion-between-spektre-and-joojaa

Hace algunos años, hice un algoritmo eficiente para probar la intersección entre un cono y un aabb para algún código de renderizado. Hace poco necesitaba esta prueba para algo en lo que estoy trabajando ahora, así que la volví a visitar y la hice aún más eficiente. He pasado mucho más tiempo del que me importa admitir que estoy trabajando en este problema, así que decidí ahorrarle miseria y publicar el código. Como tal, esta es AFAIK una solución completamente única y no se encontrará en un libro de texto (es decir, la solución de David Eberly).

BIG EDIT: mi algoritmo anterior manejó la mayoría de las situaciones lo suficientemente bien como para no notar ningún problema, hasta que tuve un bloque de tiempo lo suficientemente grande como para probar todas las situaciones con rigor. Tenía un pequeño margen de error en un caso y un margen de error bastante grande en otro cuando se compara con el enfoque de fuerza bruta de 6 aviones. La prueba de caja de segmentos que estaba haciendo al final no podía dar cuenta de todas las posibles situaciones extrañas en las que el cono expansible podría penetrar la caja. Se veía bien en mis casos de prueba 2D y mal dibujados, pero falló en la práctica. Mi nueva idea es un poco más cara, pero es a prueba de balas.

Los pasos que realiza la nueva versión son los siguientes:

1.) Salir temprano si el vértice está en el cuadro delimitador.

2.) Identifica las caras que el cono puede tocar (Máx. De 3) y agrega sus vértices a una matriz.

3.) Proyecte todos los vértices de la matriz en "espacio de cono".

4.) Salida temprana si los vértices proyectados están dentro del cono

5.) Realice una prueba de círculo-polígono contra la matriz de vértices y el radio del cono para atravesar las intersecciones de borde con el polígono en el borde del cono

bool Intersect(const Cone& pCone) const { Vector3 pFaceVerts[12]; U32 uVertCount; int piClipSigns[3]; U32 uClipCount = GetClipInfo(pCone.GetApex(), piClipSigns); switch (uClipCount) { // If the clip count is zero, the apex is fully contained in the box xcase 0: { return true; } // 1) Clips single face, 4 vertices, guaranteed to not touch any other faces xcase 1: { int iFacet = piClipSigns[0] != 0 ? 0 : (piClipSigns[1] != 0 ? 1 : 2); GetFacetVertices(iFacet, piClipSigns[iFacet], pFaceVerts); uVertCount = 4; } // 2) Clips an edge joining two candidate faces, 6 vertices // 3) Clips a vertex joining three candidate faces, 7 vertices xcase 2: acase 3: { uVertCount = 0; for (U32 iFacet = 0; iFacet < 3; iFacet++) { if (piClipSigns[iFacet] != 0) { GetFacetVertices(iFacet, piClipSigns[iFacet], pFaceVerts + uVertCount); uVertCount += 4; } } FixVertices(pFaceVerts, uVertCount); } } // Project vertices into cone-space F32 fConeRadiusSquared = Square(pCone.GetRadius()); F32 pfLengthAlongAxis[6]; bool bOutside = true; for (U32 i = 0; i < uVertCount; i++) { pfLengthAlongAxis[i] = Dot(pCone.GetAxis(), pFaceVerts[i] - pCone.GetApex()); bOutside &= Clamp1(pfLengthAlongAxis[i], LargeEpsilon, pCone.GetHeight() - LargeEpsilon); } // Outside the cone axis length-wise if (bOutside) { return false; } for (U32 i = 0; i < uVertCount; i++) { Vector3 vPosOnAxis = pCone.GetApex() + pCone.GetAxis() * pfLengthAlongAxis[i]; Vector3 vDirFromAxis = pFaceVerts[i] - vPosOnAxis; F32 fScale = (pCone.GetHeight() / pfLengthAlongAxis[i]); F32 x = fScale * Dot(vDirFromAxis, pCone.GetBaseRight()); F32 y = fScale * Dot(vDirFromAxis, pCone.GetBaseUp()); // Intersects if any projected points are inside the cone if (Square(x) + Square(y) <= fConeRadiusSquared) { return true; } pFaceVerts[i] = Vector2(x, y); } // Finally do a polygon circle intersection with circle center at origin return PolygonCircleIntersect(pFaceVerts, uVertCount, pCone.GetRadius()); }

GetClipInfo:

inline U32 GetClipInfo(const Vector3& P, int piClipSigns[3]) const { U32 N = 0; for (U32 i = 0; i < 3; i++) { if (P[i] < m_vMin[i]) { piClipSigns[i] = -1; N++; } else if (P[i] > m_vMax[i]) { piClipSigns[i] = +1; N++; } else { piClipSigns[i] = 0; } } return N; }

GetFacetVertices y FixVertices son ligeramente hacky en este momento, pero obtienen los vértices en la cara y arreglan los vértices para que sean convexos y ordenados por CCW, respectivamente.

Una alternativa sería simplemente proyectar todos los vértices en el espacio del cono sin una lógica sofisticada, pero necesito que el mío sea lo más rápido posible, así que lo descompuse en varios casos.

Intenté varios otros enfoques, especialmente una prueba de eje de separación entre el eje del cono y la caja, y usé el eje de separación más grande para obtener la cara más cercana para probar con PolygonCircleIntersect, pero identifiqué un caso de falla y lo arrojé.

Información: no sé si esta idea ya es propiedad intelectual patentada (en su región), o no, o cómo averiguarlo, o lo que sea que eso signifique. Hago esto por diversion. :)

Pero, aquí está la carne de res:

  • Paso 1: Aproximación: para mayor eficiencia, trate ambos objetos como esferas (use esferas externas). Calcule su distancia (entre sus dos puntos centrales), para descubrir si están lo suficientemente cerca como para cruzarse. Rápidamente devuelve falso, si no pueden cruzarse (porque su distancia es mayor que la suma del radio de ambas esferas).

  • Paso 2: Computación exacta: esta es la forma más sencilla de hacerlo: Interprete el cono como un lote de píxeles tridimensionales denominados vóxeles (o legos ): elija la resolución (granularidad) que considere aceptable (tal vez 0.01). Crea un vector apuntando desde (0,0,0) a cualquier punto de vóxel dentro del volumen de tu cono (comenzando en el punto que ya llamaste "vértice"). Devuelve verdadero, si la coordenada de ese vóxel existe dentro de tu cubo dado. Repita esto para cada voxel que pueda calcular para su objeto de cono, basado en la granularidad elegida.

  • Paso 3: si nada coincide , devuelve falso.

Optimización: la función que determina si un punto 3-D dado está dentro del cubo podría ser optimizable, al considerar la esfera interna del cubo. Es decir, cualquier punto 3-D dado está dentro del cubo, si está lo suficientemente cerca del centro de la esfera interna del cubo para estar dentro de esa esfera. La diversión comienza cuando comienzas a llenar las esquinas del cubo vacías con esferas adicionales para una mayor optimización (esto es totalmente opcional).

Estoy seguro de que hay más optimizaciones posibles para el paso 2. Sin embargo, lo bueno de este enfoque es que puede ajustar libremente la granularidad, para sintonizar entre el tiempo de cálculo y la precisión de cálculo.

También puede crear un solucionador que reduce automáticamente la granularidad en múltiples iteraciones. Lo que significa que la precisión aumenta con el tiempo (para una mejor resolución).