plik


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

Wyszukiwarka

Podobne podstrony:
Trochę fizyki matematyki w grach 3D
3D FON Srednevekovie
readme and terms of use 3d cad models
Piła 3D Saw VII 2010 BRRip XviD Noir
THOR 3D (SBS) 2011 ENG (Napisy PL) BluRay 1080p Side by Side Napisy THOR 3D (SBS) 2011 ENG (Napisy
(3D)(Softimage XSI)(eBook) building muscle
Staphylococcus aureus w Ĺźywnosci charakterystyka, detekcja, zwalczanie
Blender 3D Bryły Podstawowe Prosta Animacja Brył Część 1 Tutorial

więcej podobnych podstron