Ich bastel gerade an einer Kugel auf Basis eines Isokaeders, Rollenspielern auch bekannt als W20.
(Siehe auch hier: http://mathworld.wolfram.com/Icosahedron.html)

Der Vorteil des ganzen gegenüber Kugeln die über Cosinus und Sinus gebildet werden, ist das die Dreiecke alle gleich groß sind, gleichseitig und über die gesammte Kugelfläche gleichmäßig verteilt.
Die einzelnen Dreiecke zu berechnen ist auch kein Problem (Durch Rekursion werden die 20 Seiten des Isokaeders beliebig fein tesseliert)
Aber leider müssen die Mesh-Daten nachher in Form eines Vertexbuffers und eines Indexbuffers vorliegen (Ich arbeite mit D3D) d.h. es darf keine zwei gleichen Vertices geben.

Kennt jemand eine schnelle Methode, wie ich meinen Haufen Dreiecke in einen Indexbuffer und einen Vertexbuffer zerlege? Im Moment guck ich für jedes Vertex eines Dreiecks einzeln, ob es bereits im Vertexbuffer liegt. Wenn nicht hänge ich's hinten dran ansonsten verwende ich den Index an die Stelle wo es bereits vorhanden ist um das Dreieck im Indexbuffer anzugeben. Das ist aber bei fein aufgelösten Kugeln viel zu rechenaufwendig.

Für Ideen, Vorschläge oder Algorithmen wäre ich sehr, sehr dankbar!

Grüße,
Lith

_________________
Selber Denken macht klug!

Eventuell kannst du beim Unterteilen der Dreiecke den Index und Vertex Buffer direkt füllen. Wenn dann ein Dreieck unterteilt wird, könnte man anstelle der bestehenden Punkte direkt die Indizes nehmen und keinen Punkt doppelt entstehen lassen. Ich habe jetzt diesen Algorihtmus noch nicht implementiert, aber wenn man z.B. ein Dreieck in 4 kleinere unterteilt, dann gibt es ja insgesammt nur drei neue Punkte, die man direkt an den Vertex Buffer anhängt und für den Rest nimmt man die bestehenden Indizes.

Das ist der Hauptgrund, warum meine "sphärischen Landschaften" so lange für den ersten Start brauchen .
(Die generierten Dreiecke sind übrigens nicht wirklich gleichseitig (bei zunehmender Rekursionstiefe, merkt man den zugrundeliegenden Körper))
Das Problem ist, die bereits bestehenden Indizes aus dem Vertexsalat erst mal zu finden, außerdem kann eine neue Rekursion eines Dreiecks auch gar keine neuen Schnittpunkte erzeugen - wenn nämlich bereits unterteilte Dreiecke benachbart sind.
Nachdem ich zu faul war, mir einen Algorithmus zu überlegen, der eindeutige Schnittpunkte erzeugt (ist aber sicher möglich, die Dreiecke werden ja systematisch erzeugt), durchsuche ich für einen potentiellen neuen Schnittpunkt nur diejenigen bereits berechneten Dreiecke des zugrundeliegenden Ikosaeders nach Schnittpunkten, von denen ich weiß, dass sie am aktuellen Dreieck angrenzen (dazu musst du nur die Indizes der Kantenschnittpunkte vergleichen). Da die entsprechende Geosphere dann gespeichert wird, kann sie in Zukunft auch anderweitig verwendet werden (die Klasse macht das automatisch), außerdem können sich dann viele Geosphereobjekte die selben Daten (z.B. den Dreiecksbaum) teilen.
Für sehr komplexe Kugeln ist das auch nicht wirklich schnell, bringt aber immerhin eine ca 5 fache Geschwindigkeitssteigerung, da maximal vier (von 20) Wurzeldreiecken durchsucht werden müssen.

P.S. gibt es irgendeinen besonderen Grund, dass du D3D verwendest ?

_________________
Viel Spaß beim Programmieren,
Mars
http://www.basegraph.com/

Für den Schnittpunktvergleich kannst du übrigens Integer Mathematik verwenden, da die Schnittpunkte aus den selben Grunddaten kommen, müssen gleiche Werte (trotz Fließkomma) bitgenau übereinstimmen - bringt nochmals einen ordentlichen Geschwindigkeitsschub.

_________________
Viel Spaß beim Programmieren,
Mars
http://www.basegraph.com/

Stimmt schon, aber das Problem ist ja, dass die neuen Vertices auf den Kanten des zu teilenden Dreiecks liegen. Deshalb wird jeder dieser Vertices jeweils noch von 3 anderen Dreiecken mit benutzt. Bei einem rekursiven Aufbau des Algorithmus hat man auf die anderen Instanzen der Unterteilungs-Methode aber keinen Zugriff, weiß also nicht, ob das Dreieck schon berechnet worden ist oder nicht, geschweige denn an welchem Index der jeweilige Vertex dann liegen würde und muss trotzdem wieder suchen!

@Mars: Du schreibst also die generierten Daten ersteinmal in einen Baum? Und aus diesem Baum erstellst du dann den Mesh?
Wie ist der Baum aufgebaut? Werden da an jedes Dreieck die 4 Dreiecke der nächsten Rekursionsstufe gehängt?

Meine bisher einzige Idee war beim schreiben eines neuen Vertices in dem Baum 2 Knoten (Tesselationsstufen) nach oben zu wandern und alle ab diesem Knoten bereits erstellten Veritices mit dem neuen zu vergleichen um ein mehrfaches setzen zu vermeiden.
Der große Nachteil der ganzen Sache ist, dass ich so einen Baum brauche, denn der ist bisher eigentlich nicht vorgesehen. Vorallem würde er auch ganz schön speicheraufwendig sein, da ich ja nicht nur die Daten der letzten Tesselationsstufe brauch sondern auch alle vorangegangenen plus den Links.

Wie auch immer, das mit der Integermathematik ist ein guter Tipp! Das werd ich auf jeden Fall mal austesten! Ansonsten hat sich noch eine abwärtszählende Schleife (downto) bewährt, denn meistens liegen die gleichen Vertices nur wenige hundert Indices vom aktuellen entfernt.

@D3D: Ja, hat nen Grund. Das ist Teil einer Arbeit für's Computer-Grafiklabor. Wahrscheinlich hätte ich auch mit Delphi u. OpenGL arbeiten könne, aber man will ja auch mal was neues ausprobieren. Und sowohl Visual Studio als auch C# sind wirklich sehr nett! Trotzdem: Privat bleib ich natürlich bei Delphi u. OpenGL. Nur leided alles private gerade an chronischem Zeitmangel!

Grüße,
Lith

_________________
Selber Denken macht klug!

tsk tsk tsk - was ist denn mit CsGL hmm? hmm?

Stimmt schon, der Baum ist aufwendig - man kann ihn dann aber auch gut für Kollisionserkennung verwenden (ich nehme mal an, du willst die Schnittpunkte der Kugel auch irgendwie variieren).
Allerdings kann man die Baumelemente platzsparend unterbringen (insbesondere unter C#, wo es echte Zeiger an sich ja nicht gibt).

pro Element:
drei Integer, Indices in die Schnittpunkttabelle für das aktuelle Dreieck
vier Integer, Indices in die Baumelementtabelle für Nodes des Dreiecks

Du brauchst für den ganzen Baum Anzahl Dreiecke + 33% Nodes (1 + 1/4 + 1/16 + 1/64 + ...). Bei 28 Byte pro Node durchaus verkraftbar.

Da fällt mir noch ein: die Kugel hat hat ja wahrscheinlich den Ursprung in (0,0,0) - damit kannst du sehr leicht die Schnittpunkte in 8 Oktantentabellen unterbringen (je nach Vorzeichen der Komponenten) und deine Suche des weiteren stark einschränken. Du könntest die Kugel bezüglich einer Achse auch in n Slides aufteilen (jedes in einer eigenen Tabelle, z.B. in Zehntelschritten entlang der x-Achse), womit du die Anzahl der Schnittpunkte, in denen du einen neu anzulegenden Vertex suchen musst, fast beliebig reduzieren kannst.

_________________
Viel Spaß beim Programmieren,
Mars
http://www.basegraph.com/

das kann ich nur bestätigen... aber nach einer längeren Coding-"Session" damit sehne ich mich schon wieder zu Delphi zurück
während dem Kompiliervorgang habe ich immer ca. 10sekunden ZEit mich aufzuregen, dass das ganze so lange dauert

_________________
. . .

Vergiss die Oktanten und nimm die Slides: nachdem mein Algorithmus auch nicht besonder schnell war, schaut meine Vektorsuchroutine nun folgendermaßen aus:


Womit ich es schaffe in wenigen Sekunden auch Geospheres von ziemlich hoher Ordnung zu erstellen, und kann mir (zumindest für die Kugeln) das Herumgewurschtel mit Dateien sparen.

gsVNum und gsVIndex werden folgendermaßen initialisiert:


gsVNum ist ein Zeiger auf eine Integertabelle (enthält die Anzahl der Vertices in einer Scheibe)

gsVIndex ist ein Zeiger auf eine Tabelle von Integertabellen (enthält die Indizes der Schnittpunkte einer Scheibe in die Schnittpunkttabelle).
Das Schöne dabei ist: das funktioniert gut mit allen Körpern, bei denen die Schnittpunkte zumindest entlang einer Achse halbwegs gleichmäßig verteilt sind.

_________________
Viel Spaß beim Programmieren,
Mars
http://www.basegraph.com/