Matemáticas en Gamedev es simple. Triangulación y Triangle.Net en la Unidad

Hola a todos! Mi nombre es Grisha y soy el fundador de CGDevs. La matemática es una herramienta genial para desarrollar juegos. Pero si decimos que es difícil de administrar sin comprender los vectores y las matrices , entonces los algoritmos de triangulación no son tan necesarios, pero con la ayuda de ellos se resuelve una gran cantidad de problemas interesantes. Hoy me gustaría hablar sobre una herramienta bastante importante en geometría computacional, como las triangulaciones y su aplicación en la industria del juego. Además, escribí un puerto y algunos contenedores para la excelente biblioteca Triangle.Net para Unity. Si está interesado, bienvenido a cat. Enlace a github adjunto.

¿Qué es la triangulación?

En el caso general, la triangulación es una partición de un objeto geométrico en triángulos. Este concepto en sí mismo es bastante simple. Un ejemplo básico de triangulación en el caso de los motores de juego es una malla. Estrictamente hablando, una malla puede consistir no solo en triángulos, sino en motores de juegos por una variedad de razones, son mallas que consisten en triángulos que se toman.



Las triangulaciones son diferentes, pero uno de los tipos más populares de triangulaciones es la triangulación de Delaunay. Este tipo de triangulación se distingue por la propiedad de que en el círculo circunscrito alrededor de cada triángulo, solo se encuentran los vértices de este triángulo.

¿Por qué son necesarios?

En general, fuera de la industria del juego, una gran cantidad de tareas se resuelven con la ayuda de triangulaciones. En el desarrollo del juego, la primera tarea que viene a la mente es la malla de navegación. Navmesh es una estructura de datos que determina cuánto espacio puede caminar un jugador. Evita tareas computacionales tan complejas como determinar colisiones con parte del entorno.

El segundo problema interesante que se puede resolver utilizando la triangulación de Delaunay en el desarrollo del juego es la generación de terrenos y objetos representados como un conjunto de puntos. La principal ventaja de la triangulación de Delaunay en este caso es que, en función de sus propiedades, le permite evitar triángulos muy afilados que interferirán y crearán artefactos en el tirrain.



Además, utilizando la triangulación restringida de Delaunay y algoritmos como el segundo algoritmo de Chew y el algoritmo de Ruppert, puede generar mallas aún mejor para tirrains y generar buenas mallas para otra aplicación: el método de elementos finitos.

El método de elementos finitos en sí es uno de los métodos por los cuales se resuelven los problemas de la física aplicada. En gamedev, le permite resolver muchos problemas asociados con la simulación de deformaciones, simulaciones de fluidos y otros utilizados para especiales. efectos Por lo general, para grabar efectos en animación, ya que en tiempo real el método tiene una complejidad computacional demasiado alta. Un detalle importante al usar el método es que el error del método depende de los ángulos de los triángulos en la cuadrícula. Si hay ángulos muy agudos en la cuadrícula, el método genera un gran error, por esta razón se necesitan los algoritmos enumerados anteriormente.



Y, por supuesto, en general, la generación de mallas procesales. Como ejemplo, un proyecto github muestra una escena con la capacidad de dibujar mallas. Algunos acertijos físicos usan esta aplicación como mecánica básica. Pero además, los algoritmos de triangulación permiten usar la generación de procedimientos para resolver problemas como la destructibilidad de procedimientos, etc.

Además de gamedev, las triangulaciones se utilizan en redes, visión por computadora, varios algoritmos analíticos, así como en qué problemas de geometría computacional, como combinar y eliminar polígonos entre sí (que a menudo es útil en problemas que surgen en el desarrollo de juegos)

Recorte de oreja con agujeros

Quizás uno de los algoritmos de triangulación más simples. No proporciona la mejor cuadrícula y tiene la mayor complejidad computacional O (n ^ 2) en el peor de los casos.

Puedes leer más sobre esto en este artículo.

Bowyer - algoritmo Watson

Un algoritmo que genera la triangulación de Delaunay sobre un conjunto de puntos. En general, como con la mayoría de los algoritmos de Delaunay, si se implementa correctamente, la complejidad algorítmica es O (n log n), donde n es el número de vértices. Pero en algunos casos puede tomar O (n ^ 2).

Las desventajas con respecto al Ear Clipping es que este algoritmo construye triangulación convexa y en la implementación básica no involucra agujeros en la cuadrícula resultante.

Procesamiento de refinamiento de Delaunay

El segundo algoritmo de Chew y el algoritmo de Ruppert son algoritmos que le permiten ingresar restricciones en la triangulación de Delaunay y establecer el ángulo mínimo del triángulo en la cuadrícula. Un detalle importante de los algoritmos es que pueden entrar en un bucle infinito y están garantizados para dar resultados en ángulos entre aproximadamente 20.7 grados y 29 grados. La capacidad de establecer un ángulo mínimo es importante para resolver los problemas descritos anteriormente.

El segundo algoritmo de Chew se implementa en el paquete gratuito www.cs.cmu.edu/~quake/triangle.html y su puerto en .Net archive.codeplex.com/?p=triangle

Triangle.Net para Unity

Bueno, dado que con la ayuda de triangulaciones puedes resolver tantas tareas geniales, en las vacaciones quería implementar mi envoltorio para Unity, para que siempre tenga una herramienta útil a mano. En esta implementación, el algoritmo de triangulación funciona en promedio para O (n), y en el peor de los casos para O (n * log n), donde n es el número de vértices. Por ejemplo, cuando se prueban vértices de 1kk dispersos aleatoriamente en un cuadrado, las unidades en el editor del Intel Core i7-8700 construyeron una cuadrícula en un promedio de 7.56 segundos.

Las principales diferencias con la biblioteca original en la presencia de métodos de extensión diseñados para Unity, así como el reemplazo de doble con flotante en toda la biblioteca (+ un par de operadores específicos para la conversión) Doble en la unidad, no tiene mucho sentido. Si consideramos las simulaciones físicas, usaría una aplicación separada en una biblioteca plus, y el resultado de los cálculos ya le dio a Unity puramente para visualización. Y también cambió el nombre del tipo de malla a TriangleNetMesh para no derribar en relación con la malla de Unity. Sí, ya están en un espacio de nombres diferente, pero sin embargo, creo que los recién llegados se sentirían un poco abrumados por el hecho de que con la ayuda de un Mesh obtenemos otro.

La esencia de la biblioteca es que primero debe especificar el llamado polígono. Luego, en base a ello, ya genera la malla. Para que esto funcione con estructuras de datos unitarias, se han introducido varios métodos de extensión.



Por ejemplo de demostración y uso, se realizó una escena de demostración especial con la capacidad de dibujar mallas. Puede familiarizarse con él y el puerto de la biblioteca en el proyecto github.

Gracias por su atencion! Espero que el puerto y el artículo sean útiles para alguien y se aclare un poco por qué se necesita la triangulación y el conocimiento de las matemáticas en su conjunto. Intentaré continuar divulgando aplicaciones y métodos para resolver varios problemas matemáticos en el desarrollo de juegos. En la geometría computacional en sí todavía hay muchas cosas interesantes, pero además hay muchas otras secciones interesantes de matemáticas superiores.