II/ProgramowanieGier/WykladFizyka

Programowanie Gier -> Wykład: Fizyka

PomocSpisTreści

Wstęp
Przegląd popularnych silników (bibliotek) fizyki
1. Free/open-source/software
2. Proprietary / closed-source

Plan wykładu: Opowiemy najpierw ogólnie o bibliotekach (silnikach, engine'ach) fizyki: po co, jak i dlaczego. jakie są podstawowe pojęcia. Potem zrobimy krótki przegląd istniejących popularnych silników, pokażemy sobie dema i — w miarę czasu — rzucimy okiem na proste (typu "hello world") kody źródłowe używające tych silników.

Mamy tylko 1 godzinę, więc proszę mnie popędzać w trakcie dem silników

1. Wstęp

Wikipedia o "Physics engine" (będzie dużo linków do wikipedii, bo do dzisiejszego wykładu wikipedia ma dużo dobrych artykułów).

Ogólnie: Na obiekty w realnym świecie działają różne siły. Grawitacja, każde zderzenie przekazuje jakąś siłę, jest opór powietrza, tarcie etc. Bez silnika fizyki umiemy robić tylko wykrywanie kolizji. Żeby rzeczywiście świat działał fajnie musimy jeszcze umieć aplikować wszystkie siły, patrzeć jak zmieniają się fizyczne wielkości (prędkość, przyspieszenie). Engine fizyki właśnie to za nas robi (i przy okazji robi też wykrywanie kolizji, chociaż typowo na uproszczonych wersjach obiektów). Oblicza jakie siły działają, jak się zmieniają, symulując takie pojęcia jak prędkość, masa, tarcie, w przypadku soft body także elastyczność obiektów. Przede wszystkim, oblicza jak zmieniają się nasze obiekty pod wpływem tych sił.

Typowy schemat użycia fizyki to stworzenie innego "świata" 3D na potrzeby biblioteki fizyki:

Budujemy uproszczony odpowiednik naszego swiata 3D na potrzeby biblioteki fizyki.

Uproszczony, bo geometria obiektów podawanych do fizyki powinna być prostsza. Nasze typowe siatki trójkątów nie są najlepszymi reprezentacjami dla silnika fizyki (chociaż są obsługiwane przez nie-trywialne silniki fizyki, ale czasami mogą być tylko statyczne, a nawet kiedy są dynamiczne — mogą być zwyczajnie wolne). Dla obliczeń fizyki najlepsze są kształty wypukłe (prostopadłościany, sfery, cylindry, albo przynajmniej wypukła (a więc także elegancko zamknięta, 2-manifold) siatka trojkątów).

Z drugiej strony, podajemy dodatkowe parametry dla fizyki dla naszych kształtów, jak masa, współczynnik tarcia etc.
Uruchamiamy często w pętli naszego programu funkcję która robi "tick" fizyki. Czyli uaktualnia transformacje obiektów na podstawie sił, prędkości etc. obliczanych (i aktualizowanych) wewnętrznie przez silnik fizyki.
Uaktualniamy nasz świat (na potrzeby wyświetlania, a może i innych rzeczy) tak żeby odpowiadał stanowi obliczonemu prze silnik fizyki. W prostej wersji, po prostu kopiujemy transformacje obiektów.

Niektóre engine'y fizyki nadają się do real-time, niektóre nie. Nas na tym wykładzie interesują tylko te pierwsze. (Chociaż tych drugich też przecież możemy używać w grach, choćby na zasadzie "baking" przeliczonych symulacji do normalnych animacji w blenderze i potem eksport.)

Rodzaje obsługiwanej fizyki:

Rigid body, czyli ciało sztywne. Obiekty mogą się przesuwać i obracać (zazwyczaj jest to konfigurowalne i możemy włączyć tylko przesuwanie), i to właściwie tyle. Złożone obiekty tworzymy łącząc w hierarchię proste body przez joints. Obsługiwane przez wszystkie silniki fizyki.
Soft body, czyli ciało elastyczne. Typowy model to "zespół kulek połączonych sprężynkami". Proste elastyczne obiekty (np. pojedyncza sprężynka, łącząca elastycznie dwa obiekty) znajdziemy w większości engine'ów, ale "prawdziwe" soft body to obsługa obiektów które są całym połączonym systemem wielu takich sprężynek.

Jako soft body kwalifikuje się też cloth czyli symulacja ubrania.
Zaawansowane silniki mają też specjały jak fluid simulation (PhysX, offline fluid simulation w blenderze którego można zrobić "bake"). Particle engines (particles mogą też pomóc przy symulacji fluid). Hair (zarówno metody particle engines, jak soft body mogą tu mieć związek).

Biblioteki fizyki muszą rozwiązywać zestawy równań różniczkowych. Przykład:

Ogólnie, akcelerację możemy obliczyć z 2 zas dynamiki Newtona (v' = F/m), F mamy zadane (wiemy jaka siła nas interesuje). Np. air resistance, czyli opór powietrza, to (uproszczenie!) v' = -v / m, gdzie v to prędkość, m - masa, a v' - to pochodna prędkości, czyli właśnie akceleracja.
Znając akcelerację, chcemy znaleźć prędkość i faktyczne położenie. I tu wkracza rozw równań różniczkowych, które większość engine'ów fizyki (poza jednym, Newton) wykonuje numerycznie (metody Eulera etc., mamy cały przedmiot temu poświęcony.) Bo zazwyczaj równania są bardziej złożone niż przykładowe powyżej.
Istotny wniosek z tego dla nas (tzn. zwykłych użytkowników silnika fizyki): kiedy mamy numeryczne rozw. równań różniczkowych, funkcja "tick" naszego silnika naturalnie pobiera jako parametr ilość czasu jaki upłynął od ostatniego ticka. Ta ilość czasu to po prostu długość kroku dla metody rozwiązującej równ. różniczkowe. Nie jest dobrze kiedy ta ilość zbytnio się chwieje, nie jest dobrze kiedy jest zbyt duża, nie jest dobrze kiedy jest zbyt mała. Więc zazwyczaj nie należy obliczać "czasu jaki upłynął" dla fizyki na podstawie faktycznego czasu od ostatniej ramki. Silniki fizyki działają najlepiej kiedy "czas jaki upłynął" jest mniej więcej stały dla każdego "ticku". Typowo: 1/60 sekundy to typowa zalecana wszędzie wielkość.

Więc w naszej grze musimy starać się wywoływać ten "tick" rzeczywiście w miarę równomiernie 60 razy na sekundę. Jeżeli mamy dużo więcej FPS, to zapewne nie przed każdą ramką wywołamy tick fizyki. Jeżeli mamy dużo mniej FPS, to przed niektórymi ramkami możemy chcieć wywołać więcej niż raz tick fizyki.

Ponadto, silniki zazwyczaj pozwalają modyfikować ilość iteracji wykonywanych w każdym kroku. Małe wartości sprawiają że wszystko działa szybciej, ale też obniżają precyzję obliczeń. Wartości około 10, 20 są generalnie standardowe i powinny wystarczyć do każdej gry. Jeżeli mamy problemy z szybkością fizyki, możemy kombinować i zmniejszać tą ilość iteracji.

Bardzo ładne artykuły opisujące działanie fizyki (dynamiki właściwie, czyli tego co nas interesuje na tym wykładzie): by Chris Hecker. Polecam jako lekturę po wykładzie, łagodne i eleganckie wprowadzenie do działania silników fizyki.

Słowniczek niektórych mniej znanych terminów z angielskiego:

friction = tarcie, siła tarcia
torgue = moment obrotowy. Ważne gdy mamy obiekt obracający się pod wpływem siły. Wektor (cross promienia i siły) = kierunek wokół którego następuje obrót, długość to intuicyjna siła obrotu.

Bardzo ważna optymalizacja, spotykana chyba w każdym silniku fizyki: usypianie nieruchomych obiektów. W rzeczywistości wszystko cały czas "drga". W komputerze drga ponadto z powodu nieuniknionych błędów floating point. Byłoby jednak głupio tracić czas CPU na obliczanie dużych statycznych grup obiektów... Dlatego każdy chyba silnik ma ustawienie które "usypia" obiekty które nie ruszyły się w ciągu jakiegoś czasu (~sekunda) o więcej niż epsilon. Obiekt uśpiony jest traktowany jako nieruchomy do czasu aż wejdzie w kontakt z obiektem nie-uśpionym. Mamy w silnikach funkcje do kontroli parametrów usypiania i zazwyczaj możemy wyłączać usypianie (chociaż na "prawdziwych" scenach zazwyczaj należy pozwolić na usypianie żeby wszystko działało szybko.).

2. Przegląd popularnych silników (bibliotek) fizyki

2.1. Free/open-source/software

2.1.1. Box2D

http://www.box2d.org/, http://en.wikipedia.org/wiki/Box2D.

  Pojęcia: Core Concepts z Box2D.

    Przede wszystkim: constraint, i contact constraint.
    Innymi słowy, "contact constrainty" to zestaw równań który sprawia
    że obiekty nie kolidują ze sobą nawzajem (pilnują też innych rzeczy).
    Zadanie engine fizyki: zaaplikować forces ale zapobiec
    złamaniu constraintów.

  http://en.wikipedia.org/wiki/Sweep_and_prune

  Mention TARGET_FLOAT32_IS_FIXED
  Pokaż hello world.
  Pokaż testbed.
    Iteration : Mniejsze iteration -> gorsze rozwiazania ale też krótszy czas.
    1 / Hertz : o ile zmienia się czas w każdym kroku.
      Uwaga: We also don't like the time step to change much. So don't tie the time step to your frame rate (unless you really, really have to).

    Samo Shapes rysuj.
    Joins wyjaśniają połączenia.

  Look at hello world, important things:
  world z aabb w którym są kolizje
  doSleep
  static body (0 mass) - Static bodies don't collide with other static bodies and are immovable
  mass > 0 - dynamiczne ciało
  note: SetMassFromShapes, w shapes ustawiamy density (podanie kształtu + density -> masa)

Podsum:
+ free/open-source/software
+ elegancki C++, bardzo przenośny, także na konsole, portable (ma możliwość fixed floats)
+ dobre docs
-/+ tylko 2D, by design

2.1.2. Bullet

http://www.bulletphysics.com/, http://en.wikipedia.org/wiki/Bullet_(software)

Znany z Blender game engine (można robić "bake" wyników symulacji do
normalnej animacji).

Demo: Demos/AllBulletDemos
  szczególnie:
  - Ragdoll (http://en.wikipedia.org/wiki/Ragdoll_physics)
    Czyli puszczamy potworka w pełni pod kontrolę fizyki,
    zadając mu minimalne ograniczenia żeby wszystkie kawałki (tułów, nogi
    etc.) były połączone i żeby nie mogły się wyginać *za bardzo* nienaturalnie.

  - Basic demo z/bez "disable deactivation"

  - kilka dem z softbody

Rzut oka na source code Demos/HelloWorld/HelloWorld.cpp
Jak widać, generalnie podobnie do Box2D, tylko że tutaj 3D.

Jakie obiekty 3D? Rzut oka na Bullet_User_Manual.pdf (page 14).

Dla rigid body, (podobnie jak w box2d):
- masa = 0 oznacza że koliduje
  ale nie jest pod wpływem obliczeń fizyki (są 2 przypadki:
  static albo kinematic, kinematic może być ruszane przez nasz program).
- masa > 0 to obiekty dynamic, ich transform będzie updated.
- Zwróćcie uwagę że skalowanie generalnie nie jest automatyczne,
  bo zgodnie z fizyką obiekty rigid body się przecież nie skalują.
  Bullet ma specjalne metody i klasy żeby pozwalać na skalowanie
  obiektów.
- Mamy specjalne pomoce MotionState które pozwalają usprawnić etap
  uaktualniania transformacji obiektów w naszej grze na podstawie
  transformacji w Bullet. Zamiast robić za każdym razem coś jak
  "for each object do o.transform := o.physics.transform",
  mamy MotionState, abstrakcyjną klasę, możemy stworzyć jej potomka
  który będzie automatycznie powiadamiany przez Bullet o zmianach stanu.
  Idea: jeżeli każda kopia tranformacji jest kosztowna (np. może
  spowodować wysłanie jej przez sieć), to lepiej nie robić "for each ...",
  zamiast tego Bullet powiadomi tylko o faktycznych nie-zerowych zmianach.

Demo używania samego collision detection - rzut oka na
Demos/CollisionDemo. Mamy do dyspozycji getClosestPoints.

Demo: integracja z Collada, potrafi odczytać model w Collada 1.4
i automatycznie go użyć, łącznie z physics properties inside.
Można też zapisać aktualny stan modelu do Collada.
Demos/ColladaDemo - snapshots, loading your own file, created by blender collada exporter.

Podsum:
+ free/open-source/software
+ soft and rigid body
+ elegacki C++, bardzo przenośny
+ możliwosć hw accel: Playstation 3 Cell SPU, CUDA, OpenCL
+ obsługuje też Collada Physics, czyli można wprost załadować
  obiekty w Collada >= 1.4 i kształty + własności fizyczne zostaną
  załadowane.

2.1.3. ODE (Open Dynamics Engine)

http://www.ode.org/, http://en.wikipedia.org/wiki/Open_Dynamics_Engine

Kilka pojęć z manual
(local: file:///home/michalis/uniwerek/progr_gier/lecture_physics/ode/Manual_(All).html):
- rodzaje obsługiwanych obiektów: Collision Detection

- dWorldQuickStep wykonuje tylko zadaną ilość iteracji (więc tak jak Bullet),
  dWorldSetQuickStepNumIterations pozwala kontrolować ich ilość.

  Variable Step Size: Don't! (znamy już z poprzednich)

- Typical simulation code (kolizje -> dodawanie dJointCreateContact, potem dWorld[Quick]Step)

  Note that the built-in collision functions do not have to be used - other collision detection libraries can be used as long as they provide the right kinds of contact point information.

- Joints and constraints (znamy już z poprzednich)
- Joint error and the error reduction parameter (ERP)
- Soft constraint and constraint force mixing (CFM)

Proste demo:
./demo_boxstack
./demo_crash
./demo_feedback - rozrywalne jointy

Podsum:
+ free/open-source/software
+ chyba najbardziej powszechny z otwartych silników fizyki (chociaż Bullet dość nieźle nadgania), jest np. spakietowany w Debianie
+ w środku elegacki C++, bardzo przenośny
+ API w prostym C (jest też wersja C++, chociaż C bardziej powszechna), co oznacza że bindingi do wszystkich możliwych języków programowania są możliwe
+ obsługuje też Collada Physics
- nie ma w ogóle soft body (ale są proste sprężynki do łączenia obiektów)

2.1.4. PAL (Physics Abstraction Layer)

http://www.adrianboeing.com/pal/index.html, http://en.wikipedia.org/wiki/PAL_(software)

High-level API które na spodzie używa różnych engine'ów fizyki.
I rzeczywiście obsługuje ich dużo (i tych open-source, i tych drugich).
Pomysł w sumie niezły. Lista obsługiwanych engines jest imponująca,
obejmuje naprawdę większość znanych engines (np. chyba wszystkie o których
wspominam dzisiaj (Box2D, Bullet, ODE, Newton, Havok, PhysX) są
obsługiwane!).

Tradycyjny problem z takim podejściem
(znany np. z wielu bibliotek SQLa opakowujących różne bazy sql):
albo robimy API pozwalające na dużo, i w rezultacie stosunkowo złożone
w porównaniu z prostymi bazami SQL, albo robimy tylko proste API obsługujące
wspólny podzbiór, proste ale nie dające nam dostępu do wszystkiego pod spodem.
PAL ma generalnie proste API, chociaż miejscami daje dostęp do większych rzeczy
(fluid, soft body) które naturalnie mogą nie istnieć we wszystkich backendach.
API jest całkiem wygodne, przynajmniej patrząc na hello worldy.

Dzięki temu że PAL opakowuje wiele engines, feature'y
na poziomie ponad samym opakowaniem działają z każdym engine na spodzie.
Np. PAL daję obsługę Collada Physics dla wszystkich engine's opakowywanych.

Rzut oka na simple demo.

Jest duże zamieszanie przy building. Po części jest naturalnie
--- pal chce używać bibliotek fizyki,
które typowo nie są standardowo zainstalowane
na ściażkach, niektóre są budowane i typowo używane tylko do .a (nie .so),
niektóre mogą być budowane z różnymi opcjami (np. bullet fixed float).

Notki:
- aktualna wersja używa CMake, zamiast na
  http://www.adrianboeing.com/pal/install_generic.html
  lepiej patrzeć na
  http://apps.sourceforge.net/mediawiki/pal/index.php?title=Main_Page

  Generalnie (jeżeli nie mamy MSVC) trzeba edytować CMakeCache.txt pod koniec,
  albo edytować źródła (CMakeLists.txt i CMakeModules/FindXXX)
  i kasować cache co chwila (rm -f CMakeCache.txt ; cmake . -G "Unix Makefiles").
  Trzeba upewnić się że znajduje biblioteki,
  upewnić się że są na odpowiednich ścieżkach albo dopisać odpowiednie
  (w pliku albo zmiennej środ.), pod nie-Windowsem warto zmienić "dll" na "so" :).

  Uruchamianie cmake . -G "Unix Makefiles" dwukrotnie pod rząd też pomaga...
  Nie znam się na cmake, więc disclaimer: być może plotę tu bzdury i szło
  mi opornie bo robiłem to w dziwny sposób.

- Zasadniczy problem to też wersja "static" która wydaje się być wymagana
  chwilowo pod gcc, ale oznacza też że właściwie działa tylko *jeden*
  engine pod spodem (czyli trochę "po co myśli tą żabę jedli",
  no, ale można zawsze przygotować kilka wersji PALa,
  API pozostaje bez zmian).

- Jeśli ktoś ma MSVC i Windowsa, to być może będzie miał łatwiej ---
  przynajmniej niektóre notki w dokumentacji sugerują że autor sam
  głównie korzysta z MSVC, duże demo "paldemo" też jest tylko pod MSVC/Windows...

Podsum:
+ free/open-source/software
  (na spodzie pozwala też użyć closed-source)
+ obsługuje też Collada Physics (nawet z engine'ami które nie mają go "natywnie")
+ API w C++ (każdy engine to fabryka klas)
- nie do końca bezboleśnie przenośne, jeżeli nie mamy MSVC/Windows to -> duże problemy z build process, przynajmniej w moim doświadczeniu.

2.1.5. Resigned (nie omówimy)

-----------------------
Także OPAL: http://opal.sourceforge.net/

OPAL na razie obsługuje tylko ODE, ale ma aspiracje do bycia czymś lepszym.
Oba są open-source, niech Was nie zmyli fakt że tylko jeden ma "Open"
w nazwie.

-----------------------
http://en.wikipedia.org/wiki/SOFA_(Simulation_Open_Framework_Architecture)

Podsum:
+ free/open-source/software
+ także soft body
+ spakietowany w Debianie

------------------------------------------------------------------------------
http://en.wikipedia.org/wiki/Tokamak_physics_engine ?
http://en.wikipedia.org/wiki/Phyz ?

2.2. Proprietary / closed-source

Wyjątkowo, wypada jednak wspomnieć o niektórych bardziej znanych:

2.2.1. Newton

http://www.newtondynamics.com/, http://en.wikipedia.org/wiki/Newton_Game_Dynamics

Rzut oka na demos (01, 12?)
Rzut oka na API z tutorial 1, bardzo proste.
Rzut oka na demos NewtonCradle, newton playground.

Podsum:
- closed source (chociaż darmowy)
+/- deterministic solver, nie iterative, więc dokładniejszy ale też może być bardziej wolny
+ API w C, więc osiągalny z każdego języka progr.
- tylko rigid body

2.2.2. PhysX

http://developer.nvidia.com/object/physx.html, http://en.wikipedia.org/wiki/PhysX

Nastawiony od początku na hardware accelerated fizykę.

Nazwa "PhysX" oznacza też specjalną kartę (PPU, Physics Processing Unit).
Oryginalnie, firma Ageia produkowała taką kartę i specjalnie do niej
stworzyła engine o takiej samej nazwie.

Obecnie NVidia przejęła Ageia (wykupiła czy coś tam).
A sam engine może używać "PhysX PPU", ale może też używać CUDA (nowsze
GPU NVIdii, GeForce >= 8000).
Obecnie by NVidia.

Podsum:
+ hardware accelerated (oryginalnie na specjalnym procesorze PPU,
  ale obecnie także na Cuda --- NVIdia GeForce >= 8000).
+ obsługuje też Collada Physics
+ rigid, soft body
+ fluid dynamics

2.2.3. Havok

http://www.havok.com/, http://en.wikipedia.org/wiki/Havok_(software)

Chyba najbardziej znany Duży Komercyjny behemot do fizyki.
Wiele znanych tytułów (fizyka HL2).

Demo, jeśli czas.

Podsum:
- closed source, płatne (w ograniczonym zakresie można używać za darmo, jeżeli robicie gry niekomercyjne)
+ C/C++, przenośny (także na konsole), chociaż wersja do spróbowania za darmo którą znalazłem jest tylko pod Win
+ są cloth (a więc soft body) od niedawna
+ są także destructible rigid body od niedawna
~ podobno pracują nad hw accelarated