Prozedurale Geometrieerzeugung

10

Ich habe mich kürzlich mit SceneKit für OS X befasst und festgestellt, dass es verschiedene Factory-Methoden zum Erstellen geometrischer Formen gibt, z.

Box, Kapsel, Kegel, Zylinder, Flugzeug, Pyramide, Kugel, Torus und Rohr.

Ich bin daran interessiert, meinem Renderer solche primitiven Formen hinzuzufügen, habe aber Schwierigkeiten, eine vernünftige Quelle zu finden, aus der ich ein Verständnis für die prozedurale Generierung gewinnen kann. Es gibt mehrere Ressourcen, die die Theorie detailliert beschreiben, aber nicht über den entsprechenden Quellcode verfügen, um sie zu sichern.

SceneKit bietet Factory-Methoden, mit denen die Attribute solcher Formen dynamisch festgelegt werden können. Im Fall der Box können Sie ganzzahlige Werte für die Anzahl der Segmente für Breite, Höhe und Tiefe angeben, in die jede Fläche unterteilt werden soll.

Ich verstehe die Theorie, aber es fehlt mir das Wissen, um Geometrieflächen zu unterteilen, um den gewünschten Effekt zu erzielen.

Die Eckpunkte für jede Form lassen sich höchstwahrscheinlich recht einfach in einfachen Schleifen erzeugen. Was mich verblüfft, ist zu wissen, wie man die Gesichter erstellt, oder vielmehr die geeigneten Texturkoordinaten für jedes Gesicht. Normalen können pro Gesicht berechnet werden, daher bin ich ziemlich sicher, dass ich das erreichen kann, was ich will. Ich weiß nur, wo ich anfangen soll.

Kann jemand Details zur Verfahrensgeometrie angeben? Was ich wirklich brauche, ist ein Quellcode, aus dem ich Informationen abrufen kann. Ich habe hoch und niedrig nach Tutorials gesucht, aber bisher nur wenige vernünftige Websites oder Blogs gefunden. Gute Bücher, Tutorials, Blogs oder Forschungsarbeiten sind willkommen.

Bearbeiten Sie basierend auf Kommentaren

Ich hätte klarstellen müssen, dass ich weiß, wie man Scheitelpunkte für Grundformen erstellt. Die meisten davon können wahrscheinlich durch einfache Schleifen erreicht werden. Was ich nicht verstehe, ist, wie man Gesichter aus dem generierten Array von Eckpunkten erstellt. Wie erstelle ich einen Dreiecksstreifen oder Dreiecke aus einer scheinbar ungeordneten Anordnung von Scheitelpunkten?

Ich gehe davon aus, dass ich, sobald ich diesen Punkt überwunden habe, die Normalen aus jedem Gesicht erstellen kann. Obwohl ich mich noch nicht damit befasst habe, habe ich viele Hinweise darauf gesehen und bin mir sicher, dass die Implementierung einfach genug sein wird.

Idealerweise möchte ich in der Lage sein, Geometrie aus einem bestimmten Satz von Eigenschaften zu generieren, beispielsweise aus der Art und Weise, wie SceneKit sie bereitstellt. Angesichts der Tatsache, dass SceneKit dies getan hat und Sie ähnliche Dinge in Blender und Maya usw. tun können, gehe ich davon aus, dass ich nicht versuche, das Unmögliche zu implementieren.

Der letzte Aspekt wäre das Anwenden von Texturen. Auch dies habe ich nicht implementiert, habe mich aber über die Anforderungen informiert und bin mir dessen bewusst.

Das Hauptproblem hierbei ist, dass ich weiß, was ich erreichen möchte, aber Schwierigkeiten habe, die Implementierung für die oben genannten Grundelemente zu entschlüsseln. Ich hatte die Hoffnung, dass ich über den Quellcode einen Anschein von Wissen finden könnte, aber ich habe bisher wirklich nichts Passendes gefunden.

