2D CSG implementieren (für Kollisionsformen)?

7

Gibt es einfache (oder gut dokumentierte) Algorithmen für grundlegende CSG-Operationen an 2D-Polygonen?

Ich suche nach einer Möglichkeit, eine Reihe überlappender 2D-Kollisionsformen hinzuzufügen. Diese können konvex oder konkav sein, sind jedoch geschlossene Formen, definiert als eine Reihe von Liniensegmenten ohne Selbstschnittpunkte.

Die Verwendung davon wäre, einen sauberen Satz von Kollisionskanten zur Verwendung mit einer 2D-Physik-Engine aus einer Szene zu konstruieren, die aus vielen willkürlich platzierten (und häufig überlappenden) Objekten besteht, von denen jedes seine eigene Kollisionsform hat.

Zunächst muss ich nur Formen hinzufügen, aber die Fähigkeit zum Subtrahieren und Erstellen von Löchern kann auch nützlich sein.

Bluescrn
quelle
Fügen Sie selbst eine Antwort hinzu, da ich diese verwendet habe: sourceforge.net/projects/polyclipping - anstatt eine Implementierung von Grund auf neu zu versuchen. Bisher macht es den Job ganz gut und es war sehr einfach zu bedienen (mit C #) Wikipedia hat Links zu einer ganzen Reihe von Informationen zu diesem Thema, als ich anfing, mit der richtigen Terminologie zu suchen: en.wikipedia.org/wiki/ Boolean_operations_on_polygons
Bluescrn
Hier ist eine fantastische Javascript-Implementierung von 3D CSG. Dies ist sicherlich übertrieben für Ihr Problem, aber der Code ist klein, sauber und gut dokumentiert, sodass Sie viel lernen können, indem Sie ihn studieren.
DaleyPaley

Antworten:

3

Ist das für Level Designer oder für den Motor?

Für den Level-Designer benötigen Sie diesen Code, um z. B. statische Objekte zu kombinieren. Erforschen Sie vektorgrafische APIs für die Lösung. Die Aufgabe klingt für SVG, PostScript, WMF usw. ziemlich häufig. Versuchen Sie zuerst, die CombineRgn Win32-API zu verwenden :-)

Für die Spiel-Engine - ich würde vorschlagen, dass Sie nicht tun, was Sie wollen. Sie werden enorm viel CPU aufwenden, um Ihre Objekte miteinander zu kombinieren. Sie werden eine enorme Anzahl von Verzweigungsfehlvorhersagen damit verbringen, die Randbedingungen zu überprüfen, zu testen, ob sich 2 Segmente schneiden oder nicht usw. Dieser Vorgang muss in jedem Frame für den sichtbaren Teil Ihrer Karte wiederholt werden.

Führen Sie einfach Bounding-Box-Checks durch und kollidieren Sie dann mit einzelnen Objekten. Wenn Ihre Objektformen zu komplex sind, vereinfachen Sie sie beim Exportieren von Daten in die Engine und verwenden Sie verschiedene Formen für Kollisionen und Zeichnungen.

Update : Siehe meinen C # GDI + Code, der macht, was Sie wollen. Sie können dasselbe problemlos in C ++ schreiben: Die GraphicsPath-Klasse ist lediglich ein Thin Wrapper über die entsprechenden Funktionen von 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 );
        }
    }
}
Bald
quelle
2

Ich habe einen kleinen Proof of Concept geschrieben, der CSG verwendet hat, um das Spiel im Stil von Scorched Earth / Worms zu verbessern. Ich habe es mit gluTessellate implementiert . Ich habe dann die tessellierten Dreiecke auf Box2D-Polygone abgebildet. Ich konnte sowohl Schmutz zur Simulation hinzufügen und daraus entfernen als auch Löcher bohren und füllen.

Das größte Problem bei der Verwendung von gluTessallate ist, dass es kein Problem gibt, entartete Dreiecke zurückzugeben. Ich musste diese herausfiltern, bevor ich die tessellierten Dreiecke in die Physik-Engine verschob.

Eines der schönen Dinge an gluTessallate ist, dass es möglich ist, die Nachbarschaft aus den Rückrufinformationen zu bestimmen. Ich bin nie weiter gegangen, aber theoretisch könnte man die Nachbarschaft und den SCC verwenden , um Inselbildung genau zu erkennen.

deft_code
quelle
Interessant, ich muss das nachlesen. Ich versuche jedoch, mich von Dreiecksnetzen fernzuhalten - und mich nur mit Umrisskanten zu befassen (wie bei Kollisionszwecken können alle inneren / geschlossenen Kanten, die an einem Scheitelpunkt des Umrisses angebracht sind, unerwünschte Kollisionen verursachen). Aber vielleicht ist ein Dreiecksnetz als Zwischenschritt vor dem Herausfiltern der Innenkanten ein möglicher Ansatz?
Bluescrn
1
gluTessellate hat auch einen Nur-Umriss-Modus GLU_TESS_BOUNDRY_ONLY. Der von mir bereitgestellte Link enthält einen kurzen Abschnitt speziell zu CSG.
Deft_code
Wow, das sieht überraschend mächtig aus, ich hatte nie bemerkt, dass glu diese Funktionalität enthält. Es sieht so aus, als wäre es eine Option (obwohl mein Tool D3D-basiert ist), aber ich bin immer noch ziemlich neugierig auf die Algorithmen, die in einer DIY-Lösung enthalten sein würden
Bluescrn
In OpenGLs Tessellator gibt es eigentlich nichts Neues. Ich kann mir vorstellen, dass jeder fortgeschrittene Tessellator ähnliche Dinge tun kann. Auch DirectX11 bietet Hardware-Tessellation. Ich weiß nicht, ob es die erweiterten Funktionen für CSG bietet, aber es wäre einen Blick wert.
Deft_code