Zaawansowana kamera 3D

Uwaga! Informacje na tej stronie mają ponad 5 lat. Nadal je udostępniam, ale prawdopodobnie nie odzwierciedlają one mojej aktualnej wiedzy ani przekonań.

Wstęp

Artykuł dotyczy matematyki związanej z grafiką 3D. Opisuje koncepcję kamery jako wysokopoziomowe pojęcie, które odzwierciedla dość rozbudowana implementacja w C++. Pokazuje też algorytmy na testy kolizji 3D promienia i frustuma z różnymi obiektami geometrycznymi w postaci kodu w załączonych plikach. Artykuł obejmuje tematy: Koncepcja kamery i jej implementacja, renderowanie prostokątów zwróconych zawsze przodem do kamery (ang. Billboard), usuwanie obiektów poza polem widzenia (ang. Frustum Culling) oraz wskazywanie myszką obiektów sceny 3D poprzez kolizję promienia (ang. Picking). Do jego zrozumienia potrzebna jest umiejętność programowania w języku C++, znajomość biblioteki graficznej 3D (DirectX lub OpenGL) oraz znajomość zagadnień matematyki 3D, takich jak wektory i macierze.

W kodzie tego artykułu używam Direct3D i jego domyślnego, lewoskrętnego układu współrzędnych (X w prawo, Y do góry, Z w głąb). Zdaję sobie sprawę, że przedstawiony kod nie jest w każdym miejscu optymalny, a w tekście pozwoliłem sobie na pewne uproszczenia.

Wprowadzenie

Czym jest kamera? Czegoś takiego nie znajdziemy w interfejsie DirectX ani OpenGL. To pojęcie abstrakcyjne, wysokopoziomowe. Oznacza taki obiekt w scenie 3D, który reprezentuje punkt widzenia - w tym pozycję, orientację oraz parametry rzutowania, przez jakie użytkownik patrzy na scenę. Na niskim poziomie sprowadza się to do dwóch macierzy:

  1. Macierz widoku (ang. View Matrix) dokonuje przekształcenia ze współrzędnych świata do współrzędnych kamery. Reprezentuje pozycję kamery w przestrzeni oraz jej orientację, w tym przede wszystkim kierunek patrzenia.
  2. Macierz rzutowania (ang. Projection Matrix, nazywana tu dalej w skrócie ,,Proj'') dokonuje rzutowania. Dla rzutowania perspektywicznego koduje w sobie odległość bliskiej i dalekiej płaszczyzny obcinania (Z- Near, Z-Far), kąt widzenia (FOV - ang. Field of View) oraz stosunek szerokości do wysokości (ang. Aspect Ratio).

Ale kamera to coś więcej. Te macierze powstają z pewnych parametrów wejścowych, a na ich podstawie, jak i na podstawie tych macierzy, wyliczyć można wiele innych danych potrzebnych w bardziej zaawansowanym programowaniu grafiki 3D, np. podczas pisania silnika. Dlatego warto zamknąć ich obliczanie i zarządzanie wszystkimi tymi danymi w klasę, którą nazwiemy właśnie kamerą.

Są dwa rodzaje rzutowania: perspektywiczne i ortogonalne. My w tym artykule zajmiemy się wyłącznie rzutowaniem perspektywicznym.

Rys. 1 pokazuje wyobrażenie kamery w scenie 3D. Kamerę można przedstawić jako nowy układ współrzędnych. To do niego macierz widoku przekształca wierzchołki. Z kolei obszar znajdujący się w polu widzenia ma kształt ściętego ostrosłupa o podstawie prostokąta, który nie ma ładnej krótkiej nazwy w języku polskim, a po angielsku nazywa się Frustum. O wszystkim tym będzie dokładnie mowa poniżej.

Kamera w scenie 3D
Rys. 1. Kamera w scenie 3D to nowy układ współrzędnych, a pole widzenia to frustum.

Architektura kamery

Na początek chcę omówić implementację kamery. Jest to kawałek kodu w C++, który znajdziesz w załączonych plikach: Camera.hpp i Camera.cpp. Będziemy stopniowo omawiali fragmenty tego kodu. Oprócz wielu makr, stałych, funkcji i struktur pomocniczych, sednem sprawy są tam klasy kamery. Klasy, a nie klasa, bo moją propozycję implementacji pojęcia ,,kamera'' stanowią trzy klasy, zbudowane tak jak na rys. 2.

Struktura implementacji kamery
Rys. 2. Implementacja kamery składa się z trzech klas, zagnieżdżonych jedna w drugiej.

Klasa MatrixCamera reprezentuje kamerę w sposób najbardziej niskopiozmowy - jako macierz widoku, rzutowania, a także macierze i inne struktury, które z tych dwóch macierzy można wyprowadzić. Klasa ParamsCamera przechowuje parametry, z których te macierze powstają. Na życzenie udostępnia te parametry (oraz inne, które na ich podstawie można wyliczyć), a także tworzy macierz widoku i rzutowania używając poprzedniej klasy. Wreszcie, klasa Camera reprezentuję kamerę na najwyższym poziomie abstrakcji, tak jak chciałby widzieć ją użytkownik silnika 3D. Pracuje w trybie FPP, TPP albo jako sterowana kwaternionem.

Te klasy są zaprojektowane tak, że można używać każdej wewnętrznej samodzielnie. Na przykład można utworzyć obiekt klasy MatrixCamera i używać go, wpisując mu swoje macierze widoku i rzutowania. Z kolei każda klasa zewnętrzna przechowuje w sobie klasę wewnętrzną, tak że obiekt klasy ParamsCamera automatycznie ma w sobie i zarządza obiektem klasy MatrixCamera. Co dokładnie robi każda z klas, o tym będzie mowa już za chwilę.

Klasa MatrixCamera

Klasa MatrixCamera reprezentuje kamerę w sposób najbardziej niskopiozmowy - jako macierz widoku, macierz rzutowania, a także macierze i inne struktury, które z tych dwóch macierzy można wyprowadzić.

class MatrixCamera
{
private:
  D3DXMATRIX m_View;
  D3DXMATRIX m_Proj;
  // ...

public:
  MatrixCamera() { Changed(); }
  MatrixCamera(const D3DXMATRIX &View, const D3DXMATRIX &Proj) :
    m_View(View), m_Proj(Proj) { Changed(); }

  void Set(const D3DXMATRIX &View, const D3DXMATRIX &Proj)
  {
    m_View = View; m_Proj = Proj; Changed();
  }
  void SetView(const D3DXMATRIX &View) { m_View = View; Changed(); }
  void SetProj(const D3DXMATRIX &Proj) { m_Proj = Proj; Changed(); }

  const D3DXMATRIX & GetView() const { return m_View; }
  const D3DXMATRIX & GetProj() const { return m_Proj; }

  // ...
};

Oprócz macierzy widoku i rzutowania, czasami potrzebne są ich odwrotności, a także iloczyn tych macierzy (zwany ViewProj) i jego odwrotność.

private:
  mutable D3DXMATRIX m_ViewInv; mutable bool m_ViewInvIs;
  mutable D3DXMATRIX m_ProjInv; mutable bool m_ProjInvIs;
  mutable D3DXMATRIX m_ViewProj; mutable bool m_ViewProjIs;
  mutable D3DXMATRIX m_ViewProjInv; mutable bool m_ViewProjInvIs;

public:
  const D3DXMATRIX & GetViewInv() const;
  const D3DXMATRIX & GetProjInv() const;
  const D3DXMATRIX & GetViewProj() const;
  const D3DXMATRIX & GetViewProjInv() const;

Jak pomnożyć macierze albo policzyć odwrotność macierzy, to mam nadzieję jest Ci znane (nie chodzi o wzory, tylko o znajomość nazwy funkcji D3DX :) Pozostaje jednak pytanie: Kiedy je wyliczać? Nie zwlekając zdradzę od razu, że zastosowałem tu tzw. leniwe wartościowanie (ang. Lazy Evaluation). Polega ono na wyliczaniu danego wyniku ,,przy pierwszym odczytaniu wartości wyjściowej od ostatniej zmiany wartości wejściowej''.

Oto dowód, dlaczego ta technika jest optymalna: Jako przykład weźmy macierz widoku View i jej odwrotność ViewInv. Rozwiązania problemu ,,kiedy wyliczać odwrotność'' mogą być trzy. Pierwsze polega na wyliczaniu odwrotności za każdym razem, kiedy zmienia się macierz widoku. Wówczas jednak może się zdarzyć, że użytkownik naszej klasy 10 razy zmieni macierz widoku, po czym tylko raz odczyta jej odwrotność. Odwrotność niepotrzebnie policzona zostanie 10 razy, bo tylko raz będzie użyta. Drugi pomysł polega na wyliczaniu odwrotności podczas jej pobierania. Wówczas jednak może się zdarzyć taka sytuacja, że użytkownik tylko 1 raz ustawi macierz widoku, po czym 10 razy pod rząd pobierze jej odwrotność. Wówczas znów odwrotność będzie liczona 10 razy, choć wystarczyłoby policzyć ją raz.

Leniwe wartościowanie w obydwu tych przypadkach policzy odwrotność macierzy tylko raz. Wymaga jednak pamiętania dodatkowej flagi, która będzie mówiła o tym, czy zapamiętana odwrotność jest aktualna (czy macierz oryginalna nie zmieniła się od czasu ostatniego wyliczenia jej odwrotności). Flagi tego typu to pokazane wcześniej pola z przyroskiem ,,-Is'', np. bool m_ViewInvIs. Kiedy macierz widoku, rzutowania lub obydwie z nich zmieniają się (metody SetView, SetProj, Set), wówczas wywołana zostaje metoda prywatna Changed, która zeruje flagi, unieważniając wyliczone macierze dodatkowe.

void Changed()
{
  m_ViewInvIs = false;
  m_ProjInvIs = false;
  m_ViewProjIs = false;
  m_ViewProjInvIs = false;
  // ...
}

Z kolei pobranie macierzy takiej jak ViewInv odbywa się według stałego schematu: Jeśli flaga równa się false, następują obliczenia i flaga zostaje przestawiona na true, informując że od tej pory odwrotność macierzy widoku jest policzona, zapamiętana i można ją pobierać bez ponownego liczenia, aż do chwili kiedy zmiana macierzy widoku znów ją unieważni.

const D3DXMATRIX & MatrixCamera::GetViewInv() const
{
  if (!m_ViewInvIs)
  {
    D3DXMatrixInverse(&m_ViewInv, NULL, &GetView());
    m_ViewInvIs = true;
  }
  return m_ViewInv;
}

Pozostałe macierze - ProjInv, ViewProj i ViewProjInv - są wyliczane analogicznie.

Do omówienia tutaj pozostaje jeszcze rola użytych wiele razy w pokazanym wyżej kodzie słów kluczowych const i mutable. const służy do tego, żeby obiektu klasy można było używać jako stałego, w szczególności przekazywać go jako parametr przez referencję do stałej. W takiej sytuacji nie powinno się dać zmieniać zawartości obiektu, a jedynie odczytywać jego dane. Metody SetView, SetProj, Set są wtedy niedostępne. Można używać tylko metod odczytujących dane, oznaczonych jako const - tak jak ta pokazana wyżej.

Problem jednak w tym, że kompilator C++ pilnuje, by taka metoda faktycznie nie zmieniała żadnych pól klasy, jedynie je odczytywała. Tymczasem leniwe wartościowanie powinno zostać potraktowane jako wyjątek, bo np. pobranie (a co za tym idzie być może wyliczenie) odwrotności macierzy widoku powinno być dostępne dla obiektu typu const MatrixCamera, mimo że wymaga zapisywania do pola m_ViewInv. Można to rozwiązać właśnie dzięki rzadko używanemu słowu kluczowemu C++, jakim jest mutable. Oznaczone nim pola mogą być zmieniane nawet przez metody const.

Oto przykład użycia klasy MatrixCamera:

