Existem algoritmos simples (ou bem documentados) para operações básicas de CSG em polígonos 2D?
Estou procurando uma maneira de 'adicionar' várias formas de colisão 2D sobrepostas. Eles podem ser convexos ou côncavos, mas serão formas fechadas, definidas como um conjunto de segmentos de linha, sem interseções automáticas.
O uso disso seria construir um conjunto limpo de arestas de colisão, para uso com um mecanismo de física 2D, a partir de uma cena que consiste em muitos objetos colocados arbitrariamente (e freqüentemente sobrepostos), cada um com sua própria forma de colisão.
Para começar, eu preciso apenas 'adicionar' formas, mas a capacidade de 'subtrair', criar buracos, também pode ser útil.
2d
collision-detection
mathematics
geometry
csg
bluescrn
fonte
fonte
Respostas:
É para projetista de níveis ou para o mecanismo?
Para o designer de níveis - você precisará desse código para, por exemplo, combinar objetos estáticos. Pesquise APIs gráficas vetoriais para a solução, a tarefa parece bastante comum para SVG, PostScript, WMF, etc. Primeiro tente usar a API CombineRgn Win32 :-)
Para o mecanismo do jogo - sugiro que você não faça o que deseja. Você gastará uma quantidade enorme de CPU combinando seus objetos. Você gastará uma quantidade enorme de previsões errôneas de ramificações verificando as condições da borda, testando se dois segmentos se cruzam ou não, etc. E esse processo deve ser repetido a cada quadro para a parte visível do seu mapa.
Basta verificar as caixas delimitadoras e colidir objetos individuais. Se as formas do seu objeto forem muito complexas - simplifique-as enquanto exporta dados para o mecanismo e use formas diferentes para colisão e desenho.
Atualização : veja meu código C # GDI + que faz o que você deseja. Você pode escrever facilmente o mesmo em C ++: a classe GraphicsPath é apenas um invólucro fino sobre as funções correspondentes do gdiplus.dll.
fonte
Escrevi uma pequena prova de conceito que usava o CSG para fazer jogadas de terra / vermes arrasados. Eu o implementei com o gluTessellate . Em seguida, mapeei os triângulos em mosaico nos polígonos do Box2D. Eu poderia adicionar e subtrair a sujeira da simulação, além de fazer e preencher furos.
O maior problema que encontrei ao usar o gluTessallate é que ele não tem problema em retornar triângulos degenerados. Eu tive que filtrá-las antes de mover os triângulos em mosaico para o mecanismo de física.
Uma das coisas boas do gluTessallate é que é possível determinar a adjacência a partir das informações de retorno de chamada. Eu nunca fui além, mas em teoria você poderia usar a adjacência e o SCC para detectar com precisão as ilhotas.
fonte
GLU_TESS_BOUNDRY_ONLY
. O link que eu forneço tem uma seção curta especificamente sobre CSG.