Share
La capacidad de dividir dinámicamente una forma convexa en dos formas separadas es una habilidad o herramienta muy valiosa para tener en tu arsenal de gamedev. Esta división permite tipos avanzados de simulación, como particiones de espacio binario para gráficos o física, entornos dinámicamente destructivos (¡fractura frágil!), Simulación de océano o agua, resolución de colisiones para motores de física, partición espacial binaria, y la lista continúa. Un gran ejemplo es el juego Fruit Ninja para Kinect..
¿Qué significa exactamente dividir una forma convexa? En dos dimensiones, nos referimos a una forma como un polígono; en tres dimensiones, nos referimos a una forma como poliedro. (Poliedros es la palabra que se usa para hacer referencia a más de un poliedro.
Propina: En general, los polígonos y poliedros convexos simplifican muchos aspectos de la manipulación y gestión del volumen o la malla. Debido a esta simplificación, el artículo completo asume polígonos convexos y poliedros convexos. Las formas cóncavas no son parte de ninguna discusión aquí. En general, las formas cóncavas complicadas se simulan como una colección de formas convexas unidas.
Para entender las ideas presentadas en este artículo, necesitará un conocimiento práctico de algunos lenguajes de programación y una comprensión sencilla del producto punto..
Una excelente manera de dividir formas en dos y tres dimensiones es hacer uso de la rutina de recorte de Sutherland-Hodgman. Esta rutina es bastante simple y muy eficiente, y también puede extenderse ligeramente para dar cuenta de la robustez numérica. Si no está familiarizado con el algoritmo, consulte mi artículo anterior sobre el tema.
Una comprensión de los planos en dos o tres dimensiones es también una necesidad. Cabe señalar que un plano bidimensional se podría pensar como una proyección de un plano tridimensional en dos dimensiones - o, en otras palabras, una línea.
Por favor, comprenda que un avión también puede considerarse como medio espacio. Cálculo de la distancia o la intersección de los puntos en espacios intermedios es un requisito previo: consulte la última sección de Cómo crear un motor de física 2D personalizado: el motor central para obtener información sobre este.
Consulte la fuente de demostración (también en Bitbucket) que he creado al leer este tutorial. Utilicé esta demostración para crear todas las imágenes GIF en el artículo. El código fuente está en C ++ (y debe ser compatible con varias plataformas), pero está escrito de manera que se pueda portar fácilmente a cualquier lenguaje de programación.
Antes de abordar el problema de dividir un polígono completo, echemos un vistazo al problema de dividir un triángulo a través de un plano de corte. Esto formará la base de la comprensión para pasar a una solución robusta y generalizada..
Lo bueno de la división de formas es que, a menudo, los algoritmos en 2D pueden extenderse sin muchos problemas directamente en 3D. Aquí, presentaré un algoritmo de división de triángulos muy simple para dos y tres dimensiones..
Cuando un triángulo se interseca con un plano de división, se deben generar tres nuevos triángulos. Aquí hay una imagen que muestra un triángulo antes y después de dividir a lo largo de un plano:
Dado un plano de división, se generan tres nuevos triángulos durante la operación de corte. Vamos a lanzar algo de código al descubierto, asumiendo que los tres vértices de un triángulo son a B C en el orden contrario a las agujas del reloj (CCW), y que sabemos que el borde ab (borde de los vértices a a b) han intersectado el plano de división:
// Recorte un triángulo contra un plano, sabiendo que // a to b cruza el plano de recorte // Referencia: Exactamente Bouyancy para Polyhedra por // Erin Catto en Game Programming Gems 6 SlidTriangle vacío (std :: vector & out, const Vec2 & a, // Primer punto en triángulo, CCW orden const Vec2 & b, // Segundo punto en triángulo, CCW orden const Vec2 & c, // Tercer punto en triángulo, CCW orden f32 d1, // Distancia del punto a al plano de división f32 d2 , // Distancia del punto b al plano de división f32 d3 // Distancia del punto c al plano de división) // Calcule el punto de intersección de a con b Vec2 ab = a + (d1 / (d1 - d2)) * (b - a); Triángulo tri; si (d1 < 0.0f) // b to c crosses the clipping plane if(d3 < 0.0f) // Calculate intersection point from b to c Vec2 bc = b + (d2 / (d2 - d3)) * (c - b); tri.Set( b, bc, ab ); out.push_back( tri ); tri.Set( bc, c, a ); out.push_back( tri ); tri.Set( ab, bc, a ); out.push_back( tri ); // c to a crosses the clipping plane else // Calculate intersection point from a to c Vec2 ac = a + (d1 / (d1 - d3)) * (c - a); tri.Set( a, ab, ac ); out.push_back( tri ); tri.Set( ab, b, c ); out.push_back( tri ); tri.Set( ac, ab, c ); out.push_back( tri ); else // c to a crosses the clipping plane if(d3 < 0.0f) // Calculate intersection point from a to c Vec2 ac = a + (d1 / (d1 - d3)) * (c - a); tri.Set( a, ab, ac ); out.push_back( tri ); tri.Set( ac, ab, b ); out.push_back( tri ); tri.Set( b, c, ac ); out.push_back( tri ); // b to c crosses the clipping plane else // Calculate intersection point from b to c Vec2 bc = b + (d2 / (d2 - d3)) * (c - b); tri.Set( b, bc, ab ); out.push_back( tri ); tri.Set( a, ab, bc ); out.push_back( tri ); tri.Set( c, a, bc ); out.push_back( tri );
Esperemos que el código anterior te haya asustado un poco. Pero no temas; todo lo que estamos haciendo aquí es calcular algunos puntos de intersección para saber cómo generar tres nuevos triángulos. Si uno hubiera examinado cuidadosamente la imagen anterior, las ubicaciones de los puntos de intersección podrían ser obvias: es donde la línea de puntos se encuentra con el plano de división y donde el borde ab intersecta el plano de división. Aquí hay un diagrama para su conveniencia:
A partir de este diagrama, es fácil ver que los triángulos de salida deben contener los vértices a, ac, ab, ac, c, b, y ab, ac, b. (Pero no necesariamente en este formato exacto; por ejemplo,, a B C sería el mismo triángulo que c, b, a porque los vértices fueron simplemente desplazados a la derecha.)
Para determinar qué vértices contribuyen a cuál de los tres triángulos nuevos, debemos determinar si el vértice una y vértice do Estar encima o debajo del plano. Dado que estamos asumiendo que el borde ab Se sabe que se está cruzando, podemos deducir implícitamente que segundo está en el lado opuesto del plano de recorte de una.
Si la convención de una distancia negativa desde un plano de división significa penetrante En el plano, podemos formular un predicado para determinar si un punto se interseca con un medio espacio: #define HitHalfspace (distance) ((distance) < 0.0f). Este predicado se utiliza dentro de cada Si declaración para verificar y ver si un punto está dentro del espacio medio del plano de recorte.
Existen cuatro casos de combinaciones de una y segundo golpeando el medio espacio del plano de recorte:
un | T T F F ----------- b | T F T F
Dado que nuestra función requiere que ambos una y segundo Estar en lados opuestos del plano, dos de estos casos son abandonados. Todo lo que queda es ver en qué lado do establece A partir de aquí, se conoce la orientación de los tres vértices; Los puntos de intersección y los vértices de salida se pueden calcular directamente..
Para utilizar el SliceTriangle () función, debemos encontrar un borde de intersección de un triángulo. La implementación a continuación es eficiente y se puede usar en todos los triángulos de la simulación para ser potencialmente divididos:
// Corta todos los triángulos dado un vector de triángulos. // Se genera una nueva lista de triángulos de salida. La antigua // lista de triángulos es descartada. // n - La normalidad del plano de recorte // d - Distancia del plano de recorte desde el origen // Referencia: Exactitud de compra para poliedros por // Erin Catto en gemas de programación de juegos 6 void SliceAllTriangles (const Vec2 & n, f32 d) std :: vector out; para (uint32 i = 0; i < g_tris.size( ); ++i) // Grab a triangle from the global triangle list Triangle tri = g_tris[i]; // Compute distance of each triangle vertex to the clipping plane f32 d1 = Dot( tri.a, n ) - d; f32 d2 = Dot( tri.b, n ) - d; f32 d3 = Dot( tri.c, n ) - d; // a to b crosses the clipping plane if(d1 * d2 < 0.0f) SliceTriangle( out, tri.a, tri.b, tri.c, d1, d2, d3 ); // a to c crosses the clipping plane else if(d1 * d3 < 0.0f) SliceTriangle( out, tri.c, tri.a, tri.b, d3, d1, d2 ); // b to c crosses the clipping plane else if(d2 * d3 < 0.0f) SliceTriangle( out, tri.b, tri.c, tri.a, d2, d3, d1 ); // No clipping plane intersection; keep the whole triangle else out.push_back( tri ); g_tris = out;
Después de calcular la distancia firmada de cada vértice triangular al plano de división, se puede usar la multiplicación para ver si dos puntos distintos se encuentran en lados opuestos de un plano. Dado que las distancias serán de un flotador positivo y negativo dentro de un par, el producto de los dos multiplicados juntos debe ser negativo. Esto permite el uso de un predicado simple para ver si hay dos puntos a cada lado de un plano: #define OnOppositeSides (distanceA, distanceB) ((distanceA) * (distanceB) < 0.0f).
Una vez alguna el borde se intersecta con el plano de división, los vértices de los triángulos cambian de nombre y se desplazan y inmediatamente pasado al interior SliceTriangle función. De esta manera, el primer borde de intersección encontrado cambia su nombre a ab.
Esto es lo que un producto de trabajo final puede parecer:
La división de triángulos de esta manera explica cada triángulo de manera independiente, y el algoritmo presentado aquí se extiende, sin ninguna creación adicional, de dos a tres dimensiones. Esta forma de recorte de triángulos es ideal cuando no se requiere la información de adyacencia de los triángulos, o cuando los triángulos recortados no se almacenan en ningún lugar de la memoria. Este es a menudo el caso cuando se computan volúmenes de intersecciones, como en la simulación de flotabilidad..
El único problema con dividir los triángulos de forma aislada es que no hay información sobre los triángulos que están adyacente a otro. Si examina el GIF anterior con cuidado, puede ver que muchos triángulos comparten vértices colineales y, como resultado, se pueden contraer en un solo triángulo para que se puedan representar de manera eficiente. La siguiente sección de este artículo aborda este problema con otro algoritmo más complejo (que utiliza todas las tácticas presentes en esta sección).
Ahora para el tema final. Suponiendo que se comprenda el algoritmo de Sutherland-Hodgman, es bastante fácil ampliar esta comprensión para dividir una forma con un plano y generar vértices en ambos Lados del plano. La robustez numérica puede (y debe) también ser considerada.
Examinemos brevemente los viejos casos de recorte de Sutherland-Hodgman:
// InFront = plane.Distance (point)> 0.0f // Behind = plane.Distance (point) < 0.0f Vec2 p1, p2; ClipPlane plane; case p1 InFront and p2 InFront push p2 case p1 InFront and p2 Behind push intersection case p1 Behind and p2 InFront push intersection push p2
Estos tres casos funcionan decentemente, pero en realidad no tienen en cuenta el grosor del plano de división. Como resultado, el error numérico puede desviarse cuando los objetos se mueven, causando una baja coherencia del marco temporal. Este tipo de inestabilidad numérica puede dar como resultado que una esquina se recorte en un cuadro y no en otro, y este tipo de fluctuación puede ser bastante feo visualmente, o inaceptable para la simulación física.
Otro beneficio de esta prueba de plano grueso es que los puntos que se encuentran muy cerca del plano realmente pueden considerarse como en El plano, que hace que la geometría recortada sea un poco más útil. ¡Es totalmente posible que un punto de intersección calculado se coloque numéricamente en el lado incorrecto de un plano! Aviones gruesos evitan problemas tan extraños..
Mediante el uso de planos gruesos para las pruebas de intersección, se puede agregar un nuevo tipo de caso: una colocación de puntos directamente en en un avión.
Sutherland-Hodgman debería modificarse así (con un punto flotante EPSILON para tener en cuenta los planos gruesos):
// InFront = plane.Distance (punto)> EPSILON // Behind = plane.Distance (point) < -EPSILON // OnPlane = !InFront( dist ) && !Behind( dist ) Vec2 p1, p2; ClipPlane plane; case p1 InFront and p2 InFront push p2 case p1 InFront and p2 Behind push intersection case p1 Behind and p2 InFront push intersection push p2 case any p1 and p2 OnPlane push p2
Sin embargo, esta forma de Sutherland-Hodgman solo genera vértices en un lado del plano divisor. Estos cinco casos se pueden extender fácilmente a un conjunto de nueve para generar vértices a cada lado de un plano de división:
// InFront = plane.Distance (punto)> EPSILON // Behind = plane.Distance (point) < -EPSILON // OnPlane = !InFront( dist ) && !Behind( dist ) Vec2 p1, p2; Poly front, back; ClipPlane plane; case p1 InFront and p2 InFront front.push( p2 ) case p1 OnPlane and p2 InFront front.push( p2 ) case p1 Behind and p2 InFront front.push( intersection ) front.push( p2 ) back.push( intersection ) case p1 InFront and p2 OnPlane front.push( p2 ) case p1 OnPlane and p2 OnPlane front.push( p2 ) case p1 Behind and p2 OnPlane front.push( p2 ) back.push( p2 ) case p1 InFront and p2 Behind front.push( intersection ) back.push( intersection ) back.push( p2 ) case p1 OnPlane and p2 Behind back.push( p1 ) back.push( p2 ) case p1 Behind and p2 Behind back.push( p2 )
Una implementación de estos nueve casos podría parecerse a la siguiente (derivada de la Detección de Colisión en Tiempo Real de Ericson):
// Divide un polígono a la mitad a lo largo de un plano de división usando un algoritmo de recorte // llame a Sutherland-Hodgman recorte // Recurso: Página 367 de Ericson (detección de colisión en tiempo real) void SutherlandHodgman (const Vec2 & n, f32 d, const Poly * poly, std :: vector * out) Poly frontPoly; Poly backPoly; uint32 s = poly-> vertices.size (); Vec2 a = poli-> vértices [s - 1]; f32 da = Punto (n, a) - d; para (uint32 i = 0; i < s; ++i) Vec2 b = poly->vértices [i]; f32 db = Punto (n, b) - d; if (InFront (b)) if (Behind (a)) Vec2 i = Intersect (b, a, db, da); frontPoly.vertices.push_back (i); backPoly.vertices.push_back (i); frontPoly.vertices.push_back (b); else if (Behind (b)) if (InFront (a)) Vec2 i = Intersect (a, b, da, db); frontPoly.vertices.push_back (i); backPoly.vertices.push_back (i); else if (On (a)) backPoly.vertices.push_back (a); backPoly.vertices.push_back (b); else frontPoly.vertices.push_back (b); if (On (a)) backPoly.vertices.push_back (b); a = b; da = db; if (frontPoly.vertices.size ()) out-> push_back (frontPoly); if (backPoly.vertices.size ()) out-> push_back (backPoly);
Aquí hay un ejemplo de Sutherland-Hodgman en acción:
Vale la pena señalar que los polígonos finales se pueden representar como una lista de vértices con el formato de abanico triangular..
Hay un problema que debe tener en cuenta: al calcular un punto de intersección de ab y un plano de división, este punto sufre de cuantización numérica. Esto significa que cualquier valor de intersección es una aproximación del valor de intersección real. También significa que el punto de intersección licenciado en Letras no es numéricamente igual; La pequeña deriva numérica resultará en dos valores diferentes!
Ejemplo de una grieta visible entre triángulos como resultado de un recorte inconsistente (imagen inspirada en el libro de detección de colisiones en tiempo real de Ericson). Una rutina de recorte ingenua puede cometer un gran error al calcular los puntos de intersección a ciegas, lo que puede provocar uniones en T u otros huecos en la geometría. Para evitar tal problema, se debe utilizar una orientación de intersección consistente. Por convención, los puntos deben recortarse de un lado de un plano a otro. Este ordenamiento estricto de intersecciones garantiza que se calcule el mismo punto de intersección y resolverá posibles huecos en la geometría (como se muestra en la imagen de arriba, hay un resultado de recorte consistente a la derecha).
Para poder renderizar texturas sobre formas divididas (tal vez al dividir sprites), necesitarás un entendimiento de las coordenadas UV. Una discusión completa de las coordenadas UV y el mapeo de texturas está más allá del alcance de este artículo, pero si ya tiene esta comprensión, debería ser fácil transformar los puntos de intersección en el espacio UV.
Por favor, comprenda que una transformación del espacio mundial al espacio UV requiere una transformación de cambio de base. Dejaré las transformaciones UV como ejercicio para el lector.!
En este tutorial, observamos algunas técnicas simples de álgebra lineal para abordar el problema de dividir dinámicamente formas genéricas. También abordé algunos problemas de robustez numérica. Ahora debería poder implementar su propio código de división de formas, o usar la fuente de demostración, para lograr muchos efectos o funciones avanzadas e interesantes para la programación general del juego..
Accentsconagua