Como converter um bitmap 2D (Usado para terrenos) em uma malha poligonal 2D para colisão?

7

Então, eu estou fazendo um jogo do tipo artilharia, parecido com o Worms, com todo o material usual, como terrenos destrutíveis, etc ... e enquanto eu poderia usar a colisão por pixel que não me dá normais de colisão ou algo assim. Converter tudo isso em uma malha também significaria que eu poderia usar uma biblioteca de física existente, o que seria melhor do que qualquer coisa que eu possa fazer sozinha.

Já vi pessoas mencionando isso usando Marching Squares para obter contornos no bitmap, mas não consigo encontrar nada que mencione como transformá-los em uma malha (a menos que se refira a uma malha 3D com linhas de contorno que definem diferentes alturas, que NÃO é o que eu quero). No momento, posso obter um contorno básico dos Marching Squares que se parece com isso (onde as linhas semelhantes à grade no fundo seriam as 'células' dos Marching Squares):

Resultado das Praças de Marcha

Isso precisa ser interpolado para obter um resultado mais suave e preciso, mas essa é a ideia geral. Eu tinha algumas idéias de como transformar isso em uma malha, mas muitas delas não funcionavam em certos casos, e a que eu pensei que funcionaria perfeitamente acabou sendo muito lenta e eu nem terminei ainda! Idealmente, gostaria que o que eu acabasse usando fosse rápido o suficiente para fazer todos os quadros em casos como armas de disparo rápido ou ferramentas de escavação.

Estou pensando que deve haver algum tipo de algoritmo / técnica existente para transformar algo assim em uma malha, mas não consigo encontrar nada. Eu olhei para algumas coisas como a triangulação de Delaunay, mas até onde eu sei, isso não vai lidar corretamente com formas côncavas, como no exemplo acima, e também não é responsável por buracos no terreno.

Vou seguir a técnica que criei para comparação e acho que vou ver se alguém tem uma ideia melhor. Antes de tudo, interpole as linhas de contorno dos Marching Squares, criando vértices a partir das extremidades da linha e obtendo vértices onde as linhas cruzam as bordas das células (Importante). Em seguida, para cada célula contendo vértices, crie polígonos usando 2 vértices e um canto da célula como o terceiro vértice (provavelmente o canto mais próximo).

insira a descrição da imagem aqui

Faça isso para cada célula e acho que você deve ter uma malha que represente com precisão o bitmap original (embora haja apenas polígonos nas bordas do bitmap, e grandes áreas preenchidas no meio estarão vazias). O único problema é que isso envolve cortar todos os pixels uma vez para os Marching Squares iniciais e percorrer todas as células (altura da imagem + 1 x largura da imagem + 1) pelo menos duas vezes, o que acaba sendo muito lento para qualquer tamanho decente imagem...

Megadanxzero
fonte
11
"isso não me dá normais de colisão ou algo assim." Quem disse? Você pode verificar os pixels próximos e gerar uma colisão normal muito bem. De fato, você pode usar cubos de marchas sob demanda para fazer exatamente isso. Não há necessidade de uma malha; você só precisa de um normal, certo?
Nicol Bolas
Ah, sim, eu já fiz algo parecido na verdade, mas não é ótimo. Quero dizer, funciona bastante bem, mas definitivamente não é perfeitamente. Usar os Marching Squares em uma pequena área ao redor do ponto de colisão provavelmente seria uma solução um pouco melhor que a anterior, mas ainda vejo problemas com ele. Por exemplo, uma área de amostra muito pequena produzirá um normal impreciso porque você perde detalhes, enquanto uma área muito grande significa que você provavelmente terá que calcular a média do ângulo das arestas que obtém (o que novamente pode ser impreciso).
Megadanxzero
E é claro que isso está ignorando o fato de que eu ainda teria que fazer minha própria física, o que provavelmente não acabaria sendo muito bom, em vez de apenas usar um mecanismo de física robusto existente. Não conheço nenhum mecanismo de física que permita que você anule a detecção de colisão por seu próprio material por pixel e, em seguida, forneça uma colisão normal para reagir. Pode ser que algo assim exista embora.
Megadanxzero
Qual a precisão de um normal que você precisa? Você está fazendo um jogo no estilo Terra Ardente / Worms. Acho que seus jogadores o perdoarão se o salto não for perfeito. Quero dizer, você acha que a velha Terra Escaldada do DOS estava construindo malhas altamente precisas e assim por diante? Você acha que mesmo os jogos modernos do Worms se esforçam bastante para calcular essas coisas?
Nicol Bolas
11
A parte "física" de um sistema de física ( especialmente em 2D) é a parte mais fácil. É a parte da "colisão" que é difícil.
Nicol Bolas

Respostas:

2

Eu não trabalhei com motores de física 2D antes, não sei exatamente como a malha de colisão deve parecer.

Se é simplesmente um conjunto de triângulos 2D, você deve procurar métodos de triangulação. Por exemplo, triangulação restrita de Delauney .

As triangulações de Delaunay maximizam o ângulo mínimo de todos os ângulos dos triângulos na triangulação; eles tendem a evitar triângulos finos.

O que é bom quando se trata de renderizar esses triângulos, pelo menos, e também pode ou não ser bom para a detecção de colisões.

Uma triangulação restrita do Delauny incorpora arestas fixas, que seriam as arestas detectadas. Essa biblioteca pode fornecer o que você precisa


fonte
Ah, eu não tinha ouvido falar da triangulação restrita de Delaunay, que parece que poderia ser exatamente o que eu preciso. Definitivamente vou ter que investigar. Obrigado!
Megadanxzero