Drahtgitteroptimierung evtl. mit Baumstruktur. Wie?

[dizzy]

Hallo liebe Leut'.

Folgendes Problem: Ich muss ein 3D-Drahtgitter optimieren. Bisheriges Problem ist, dass mein Programm zwar ein 3D-Objekt bzw. die Koordinaten der Flächenpunkte erfolgreich errechnet, allerdings werden bei z.B. 2 zusammenhängenden Flächen die gemeinsamen Punkte doppelt hinterlegt. Dies möchte ich gerne verhindern!
Als Beispiel mal im .obj-Stil (.obj = 3D-Dateiformat als ASCII, ähnlich .dfx (Autocad)) wie es dann ausschaut:

Delphi-Quellcode:

Vertices:
1 :  0 /  0 /  0
2 : 10 /  0 /  0
3 :  0 / 10 /  0
Face 1: 1 / 2 / 3       <---- gibt an, aus welchen Punkten (Vertices) die Fläche besteht

Vertices:
4 : 10 /  0 /  0
5 :  0 / 10 /  0
6 : 10 / 10 /  0
Face 2: 4 / 5 / 6

Man sieht: Die Punkte (Koordinaten) 2/3 und 4/5 sind redundant und unnötig. Optimiert würde das etwa so aussehen:

Delphi-Quellcode:

Vertices:
1 :  0 /  0 /  0
2 : 10 /  0 /  0
3 :  0 / 10 /  0
4 : 10 / 10 /  0
Face 1: 1 / 2 / 3
Face 2: 2 / 3 / 4

Ich kenne bei der Berechnung der Puntke sowohl seine Koordinaten, als auch seine Flächenzugehörigkeit. Ein Weg, den ich mir vorstellen könnte, wäre eine Baumstruktur, die man dann beim Schreiben in die Datei rekursiv ausliest. Jedoch wurschtel ich hier schon gut rum, bekomm aber keine ordentliche unproblematische Struktur auf die Beine

Was auch zu beachten wäre: Es sind nicht selten > 1.000.000 Punkte!!! die es zu verwalten gilt. Also muss das Teil auch noch sehr schnell sein UND zu allem Überfluss auch noch speicheroptimiert sein.


Wie würdet IHR an sowas herangehen?
(Ist übrigends mein erstes Problem dieser Art. Mir fehlt wohl etwas Übung...)

Nochwas: Dieses Programm hat mit DirectX oder OGl nix zu tun. Von daher (falls es solche Methoden dort überhaupt gibt) wären Verweise in diese Richtung nicht sonderlich hilfreich. Das wäre dann nochmal Neuland für den kleinen dizzy

Ganz dick danke schonmal!
Herzlichen Gruss,
dizzy

[choose]

Hallo dizzy,

ich gehe nach Deiner Beschreibung davon aus, dass Du bisher keine Datentypen für die Vertices bzw Faces besitzt. Darüber hinaus scheints Du über keine Art von Container dieser nicht-vorhandenen Datentypen zu verfügen.

Führe beides in der Form TVertex, TShape bzw TVertices und TShapes in Form von Klassen ein bzw. schreibe Dir Hilfsfunktionen, wenn Du mit dynamischen Arrays und Records oder etas ähnlichem Arbeiten möchtest.

Neben der Möglichkeit, dem Container TVertices neue Punkte hinzuzufügen, z.B.

Delphi-Quellcode:

var
  myVertex: TVertex;
begin
  myVertex:= myVertices.Add(x, y, z);

solltest Du auch Methoden zum Finden (Find), Löschen (Clear) etc. erstellen, so dass Du mit der Methode

Delphi-Quellcode:

function TVertices.FindOrCreateAndAdd(const X, Y, Z: Integer): TVertex;
begin
  if Self.Has(X, Y, Z) then
    Result:= Self.Find(X, Y, Z)
  else
    Result:= Self.Add(X, Y, Z);
end;

Dein Problem lösen können solltest:

Code:

