"Inseln" im Dreiecksmesh finden

Design Patterns, Erklärungen zu Algorithmen, Optimierung, Softwarearchitektur
Forumsregeln
Wenn das Problem mit einer Programmiersprache direkt zusammenhängt, bitte HIER posten.
Antworten
joggel

"Inseln" im Dreiecksmesh finden

Beitrag von joggel »

Hallo,

ich habe ein Dreiecksmesh (Liste von Vertices und Liste von Indices, die Dreiecke definiert. Ein Mesh eben..).
Jetzt kann es sein, dass dieser Mesh aus "Inseln" von Dreiecken besteht. Also Mengen von Dreiecken die "lose" zu dem Rest sind.
(Falls unklar ist was ich meine kann ich ja mal eine Skizze machen)

Ich möchte also die "losen" Teile separat haben. Quasi dann als eigenes Mesh. Dazu muss ich die "losen" Dreiecke aus dem ursprünglichen Mesh entfernen und in ein neues Mesh überführen.

Meine Frage ist nun:
Wie bekomme ich heraus (ich habe eben nur eine Liste von Vertices und eine mit Indices) welche Dreiecke ich da entfernen muss?
Gibt es dazu vlt schon einen Algorithmus nach dem ich googeln kann? Oder irgend welche Schlagwörter oder so?
Oder eine Idee..?
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: "Inseln" im Dreiecksmesh finden

Beitrag von Jonathan »

Ich nehme an, du willst das in C++-Code machen? Abhängig davon, wann und wie oft du das brauchst, wäre halt die Alternative es in einem Programm wie Blender zu machen, dass dafür schon entsprechende Funktionen bietet.

Ansonsten ist die zweite Frage, wie oft du es brauchst. Wenn du es nicht zu Laufzeit machen musst, kannst du einen simplen, aber ineffizienten Algorithmus implementieren, wenn es schnell laufen muss, musst du dir ggf. mehr Mühe geben.

Intuitiv würde ich sagen, dass eine Art Floodfill Inseln erkennt. D.h. du startest von einem beliebigen Punkt und markierst alle erreichbaren Punkte, den Cluster kann man ja als zusätzliches Vertexattribut speichern. Dann fängst du mit einem noch unmarkiertem Punkt von vorne an und findest so die zweite Insel.
Das setzt natürlich voraus, dass entsprechende Nachbarschaftsinformationen effizient bekannt sind. Wenn man die zur Laufzeit sucht, hat man da direkt quadratische oder noch üblere Laufzeiten, was bei großen Modellen entsprechend zu langsam ist. Daher wäre es vermutlich sinnvoll, zunächst ein paar Zusatzinfos zu sammeln. Spontan fällt mir da etwa die Winged Edge Darstellung ein, es gibt aber noch mehr. Hat man diese Darstellung erstmal, kann man sehr viele Mesh-Algorithmen viel effizienter implementieren, und da das so Standarddinger sind, sollte man auch genügend Infos finden, wie man die effizient aus einem Vertex- und Indexbuffer erzeugen kann.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: "Inseln" im Dreiecksmesh finden

Beitrag von dot »

Was ich machen würde ist effektiv einfach was Jonathan schon gesagt hat. Je nachdem wie du dein Mesh repräsentierst, kann man die Nachbarschaftsinfos einfach z.B. per Hashtable in O(n) aufbauen und O(1) abfragen…
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: "Inseln" im Dreiecksmesh finden

Beitrag von Jonathan »

Ich hab nochmal kurz nachgedacht. Was du für ein Floodfill ja eigentlich nur brauchst ist eine Liste an Nachbarschaften / Vertices die mit dem aktuellen verbunden sind. Ich glaube effizienter als eine Hashtabelle könnte es sein, einfach eine neue Struktur anzulegen, die für jeden Vertex z.B. 5 Nachbarn (abhängig davon, wie viele du maximal brauchst) speichern kann. Einfach als 2D Array. Die sind alle mit z.B. -1 initialisiert, so dass du erkennen kannst, wie viele belegt sind, bzw. wo der nächste freie Platz ist. Das 2D Array ist hier günstiger als z.B. eine Liste oder ein dynamischer Vektor, da du keine zusätzlichen Zeiger brauchst.
Dann musst du nur einmal deinen Indexbuffer durchgehen und die Nachbar eintragen, und kannst danach sehr effizient deine Inseln suchen. Die Hashmap wäre zwar allgemeiner, aber in diesem Fall weißt du ja, das so ziemlich jeder Vertex Nachbarn hat und das vermutlich keiner sehr viele hat, und kannst daher ziemlich schnell die richtige Stelle finden.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: "Inseln" im Dreiecksmesh finden