Captain Redmuff
quelle
Sie sagen, dass Ihr Problem darin besteht, die Geometrie zu unterteilen, aber dann sagen Sie, dass das Erstellen der Scheitelpunkte einfach sein sollte, und dann sagen Sie, dass Ihr Problem darin besteht, Gesichter zu erstellen, und dann sagen Sie, dass Ihr Problem die Texturabbildung ist. Was ist dein Problem? Können Sie die Scheitelpunktpositionen generieren? Können Sie die Kanten und Flächen erzeugen? Außerdem hängen die Texturkoordinaten von Ihrer Textur ab und davon, was Sie damit erreichen möchten. Daher ist die Frage nach den Texturkoordinaten nicht gut. Schließlich geht es bei der Erzeugung von Primitiven einfach um Geometrie, und die Leute nennen sie selten "prozedurale Geometrie", obwohl es so ist.
jrsala
Ich verstehe, wie man die Geometrie für einfache Formen wie einen Würfel oder eine Ebene erstellt. Es ist die Erstellung der Gesichter, die ich nicht verstehe. Wie erstelle ich die Gesichter aus einer Reihe von Eckpunkten? Das Zeichnen der Punkte für komplexere Formen ist Teil des Problems, obwohl ich ein grundlegendes Verständnis habe. Wenn ich sie alle zu einem Dreieck oder Dreiecken zusammenklebe, habe ich Mühe, meinen Kopf herumzuwickeln.
Captain Redmuff
OK, danke für die Details. Möglicherweise möchten Sie Ihre Frage bearbeiten, um dies zu klären. Antwortzeit!
jrsala

Antworten:

11

Die Art und Weise, die Kanten und Flächen einer primitiven Form wie eine Box, einen Kegel und alle von Ihnen genannten zu erzeugen, besteht darin, sie gleichzeitig mit der Erstellung der Scheitelpunkte zu erzeugen. Tatsächlich sollten Sie die Scheitelpunkte auf eine logische Weise erstellen, die es einfach macht, die Kanten und Flächen entsprechend zu berechnen.

Es gibt Algorithmen, die eine Menge von Punkten im Raum als Eingabe verwenden und eine sogenannte " Punktmengen-Triangulation " darüber berechnen , aber das Problem der Punktmengen-Triangulation ist NP-vollständig , so dass es schneller ist, Kanten und Flächen zu erstellen während Sie gehen, als nur die Eckpunkte zu berechnen und einen Algorithmus die Arbeit machen zu lassen. Ich möchte Sie nur wissen lassen, dass es diese Lösung gibt.

Abgesehen von dieser ineffizienten Lösung können Sie die Grundelemente meiner Meinung nach nur pro Fall behandeln, wie in den folgenden Beispielen.

Ein Netz besteht aus Eckpunkten und Flächen . Die Kanten sind in der Beschreibung der Flächen enthalten, es sei denn, Ihr Netz enthält Linien, aus denen keine Flächen bestehen. Die Eckpunkte sind Tupel mit 3 Gleitkommakoordinaten. Die Kanten sind einfach Paare von Verweisen auf die Eckpunkte, aber andererseits werden Sie sie sicherlich nicht brauchen. Angenommen, Ihre Scheitelpunkte befinden sich in einem indizierten Array. Nun, Ihre Kanten könnten dann Paare von Indizes dieses Arrays sein. Die Flächen sind Tripletts von Verweisen auf Scheitelpunkte oder Tripletts von Indizes im Fall eines indizierten Arrays .

Sie sollten in der Lage sein, die Scheitelpunkte, Kanten und Flächen zu zählen, aus denen jede dieser primitiven Formen besteht. Wenn Sie sie zählen können, müssen Sie die Eigenschaften des Objekts verstehen und die Methode entwickeln, mit der Sie sie mithilfe von Schleifen und erstellen andere Tools, wie wir sehen werden.

Kegel

