Raytracing

Prowadzący

 Paweł Marczewski (pwmarcz@gmail.com)


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ęć

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

Zadania kwalifikacyjne

Na rozwiązania czekam do 7 lipca pod adresem pwmarcz@gmail.com.

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:


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).