Also ich stehe gerade vor dem Problem, dass ich einen halbwegs schnellen Inside-Test für ein geschlossenes Dreiecksmesh machen muss. Das Mesh ist außerdem auch 2-mannigfaltig. Desweiteren ist das Mesh nicht zwangsläufig konvex.
=> Kurze Erklärung für Laien: Für jeden Punkt kann man eindeutig angeben, ob er sich innerhalb oder außerhalb des Meshes befindet. Außerdem besitzt das Mesh keine aufgesetzten Teile, genauer gesagt: Jede Kante besitzt genau zwei adjazente Faces. Stelle dir als Beispiel einen Donut (=Torus) vor.

Was ich nun also testen will ist ob sich ein Punkt P innerhalb oder außerhalb befindet. Üblicherweise geht man einfach so vor, dass man ausgehend vom gegebenen Punkt P einen Strahl in eine beliebige Richtung schießt. Dabei zählt man wie oft der Strahl Dreiecke die Oberfläche des Meshes schneidet. Ist diese Zahl gerade befindet man sich außerhalb des Meshes, ist die Zahl ungerade befindet man sich innerhalb. Soweit so einfach, wobei man natürlich eine Baumstruktur benötigt um den Strahl schnell mit allen Dreiecken zu schneiden.

Das Problem sind die Spezialfälle, von denen ich alle bis auf den letzten im Griff habe:
1. Strahl trifft genau eine Kante: trifft also zwei Dreiecke im selben Punkt
2. Strahl trifft genau einen Vertex: trifft also mehrere Dreiecke im selben Punkt
3. Strahl läuft genau parallel zu einem Dreieck

In den Fällen 1. und 2. darf der Treffer nur einmal gezählt werden. Ich habe das so gelöst, dass ich einfach eine Liste aller Entfernungen der Treffer von Punkt P erstelle. Diese Liste wird zunächst sortiert. Alle Treffer die näher als z.B. 0.00001 zusammen sind werden als ein Treffer gezählt.

Die eigentliche Frage ist nun was im Fall 3. zu tun ist. Im Moment habe ich einfach eine total krumme Richtung gewählt (z.B. 0.101, 0.91352, -0.5411), so dass die Wahrscheinlichkeit ziemlich gering ist das Strahlrichtung und Dreieck parallel sind.

Hat jemand eine tolle Idee wie man das auf simple Art lösen kann?

_________________
Yeah!

Ich kenn mich vielleicht nicht so richtig damit aus, aber ich würde parallele Dreiecke garnicht mit zählen. Es gibt ja nur die Möglichkeiten das der Strahl das Dreieck garnicht oder unendlich mal schneidet. Und das der Punkt genau auf der Ebene ist, tritt fast nie auf (gemessen an der Anzahl der möglichen Positionen).
Das hätte dann denke ich den Effekt, das Punkte auf einem Dreieck nicht innerhalb des Meshs sind.

Oder betrifft dein Problem Ungenauigkeiten in der Berechnung? Zu bestimmen wann der Strahl parallel ist sollte ja nicht das Problem sein.

ein kleines Bildchen zur Verdeutlichung. Würde ich das zum Strahl parallel liegende Dreieck ignorieren, hätte ich in beiden Fällen zwei Treffer, nämlich Kanten (oder Vertex) Treffer des Dreiecks darunter und des Dreiecks darüber.

Desweiteren ist es nicht so einfach festzustellen ob Dreieck und Strahl parallel sind. Wegen Rundungsfehlern muss immer ein Epsilon (kleine Zahl, z.B. 0.00001) berücksichtigt werden.

_________________
Yeah!

Hm, ok, jetzt versteh ich das auch. Die Rundungsfehler hat man ja irgendwie immer.

Wie wärs so: Man kann 2 Schnittpunkte zusammenziehen, wenn die dazugehörigen Dreiecke über eine Reihe von parallelen Dreiecken miteinander verbunden sind und der zu testende Punkt bei beiden Dreiecken auf der selben Seite (davor oder dahinter, z.B innen oder außen) liegt.

Also das ist jetzt kein Gesetz oder eine Regel, nur Pseudocode. D.h. es muss nicht funktionieren, weil ich mir das jetzt auch nur so auf die schnelle überlegt hab.
Und dass das simpel ist, bezweifel ich auch. Um zu bestimmen ob ein Dreieck parallel ist muss man dann eben, wie du schon sagtest, ein bischen großzügig sein.

Das Problem ist wohl, dass ich die Dreiecke unabhängig voneinander betrachte. Ich habe keine Information über eventuelle Nachbardreiecke. Das macht es ziemlich schwer da irgendwelche Punkte zusammenzufassen.

Idee: Könnte man vielleicht Ein- und Austritte zählen? Die Vertices sind alle im Uhrzeigersinn (ggf. auch gegen den Uhrzeigersinn, jedenfalls alle gleich) angeordnet. Also man könnte die Normale berechnen.

Vielleicht

oder sowas?

_________________
Yeah!

Das klingt schonmal nicht schlecht und wäre auch schnell und einfach.
Muss man dann bloß aufpassen, dass nicht Ungenauigkeiten wieder einen Strich durch die Rechnung machen.
z.B. könnte vielleicht der Strahl wenn er auf einem parallelen Dreieck entlang verläuft, 2 angrenzende Dreiecke in der selben Richtung schneiden ohne selbst geschnitten zu werden, weil parallel. Wenn der Punkt dann außerhalb wäre, hätte man zB einen Eintritt und 2 Austritte.