Autor Wątek: Kolizje w praktyce  (Przeczytany 4066 razy)

Offline Grik

  • Użytkownik

# Maj 11, 2007, 20:29:47
Witam!
     Podczas przygotowywania się do kodzenia fizyki pod kątem gier ( może wreszcie kiedyś powstanie ta pierwsza gra :D ) natrafiłem na problem - mianowicie - jak w praktyce zaprogramować detekcję kolizji?
     Przypuszczam, że kolizje trójkąt-trójkąt będą zbyt wolne, ale czy aby na pewno? Jeśli w pierwszej kolejności sprawdzimy kolizje sfera-sfera, zastosujemy uproszczone siatki ( co jest pewnym utrudnieniem ), i podzelimy scenę jakimś drzewkiem to może jednak zdołamy utrzymać rozsądną ilość FPSów?
     A jak sprawa ma się z elipsoidami? Znalazłem w internecie sporo artykułów opisujących kolizje elipsoida-trójkąt, ale nigdzie nie ma kolizji elipsoida-elipsoida. Czemu? ( w zasadzie domyślam się, że obliczenia muszą być kosztowne, ale czy nie można sobie z tym jakoś poradzić? )
     W końcu co myślicie o innych typach kolizji np. cylindry, OBB etc. Co w praktyce stosujecie w swoich grach? I w końcu którą metodę do czego używacie? ( np. przy kolizjach między postaciami cylindry, przy kolizjach postać-ściana elipsoidy itd. )

Pozdrawiam,
     Mateusz -=Grik=- Wieloch

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline ziomber

  • Użytkownik

  • Zbanowany
# Maj 13, 2007, 11:48:41
Gry 2d, kolizje obiektów: trojkat punkt, prostokat-prostokat, piksel-piksel, punkt-punkt
Gry 3d ee tutaj jest za duzo: ale mozna np. zamiast kolizji z drzewami zastosować coś takiego: jak pozycja drzewa to X,Y,Z to my operujemy tylko na X,Z jak odleglosc naszeg gracza w tej plaszczyznie jest równa promieniowi pnia to mamy kolizje :S

maxest

  • Gość
# Maj 13, 2007, 12:17:29
Ja osobiscie na razie wykorzystuje jeden model kolizji - prosta-punkt i plaszczyzna-punkt :).
Odnosnie pierwszego:
Wyznaczasz sobie rownanie prostej, znajdujesz jej wektor normalny. Sprawdzasz czy punkt "przekroczyl" prosta (mozna z nie zrobic sobie oczywiscie odcinek), a jesli tak to stosujemy odpowiedni wzor na "odbicie" punktu od prostej, dzieki czemu mozemy otrzymac plynny ruch punktu wzdluz sciany, ktory obserwujemy w wielu grach :)

Wzor:
v -= ( ( v . n ) / ( n . n ) ) * n

Oznaczenia:
v – wektor prędkości obiektu,
n – wektor normalny ściany.

Offline Grik

  • Użytkownik

# Maj 13, 2007, 13:34:29
     Hehe chyba trochę źle mnie zrozumieliście :)  W tym temacie mam na myśli kolizje w przestrzeni trójwymiarowej - w 2d nie stanowi to dla mnie problemu.
     Dokładniej chodzi mi o to co stosujecie np. w grach FPS - zapewne do detekcji kolizji obiektów pojedyncza sfera nie wystarczy, bo precyzja będzie zdecydowanie zbyt mała. Jak w związku z tym sobie radzicie - którą z metod stosujecie i jak wasz sposób spisuje się w praktyce? Czy stosujecie elipsoidy, AABB, OBB, czy kolizje na uproszczonych modelach, czy może jakieś drzewa sfer dla każdego modelu?

maxest

  • Gość
# Maj 13, 2007, 14:31:01
No wlasnie to co podalem (puntk-prosta) spokojnie mozna zastosowac w 3D :P. Ewentualnie rozszerza sie ten model o plaszczyzne i mozna dostac piekne kolizje :)

Offline Charibo

  • Redaktor

# Maj 13, 2007, 20:29:57
Uzywaj roznych metod - dla postaci mam sfere, bo model "miesci" sie w niej w kazdym polazeniu, dla innych meshy zazwyczaj convex hull albo uproszczona siatka...

Do przechowywania dynamicznych obiektow polecam drzewo kul - opisane ladnie w GPG2

Offline Ocelot

  • Użytkownik
    • Ocelot's Jungle

# Maj 14, 2007, 11:45:47
Poczytaj o możliwościach silników fizycznych (np. ODE, Newton itp) większość oferuje oprócz kolizji trójkąt/trójkąt prymitywy takie jak box, sphere, capsule, cylinder; albo convex hull. Pozatym przetrzeń dzieli się jakimś drzewem i działa to wystarczająco szybko.

PS. jeżeli chodzi o proste kolizje dla graczy/NPC itp. wystarczy elipsoid wsparty ewentualnie raya'ami  ;D

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Maj 14, 2007, 12:32:25
Kolizje robi się na różnych poziomach:

1. Podział przestrzeni, np. BSP, quadtree/octree czy jeszcze coś innego, po to żeby jeśli obiektów jest więcej niż kilka to nie testować w każdej klatce każdego który się porusza z każdym innym który jest na planszy.
2. Kolizja ogólna tego co koliduje (bryła otaczająca obiektu, promień - jeśli to pocisk leci czy też swept sphere - jeśli leci coś większego) z bryłą otaczającą danego obiektu - np. sferą, AABB czy OBB.
3. Kolizja dokładna, jeśli jest potrzebna. Nawet wtedy niekoniecznie musisz testować kolizję z pojedynczymi trójkątmi. To pewnie zależy od rodzaju gry, ale może wystarczy zrobić test z np. AABB otaczającym daną część modelu - rękę czy nogę.