void Funkcja1()
{
  MatrixCamera MCam;

  D3DXMATRIX View, Proj;
  D3DXMatrixLookAtLH(
    &View,                            // Out
    &D3DXVECTOR3(0.0f, 2.0f, -10.0f), // Eye
    &D3DXVECTOR3(0.0f, 0.0f, 0.0f).   // At
    &D3DXVECTOR3(0.0f, 1.0f, 0.0f));  // Up
  D3DXMatrixPerspectiveFovLH(
    &Proj,     // Out
    0.95993f,  // fovy - 55 stopni
    4.0f/3.0f, // Aspect
    1.0f,      // zn
    100.0f);   // zf

  MCam.Set(View, Proj);
  Funkcja2(MCam);
}

void Funkcja2(const MatrixCamera &MCam)
{
  // Wpisz do stałej Vertex Shadera połączoną macierz View*Proj
  g_Effect->SetMatrix("ViewProj", &MCam.GetViewProj());
}

Klasa ParamsCamera

Klasa ParamsCamera przechowuje parametry, z których powstają macierze widoku i rzutowania. Jakie to parametry, to zapewne wiesz - to wszystkie dane podawane do funkcji D3DXMatrixLookAtLH i D3DXMatrixPerspectiveFovLH. Na życzenie udostępnia te parametry (oraz inne, które na ich podstawie można wyliczyć), a także tworzy macierz widoku i rzutowania używając zawartej w jej wnętrzu klasy MatrixCamera, którą omówiliśmy wyżej.

Jeśli chodzi o parametry, z których powstaje macierz widoku, są to:

D3DXVECTOR3 m_EyePos;
D3DXVECTOR3 m_ForwardDir;
D3DXVECTOR3 m_UpDir;

EyePos to oczywiście pozycja kamery (punkt widzenia). ForwardDir to wektor jednostkowy wskazujący kierunek ,,do przodu'' (kierunek patrzenia), który stanie się osią Z układu współrzędnych kamery. Funkcja D3DXMatrixLookAtLH przyjmuje zamiast niej punkt zwany At, który pokazuje jakoby miejsce, na które kamera patrzy. Jeśli otworzysz jednak dokumentację DirectX SDK na rozdziale poświęconym tej funkcji, to zobaczysz, że coś takiego jak punkt na który patrzymy nie istnieje. Jako oś Z brany jest tylko znormalizowany wektor od punktu widzenia Eye do punktu At, czyli taki właśnie wektor kierunku patrzenia. Innymi słowy, całkowicie bez znaczenia jest, jakim konkretnie punktem jest At i jak daleko leży od punktu Eye. Liczy się tylko kierunek wektora między nimi. Dlatego moim zdaniem bardziej intuicyjne jest posługiwanie się takim wektorem kierunku patrzenia.

Oto cytat z DirectX SDK, z hasła ,,D3DXMatrixLookAtLH'', pokazujący jak tworzona jest macierz widoku:

zaxis = normal(At - Eye)
xaxis = normal(cross(Up, zaxis))
yaxis = cross(zaxis, xaxis)

 xaxis.x           yaxis.x           zaxis.x          0
 xaxis.y           yaxis.y           zaxis.y          0
 xaxis.z           yaxis.z           zaxis.z          0
-dot(xaxis, eye)  -dot(yaxis, eye)  -dot(zaxis, eye)  l

Trzeci wektor - UpDir - powinien wskazywać kierunek ,,do góry''. Zwykle podaje się tam po prostu (0, 1, 0), chyba że kamera ma się przechylać na boki, tak jak przy wychylaniu się zza rogu w strzelankach albo w czasie lotu samolotem.

Z kolei macierz rzutowania powstaje z takich parametrów:

float m_FovY;
float m_Aspect;
float m_ZNear;
float m_ZFar;

FovY to kąt widzenia w osi pionowej, w radianach. Zdania na temat jego optymalnej wartości są podzielone. Pewne jest tyle, że musi być mniejszy niż pi radianów (180 stopni). Jedni preferują mieć szersze pole widzenia i podają tam 90 stopni (oczywiście przeliczone na radiany). Jednak wtedy rysowana geometria jest nienaturalnie powyginana. Dlatego ja preferuję kąt 60 albo nawet 55 stopni. Wówczas zniekształcenia od perspektywy nie są tak bardzo widoczne.

Aspect to stosunek szerokości do wysokości pola widzenia. Na przykład jeśli gra pracuje w rozdzielczości 800 x 600 i rysuje widok 3D na całym ekranie, to należy tam podać wartość (800.0f/600.0f), co jest równe 4/3, czyli 1.33333... Dla innych rozdzielczości będzie to inna wartość, szczególnie dla monitorów typu Wide Screen. Dlatego nie można zapomnieć zmienić tego parametru, a tym samym przeliczyć od nowa macierz rzutowania (klasa ParamsCamera zrobi to drugie sama), kiedy tylko gracz zmienia w opcjach rozdzielczość ekranu.

Z-Near i Z-Far to odległość bliskiej i dalekiej płaszczyzny przycinania. Wszystkie punkty bliższe niż ZNear czy dalsze niż ZFar nie będą rysowane. Chciałoby się podać ZNear bardzo małe, a ZFar bardzo duże. O ile zwiększanie ZFar (np. do 100, 200 czy nawet 1000) w zasadzie niczemu nie szkodzi, o tyle zbyt małe ZNear powoduje, że nieliniowość przekształcenia perspektywicznego mapuje większość zakresu głębokości Z-bufora tylko na najbliższe odcinki pola widzenia, co powoduje utratę dokładności i w efekcie może dać brzydkie artefakty na obrazie. Dlatego zamiast podawać jako ZNear bardzo mały ułamek, lepiej poprzestać na 1.0, 0.5, ostatecznie 0.1. Do dokładności Z-bufora liczy się tak naprawdę stosunek odległości rysowanych punktów do ZNear.

Oto kod na ustawianie i pobieranie opisanych parametrów:

// Tworzy NIEZAINICJALIZOWANĄ
ParamsCamera() { Changed(); }
// Tworzy zainicjalizowaną
ParamsCamera(const D3DXVECTOR3 &EyePos, const D3DXVECTOR3 &ForwardDir,
  const D3DXVECTOR3 &UpDir, float FovY, float Aspect,
  float ZNear, float ZFar);

void Set(const D3DXVECTOR3 &EyePos, const D3DXVECTOR3 &ForwardDir,
  const D3DXVECTOR3 &UpDir, float FovY, float Aspect,
  float ZNear, float ZFar);
void SetEyePos(const D3DXVECTOR3 &EyePos) {
  m_EyePos = EyePos; Changed();
}
void SetForwardDir(const D3DXVECTOR3 &ForwardDir) {
  m_ForwardDir = ForwardDir; Changed();
}
void SetUpDir(const D3DXVECTOR3 &UpDir) {
  m_UpDir = UpDir; Changed();
}
void SetFovY(float FovY) {
  m_FovY = FovY; Changed();
}
void SetAspect(float Aspect) {
  m_Aspect = Aspect; Changed();
}
void SetZNear(float ZNear) {
  m_ZNear = ZNear; Changed();
}
void SetZFar(float ZFar) {
  m_ZFar = ZFar; Changed();
}
void SetZRange(float ZNear, float ZFar) {
  m_ZNear = ZNear; m_ZFar = ZFar; Changed();
}

const D3DXVECTOR3 & GetEyePos() const { return m_EyePos; }
const D3DXVECTOR3 & GetForwardDir() const { return m_ForwardDir; }
const D3DXVECTOR3 & GetUpDir() const { return m_UpDir; }
float GetFovY() const { return m_FovY; }
float GetAspect() const { return m_Aspect; }
float GetZNear() const { return m_ZNear; }
float GetZFar() const { return m_ZFar; }

Przed nami rzecz najważniejsza, czyli wyliczanie z tych parametrów docelowych macierzy widoku i rzutowania. Klasa nie przechowuje sama tych macierzy, ale wykorzystuje w tym celu zawarty w swoim wnętrzu obiekt typu MatrixCamera. Obiekt ten udostępnia na zewnątrz metodą GetMatrices. Zanim jednak go udostępni, wpisuje do niego nowe macierze taką metodą, jaką klasa MatrixCamera wylicza odwrotność macierzy widoku, rzutowania i inne dodatkowe wyniki - poprzez leniwe wartościowanie. Innymi słowy, użytkownik może zmieniać parametry takie jak pozycja kamery, kierunek patrzenia itd., a macierze zostaną wyliczone dopiero, kiedy będą potrzebne. Oto jak wygląda odpowiedni kod:

private:
  mutable MatrixCamera m_Matrices; mutable bool m_MatricesIs;
public:
  const MatrixCamera & GetMatrices() const;

(...)

const MatrixCamera & ParamsCamera::GetMatrices() const
{
  if (!m_MatricesIs)
  {
    D3DXMATRIX View, Proj;

    D3DXMatrixLookAtLH(
      &View,                          // Out
      &GetEyePos(),                   // Eye
      &(GetEyePos()+GetForwardDir()), // At
      &GetUpDir());                   // Up
    D3DXMatrixPerspectiveFovLH(
      &Proj,       // Out
      GetFovY(),   // fovy
      GetAspect(), // Aspect
      GetZNear(),  // zn
      GetZFar());  // zf

    m_Matrices.Set(View, Proj);
    m_MatricesIs = true;
  }
  return m_Matrices;
}

Chciałbym jeszcze dokładniej pomówić o wektorach. Jak widać na rys. 1 na początku artykułu, kamerę można wyobrazić jako nowy układ współrzędnych, położony gdzieś w przestrzeni sceny 3D i jakoś zorientowany (czyli posiadający swoją translację i rotację). Orientację tego układu opisuje pewna baza ortonormalna, czyli mówiąc po ludzku trzy jednostkowe, wzajmnie prostopadłe wektory. Wektor niebieski - wyznaczający dodatnią oś Z - to nic innego jak kierunek patrzenia, czyli wspomniany wyżej ForwardDir. Co z pozostałymi wektorami?

Te wektory to kierunek odpowiednio ,,w prawo'' (wektor czerwony - oś X) i ,,do góry'' (wektor zielony - oś Y). Kiedy zobaczysz na zacytowane wcześniej wzory z DirectX SDK, to przekonasz się, że macierz widoku tworzy nie co innnego, jak tylko te trzy wektory, wpisane do trzech kolumn macierzy (plus translacja w czwartym wierszu). Skoro wektory te są wpisane do kolumn macierzy widoku, a macierz ta przekształca współrzędne globalne świata do lokalnych kamery, to transpozycja jej podmacierzy 3x3 będzie opisywała dla wektorów odwrotne przekształcenie - z przestrzeni kamery do przestrzeni świata. Tak więc wektory ,,w prawo'' (nazwijmy go RightDir) i ,,do góry'' (nazwijmy go RealUpDir) można wyczytać z wierszy macierzy odwrotnej do macierzy widoku. Oczywiście można je też wyliczyć ze wzorów. Do czego te wektory mogą się przydać? - o tym przeczytasz w następnym rozdziale.

Oto w jaki sposób klasa ParamsCamera pobiera i zwraca na żądanie użytkownika te dwa wektory:

private:
  mutable D3DXVECTOR3 m_RightDir; mutable bool m_RightDirIs;
public:
  const D3DXVECTOR3 & GetRightDir() const;
  const D3DXVECTOR3 & GetRealUpDir() const;

(...)

const D3DXVECTOR3 & ParamsCamera::GetRightDir() const
{
  if (!m_RightDirIs)
  {
    // WERSJA 1
    D3DXVec3Cross(&m_RightDir, &GetUpDir(), &GetForwardDir());
    D3DXVec3Normalize(&m_RightDir, &m_RightDir);

    // WERSJA 2
    //m_RightDir = (const D3DXVECTOR3 &)GetMatrices().GetViewInv()._11;

    m_RightDirIs = true;
  }
  return m_RightDir;
}

const D3DXVECTOR3 & ParamsCamera::GetRealUpDir() const
{
  return (const D3DXVECTOR3 &)GetMatrices().GetViewInv()._21;
}

