2D Ebene-Ebene Schneidung mit Lua

  • Schneidung von 2D Ebenen in Lua

    In diesem Tutorial möchte ich euch beibringen, wie man 2D Ebenen mit Software schneidet und dadurch simple convexe 2D Formen (Rechtecke, Dreiecke) zeichnen kann. Ihr müsst Code ja nur lesen können da die Implementierung ein Geschenk von mir ist.

    Und nun zur Motivation. Seit ich Spiele auf dem PC spiele hat mich schon immer die Lineare Algebra fasziniert. In der Schule hat man noch das Schneiden von unendlichen Ebenen auf Papier gelernt (lasst euch bitte nicht von Mathe abschrecken!). Streng genommen hat man da nur geprüft, ob zwei Ebenen windschief sind, was equivalent dazu ist, dass die die 2 Ebenenvektorenpärchen zueinander linear abhängig sind. Doch das sollte nur der Anfang sein.

    Sicherlich kennt ihr die GPUs, die im Allgemeinen schnelle, parallele Löser von linearen Gleichungssystemen sind. Und wie genau das funktioniert, das möchte ich euch beibringen!

    Quellcode: https://github.com/quiret/lua_math

    Anleitung
    Ladet euch den Quellcode von GitHub runter und stellt ihn als Resource in den MTA Server rein. Startet dann den MTA Server (oder macht halt nen refresh) mit der "lua_math" resource (kann auch anders heißen). Nachdem ihr euch mit dem Client zum Server verbunden habt, könnt ihr den Befehl "send_bbuf" benutzen um euch ein durch den Server generiertes Bild zu senden, auf dem 2D Formen durch Mathematik allein durch Lua gezeichnet wurden (Bild oben).

    Idee: Spiele zum Beispiel mit den Ebenenmethoden wie "addSupremumPolynomeU" oder "addInfimumPolynomeV" herum, um andere Ebenenformen zu erzeugen.

    Ausrechnung von Ebene-Ebene Schneidung auf Blatt Papier
    Alles was da im Quellcode steht ist einfach auf Blatt Papier ausrechenbar. Benötigte Fähigkeiten sind: Umstellung von linearen Gleichungssystemen nach Variablen, Verständnis von Ungleichungen und deren Folgerungen, Wissen wie man richtig Zahlen sortiert und Intervalle. Und wenn man nicht so viele Fehler macht (wie ich, lol) dann geht es richtig flott.

    Es ist empfohlen, dass du mit Hochschulmathematik vertraut bist oder das Lernen willst. Bitte versuche auch mitzurechnen.

    Wir definieren eine Ebene als ein Positionsvektor (p1x, p1y) mit Richtungsvektoren (u1x, u1y) und (v1x, v1y) Spaltenvektoren die eine Fläche aufspannen. Dementsprechend ist (p2x, p2y) der Positionsvektor der zweiten Ebene und (u2x, u2y), (v2x, v2y) deren Aufspannvektoren.

    Externer Inhalt i.imgur.com
    Inhalte von externen Seiten werden ohne Ihre Zustimmung nicht automatisch geladen und angezeigt.

    Weiter setzen wir vorraus, dass alle Variablen u2, v2, u1, v1 im Intervall zwischen 0 und 1 liegen (einschließlich).

    Um euch nicht am Anfang zu überfordern möchte ich dieses Problem an einem Beispiel vorstellen. Ihr werdet im Nachhinein merken, dass da nicht alzu viel mehr ist.

    Das oben gezeigte Gleichungssystem stellen wir nach u1 und v1 um, sodass wir folgende Gleichungen erhalten.

    Erinnere dich nun, dass wir gefordert haben, dass u1 und v1 zwischen 0 und 1 liegen (einschließlich). Wir setzen also die Lösungen von u1 und v1 in die Ungleichungen ein und erhalten somit Ungleichungen, die nur noch auf den u2 und v2 Variablen basieren.


    Da wir ja nur an Ungleichungen von u2 und v2 interessiert sind, haben wir sie gezielt umgeformt. Jetzt kommt ein Punkt, an dem mit der höheren Hochschulmathematik vielleicht höchste Konzentration erforderlich ist. Die Ungleichungen in u2 und v2 sind zwar Schranken, jedoch nicht unbedingt eng an unserer eingeschlossenen Fläche gebunden.

    Was wir also suchen sind Intervalle für u2, in denen die Ungleichungen in v2 tatsächlich eng an unsere Fläche grenzen. Das gleiche suchen wir natürlich für v2 und Ungleichungen in u2 (Polynome). Wir fassen also zur Verdeutlichung alle Unter- und Oberpolynome in u2 in eine gemeinsame Ungleichung von v2 zusammen.

    Die Minimumsfunktion gibt für jeden Wert von u2 das Polynom und somit dessen Wert aus, das am kleinsten ist (zur Bestimmung des Supremumpolynoms). Also gibt es ja (eventuell) eine Menge von Werten, für die jedes Polynom das Kleinste sein kann! Es funktioniert genauso analog für die Maximumsfunktion.

    Wir schreiben diesen Gedanken gründlich auf Blatt Papier auf und Lösen das Problem.


    Falls man die Ebene auf Blatt Papier zeichnet sollte man feststellen, das diese Werte tatsächlich die sind, bei denen sich die Schranken der Ebenen abwechseln. Ansonsten hat man ja falsch gerechnet.

    Sicherlich hast du gemerkt, dass wir zwischen Unter- und Oberpolynomen streng unterscheiden. Dies ist so, weil die Unterpolynome die kleinstmöglichen Werte von u2 bzw v2 in einem Wert von v2 bzw u2 darstellen. Somit befinden sich alle gültigen Werte zwischen dem Ober- und Unterpolynom.

    Das ist wichtig, weil wir noch gar nicht berechnet haben, für welche Werte das Unterpolynom tatsächlich kleiner-gleich dem Oberpolynom ist! Wir nehmen also alle Intervalle, in denen ein Unterpolynom in u2 das Größte und ein Oberpolynom in u2 das Kleinste ist und schrenken das Gültigkeitsintervall von u2 weiter ein durch direktes Gegenüberstellen.


    (Sichtlich ein sehr einfaches Beispiel, wo keine Rechnung nötig ist; für etwas komplizierteres weiter unten schauen)

    Zu guter Letzt erhalten wir ein eindeutiges Ergebnis: Intervalle von u2/v2, in denen ein Unter- und ein Oberpolynom die Werte von v2/u2 einschränken. Falls keine solche Intervalle existieren so schneiden sich die Ebenen nunmal nicht.

    Beispielrechnungen als Bilder:
    - Beispiel mit eingeschlossener Ebene
    - Beispiel mit Ebenen die sich kreuzen

    Ideen:
    - schreibe eine Implementierung der 2D Ebenen Schneidung in C++
    - erweitere das Zeichnen von 2D Ebenen, indem du mit den U/V Koordinaten eine Texture ausliest und somit gefärbte Formen erstellst
    - lese DFFs mit einem Luascript ein und erzeuge mit einer gezielten inversen 3D Transformation 2D Formen, die du ohne Tiefeneinwirkung auf dem Bildschirm zeichnen kannst

    Anwendungen und Ausblick
    Als Beispiel habe ich euch das Zeichnen von Formen mit Software herangebracht. In Spielen ist es auch möglich, zu prüfen, ob ein Charakter, der durch Dreiecke approximiert wird, auf ein bestimmtes Feld ohne Kollision (und ohne Bewegung) platziert werden kann, wie beispielsweise das Platzieren von Gebäuden bei Command and Conquer.

    Ich plane noch mehr über Lua und Mathematik in diesen Thread zu posten. Schließlich ist die Programmierung ein gutes Werkzeug, um deine Vorstellungskraft auszudrücken, in gezielter Modellierung. Also könnt ihr mich in Zukunft durch meine Forschung begleiten und was dabei lernen ^^

    Mit freundlichen Grüßen,
    - Martin a.k.a. The_GTA

    Developer of Magic.TXD

    2 Mal editiert, zuletzt von The_GTA (26. Juni 2018 um 01:04) aus folgendem Grund: Beispiel hinzugefügt: Ebenen die sich kreuzen Beispiel hinzugefügt: Ebenen die inneinander sind

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!