Autor Wątek: Kolizje  (Przeczytany 5245 razy)

Offline LukiX93

  • Użytkownik

# Marzec 14, 2008, 15:37:03
Jaki sposób detekcji kolizji proponujecie? Rzecz jasna nie chodzi o linki tylko o opinie na temat większości - w google nie trudno coś znaleźć :P ale chodzi o to żeby to było szybkie i skuteczne. Myślę że jest dużo ludzi, którzy mają z tym doświadczenie.

Offline Mr. Spam

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

Offline klosio.neostr...

  • Użytkownik
    • Moje Stare Gierki

# Marzec 14, 2008, 15:40:18
A o jakie kolizje chodzi?
3D? Jak bardzo ma być realistycznie?

Offline LukiX93

  • Użytkownik

# Marzec 14, 2008, 15:44:06
Tu właśnie trzeba znaleźć złoty środek ;D ma być w miarę (bez przesady...) realistyczna, ale i wydajna. W 3D rzecz jasna ;)

RageX

  • Gość
# Marzec 14, 2008, 16:18:12
Zacznij powoli i leć po kolei:
1. Mapy kolizji 2 wymiarowe niczym w Doom-ie
2. AABB, sfery
3. Ciągłe wykrywanie kolizji
4. Podział przestrzeni i hierarchie obiektów
5. Kolizje trójkątów, convex hull (nie umiem przetłumaczyć, a nie chce skaleczyć próbując)
6. Fizyka obiektów
7. Krzywe trajektorie
8. ... nie wiem.

Albo - przede wszystkim -weź cudzy silnik się tym zajmujący, ale nie ma idealnych.

Offline Khaine

  • Użytkownik

# Marzec 15, 2008, 03:32:49
mysle, ze dosc dobrym pomyslem bedzie na pewno jakies drzewo osemkowe, wtedy mamy juz raczej malo do sprawdzania. Potem sprawdzamy sfery otaczajace. Nastepnie szescian otaczajacy. Jesli model sklada sie z kilku czesci, to warto zeby kazda miala swoj szescian otaczajacy i wtedy sprawdzamy kazdy taki szescian. Na koncu przeciecia z trojkatem.

Tu moze byc pewien problem jesli postac ma sie zderzyc z inna postacia bo wtedy trzeba robic trojkat-trojkat obu postaci (juz dla jednej jest sporo liczenia). Na razie nie mam pomyslu jakby sobie z tym poradzic. Moze kosci uzyc?

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

# Marzec 15, 2008, 09:52:20
Trzeba sobie zadać pytanie czy naprawdę potrzebne są kolizje między poszczególnymi trójkatami dwóch postaci? Czy nie można się zatrzymać gdzieś na wyższym poziomie?

Kiedy strzelamy do animowanego potwora to oczywiście warto sprawdzić czy kula trafiła akurat w podniesioną rękę itd., chociaż nawet wtedy możnaby używać jakiś OBB (bounding boksów) otaczających kości zamiast pełnej siatki trójkątów.

A w przypadku zwykłego chodzenia po mapie i obijania się o ściany dobra będzie kolizja elipsoidy z trójkątami mapy.
http://www.gamedev.net/reference/articles/article1026.asp

RageX

  • Gość
# Marzec 15, 2008, 14:45:14
Ja nie widzę np. rag dolla na czymś innym niż sfery czy AABB.

Offline ziomber

  • Użytkownik

  • Zbanowany
# Marzec 15, 2008, 15:06:34
Ja bym jeszcze dodal do listy ragex'a taki problem jak przeliczenie kilku klatek w przód zeby sprwdzic czy przypadkiem coś sie nie spieprzylo i mamy quake'a

Offline LukiX93

  • Użytkownik

# Marzec 15, 2008, 16:19:58
Stawiam karmę, każdy pomógł! :D Szczególne podziękowania dla RageX za listę i Reg'a, który od razu zapodał linkiem ;)

Offline Spider100

  • Moderator
    • Strona domowa