Jeśli czytałeś uważnie powyższy opis, to z pewnością zaintrygowało Cię, dlaczego mamy dwa wektory ,,do góry'' - UpDir i RealUpDir. Czym one się różnią? Różnica jest bardzo duża i nie należy ich pomylić, żeby nie powstał wredny błąd (wszystkie błedy związane z matematyką potrafią być wredne :) Wektor ,,zwykły do góry'' - UpDir - to ten, który podajemy podczas tworzenia macierzy widoku i który prawie zawsze wynosi po prostu (0, 1, 0). Jest parametrem wejściowym, podawanym do ParamsCamera. Natomiast wektor ,,prawdziwy do góry'' - RealUpDir - jest częścią bazy układu współrzędnych kamery i pokazuje prawdziwy kierunek ,,do góry'', obracający się kiedy kamera patrzy bardziej w górę lub bardziej w dół. On jest zawsze wzajemnie prostopadły do ForwardDir i RightDir. Jest parametrem wyjściowym - zostaje wyliczony. Różnicę między nimi próbuje zilustrować rys. 3.

Wektory UpDir i RealUpDir
Rys. 3. Różnica między wektorami tworzącymi macierz widoku i wektorami, które można z niej odczytać.

Klasa Camera

klasa Camera reprezentuję kamerę na najwyższym poziomie abstrakcji, tak jak chciałby widzieć ją użytkownik silnika 3D. Pracuje w trybie FPP, TPP albo jako sterowana kwaternionem. Część przechowywanych przez nią danych (szczególnie parametry rzutowania) dubluje z klasy poprzednio omówionej, bo użytkownik tak czy owak musi je podać bezpośrednio. Sposób wyliczania pozycji i orientacji kamery może już być różny, zależnie od wybranego trybu. Parametry obecne zawsze to:

D3DXVECTOR3 m_Pos;
float m_ZNear, m_ZFar;
float m_FovY;
float m_Aspect;

Pos nie oznacza przy tym pozycji kamery, ale pozycję ,,gracza'', co dla kamery w widoku TPP nie jest równoznaczne.

Dalej mamy tryb, tj. sposób opisania orientacji. Możliwe sposoby są dwa. Tryb MODE_CHARACTER to sterowanie orientacją za pomocą dwóch z kątów Eulera - nazwanych tutaj AngleY i AngleX (od nazw osi, wokół których obracają), a odpowiadających kątom Eulera nazywanym Yaw i Pitch. Tego trybu należy używać do kamery pracującej w widoku FPP (ang. First Person Perspective - perspektywa pierwszej osoby, jak w strzelankach) lub TPP (ang. Third Person Perspective - perspektywa trzeciej osoby, jak w Tomb Raider czy World of Warcraft).

Drugi tryb - MODE_QUATERNION - steruje orientacją kamery za pomocą kwaterniona. Jego warto używać, kiedy kamera swobodnie lata po świecie 3D wg jakiejś ustalonej krzywej, np. pokazując ,,cut-scenkę''. Kwaterniony mają tę zaletę, że dają się płynnie interpolować. Sama ta interpolacja nie jest jednak częścią opisywanej klasy kamery - trzeba do niej po prostu podać aktualny kwaternion.

public:
  enum MODE
  {
    MODE_CHARACTER,
    MODE_QUATERNION,
  };

private:
  MODE m_Mode;

  // ======== Parametry dla MODE_CHARACTER ========
  // Nachylenie do góry / w dół
  float m_AngleX;
  // Ten zwykły, główny obrót
  float m_AngleY;
  // Odległość kamery TPP od gracza
  float m_CameraDist;
  // ======== Parametry dla MODE_QUATERNION ========
  D3DXQUATERNION m_Orientation;

W trybie MODE_QUATERNION sprawa jest prosta. Punkt patrzenia kamery leży dokładnie tam gdzie podany Pos, a orientacją steruje bezpośrednio kwaternion Orientation. Z kolei w trybie MODE_CHARACTER można po pierwsze zmieniać orientację kamery poprzez kąty AngleX i AngleY, a po drugie oddalić kamerę od punktu Pos ,,w tył'' na odległość CameraDist, osiągając dzięki temu w prosty sposób widok TPP, taki jak w World of Warcraft. Te możliwości pokazuje rys. 4. Aby taka kamera TPP nie wchodziła w ściany zasłaniając widok na bohatera, trzeba liczyć kolizję promienia od pozycji Pos do pozycji kamery (GetParams().GetEyePos()) z geometrią mapy i odpowiednio dostosowywać odległość CameraDist.

Kamera w trybie MODE_CHARACTER - FPP lub TPP
Rys. 4. Kamera w trybie MODE_CHARACTER (FPP lub TPP) - wpływ poszczególnych parametrów.

Oto kod odpowiedzialny za wpisywanie i odczytywanie omówionych parametrów:

// Tworzy NIEZAINICJALIZOWANĄ
Camera();
// Tworzy zainicjalizowaną w trybie CHARACTER
Camera(const D3DXVECTOR3 &Pos, float AngleX, float AngleY, float CameraDist,
  float ZNear, float ZFar, float FovY, float Aspect);
// Tworzy zainicjalizowaną w trybie QUATERION
Camera(const D3DXVECTOR3 &Pos, const D3DXQUATERNION &Orientation,
  float ZNear, float ZFar, float FovY, float Aspect);

// Wypełnia od nowa wszystkie dane, ustawia tryb CHARACTER
void Set(const D3DXVECTOR3 &Pos, float AngleX, float AngleY, float CameraDist,
  float ZNear, float ZFar, float FovY, float Aspect);
// Wypełnia od nowa wszystkie dane, ustawia tryb D3DXQUATERNION
void Set(const D3DXVECTOR3 &Pos, const D3DXQUATERNION &Orientation,
  float ZNear, float ZFar, float FovY, float Aspect);

void SetPos(const D3DXVECTOR3 &Pos) { m_Pos = Pos; Changed(); }
void SetZNear(float ZNear) { m_ZNear = ZNear; Changed(); }
void SetZFar(float ZFar) { m_ZFar = ZFar; Changed(); }
void SetZRange(float ZNear, float ZFar) {
  m_ZNear = ZNear; m_ZFar = ZFar; Changed(); }
void SetFovY(float FovY) { m_FovY = FovY; Changed(); }
void SetAspect(float Aspect) { m_Aspect = Aspect; Changed(); }
void SetMode(MODE Mode) { m_Mode = Mode; Changed(); }

// Dane tylko dla MODE_CHARACTER
void SetAngleX(float AngleX) {
  m_AngleX = Min(Max(-D3DX_PI*0.5f+1e-3f, AngleX), +D3DX_PI*0.5f-1e-3f);
  Changed(); }
void SetAngleY(float AngleY) { m_AngleY = NormalizeAngle(AngleY); Changed(); }
void SetCameraDist(float CameraDist) { m_CameraDist = CameraDist; Changed(); }

// Dane tylko dla MODE_QUATERNION
void SetOrientation(const D3DXQUATERNION &Orientation) {
  m_Orientation = Orientation; Changed(); }

void Move(const D3DXVECTOR3 &DeltaPos) { SetPos(GetPos() + DeltaPos); }
void RotateX(float DeltaAngleX) { SetAngleX(GetAngleX() + DeltaAngleX); }
void RotateY(float DeltaAngleY) { SetAngleY(GetAngleY() + DeltaAngleY); }

const D3DXVECTOR3 & GetPos() const { return m_Pos; }
float GetZNear() const { return m_ZNear; }
float GetZFar() const { return m_ZFar; }
float GetFovY() const { return m_FovY; }
float GetAspect() const { return m_Aspect; }
MODE GetMode() const { return m_Mode; }

// Dane tylko dla MODE_CHARACTER
float GetAngleX() const { return m_AngleX; }
float GetAngleY() const { return m_AngleY; }
float GetCameraDist() const { return m_CameraDist; }

// Dane tylko dla MODE_QUATERNION
const D3DXQUATERNION & GetOrientation() const { return m_Orientation; }

Pozostaje już tylko odpowiedzieć na pytanie, co dalej dzieje się z tymi danymi. Odpowiedzią jest pojedyncza metoda - GetParams. Obiekt klasy Camera ma w sobie obiekt klasy ParamsCamera, a za pomocą leniwego wartościowania, w momencie pobierania tego obiektu zagnieżdżonego, wpisuje do niego odpowiednio przeliczone dane, aby on dalej mógł na podstawie tych danych udostępnić swoje dane i obiekt klasy MatrixCamera, który z kolei policzy z nich finalne macierze.

private:
  mutable ParamsCamera m_Params; mutable bool m_ParamsIs;
  void Changed() { m_ParamsIs = false; }

(...)

const ParamsCamera & Camera::GetParams() const
{
  if (!m_ParamsIs)
  {
    if (m_Mode == MODE_CHARACTER)
    {
      D3DXVECTOR3 EyePos, ForwardDir;
      D3DXVECTOR3 UpDir = D3DXVECTOR3(0.0f, 1.0f, 0.0f);

      // Wersja 1 lub 2
      //D3DXMATRIX Rot;

      // Wersja 1
      //D3DXMatrixRotationYawPitchRoll(&Rot, GetAngleY(), GetAngleX(), 0.f);

      // Wersja 2 - Rozpisane dla optymalizacji.
      //float sy = sinf(GetAngleY()), cy = cosf(GetAngleY());
      //float sp = sinf(GetAngleX()), cp = cosf(GetAngleX());
      //Rot._11 = cy;    Rot._12 = 0.0f; Rot._13 = -sy;   Rot._14 = 0.0f;
      //Rot._21 = sy*sp; Rot._22 = cp;   Rot._23 = cy*sp; Rot._24 = 0.0f;
      //Rot._31 = sy*cp; Rot._32 = -sp;  Rot._33 = cy*cp; Rot._34 = 0.0f;
      //Rot._41 = 0.0f;  Rot._42 = 0.0f; Rot._43 = 0.0f;  Rot._44 = 1.0f;
      //D3DXVECTOR3 v = D3DXVECTOR3(0.0f, 0.0f, 1.0f);

      // Wersja 1 lub 2
      //D3DXVec3TransformNormal(&ForwardDir, v, Rot);

      // Wersja 3
      SphericalToCartesian(&ForwardDir, GetAngleY() - PI_2, -GetAngleX(), 1.f);

      // FPP
      if (GetCameraDist() == 0.f)
        EyePos = GetPos();
      // TPP
      else
        EyePos = GetPos() - ForwardDir * GetCameraDist();

      m_Params.Set(EyePos, ForwardDir, UpDir, GetFovY(), GetAspect(),
        GetZNear(), GetZFar());
    }
    else // m_Mode == MODE_QUATERNION
    {
      D3DXMATRIX RotMat;
      D3DXMatrixRotationQuaternion(&RotMat, &m_Orientation);
      D3DXVECTOR3 Forward, Up;
      D3DXVec3TransformNormal(
        &Forward, &D3DXVECTOR3(0.0f, 0.0f, 1.0f), &RotMat);
      D3DXVec3TransformNormal(
        &Up,      &D3DXVECTOR3(0.0f, 1.0f, 0.0f), &RotMat);
      m_Params.Set(GetPos(), Forward, Up, GetFovY(), GetAspect(),
        GetZNear(), GetZFar());
    }

    m_ParamsIs = true;
  }
  return m_Params;
}

Jeśli chce Ci się analizować powyższy kod, zauważ, że w przypadku MODE_QUATERNION kwaternion zostaje zamieniony na macierz rotacji i ta macież służy do wyliczenia wektorów Forward i Up przekazywanych do ParamsCamera. Z kolei dla trybu MODE_CHARACER, wektor Up pozostaje zawsze równy (0, 1, 0), a wektor Forward jest wyliczany na podstawie kątów AngleY i AngleX. Na to wyliczanie są aż trzy sposoby, z czego jeden pozostał niezakomentowany.

Dodatkowo, dla wygody, klasa Camera udostępnia wprost obiekt klasy MatrixCamera w ten sposób:

public:
  const MatrixCamera & GetMatrices() const;

