Vertices mergen und Reorganisation der Abhängigkeiten

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
Walker
Beiträge: 42
Registriert: 28.07.2017, 08:58
Alter Benutzername: Walker

Vertices mergen und Reorganisation der Abhängigkeiten

Beitrag von Walker »

Der Klassiker: Ich habe 3ecks-Fläche mit Indizes auf eine Vertexliste
-----------------------------------------------------------------------------------

Code: Alles auswählen

Faces with Indexes for Vertices:
 0:   1  7  3
 1:   0  2  4
 2:   3  5  4
 3:   8  0  5
 
 Vertices:
 0:    x0,y0,z0
 1:    x1,y1,z1
 2:    x2,y2,z2
 3:    x3,y3,z3
 4:    x4,y4,z4
 5:    x5,y5,z5
 6:    x6,y6,z6
 7:    x7,y7,z7
 8:    x8,y8,z8
-----------------------------------------------------------------------------------
Diese will ich nun mergen. Also Vertices zusammenfassen die ähnlich sind .

Merge ==> Ergebnis:
Vertex 4 and 5 and 7 are the same
Vertex 2 and 6 are the same

Result:

Code: Alles auswählen

Faces with Indexes for Vertices:
 0:   1  4  3
 1:   0  2  3
 2:   3  4  3
 3:   5  0  4
  
 Vertices:
 0:    x0,y0,z0
 1:    x1,y1,z1
 2:    x2,y2,z2 -> like 6
 3:    x3,y3,z3
 4:    x4,y4,z4 -> like 5 and 7
    5:    x5,y5,z5 ->remove
    6:    x6,y6,z6 ->remove
    7:    x7,y7,z7 ->remove
 8:    x8,y8,z8 -> becomes 5:
 
Ich weiß also welche Original Vertex Index ggf. noch gleiche Vertices hat und welche das sind in der Original Vertexliste.

Jetzt gibt es natürlich unendlich viele Möglichkeiten an so ein Thema heranzugehen. Man kann eine Kopie der Daten machen wenn man das von Original zum Ziel überträgt. Man kann ein Puzzle machen und Stück für Stück einzelne Indexe die in den Faces verwendet werden durch den ersten Index der Kopien halt ersetzen und deren Kopien in der Vertexliste dann rauswerfen. Dabei verschieben sich die Indexe wieder...

Gibt es für sowas Erfahrungen bei euch, wie würdet ihr vorgehen ?

Es geht durchaus um bis zu 500000 Dreicke mit entsprechenden Vertices (und Normalen und UVs.. selbes Thema), aber letztlich ist es nicht groß Zeitkritisch da es ein vorgelagerter Prozess ist.
Benutzeravatar
dot
Establishment
Beiträge: 1745
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: Vertices mergen und Reorganisation der Abhängigkeiten

Beitrag von dot »

Mach ein Array wo für jeden Vertex dessen neuer Index drinsteht: Lauf über alle Vertices, zähl mit was der nächste freie Index ist. Wenn ein Vertex gelöscht werden soll wird der Counter nicht inkrementiert und stattdessen der Index des Vertex mit dem germerged werden soll ausgegeben (wenn bei zu mergenden Vertices immer der mit dem niedrigsten Index behalten wird, kannst du im bereits bestehenden Teil des Arrays nachschlagen was der neue Index ist). Gleichzeitig kannst du auch die Vertices die nicht gelöscht werden schon an ihren neuen Platz kopieren. Dann ist das nur noch eine Frage von den Indexbuffer durch dieses Mapping laufen lassen (für jeden alten Index kannst du im generierten Array den neuen Index nachschlagen) und du bist fertig.
Zuletzt geändert von dot am 17.11.2022, 14:51, insgesamt 4-mal geändert.
Benutzeravatar
Krishty
Establishment
Beiträge: 8316
Registriert: 26.02.2009, 11:18
Benutzertext: state is the enemy
Kontaktdaten:

Re: Vertices mergen und Reorganisation der Abhängigkeiten

Beitrag von Krishty »

