Dreiecksgitter: Scharfe Kanten finden
-
Die Dreiecke kommen aus einem CAD Programm. Da sollte kein Rauschen passieren.
-
Ich verstehe die Aufgabenstellung nicht. Kannst Du vielleicht mal ein Bild malen?
-
Ich verstehe das so als bräuchtest Du einfach eine Art Nachbarschaftsbeziehung zwischen den Dreiecken in der Triangulierung (z.B. 1 grenzt an 4, 9 und 10). Dann müsstest Du einfach die Normalen der jeweiligen benachbarten Dreiecke anschauen um scharfe Kanten zu erkennen.
-
Jester schrieb:
Ich verstehe die Aufgabenstellung nicht. Kannst Du vielleicht mal ein Bild malen?
So etwa:
http://img829.imageshack.us/img829/4421/examplerx.png
Gegeben habe ich nur das Dreiecksgitter. Nachbarschaften und Normalen kenne ich.
Ich suche jetzt die Umrandungen der beiden blauen und der roten Fläche. Das meine ich mit scharfe Kanten finden. (Kanten ist vielleicht etwas doppeldeutig, weil jedes Dreieck ja auch Kanten hat...) Ich suche nur geschlossene Umrandungen.Anderes Beispiel: Im Falle eines Würfels, dessen Seiten in viele kleine Dreiecke zerlegt sind, möchte ich die Umrandungen von allen sechs Seiten finden. Falls dem Würfel eine Seite fehlt (wie bei einem Karton ohne Deckel) möchte ich entsprechend die Umrandungen von den verbleibenden fünf Seiten finden.
-
Walli schrieb:
Ich verstehe das so als bräuchtest Du einfach eine Art Nachbarschaftsbeziehung zwischen den Dreiecken in der Triangulierung (z.B. 1 grenzt an 4, 9 und 10). Dann müsstest Du einfach die Normalen der jeweiligen benachbarten Dreiecke anschauen um scharfe Kanten zu erkennen.
Das auf jeden Fall. Wobei ich noch nicht so recht weiß, wie man vernünftige Toleranzen wählen soll. Sowas kann in ungünstigen Fällen immer in die Hose gehen.
Deswegen muss da ein Algorithmus zum "scharfe Kanten finden" her, der mit sowas möglichst robust umgehen kann.
-
Mups schrieb:
Das auf jeden Fall. Wobei ich noch nicht so recht weiß, wie man vernünftige Toleranzen wählen soll. Sowas kann in ungünstigen Fällen immer in die Hose gehen.
Deswegen muss da ein Algorithmus zum "scharfe Kanten finden" her, der mit sowas möglichst robust umgehen kann.
Die Frage ist, wie willst du sonst eine "scharfe Kante" definieren, wenn nicht über den Normalen-Unterschied von benachbarten Dreiecken? Man könnte noch überlegen, dass etwas immernoch recht "scharf" ist, wenn über den Verlauf von mehreren kleineren, direkt nebeneinander liegenden Dreiecken, sich die Normale recht stark ändert.
Du suchst also in einer gewissen räumlichen Umgebung nach einem Dreieck, welches eine stark unterschiedliche Normale zum Ausgangsdreieck aufweist.
Also ohne zusätzliche Informationen, sehe ich da keine Möglichkeit, da anders ran zu gehen. Es sei denn, du kannst "scharf" noch anders definieren.
-
ich habe genau so etwas programmiert. Aber erstmal die Masterfrage wofür brauchst du das ?
-
Hallo Mups,
Zwei Dreiecke haben genau dann eine gemeinsame Seite, wenn sie zwei Punkte gemeinsam haben. Findest Du also ein Dreieck, welches ein Punktepaar exklusiv besitzt - d.h kein zweites Dreieck hat diese Punktepaar, so ist das schon mal eine 'harte' Kante. Bzw. schlichtweg das Ende der Fläche (-> aufgeschnittener Würfel).
Findest Du ein zweites Dreieck mit dem Punktepaar, so bestimmst Du den Winkel der beiden Normalen der Dreiecke. Diese Winkel zwischen den Normalen klassifizierst Du dann, d.h. man denke sich ein Raster von vielleicht 5Grad, also 0,5,10,15 Grad usw., und für jedes Intervall addiert man den passenden Winkel zwischen zwei Normalen zweier Dreiecke. Man erhält dann eine Art Histogramm.
In diesem Histogramm sucht man jetzt 'Anhäufungen', die man mit den Mitteln der Bildverarbeitung finden kann. In Deinem Fall reicht es vielleicht aus, eine Schwellwert (Anzahl Kanten pro Raster) festzusetzen. Jeder Rasterpunkt, der oberhalb dieses Schwellwert liegt, ist eine Anhäufung.
Im Falle eines Würfels bekommt man haufenweise Einträge für 0Grad und für 90Grad.
Im besten (allgemeinen) Fall findest Du genau zwei Anhäufungen, nämlich die der 'kleinen' Winkel (z.B. die auf dem Kegelmantel) und die der 'scharfen' Kante (z.B. zwischen Kegelmantel und Kegelgrundfläche).Gruß
Werner
-
Hallo Werner,
der Tipp klingt sehr gut. Leicht modifiziert habe ich das eben ausprobiert. Statt der Winkel nehme ich den Cosinus des Winkels. Für den Würfel kommt genau ein Histogramm mit zwei Peaks an den Enden heraus. Für mein anderes Beispiel sieht man sehr schön, dass ca. 99% der Kanten keine "scharfen" Kanten sind. das restliche Prozent ist leider ziemlich über das Histogramm verschmiert. Aber damit komme ich bestimmt schon etwas weiter.
ich habe genau so etwas programmiert. Aber erstmal die Masterfrage wofür brauchst du das ?
Natürlich um Teilflächen einer durch ein Dreiecksgitter beschrieben Fläche zu identifizieren
Ich möchte auf das gegebene Gitter ein neues mit anderen Eigenschaften draufsetzen. Der Algorithmus, den ich habe, erkennt aber keine Kanten und macht diese "rund". Idee: Stecke in den Gittergenerierer nur die Teilfächen, dann sieht er keine Kanten mehr, die rund gemacht werden könnten.
-
und was macht man mit deiner Software?
-
Anderes Beispiel: Im Falle eines Würfels, dessen Seiten in viele kleine Dreiecke zerlegt sind, möchte ich die Umrandungen von allen sechs Seiten finden. Falls dem Würfel eine Seite fehlt (wie bei einem Karton ohne Deckel) möchte ich entsprechend die Umrandungen von den verbleibenden fünf Seiten finden.
Harte Diskontinuitäten:
-
Wenn du eine Beziehung zwischen Kanten und Dreiecken hast, dann kannst du einfach die Kanten raussuchen an die nur ein Dreieck angrenzt.
-
Wenn du Nachbarschaftsbeziehungen zwischen Dreiecken hast (z.B. "Dreieck 17 hat als Nachbarn die Dreiecke 3,5 und 78", dann such einfach die Dreiekce mit weniger als 3 Nachbarn.
scharfe Kanten:
Normalen von benachbarten Dreiecken vergleichen. Wenn diese oberhalb eines Schwellwerts liegen (z.B. 90°) hast du eine scharfe Kante.Achtung: das funktioniert nicht unbedingt bei sehr kleinen Dreicken. Denn hier kannst du den Fall haben, dass viele kleine Dreiecke mit minimaler Normalenabweichung aneinander hängen - aber im makroskopischen Bild dennoch das Ganze wie eine 'scharfe Kante' aussieht.
-