Offline Haxy.M

  • Użytkownik

# Czerwiec 10, 2007, 15:05:56
Sorry, że się tak wtrącam, ale mam taką srawę:

Mam dość złożony model w OpenGL'u przeczytany z pliku 3ds. I teraz muszę zrobić jego uproszczenie do pewnego zbioru sześcianów/prostopadłościanów/czegokolwiek. Metoda która pierwsza przychodzi na myśl to zamnąć tą bryłę w sześcianie/prostopadlościanie a później iterazcyjnie dzielić każdy jego bok na pół i sprawdzać, który z tak powstałych sześcianów/prostopadłościanów nie należy do bryły. No tylko, że w tym punkcie dochodzimy do zasadniczego prolemu - Jak wykryć kolizję czegoś takiego nie tylko z samą powierzchnią bryły ale także ze środkiem?
Jako, że jest to moment generowania modeli dopiero, a nie samej gry więc koszt oblczeń na szczęście może być duży.

Błagam poratujcie!

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Czerwiec 11, 2007, 16:06:33
Właściwie to nie wiem dokładnie jak to zrobić, ale napiszę odpowiedź bo przychodzą mi tu do głowy trzy sprawy:

- Po pierwsze, to jest coś takiego jak upraszczanie modelu do zbioru brył otaczających i nawet się to pewnie jakoś nazywa ;P Tylko nie wiem jak. Poszukaj, to pewnie znajdziesz dobre algorytmy na to, lepsze niż sam byś wymyślił.

- Po drugie to ja wymyślanie takiego algorytmu zacząłbym raczej od drugiej strony tzn. wyobrażając sobie każdy jeden trójkąt otoczony sześcianem czy co tam masz zaczął je łączyć w coraz większe wybierając do połączenia te, które (tu wstaw jakiś fajny warunek, np. które najściślej przylegają do siebie, pasują kształtem, najmniej wolnej przestrzeni marnują itp.).

- Po trzecie, jeśli ta siatka trójkątów jest zamknięta to test na zawieranie się wybranego punktu wewnątrz tej siatki sprowadza się do prostego rzucenia promienia z tego punktu w dowolnym kierunku i policzeniu przecięcia tego promienia z właśnie tą powierzchnią siatki, o której piszesz - tak jak w tym artykule - http://www.warsztat.gd/articles.php?x=view&id=192, tyle że w 3D.

Offline Haxy.M

  • Użytkownik

# Czerwiec 11, 2007, 19:50:10
Dzięki wielkie :)

Zasadniczo jeśli dobrze zrozumiałem to te pierwsze dwa raczej tak średnio, ale trzeci jest super :)

Bo te sześciany oprócz robienia za hitboxy, zasadniczo mają robić za przybliżony rozkład masy w bryle (zakładając równomierną gęstość). Gdybym od początku znał kształt tego czegoś to byłoby prościej.
Ale to chyba nie dział na rozpisywanie się o projetktach więc z dokładnymi szczegółami przeniosę się gdzie indziej.
« Ostatnia zmiana: Czerwiec 11, 2007, 19:55:33 wysłana przez Haxy.M »

Offline Spider100

  • Moderator
    • Strona domowa

# Czerwiec 12, 2007, 16:34:27
W praktyce to korzysta się często z metody SAT (separating axis theorem) opisałbym to dokładniej, ale już 2 razy w innych tematach o kolizjach pisałem i dawałem linki ... polecam więc zajrzeć, co google na ten temat wypluje.

Offline Haxy.M

  • Użytkownik

# Czerwiec 13, 2007, 08:05:36
Dzęki, na kartce to to nawet ładne wyglada, ale jakoś cienko to, to widzę w kodzie, ale skoro twierdzisz, że się częso stosuje, może wolniejszą chwilą...

A swoją drogą własnie przed chwilą skończyłem pisać to "wypełnianie". Stanęło w końcu na prostopadlościanach. Choć już mi po orzeszku harcują pomysły jakby to jeszcze uprościć i zoptymaizować, ale grunt, że jest i chyba działa ;)

Offline counterClockWise

  • Użytkownik

# Czerwiec 18, 2007, 17:15:19
Sorry, że się tak wtrącam, ale mam taką srawę:

Mam dość złożony model w OpenGL'u przeczytany z pliku 3ds. I teraz muszę zrobić jego uproszczenie do pewnego zbioru sześcianów/prostopadłościanów/czegokolwiek. Metoda która pierwsza przychodzi na myśl to zamnąć tą bryłę w sześcianie/prostopadlościanie a później iterazcyjnie dzielić każdy jego bok na pół i sprawdzać, który z tak powstałych sześcianów/prostopadłościanów nie należy do bryły. No tylko, że w tym punkcie dochodzimy do zasadniczego prolemu - Jak wykryć kolizję czegoś takiego nie tylko z samą powierzchnią bryły ale także ze środkiem?
Jako, że jest to moment generowania modeli dopiero, a nie samej gry więc koszt oblczeń na szczęście może być duży.

Błagam poratujcie!

Przychodzi mi prosty w idei a dosyć trudny w implementacji algorytm maszerujących sześcianów - googluj pod "marching cubes algorithm".
« Ostatnia zmiana: Czerwiec 18, 2007, 17:21:21 wysłana przez counterClockWise »

Offline Haxy.M

  • Użytkownik

# Czerwiec 21, 2007, 22:18:54
Wygląda całkiem, całkiem, dzięki.