Hallo,

Nachdem ich die Volumenberechnung hinbekommen habe und auch die Oberfläche eines beliebigen Mesh aus Dreiecksflächen hinbekommen habe, fehlt mir eigentlich noch der Schritt davor, denn zuerst müsste ich meine Meshs auf Geschlossenheit prüfen.

Ich habe jetzt nach viel googeln und lesen gelernt das ein Mesh aus Dreiecken dann als geschlossen gilt, wenn alle Kanten genau zu zwei Flächen existieren.
Existiert eine Kante nur zu einer Fläche, dann ist das eine "offene" Kante.

Soweit die Theorie...

Jetzt die Frage:

Hat zufällig jemand mal irgendwo einen Algorythmus oder Codefetzen gesehen wie man ein Mesh am besten danach durchsucht? Ich hab (mal wieder) mehrere Stunden gegoogelt und gelesen aber nix finden können...
Bei mir liegen die Vertices des Mesh in einem Array of TVertex vor.

Gruß und Danke schonmal.

Wölfchen

Also ein Algo mit einer schlechten durchschnittlichen Dauer (weil Aufwand=n²) wäre doch einfach


Wobei die Beschreibung von dir und mein Code aber MEHRERE geschlossene Meshes zulässt.

LG Ziz

PS: Der neue Highlighterstil ist total depri - scheiß Demokratie -_-

_________________
Denn wer nur schweigt, weil er Konflikte scheut, der macht Sachen, die er hinterher bereut.
Und das ist verkehrt, denn es ist nicht so schwer, jeden Tag zu tun als ob's der letzte wär’.
Und du schaust mich an und fragst ob ich das kann.
Und ich denk, ich werd' mich ändern irgendwann.
_________________Farin Urlaub - Bewegungslos

hmm ja danke erstmal

aber ich hab hier teilweise meshs mit paarhunderttausend triangles... wär schon schön wenns da was schnelleres geben würde...

dann nochwas...
*hust*
also ne Kante AB mit A= (Ax,Ay,Az) und B = (Bx,By,Bz) ist doch (dachte ich) Ax-Bx, Ay-By, Az-Bz...
das würde aber für nen doofen würfel mit Kantenlänge 1 ja ergeben das da ziemlich viele Kanten gleich wären...

Wie ist denn dein Modell gebaut. Können 2 Vertices an der selben stelle existieren, oder gibts an einer Stelle immer nur ein Vertex.
Letzteres wäre einfacher zu händeln.
Dann könntest du mit Idices/Pointer arbeiten und eine Datenstruktur aufbauen wo du leicht nachschauen kannst, welche Kanten existieren und aus welchen Vertices sie bestehen, und in welchen Tris die wiederum benutzt werden.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Die Modelle sind in CAD erstellt und somit ist mit allem zu rechnen... Modelle mit nur einer Haut (offene shells) genauso wie doppelte flächen und was man sonst noch anstellen kann wenn man den 3D malpinsel schwingt.

Allerdings liegen auch "saubere" daten - also darunter verstehe ich hier geschlossene volumen - so vor, das jeder vertice mehrfach vorkommt meine versuche das nachträglich zu reduzieren scheiterten an der normalendarstellung.

Wieso kannst du das nicht reduzieren? Ich meine, wenn du einfach das Modell beim laden in einen Quadtree lädst, und dann Vertices vergleichst die in einem Knoten liegen (und den direkten Nachbarn) dann kannst du alle Vertices die näher als X sind zusammenlegen.

_________________
Blog: kevin-fleischer.de und fbaingermany.com

Also Geschlossenheit ist nicht so leicht zu prüfen wenn du 2 Mannigfaltigkeit nicht voraussetzen kannst. Denn es gilt zwar für ein 2-mannigfaltiges und geschlossenes Mesh, dass jede Kante zu genau zwei Faces adjazent ist, aber diese Aussage gilt nicht umgekehrt.

Siehe auch:
http://wiki.delphigl.com/index.php/Mesh#Eigenschaften

Du solltest dir wirklich überlegen ob du das wirklich testen musst oder ob du dem Nutzer deiner Methode/Funktion lieber im Kommentar mitteilst, dass dies nur für geschlossene 2-mannigfaltige Meshes funktioniert.

