Registriert: Di Jun 26, 2012 08:15 Beiträge: 10
Programmiersprache: C#
Hi,
ich habe mir einen kleinen Viewer für Autodesk Inventor Modelle mit OpenGL gebastelt. Derzeit funktioniert das Einlesen von STL Dateien. Da diese ja die Dreiecke eines Modells beinhalten, lassen sich die Daten sehr gut mit OpenGL verarbeiten und anzeigen. Ich habe also Polygone, die aus Dreiecken bestehen.
Diese Polygone möchte ich nun gruppieren. Beispielsweise möchte ich von einem eingelesenen Würfel die 6 Seiten (bspw. mit ColorPicking) einzeln ansteuern können, also sie als Polygone behandeln. Dazu muss ich ja die Seiten jeweils in eine GenLists packen, und dazu muss ich die eingelesenen Dreiecke ja irgendwie gruppieren.
Mein Ansatz, der auch schon soweit funktioniert, bis zu einer Anzahl Dreiecke >4000: - Ich lese das STL File ein und packe alle Dreiecke in eine Liste (Array) - Ich gehe die Liste der Dreiecke durch und ordne jedem Dreieck seine 3 Nachbarn zu. - Jedes Dreieck bekommt ein Flag gesetzt, das angibt, ob die Z-Achse, Y-Achse oder X-Achse bei allen 3 Punkten gleich ist. Wenn keines der drei Fälle auftritt, erhält es ebenfalls ein Flag. - Ich gehe rekursiv die Liste der verknüpften Dreiecke durch und erstelle mir jeweils eine Liste mit allen zusammenhängenden Nachbarn, die auf einer Ebene liegen. Die besuchten Dreiecke markiere ich. Markierte Dreiecke werden nicht noch einmal besucht. So habe ich am Ende alle zusammenhängenden 2d Flächen als einzelne Polygone.
Das ganze funktioniert bei kleinen Dateien sehr gut, bei großen nicht. Ich komme auch nicht mal über den Aufwand von O(n²) hinaus.
Gibt es für so etwas vielleicht noch eine andere Lösung? # Viele Grüße chris
Die Standard-Lösung wäre das du diese Gruppen direkt aus deiner Modelingsoftware mit exportierst. Häufig hat man nämlich etwa leichte Rundungen die trotzdem die gleiche Textur bekommen sollen, oder die Normalen gesmootht werden sollen. => Das legt der Artist bei modellieren fest! Allerdings kenne ich das STL-Format nicht, also wäre möglich das dies nicht geht.
Der Aufwand steckt bei dir beim finden der Nachbar-Dreiecke. Hier kannst du mit einer Suchstruktur optimieren. Ich nutze für sowas gerne ein SparseGrid, weil bei Nutzung der Standardbibliothek einfach zu implementieren. Die Grundidee ist einfach das du für jeden Punkt einen Hash berechnest. Letztlich schneidest du einfach von einem Punkt die Nachkommastellen ab erhältst so Zellen. Jede Zelle kriegt eine Nummer (einfach in allen drei Dimensionen durch zählen) und dann sortierst du die Punkte anhand dieses Zellenindex in eine Map-Datenstruktur ein. Suchst du nun einen Partner zu einem bestimmten Punkt brauchst du nur noch gegen die in dieser Zelle enthaltenen Punkte prüfen. Der Trick hier ist das nicht alle möglichen Zellen realisiert werden, sondern du erzeugst in der Map-Datenstruktur nur die Zellen die es auch tatsächlich gibt.
Als Erweiterung kannst du auch leicht einen Epsilon-Radius um einen Punkt prüfen. Solange Epsilon kleiner als eine Zelle ist, reicht es den 2x2x2 Block um den fraglichen Punkt zu prüfen. Einfach den Punkt + bzw. - Epsilon auf jeder Achse und den Index berechnen. Vorausgesetzt die Zellen sind vernünftig dimensioniert, liegt der Aufwand für die Aktion bei vernünftiger Map-Datenstruktur bei O(n*log(n)). Ggf. macht es Sinn vorher eine BoundingBox zu berechnen um die Daten vor der Indexberechnung sinnvoll skalieren/verschieben zu können.
Registriert: Di Jun 26, 2012 08:15 Beiträge: 10
Programmiersprache: C#
Hi,
super vielen Dank für die schnelle Antwort. Via Modellierungssoftware kann ich das in STL leider nicht exportieren. STL ist dafür nicht ausgelegt. Das Dateiformat enthält lediglich Dreiecke mit den Inhalten: Facet - Normalvektor (ist meistens in allen Exporten (0,0,0)) - Vertex 1 - Vertex 2 - Vertex 3 - Color EndFacet
Zitat:
Der Aufwand steckt bei dir beim finden der Nachbar-Dreiecke.
Genau. Ich habe derzeit mit meiner Rekursion eine Ladezeit von 1min bei 13000 Dreiecken. Mit vielen Tricks und gutem Vorbereiten der Daten (bspw. nach einmaligen Einlesen eine neue vorsortierte Datei anlegen) kann ich das sicher auf wenige Sekunden runterschrauben.
Es wäre natürlich schön, wenn das auch ohne Vorsortieren ginge. Leider komme ich mit deiner Hilfe noch nicht klar. Ich kenne mich mit SparseGrid gar nicht aus. Kannst du mir ein kleines Beispiel mit 2-3 Dreiecken geben? Oder vielleicht einen guten Link, in dem dein Vorschlag erklärt wird? Am besten mit Bildern. Ich bin mir sicher, dass ich das hin bekomme, sofern ich es dann verstanden habe.
Genau. Ich habe derzeit mit meiner Rekursion eine Ladezeit von 1min bei 13000 Dreiecken.
Rekursion? Das sollte über eine Doppelschleife gelöst werden.(darum ja auch O(n²) )
Zitat:
Leider komme ich mit deiner Hilfe noch nicht klar. Ich kenne mich mit SparseGrid gar nicht aus.
Da gibt es eigentlich nicht viel zu erklären. Eine Grid-Datenstruktur ist in deinem Fall einfach ein 3D-Array bei dem in jeder Zelle wieder ein dynamisches Array liegt. Das brauchst natürlich viel zu viel Speicher, weil die meisten Zellen ja eh leer sein werden. Ein SparseGrid ("Sparse" = spärlich/wenig) ist nun ein Grid bei dem nur die notwendigen Zellen realisiert werden. Durch die Indexgenerierung kannst du deine 3D-Daten auf 1D abbilden, was es erlaubt existierende Datenstrukturen zu missbrauchen.
Vorweg: Ich kann leider kein C#, ich versuche daher via C++ zu erklären. Und ich hab den Code natürlich nur gerade so runtergeschrieben, nicht ausprobiert....
Also als Datenstruktur benutze ich ein std::multimap<unsigned, unsigned>. Das ist eine Map-Datenstruktur die mehrere Einträge mit dem gleichen Key erlaubt. Laut Google scheint es sowas in C# tatsächlich nicht zu geben (WTF? Ich dachte die C++STL wäre unvollständig...), was am nächsten ran kommt wäre wohl System.Collections.Generic.Dictionary<k,v>. Die mehreren Einträge mit dem gleichen Key musst du dann über ein dynamisches Array als "Value" simulieren oder dir irgendwo eine Implementierung suchen.
Worum es mir geht ist einen Punktindex als "Key" zu benutzen und einen Dreiecksindex als "Value". Im ersten Schritt füllst du deine Datenstruktur mit Daten:
Code:
for (unsigned i=0; i<DREIECKE; ++i) {
for (unsigned j=0; j<3; ++j) {
unsigned index = GetIndex(Dreiecke[i].Punkt[j]);
pointMap.insert(std::make_pair(index, i));
}
}
Jedes Dreieck ist also genau dreimal in der Datenstruktur einsortiert. Ich vermute mal deine Definition von Nachbar ist wenn zwei Punkt der Dreiecke gleich sind, richtig? Wenn du nun deine Nachbardreiecke suchst gehst du ca. so vor:
Registriert: Di Jun 26, 2012 08:15 Beiträge: 10
Programmiersprache: C#
Hi,
also, ich habs dann jetzt verstanden. Ich habs dann nur ein wenig anders umgesetzt: Beim Einlesen der Daten erstelle ich mir eine Liste meiner Dreiecke und zusätzlich eine Liste aller Linien insgesamt. Die Linien sind ein Struct, das die Referenz zu dem dazugehörigen Dreieck (erspart mir eine Id) und einen String aus den zwei Punkten (x1y1z1x2y2z3) (erspart mir das errechnen eines Hashwertes) beinhaltet. Ich sortiere mir jetzt Liste der Linien und gehe dann O(n)/2 durch und vergleiche immer die beiden aufeinanderfolgenden Linien und verlinke die Dreiecke der Linien miteinander. Das reduziert meine Ladezeit von >60sekunden auf <1sek.
Danke!!!
Zitat:
Rekursion? Das sollte über eine Doppelschleife gelöst werden.(darum ja auch O(n²) )
Ja.. sorry, die Rekursion, die ich meinte, führe ich danach aus. Mit dem o.g. Schritt habe ich mir einen Graphen gebastelt und ich hole mir nun alle Dreiecke, die verknüpft sind. Vorher verknüpfe ich ja immer nur zwei Dreiecke. Ich meinte in dem Post natürlich die Doppelschleife.
Mitglieder in diesem Forum: 0 Mitglieder und 2 Gäste
Du darfst keine neuen Themen in diesem Forum erstellen. Du darfst keine Antworten zu Themen in diesem Forum erstellen. Du darfst deine Beiträge in diesem Forum nicht ändern. Du darfst deine Beiträge in diesem Forum nicht löschen. Du darfst keine Dateianhänge in diesem Forum erstellen.