Ich hatte das damals (2009?) für Assimp poliert, und da hatten wir es so gemacht:
  • Von 3-D-Problem zu 1-D-Problem reduzieren, indem alle Vertices auf eine schief im Raum liegende Achse projiziert werden
    • Da gibt es noch verschiedene Möglichkeiten, eine optimale Achse zu finden … Prinicipal Component Analysis oder so?
    • Für Assimp war einfach irgendein schiefer Vektor hard-coded
  • Nun die Vertices gemäß ihrer Koordinate auf der Achse sortieren (Indizes entsprechend anpassen)
  • Durchs sortierte Array laufen:
    • Falls zwei aufeinander folgende Vertices die selbe Koordinate auf der Achse haben, könnten sie im 3D-Raum identisch sein -> dann volle Prüfung auf Duplikat (Koordinaten, Texturkoordinaten, Farben)
    • Da wird klar, warum die Achse möglichst schief liegen sollte
    • Bei erkanntem Duplikat alle Indizes des Duplikats auf den ersten Index umbiegen
    • Kann man optimieren, so dass unbenutzte Vertices ans Ende des Arrays geschoben oder direkt überschrieben werden (Edit: Was dot schreibt)
  • ???
  • PROFIT
seziert Ace Combat, Driver, und S.T.A.L.K.E.R.   —   rendert Sterne
Walker
Beiträge: 42
Registriert: 28.07.2017, 08:58
Alter Benutzername: Walker

Re: Vertices mergen und Reorganisation der Abhängigkeiten

Beitrag von Walker »

Krishty hat geschrieben: 17.11.2022, 14:45 [*]Bei erkanntem Duplikat alle Indizes des Duplikats auf den ersten Index umbiegen
[*]Kann man optimieren, so dass unbenutzte Vertices ans Ende des Arrays geschoben oder direkt überschrieben werden (Edit: Was dot schreibt)
Das mit dem nach hinten setzen ist interessant. Man fängt ja i.d.R. von Vorne nach hinten an, so das man das auch in der Faceliste "mitziehen" kann.

Ich habe gerade mal testhalber etwas nachgebaut was Three.js da macht. Der Ansatz mit den "Strings" in einer Map würde für mich da erstmal ausreichen.
Die Erzeugen eine Kopie und parallel eine Changelist.
https://github.com/mrdoob/three.js/blob ... #L847-L928
Matthias Gubisch
Establishment
Beiträge: 488
Registriert: 01.03.2009, 19:09

Re: Vertices mergen und Reorganisation der Abhängigkeiten

Beitrag von Matthias Gubisch »

Ich hab das mal mittels einer hashmap gelöst
Hashvalue für vertices bestimmen
Wenn der hashvalue nicht in der map ist den vertex in das array packen und den zugehörigen Index in der hashmap speichern
Und dann halt den indexbuffer mit den Werten aus der hasmap direkt mit aufbauen

Das ganze war beim Laden der assets eingehängt
Effizienz ka, für nen asset converter hats gereicht.

Mittlerweile nutze ich eine opensource lib dafür die relativ flott ist. Da könnte man mal reinschauen wie das gelöst ist.
Hier noch der link.
https://github.com/zeux/meshoptimizer
Bevor man den Kopf schüttelt, sollte man sich vergewissern einen zu haben
Walker
Beiträge: 42
Registriert: 28.07.2017, 08:58
Alter Benutzername: Walker

Re: Vertices mergen und Reorganisation der Abhängigkeiten

Beitrag von Walker »

Hat etwas gedauert wegen anderer Dinge aber es läuft jetzt. Ich habe den Kopieransatz genutzt (also die optimierte Liste parallel mit aufbauen und Indexverschiebung merken) . Das Ganze in einer Template Klasse für 2 versch. Klassentypen (UV hat nur u und v, Normalen oder Vertices x,y,z). Ich kann das jetzt nach Bedarf kombinieren. Also wenn Normalen und UVs von der Anzahl gleich sind werden die zusammengefasst (einfach via string-key) berücksichtigt, sonst halt nur einzelne "Listen" (UV(UV2),Normals,Vertices) optimiert.
Die Idee von Krishty "Von 3-D-Problem zu 1-D-Problem reduzieren" hat etwas gebraucht, aber wäre sicherlich interessant wenn das ganze Zeitkritisch ist. Ebenso die Hash-Dinge.

Ich danke euch.
Antworten