Autor Wątek: BVH - optymalizacja kolizji  (Przeczytany 1547 razy)

Offline Risist

  • Użytkownik

# Sierpień 30, 2016, 14:51:23
Witam.

Ostatnio postanowiłem ulepszyć część związaną z kolizjami w swoim silniku.
Wybrałem algorytm bvh (a raczej coś na kształt ). Ok, ostatecznie działa, ale wydajność jest gorsza niż w przypadku sprawdzania każdy z każdym.

Obecnie całą strukturę muszę odbudowywać z każdą klatką. Pewnie tutaj leży problem i powinienem jakoś reusować dane z poprzednich klatek. Tylko jak to zrobić? Gdyby część mapy była statyczna byłoby dobrze. Może i będzie ale jeżeli zacina się przy 20-30 koliderach to raczej statyczność mnie nie uratuje. Mógłbym aktualizować jedynie dynamiczne obiekty, ale co mi z tego jak potrzebuję przynajmniej z 30 dynamicznych (na przeciwnika idzie od 5 do nawet  15 )

Pomocy!!!!!!!!!!!!!!!!!!!!!!!!!!

Offline Mr. Spam

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

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

  • +1
# Sierpień 30, 2016, 20:24:35
Dobrze, że mierzysz wydajność swojego rozwiązania i porównujesz, które jest szybsze. Żeby to zoptymalizować, możesz spróbować:

- Przejrzeć algorytm budowania tego drzewa, czy aby na pewno jest odpowiednio wydajny.
- Spróbować aktualizować jednak tylko dynamiczne obiekty - może uda się to zrealizować tak, że będzie działało szybciej.
- Podzielić obiekty na statyczne i dynamiczne. Trzymać je w oddzielnych strukturach. Tylko te dynamiczne odbudowywać co klatkę.
- Nie trzymać każdego obiektu w oddzielnym węźle drzewa, tylko dzielić obiekty na hierarchię jedynie do jakiegoś poziomu, kiedy w jednym węźle jest maksymalnie np. 10 czy 100 obiektów - granicę dobrać eksperymentalnie.

Offline lethern

  • Użytkownik

# Sierpień 30, 2016, 21:35:22
Cytuj
Dobrze, że mierzysz wydajność swojego rozwiązania i porównujesz, które jest szybsze
czy tylko ja pomyślałem, że chwalisz go za wyświetlacz FPS? :D
(nie mogłem sie oprzec)

Offline Reg

  • Administrator
    • Adam Sawicki - Home Page

  • +1
# Sierpień 31, 2016, 12:29:48
Wyświetlacz FPS to jedno. Chociaż FPS to nie jest dobra miara wydajności, bo jest nieliniowy - to odwrotność średniego czasu klatki. Nie można mówić "przyspieszyłem o 10 FPS", bo to zupełnie inna skala, jeśli tych FPS było 10, 100 albo 1000. Lepiej mierzyć czas klatki w milisekundach.

Ale drugie to patrzeć na ten wyświetlacz. Niejeden mógłby napisać superskomplikowaną optymalizację i ogłosić "mam algorytm podziału przestrzeni, mój silnik jest zoptymalizowany" nie sprawdzając, czy rozwiązanie brute force nie jest czasem szybsze (a nieraz zdarza się, że jest).

Offline Mergul

  • Użytkownik

# Sierpień 31, 2016, 14:31:13
Dokładnie. Nie raz przekonałem się, że super optymalizacja może okazać się spowalniaczem programu a nie optymalizacją. Ale druga sprawa, że często optymalizacje wypadają gorzej przy małej ilości danych, a później wyprzedzają te niezoptymalizowane wersje. Więc warto pisać różne wersje i testować je w różnych warunkach.

Offline Adam27

  • Użytkownik

# Sierpień 31, 2016, 15:20:59
Cytat: Reg
Nie można mówić "przyspieszyłem o 10 FPS", bo to zupełnie inna skala, jeśli tych FPS było 10, 100 albo 1000. Lepiej mierzyć czas klatki w milisekundach.

A co się zmieni gdy powiemy "przyspieszyłem o 10ms"? FPS jest tak samo dobrą miarą wydajności jak czas w ms, bo jedną jednostkę możemy otrzymać z drugiej. Ale obie miary tak samo nie nadają się w przypadku podawania różnicy wydajności - do tego służą procenty. Wtedy nie ma znaczenia, czy będziemy mieli 10ms, czy 100FPS, bo 100% skoku wydajności da nam w obu przypadkach taki sam wynik 5ms/200FPS.

Offline Kos

  • Użytkownik
    • kos.gd

# Sierpień 31, 2016, 19:09:00
@Adam27 milisekundy mają tę cechę że dają się dodawać i odejmować. Możesz sobie np. powiedzieć że średnio podczas jednej klatki przez 7ms liczysz fizykę, przez 3ms AI a przez 5ms rendering i całość się akurat ledwo mieści poniżej 16ms/f.

Offline pturecki

  • Użytkownik

  • +2
# Październik 04, 2016, 16:25:12
Witam. Implementowałem BVH jakiś (spory) czas temu i bardzo fajnie się sprawdzało, ale do statycznej geometrii (akurat u nas nie było to do kolizji obiekt vs obiekt, ale do sprawdzania kolizji z rayem i frustumem). Jako, że w BVH rozmiar i współrzędne "celek" liczone są na podstawie rozkładu obiektów w przestrzeni to liczenie tego trochę trwa (ale bez przesady oczywiście). Dla kolizji tylko 30 obiektów raczej nie opłaca się nic kombinować ze "strukturami przyspieszającymi" (ew super prostymi).

Takie np octree, które ma stały rozkład "celek" dużo lepiej się sprawdzi dla dynamicznych obiektów (jest cała masa różnych wersji octree, zresztą BVH też). Nie trzeba przebudowywać (ew odrobinę, zależnie od wersji), a wstawianie i usuwanie obiektów z octree jest proste i szybkie.

PS. I testuj na "żywym" przykładzie. Jeśli docelowo ma być np 300 (lub więcej) obiektów w grze, to testy na 30 mogą prowadzić do mylnych wniosków. Albo jeśli docelowo kolizja obiekt-obiekt ma być bardzo kosztowna (super dokładna itp) a teraz testujesz na "prostych" kształtach to może być podobnie jak w poprzednim zdaniu.