Nachbarbeziehungen bei Dreiecken
-
Hallo,
ich habe eine Liste von Dreiecken, die zusammen ein gesschlossenes 3D-Modell ergeben.
Nun möchte ich daraus eine Mesh - artige Struktur erstellen, ins besondere Nachbar-Beziehungen hinzufügen. Jedes Dreieck soll genau drei Nachbarn haben.
Das wäre ja prinzipiell machbar, aber da es sein kann, dass ein Dreieck mal mehrere Nachbarn an einer Kante hat, muss es in diesem Fall passend in mehrere Dreiecke zerlegt werden, so dass im Endeffekt genau 3 Nachbarn pro Dreieck ermöglicht werden. Und die einzige Art die mir einfällt die Nachbarbeziehungen für die unterteilten Dreiecke vollständig herzustellen ist wieder ein Vergleich mit allen vorhandenen Dreiecken, was zu extrem ungünstigen Laufzeiten führen kann.
Meine eigentliche Frage ist also: gibt es für diese Art Problem schon irgendwo sinnvolle Lösungsansätze, beziehungsweise hat jemand mit etwas vergleichbaren Erfahrung und kann mich auf den richtigen Weg leiten?
klaus
-
wenn ein dreieck eine kante mit mehr als einem dreieck teilt, wird unterteilen doch nichts bringen, dann hast du doch zwei kleine dreiecke die ihre kante weiterhin mit zwei dreiecken teilen.
oder ich versteh etwas nicht ?
wenn du ein dreiecksnetz generieren willst, bietet es sich an vorher alle vertexdaten zu indizieren. dafuer kannst du dir z.b. std::map<Vector3D,Idx> bauen und das als cache nutzen. wenn eine position nicht in der map ist, steckst du sie in dein vertex array/buffer/vector und den index in die map.
spaeter hast du dann nur 3 indices pro dreieck, meist sind diese nicht besonders riesig, sodass du eine kante als index1|(index2<<shift) zusammenbauen kannst. mit diesem wert kannst du in einem array indizieren, dass dreiecke enthaelt. ist noch kein dreieck drinne, ist das aktuelle dreieck vermutlich das erste mit dieser kante, also schreibst du den pointer fuer dieses in das array. ist schon eines drinnen, hast du das gegenstueck fuer die kankte gefunden.
das ganze ist sehr performant, kann aber speicherkritisch sein falls du millionen von dreiecken hast