Für einen Kegel mit n + 2 Eckpunkten, 3n Kanten und 2n Flächen:

  1. Machen Sie zwei separate Eckpunkte.
  2. Machen Sie einen Kreis um einen der Scheitelpunkte (den Basisscheitelpunkt), dh innerhalb einer Ebene senkrecht zum Segment zwischen den ersten beiden Scheitelpunkten. Hoffentlich können Sie mit Trigonometrie einen Kreis bilden, oder? Das sind schon alle Eckpunkte des Kegels. Das ist auch ein Drittel aller Kanten (es gibt n Kanten im Kreis und insgesamt 3n ).
  3. Machen Sie n Kanten vom Basisscheitelpunkt zu den n Scheitelpunkten im Kreis. Sie können dabei eine Hälfte der Gesichter (das sind n Gesichter) erstellen.
  4. Machen Sie n Kanten vom Spitzenscheitelpunkt zu den n Scheitelpunkten im Kreis. Sie können dabei die andere Hälfte der Gesichter (das sind n Gesichter) erstellen.

1) Zwei Eckpunkte 2) und ein Kreis
3) und Gesichter
4) und Gesichter
Endergebnis:Ergebnis

Sie können auch die Kanten und Flächen erstellen, während Sie die Schleife ausführen, aus der der Kreis besteht. Gleiche Komplexität, gleiche Sache. Erstellen Sie einen Scheitelpunkt auf dem Kreis, speichern Sie ihn in Ihrem Scheitelpunktarray, fügen Sie die entsprechende Kante (Paar von Indizes) zum Array von Indexpaaren hinzu, wenn Sie Lust dazu haben, und fügen Sie schließlich die entsprechende Fläche zu Ihrem Array von Tripletts von Indizes hinzu . Fahren Sie mit dem nächsten Scheitelpunkt fort.

Der Zylinder und das Rohr: nicht zweimal die gleiche Arbeit machen und Quads

Wiederum beginnt das Rohr mit einem Scheitelpunkt und einem Kreis, die entweder die Mitte der oberen oder der unteren Scheibe des Zylinders bilden:

  1. Machen Sie einen Scheitelpunkt.
  2. Machen Sie einen Kreis um den Scheitelpunkt. Fügen Sie Kanten (wenn Sie Kanten möchten) zwischen den aufeinanderfolgenden Scheitelpunkten des Kreises und zwischen dem mittleren Scheitelpunkt und jedem Kreisscheitelpunkt hinzu. Fügen Sie Flächen zwischen jedem Triplett von Scheitelpunkten aus dem mittleren Scheitelpunkt und zwei aufeinanderfolgenden Scheitelpunkten auf dem Kreis hinzu.
  3. Duplizieren Sie das alles und verschieben Sie die Kopie in der Richtung senkrecht zur Basis, die Sie gerade erstellt haben, um die Länge des gewünschten Zylinders.
  4. Verbinden Sie die Oberseite und die Unterseite.

Um die Ober- und Unterseite zu verbinden, müssen Sie Quads zwischen Paaren von Scheitelpunktpaaren erstellen, die sich gegenüberstehen. Denken Sie also voraus und warum machen Sie sich nicht zu einer Funktion, die aus vier Eckpunkten zwei dreieckige Flächen macht?

Erledigt. Beachten Sie, dass wir diesmal die Tatsache verwenden, dass dieselbe Struktur (Kreis + Mitte) zweimal in einem Zylinder erscheint, um eine Verknüpfung zu erstellen. Wir müssen nicht alle Eckpunkte, Kanten und Flächen von Hand machen, im Gegensatz zu dem Kegel, wo es notwendig war.

Nach diesem Faulheitsprinzip ist es auch möglich, nur ein Viertel des Kreises zu erstellen und zu duplizieren und erneut einen vollständigen Kreis mit sehr einfachen Transformationen zu erstellen (gültig für jeden Kreis, also auch für den Kegel), aber das ist für einen wirklich übertrieben nicht so komplexe Form.

