[Solved]Auslesen eines STL-Files

Guten Morgen !
Bräuchte ein paar Gedanken zur Effizienz meines STL-Readers.
Es gibt sogenannte STL-Files um CAD-Modelle zu beschreiben. Es ist in meinem Fall eigentlich nur eine Folge von Dreiecken (auch Facette gennant, "Face" in english).
Sieht folgendermaßen aus:

facet normal 9.312581 -3.607713 -5.101419 //Beschreibt die Normale der aktuellen Facette
    outer loop
      vertex   6.346045 3.087754 3.050000       //1. Eckpunkt
      vertex   6.358383 3.112533 3.100000       //2. Eckpunkt
      vertex   6.338470 3.061131 3.100000       //3. Eckpunkt
    endloop
  endfacet
  facet normal 8.491101 -5.257467 5.101419
    outer loop
      vertex   6.346045 3.087754 3.050000
      vertex   6.375064 3.134622 3.050000
      vertex   6.358383 3.112533 3.100000
    endloop
  endfacet
usw.

Ich gehe sequentiell durch die Datei und speicher die Punkte ab (vector.push_back()). Für die Facetten lege ich Zeiger auf die entsprechenden Punkte an.

Das Problem ist, dass ich Punkte, die in mehreren Facetten Verwendung finden, nicht mehrfach speichern möchte. Deshalb schaue ich für jeden Punkt (naive Suche, also Vergleich mit jedem Element der Datenstruktur) ob er schon abgelegt wurde.
Die Daten, sind so abgelgt, dass wenn ein Punkt schon in der Liste ist, es schnell aufzufinden ist, weil ich von hinten suche (wegen push_back) und gemeinsam genutzte Punkte nah beieinander liegen.
Wenn das Element nicht vorhanden ist, muss ich aber die komplette Liste durchchecken.
Habe aber leider riesige Daten (Bis zu 50000 Punkte) und deshalb dauert es ewig bis das Modell geladen ist.

Würde mir ein besserer Suchalgorithmus(Bucketsort, Quicksort) überhaupt was bringen ?

Thx

Blue

rapso

Blue5teel schrieb:

Würde mir ein besserer Suchalgorithmus(Bucketsort, Quicksort) überhaupt was bringen ?

sort (english fuer sortieren) ist kein suchalgorithmus und wuerde dir somit nichts bringen.
std::map, use it.

C++ Forumbot

Dieser Thread wurde von Moderator/in rapso aus dem Forum Spiele-/Grafikprogrammierung in das Forum C++ verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

rapso schrieb:

Blue5teel schrieb:

Würde mir ein besserer Suchalgorithmus(Bucketsort, Quicksort) überhaupt was bringen ?

sort (english fuer sortieren) ist kein suchalgorithmus und wuerde dir somit nichts bringen.

Uups, wie peinlich. Meint natürlich Quicksearch. Und wie Bucketsort dahin kommt, weiss ich auch nicht. LOL (gibt es kein Smilie für rote Backen ?)

rapso schrieb:

std::map, use it.

Naja, sehr knapp dein Vorschlag. Bin mehr oder weniger C++ - Newbie.
Noch nicht verwendet diesen Container. Aber mal schauen, sonst heißt es ja noch ich sei ein faules Stück...

CStoll

Das Format kenne ich zufälligerweise, weil ich hier auch damit arbeite. Und wir haben hier eine recht schnelle Einlesefunktion auf der Basis von std::set<> (sprich: mittels binärer Suche) vorliegen.

Ok, dann mach ich einfach mal ne binäre Suche. Dann seh ich ja was es bringt
Thx

thordk

hab das ganze vor paar jahren für nen projekt auch gebraucht und std::set zum "aussortieren" verwendet. lief mit "paar mehr" punkten* noch recht performant.

* 500k aufwärts, 3D volumendaten

CStoll

Blue5teel schrieb:

rapso schrieb:

Blue5teel schrieb:

Würde mir ein besserer Suchalgorithmus(Bucketsort, Quicksort) überhaupt was bringen ?

sort (english fuer sortieren) ist kein suchalgorithmus und wuerde dir somit nichts bringen.

Uups, wie peinlich. Meint natürlich Quicksearch. Und wie Bucketsort dahin kommt, weiss ich auch nicht. LOL (gibt es kein Smilie für rote Backen ?)

Nicht wirklich, nur für rote Nasen

@binäre Suche: Dann mußt du natürlich auch ein Sortierkriterium für Punkte haben (bei uns wird komponentenweise verglichen) deine Punktliste sortiert halten (oder eine Hilfsliste verwenden - ist wohl günstiger für die weitere Verarbeitung).

thordk schrieb:

hab das ganze vor paar jahren für nen projekt auch gebraucht und std::set zum "aussortieren" verwendet. lief mit "paar mehr" punkten* noch recht performant.

* 500k aufwärts, 3D volumendaten

Keine falsche Bescheidenheit....
Klingt ja sehr vielversprechend.

Danke

Ok, hier bin ich nochmal.
Hab mich entschieden es mit einer std::map zu versuchen. Mir erschließt sich mehr und mehr der Sinn und Nutzen der STL !

Im Header der Klasse, in der ich die map verwenden möchte, habe ich stehen:

std::map<int, Vec, vecLess> VertexMap;

Meine Punkte sind vom selbstdefinierten Typen "Vec" (Klasse mit drei Floats x, y, z)
Damit die Sortierung der Map funktioniert brauche ich ja nen passenden Vergleichsoperator. Dafür habe ich "vecLess" definiert, welcher auf einen lexikographischen Kleiner-Vergleich der einzelnen Komponenten des Punktes(x,y,z) verweist.