(...)

const MatrixCamera & Camera::GetMatrices() const
{
  return GetParams().GetMatrices();
}

Czas na przykład. Oto jak z użyciem klasy Camera zaimplementowałem kamerę FPP swobodnie latającą w przestrzeni 3D w jednym z moich programów, aby móc eksperymentować z różnymi efektami graficznymi i bez problemu oglądać je ze wszystkich stron. Najpierw zdefiniowane jest pole z kamerą:

Camera m_Camera;

W konstruktorze mojej klasy kamera zostaje zainicjalizowana:

m_Camera.Set(
  D3DXVECTOR3(0.0f, 0.0f, -10.0f), // Pos
  0.0f,   // AngleX
  0.0f,   // AngleY
  0.0f,   // CameraDist
  0.5f,   // ZNear
  100.0f, // ZFar
  DegToRad(55.0f), // FovY
  (float)BackBufferWidth / (float)BackBufferHeight); // AspectRatio

Po każdej zmianie rozdzielczości ekranu trzeba uaktualnić stosunek szerokości do wysokości pola widzenia:

void MyClass::OnResolutionChange()
{
  m_Camera.SetAspect((float)BackBufferWidth / (float)BackBufferHeight);
}

W zdarzeniu OnMouseMove dostaję przesunięcie kursora myszki w pikselach względem poprzedniej pozycji (czyli względne przesunięcie, a nie bezwzględną pozycję na ekranie). Wówczas mogę za pomocą myszki bez ograniczeń obracać kamerę takim oto prostym kodem:

void MyClass::OnMouseMove(const D3DXVECTOR2 &Pos)
{
  m_Camera.RotateY(Pos.x * 0.01f);
  m_Camera.RotateX(Pos.y * 0.01f);
}

Z kolei przemieszczanie kamery w kierunku do przodu, do tyłu, w lewo, w prawo, w górę i w dół realizuje funkcja wywoływana w każdej klatce, która liczy wektor przesunięcia na podstawie stanu wciśnięcia klawiszy: W, S, A, D, Q, E oraz dla dodatkowego klawisza przyspieszenia Shift.

void MyClass::CalcCameraMovement()
{
  D3DXVECTOR3 Move = D3DXVECTOR3(0.0f, 0.0f, 0.0f);
  if (frame::GetKeyboardKey('S'))
    Move -= m_Camera.GetParams().GetForwardDir();
  if (frame::GetKeyboardKey('W'))
    Move += m_Camera.GetParams().GetForwardDir();
  if (frame::GetKeyboardKey('D'))
    Move += m_Camera.GetParams().GetRightDir();
  if (frame::GetKeyboardKey('A'))
    Move -= m_Camera.GetParams().GetRightDir();
  if (frame::GetKeyboardKey('E'))
    Move += m_Camera.GetParams().GetUpDir();
  if (frame::GetKeyboardKey('Q'))
    Move -= m_Camera.GetParams().GetUpDir();

  if (frame::GetKeyboardKey(VK_SHIFT))
    Move *= 18.0f;
  else
    Move *= 6.0f;
  Move *= GetDeltaTime();

  m_Camera.Move(Move);
}

Trzeba pamiętać, że podczas przesuwania kamery w każdej klatce zależnie od stanu klawiszy mnożymy wektor przesunięcia razy DeltaTime, czyli czas jaki upłynął od poprzedniej klatki, a podczas obracania kamery w reakcji na ruch myszy tego nie robimy.

Wreszcie, wykorzystujemy kamerę do pobrania połączonej macierzy widoku i rzutowania, którą na podstawie podanych parametrów klasa Camera, wraz z pozostałymi klasami w niej zagnieżdżonymi, automatycznie wyliczy, ale dzięki leniwemu wartościowaniu tylko wtedy, kiedy to naprawdę jest konieczne.

ID3DXEffect *E = ...
E->SetMatrix("ViewProj", &m_Camera.GetMatrices().GetViewProj());

To by było na tyle, jeśli chodzi o moją implementację kamery. Pozostawiłem niepokazane kilka pól i metod, żeby omówić je później przy okazji, ale wszystko co najważniejsze zostało już opisane. Jeśli chciałeś tylko zobaczyć, jak zrobiłem swoją klasę kamery, właściwie możesz przerwać czytanie w tym miejscu. Ale jeśli chcesz dowiedzieć się kilku ciekawych rzeczy związanych z zastosowaniem takiej kamery w programowaniu grafiki 3D, zapraszam do lektury pozostałych trzech rozdziałów :)

Przodem do kamery

Większość elementów sceny 3D to siatki trójkątów, które można oglądać z każdej strony. Bywają jednak płaskie obrazy, które trzeba rysować w 3D. Takie obrazy warto pokazywać w ten sposób, aby były zwrócone zawsze przodem do kamery - niezależnie od jej położenia względem obiektu. Innymi słowy, muszą się obracać zawsze w kierunku punktu widzenia kamery. Dawniej, w bardzo starych grach, w ten sposób rysowano drzewa i inne złożone kształty, np. postacie wrogów w Wolfenstein 3D i pierwszej wersji Doom. Teraz nie robi się już tego w ten sposób, ale są zastosowania, w których nadal zachodzi potrzeba rysowania prostokątów zwróconych zawsze przodem do kamery. Jedno z nich to efekty cząsteczkowe.

Efekt cząsteczkowy

Jako przykład renderowania prostokątów zwróconych zawsze przodem do kamery pokażę efekt cząsteczkowy. Nie będzie to pełna implementacja - nie napisze ani słowa o tym gdzie przechowywać ani jak wyliczać pozycje, kolory, rozmiary i inne parametry cząstek. Oczekuję, że ten temat nie jest Ci obcy. W zamian pokażę, jak napisać efekt cząsteczkowy, w którym sami ręcznie narysujemy kwadraty cząstek, bez korzystania ze sprzętowego mechanizmu Point Sprites. Takie rozwiązanie ma tę przewagę, że pozwala poszczególne cząsteczki obracać (nie chodzi tu o obracanie w stronę kamery, ale o obrót w przestrzeni ekranu), a także zmieniać ich rozmiar. To pierwsze jest w Point Sprites w ogóle niedostępne, a to drugie dostępne tylko na kartach legitymujących się ,,kapsem'' D3DFVFCAPS_PSIZE.

Można to osiągnąć rysując dla każdej cząstki jej pełną geometrię, tj. 4 wierzchołki i 6 indeksów, które łączą te wierzchołki w kwadrat złożony z dwóch trójkątów. Najciekawsze jest to, że wszystkie 4 wierzchołki danej cząstki będą miały wpisaną tą samą pozycję - pozycję środka cząstki - a do czterech rogów kwadratu będzie je rozsuwał vertex shader, wykorzystując w tym celu pobrane z kamery wektory ,,w prawo'' RightDir i ,,w górę'' RealUpDir. Zobacz rys. 5.

Cząsteczka zbudowana z dwóch trójkątów
Rys. 5. Cząsteczka złożona jest z czterech wierzchołków, rozsuwanych przez vertex shader.

Do vertex shadera przekazywane są następujące parametry:

float4x4 g_WorldViewProj;
float3 g_RightDir;
float3 g_UpDir;

g_WorldViewProj to połączona macierz świata, widoku i rzutowania dla efektu cząsteczkowego. Jeśli obiekt efektu ma własne przekształcenie świata (które ustawia efekt w danej pozycji i orientacji w świecie 3D, tak że pozycje wierzchołków będą wyrażone w lokalnym układzie tego efektu), to wtedy wektory g_RightDir i g_UpDir muszą wskazywać kierunek ,,w prawo'' i ,,w górę'' pobrany z kamery, ale przekształcony z przestrzeni świata do przestrzeni lokalnej modelu. Robimy to mnożąc je przez odwrotność macierzy świata obiektu efektu cząsteczkowego.

D3DXMATRIX World = /* macierz świata tego obiektu */
D3DXMATRIX WorldInv = /* Odwrotność World - D3DXMatrixInverse */
D3DXVECTOR3 RightDir_Local, UpDir_Local;

D3DXVec3TransformNormal(
  &RightDir_Local, &Cam.GetParams().GetRightDir(),  &WorldInv);
D3DXVec3TransformNormal(
  &UpDir_Local,    &Cam.GetParams().GetRealUpDir(), &WorldInv);

Effect->SetMatrix("g_WorldViewProj",
  &(World * Cam.GetMatrices().GetViewProj()));
Effect->SetVector("g_RightDir",
  &D3DXVECTOR3(RightDir_Local.x, RightDir_Local.y, RightDir_Local.z, 1.0f));
Effect->SetVector("g_UpDir",
  &D3DXVECTOR3(UpDir_Local.x,    UpDir_Local.y,    UpDir_Local.z,    1.0f));

Jedną z rzeczy, które trzeba umieć chcąc pisać fajne efekty graficzne 3D, jest kreatywne wykorzystanie struktury wierzchołka do przenoszenia różnorodnych informacji. Struktura wierzchołka dla naszych cząsteczek będzie wyglądała tak:

struct PARTICLE_VERTEX
{
  static const DWORD FVF =
    D3DFVF_XYZ | D3DFVF_DIFFUSE | D3DFVF_TEX1 | D3DFVF_TEXCOORDSIZE4(0);

  D3DXVECTOR3 Pos;
  DWORD Color;
  D3DXVECTOR2 Tex;
  float Orientation;
  float Size;
};

Sztuczka polega tutaj na tym, że definiujemy 4-wymiarową współrzędną tekstury. Oczywiście nie ma 4-wymiarowych tekstur. To są po prostu 4 liczby, które kod naszego vertex shadera wykorzysta tak jak chce. W tym przypadku dwie pierwsze składowe (wektor Tex) to prawdziwe zwyczajne współrzędne tekstury (które dla wierzchołków cząsteczki wynoszą zawsze kolejno (0, 1), (1, 1), (0, 0), (1, 0)), trzecia liczba zdefiniowana jako Orientation to orientacja cząstki (czyli jej obrót w radianach), a czwarta liczba zdefiniowana jako Size to rozmiar cząstki (właściwie to połowa długości jej przekątnej).

Strukturze tej odpowiada taka struktura wejściowa zdefiniowana w kodzie efektu w języku HLSL:

struct VS_INPUT
{
  float3 Pos : POSITION;
  float Size : PSIZE;
  float4 Color : COLOR0;
  // x, y = TexCoord, z = Orientation, w = Size
  float4 Tex_Orientation_Size : TEXCOORD0;
};

Z kolei wyjście vertex shadera jest już całkiem normalne i nie wymaga wyjaśnienia:

struct VS_OUTPUT
{
  float4 Pos : POSITION;
  float4 Color : COLOR0;
  float2 Tex : TEXCOORD0;
};

Teraz proszę o uwagę, bo będzie rzecz najważniejsza - Jego Wydajność Vertex Shader we własnej osobie :) To właśnie tutaj dzieje się cała magia ,,rozsuwania'' wierzchołków cząstki w kierunku wektorów RightDir i UpDir oraz ich obracania. Najpierw pokażę kod, a potem postaram się dokładnie go omówić.

void vs_main(VS_INPUT In, out VS_OUTPUT Out)
{
  float2 DeltaPos = In.Tex_Orientation_Size.xy * 2 - 1; // -1..1
  float Angle = In.Tex_Orientation_Size.z;
  float Size = In.Tex_Orientation_Size.w;

  float SinAngle, CosAngle;
  sincos(Angle, SinAngle, CosAngle);

  float2 DeltaPos2;
  DeltaPos2.x = DeltaPos.x * CosAngle - DeltaPos.y * SinAngle;
  DeltaPos2.y = DeltaPos.x * SinAngle + DeltaPos.y * CosAngle;

  float3 LocalPos = In.Pos + Size * (
    g_RightDir * DeltaPos2.x +
    g_UpDir    * DeltaPos2.y);

  Out.Pos = mul(float4(LocalPos, 1), g_WorldViewProj);
  Out.Color = In.Color;
  Out.Tex = In.Tex_Orientation_Size.xy;
}

