Share
Recorte es el proceso de determinar qué región del espacio está dentro de otra región del espacio. Esto es especialmente importante en áreas de estudio tales como gráficos de computadora y simulación física. Por ejemplo, al representar un mundo en la pantalla, es mejor saber qué habrá en la pantalla antes de procesar cualquier dato. Esto permite ignorar muchos datos extraños, mientras que solo se procesa y presenta lo que verá el usuario.
En la simulación física, los cuerpos rígidos a menudo se encuentran interpenetrante - es decir, dos objetos separados se superponen. Esto es malo. La interpenetración es algo que nunca sucede en el mundo real, pero es un problema que debe resolverse en la detección de colisiones. Muchas veces, una forma se recorta contra otra para determinar qué características realmente se tocan. Desde aquí se puede iniciar una respuesta de colisión..
Las características avanzadas de los motores de juego se pueden implementar con algún tipo de recorte; simulación de flotabilidad, planos de vista de cámara; fracturamiento frágil, generación de contactos con la prueba de eje de separación; Todas estas cosas (y mucho más) se pueden lograr con algoritmos de recorte. De hecho, este tipo de recorte fue necesario en mi tutorial anterior sobre la construcción de un motor de física de cuerpo rígido.
Este artículo requiere que tengas un buen entendimiento de:
Las áreas de estudio anteriores se pueden aprender de una amplia variedad de recursos en Internet (como la guía de Wolfire para el álgebra lineal o la Academia Khan, y no son tan difíciles de aprender!
Muchas rutinas de recorte complejas implican hacer uso de un solo tipo de operación: dividir una forma con un solo plano. La división de una forma por un plano implica tomar una forma y cortar en dos partes a través de un plano sólido.
Es importante darse cuenta de que dividir una forma con un plano es una herramienta fundamental en esta rutina de recorte..
Vea las excelentes animaciones de Davide Cervone para una clara demostración de esto:
El recorte de Sutherland Hodgman es mi rutina de recorte favorita, ya que funciona para recortar bucles de línea contra aviones. Con este algoritmo, dada una lista de vértices de entrada y una lista de planos, se puede calcular una salida de vértices nuevos que existen puramente dentro del conjunto de planos.
El término plano se puede utilizar para referirse tanto a un plano en 3D como a 2D. Un plano 2D también puede llamarse línea.Podemos imaginar la lista de vértices como un solo polígono. Podemos imaginar (por ahora) la lista de planos como una sola línea. Visualizar esto en dos dimensiones podría parecerse a la siguiente imagen:
Con el recorte de Sutherland Hodgman, el polígono de la derecha es la forma deseada, mientras que el polígono rojo de la izquierda es la forma de entrada y aún no se ha recortado. La línea azul representa un plano de división en dos dimensiones. Se puede usar cualquier número de planos de división; en el ejemplo anterior solo se utiliza un plano de división. Si se utilizan muchos planos de división, el recorte se producirá en un plano a la vez, eliminando cada vez más una forma original para generar una nueva:
Para simplificar, trabajemos en dos dimensiones estrictas. Al dividir un polígono contra un plano, será importante saber en qué lado del plano se encuentra un punto dado..
Arriba es la forma más utilizada para encontrar la distancia desde un punto a un plano. Tenga en cuenta que el símbolo de punto en la ecuación anterior representa el producto de punto.
La distancia no necesita ser calculada explícitamente; el vector normal norte no necesita ser normalizado (es decir, no necesita tener una longitud de exactamente una unidad). Todo lo que necesita ser verificado es el signo del resultado de la distancia. re. Si norte no se normaliza entonces re estará en unidades de la longitud de norte. Si norte se normaliza, entonces re Estarán en unidades equivalentes a las unidades espaciales mundiales. Es importante darse cuenta de esto, ya que permite realizar el cálculo para ver si re es positivo o negativo Positivo re denota que el punto pag Está en la parte frontal del avión. Negativo significa que está en la parte posterior.
Ahora, ¿qué queremos decir exactamente con los lados "frontal" y "trasero" de un avión? Bueno, realmente depende de lo que definas delante y detrás como. Por lo general, "frente" significa que está en el mismo lado del plano que lo normal.
Vamos a bucear directamente en el algoritmo. Tome una exploración rápida sobre el pseudocódigo:
Polygon SutherlandHodgman (const Polygon startingPolygon, Plane [] clippingPlanes) Polygon output = startingPolygon para cada plano ClippingPlane en clippingPlanes input = output output.Clear () Vec2 startingPoint = input.Last () Para cada Vec2 EndPoint en la entrada si se iniciaPoint y endPoint en front of clippingPlane out.push (endPoint) más si startingPoint delante y endPoint detrás de clippingPlane out.push (Intersection (clippingPlane, startingPoint, endPoint)) else si startingPoint y endPoint detrás de clippingPlane out.push (Intersection (clippingPlane, startingPoint, endPoint) ) out.push (endPoint) endPoint = startingPoint return output
El algoritmo toma un polígono de entrada y algunos planos de recorte, y genera un nuevo polígono. La idea es recortar cada segmento de línea del polígono de entrada contra un plano de recorte a la vez. Esta imagen de Wikimedia Commons demuestra esto bastante bien:
Cada operación de recorte tiene solo unos pocos casos diferentes en los que generar vértices, y puede resumirse así:
// 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
La mejor manera de entender este algoritmo es dibujar una forma 2D en una hoja de papel y dibujar una línea recta a través de la forma. Luego haga un bucle a lo largo de los vértices del polígono y realice el algoritmo de Sutherland-Hodgman y dibuje los resultados. Esto creará una intuición sobre cómo el algoritmo se ejecuta en cada línea de forma secuencial, asegurándose de mantener todos los vértices detrás del plano..
Después de que corra su propio lápiz y papel, pruebe esta gran página web. Hay algunas imágenes impresionantes y un applet de Java (en la parte superior de la página) que le permite al usuario ver partes del algoritmo ejecutarse!
Calcular la intersección de un plano dados dos puntos es muy simple. La idea es utilizar el cálculo de la distancia para encontrar la distancia de cada punto a un plano. Dadas estas distancias, una intersección se puede calcular utilizando interpolación lineal.
Propina: La interpolación lineal es un concepto extremadamente útil para entender, ya que tiene una aplicación prolífica en todos los programas de gráficos y en el software de simulación física. La interpolación lineal puede denominarse coloquialmente como lerp. Cualquier cosa puede ser interpolada linealmente desde una posición inicial hasta una posición final, siempre y cuando ecuación de movimiento es lineal.En general, la fórmula para interpolar linealmente desde comienzo a fin con intersección alfa es:
Lerp (start, end, alpha) return start * (1 - alpha) + end * alphaPropina: En el ejemplo anterior,
Accentsconagua
alfa es lo que se llama un interpolante. Los interpolantes se utilizan en los cálculos de interpolación lineal para calcular las posiciones entre los puntos de inicio y final. Sabiendo esto, las distancias desde el plano hasta cada punto se pueden usar como valores para calcular una alfa interpolante Las variables t1 y t2 Puede representar las distancias al plano de p1 y p2 respectivamente.
En este sentido, el punto de intersección es simplemente un Lerp desde el punto de inicio hasta el punto final, dado un tiempo de intersección.
Este algoritmo puede extenderse fácilmente en un espacio tridimensional y ejecutarse allí. (Este algoritmo se podría realizar en cualquier dimensión superior, sea lo que sea lo que signifique). Sin embargo, en aplicaciones prácticas, este algoritmo generalmente nunca es actualmente Realizado en 3D. Mediante el uso de transformaciones inversas inteligentes, el problema de recortar un poliedro 3D contra un plano puede simplificarse (en ciertos escenarios) a un polígono 2D a una rutina de recorte de polígono. Esto permite una optimización computacional significativa..
De manera similar, si uno estudiara el código fuente de Bullet Physics, encontraría que el recorte se realiza en un espacio tridimensional único, a pesar de que realmente se está realizando el recorte en 3D. Esto se debe a la capacidad de calcular un interpolante válido dada solo una dimensión del espacio del problema.
Por ejemplo, si uno sabe el tiempo de intersección de la X valores de un problema simple, este tiempo de intersección se puede usar como interpolante para realizar una Lerp sobre un punto tridimensional.
Vamos a examinar esto con un poco más de detalle. Echa un vistazo al siguiente diagrama:
Supongamos que la línea amarilla es el suelo en una posición y de 0. Ahora asuma que la posición inicial y está en 10, y la posición y final es en -1. Calculemos una posición de intersección e intersección válida a lo largo de la coordenada y:
// alpha = 0.9 / 10.0f float alpha = 0.9f // finalY = 0.0f float finalY = Lerp (y1, y2, alpha);
Lo anterior se puede leer como "90% de la manera de 10 a -1", que sería cero. Este interpolante se puede aplicar a tipos de datos arbitrarios, incluido un vector bidimensional:
// alpha = 9.0f / 10.0f float alpha = 0.9f Vec2 finalPosition = Lerp (p1, p2, alpha);
El código anterior en realidad calcularía la coordenada x correcta para el momento del impacto, sin siquiera realizar operaciones con la coordenada x para determinar el interpolante. Esta idea de calcular interpolantes y aplicarlos a dimensiones más altas de las que se calcularon es una excelente manera de optimizar el código..
Hay algunos problemas que pueden persistir cuando se ejecuta una implementación ingenua de esta rutina de recorte. Cada vez que se calcula el error numérico del punto de intersección se introduce en el cálculo. Esto plantea un problema importante al dividir un polígono con un plano mientras se genera una salida en ambos lados del avion. Para generar una salida para ambos lados de un plano de división, el algoritmo original de Sutherland-Hodgman debe modificarse ligeramente, y aquí es donde surgirán los problemas..
Cada vez que se calcula un punto de intersección, se produce un error numérico. Este es un problema ya que el punto de intersección se calcula desde el punto UNA apuntar segundo Será ligeramente diferente al cálculo del punto. segundo apuntar UNA. Para evitar estos problemas, la intersección debe calcularse de manera consistente. Esto evita una terrible T-Junction problema. Está bien si hay un error numérico siempre que el error sea consistente.
Problema de empalme en T: Un espacio entre dos mallas que hace que la rasterización de triángulos deje un espacio visible entre tres triángulos. Usualmente causado por un mal manejo de la máquina épsilon durante el cálculo de punto flotante. Posibles soluciones: transformaciones consistentes de vértice; soldadura de vértice post procesamiento.
Otro problema es cuando se determina si un punto está en un lado de un plano u otro. Por toda una serie de razones, se deben hacer verificaciones de aviones gruesos. La idea es tratar un plano como un plano grueso, en lugar de uno con un ancho infinitesimalmente pequeño. Esto permite que surja un caso adicional dentro de la rutina de Sutherland-Hodgman: el en el avión caso.
flotante D = plano. Distancia (punto); // EPSILON es un número numéricamente significativo y visualmente insignificante. Quizás 0.00001f. bool OnPlane (float D) return D> -EPSILON y D < EPSILON;
Si se encuentra algún punto en el plano de recorte, simplemente presione el punto final. Esto traerá el total de 3 casos a 4 en total. Para más información sobre EPSILON, mira aquí.
La mejor referencia para este algoritmo de recorte reside en el libro de detección de colisiones en tiempo real de Christer Ericson (también conocido como el Libro Naranja). Puedes encontrar este libro en casi todos los estudios de juegos existentes..
Más allá de desembolsar mucho dinero por un libro, existen un par de recursos gratuitos:
El recorte de Sutherland-Hodgman es una excelente manera de realizar el recorte en espacios 2D y 3D. Este tipo de rutina se puede aplicar para resolver muchos problemas diversos, algunos de los cuales son aplicables en áreas de estudio bastante avanzadas. Como siempre, siéntase libre de hacer cualquier pregunta en la sección de comentarios a continuación.!