Problem ist nur wo muss ich die Definition von "vecLess" hinschreiben ?
In den Header, ins Cpp-File, mit Edding auf den Bildschirm ??
Nach wie Vor burning Cpp-Noob....

Danke

Blue

hustbaer

Du kannst das hinschreiben wo du willst, es muss nur an der Stelle wo du map<X, Y, Z> verwenden möchtest X, Y und Z bereits definiert sein.

Normalerweise schreibe ich so Funktoren immer ins gleiche Headerfile wo auch die Klasse drinsteht wo sie dazugehören.

Hallo,

Bist Du sicher, dass Du ein int als Schlüssel der Map verwenden willst? Ich dachte, Du willst die map nach deinen Punkten (Dein selbsdefiniertes Vec) sortieren?
Da dann zum Schlüssel keine weiteren Daten gehören, kannst Du gleich, std::set nehmen, wie ja auch schon vorgeschlagen wurde.

CStoll

Die Punkte direkt in die map<> zu packen ist sowieso weniger sinnvoll, schließlich muß jedes Dreieck einen Bezug zu seinen Eckpunkten behalten und da ist ein map-Iterator größer als ein einfacher Zeiger.

(Bei "uns" werden die 3D-Daten in einer "Triangulation" (bestehend aus einem vector<NodeEntry> für die Ecken und einem vector<EdgeEntry> für die Kanten (Dreieck i besteht aus den Kanten 3i,3i+1,3i+2)) gespeichert und die Suchstruktur wird nur zum Einlesen der Daten aufgebaut (danach brauchst du sie auch nicht mehr) - ein set<int,point_less> (point_less vergleicht die Punkte "seines" Objekts anhand des Index))

Ok, Danke erstmal. Es klappt...
Habs mit std::set gemacht.

Ich lese die Eckpunkte der aktuellen Facette aus und speichere sie in folgenden Variablen:

Vec vec_a, vec_b, vec_c;

Der folgende Code beschreibt eine Iteration, in der überprüft wird ob die betrachteten Punkte schon vorhanden sind.

Vec temp;
it_a = model->VertexSet.find(vec_a);
if(it_a != model->VertexSet.end()){
temp = *it_a;
index_a = temp.index;
}

it_b = model->VertexSet.find(vec_b);
if(it_b != model->VertexSet.end()){
temp = *it_b;
index_b = temp.index;
}

it_c = model->VertexSet.find(vec_c);
if(it_c != model->VertexSet.end()){
temp = *it_c;
index_c = temp.index;
}

if(it_a == model->VertexSet.end()){
index_a = vec_a.index = vecindex++;
model->VertexSet.insert(vec_a);
}

if(it_b == model->VertexSet.end()){
index_b = vec_b.index = vecindex++;
model->VertexSet.insert(vec_b);
}

if(it_c == model->VertexSet.end()){
index_c = vec_c.index = vecindex++;
model->VertexSet.insert(vec_c);
}

}

myFace.x = index_a;
myFace.y = index_b;
myFace.z = index_c;

model->FaceList.push_back(myFace);

Wie CStoll ja schon geschrieben hat brauchte ich die Datenstruktur std::set nur zum Einlesen. Jetzt möchte ich die Punkte geordnet nach ihren Indizes (die ich ja während des Einlesens eindeutig vergeben habe)in ein std::vector<Vec> schreiben um beim Rendern schnellen Zugriff auf sie zu haben.
Wie bekomme die Punkte am schnellsten in den Vector ?

CStoll

Blue5teel schrieb:

Wie bekomme die Punkte am schnellsten in den Vector ?

push_back() (damit kannst du dir auch ersparen, den nächsten freien Index mitzuschleifen - den kannst du aus der Größe (size()) des Vektors ermitteln)

PS: die Hilfsvariable Temp ist übrigens überflüssig - du kannst direkt mit index_a=it_a->index; zuweisen. Und ansonsten solltest du deine if-Blöcke besser zusammenfassen:

it_a = model->VertexSet.find(vec_a);
if(it_a != model->VertexSet.end())
  index_a = it_a->index;
else
{
  index_a = vec_a.index = model->VertexList.size();
  VertexSet.insert(vec_a);
  model->VertexList.push_back(vec_a);
}

(wie gesagt, VertexSet kannst du lokal in der Lesefunktion anlegen - und anstelle der Punkte selber brauchst du eigentlich nur ihre Indizes speichern (und einen Comparator mitgeben, der das zugehörige Model kennt))

rapso

benutze

std::map<Vec,int>

Vec is dein vertextyp, int ist der index

einfuegen ueber

if(map.find(meinVektor)==map.end())map.insert(std::pair<Vec,int>(meinVektor,map.size())

wenn du fertig bist, steckst du alles in einen std::vector<Vec>, mit der size von der map. dafuer iterierst du dann durch die map und setzt vector[it->second]=it->first;

recht trivial.

[edit]
btw. kannst du den vergleichoperator in die Vec klasse einbauen, da die eh nen vergleichsoperator mit anderen Vec(toren) haben darf.

@CStoll Danke, klappt super. Ich bin fasziniert. Vielleicht sollte ich das nächste Mal nachdenken sollen bevor ich poste. Aber wenn man grad im Postwahn ist, vergisst man sowas schnell

@rapso Auch dein Ansatz sieht interessant aus. Aber et geht ja jetzt. Ausserdem haben die da oben mir ja verboten ne map zu verwenden

Bis demnächst

Blue

rapso

Blue5teel schrieb:

@rapso Auch dein Ansatz sieht interessant aus. Aber et geht ja jetzt. Ausserdem haben die da oben mir ja verboten ne map zu verwenden

1.wir haben wohl beide gleichzeitig die antwort getippt.
2. sie haben dir lediglich verboten dein map falsch zu verwenden, wenn ich das richtig sehe.