Implementando CSG 2D (para formas de colisão)?

7

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.

bluescrn
fonte
Eu mesmo adicionando uma resposta - como acabei usando: sourceforge.net/projects/polyclipping - em vez de tentar uma implementação do zero. Até agora, ele está fazendo o trabalho muito bem, e era muito fácil de usar (com C #). A Wikipedia tem links para uma boa quantidade de informações sobre o assunto, assim que comecei a pesquisar usando a terminologia correta: en.wikipedia.org/wiki/ Boolean_operations_on_polygons
bluescrn
Aqui está uma implementação javascript fantástica do 3D CSG. Isso certamente é um exagero para o seu problema, mas o código é pequeno, limpo e bem documentado, para que você possa aprender bastante estudando-o.
DaleyPaley 17/04

Respostas:

3

É 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.

static class GraphicsPathExt
{
    [DllImport( @"gdiplus.dll" )]
    static extern int GdipWindingModeOutline( HandleRef path, IntPtr matrix, float flatness );

    static HandleRef getPathHandle( GraphicsPath p )
    {
        return new HandleRef( p, (IntPtr)p.GetType().GetField( "nativePath", BindingFlags.NonPublic | BindingFlags.Instance ).GetValue( p ) );
    }

    public static void FlattenPath( this GraphicsPath p )
    {
        HandleRef h = getPathHandle( p );
        int status = GdipWindingModeOutline( h, IntPtr.Zero, 0.25F );
        // TODO: see http://msdn.microsoft.com/en-us/library/ms534175(VS.85).aspx and throw a correct exception.
        if( 0 != status )
            throw new ApplicationException( "GDI+ error " + status.ToString() );
    }
}

class Program
{

    static void Main( string[] args )
    {
        PointF[] fig1 = 
        {
            new PointF(-50, 0),
            new PointF(0, 50),
            new PointF(50, 0),
        };

        PointF[] fig2 = 
        {
            new PointF(-50, 25),
            new PointF(50, 25),
            new PointF(0, -25),
        };

        GraphicsPath path1 = new GraphicsPath();
        path1.AddLines( fig1 );
        path1.CloseAllFigures();

        GraphicsPath path2 = new GraphicsPath();
        path2.AddLines( fig2 );
        path2.CloseAllFigures();

        GraphicsPath combined = new GraphicsPath();
        combined.AddPath( path1, true );
        combined.AddPath( path2, true );
        combined.FlattenPath();

        foreach (var p in combined.PathPoints)
        {
            Console.WriteLine( "<{0}, {1}>", p.X, p.Y );
        }
    }
}
Soonts
fonte
2

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.

deft_code
fonte
Interessante, vou ter que ler sobre isso. No entanto, estou tentando ficar longe das malhas triangulares - e lidar exclusivamente com as bordas do contorno (como para fins de colisão, qualquer borda interna / fechada anexada a um vértice no contorno pode causar colisões indesejadas). Mas talvez uma malha triangular como passo intermediário, antes de filtrar as arestas interiores, seja uma abordagem possível?
bluescrn
11
O gluTessellate também possui um modo de estrutura de tópicos GLU_TESS_BOUNDRY_ONLY. O link que eu forneço tem uma seção curta especificamente sobre CSG.
Deft_code
Uau, isso parece surpreendentemente poderoso, eu nunca tinha percebido que a glu continha essa funcionalidade. Parece que é uma opção (apesar meu ser ferramenta baseada D3D), mas ainda estou muito curioso sobre os algoritmos que estariam envolvidos em uma solução DIY
bluescrn
Não há realmente nada de novo no tessellator do OpenGL. Imagino que qualquer técnico avançado possa fazer coisas semelhantes. Além disso, o DirectX11 possui mosaico de hardware, não sei se ele possui os recursos avançados necessários para o CSG, mas vale a pena dar uma olhada.
Deft_code