Jak sprawdzić, czy obiekt 3D pasuje do innego obiektu 3D (kontenera)?

Question

Biorąc pod uwagę dwa obiekty 3D, jak znaleźć, czy pasuje do wnętrza drugiego (i znaleźć położenie obiektu w pojemniku).

Obiekt powinien zostać przetłumaczony i obrócony, aby zmieścił się w pojemniku, ale w przeciwnym razie nie został zmodyfikowany.

Dodatkowe komplikacje:

1. Taka sama sytuacja - ale wygląda na najlepsze rozwiązanie pasuje, nawet jeśli nie jest to właściwa mecz (zminimalizować wielkość obiektu, który nie mieści się w kontenerze)

2. Wsparcie dla elastycznych obiektów - znaleźć najlepsze dopasowanie, jednocześnie minimalizując zniekształcenia „” w obiektach

jest to dość ogólne pytanie - i nie oczekuję kompletnego rozwiązania. Wszelkie wskazówki do odpowiednich artykułów \ articles \ bibliotek \ tools byłyby użyteczne

Answer 1

Oto jedna z może mniej idealnych metod.

Możesz spróbować naprawić pozycję (w przestrzeni 3D) o 1 kształcie. Umieszczanie drugiego kształtu na tym kształcie. Następnie utwórz łącza łączące jeden punkt w kształcie z punktem w innym kształcie. Następnie zasymuluj, co dzieje się, gdy linki są równie ciasno przyciągane. Powoduje, że punkt, który nie jest nieruchomy, obraca się i tłumaczy, dopóki nie jest stabilny.

Jeśli dopasowanie jest wystarczająco luźne, można użyć tylko 3 ogniwa (minimalna liczba odsyłaczy do 3D) i wypróbować każdą możliwą kombinację. Jednak, aby uzyskać mocniejsze pasowania, potrzebujesz więcej linków, być może wystarczy, aby umieścić je na każdym punkcie kształtu z najmniejszą liczbą punktów. Co oznacza, że ​​będziesz miał jakąś metodę ustalenia, jak umieścić linki, co nie jest banalne.

Answer 2

To wydaje się dość trudnym problemem. Podejściem prawdopodobnym jest posiadanie heurystyki sugerującej transformację, a sprawdzenie jest dobre. Jeśli transformacja przesuwa obiekt tylko nieznacznie poza jego wnętrze (np. Na jedną część), należy wykonać nieznaczne dostosowanie do transformacji i przetestować ją. Jeśli obiekt jest "lotem" (np. Na tej samej/całej osi po obu stronach), należy dokonać nowego heurystycznego zgadnięcia.

Po prostu ogólny pomysł na heurystykę. Zrób rasteryzację obiektów o tym samym rozmiarze piksela. Może to być ósemka objętości obiektu. Utwórz wykres łączności między pikselami. Sprawdź izomorfizm subgraph między wykresami. Jeśli istnieje podgraf, to ta pozycja jest przeznaczona do testowania.

Podejście to obsługuje również obrót o 90 stopni.

Niektóre testy można wykonać nawet na wykresach. Jeśli wszyscy sąsiadów wolumenu w podgraphie znajdują się w większym grafie, niż obiekt jest w nim.

Ogólnie rzecz biorąc jest to podejście "dopracowane".

Answer 3

Innym rozwiązaniem jest wyświetlenie równej liczby punktów na obu obiektach i wykonanie najmniejszych kwadratów najlepiej pasujących do zestawów punktów. Zestawy punktów najprawdopodobniej nie zostaną uporządkowane tak samo, dlatego iteracja między najmniejszymi kwadratami, które najlepiej pasują, i zmiana kolejności punktów, tak aby punkty na obu obiektach były zbliżone do tej samej kolejności. Rozwój tego równania to dużo algebry, ale nie koncepcyjnie skomplikowane.

Answer 4

Rozpatrz jeden wielokąt (trójkąt) w obiekcie docelowym. W przypadku tego wielokąta znajdź równoważny wielokąt w drugiej geometrii (źródło), tj.długość boków, kąt pomiędzy krawędziami, powierzchnia powinna być taka sama. Jeśli jest tylko jeden odpowiednik, znajdź sztywną macierz transformacji, która zmieni wierzchołki w ten sposób: X' = M*X. Ponieważ X' AND X są znane ze wszystkich punktów na dopasowanych wielokątach, powinno to być możliwe do wykonania za pomocą algebry liniowej.

Jeśli chcesz odwzorować jeden-jeden między wierzchołkami wielokąta, przesuwaj krawędzie wielokątów w tej samej kolejności i stwórz tabelę odnośników, która mapuje każdy wierzchołek jeden do drugiego w kierunku wierzchołka. Jeśli masz obiekt 3d, który znacznie uprości ten proces.

Jeśli znajdziesz więcej niż jeden pasujący wielokąt, przesuń wielokąt źródłowy z obu punktów i dopasuj do siebie sąsiednie wielokąty z docelowymi wielokątami. Kontynuuj, aż jeden z nich się zepsuje, po czym możesz wykonać te same kroki, co w wersji jednoprzebiegowej.

Istnieją poważniejsze rozwiązania, które są wymienione here, ale myślę, że powyższa metoda również będzie działać.