Dwie ostatnie linijki nie wzbudzają zdziwienia. VS po prostu przepisuje na wyjście otrzymane na wejściu kolor i współrzędne tekstury. Cała reszta kodu poświęcona jest obliczaniu docelowej pozycji wierzchołka. Idziemy przez kod od końca. Wyliczenie ostatecznej, docelowej pozycji cząstki na ekranie Out.Pos polega na pomnożeniu pozycji w przestrzeni lokalnej modelu LocalPos przez połączoną macierz świata, widoku i rzutowania g_worldViewProj. To też nie powinno być dla Ciebie nowe.

Skąd się bierze LocalPos? Wiemy, że wierzchołek początkowo leży w miejscu środka cząsteczki In.Pos. Naszym zadaniem będzie dodanie do jego pozycji odpowiedniego przesunięcia, które rozsunie go w prawo i w górę, czyli o DeltaPos2.x w kierunku wektora g_RightDir i o DeltaPos2.y w kierunku wektora g_UpDir. Te wartości przesunięcia DeltaPos2 powstają przez obrócenie o kąt Angle wektora DeltaPos. Całe te obliczenia z sinusem i cosinusem to powszechnie znany wzór na obracanie punktu 2D wokół środka układu współrzędnych (0, 0).

Przesunięcie początkowe DeltaPos to przesunięcie ,,w prawo'' (składowa X) i ,,do góry'' (składowa Y) przed obrotem. Ten wektor musi być różny dla poszczególnych wierzchołków cząstki, żeby mogły zostać rozsunięte w cztery strony ze swojego wspólnego punktu początkowego tworząc kwadrat. Wartości DeltaPos dla kolejnych wierzchołków cząstki muszą wynosić odpowiednio: (-1, 1), (1, 1), (-1, -1), (1, -1). Skąd je wziąć?

Nasuwa się pomysł zapisania ich jako osobne dane w strukturze wierzchołka, ale taki pomysł powinien natychmiast zostać porzucony. Wartości te możemy bowiem wyprowadzić łatwo ze współrzędnych tekstury danego wierzchołka, które również są zróżnicowane dla poszczególnych wierzchołków danej cząstki i są ułożone w taki sam sposób. Trzeba tylko przeskalować je z zakresu 0..1 do zakresu -1..1. To właśnie robi pierwsza linijka kodu shadera.

Pixel shaderowi pozostaje już tylko oteksturować otrzymane cząsteczki, pomnożyć kolor wczytany z tekstury razy kolor cząsteczki przekazany z wierzchołków i zwrócić iloczyn na wyjściu wraz z kanałem alfa, gdzie czeka na niego włączony alfa-blending.

Dla kompletności muszę jeszcze pokazać, jak wygląda w C++ wypełnianie bufora wierzchołków, indeksów oraz rysowanie. Dla uproszczenia użyjemy rysowania prosto ze wskaźnika, chociaż w porządnym kodzie należałoby raczej użyć bufora wierzchołków i indeksów. Bufor indeksów może być w puli MANAGED i można go wypełnić raz, bo pozostaje stały. Bufor wierzchołków powinien być dynamiczny.

Każdej cząstce odpowiada 6 indeksów, które budują kwadrat z 4 wierzchołków.

unsigned short Indices[PARTICLE_COUNT * 6];

for (unsigned pi = 0, vi = 0, ii = 0; pi < PARTICLE_COUNT; pi++, vi += 4)
{
  Indices[ii++] = vi;
  Indices[ii++] = vi + 1;
  Indices[ii++] = vi + 2;
  Indices[ii++] = vi + 1;
  Indices[ii++] = vi + 2;
  Indices[ii++] = vi + 3;
}

Jeśli zaś chodzi o wierzchołki, współrzędne tekstury pozostają stałe przez cały czas:

PARTICLE_VERTEX Vertices[PARTICLE_COUNT * 4];

for (unsigned pi = 0, vi = 0; pi < PARTICLE_COUNT; pi++)
{
  m_Vertices[vi++].Tex = D3DXVECTOR2(0.0f, 1.0f);
  m_Vertices[vi++].Tex = D3DXVECTOR2(1.0f, 1.0f);
  m_Vertices[vi++].Tex = D3DXVECTOR2(0.0f, 0.0f);
  m_Vertices[vi++].Tex = D3DXVECTOR2(1.0f, 0.0f);
}

Natomiast pozostałe parametry trzeba zmieniać w każdej klatce, wpisując do wszystkich czterech wierzchołków danej cząstki te same wartości.

PARTICLE_VERTEX *V2, *V = Vertices;
for (unsigned pi = 0; pi < PARTICLE_COUNT; pi++)
{
  V->Pos = /* Pozycja środka czątki pi */
  V->Color = /* Kolor i alfa cząstki pi */
  V->Size = /* Rozmiar cząstki pi */
  V->Orientation = /* Orientacja cząstki pi */

  V2 = V;
  V2++;
  V2->Pos = V->Pos;
  V2->Color = V->Color;
  V2->Size = V->Size;
  V2->Orientation = V->Orientation;
  V2++;
  V2->Pos = V->Pos;
  V2->Color = V->Color;
  V2->Size = V->Size;
  V2->Orientation = V->Orientation;
  V2++;
  V2->Pos = V->Pos;
  V2->Color = V->Color;
  V2->Size = V->Size;
  V2->Orientation = V->Orientation;

  V += 4;
}

Wreszcie, wywołanie rysujące może wyglądać tak:

g_Dev->DrawIndexedPrimitiveUP(
  D3DPT_TRIANGLELIST, // PrimitiveType
  0,                  // MinVertexIndex
  PARTICLE_COUNT * 4, // NumVertices
  PARTICLE_COUNT * 2, // PrimitiveCount
  Indices,            // pIndexData
  D3DFMT_INDEX16,     // IndexDataFormat
  Vertices,           // pVertexStreamZeroData
  sizeof(PARTICLE_VERTEX)); // VertexStreamZeroStride

Stopnie swobody

To nie koniec tematu rysowania obrazków zwróconych przodem do kamery. Zapomnijmy teraz o cząsteczkach i wyobraźmy sobie pojedynczy płaski obiekt w scenie 3D - np. drzewo. Jego narysowanie polega na rozsunięciu pozycji wierzchołków prostokąta o połowę szerokości w kierunku plus/minus ,,w prawo'' i o połowę wysokości w kierunku plus/minus ,,do góry''. Te wektory w poprzednio pokazanym kodzie pobieraliśmy wprost z kamery metodami GetRightDir i GetRealUpDir. Jeśli zastanowiłeś się wtedy, dlaczego bierzemy właśnie te wektory, czy mogłyby to być jakieś inne albo chociaż czy lepszy jest UpDir czy RealUpDir, to może być początek rozważań na temat bardziej ogólnego algorytmu wyznaczania tych dwóch wektorów wyjściowych.

Proponuję wprowadzić pojęcie liczby stopni swobody DegreesOfFreedom na określenie liczby osi, wokół których nasz obiekt może się obracać śledząc położenie kamery. Liczba stopni swobody może wynosić 0, 1, 2. Kiedy wynosi 0, wówczas płaski obiekt w ogóle się nie obraca. Innymi słowy, jest statycznym prostokątem w scenie 3D o stałych pozycjach wierzchołków. Żeby wyznaczyć te pozycje, można zapisać wśród parametrów obiektu jego własne wektory ,,w prawo'' i ,,do góry'', na których będzie rozpięta jego płaszczyzna. Te wektory nazwiemy DefinedRight i DefinedUp. Zobacz rys. 6a, na którym te wektory przedstawione są jako czerwona i zielona strzałka.

Zachowanie obiektu zależnie od liczby stopni swobody.
Rys. 6. Płaski obiek na scenie 3D i jego zachowanie zależnie od liczby stopni swobody DegreesOfFreedom.

Kiedy liczba stopni swobody DegreesOfFreedom wynosi 1, obiekt uzyskuje zdolność obracania się wokół jednej osi - tej pionowej, wyznaczonej przez jego wektor DefinedUp (pokazany na rys. 6b na zielono). Wektor DefinedRight przestaje mieć znaczenie, jako że wektor ,,w prawo'' brany jest z kamery, po to aby obiekt mógł obracać się zawsze przodem do kamery. Oczywiście będzie się obracał przodem do kamery tylko kiedy ta okrąża go dookoła w płaszczyźnie poziomej, a patrząc na niego z góry czy z dołu widoczna stanie się jego płaska natura. Ten sposób rysowania billboardów jest dobry np. do prostej realizacji drzew.

Z kolei kiedy liczba stopni swobody DegreesOfFreedom wynosi 2, wówczas obiekt może naprawdę ustawiać się zawsze przodem do kamery, niezależnie czy ta okrąża go dookoła czy patrzy na obiekt z góry albo z dołu. Obiekt obraca się wokół dwóch osi, całkowicie ignorując swoje obydwa lokalne wektory DefinedRight i DefinedUp. Zobacz rys. 6c.

Rozszerzymy te rozważania o jeszcze jedną rzecz. Mianowicie możemy zastanowić się, co tak naprawdę oznacza używane przez nas wcześniej, intuicyjne określenie ,,przodem do kamery''? Płaskie obiekty sceny, które są w zasięgu kamery, mogą znaleźć się w różnych miejscach na ekranie. Jeśli mają się obracać w stronę kamery, to jak będą zorientowane względem siebie? Są tutaj dwie możliwości. Pierwsza jest prostsza. To ta, której używaliśmy dotychczas. Jako kierunek ,,do kamery'' uważany jest kierunek, w jakim patrzy kamera (jej ForwardDir), tylko że zanegowany. W ten sposób wszystkie płaskie obiekty mają tą samą orientację. Jest też druga możliwość - dla każdego obiektu wyznaczać jego własny ,,prawdziwy'' kierunek do kamery, jako wektor od pozycji środka obiektu do pozycji punktu patrzenia kamery. Tą możliwość nazwiemy UseRealDir.

Poniższy listing zbiera wszystkie możliwości omówione w tym podrozdziale w jedną prostą do użycia funkcję. Oto znaczenie jej parametrów:

void CalcBillboardDirections(
  D3DXVECTOR3 *OutRight,
  D3DXVECTOR3 *OutUp,
  unsigned DegreesOfFreedom,
  bool UseRealDir,
  const D3DXVECTOR3 &ObjectPos,
  const D3DXVECTOR3 &DefinedRight,
  const D3DXVECTOR3 &DefinedUp,
  const D3DXVECTOR3 &EyePos,
  const D3DXVECTOR3 &CamRightDir,
  const D3DXVECTOR3 &CamRealUpDir)
{
  if (DegreesOfFreedom == 0)
  {
    *OutRight = DefinedRight;
    *OutUp = DefinedUp;
  }
  else if (DegreesOfFreedom == 1)
  {
    *OutUp = DefinedUp;

    if (UseRealDir)
    {
      D3DXVECTOR3 Forward = ObjectPos - EyePos;
      D3DXVec3Normalize(&Forward, &Forward);
      D3DXVec3Cross(OutRight, &Forward, &DefinedUp);
      *OutRight = - *OutRight;
      D3DXVec3Normalize(OutRight, OutRight);
    }
    else
      *OutRight = CamRightDir;
  }
  else // (DegreesOfFreedom == 2)
  {
    if (UseRealDir)
    {
      D3DXVECTOR3 Forward = ObjectPos - EyePos;
      D3DXVec3Normalize(&Forward, &Forward);

      // Tu Up wykorzystany tylko tymczasowo, wyliczam Right
      *OutUp = D3DXVECTOR3(0.0f, 1.0f, 0.0f);
      if (fabsf(D3DXVec3Dot(OutUp, &Forward)) > 0.99f)
        *OutUp = D3DXVECTOR3(0.0f, 0.0f, 1.0f);
      D3DXVec3Cross(OutRight, &Forward, OutUp);
      *OutRight = - *OutRight;
      D3DXVec3Normalize(OutRight, OutRight);

      // Tu wyliczam docelowe Up
      D3DXVec3Cross(OutUp, &Forward, OutRight);
      D3DXVec3Normalize(OutUp, OutUp);
    }
    else
    {
      *OutRight = CamRightDir;
      *OutUp = CamRealUpDir;
    }
  }
}

