Algorithmus für die Bestimmung, ob ein Punkt in einem 3D-mesh
Was ist ein schneller Algorithmus für die Bestimmung, ob ein Punkt in einem 3D-mesh? Einfachheit halber können Sie davon ausgehen das Netz ist alle Dreiecke und hat keine Löcher.
Was ich bisher wissen ist, dass eine populäre Weise zu bestimmen, ob oder nicht ein Strahl überquert hat eine Masche ist, um die Anzahl der Strahl/Dreieck-Kreuzungen. Muss es schnell gehen, weil ich es mit einer haptischen medizinische simulation. So kann ich nicht testen aller Dreiecke für ray-Kreuzung. Ich brauche eine Art von hashing-oder Baum-Datenstruktur, die zum speichern der Dreiecke in zu helfen, festzustellen, welches Dreieck relevant sind.
Weiß ich auch, dass wenn ich eine beliebige 2D-Projektion der Eckpunkte, eine einfache point/triangle intersection test ist alle notwendigen. Allerdings würd ich noch brauchen, um zu wissen, welche Dreiecke sind relevant, und, zusätzlich, die Dreiecke liegen in front of a der Punkt, und nur diese testen Dreiecke.
InformationsquelleAutor der Frage Jeff Jenkins | 2011-07-02
Du musst angemeldet sein, um einen Kommentar abzugeben.
Löste ich mein eigenes problem. Im Grunde nehme ich eine beliebige 2D-Projektion (werfen eine der Koordinaten), und hash, die AABBs (Axis Aligned Bounding Boxes) der Dreiecke zu einem 2D-array. (Ein 3D-Würfel wie erwähnt von titus ist übertrieben, denn es gibt nur einen Konstanten Faktor erhöht.) Verwenden Sie das 2D-array und 2D-Projektion von der Stelle, die Sie auf testen, um eine kleine Menge von Dreiecken, die Sie tun, eine 3D-ray/triangle intersection test auf (siehe Die Schnittpunkte der Strahlen, die, Segmente, Ebenen und Dreiecke in 3D), und die Anzahl der Dreiecke, die ray-Kreuzung, wo die z-Koordinaten (die Koordinate geworfen) größer ist als der z-Koordinate des Punkts. Eine gerade Anzahl von Schnittpunkten, d.h. es ist außerhalb der Gitter. Eine ungerade Anzahl von Kreuzungen bedeutet, es ist innerhalb des mesh. Diese Methode ist nicht nur schnell, sondern sehr einfach zu implementieren (was genau das ist, was ich suchte).
InformationsquelleAutor der Antwort Jeff Jenkins
Dies ist der Algorithmus effizient ist, nur, wenn Sie viele Abfragen zu rechtfertigen, die Zeit für den Aufbau der Datenstruktur.
Teilen den Raum in Würfel von gleicher Größe (wir werden herausfinden, die Größe später). Für jede cube-weiß, die Dreiecke, die mindestens einen Punkt. Wirf die Würfel, die nicht alles enthalten. Machen Sie ein ray-casting-Algorithmus vorgestellt wie auf wikipedia, aber statt o testen, wenn die Linie schneidet jedes Dreieck, bekommen alle Würfel, die sich mit der Zeile, und führen Sie dann ray casting nur mit der Dreiecke, die in diesen Würfel. Watch out nicht zu testen, das gleiche Dreieck mehr als einmal da, es ist vorhanden in zwei Würfel.
Das finden der richtigen cube Größe ist schwierig, es sollte nicht sein, weder zu groß oder zu klein. Es kann nur durch Versuch und Irrtum gefunden.
Lassen Sie uns sagen
number of cubesistcundnumber of trianglesistt.Die mittlere Anzahl von Dreiecken in einem cube ist
t/ckist die mittlere Anzahl der Würfel, schneiden Sie die rayline-cube Kreuzungen + line-Dreieck-Kreuzung in die cubes werden minimal
c+k*t/c=minimal=>c=sqrt(t*k)Sie haben zu testen, die Werte für die Größe der Würfel, bis
c=sqrt(t*k)ist wahrEin guter Anfang, denke für die Größe des cube wäre
sqrt(mesh width)Um irgendeine Perspektive für 1M Dreiecke, Sie werde test in der Größenordnung von 1k Kreuzungen
InformationsquelleAutor der Antwort titus
Ray-Triangle Intersection scheint ein guter Algorithmus, wenn es um die Genauigkeit im Sinne dieser Diskussion. Die Wiki hat einige weitere algorithmen. Ich bin Verlinkung hier, aber vielleicht kennt Ihr das schon.
Kann man vielleicht improvisieren, durch die Aufrechterhaltung einer matrix der Beziehung zwischen den Punkten der Ebene an die Sie die Eckpunkte? Dieses Thema scheint ein Thema der Untersuchung in der Wissenschaft. Nicht sicher, wie Sie Sie zum Zugriff auf weitere Diskussionen im Zusammenhang mit diesem.
InformationsquelleAutor der Antwort vpit3833