Własny silnik graficzny. Część II: detekcja kolizji.

30.11.2010 - Robert Kraus
TrudnośćTrudnośćTrudnośćTrudność

Reprezentacja sceny

Scena zawiera ona zbiót sfer, zbiór trójkątów, kamerę oraz źródło światła. W konstruktorze wczytujemy tekstury, tworzymy przy ich pomocy materiały z teksturami, a następnie tworzymy obiekty sceny (sfery i trójkąty).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
struct scene {
  std::vector<sphere> spheres; // zbiór sfer 
  std::vector<triangle> triangles; // zbiór trójkątów
  lightSrc light; // punktowe źródło światła
  camera cam; // kamera
 
  scene(camera c) : cam(c), light(lightSrc(vec3(0.0f, 2.0f, 2.0f), yellow)) {
    // wczytanie tekstur
    colorMap* tex1 = loadColorMap("ice.png");
    colorMap* tex2 = loadColorMap("marble.png");
    vectorMap* nMap1 = loadVectorMap("waterNormals.jpg");
    vectorMap* nMap2 = loadVectorMap("brickNormals.jpg");
 
    // tworzenie materiałów zależnych od tekstur
    material* rStone = new material(redStone, tex1, NULL);
    material* gStone = new material(greenStone, tex1, NULL);
    material* bStone = new material(blueStone, tex1, NULL);
    material* marble1 = new material(yellowStone, tex2, NULL);
    material* marble2 = new material(yellowStone, tex2, nMap2);
    material* water = new material(darkBlueGlass, NULL, nMap1);
 
    // tworzenie obiektów sceny
    triangles.push_back(triangle(
      vec3(-4.0f, 0.0f,  2.0f),  // v1
      vec3( 4.0f, 0.0f,  2.0f),  // v2
      vec3( 0.0f, 0.0f, -4.0f),  // v3
      vec2(0.0f, 0.0f),          // v1 na teksturze
      vec2(0.5f, 1.0f),          // v2 na teksturze
      vec2(1.0f, 0.0f),          // v3 na teksturze
      water
    ));
    spheres.push_back(sphere(vec3(-1.0f,0.5f, 0.0f), 0.5f, rStone));
    spheres.push_back(sphere(vec3(-0.5f,1.3f,-0.2f), 0.5f, marble1));
    spheres.push_back(sphere(vec3( 0.0f,0.5f, 0.0f), 0.5f, gStone));
    spheres.push_back(sphere(vec3( 0.5f,1.3f,-0.2f), 0.5f, marble2));
    spheres.push_back(sphere(vec3( 1.0f,0.5f, 0.0f), 0.5f, bStone));
    spheres.push_back(sphere(vec3(-0.3f,0.65f, 0.8f), 0.2f, &pureGlass));
    spheres.push_back(sphere(vec3( 0.3f,0.45f, 0.8f), 0.2f, &pureGlass));
  }
};

Szukanie najbliższego najbliższego przecięcia

Szukamy najbliższej sfery, w którą uderza promień, wywołując procedurę $ intersect $ dla wszystkich sfer w scenie i wybieramy tą, dla której wynik procedury $ intersect $ jest najmniejszy. Analogicznie robimy dla trójkątów.

1
2
3
4
5
6
7
8
9
10
11
12
13
// szukanie najbliższej sfery
inline hit nearestSphere(ray::i r, scene& s) {
  float nearest(undefined);  // najbliższe znalezione przecięcie
  nat id(0);                 // indeks najbliższej sfery
  for (nat i = 0; i < s.spheres.size(); i++) { // przeglądamy wszystkie sfery
     float t = intersect(s.spheres[i], r); // obliczenie odległości
     if (t < nearest) { // czy obiekt jest bliżej od ostatniego najbliższego
       nearest = t;
       id = i;
     }
  }
  return (nearest != infinity) ? hit(s.spheres[id], nearest, r) : hit();
}

Mając najbliższy trójkąt i najbliższą sferę porównujemy ich odległości od źródła promienia i wybieramy obiekt z mniejszą odległością.

1
2
3
4
5
inline hit nearestHit(ray::i r, scene& s) {
  hit hitT = nearestTriangle(r, s);
  hit hitS = nearestSphere(r, s);
  return hitT.t < hitS.t ? hitT : hitS;
}

Optymalizacja

Nietrudno się domyślić, że jeśli śledząc każdy promień będziemy wykonywali test przecięcia z wszystkimi obiektami sceny w celu znalezienia obiektu, z którym zderzy się promień, to będzie to mówiąc wprost lekka przesada. Można to zrobić lepiej, np. poprzez zorganizowanie zbioru obiektów w pewną strukturę danych. Jest to bardzo ważne, gdyż szacuje się, że od 80% do 90% czasu działania proramu śledzącego promienie zajmuje własnie testowanie kolizji.

Jest wiele struktur danych przeznaczonych do przyspieszania śledzenia promieni, my zajmiemy się jedną z nich, będzie to kd-drzewo (ang. kd-tree) powszechnie uważaną za jedną z najlepszych. Struktura ta ma dość prostą definicję: każdy węzeł wewnętrzny drzewa reprezentuje płaszczyznę podziału sceny (która do każdej z osi układu jest równoległa lub prostopadła), natomiast w liściach drzewa znajduję się elementy sceny. Przyjrzyjmy się 2-wymiarowej wersji takiego drzewa.

Wyobraźmy sobie, że na powyższym rysunku każdy kwadrat oznacza pewien obiekt. Rysunek (A) przedsawia scenę zawierającą 20 obiektów bez podziału. Śledząc promień musielibyśmy wykonać test przecięcia dla wszystkich 20 obiektów. Na rysunku (B) dzielimy przestrzeń na dwie części pionową prostą, na rysunku (C) dzielimy każdą z tych dwóch części jeszcze raz poziomymi odcinkami, itd. Na rysunku (D) mamy ostatecznie podział prostymi na 3 poziomach oraz promień o pewnym położeniu i kierunku ruchu. Widzimy dokładnie, w który kwadrat trafi nasz promień. Komputer nie jest tak bystry, musimy mu jakoś pomóc. Pod rysunkiem (D) znajduje się wizualizacja kd-drzewa odpowiadającego podziałowi z rysunku (D). Zakolorowane węzły są tymi które odwiedziliśmy szukając najbliższego obiektu. Podsumowując zamiast testowania przęcięcia z wszystkimi dwudziestoma obiektami wykonaliśmy trzy decyzje odnośnie kierunku przechodzenia drzewa i tylko jeden test przecięcia z obiektem. To jeszcze nie robi wrażenia, ale wyobraźmy sobie, że nasza scena zawiera $ 2^{24} = 16777216 $ obiektów. Przy dobrze zbudowanym kd-drzewie możemy liczbę przecięć zredukować z $ 2^{24} $ do zaledwie kilku plus około 24 decycje o kierunku przechodzenia w drzewie, to już jest coś! Teraz czas na złe wieści, niestety budowanie tak dobrego kd-drzewa nie jest zadaniem banalnym. Program, który do tej pory napisaliśmy zawiera małą scenę, więc takie kd-drzewo nie jest mu potrzebne. W przyszłości rozbudujemy scenę i wtedy dowiemy się jak zbudować taką strukturę danych.

Część I    Część II    Część III    Część IV   

5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com