_________________
Yeah!

hmm das ist mir jetzt irgendwie zu theoretisch.

nehmen wir doch mal dieses beispiel:


So, das sind nun 3 Dreiecksflächen, die aneinander grenzen.. von den insgesamt 9 Kanten sind 5 offen und 2 sind jeweils identisch.
Und nichts anderes will ich gerne mit einer effizienten Schleife prüfen, ob alle Kanten geschlossen sind und wenn nicht, welche offen sind (nur an eine Fläche grenzen).

Offtopic@Wölfchen: Bitte nicht immer komplette Posts zitieren. Es macht höchstens Sinn einzelne Passagen zu zitieren wenn du direkt darauf Bezug nimmst. Danke.


Ich weiß zwar nicht wozu das gut sein soll, aber gut...also:
Schritt 1: Vertices mergen
Du schreibst etwas von ein "paarhunderttausend triangles", du wirst also auch entsprechend viele Vertices haben. Sind das eher eine Million als Hundertausend Vertices? Wenn das dann noch wirklich effizient sein soll, du also weniger als quadratische Laufzeit (O(n^2)) für diesen Schritt haben möchtest brauchst du eine räumliche Datenstruktur. Damit ließe sich eine Laufzeit von O(n * log n) erreichen. Als Datenstruktur eignet sich beispielsweise ein Octree, ein Gridfile oder auch ein R-Baum. Der Octree ist vergleichsweise leicht und müsste auch im Wiki beschrieben sein. Die beiden anderen Methoden sind komplizierter zu implementieren.

Dies ist aber das Einsteiger-Forum daher empfehle ich dir die Variante ohne Datenstruktur.
Ich schreibe das mal als Pseudocode in C-Syntax, wenn was unklar ist einfach Fragen.



Schritt 2: identische Kanten zählen
Dies ist der aufwendigere Schritt, da es deutlich mehr Kanten als Vertices gibt (*). Habe gerade schon 30min am obigen Code gebastelt, ich bin da gerade zu faul zu. Hier darf sich jemand anderes austoben
Auf keinen Fall sollte ein Array über alle möglichen Kanten angelegt werden, den das sind quadratisch viele. Die Idee wäre eine HashMap (TreeMap ginge genauso) zu benutzen um Kanten auf ein Bool zu mappen. Dabei steht "false" für offene Kante und "true" für geschlossen. Also man geht alle Kanten durch und fügt sie in die HashMap ein. Wenn die Kante schon drin ist und der Bool "false" ist wird auf "true" gesetzt. Ist der Wert schon "true" ist was faul, also eine Kante mit drei Dreiecken.
Am Ende gehst du nochmal die HashMap durch und guckst ob es noch Werte mit "false", also offene Kanten gibt.

(*) ungefähr dreimal so viele bei einem geschlossenen 2-mannigfaltigen Mesh mit vernachlässigbarem Genus, siehe Mesh.

_________________
Yeah!

huhu,

danke für die Zeit die du dir da genommen hast - ich habe mir jetzt eine krücke gebastelt die fürs erste ausreicht. Ich baller alle kanten in eine sortierte stringlist, laufe dann noch einmal durch diese durch und zähle ob es kanten gibt die weniger oder öfter als 2 mal vorkommen.

Das ist bei > 500 000 flächen dann zwar schon sehr zäh (zwischen 25 und 45 sekunden) aber 95% meiner teile haben max 100 000 flächen und da gehts noch mit 0-3 sekunden, erträglich zu. Zumal der pc hier an dem ich das gestoppt habe eh nicht der schnellste ist.

den punkt schau ich mir aber sicherlich bei gelegenheit (wenn ich auch noch bissi mehr C kenne und so) nochmal an.

*EDIT - 31.01.2010*

Ich habe das Verfahren zwar grundsätzlich beibehalten aber ich gehe nun nicht mehr den Umweg über eine Stringlist sondern habe alles in einem array, das ich sortiere und danach zähle wie oft was eine Kante vorkommt. Das hat die Rechenzeit selbst bei den größten Testmodellen in Bereiche unter 2 Sekunden gebracht (von ehemals 45 Sekunden) was absolut in Ordnung ist für meine Zwecke.