Działanie przedstawionej funkcji dla różnych ustawień najłatwiej zrozumieć obserwując rys. 7.

Billboard z różnymi ustawieniami.
Rys. 7. Zachowanie funkcji CalcBillboardDirections dla różnych ustawień.

Przycinanie frustumem

Podstawą optymalizacji w grafice 3D jest nierysowanie tego, czego nie widać. Takie odrzucanie tego co niewidoczne odbywa się na wszystkich poziomach. Sprzętowo karta graficzna robi to na poziomie pikseli (Z-Test i inne testy) oraz na poziomie trójkątów (Backface Culling). Twoim zadaniem jako programisty jest robić to samo w swoim kodzie C++ na wyższym poziomie - na poziomie całych obiektów. Najprostszą i bardzo skuteczną techniką jest odrzucanie tych obiektów, które nie są w zasięgu widzenia kamery.

Aby to zrobić, musimy mieć jakoś opisany kształt obiektu, kształt pola widzenia kamery i dysponować kodem na test kolizji między tymi dwoma bryłami geometrycznymi 3D. Gotowe funkcje na takie testy umieściłem w dołączonych plikach z kodem i opisałem na końcu tego rozdziału. Kształt obiektów zapisujemy jako proste bryły otaczające opisane na tych obiektach (ang. Bounding Volume) - np. sfery (ang. Sphere) czy prostopadłościany o krawędziach równoległych do osi układu współrzędnych (AABB - ang. Axis-Aligned Bounding Box). Pozostaje pytanie, jak wygląda i należy reprezentować kształt pola widzenia kamery.

Jeżeli kamera używa rzutowania perspektywicznego, jej pole widzenia przedstawione w układzie świata to ścięty ostrosłup o podstawie prostokąta. Nie ma eleganckiej polskiej nazwy (chłopaki z Warsztatu zaproponowali ,,ściętosłup''), a po angielsku nazywa się frustum. Jego wygląd w 3D pokazuje rys. 1 na początku artykułu, a poniższy rys. 8 przedstawia jego widok od boku wraz z zaznaczonymi parametrami.

Frustum w rzucie od boku.
Rys. 8. Frustum kamery w rzucie od boku i jego parametry.

Ponieważ kamerę na niskim poziomie opisują dwie macierze - macierz widoku i rzutowania - frustum można utworzyć właśnie z tych macierzy. Macierz widoku opisuje pozycję i orientację frustuma, a macierz rzutowania jego kształt. Spośród parametrów tej drugiej macierzy, Z-Near to odległość punktu widzenia od bliskiej płaszczyzny przycinającej, a Z-Far to jego odległość od dalekiej płaszczyzny przycinającej, czyli maksymalny zasięg widzenia. FovY to kąt widzenia w pionie. Ostatni parametr - AspectRatio - reprezentuje niewidoczny na powyższym rysunku stosunek szerokości do wysokości frustuma.

Reprezentacje frustuma

Skoro już wiemy, jak wygląda frustum, czas zastanowić się, jak zapisać go w pamięci. Nie ulega chyba wątpliwości, że do opisania tak dziwnej bryły potrzebna jest osobna struktura. Okazuje się, że można wymyślić aż trzy różne reprezentacje frustuma. Wszystkie je teraz pokażę i omówię.

Pierwsza możliwość to opisanie frustuma jako 6 płaszczyzn. Oczekuję w tym miejscu, że wiesz, jak wygląda reprezentacja płaszczyzny w 3D (chodzi o cztery współczynniki równania Ax + By + Cz + D = 0 zapisane w strukturze D3DXPLANE). Znajomość równań płaszczyzn ograniczających frustum z lewej, z prawej, z góry, z dołu, z bliska i z daleka pozwala łatwo stwierdzać kolizję różnych brył z takim frustumem. Na przykład punkt leży wewnątrz frustuma wtedy, kiedy leży po odpowiedniej stronie każdej z tych płaszczyzn. Musimy się jednak najpierw umówić co do kolejności tych płaszczyzn w tablicy oraz co do ich zwrotu. W sprawie zwrotu przyjmujemy, że płaszczyzny będą miały wektor normalny zwrócony do wnętrza frustuma. W sprawie kolejności natomiast, wszystko powinno wyjaśnić nadanie nazw poszczególnym indeksom tablicy.

struct FRUSTUM_PLANES
{
  static const unsigned PLANE_LEFT   = 0;
  static const unsigned PLANE_RIGHT  = 1;
  static const unsigned PLANE_TOP    = 2;
  static const unsigned PLANE_BOTTOM = 3;
  static const unsigned PLANE_NEAR   = 4;
  static const unsigned PLANE_FAR    = 5;

  D3DXPLANE Planes[6];

  // Tworzy niezainicjalizowany
  FRUSTUM_PLANES() { }
  // Inicjalizuje na podstawie macierzy
  FRUSTUM_PLANES(const D3DXMATRIX &WorldViewProj) { Set(WorldViewProj); }
  // Inicjalizuje na podstawie reprezentacji punktowej
  FRUSTUM_PLANES(const FRUSTUM_POINTS &FrustumPoints) { Set(FrustumPoints); }
  // Wypełnia
  void Set(const D3DXMATRIX &WorldViewProj);
  void Set(const FRUSTUM_POINTS &FrustumPoints);
  // Normalizuje płaszczyzny
  void Normalize();

  D3DXPLANE & operator [] (unsigned Index) { return Planes[Index]; }
  const D3DXPLANE & operator [] (unsigned Index) const { return Planes[Index]; }
};

Frustum w reprezentacji płaszczyznowej tworzy się na podstawie przekazanej macierzy banalnie prosto i jest to operacja bardzo szybka. Wystarczy znać magiczne wzory :) Odpowiedni kod zawiera metoda FRUSTUM_PLANES::Set(const D3DXMATRIX &WorldViewProj). Ten algorytm ma jedną ciekawą cechę. Otóż jako macierz w parametrze podać można równie dobrze: samą macierz rzutowania (frustum jest wtedy w przestrzeni kamery), macierz widoku * rzutowania (frustum jest wtedy w przestrzeni świata), jak i macierz świata danego obiektu * widoku * rzutowania (frustum jest wtedy w przestrzeni lokalnej tego obiektu).

Drugą bardzo intuicyjną reprezentacją frustuma, jako że jest on przecież bryłą wypukłą, jest zapisanie jego wierzchołków, czyli 8 punktów. Ponownie musimy umówić się co do ich kolejności w tablicy i stworzyć nową strukturę.

struct FRUSTUM_POINTS
{
  // Indeksy do tej tablicy
  // kolejno na przecięciu płaszczyzn:
  static const unsigned NEAR_LEFT_BOTTOM  = 0;
  static const unsigned NEAR_RIGHT_BOTTOM = 1;
  static const unsigned NEAR_LEFT_TOP     = 2;
  static const unsigned NEAR_RIGHT_TOP    = 3;
  static const unsigned FAR_LEFT_BOTTOM   = 4;
  static const unsigned FAR_RIGHT_BOTTOM  = 5;
  static const unsigned FAR_LEFT_TOP      = 6;
  static const unsigned FAR_RIGHT_TOP     = 7;

  D3DXVECTOR3 Points[8];

  // Tworzy niezainicjalizowany
  FRUSTUM_POINTS() { }
  // Inicjalizuje na podstawie płaszczyzn
  FRUSTUM_POINTS(const FRUSTUM_PLANES &FrustumPlanes) { Set(FrustumPlanes); }
  // Inicjalizuje na podstawie ODWROTNOŚCI macierzy View*Projection
  FRUSTUM_POINTS(const D3DXMATRIX &WorldViewProjInv) { Set(WorldViewProjInv); }
  // Wypełnia
  void Set(const FRUSTUM_PLANES &FrustumPlanes);
  void Set(const D3DXMATRIX &WorldViewProjInv);

  D3DXVECTOR3 & operator [] (unsigned Index) { return Points[Index]; }
  const D3DXVECTOR3 & operator [] (unsigned Index) const { return Points[Index]; }
};

Utworzenie frustuma w reprezentacji punktowej na podstawie macierzy widoku * rzutowania jest dość proste. Pomysł opiera się na spostrzeżeniu, że w przestrzeni po rzutowaniu rogi frustuma to po prostu wierzchołki prostopadłościanu (-1..1, -1..1, 0..1). Wystarczy więc przekształcić je z powrotem do przestrzeni świata mnożąc przez odwrotność macierzy (widoku*rzutowania), aby otrzymać pozycje wierzchołków frustuma w przestrzeni świata. Odpowiedni kod zawiera metoda FRUSTUM_POINTS::Set(const D3DXMATRIX &WorldViewProjInv).

Niestety, ta operacja jest stosunkowo powolna. Jako parametr do tej funkcji trzeba przekazać odwrotność macierzy widoku * rzutowania (czy też samej rzutowania, albo też świata * widoku * rzutowania, tak jak w przypadku tworzenia reprezentacji płaszczyznowej frustuma), a odwracanie macierzy jest jak wiadomo kosztowne obliczeniowo. Dodatkowo każde przekształcenie punktu przez macierz, która zawiera transformację perspektywiczną, wymaga wykonania trzech dzieleń sprowadzających punkt ze współrzędnych jednorodnych do zwykłych 3D, czego dokonuje funkcja D3DXVec3TransformCoord.

Dlatego, choć może się to wydawać zaskakujące, szybciej jest utworzyć z macierzy frustum w pokazanej wyżej reprezentacji płaszczyznowej, a potem na jej podstawie dopiero utworzyć reprezentację punktową. Z mojego eksperymentu wyszło, że jest to w kompilacji DEBUG 8 razy, a w kompilacji RELEASE 2 razy szybsze. Jak powstaje reprezentacja punktowa na podstawie płaszczyznowej? Algorytm polega na znalezieniu punktów przecięcia się poszczególnych płaszczyzn (przecięcie trzech płaszczyzn daje punkt). Odpowiedni kod zawiera metoda FRUSTUM_POINTS::Set(const FRUSTUM_PLANES &FrustumPlanes).

Można też napisać przekształcenie odwrotne - z reprezentacji punktowej frustuma do reprezentacji płaszczyznowej. Ten algorytm polega z kolei na znalezieniu równania każdej płaszczyzny na podstawie trzech punktów. Odpowiedni kod zawiera metoda FRUSTUM_PLANES::Set(const FRUSTUM_POINTS &FrustumPoints). Z tym kodem (i nie tylko z nim) związany jest jednak pewien kruczek. Otóż otrzymane z niego płaszczyzny nie muszą wyjść znormalizowane, a kiedy nie są znormalizowane, niektóre algorytmy operujące na takim frustumie mogą źle liczyć. Dlatego po utworzeniu frustuma w ten sposób należy jego płaszczyzny znormalizować.

Istnieje jeszcze trzeci sposób opisywania frustuma - reprezentacja radarowa. Jest dużo mniej intuicyjna, bo przechowuje po prostu zbiór przeliczonych w odpowiedni sposób parametrów widoku i rzutowania, ale za to oferuje niezwykle szybki test kolizji z punktem i sferą (wszystkie te testy omówię w następnym podrozdziale). Dokładny opis tego pomysłu można znaleźć w książce [2], a spośród materiałów dostępnych za darmo/legalnie w Sieci także w tutorialu [3] w podrozdziale Radar Approach - Testing Spheres. W poniższym kodzie jest jedna bardzo niebezpieczna pułapka. Jako wektor Up trzeba zawsze podawać wektor ,,prawdziwy do góry'', otrzymyny metodą ParamsCamera::GetRealUp i zawsze prostopadły do Forward i Up, a nie ten standardowy równy zwykle (0, 1, 0). W przeciwnym wypadku kolizje liczą się źle.

