Algorytm określania, czy punkt znajduje się wewnątrz siatki 3D

Question

Algorytm określania, czy punkt znajduje się wewnątrz siatki 3D

Jaki jest szybki algorytm do określania, czy punkt znajduje się w siatce 3D? Dla uproszczenia można założyć, że siatka ma wszystkie trójkąty i nie ma dziur.

Wiem, że jednym z popularnych sposobów określenia, czy promień przekroczył siatkę, jest policzenie liczby przecięć promieni / trójkątów. Musi być szybki, ponieważ używam go do symulacji medycznej. Więc nie mogę sprawdzić wszystkich trójkątów na przecięcie promieni. Potrzebuję trochę. rodzaj hashowania lub struktury danych drzewa do przechowywania trójkątów w celu określenia, które Trójkąty są istotne.

Również, Wiem, że jeśli mam dowolny rzut 2D wierzchołków, prosty punkt / Trójkąt test przecięcia jest konieczne. Jednak nadal musiałbym wiedzieć, które Trójkąty są istotne, a ponadto, które Trójkąty leżą przed punktem i tylko testować te Trójkąty.

20

algorithm intersection mesh point

Author: Olivier Moindrot, 2011-07-02

Source

3 answers

Jest to algorytm efektywny tylko wtedy, gdy masz wiele zapytań uzasadniających czas na zbudowanie struktury danych.

Podziel przestrzeń na sześciany o jednakowej wielkości(Rozmiar dowiemy się później). Dla każdego sześcianu wiedzieć, które Trójkąty ma przynajmniej punkt w nim. Wyrzuć kostki, które nie zawierają niczego. Wykonaj algorytm rzutu promieni przedstawiony na Wikipedii, ale zamiast tego o testowanie, czy linia przecina każdy trójkąt, Pobierz wszystkie kostki, które przecinają się z linią, a następnie czy Ray casting tylko z trójkątów w tych kostek. Uważaj, aby nie przetestować tego samego trójkąta więcej niż jeden raz, ponieważ jest on obecny w dwóch kostkach.
Znalezienie odpowiedniego rozmiaru kostki jest trudne, nie powinno być ani Duże, ani zbyt małe. Można go znaleźć tylko metodą prób i błędów. Powiedzmy, że number of cubes jest c i number of triangles jest t.
Średnia liczba trójkątów w sześcianie wynosi t/c
k jest średnią liczbą sześcianów przecinających promień
przecięcia linia-sześcian + przecięcie linia-Trójkąt w tych kostkach musi być minimum
c+k*t/c=minimal => c=sqrt(t*k)
Będziesz musiał przetestować wartości dla wielkości sześcianów, aż c=sqrt(t*k) będzie prawdziwe
Dobry początek zgadywać dla rozmiar sześcian być sqrt(mesh width)
Aby mieć jakąś perspektywę, dla trójkątów 1M przetestujesz NA kolejności przecięć 1k

4

Author: titus,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2011-07-02 02:32:42

Skrzyżowanie trójkąta Ray ' a wydaje się być dobrym algorytmem, jeśli chodzi o dokładność. Wiki ma więcej algorytmów. Łączę to tutaj, ale może już to widziałeś.

Czy możesz, być może improwizować, zachowując macierz relacji między punktami a płaszczyzną, na którą składają się wierzchołki? Temat ten wydaje się być przedmiotem badań w środowisku akademickim. Nie wiem, jak uzyskać dostęp do więcej dyskusji związanych z tym.

0

Author: vpit3833,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/doraprojects.net/template/agent.layouts/content.php on line 54
2019-01-16 07:02:32

score 18 · Accepted Answer

Rozwiązałem swój własny problem. Zasadniczo, biorę dowolny rzut 2D (wyrzucić jedną ze współrzędnych), i hash AABBs (Axis Aligned Bounding Boxes) trójkątów do tablicy 2D. (Zestaw sześcianów 3D, o którym wspomniał titus, jest przesadą, ponieważ daje tylko stały współczynnik przyspieszenia.) Użyj tablicy 2D i projekcji 2D testowanego punktu, aby uzyskać mały zestaw trójkątów, na których wykonujesz test przecięcia promieni/trójkątów 3D (Zobacz przecięcia promieni, segmentów, Płaszczyzny i trójkąty w 3D) i policzyć liczbę trójkątów przecięcia promieni, gdzie współrzędna z (współrzędna wyrzucona) jest większa niż współrzędna z punktu. Parzysta liczba przecięć oznacza, że znajduje się poza siatką. Nieparzysta liczba przecięć oznacza, że znajduje się wewnątrz siatki. Metoda ta jest nie tylko szybka, ale bardzo łatwa do wdrożenia (czego dokładnie Szukałem).