Raytracing

Prowadzący: Paweł Marczewski

YwPskWK.png

Opis

Raytracing (śledzenie promieni) to prosta, ale efektowna metoda generowania fotorealistycznych obrazów. Pisząc raytracer stosunkowo łatwo jest zaimplementować efekty takie jak odbicia, cienie, przezroczystość czy kolorowe światła. Mamy również satysfakcję napisania całego systemu od zera, nie korzystając z procedur OpenGLa czy innego silnika graficznego.

Program zajęć

  • Podstawy, rysowanie obiektów na ekranie - kula, dysk, wielokąt
  • Światła, model oświetlenia (ambient, diffuse)
  • Cienie
  • Odbicia
  • Inne (co się zmieści) - tekstury, wygładzanie krawędzi, bump-mapping, optymalizacje

Na początek omówimy daną fazę projektu, przeliczymy co należy na tablicy, a potem trzeba będzie to zakodować. Dostarczę kod szkieletowy, na którym będzie można budować (nie będzie bardziej skomplikowany niż "narysuj piksel na ekranie, zapisz obrazek na dysk").

Wymagania

  • Komputer (chociaż programowanie w parze z kimś innym też pewnie ma sens).
  • Znajomość C++ w stopniu pozwalającym na implementację algorytmów i struktur danych. Wybieram C++, ponieważ liczę na jego największą popularność - jeśli znasz inny język lepiej, napisz; zobaczymy, co da się zrobić.
  • Podstawy geometrii obliczeniowej - pojęcia takie jak iloczyn skalarny czy równanie prostej. Macierze raczej się już nie pojawią.

Zadania kwalifikacyjne

Na rozwiązania czekam do 7 lipca pod adresem moc.liamg|zcramwp#moc.liamg|zcramwp.

Matematyka

1. Dane są dwie proste na płaszczyźnie (jako współrzędne punktów A, B, C, D, takich, że odcinek AB leży na jednej, a CD na drugiej). Wyprowadź wzór na punkt przecięcia tych prostych.

2. Teraz w przestrzeni (współrzędne trójwymiarowe): mamy płaszczyznę (jako współrzędne niewspółliniowych punktów ABC) oraz prostą (współrzędne punktów DE). Wyprowadź wzór na punkt przecięcia prostej z płaszczyzną.

3. Jak sprawdzić, czy znaleziony punkt znajduje się wewnątrz trójkąta? Tzn.: mamy współrzędne punktów ABC, oraz punktu F znajdującego się na tej samej płaszczyźnie, co ABC. Zaproponuj warunek pozwalający sprawdzić, czy punkt F znajduje się wewnątrz trójkąta ABC.

Programowanie

Wszystkie dane są liczbami całkowitymi. Ponieważ raczej będziemy pisać w C++, oczekuję rozwiązań w tym języku - ale jeśli znasz inny język lepiej, napisz; zobaczymy, co da się zrobić.

4. (łatwe) Dane jest N odcinków na prostej - tzn. na wejściu jest N, a następnie N par liczb x1, x2: 1 <= N <= 100 000, 0 <= x1 <= x2 < 1 000 000. Napisz program, który wypisuje największą liczbę odcinków, które nakładają się w jakimś punkcie (odcinki są domknięte, więc mogą nakładać się końcami). Przykład:

  • Wejście:
5
0 10
2 3
3 4
5 6
1 2
  • Wyjście:
3
(w punkcie 2 nakładają się trzy odcinki).

5. (trudne) To samo zadanie dla prostokątów na płaszczyźnie - tzn. na wejściu jest N, a następnie N czwórek x1, y1, x2, y2: 1 <= N <= 100 000, 0 <= x1 <= x2 < 1 000 000, 0 <= y1 <= y2 < 1 000 000. Napisz program, który wypisuje największą liczbę prostokątów, które się nakładają (prostokąty są domknięte, więc mogą nakładać się brzegami i rogami). Przykład:

niPZJPp.png
  • Wejście:
4
1 1 3 3
2 2 6 7
5 5 8 9
4 3 6 5
  • Wyjście:
3
(w punkcie (5, 5) nakładają się trzy prostokąty).
O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License