conversión de formas basadas Azulejos 2D a polígonos simplificados

Question

Como se ve en la imagen de arriba, que tienen una matriz 2D de azulejos, cada uno con 4 puntos en mi mundo del juego. Estoy buscando un método para convertir estas formas construidas a partir de fichas individuales en formas de polígono simplificadas (sin vértices innecesarios, solo las necesarias para formar el contorno).

He estado mirando alrededor, aquí y en otros lugares y he tenido muy poca suerte. Pero tal vez no conozco la terminología correcta para buscar. Cualquier ayuda es apreciada.

Información adicional: Estoy buscando utilizar esto para optimizar la iluminación dinámica. Si alguien tiene un enfoque diferente para lograr sombras dinámicas rápidas en un mundo basado en fichas, eso también responderá la pregunta.

Answer 1

I sugieren siguiente algoritmo:

1. Almacenamiento de todas las posiciones de borde en una matriz 2D (posición de borde es el centro de borde).
2. Contando los bordes duplicados en este conjunto (1 no es duplicado, 2 se cruza con otro borde. Otros valores son imposibles).
3. Escogiendo el primer borde sin marcar de la matriz con el conteo de duplicación 1 (sin duplicados) y aplicando el algoritmo de llenado recursivo simple en la dirección de certeza (en el sentido de las agujas del reloj, por ejemplo) hasta que alcance el primer borde. Todos estos bordes formarán un polígono simplificado. Si no se ha fundado el borde sin marcar, entonces GOTO 5.
4. Marcando todos estos bordes desde el paso 3 como se usa. GOTO al paso 3.
5. Fin.

Para una representación más intuitiva del algoritmo, he publicado una imagen a continuación.

Answer 2

El enfoque ingenuo sería simplemente atravesar cada una de las fichas y marcar los bordes de transición en un polígono, pero podría reutilizar una rutina edge detection común para un mejor rendimiento.

Después de eso, probablemente esté interesado en teselar esos polígonos para convertirlos en colecciones de triángulos (lo que hace que la sombra/iluminación/intersección matemática sea mucho más simple), el único problema en este caso es que termine con un polígono cóncavo, pero un teselador decente debería permitirle dividirlo en polígonos convexos. No creo que XNA tenga nada incorporado para el teselado, por lo que es posible que necesite encontrar una biblioteca de utilidad para que lo haga por usted.