Progressive Mesh Datenstruktur?

[thordk]

ich will für ein paar objekte die dreiecks anzahl reduzieren und dafür progressive meshes benutzen. die dinger werden also als eine folge von meshes beschrieben, ausgehend von der kleinsten menge an ecken. dafür muss ich die ecken bzw. kanten schrittweise reduzieren.

allerdings liegen die objekte als eine liste von dreiecken vor und sind teilweise extrem gross. deshalb wollte ich sie in eine struktur bringen, die dafür besser geeignet ist, aber irgendwie will mir nicht so recht einfallen, welche struktur dafür am geeignetsten ist.

- ich brauch alle ecken
- ich brauch alle kanten
- die ecken müssen disjunkt sein

im laufe der reduktion werden kanten verglichen und knoten entfernt. sobald ein knoten entfernt wurde, müssen alle kanten, die diesen knoten enthalten, entsprechend angepasst werden.

ich hab erst überlegt, die ecken als std::map zu speichern und die kanten als std::vectorstd::pair. so wäre garantiert, dass die ecken disjunkt sind, aber der zugriff auf die kanten bei entfernung einer ecke wäre extrem langsam, da man den vector komplett durchlaufen muss.

speicher ich nun die kanten auch in ner map (oder multimap), müsste ich sie zweimal vorhalten, um reflexivität abzudecken... alles nur halbgar.

es ist zudem nicht garantiert, dass die objektoberfläche geschlossen ist. können durchaus mal paar dreiecke irgendwo in der gegend rumfliegen.

jemand ne tolle idee?

[mac_bu]

Hi,

Ich denke, dass du dir über den Speicher zunächst keine Sorgen machen solltest. Das verkompliziert die Implementierung oft unnötig. Vorstellbar wäre etwas in der Art:

class CPoint;
class CEdge;
class CTriangle;

class CPoint
{
int Index; //falls z.B. hashing benutzt wird. jeder Punkt benötigt dann einen einmaligen index
ConnectedList<CTopoTriangle*> m_ConnectedTris; //Verkettete Liste, die auf angrenzende Dreiecke verweist. -Kostet Arbeitspeicher, verringert den Aufwand aber enorm
};

class CEdge
{
CPoint* m_P[2];
CTriangle* m_AdjacentTris[2]; //Benachbarte Dreiecke (max. 2 bei regulärer Oberfläche - sonst vector<CTriangle*> benutzen)
};

class CTriangle
{
CTriangle* m_pAdjacentTri[3];
CEdge* m_pEdge[3];
CPoint* m_pPoint[3];
};

.
.
.

sehr grob, ich weiß.
Wenn du es schnell (und ein bischen schmutzig) machen willst dann würde ich dir vorschlagen die Elemente in verketteten listen zu speichern (je eine für Punkte, Ecken, Tris). Den Elementen kannst du dann einen Pointer auf ihren Eintrag mitgeben und sie so mit praktisch keinem Aufwand aus der Liste entfernen.

Generell mußt du dich entscheiden ob du lieber etwas mehr Speicher verbrauchen, oder mehr Rechenleistung investieren willst. Ich würde dir dringend dazu raten den Speicher zu belasten da du sonst schnell bei einem Aufwand von o(n^3) oder mehr landest (n Anzahl der Kanten oder Knoten oder Dreiecke - sollte im normalfall zusammenhängen). Solltest du eine Struktur wie oben benutzen (mit vielen Pointer-querverweisen) mußt du sehr darauf achten beim Löschen von Elementen die Verweise der benachbarten Elemente zu erneuern (mußt du ja sowieso machen).

Falls du Texturierte Objekte benutzt kann die Sache recht knifflig werden (da dann beim löschen von Knoten auch die u-v Koordinaten überarbeiten werden müssen).

Nur noch zur Info: DirectX (d3dx9) stellt Progressive meshes zur Verfügung.
Außerdem gibt es da noch nVidia melody. Das kann dir sogar normalmaps für dein Objekt generieren (habs allerdings noch nie ausprobiert).

Die papers kennst du ja wahrscheinlich-
Hoppe Mesh optimization
Hoppe progressive meshes

Viel Spaß!