# Marzec 15, 2008, 16:51:00
Cytuj
Ja nie widzę np. rag dolla na czymś innym niż sfery czy AABB.
Ja swojego napisałem na kapsułkach i też nieźle działał...

Co do tematu kolizje heh jest jedno ale
Po pierwsze  Jaki test kolizji broadpahse czy nearphase bo ktoś tu chyba myli pojęcia

Druga sprawa jakich obiektów trójkąty mapy wysokości wielościany wypukłe ? Czy geometria może się obracać czy jedynie przesuwać ? Jak duzo siatek statycznych mamy ?
Jak widać jest wiele ale i nie znajdziemy najlepszego rozwiązania jednak możemy szukać:

Zacznę jednak od początku z tego co mi wiadomo (ale nie mam zamiaru opisywać tych metod głownie dlatego ze podając nazwy każdy może sobie poszukać)

broad-phase  (test ogólny)
Wiadomo używamy bounding boxów lub bounding sphere zależnie od tego co nam wygodniej...
W przypadku wyszukiwania par najbliżej znajdujących się obiektów najlepiej użyć jakiegoś lepszego rozwiązania niż standardowe n^2 porównań. Tutaj można zainteresować się:
Dla siatek w większości dynamicznych dobry jest algorytm SAP (Sweep-and-prune).
Jeśli jednak większość obiektów jest statyczna najlepiej podzielić przestrzeń drzewami.
Mamy jeszcze rozwiązanie nazwane Spatial Hashing ale ma taką wadę ze obiekty powinny być podobnych rozmiarów aby dobrać odpowiedni podział...

narrow-phase (test szczegółowy)
Tutaj mamy do wyboru multum rozwiązań dla siatek wypukłych ja polecam:
SAT (Separation axis theorem) - rozwiązanienie zostało jednak udowodnione dla siatek w 3d jednak da się z niego korzystać i większości przypadków dziąła poprawnie dość szybko.
JKG (Gilbert-Johnson-Keerthi) - algorytm ciekawy warto się zainteresować ale niestety korzysta z sumy Minkowskiego której wyznaczenie też sprawi sporo problemów (złożonośc duża) Dla obiektów nie obracających się wygenerowanie wcześniej sum jest doskonałym rozwiązaniem i daje najszybszy możliwy test kolizji.
Spotkałem się też z kożystaniem z dualności siatek wypukłych. Nalezy skożystać z twierdzanie że, otoczka wypukła brył dualnych jest częścią współną siatek pierwotnych. Jest to dośc trudne w implementacji dla 3d.

Jeśli siatka nie jest wypukła warto zaznajomić si ez algorytmem diagramu voronoi




Offline human

  • Użytkownik

# Marzec 16, 2008, 11:09:19
A co myslicie o tym żeby zaprządz PhysiXa do liczenia kolizji gracza ?
W SDK jest lekcja pt. Character Controller. Chyba nie powinno byc to wolniejsze
od wlasnej implementacji kolizji gracza ?

Offline raver

  • Użytkownik
    • Moja strona domowa.

# Marzec 16, 2008, 11:25:46
Moim zdaniem, jeśli kogoś nie interesuje pisanie silnika pod fizykę, może śmiało sięgnąć po coś gotowego (Bullet, Newton, PhysX). Po co wywarzać otwarte drzwi? :D

RageX

  • Gość
# Marzec 16, 2008, 12:50:16
zwłaszcza że są to mocarne drzwi które mogą takiego twórcę wielokrotnie zniechęcić.

Offline Kos

  • Użytkownik
    • kos.gd

# Marzec 16, 2008, 12:54:56
Ale ile przy tym zabawy i jaka później satysfakcja! :]
(Geez, jak ja się kiedyś cieszyłem gdy za młodu, jeszcze pod DelphiX, zrobiłem po długich męczarniach skuteczne (czyt. niebugujące przy narożnikach) reakcje na kolizję prostokąt vs prostokąt ^^")

RageX

  • Gość
# Marzec 16, 2008, 13:06:19
A ile to ja razy się cieszyłem że coś działa a po bardziej wnikliwych testach się okazywało że jednak nie do końca.