Wykrywanie kolizji trójkątów do trójkątów w 3D

Rozumiem, że trójkąt wykrywa kolizję trójkątną między 2 trójkątami. Czy ktoś może wyjaśnić, w jaki sposób mogę użyć tego obiektu 3D złożonego z 1000 wierzchołków? Jak utworzyć listę trójkątów dla każdej siatki? Czy muszę wziąć każdą permutację wierzchołków? To mogłoby doprowadzić do O (n^3), które uważam za bardzo złe.Wykrywanie kolizji trójkątów do trójkątów w 3D

Jak mogę to uogólnić?

Będę wymagał odczytania danych z formatu. Jeśli wszystko inne zawiedzie, czy ktoś może zaproponować format, który sprawia, że Siatka z trójkątów? Potrzebowałbym również katalogu siatek dla tego formatu, przynajmniej na początek.

Dziękuję bardzo.

Źródło

2011-01-13 Iustin

Jest w to wiele pytań i wszystkie powinny być zadawane osobno, zamiast ułożyć w jedno pytanie. Zazwyczaj "obiekt 3D", z którym mógłbyś pracować, to nie tylko chmura punktów (http://en.wikipedia.org/wiki/Point_cloud), zazwyczaj jest to [wielobokowa siatka] (http: //en.wikipedia.org/wiki/Polygon_mesh) i/lub zestaw krzywych 3D. Jeśli naprawdę zaczynasz od chmury punktów, możesz chcieć sprawdzić algorytmy, które są zaprojektowane do tworzenia siatek wieloboków z chmur punktów, zanim zaczniesz pracować nad wykrywaniem siatek-> nakładanie siatek. –

Gdy masz już siatkę wieloboków, zacznij stosować optymalizacje, o których rozmawiają Gareth/James, aby uniknąć porównania każdego trójkąta w jednej siatce z każdym trójkątem w drugiej siatce. To nigdy nie będzie dotyczyć każdego * możliwego * trójkąta, który mógłby zostać utworzony ze wszystkich wierzchołków każdej siatki, jak wydaje się to sugerować twoje pytanie. Ale każdy trójkąt w siatce -> każdy trójkąt w drugiej siatce jest wciąż powolny, dlatego optymalizujesz dalej :) –

http://en.wikipedia.org/wiki/Binary_space_partitioning

Drzewo BSP jest bardzo skutecznym sposobem na sprawdzenie kolizji oczek statycznych, ale to wymaga trochę wstępne przetwarzanie z siatki, aby upewnić się żadne trójkąty przecinają. Działa, dzieląc siatkę na półprzestrzeń. Dzięki temu sprawdzenie kolizji i fizyka są łatwiejsze.

EDIT:

czuję jakby Należy również wspomnieć o Octree. Taki sam ogólny pomysł jak drzewo BSP, ale dzieli model na rekurencyjnie mniejsze sześciany zamiast półprzestrzeni.

http://en.wikipedia.org/wiki/Octree

W odpowiedzi na drugie pytanie, coś w formacie .obj może być to, czego szukasz.

http://en.wikipedia.org/wiki/Wavefront_.obj_file

Źródło

2011-01-13 15:24:23 James

Istnieje wiele optymalizacje można zastosować do wykrywania kolizji pomiędzy oczkami:

Kosmicznej partycjonowanie, jak opisał James.
Wcześniejsze odrzucenie za pomocą bounding volumes. Na przykład zderzenie kuli z kulą jest tanie, więc przed sprawdzeniem, czy zderzają się siatki A i B, możesz zobaczyć, czy kula otaczająca A zderza się z kulą otaczającą B. Jeśli sfera nie trafi, oczywiście siatka nie może się zderzyć, więc nie trzeba je przetestować. Różne rodzaje obiektów mogą wymagać różnych rodzajów objętości ograniczających: prostopadłe prostopadłościany i cylindry są wspólne.
Buforowanie świadków. W niektórych testach kolizyjnych kończy się obliczanie "świadka" kolizji, na przykład przy zastosowaniu separating axis test oblicza się oś oddzielającą. Jeśli oś oddziela dwa obiekty w czasie t, prawdopodobnie nadal będzie je rozdzielać w czasie t + δ, więc może zapłacić za buforowanie znalezionej osi i wypróbować ją po raz pierwszy (patrz Rabbitz, "Szybko Wykrywanie kolizji ruchomych wypukłych Polyhedra "w Graphics Gems IV).

Źródło

2011-01-17 16:17:00

Wykrywanie kolizji trójkątów do trójkątów w 3D

Odpowiedz

Powiązane problemy