Mam tysiące OOBB (obiektowych ramek ograniczających) w przestrzeni 3d, które obejmują proste wydłużone siatki 3D. Są ciasno spakowani razem.Jak szybko przetestować skrzyżowania promienia z wąską grupą OOBB?
Chciałbym strzelać do nich promienie i dowiedzieć się, które OOBB są trafione. Ze względu na liczbę testów przecięć promieni, które muszę wykonać (miliony), podejście brutalnej siły przeciwko wszystkim OOBB nie będzie wystarczające.
Początkowo myślałem, że byłoby łatwo użyć pewnego rodzaju systemu partycjonowania przestrzennego, aby szybko zawęzić potencjalne wyniki, ale systemy takie jak BVH lub KDTrees polegają na AABB (wyrównane względem osi ramki ograniczające), aby przyspieszyć zapytania, aw moim przypadku te Byłoby to bardzo nieefektywne (ponieważ wiele moich ściśle zapakowanych OOBB ma z grubsza taki sam AABB ze względu na przekątną siatkę, którą obejmują).
Czytałem o OBBTrees w bibliotece RAPID, ale wygląda na to, że są one budowane od góry do dołu (zaczynają się od zupy wielokątnej i dzielą się na coraz mniejsze grupy OOBB w celu utworzenia drzewa), a nie oddolnie (początek z dużą ilością OOBB i buduj z nich drzewo).
Czy są jakieś inne struktury danych, których mogę użyć do przyspieszenia moich testów przecięcia?
Oto zdjęcie moich OOBB. Jak widać, są one szczelnie zapakowane i jeśli możesz sobie wyobrazić, jak będzie wyglądać ich AABB, zobaczysz, że pokrywają się one do punktu, w którym drzewo oparte na AABB nie poprawiłoby wydajności (ponieważ praktycznie wszystkie z nich zostanie trafiony przez promień strzelający przez środek grupy).
Warto zauważyć, że muszę zapytać wszystkie OOBB uderzone przez promień, a nie tylko pierwszy/najbliższy.
spróbuj obrócić promień w przestrzeń, w której większość bbs jest blisko bycia aabbs i używając jakiegoś algorytmu podziału przestrzeni w tej nowej przestrzeni. inne rozwiązanie, które ma zastosowanie, jeśli obiekt nie zmienia się z promienia na promień, z wyjątkiem transformacji liniowej: można również wygenerować tablicę 3D, w której każda komórka ma listę przecinanych trójkątów/oobbystów i krok wzdłuż promienia, mimo że 3D szyk. – programmerjake
Jak dynamiczna jest scena? To znaczy, ile promieni będzie rzucać, dopóki nie zmienią się OOBB i jak drastycznie się zmienią? – Angew
@programmerjake Niestety pierwsza sugestia nie zadziała, ponieważ OOBB nie zawsze będą ładnie wyrównane jak na moim przykładowym obrazie. Druga opcja może być bliższa czegoś, ale problem z pamięcią i prekonfiguracją może być problemem ...Potrzebuję rozwiązania do pracy w bardzo dużych środowiskach 3D, w których matryca 3D nie byłaby możliwa (potrzebowałaby miliardów komórek, aby uwzględnić wszystko przy zachowaniu rozsądnej szczegółowości). Ale dzięki za sugestie. – Tyson