class FRUSTUM_RADAR
{
private:
  D3DXVECTOR3 m_Eye;
  D3DXVECTOR3 m_Forward;
  D3DXVECTOR3 m_Up;
  D3DXVECTOR3 m_Right;
  float m_RFactor;
  float m_UFactor;
  float m_RSphereFactor;
  float m_USphereFactor;
  float m_ZNear;
  float m_ZFar;

public:
  // Tworzy niezainicjalizowany
  FRUSTUM_RADAR() { }
  // Tworzy w pełni zainicjalizowany
  FRUSTUM_RADAR(const D3DXVECTOR3 &Eye, const D3DXVECTOR3 &Forward,
    const D3DXVECTOR3 &Up, const D3DXVECTOR3 &Right, float FovY, float Aspect,
    float ZNear, float ZFar)
  {
    Set(Eye, Forward, Up, Right, FovY, Aspect, ZNear, ZFar);
  }

  // Zwraca poszczególne pamiętane pola (FovY i Aspect nie pamięta bezpośrednio)
  const D3DXVECTOR3 & GetEye() const     { return m_Eye; }
  const D3DXVECTOR3 & GetForward() const { return m_Forward; }
  const D3DXVECTOR3 & GetUp() const      { return m_Up; }
  const D3DXVECTOR3 & GetRight() const   { return m_Right; }
  float GetZNear() const { return m_ZNear; }
  float GetZFar() const  { return m_ZFar; }

  // Zwraca dane pomocnicze
  float GetRFactor() const { return m_RFactor; }
  float GetUFactor() const { return m_UFactor; }
  float GetRSphereFactor() const { return m_RSphereFactor; }
  float GetUSphereFactor() const { return m_USphereFactor; }

  // Ustawia poszczególne pola
  void SetEye    (const D3DXVECTOR3 &Eye)     { m_Eye = Eye; }
  void SetForward(const D3DXVECTOR3 &Forward) { m_Forward = Forward; }
  void SetUp     (const D3DXVECTOR3 &Up)      { m_Up = Up; }
  void SetRight  (const D3DXVECTOR3 &Right)   { m_Right = Right; }
  void SetZNear(float ZNear) { m_ZNear = ZNear; }
  void SetZFor (float ZFar)  { m_ZFar = ZFar; }
  void SetFovAndAspect(float FovY, float Aspect);

  // Kompletnie wypełnia
  void Set(const D3DXVECTOR3 &Eye, const D3DXVECTOR3 &Forward,
    const D3DXVECTOR3 &Up, const D3DXVECTOR3 &Right, float FovY, float Aspect,
    float ZNear, float ZFar)
  {
    SetProjection(FovY, Aspect, ZNear, ZFar); SetView(Eye, Forward, Up, Right);
  }
  // Wypełnia jedną połówkę danych
  void SetProjection(float FovY, float Aspect, float ZNear, float ZFar);
  // Wypełnia drugą połówkę danych
  void SetView(const D3DXVECTOR3 &Eye, const D3DXVECTOR3 &Forward,
    const D3DXVECTOR3 &Up, const D3DXVECTOR3 &Right);
};

void FRUSTUM_RADAR::SetFovAndAspect(float FovY, float Aspect)
{
  float FovY_half = FovY * 0.5f;
  float FovY_half_tan = tanf(FovY_half);
  float FovY_half_tan_aspect = FovY_half_tan * Aspect;

  m_UFactor = FovY_half_tan;
  m_RFactor = FovY_half_tan_aspect;

  m_USphereFactor = 1.f / cosf(FovY_half);
  m_RSphereFactor = 1.f / cosf(atanf(FovY_half_tan_aspect));
}

void FRUSTUM_RADAR::SetProjection(float FovY, float Aspect,
  float ZNear, float ZFar)
{
  m_ZNear = ZNear;
  m_ZFar  = ZFar;

  SetFovAndAspect(FovY, Aspect);
}

void FRUSTUM_RADAR::SetView(const D3DXVECTOR3 &Eye, const D3DXVECTOR3 &Forward,
  const D3DXVECTOR3 &Up, const D3DXVECTOR3 &Right)
{
  m_Eye = Eye;
  m_Forward = Forward;
  m_Up = Up;
  m_Right = Right;
}

Kolizje z frustumem

Pożytek z frustuma jest taki, żeby można było testować z nim kolizję bryły otaczającej jakiś obiekt. Jeśli kolizja nie zachodzi, to znaczy, że obiekt jest poza polem widzenia kamery i można go nie renderować. W tym podrozdziale opiszę kod funkcji testujących kolizję różnych prostych brył 3D z różnymi reprezentacjami frustuma. Po szczegóły odsyłam do kodu w dołączonych plikach Camera.hpp i Camera.cpp.

Funkcja sprawdzająca, czy punkt 3D należy do wnętrza frustuma, nazywa się PointInFrustum. Dla reprezentacji płaszczyznowej frustuma algorytm polega na wstawieniu punktu do równania każdej płaszczyzny i w ten sposób sprawdzeniu, czy punkt leży po dodatniej stronie wszystkich 6 płaszczyzn. Dostępna jest też bardzo wydajna, przeciążona wersja tej funkcji używająca reprezentacji radarowej.

Podstawowa funkcja sprawdzająca, czy prostopadłościan AABB koliduje z frustumem, to BoxToFrustum_Fast. Pomysł, na którym jest oparta, polega na sprawdzeniu, czy choć fragment prostopadłościanu leży wewnątrz frustuma. Ponieważ AABB jest bryłą wypukłą, trzeba sprawdzić czy któryś z jego wierzchołków leży we frustumie. Zastosowana jest tu jednak sztuczka pochodząca książki [4], która pozwala dla każdej płaszczyzny frustuma testować nie wszystkie 8 wierzchołków prostopadłościanu, ale tylko jeden - ten najbardziej wysunięty w stronę, w którą zwrócony jest wektor normalny danej płaszczyzny.

Ta funkcja, mimo swojego sprytu i wydajności, ma też jedną drobną wadę. Otóż istnieje przypadek szczególny, kiedy stwierdza kolizję mimo, że tak naprawdę jej nie ma. Przykład w rzucie od góry pokazuje rys. 9. Najczęściej nie jest to jednak problemem - ten przypadek jest rzadki, a funkcja testująca kolizję wykorzystywana do eliminowania obiektów poza zasięgiem widzenia nie musi być w 100% dokładna - naraysowanie raz na jakiś czas obiektu którego jednak nie widać nie zaszkodzi.

Przypadek szczególny kolizji frustuma z AABB.
Rys. 9. Fałszywy pozytywny wynik testu kolizji frustuma z AABB.

Na wypadek, gdyby jednak potrzebny był dokładny test, dostępna jest też funkcja BoxToFrustum. W swoje implementacji wykonuje najpierw opisany wyżej prosty test, a kiedy ten stwierdzi kolizję, upewnia się co do tej kolizji stosując twierdzenie o osiach rozdzielających - SAT (ang. Separating Axis Theorem) [5]. W skrócie twierdzenie to mówi, że dwie figury (2D) / bryły (3D) wypukłe nie kolidują ze sobą, kiedy istnieje prosta (2D) / płaszczyzna (3D) taka, że cała pierwsza bryła znajduje się po jednej jej stronie, a cała druga bryła po drugiej stronie. Dlatego w tej funkcji testującej kolizję frustuma z AABB potrzebna jest dodatkowo reprezentacja punktowa frustuma. Opcjonalnie można ją podać jako parametr, jeśli już jest wyliczona. W przypadku podania NULL funkcja sama sobie ją wyliczy. Kod zawiera też przeciążoną wersję funkcji testującą kolizję AABB z frustumem w reprezentacji radarowej, napisaną na podstawie [2].

Funkcja BoxInFrustum zwraca true, kiedy podany AABB w całości zawiera się (a nie tylko koliduje) z frustumem podanym w reprezentacji płaszczyznowej. Jej algorytm jest bardzo prosty - wystarczy upewnić się, że wewnątrz frustuma leży wszystkie 8 wierzchołków danego prostopadłościanu.

Kolizja sfery z frustumem to funkcja SphereToFrustum_Fast. Jej implementacja jest podobna do sprawdzania czy punkt leży wewnątrz frustuma, ponieważ punkt to tak jakby sfera o promieniu 0. Wstawienie pozycji punktu do równania (znormalizowanej) płaszczyzny daje w wyniku liczbę, której znak mówi po której stronie płaszczyzny znajduje się punkt, a wartość bezwzględna to odległość tego punktu od płaszczyzny. Wystarczy więc porównać odległość środka sfery od poszczególnych płaszczyzn frustuma z promieniem tej sfery.

Funkcja ta jest podatna na szczególny przypadek, w którym może zwrócić fałszywy pozytywny wynik, na tej samej zasadzie jak ,,szybka'' wersja funkcji do kolizji frustuma z AABB. Dlatego w podobny sposób powstałą funkcja dokładna - SphereToFrustum, która oprócz tego testu wykonuje dodatkowy test algorytmem SAT, używając do niego reprezentacji punktowej frustuma.

Wreszcie, dostępna jest też przeciążona wersja funkcji SphereToFrustum przyjmująca frustum w reprezentacji radarowej. To jest właściwie kwintesencja wykorzystania reprezentacji radarowej - test jest bardzo szybki. Implementacja tej funkcji uwzględnia dodatkowe poprawki, które pominął artykuł w książce [2], ale opisuje je artykuł [3].

Sprawdzenie, czy sfera leży w całości wewnątrz frustuma, to funkcja SphereInFrustum. Jej algorytm jest prosty. Sfera leży wewnątrz frustuma opisanego 6 znormalizowanymi płaszczyznami wtedy i tylko wtedy, gdy środek tej sfery leży po dodatniej stronie każdej z tych płaszczyzn, w odległości nie mniejszej niż sfery.

Funkcja ClassifyFrustumToPlane też jest bardzo prosta. Klasyfikuje ona bryłę frustuma względem podanej płaszczyzny, zwracając liczbę dodatnią kiedy frystum leży po dodatniej stronie płaszczyzny, liczbę ujemną kiedy leży po ujemnej stronie płaszczyzny i zero, kiedy płaszczyzna przecina frustum. Frustum musi być podany w reprezentacji punktowej, a test polega oczywiście na sprawdzeniu, po której stronie płaszczyzny leżą te wierzchołki i czy wszystkie po tej samej.

Funkcji TriangleInFrustum właściwie w ogóle nie trzeba opisywać. Testuje ona, czy trójkąt leży w całości wewnątrz frustuma i robi to sprawdzając, czy wewnątrz frustuma leżą wszystkie jego 3 wierzchołki. Funkcja testująca, czy trójkąt przecina frustum - TriangleToFrustum - jest już nieco bardziej skomplikowana. Jej algorytm opiera się na SAT. Potrzebuje w tym celu najpierw przetestować, czy wszystkie wierzchołki trójkąta leżą po ujemnej stronie każdej z płaszczyzn frustuma. Jeśli tak, kolizja na pewno nie zachodzi. Jeśli nie, to dla pewności musi sprawdzić też, czy wszystkie wierzchołki frustuma leżą po jednej stronie płaszczyzny, do której należy trójkąt. Do tego potrzebna jest reprezentacja punktowa frustuma (można ją podać lub pozostawić do samodzielnego wyliczenia funkcji) oraz wyznaczenie płaszczyzny trójkąta (również można ją podać lub funkcja ją wyliczy).

Wreszcie, ,,najwyższym szczeblem ewolucji'' funkcji do kolizji jest test frustuma z drugim frustumem. Do czego taki test może się przydać, skoro dziwaczna bryła, jaką jest frustum, opisuje wyłącznie pole widzenia kamery? Można w ten sposób sprawdzać na przykład, czy dwaj gracze w grze sieciowej (albo gracz i postać sterowana przez AI) widzą jakiś wspólny fragment przestrzeni. Innym zastosowaniem jest sprawdzenie, czy w polu widzenia gracza jest cokolwiek, co znajduje się w zasięgu światła typu Spot. Choć światło takie świeci raczej na kształt stożka, to przy braku pod ręką funkcji do testowania kolizji ze stożkiem można go przybliżyć opisanym na nim frustumem o podstawie kwadratu (AspectRatio=1). Funkcja testująca kolizję dwóch frustumów wbrew pozorom nie jest skomplikowana i również opiera się na SAT. Potrzebne są dla obydwu frustumów reprezentacje zarówno płaszczyznowe, jak i punktowe. Dwa frustumy nie kolidują, jeśli wszystkie wierzchołki jednego z frustumów leżą po ujemnej stronie którejś z płaszczyzn drugiego.

