Doppelte Dreiecke in einem Array finden.... ?

[dizzy]

Zitat von turboPASCAL:

Die Normalen sin uninteressant da es (noch) keine gibt.

Jain, OpenGL z.B. erzeugt, wenn nicht anders angegeben, implizit Normalen senkrecht zu der Ebene die das Dreieck beschreibt. Wie sie orientiert ist, ist von der Reihenfolge der Punkte abhängig. Ich glaub es ist so, dass wenn du das Dreieck plan vor dir siehst, und die Punkte gegen den Uhrzeigersinn beschrieben sind, zeigt die Normale auf dich.
Das ist in sofern interessant, als dass in vielen Realtimeanwendungen Backfaceculling betrieben wird, also Dreiecke, deren Normalen nach "hinten" in den Bildschirk rein zeigen, werden nicht gezeichnet, da sie bei geschlossenen Objekten eh immer verdeckt wären.
Vertauscht du die Reihenfolgen nun bei manchen, tauchen u.U. Löcher in der Darstellung auf. Es gilt zudem als guter Stil für alle Faces die gleiche "Vertex-Order" zugrunde zu legen.

Zitat von turboPASCAL:

Zitat:

Du könntest beim Einlesen die Vertices so drehen, dass immer der z.B. betragsmäßig kleinste Vektor im 0-ten Element steht.

Dann müsste ich ja dort diese Vectoren vergleichen. Also getippe 3 * 3 if abfragen... ?!

Nein, du würdest drei mal einen Vektorbetrag errechnen, dann 1 bis 2 mal die Arrayelemente verschieben, und müsstest zum einsortieren nur noch einen Vergleich (0-tes Element) durchführen.
Bei binärer Suche kommt hinzu, dass du extrem weniger Vergleiche zum einsortieren brauchst, und du hast anschließend schön alle Dreiecke hintereinander stehen, bei denen der kürzeste Vektor (vom Urprung gesehen) gleich ist. Damit musst du nur noch diese kleine Gruppe untereinander elementweise vergleichen um doppelte auszumachen.
Bei dem jetzigen Vorgehen prüfst du jedes Dreieck gegen jedes andere. Der Aufwand ist O(n²), bestenfalls, wenn man es geschickt löst, O((n*(n+1))/2).
Das binäre einsortieren hat eine worst-case Laufzeit von O(log(n)), und die gruppenweise Vergleiche wieder O(n²) bzw. O((n*(n+1))/2), jedoch mit einem weiiiiiit aus kleinen n!

Es gibt hierbei noch 2 Spielarten:
1) Direkt beim Einsortieren in die Liste Nachbarn mit gleichem 0-ten Element auf Gleichheit prüfen, und bei Fund den Eintrag erst garnicht machen, oder
2) Erst die Liste komplett aufbauen, und dann die Vergleiche machen.

Ersteres ist natürlich nochmal etwas schneller, da man die Liste von vorne herein möglichst klein hält, was dem Suchen beim Einsortieren zugute kommt, sowie ein zweites Durchgehen der gesamten Liste vermeidet.
Die einzige Optimierung, die mir dann noch einfiele, wäre statt binärer Suche zum Eintragen die Interpolationssuche. Aber das ist dann wirklich nur noch Finetunig. Die anderen Dinge jedoch sind echte Booster!


Zum Thema Strings: Wenn ich doch schon wunderbare Zahlenwerte habe, warum diese dann als Strings behandeln!? Zusammen mit den Konvertierungen und aufwendigen Vergleichen dürfte die Laufzeit damit unheimlich steigen, und so wirklich Speicherfreundlich ist das auch nicht! Zumal wir hier von einem 3D-Modell reden, welche gerne mal mehrere Tausend Faces haben, evtl. Millionen. DA mit Strings dranzugehen ist, nett ausgedrückt, unglaublich ungeeignet


Gruss,
Fabian