Hi, Ich hab ein geometrisches Problem.

Ich möchte gerne Geospheren implementieren, also sie via VBO zeichnen lassen. Durch einige Recherche hab ich herraus gefunden, dass man eine Geosphere erhält, in dem man die Flächen eines Tetraeder zerteilt und die dadurch resultierenden Vertieces auf den Abstand der anderen Vertieces normiert. Diesen Schritt des Zerteilens kann man immerwieder durchführen, die Kugel wird dadurch runder.

Nun ist meine Frage, hat jemand einen gescheiten Algorithmus, mit dem man sowas berechnen kann? Immerhin brauch ich ja nicht nur alle Eckpunkte, sondern auch alle Adjazenzen, also Indizes der Vertices aus denen die Flächen bestehen um Sie rendern zu können. Die Ausgangskoordinaten für den Tetraeder sind nicht so schwer zu finden. Aber wenn es dann um die Zerteilung geht, weiß ich nicht mehr weiter und Google scheinbar auch nicht.
Vielleicht kennt ja jemand von euch Milkshape. Dort kann man Geospheren als Primitive erzeugen in dem man die Anzahl der Tetraederteilungen angibt. Interessant ist allerdings, dass dort die Teilung erst ab einem Ikosaeder beginnt. Wobei der Ikosaeder durch die erste Teilung des Tetraeders entstehen würde.
Ich hatte mir überlegt eine Baumstruktur zu bauen, in der ich mit 4 Dreiecksflächen beginne, die sich die 4 Eckpunkte des Tetraeders teilen und einfach eine Funktion implementiere mit der ich dann anschließend ein Dreieck in 4 weiter unterteile. So wie es beim Sirpinski-Dreieck der Falls ist. Diese Dreiecke würden dann wieder so zerteilt werden können. Aber wie vermeide ich da redundante Daten? Also doppelt auftretende Vertizes ? Angrenzende Dreiecke würden sich ja die Vertizes teilen können.
Die Berechnung der Anzahlen für Flächen, Vertizes und Kanten ist kein Problem. Das bekomme ich anhand der Teilungstiefe schon hin. Auch die Formel für den nötigen Radius um eine ideale Kugel in der Geosphere einzuschließen ist bereits geschafft. Nur der Rest tut mir etwas zu schaffen.

Achja, Warum das ganze? Ich brauche Kugeln um im deffered Rendering meine Lichtvolumen einzuschränken und möchte dabei normale Spheren (Breiten- und Längengradunterteilung) und Geospheren von der performance vergleichen. Beide Geometrien müssten nur einmal als VBO erzeugt werden, die Geosphere wäre aber durchaus Runder und würde somit weniger Fragmente abdecken, bei weniger Vertizes und Flächen.

Ich hoffe, das mir da jemand etwas empfehlen kann. PDFs oder Weblinks zu solchen Teilungsproblemen sind auch herzlich willkommen. Ich war beim Suchen bisher nicht erfolgreich.

gruß, Sellmann.

_________________
Klar Soweit?

Warum erzeugst du die Sphere nicht mit Milkshape und lädst sie als Mesh? Wenn nötigst kannst du dir auch leicht verschiedene Auflösungen produzieren.

Tipp: Die Kugel einfach ein Stücken größer machen als eigentlich nötig. Du musst im Shader ja sowieso die Entfernung checken, und kannst Pixel außerhalb des Lichtradius dunkel machen bzw. discard benutzen. So kann die Kugel eine geringere Auflösung haben.

_________________
Yeah!

Das wäre natürlich der schnellste weg (nen Loader dafür hab ich ja bereits geschrieben), allerdings bin ich Minimalist, was externe Rescourcen angeht und einfach scharf drauf das Problem dahinter zu lösen.

Die Idee ist, dass ich den Lightbuffer schwarz initialisiere. Zeichne ich die Geometrie, dann werden ja nur die Fragmente neuberechnet, die von der Kugel auch eingeschlossen werden. So bleibt alles außerhalb der Kugel automatisch unbeleuchtet. Die Kugel soll so groß sein, dass der Flächenmittelpunkt aller Dreiecke genau 1 vom Ursprung entfernt ist (deshalb müssen die Vertices immer etwas weiter als 1 vom kugelmittelpunkt weg sein, sonst wäre das Lichtvolumen abgeschnitten), so kann ich mittels Skalierung der Kugel den Lichtradius festlegen und durch eine einfache Translation um die Lichtposition die Kugel an den Ursprung der Lichtquelle bringen (eine vollständie Ausrichtung mittels 4x4Matrix ist ja nicht notwendig, da die Kugel aus jeder Richtung ideal Rund ist). Ich erhoffe mir darauß, dass ich möglichst wenige Fragmente mit meiner Lichtberechnung belästige und gleichzeitig Geometrie einspare.
Für mich klingt das plausibel, da ich ein evtl. hundertfach genutztes Objekt durch eine einmalige Berechnung performanter mache.

Ich denke aber, dass ich einen Ansatz gefunden habe:
Im Groben halte ich mir eine Liste von Dreiecken, die spaltbar sind. Sie definieren sich aus Kanten, die ebenfalls spaltbar sind. Die Kanten werden aber nur referenziert und liegen in einer seperaten Liste, genauso wie die Vertices, aus denen die Kanten bestehen.
Ist eine Kante bereits gespalten, wird sie nicht nochmal gespalten im jeweiligen Durchgang. Jede Kante kennt seine SubKanten und jedes Dreieck seine SubDreiecke, sofern sie schon erzeugt wurden. Wird ein Dreieck gespalten, spaltet es seine Kanten und verbindet aus den neuen SubKanten seine neuen SubDreiecke. Am Ende brauch ich nur die tiefste Schicht von Dreiecken auffordern mir ihre Vertexindizes als Array auszugeben, die ich durch die Vertexliste kenne. So sollte das ungefähr klappen.

_________________
Klar Soweit?

Das hat mir Coolcat in einem anderen Thread empfohlen, vielleicht hilft es dir: The Half Edge Data Structure.

greetings

_________________
If you find any deadlinks, please send me a notification – Wenn du tote Links findest, sende mir eine Benachrichtigung.
current projects: ManiacLab; aioxmpp
zombofant network • my photostream
„Writing code is like writing poetry“ - source unknown

„Give a man a fish, and you feed him for a day. Teach a man to fish and you feed him for a lifetime. “ ~ A Chinese Proverb

Etwas OffTopic:
Könntest du das nachher auch noch mit einer BoundingBox vergleichen? Würde mich mal interessieren wie sich der Mehraufwand durch die größere Menge an Vertices bei der Kugel gegenüber dem Mehraufwand an Fragmenten bei der BoundingBox verhält. Wenn ich es richtig überschlagen habe benötigt die Box ca. 30 % mehr Fragmente.

_________________
Es werde Licht.
glEnable(GL_LIGHTING);
Und es ward Licht.

Zitat aus einem Java Buch: "C makes it easy to shoot yourself in the foot; C++ makes it harder, but when you do it blows your whole leg off"

on error goto next