Beitrag von dot »

Jonathan hat geschrieben: 12.10.2021, 15:44Dann musst du nur einmal deinen Indexbuffer durchgehen und die Nachbar eintragen, […]
Die Frage ist dabei halt nur: Wie genau findest du raus wer deine Nachbarn sind? 😉

Ich verwend in der Regel eine Hashtable, in der jede Dreiecksedge als Paar von Start- und Endvertexindex auf den Index des jeweiligen Dreiecks gemapped wird. Dabei lauf ich alle Dreiecke einmal durch und schau für jede Kante, ob die umgekehrte Kante (also Start- und Endvertexindex vertauscht) schon in der Hashtable steht (für non-manifold Meshes einfach die Kante in beiden Richtungen checken). Falls ja hab ich einen Nachbar gefunden. Falls nicht adde ich die Kante. Auf diese Weise kannst du dann so eine Nachbarschaftsmap aufbauen, wie du sie beschreibst. Wobei ich vermutlich pro Dreieck einfach dessen maximal drei Nachbarn entlang jeder Kante in einem N×3 Array speichern würde. Und darauf kannst du dann einen Floodfill laufen lassen…
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: "Inseln" im Dreiecksmesh finden

Beitrag von Jonathan »

dot hat geschrieben: 12.10.2021, 15:58 Die Frage ist dabei halt nur: Wie genau findest du raus wer deine Nachbarn sind? 😉
Wieso ist das denn schwierig? Im Indexbuffer stehen ja die Indices direkt drin, man muss halt nur noch wissen, für welchen Draw-Mode (Triangle-Strip, Triangle-Fan, etc.) die sind. Der Vertex-Index ist dann ja auch dein Index für die Nachbarschafts-Struktur, also kannst du es direkt an der richtigen Stelle eintragen. Also zumindest solange es um Vertex-Nachbarn geht, möchte man für ein Dreieck alle angrenzenden Dreiecke wissen, braucht man wieder etwas leicht anderes, aber das erscheint mir für die Lösung des Problems nicht nötig.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Benutzeravatar
dot
Establishment
Beiträge: 1734
Registriert: 06.03.2004, 18:10
Echter Name: Michael Kenzel
Kontaktdaten:

Re: "Inseln" im Dreiecksmesh finden

Beitrag von dot »

Jonathan hat geschrieben: 12.10.2021, 17:05
dot hat geschrieben: 12.10.2021, 15:58 Die Frage ist dabei halt nur: Wie genau findest du raus wer deine Nachbarn sind? 😉
Wieso ist das denn schwierig? Im Indexbuffer stehen ja die Indices direkt drin, man muss halt nur noch wissen, für welchen Draw-Mode (Triangle-Strip, Triangle-Fan, etc.) die sind. Der Vertex-Index ist dann ja auch dein Index für die Nachbarschafts-Struktur, also kannst du es direkt an der richtigen Stelle eintragen. Also zumindest solange es um Vertex-Nachbarn geht, möchte man für ein Dreieck alle angrenzenden Dreiecke wissen, braucht man wieder etwas leicht anderes, aber das erscheint mir für die Lösung des Problems nicht nötig.
Gut, das läuft dann auf die Frage hinaus, was genau man als Nachbarschaft betrachten will. Sind Dreiecke die nur einen Vertex gemeinsam haben benachbart?
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: "Inseln" im Dreiecksmesh finden

Beitrag von Jonathan »

Gute Frage, das müsste unbedingt von joggel noch präzisiert werden.

Spontan würde ich sagen, dass ich Dreiecke die sich einen Vertex teilen, zu einer Insel gehören. Natürlich könnte man aber auch z.B. duplizierte Vertexe haben, da wäre dann zunächst die Frage, ob man die als getrennt oder verbunden betrachten will und danach, wie man das effizient implementiert.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
joggel

Re: "Inseln" im Dreiecksmesh finden

Beitrag von joggel »

Sind Dreiecke die nur einen Vertex gemeinsam haben benachbart?
Nicht nur. Auch Dreiecke sind benachbart, deren Vertices "gleich" sind.
Es können also 2 Dreiecke benachbart sein, die keine gemeinsamen Vertices haben; also jedes Dreieck hat seine eigenen Vertices.

Ich weiß nämlich nicht woher die Meshes kommen, und wer die gemacht hat...also muss ich davon ausgehen, dass es Dreiecke gibt, die zB keine gemeinsamen Vertices haben :P