Laden der Punkte nach EingabePunkte (TVertices)
Laden der Flächen nach EingabeFlächen (TShapes)
Erzeugen einer Leeren Punktmenge (TVertices)
Erzeugen einer Leeren Flächenmenge (TShapes)
Für jede Fläche f in EingabeFlächen 
  Wenn Fläche nicht in AusgebeFlächen 
    erstelle neue Fläche g
    Für jeden Punkt p in f
      q:= findeOderErzeugePunkt in AusgabePunkte
      füge q zu g hinzu
    füge g den Ausgabeflächen hinzu
Speichere die AusgabePunkte
Speichere die AusgabeFlächen

Bleiben nun nur noch die Funktionen zum Laden/Speichern

[marvin.maybe]

Hallo,

habe ich das richtig verstanden? Du willst aus Deiner Punkt-Liste einfach nur die Duplikate entfernen und die Index in den Flächen richtig anpassen? Wenn das schnell gehen soll (also kleiner als quadratischer Aufwand) würde ich so vorgehen:
1. Die Punktliste (samt ursprünglichem Index) sortieren, z.B. nach X, Y, Z.
2. Die Punktliste traversieren. Wenn Punkt i = Punkt i+1, dann Punkt i+1 löschen und die Flächen anpassen.

Die Flächen müssen natürlich auch schnell zugreifbar sein, aber dass sollte kein Problem sein, oder?

Gruß, Marvin.

[dizzy]

Delphi-Quellcode:

type
  TVertex = record
    x,
    y,
    z : double;
  end;

  TOBJFace = record
    num : Integer;
    x,
    y,
    z : double;
  end;

Methode zum File-Schreiben:

Delphi-Quellcode:

procedure WriteOBJ(const coords: TVertex);
var Fnum, c, ed : Byte;
    PolyVertex  : TVertex;
begin
  TestFileSize;

  Fnum := DeterminPolyCount;
  if Fnum > 0 then
   begin
     for c := 1 to Fnum+1 do
      begin
        MakePolygonIndex(c);
        for ed := 1 to 3 do
         begin
           PolyVertex := MakeWorldCoords(Edges[ind[ed]], coords);
           WriteLn(f, 'v ' + FloatToStrF(PolyVertex.x*10, ffFixed, 16, 3, fset) + ' ' +
                             FloatToStrF(PolyVertex.y*10, ffFixed, 16, 3, fset) + ' ' +
                             FloatToStrF(PolyVertex.z*10, ffFixed, 16, 3, fset));
         end; // ed-Loop
       WriteLn(f, 'f ',cf,'/',cf,' ',cf+1,'/',cf+1,' ',cf+2,'/',cf+2,'');
       inc(cf, 3);
       inc(cf2, 3);
      end; // c-Loop
   end; // If Fnum > 0
end;

