Files |  Tutorials |  Articles |  Links |  Home |  Team |  Forum |  Wiki |  Impressum

Aktuelle Zeit: Do Mär 28, 2024 12:58

Foren-Übersicht » Programmierung » Mathematik-Forum
Unbeantwortete Themen | Aktive Themen



Ein neues Thema erstellen Auf das Thema antworten  [ 6 Beiträge ] 
Autor Nachricht
BeitragVerfasst: Di Jun 26, 2012 13:04 
Offline
DGL Member

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


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Di Jun 26, 2012 17:57 
Offline
DGL Member
Benutzeravatar

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java
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.

_________________
Yeah! :mrgreen:


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Jun 27, 2012 12:43 
Offline
DGL Member

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.

Anbei noch mal drei beispielhafte Dreiecke.


Viele Grüße
Chris


Dateianhänge:
Dateikommentar: Beispieldreiecke
Dreiecke.jpg
Dreiecke.jpg [ 21.61 KiB | 11207-mal betrachtet ]
Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Mi Jun 27, 2012 17:57 
Offline
DGL Member
Benutzeravatar

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java
Zitat:
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:
  1. for (unsigned i=0; i<DREIECKE; ++i) {
  2.     for (unsigned j=0; j<3; ++j) {
  3.         unsigned index = GetIndex(Dreiecke[i].Punkt[j]);
  4.         pointMap.insert(std::make_pair(index, i));
  5.     }
  6. }

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:
Code:
  1. // ein paar typedefs für die lesbarkeit
  2. typedef std::multimap<unsigned, unsigned> PointMap;
  3. typedef PointMap::const_iterator PointMapItr;
  4. typedef std::pair<PointMapItr,PointMapItr> PointMapItrPair;
  5.  
  6.  
  7. std::vector<unsigned> matches; // dynamisches Array zum sammeln der potentiellen Nachbarn
  8.  
  9. for (unsigned i=0; i<DREIECKE; ++i) {
  10.     matches.clear();
  11.     for (unsigned j=0; j<3; ++j) {
  12.         unsigned index = GetIndex(Dreiecke[i].Punkt[j]);
  13.         PointMapItrPair range = pointMap.equal_range(index);  // gibt Begin/End-Iterator auf den Bereich mit "Key = Index" zurück
  14.         for (PointMapItr itr = range.first; itr != range.second; ++itr) {
  15.             matches.push_back(itr->second);    // alle potentiellen Nachbarn sammeln
  16.         }
  17.     }
  18.  
  19.     // findet sich nun ein Dreiecksindex mehrfach im Array sind offensichtlich zwei (oder drei) Punkte gleich!!
  20.     // Das Array sollte mindestens drei Elemente enthalten, nämlich drei Treffer für das Dreieck selbst
  21.  
  22.     std::sort(matches.begin(), matches.end()); // potentielle Nachbarn sortieren
  23.    
  24.     for (unsigned m=0; m<matches.size()-1; ++m) {
  25.         if (matches[m] != matches[m+1]) { continue; }
  26.  
  27.         // Nachbar gefunden!! (=> hier die Behandlung dafür einfügen)
  28.  
  29.         ++m; // nächsten überspringen, so werden Dreifach-Treffer automatisch ignoriert.
  30.     }
  31. }



Edit: Hier noch eine Implementierung für GetIndex gerade mal aus meiner alten Diplomarbeit geklaut:
Code:
  1. uint32_t Building::indexCoord(CML::Vector3i coord) {
  2.     static const uint32_t SIZE = 1024; // Range: -511...512 => 0...1023
  3.     static const CML::Vector3i MAX = CML::Vector3i(SIZE/2-1,SIZE/2-1,SIZE/2-1);
  4.     static const CML::Vector3i MIN = CML::Vector3i(-SIZE/2,-SIZE/2,-SIZE/2);
  5.     coord = CML::max(coord, MIN);
  6.     coord = CML::min(coord, MAX);
  7.     coord += MAX;
  8.     return (uint32_t)coord.x + (uint32_t)coord.y*SIZE + (uint32_t)coord.z*(SIZE*SIZE);
  9. }

Wie in meinem ersten Post schon sagte macht es Sinn deine Daten zu verschieben bzw. zu skalieren damit das runden auf Integer Sinn macht.

_________________
Yeah! :mrgreen:


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Jun 28, 2012 13:06 
Offline
DGL Member

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.


Nach oben
 Profil  
Mit Zitat antworten  
BeitragVerfasst: Do Jun 28, 2012 16:53 
Offline
DGL Member
Benutzeravatar

Registriert: Do Dez 29, 2005 12:28
Beiträge: 2249
Wohnort: Düsseldorf
Programmiersprache: C++, C#, Java
Beim draufgucken springt mir gerade ein Fehler ins Auge:
Code:
  1. for (PointMapItr itr = range.first; itr != range.second; ++itr) {
  2.       matches.push_back(itr->second);    // alle potentiellen Nachbarn sammeln
  3. }


Hier muss natürlich geprüft werden ob die Punkte wirklich übereinstimmen....wenn der Index gleich ist reicht das natürlich nicht. :roll:

_________________
Yeah! :mrgreen:


Nach oben
 Profil  
Mit Zitat antworten  
Beiträge der letzten Zeit anzeigen:  Sortiere nach  
Ein neues Thema erstellen Auf das Thema antworten  [ 6 Beiträge ] 
Foren-Übersicht » Programmierung » Mathematik-Forum


Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 10 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.

Suche nach:
Gehe zu:  
cron
  Powered by phpBB® Forum Software © phpBB Group
Deutsche Übersetzung durch phpBB.de
[ Time : 0.050s | 19 Queries | GZIP : On ]