Und ich benutze kein Triangle_Fan oder-Strip. Einfach nur einzelne Triangles. Ich weiß, es nicht die performanteste Art das Mesh zu rendern, aber ich denke ich kann das in diesem Anwendungsfall ignorieren
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: "Inseln" im Dreiecksmesh finden

Beitrag von Jonathan »

joggel hat geschrieben: 12.10.2021, 18:08
Sind Dreiecke die nur einen Vertex gemeinsam haben benachbart?
Nicht nur. Auch Dreiecke sind benachbart, deren Vertices "gleich" sind.
Es können also 2 Dreiecke benachbart sein, die keine gemeinsamen Vertices haben; also jedes Dreieck hat seine eigenen Vertices.
Ok, ich glaube dann müsste man zunächst Vertices die nahezu identisch sind zusammenlegen, und danach diese Nachbarschaftsanalyse durchführen. Das hört sich für mich nach dem Nearest neighbor Problem an:

https://en.wikipedia.org/wiki/Nearest_neighbor_search

d.h. du musst für jeden Vertex prüfen, ob es einen anderen Vertex gibt, der näher als x-Einheiten entfernt ist (bei Fließkommazahlen sollte man ja immer mit Toleranzen arbeiten), und die dann entsprechend kombinieren.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
joggel

Re: "Inseln" im Dreiecksmesh finden

Beitrag von joggel »

@Jonathan
Wie heißt denn die Funktionalität bei Blender die das machen würde?
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: "Inseln" im Dreiecksmesh finden

Beitrag von Jonathan »

joggel hat geschrieben: 12.10.2021, 18:27 @Jonathan
Wie heißt denn die Funktionalität bei Blender die das machen würde?
"Remove Doubles". Da kann man auch entsprechend eine Toleranz einstellen. Oh, ich sehe gerade: https://blender.stackexchange.com/quest ... y-distance

Aber an diesem Punkt würde ich so langsam gucken, ob es nicht eine nette Mesh-Bibliothek gibt, die das alles kann.Ich meine, wir sind ja jetzt schon irgendwie bei 3 Algorithmen die man nacheinander ausführen muss (Duplikate entfernen, Nachbarn finden, Inseln finden), das will man ja vlt. nicht alles selber machen.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
joggel

Re: "Inseln" im Dreiecksmesh finden

Beitrag von joggel »

Danke für die Ideen und Links.
Ich werde mir mal Gedanken machen wie ich das am besten umsetze...

Doppelte Vertices kann ich ja eigentlich beim Laden schon entfernen, was allgemein schon mal keine schlechte Idee wäre
EyDu
Establishment
Beiträge: 100
Registriert: 24.08.2002, 18:52
Wohnort: Berlin
Kontaktdaten:

Re: "Inseln" im Dreiecksmesh finden

Beitrag von EyDu »

Vielleicht etwas spät, aber möglicherweise hilft es ja noch. Das ganze ist eigentlich ein ganz klassisches Problem aus der Graphentheorie, der Begriff "Component" wurde oben ja schon einmal verlinkt. Wenn du eine Bibliiothek suchst, welche das für dich erledigen soll, ist "Connected Components" das richtige Stichwort.

Das Problem wird deutlich einfacher zu verstehen, wenn du das Mesh als Graph interpretierst. Was du dann eigentlich "nur" machen musst, ist aus dem Mesch-Graph den dualen Graphen zu bilden. D.h. Die Dreiecke werden zu Knoten im neuen Graph und die Nachbarschaftsbeziehungen werden zu Kanten zwischen den neuen Knoten. Implizit machst du das ja quasi schon, manchmal muss man sich das nur explizit vor Augen führen.

Auf den resultierenden Graphen kannst du jetzt ein beliebiges Verfahren zur Connected-Components-Analyse werfen. Dann erreichst du auch optimale Komplexität.
Benutzeravatar
Jonathan
Establishment
Beiträge: 2353
Registriert: 04.08.2004, 20:06
Kontaktdaten:

Re: "Inseln" im Dreiecksmesh finden

Beitrag von Jonathan »

EyDu hat geschrieben: 15.10.2021, 11:03 Vielleicht etwas spät, aber möglicherweise hilft es ja noch.
Ich finde, es lohnt sich auch nachdem man ein Problem gelöst hat, es noch besser zu verstehen. Und deine Darstellung ist glaube ich eine sehr nützliche Art über das Problem nachzudenken. Man will ja eigentlich immer nicht nur das Problem ansich lösen, sondern auch etwas dazulernen, d.h. selbst wenn man schon eine funktionierende Lösung hat und die bessere gar nicht mehr implementieren will, kann es nützlich sein, darüber nachzudenken.
Lieber dumm fragen, als dumm bleiben!
https://jonathank.de/games/
Antworten