Ich habe immer eine Ebene von Würfeln, die die Punkte enthalten (array), allerdings erst noch über einen internen Index. Also muss ich erst noch die "Weltkoordinaten" bestimmen - das bläht den Code so auf. Ferner nehme ich mir jeden Würfel einzeln vor, und schaue nach, wie viele Flächen in ihm errechnet wurden. Es sind IMMER Dreiecke. Dann nehme ich mir eine jede Fläche, und bestimme die Weltkoordinaten der zugehörigen Punkte (anhand von Daten, die hier nicht ersichtlich sind. Nicht wirklich relevant.). Diese werden nacheinander in das File geschrieben, und über das gesamte Drahtgitter mitgezählt. Danach schreibe ich mit der Zeile:
WriteLn(f, 'f ',cf,'/',cf,' ',cf+1,'/',cf+1,' ',cf+2,'/',cf+2,'');
Die Flächendefinition direkt unter die Deklaration der 3 Vertices.
(Das Gedönse mit 'cf' und so kommt deshalb zu stande, weil ich der Größe wegen schon die Ausgabe in mehrere Files splitten muss! Und die Vertex-Zählung beginnt für jedes File von neuem.

... ein kleiner Copy&Paste aus meinem Code

Das an sich ist nicht das Problem!

Zitat von choose:

Wenn Fläche nicht in AusgebeFlächen
erstelle neue Fläche g
Für jeden Punkt p in f
q:= findeOderErzeugePunkt in AusgabePunkte
füge q zu g hinzu
füge g den Ausgabeflächen hinzu

Die fetten Zeilen sind das eigentlich Problem. Ich habe über 1mio Punkte, die ich ALLE auf Redundanz testen müsste. Das ist schon ressourcentechnisch hart an der Grenze, von Rechenzeit mal ganz abgesehen

Von daher dachte ich an eine Baumstruktur, wo jeder Node (=Vertex) auf seine "Mit-Flächen-Erzeuger" zeigt, und ich rekursiv absuche, ab einem Startpunkt, welche Koordinaten zu welcher Fläche gehören. Allerdings entsteht ein Zeiger-Loop, da in einem Dreieck ja jeder Punkt eine Verbindung zu seinen beiden Mitstreitern hat. Somit würde man "im Kreis pointern", und die Rekursion läuft bis in alle Tage...


Sorry, die erste Erklärung war wohl doch etwas knapp in den Details. Es geht letztenendes um das "Marching Cube"-Verfahren, daher die Unterteilung in virtuelle Würfel. Das ist aber für das Problem an sich nicht maßgebend, aber vielleicht hilfreich zu wissen


Dank'schö schonmal, und nochmal,
dizzy

[dizzy]

Zitat von marvin.maybe:

Hallo,

habe ich das richtig verstanden? Du willst aus Deiner Punkt-Liste einfach nur die Duplikate entfernen und die Index in den Flächen richtig anpassen? Wenn das schnell gehen soll (also kleiner als quadratischer Aufwand) würde ich so vorgehen:
1. Die Punktliste (samt ursprünglichem Index) sortieren, z.B. nach X, Y, Z.
2. Die Punktliste traversieren. Wenn Punkt i = Punkt i+1, dann Punkt i+1 löschen und die Flächen anpassen.

Die Flächen müssen natürlich auch schnell zugreifbar sein, aber dass sollte kein Problem sein, oder?

Gruß, Marvin.

Ich bewege mich bei Dateigrößen von deutlich > 2 Gigabyte. Der Zeitaufwand wäre zu groß. Lieber würde ich bevor ich überhaupt etwas in eine Datei schreibe optimieren.

Als Beispiel: Ich lade meine erzeugten (nicht optimierten) .obj-Files in Cinema4D (3D-Tool). Dort gibt es einen Menupunkt "Mesh optimieren". Dort lässt sich einstellen, wie weit 2 Vertices max. von einenander entfernt sein dürfen um sie zu einem Vertex zusammen zu fassen. Für ein Mesh mit ca. 700.000 Polygonen (NICHT Punkten!) braucht das Programm ca. 1-2 Minuten um das zu bewerkstelligen. Nur möchte ich das im Vorhinein selber erledigen, allein schon der Dateigrößen wegen


Aber schon mal danke für einen Denkanstoß!
dizzy

[dizzy]

Eine kleine Grafik dazu.

[choose]

Hallo dizzy,

unter diesen Rahmenbedingungen halte ich es für besser, meinen Ansatz nur als Orientierung zu verwenden und stattdessen möglichst wenig im Speicher zu halten. Tatsächlich kann direkt bei Laden entschieden werden, ob ein Punkt abgebiltet werden muss oder nicht.

1. Für diesen Ansatz wäre Marvins Konzept anwendbar, ohne jedoch eine Menge sortieren zu müssen sondern lediglich in eine sortierte Menge neue Einträge einzuordnen (O(n)=ln(n))
2. Für den späteren Zugriff sollte zu jedem Punkt eine direkte Referenz in einer direkt addressierbaren Struktur (Array) abgelegt werden (die Menge der Punkt ist schon vor der Verarbeitung ermittelbar), mit der Komplexität O(n)=1 erreichbar.
   Tatsächlich ist es nicht notwendig, eine Objektreferenz abzulegen: Es reicht vollkommen aus, den ermittelten Index des neu hinzugefügten Punktes bzw des gefundenen abzulegen
3. Die Menge der Punkte wird gespeichert O(n)=n
4. Beim Lesen des Shapes (O(n)=n) werden die ursprünglichen Indizes mit der direkt adressierbaren Struktur verglichen, um den neuen Index zu ermitteln O(n)=1 und
5. unmittelbar in die Datei zurückgeschrieben O(n)=1

Wie man sieht, sollte sich das Problem mit einer Komplexität von O(n)=n lösen lassen

Hallo Marvin,

Zitat von marvin.maybe:

Die Flächen müssen natürlich auch schnell zugreifbar sein, aber dass sollte kein Problem sein, oder?

Wie willst Du das hinbekommen, ohne von jedem Punkt Referenzen zu halten? Wie hältst Du die Reihenfolge der Punkte (zB Uhrzeigersinn) aus Sicht einer Fläche bei, wenn Du lediglich eine Liste aller Flächen pro Punkt ablegst?

[dizzy]

Södale, ich hab mal ordentlich rumprobiert. Aber leider ist es keine O(n)=n Story

Das Problem sind die VIELEN Plattenzugriffe, und immens viele String-Operationen, und String-Vergleiche. Das zieht ganz gehörig an der Bremse.

Ich habs jetzt logendermaßen gemacht:

- Ich schreibe meinen ersten Punkt in die Datei
- überprüfn bis EOF, ob der nächste String schon vorhanden ist
- wenn ja, break, und aktuelle Zeilennummer gehört zum aktuellen Face
- dieses in nem dicken array merken
- wenn nein (bis EOF durchgerannt) -> append neuen Vertex
- in dickem array merken

Und das ganze in einer Schleife für eine tierisch wachsende Datei. Bei einer Qualitätsstufe des Meshes, die man getrost als "unbrauchbar" bis "indiskutabel" bezeichnen kann, bin ich trotz Optimierung bei Files von locker > 2 MB, und schon ab ca. 500k (ca. 3000 Vertices - und es werden bei guter Quali > 1mio !!!) wirds ungemütlich lahm .
Das liegt mit unter auch daran, dass allein die Berechnung des Meshes SEHR zeitintensiv ist (es geht um Quaternion-Fraktale = "echte" 3D-Fraktale). Das ist aber noch verschmerzbar, und teuflisch optimiert. Aber das ganze Platten- und Stringgerödel jetzt, das haut mir die ganze Codeoptimierung ad absurdum .

Aber funktionieren tut das SUPER! Nur ganz deutlich zu langsam.
Deshalb hoffte ich auch auf ein Verfahren, die ganze Optimierung schon bevor IRGENDWAS auf die Platte kommt erledigen zu können.
Ein Fakt hilft evtl.: Ich berechne das Objekt würfelweise. D.h. ich müsste lediglich die Vertices auf Dopplung prüfen, die zu Faces gehören, die zu Nachbarwürfeln gehören. Das Problem dabei ist allerdings, dass die vollkommen verstreut in der Datei liegen, und es gibt kein Sortierkriterium DAS in den Griff zu bekommen (zumal das ein 3-Dimensionales Problem ist).

Daher kam ich ursprünglich auf den Trichter eine Art verkettete Liste oder einen Zeigerbaum zu verwenden. Nur fehlt mir da leider jeglicher Ansatz zur Realisierung
Zumal man ja auch einen Baum für jeden neuen Vertex einmal komplett durchsuchen müsste, ob der nicht schon existiert! Aber das wäre halt im RAM und net auf der Pladde. Ich fürchte aber, dass ich da arg Speicherprobleme bekäme bei > 1mio Nodes (whatever) (Und der Stack bedankt sich bei einer solchen, wohlmöglich rekursiven Suche...)
Also muss wohl eine partielle Lösung her, weil alles im RAM -> zu viele Daten und alles auf der Platte -> deutlich zu langsam.
Isch krisch die Kriese

Habt schon mal kräftig Dank für etwas mehr Klarheit bei mir!
Falls euch dazu noch was nettes einfällt... ich sitz da jetzt sporadisch immer mal wieder, seit über 1 Monat dran. Hülfeee!