To były testy kolizji różnych brył z frustumem. Oczywiście można ich wymyślić dużo więcej - na przykład test z dowolną bryłą wypukłą, z dowolnie zorientowanym prostopadłościanem (OBB - ang. Oriented Bounding Box) itd. Osobną kategorię stanowią testy brył poruszających się, które oprócz swojego kształtu mają wektor mówiący o kierunku i prędkości ruchu. Funkcje do takich testów zwracają parametr t - czas kolizji (albo dwa czasy - rozpoczęcia i zakończenia kolizji) wyrażone w wielokrotnościach długości wektora ruchu.

Przykładem takiego testu jest funkcja SweptSphereToFrustum sprawdzająca kolizję poruszającej się sfery z frustumem. Jej imeplementację opracowałem na podstawie [6]. Dokładnego omówienia tego typu testów nie zaplanowałem jednak w tym artykule. Wspomnę tylko, że mogą się przydać na przykład do sprawdzania, czy dany obiekt rzuca cień na fragment sceny widoczny dla kamery (kierunkiem ruchu sfery otaczającej obiekt jest wówczas kierunek padania światła).

Rzucanie promienia

Częstym problemem, na który natrafiają początkujący programiści gier 3D, jest określanie, na co gracz wskazał myszką. Na płaszczyźnie dwuwymiarowej sprawa jest stosunkowo prosta. W przestrzeni 3D nie robi się tego podobnie - sprawa ogromnie się komplikuje. Problem polega na tym, że nie można, ot tak, zamienić punktu 2D odpowiadającego pozycji kursora myszki na ekranie, na jakiś konkretny punkt 3D w przestrzeni świata wirtualnej sceny. Dodanie trzeciego wymiaru powoduje, że wskazany myszką punkt staje się promieniem.

Promień (ang. Ray) to półprosta w przestrzeni 3D. Zobacz rys. 10. Nie wprowadzimy dla niego osobnej struktury C++. Promień opisywany będzie po prostu jako dwie wartości typu D3DXVECTOR3. Pierwsza to punkt początkowy zwany RayOrig (od Origin - źródło), a druga to wektor kierunku RayDir (od Direction - kierunek). Sprawdzenie, jaki obiekt 3D użytkownik wskazał myszką, jest jak strzelanie laserem. Polega najpierw na utworzeniu promienia w przestrzeni świata 3D na podstawie pozycji kursora, a następnie policzeniu kolizji tego promienia z obiektami w scenie.

Kolizja promienia z obiektem 3D.
Rys. 10. Promień jako punkt początkowy i wektor kierunku oraz jego kolizja z obiektem 3D.

Jedną z nieopisanych wcześniej możliwości klasy Camera jest tworzenie promienia na podstawie podanej pozycji kursora myszy. Dokonuje tego przedstawiona niżej metoda CalcMouseRay. Jako pozycję kursora trzeba podać do niej współrzędne sprowadzone do przedziału 0..1 i rozpoczynające się od lewego górnego rogu obszaru klienta okna programu. Innymi słowy, jeśli zdarzenia od myszki otrzymujesz przez komunikat WinAPI WM_MOUSEMOVE, musisz otrzymane współrzędne podzielić odpowiednio przez szerokość i wysokość obszaru klienta w pikselach, któremu odpowiada zwykle szerokość i wysokość Back-Buffera. Zakładam tutaj, że Viewport, w którym prezentowana jest scena 3D, pokrywa cały obszar Back-Buffera.

Algorytm polega na znalezieniu dwóch punktów w przestrzeni po rzutowaniu odpowiadających wskazanemu na ekranie miejscu, a potem przekształceniu ich do przestrzeni świata. Rzutowanie perspektywiczne sprowadza widoczny obszar do kostki o wymiarach X=-1..1, Y=-1..1, Z=0..1. Otrzymane współrzędne kursora trzeba więc poddać przekształceniu: X z 0..1 do -1..1, a Y z 0..1 do 1..-1 (Y trzeba odwrócić, ponieważ w 3D rośnie do góry). Jako trzecią współrzędną oznaczającą głębokość Z wpisujemy do pierwszego punktu 0, a do drugiego 1.

Dalej jest pomnożenie tych dwóch punktów przez odwrotność macierzy widoku * rzutowania, co przekształca je do przestrzeni świata. Wtedy punkt początkowy promienia RayOrig jest po prostu pierwszym z tych punktów, a kierunek promienia RayDir to kierunek do punktu pierwszego do drugiego.

void Camera::CalcMouseRay(D3DXVECTOR3 *OutRayOrig, D3DXVECTOR3 *OutRayDir,
  float MouseX, float MouseY) const
{
  D3DXVECTOR3 PtNear_Proj = D3DXVECTOR3(
    MouseX * 2.f - 1.f,
    (1.f - MouseY) * 2.f - 1.f,
    0.f);
  D3DXVECTOR3 PtFar_Proj = D3DXVECTOR3(PtNear_Proj.x, PtNear_Proj.y, 1.f);

  const D3DXMATRIX & ViewProjInv = GetMatrices().GetViewProjInv();

  D3DXVECTOR3 PtNear_World, PtFar_World;
  D3DXVec3TransformCoord(&PtNear_World, &PtNear_Proj, &ViewProjInv);
  D3DXVec3TransformCoord(&PtFar_World,  &PtFar_Proj,  &ViewProjInv);

  *OutRayOrig = PtNear_World;
  *OutRayDir = PtFar_World - PtNear_World;
  D3DXVec3Normalize(OutRayDir, OutRayDir);
}

Mając promień w przestrzeni świata możemy policzyć jego kolizje z obiektami na scenie. Jeśli wystarczy przybliżony test, można sprawdzić kolizje tylko z bryłami otaczającymi te obiekty - np. sferami czy prostopadłościanami AABB. Jeśli potrzebny jest dokładny test, warto najpierw sprawdzić kolizję z prostą bryłą otaczającą dany obiekt, a jeśli kolizja zachodzi, dopiero testować promień kontra poszczególne trójkąty siatki.

Do takiego testu promień musi być w tym samym układzie współrzędnych, co obiekt, z którym testujemy kolizję. To z resztą ogólna zasada w matematyce - porównywanie dwóch punktów czy wektorów w różnych układach współrzędnych nie ma sensu. Dlatego przydatna może być taka konstrukcja: Testuj promień w przestrzeni świata z bryłami otaczającymi obiekty sceny, wyrażonymi również w przestrzeni świata. Jeśli zachodzi kolizja, przekształć promień do przestrzeni lokalnej danego obiektu i wywołaj jego metodę, która sprawdzi dokładną kolizję tego promienia z trójkątami siatki tego obiektu, które zwykle też są wyrażone w przestrzeni lokalnej.

Przekształcenie promienia do innego układu współrzędnych jest proste. Trzeba tylko pamiętać, by do transformacji punktu początkowego użyć funkcji do przekształcania punktów, a do transformacji wektora kierunku użyć funkcji do wektorów (która nie wykonuje translacji). Oto przykład:

case WM_MOUSEMOVE:
  {
    int MouseX = LOWORD(lParam);
    int MouseY = HIWORD(lParam);
    float MouseX_F = (float)MouseX / (float)PresentParams.BackBufferWidth;
    float MouseY_F = (float)MouseY / (float)PresentParams.BackBufferHeight;

    D3DXVECTOR3 RayOrig_World, RayDir_World;
    Camera1.CalcMouseRay(
      &RayOrig_World, &RayDir_World,
      MouseX_F, MouseY_F);

    for (unsigned i = 0; i < Objects.GetCount(); i++)
    {
      float RayT;
      if (RayToSphere(RayOrig_World, RayDir_World,
        Objects[i].GetBoundingSphereCenter(),
        Objects[i].GetBoundingSphereRadius(),
        &RayT) && RayT >= 0.0f)
      {
        // Jest ogólna kolizja

        D3DXVECTOR3 RayOrig_Local, RayDir_Local;
        D3DXVec3TransformCoord(&RayOrig_Local, &RayOrig_World,
          Objects[i].GetWorldInvMatrix());
        D3DXVec3TransformNormal(&RayDir_Local, &RayDir_World,
          Objects[i].GetWorldInvMatrix());
        if (Objects[i]->LocalRayCollision(RayOrig_Local, RayDir_Local, &RayT)
          && RayT >= 0.0f)
          // Jest dokładna kolizja
      }
    }
  }
  break;

Jak wygląda taka funkcja do liczenia kolizji promienia z jakimś obiektem 3D? Stwierdza ona zwykle nie tylko czy jest albo nie ma kolizji, ale wylicza też parametr zwany t, który mówi o odległości początku kolizji. Odległość ta wyrażona jest w wielokrotnościach długości wektora kierunku promienia RayDir, a kiedy ten jest znormalizowany, to jest prawdziwą odległością w przestrzeni świata.

Inaczej można spojrzeć na promień jak na poruszający się punkt. Punkt RayOrig to pozycja początkowa punktu, a wektor RayDir to jego prędkość, czyli przesunięcie na sekundę. Wówczas otrzymywana wartość t to czas, po jakim nastąpi kolizja tego punktu z obiektem, w sekundach.

Osobno określić trzeba, co się dzieje wtedy, kiedy początek promienia wypada wewnątrz testowanej bryły. Warto wtedy zwrócić pozytywny wynik testu i T=0. Często trzeba tą sytuację w szczególny sposób uwzględnić w algorytmie. Jeszcze inny przypadek jest, kiedy promień przecina bryłę ,,od tyłu'', czyli jako półprosta jej nie przecina, ale przecina ją prosta do której promień należy. Często ta sytuacja wynika sama z obliczeń i zwraca rezultat pozytywny, dając w wyniku t mniejsze od zera.

Dołączony kod zawiera zestaw funkcji do liczenia kolizji promienia z różnymi prostymi bryłami 3D. RayToBox liczy kolizję promienia z prostopadłościanem AABB, RayToSphere ze sferą, RayToPlane z płaszczyzną, RayToTriangle z trójkątem, a RayToFrustum z frustumem. Algorytmy i wzory na tego typu obliczenia można próbować wyprowadzić samemu z układu równań (np. kolizja promienia ze sferą to rozwiązywanie równania kwadratowego) lub znaleźć w książkach takich jak [1], [4] czy serii Graphics Gems. Ogromną bazę odnośników do miejsc w literaturze, w których opisane są algorytmy na testy między różnymi rodzajami brył 3D, zawiera strona [7].

Załącznik

Pobierz pliki:
Camera.hpp
Camera.cpp

Bibliografia

  1. Fletcher Dunn, Ian Parberry, 3D Math Primer for Graphics and Game Development, Wordware Publishing, 2002.
  2. Frank Puig Placeres, Improved Frustum Culling, w: Kim Pallister, Game Programming Gems 5, Charles River Media, 2005.
  3. Antonio Ramires Fernandes, View Frustum Culling Tutorial, Lighthouse 3D, http://www.lighthouse3d.com/opengl/viewfrustum/.
  4. Stefan Zerbst, Oliver Duvel, 3D Game Engine Programming, Course Technology PTR, 2004.
  5. Raigan Burns, Mare Sheppard, Collision Detection and Response, http://www.harveycartel.org/metanet/tutorials/tutorialA.html.
  6. PracticalPSM, NVIDIA Corporation, w: NVIDIA SDK 9.5
  7. 3D Object Intersection, http://www.realtimerendering.com/int/.
Adam Sawicki
05.06.2008
[Download] [Dropbox] [pub] [Mirror] [Privacy policy]
Copyright © 2004-2019