Warsztat - Programowanie gier komputerowych :: Detekcja kolizji w grach 3D Strona g³ówna Forum Szukaj Lista u¿ytkowników Grupy Zarejestruj Zaloguj Artyku³y Kliknij na kategoriê ¿eby dodaæ artyku³ Szukaj Programowanie gier » Artyku³y » Grafika 3D [Wersja do drukowania] Detekcja kolizji w grach 3D Opis Wykrywanie kolizji przy u¿yciu OctTrees Autor Micha³ "Mike" Zientkiewicz Data Pon 25 Pa¼, 2004 10:47 pm Typ *** S³owa klucze Kategoria Grafika 3D Ods³ony 713 Detekcja kolizji w grach 3D Wykrywanie kolizji przy u¿yciu OctTrees Temat czêsto by³ poruszany na forum, wiêc postanowi³em podzielic siê z Wami swoimi przemy¶leniami na temat detekcji kolizji w grach 3D. 1. Organizacja ¶wiata gry Po d³u¿szym zastanowieniu doszed³em do wniosku, ¿e najlepsz± metod± podzia³u (je¿eli chodzi o kolizje) jest OCTTree - drzewo ósemkowe. Na pocz±tek w wielkim skrócie obja¶nie, jak to dzia³a. a) robi siê prostopad³o¶cienny obrys mapy (tzw. Bounding Box) o ¶cianach le¿±cych na g³ównych p³aszczyznach (XY, XZ, YZ) b) je¿eli jest w ogóle s± jakie¶ wielok±ty, to je¿eli ich ilo¶æ jest du¿a lub rozmiar pude³ka jest za du¿y (ilo¶æ wielok±tów i rozmiar trzeba dobraæ samemu), to dzielimy mapê na pó³ wzd³u¿ najd³u¿szej osi prostopad³o¶cianu c) nie liczymy nowego obrysu - zostawiamy stary, podzielony na pó³ d) przechodzimy do punktu b) Zastosowanie OCTTrees ma dwie zalety: szybko¶æ generowania i szybko¶æ dzia³ania. Ró¿nica w jako¶ci pracy detektora kolizji jest du¿a. Na tyle, ¿e op³aca siê robiæ to drzewo nawet wtedy, gdy do rysowania u¿ywane jest np. BSP. 2. Gdzie mo¿e byæ BBOX? Ka¿dy przedmiot opisujemy przy pomocy prostopad³o¶cianu o ¶cianach równoleg³ych do g³ównych p³aszczyzn. Da siê on opisaæ sze¶cioma liczbami. Pierwszym etapem jest zrobienie du¿ego BBoxa - wyznaczonego przez minimalne i maksymalne wspó³rzêdne BBoxa przed i po przesuniêciu o ¿±dany wektor. Teraz rozpoczynamy dzielenie - tniemy BBox kolejnymi p³aszczyznami OCT (tu w³a¶nie jest oszczêdno¶æ mocy obliczeniowej) nasz BBox - po prostu zmieniamy za ka¿dym razem jedn± wspó³rzêdn±. Jak nic nie zostaje z BBoxa lub wchodzimy w pusty sektor OCT, to siê cieszymy - nie ma tam ju¿ nic do sprawdzania. Po zakoñczeniu tego procesu mamy listê sektorów OCT (np. od³o¿on± na stos), w których jest czego szukaæ. Teraz trzeba zaznaczyæ pierwotne (sprzed podzia³u) wielok±ty, które potencjalnie koliduj± ze sprawdzanym obiektem. W tym celu trzeba zachowaæ oryginaln± geometriê oraz przekazywaæ podczas podzia³u informacjê o pochodzeniu podzielonych ¶cian. Potrzebna jeszcze bêdzie tablica flag - w niej zaznaczone bêd± sprawdzone ¶ciany. Jest ona niezbêdna, gdy¿ niektóre indeksy ¶cian mog³y zostaæ powielone. Przechowywanie takiej tablicy jak i niepodzielonych ¶cian jest op³acalne - ogranicza liczbê wielok±tów do sprawdzenia. 3. Sprawdzanie Samo sprawdzanie ogranicza siê do przyciêcia ka¿dego z zaznaczonych wielok±tów wszystkimi p³aszczyznami BBoxa. Je¿eli co¶ zosta³o, to jest kolizja. ¯eby jak najszybciej eliminowaæ ¶ciany sprawdzanie najlepiej zacz±æ od ¶ciany BBoxa zwróconej w kierunku mo¿liwie zbli¿onym do wektora normalnego sprawdzanej ¶ciany - daje to du¿y odsetek odrzuceñ ju¿ na pierwszej p³aszczy¼nie. 4. Wyszukiwanie binarne Aby sprawdzanie by³o jak najbardziej efektywne trzeba sprawdziæ, w którym momencie przesuniêcia nast±pi³a kolizja. Po pierwsze, je¿eli przesuniêcie jest bardzo du¿e, to trzeba je liniowo podzieliæ. Na ka¿dym takim fragmencie robimy 'motylka' - wyszukiwanie binarne miejsca kolizji. Jak wiadomo, ma ono z³o¿ono¶æ log2(n), czyli mo¿na sobie pozwoliæ na bardzo du¿± dok³adno¶æ detekcji (przy 10 krokach 0.001 przesuniêcia). Dobrze jest ograniczyæ ilo¶æ kroków wyszukiwania do 32 - wtedy mo¿na u¿ywaæ kolejnych bitów z tablicy flag bez zerowania interesuj±cego nas fragmentu tablicy. Skocz do: Wybierz forumWarsztat - Programowanie gier komputerowych|--Szkó³ka| |--Szkó³ka - jêzyki| |--Szkó³ka - grafika| |--Szkó³ka - inne|--Programowanie gier| |--Ogólnie| |--D¼wiêk| |--Sztuczna Inteligencja| |--Inne|--Programowanie grafiki| |--Programowanie grafiki| |--OpenGL| |--DirectX|--Produkcja| |--Pomys³y| |--Projektowanie| |--Projekty| |--Grafika| |--Og³oszenia|--O czym innym| |--Konferencje, spotkania| |--Warsztat| |--Aktualno¶ci| |--Artyku³y| |--Wyk³ady| |--Compo| |--Lepperlandia|--¦mietnik| |--Z odrzutu Powered by Knowledge Base, wGEric (C) 2002 PHPBB.com MOD This script (Knowledge Base - MX Addon v. 1.03e) is modified by Haplo W1.5b (C) 2004 [admin: ayufan, g[R]eK, Goliatus, mikael_, Regedit] Wszystkie czasy w strefie CET (Europa) Powered by phpBB2 Plus 1.52 based on phpBB 2.0.10 © 2001, 2002 phpBB Group :: FI Theme :: Mody i Podziêkowania