Sie müssen immer die geometrischen Eigenschaften der von Ihnen erstellten Objekte verwenden, um deren Erstellung zu vereinfachen . Ihre Symmetrien und Invarianten .

Machen Sie für einen Zylinder einfach nicht den Basisscheitelpunkt, sondern nur den Kreis, duplizieren Sie, übersetzen Sie die Kopie, erstellen Sie die Quads, fertig.

Die Kugel und die Kapsel: Komplexität hinzufügen, immer noch nicht zweimal dieselbe Arbeit

Um eine Kapsel zu erstellen, möchten wir eine UV-Kugel erstellen, sie in zwei Hälften teilen, die erste Hälfte verschieben und dann die beiden mit den Seiten der Kapseln verbinden.

Wieder ist es möglich, nur ein Achtel (!!) der Kugel zu erstellen, sie dann zu duplizieren und umzukehren und dann das Ergebnis zu duplizieren und umzukehren, außer entlang einer anderen Achse usw., um eine vollständige Kugel in 4 Schritten zu erhalten (erstellen Sie die Achtel) dreimal duplizieren und umkehren). Vielleicht übertrieben, aber weniger als im Fall des Kreises.

Eine einfache UV-Kugel:
Kugel

Wir machen tatsächlich nur eine Hälfte davon (zum Beispiel), duplizieren diese Hälfte, drehen die Kopie um und übersetzen sie um die Länge der Kapsel:
Hälften

Wir verbinden die obere und untere Hälfte:
Kapsel

Die wirkliche (etwas) harte Arbeit kommt von der Trigonometrie, die zur Herstellung einer Kugel beiträgt. Die Menge aller zu einer UV-Kugel gehörenden Eckpunkte kann als die Menge aller Punkte der Form beschrieben werden:

Punkte

Dabei ist R der Radius der Kugel und für eine bestimmte positive gerade ganze Zahl N haben wir die Konstante

θ = × π / N ,

k und n sind ganze Zahlen, wobei k von 0 bis 2N-1 und n von -N / 2 bis + N / 2 variiert .

Um eine Halbkugel oder ein Achtel einer Kugel zu erstellen, müssen Sie die Menge der von k und n angenommenen Werte einschränken .

Wenn k reelle Zahlen und nicht nur ganzzahlige Zahlen wären, würden Sie eine ganze Kugel erhalten, nicht nur die Eckpunkte auf ihrer Oberfläche. Wir haben hier also die Oberflächengleichung des Grundelements gerastert .

Der furchterregende Torus : Nach allem, was wir gesehen haben, ist es einfach!

Wieder mehr Trigonometrie, mehr Eckpunkte, mehr Quads, mehr Symmetrien, mehr Invarianten ... mehr Geometrie! Finden Sie die Gleichung für die Oberfläche eines Torus heraus, "rasteren" Sie sie richtig, vereinfachen Sie das Problem mithilfe der (offensichtlichen) Symmetrien des Torus und durchlaufen Sie schließlich die soeben definierten Scheitelpunkte und erstellen Sie die Kanten und Flächen wie Sie gehen!

Sehen? Ganz einfach.

jrsala
quelle
Beeindruckend. Vielen Dank für eine so detaillierte Antwort und für so viele Beispiele. Ich hatte nicht daran gedacht, einfach eine halbe Kugel zu erzeugen und die symmetrischen Elemente zu spiegeln. Vielen Dank, dass Sie sich die Zeit genommen haben, dies so zu schreiben, dass ich es leicht verstehen und hoffentlich problemlos in die Praxis umsetzen kann.
Captain Redmuff
Bitte! Es tut mir leid, dass es keinen Code gab.
jrsala
Der Umriss der Methoden war mehr von dem, was ich wirklich brauchte. Von dort aus kann ich zumindest einen Aktionsplan ausarbeiten:] Ich nehme an, Sie haben keine Informationen zu Boxen / Würfeln mit abgeschrägten Kanten? docs.autodesk.com/3DSMAX/15/ENU/3ds-Max-Help/images/…
CaptainRedmuff