Bestimmen, wenn ein 3D-Punkt innerhalb eines Dreiecks
Gegeben ein 3D-Punkt (x, y & z) und ein Dreieck aus drei anderen 3D-Punkte, wie kann ich feststellen, ob der Punkt im Dreieck?
Ich habe viel gelesen, über das tun dies in 2D, die sehr hilfreich sein http://imusthaveit.spaces.live.com/blog/cns!B5212D3C9F7D8093!410.Eintrag, aber ich bin kämpfen, um Sie zu bewegen, das Konzept zu 3D - könnte mir jemand helfen, entweder das Allgemeine Konzept oder ein code Beispiel?
Letztlich das, was ich bin zu wollen tun ist, erhalten Sie eine Liste der Punkte, die darstellen können, ist das innere des Dreiecks.
Können Sie uns etwas mehr Details darüber, warum Sie möchten, dass die Liste der Punkt - nach all es ist eine theoretisch unendliche Liste
Ich habe eine facettierte Darstellung eines 3D-solid, was ich versuche zu tun, ist für jede Facette in einem 3D-Gitter-Struktur (ein grundlegendes voxel-Darstellung). Um dies zu tun, ich muss in der Lage sein, zur Darstellung der Facetten (Dreiecke) als einen Satz von Datenpunkten (für meine gegebene Repräsentation,...)
Könnten Sie das näher erläutern? Sie entweder wollen, um zu sehen, ob ein Punkt auf einer dreieckigen Ebene, oder wenn der Punkt innerhalb einer Pyramide. Richtig?
Ich habe eine facettierte Darstellung eines 3D-solid, was ich versuche zu tun, ist für jede Facette in einem 3D-Gitter-Struktur (ein grundlegendes voxel-Darstellung). Um dies zu tun, ich muss in der Lage sein, zur Darstellung der Facetten (Dreiecke) als einen Satz von Datenpunkten (für meine gegebene Repräsentation,...)
Könnten Sie das näher erläutern? Sie entweder wollen, um zu sehen, ob ein Punkt auf einer dreieckigen Ebene, oder wenn der Punkt innerhalb einer Pyramide. Richtig?
InformationsquelleAutor | 2009-06-15
Du musst angemeldet sein, um einen Kommentar abzugeben.
Sind Sie wirklich reden über die 3 Punkte eines Dreiecks oder 4 Punkte einer Pyramide?
Einem einzigen Punkt ist äußerst unwahrscheinlich, dass jemals genau werden auf der Ebene eines flachen Dreiecks in einem 3d Raum.
EDIT:
Als Idee für die Dreieck-version, wie es scheint, Sie wollen). Sie erfüllen könnten, 3x2D überprüft. Verwerfen der Z-cooridinates aus Ihren check point und die drei Dreieck-Punkte, dann sehen, wenn der Punkt in der Ebene, mit Ihren vorhandenen Methode. Dann tun Sie das gleiche Missachtung nur die X-Koordinate und dann wieder eine Missachtung gerade der Y-Koordinate. Ich bin mir sicher, dass es nicht die effizienteste Methode, aber es wird einfach zu code.
Bearbeitet mit einer Idee, aber nicht effizient.
Die 2D-Projekte-Idee wird nicht funktionieren. In Blender könnte ich einfach ein Dreieck und einen Punkt (eine kleine Kugel), wo der Punkt wird in der traingle in allen drei x -, y -, z-Projektionen, sondern in eine Allgemeine Ansicht, ist eindeutig nicht in der Ebene des Dreiecks.
Ich meinte "Projektionen", nicht "Projekte", duh.
InformationsquelleAutor Robin Day
Gegebenen Punkt P und das Dreieck A, B, C, berechnen:
(Holen Sie sich die richtige Reihenfolge!)
Denken Sie jetzt an die dot-Produkt N1*N2. wenn P in der Ebene des Dreiecks, und innerhalb der drei Seiten, die diesen normalen parallel sein sollten, so ist dieses Skalarprodukt wird 1.0000 (oder 0.999...). Wenn P gehalten wird, das Flugzeug aber bewegt über die Seite BC, die beiden normalenvektoren entgegengesetzt: N1*N2==-1. Wenn P nicht in der Ebene, das Skalarprodukt wird einige Zwischenwert. Hoppla, wir haben noch eine Lücke, die - wenn P geht in die Vergangenheit Seite CA. Wir brauchen zur Berechnung noch mal:
Machen diese beiden tests (in einer idealen Welt):
(Prüfung N3*N1 redundant ist) natürlich ist die Prüfung zu ermöglichen, einige slop für die Unvollkommenheiten der computer-Arithmetik. Suchen (N1*N2 > 1-epsilon), wo der epsilon ist etwas kleiner der Wert, je nach benötigter Genauigkeit und floating-point-Typen.
Möglicherweise benötigen Sie die Formel für diese Einheit normalen. Gegeben (A,B,C) berechnen Sie das Kreuzprodukt N =(B-A)x(C-B). Dann teilen durch sqrt(N*N). Definitionen von "Punkt-Produkt" und "Kreuzprodukt" sind leicht zu finden in Lehrbüchern und wikipedia etc. Es ist möglich, um die Leistung zu erhöhen, mit einigen algebra zu über Quadratwurzeln.
Ich nicht behaupten, das ist der Schnellste Algorithmus, aber sollte funktionieren (bis
InformationsquelleAutor DarenW
InformationsquelleAutor omid
Beschriebene Methode hier ist sehr gut für den 2D-Fall. Ich denke, es ist möglich, dies zu ändern, in 3D zu arbeiten. Diese nicht direkt auf Ihre Frage zu beantworten, aber wenn Sie verstehen, diese Methode sollten Sie in der Lage sein, um herauszufinden, wie es zu ändern für 3D (wenn das möglich ist).
Tolle Referenz! Das hilft mir viel.
InformationsquelleAutor David Johnstone
Guter Punkt. Das wäre Punkt 3. Aber ich würde vorschlagen, dass die erste Phase, die ich beschrieben, beseitigen eine Menge von Fällen.
InformationsquelleAutor PaulJWilliams
Gegeben ein 3D-Punkt P und die drei vertices eines Dreiecks T1, T2, T3
Nun können Sie verwandeln alle Punkte der 2D-problem zu finden, einen Punkt im Dreieck.
Auch der Abstand von P zur Ebene wird Ihnen sagen, wie nahe der Punkt ist genau auf das Dreieck.
Wenn ich verstehe deine Ausarbeitung richtig, Sie planen zu prüfen, alle voxels im 3D-raster, um herauszufinden, ob Sie in einem gegebenen Dreieck? Das wäre sehr ineffizient - ich denke, eine 3D-version von Bresenham ' s line algorithm kann arbeiten für das, was Sie tun möchten. Es wäre trivial zu finden, die voxel, die T1 ist, dann wird durch den Fortschritt des voxels in Richtung T2, Wiederholung für T3 und zurück zu T1.
InformationsquelleAutor danio
Nur meine Beobachtungen, die für eine Verbesserung auf diesem (alten) Beitrag.
Wenn Sie (vor-) Berechnung des U&V-Vektoren für das Dreieck (U wird der Vektor von A nach B und V wird der Vektor von A nach C in einem standard-Dreieck A-B-C, die beide U und V sind nicht unbedingt Einheit der Länge), dann wird der Vektor P (von A nach dem Punkt) benutzt werden können in der folgenden Weise: berechnen Skalarprodukt von P mit U und P mit V. Wenn beide Punkt-Produkte sind weniger (oder gleich für Punkt auf Kante) auf eine, sondern größer (oder gleich) null und Ihre Summe ist kleiner als (oder gleich) eins , dann ist der Punkt innerhalb, sonst außerhalb. Dieser Ansatz ist effizienter, als zunächst ein Vergleich zwischen der normalen (cross) und dann auch den Punkt Produkte.
Dieser Ansatz verlangt nicht, dass das die Punkte sind in der Tat bereits in der Reihenfolge, in form einer rechtshändigen Dreieck und als solche mehr stabil. Was es erfordert, ist, dass der Punkt liegt in der Ebene (oder nahe dran) damit Sie in etwa richtig.
InformationsquelleAutor Solveering