Performanz Steigerung von Marching Cubes

Hallo,

ich würde gerne meinen Marching Cubes performanter machen.

Dazu würde ich gerne eine Art indizierte Liste erstellen, um die mehrfache Berechnung von Vertices und Normalen zu verhindern.
Allerdings stehe ich momentan etwas auf dem Schlauch und wäre für jeden Tipp dankbar, wie ich das am besten lösen kann.

Ich habe mir das etwa wie Hashing vorgestellt, also dass aus jeder xyz-Koordinate ein Key erzeugt wird.
Wenn dieser Platz noch leer ist, sollen dafür Normale und Vertex Position berechnet und eingetragen werden,
ansonsten soll einfach ein Index dafür erstellt werden.

Nur bin ich mir nicht sicher, ob das wirklich der beste Ansatz ist, da es viele Millionen Voxel geben kann und die Hashmap dadurch sehr riesig ausfallen würde.

Ich bin gespannt auf Eure Meinungen!

jencas

Schau Dir mal std::map an.

Hallo,

danke für die Antwort! Ich habe mir mal std::map angeschaut und es ist schon so ziemlich was ich gesucht habe.

Mein Problem ist jetzt nur, einen eindeutigen key für jeden Vertex zu generieren.

Da ich nicht wirklich Marching Cubes, sondern einen selbst entwickelten Algorithmus zum triangulieren des Volumens verwende,
habe ich Vertices, deren xyz-Koordinaten floats von 0 bis 255 sein können.

Am liebsten würde ich als key den Positionsvektor der Vertices nehmen, was mit std::map aber leider nicht kompatibel ist.

Meine Idee war, aus dem Vector einen Integer-key zu machen (x = 100.5, y = 56.0, z = 242.5 --> 100505602425), aber die Länge sprengt ja leider den Rahmen.

Kann mir vielleicht jemand weiterhelfen?

knivil

was mit std::map aber leider nicht kompatibel ist.

Doch, das geht. Du musst nur einen entsprechend < Funktion/Operator definieren.

jencas

t0bsen schrieb:

Meine Idee war, aus dem Vector einen Integer-key zu machen (x = 100.5, y = 56.0, z = 242.5 --> 100505602425), aber die Länge sprengt ja leider den Rahmen.

Nimm doch einfach einen string als key:

"100.5;56.;242.5"

Eindeutigkeit erreichst Du, indem Du "trailing zeros" bei den Nachkommastellen weglässt (siehe Beispiel oben) oder auf eine feste Anzahl Nachkommastellen normierst.

knivil

Um ehrlich zu sein: das ist eine dumme Idee.

jencas

knivil schrieb:

Um ehrlich zu sein: das ist eine dumme Idee.

Wenn Du schon sowas von Dir gibst, dann solltest Du das auch begründen. So ein Beitrag hilft dem TO in keiner Weise weiter.

kimmi

Ich denke, es geht darum, daß das Generieren des Keys bestehend aus Strings, die ja erst aus den Koordinaten erstellt werden müssen, teuer ist. Nimm doch als Key einfach den Index den vertices im Array oder so was.

Gruß Kimmi