Raycasting, siatka promieni

0

Witam.

Próbuję napisać prosty silnik raycastingowy, wyświetlający grafikę pseudo-3D (coś podobnego napędza np. Wolfensteina 3D). W skrócie polega to na tym, że z pozycji obserwatora (gracza) wystrzeliwuje się promienie (linie proste) w danym kierunku i pod odpowiednim kątem (zależnym od orientacji gracza) i na podstawie tego w co promienie trafiły, rysuje się klatkę obrazu wyświetlaną na ekranie.

Obrazek poglądowy:

TR1

Gdzie zielona kropka tam jest obserwator. Tutaj patrzy dokładnie na północ (w kierunku zielonej kreski), zatem jego orientacja na mapie to 270 stopni. Pierwszy promień z lewej "wystrzeliwany" jest pod kątem 240 stopni, a pierwszy od prawej pod kątem 300 stopni, czyli pole widzenia wynosi 60 stopni. Wyznaczam sobie współrzędne pixeli końcowych lewego i prawego promienia, następnie odczytuję współrzędne wszystkich, kolejnych pixeli, znajdujących się między nimi w linii prostej (oznaczone zieloną kreską). Następnie do tak odczytanych pixeli wysyłam kolejne promienie (tyle promieni, ile pixeli), czego efektem jest ten oto ładny trójkącik powyżej.

Problem mam tego rodzaju, że taki ładny trójkącik wychodzi mi tylko dla orientacji obserwatora równej 90, 180, 270 i 360 stopni. Przy kątach pośrednich, wychodzi mi coś takiego:

title

Skutkuje to tym, że w przypadku trafienia w jakiś obiekt, informacja zwrotna z promieni nie narysuje tego obiektu w 100% poprawnie, tylko właśnie z dziurami, z uwagi na widoczne na obrazku niedokładności trafień (a to problem, bo obiekt pokryty jest teksturą, a nie jednolitym kolorem). Wiem, że to wynika z zaokrągleń i bywa tak, że np. 2 promienie uderzają w ten sam pixel, dajmy na to o współrzędnych (200, 100), potem żaden nie trafia w (201,100), tylko od razu w (202, 100), przez co powstaje luka i ten pixel nie zostanie narysowany. Myślałem o wyznaczaniu promieni drogą interpolacji, ale problem w tym, że ja chcę uniknąć odczytywania pełnych ścieżek dla wszystkich promieni (np. algorytmem Bresenhama), bo to po prostu za wolne.

Ja robię to tak, że wysyłam promień pod konkretną współrzędną (równą maksymalnej odległości widzenia obserwatora, w tym wypadku 200), a następnie wyznaczam jego funkcję liniową i sprawdzam, czy doszło do kolizji (szukając punktu przecięcia) między tym promieniem, a potencjalnym obiektem, który powinien zostać narysowany (np. ścianą). To dużo szybsze, niż sprawdzanie pixel po pixelu (dla każdego promienia!), czy doszło do trafienia w jakiś obiekt.

Czy ktoś ma jakiś pomysł, jak to rozwiązać? Nie pytam o kod, czy gotowe rozwiązanie programistyczne, tylko samą koncepcję lub algorytm.

0

Jak klepałem klon Wolfensteina 3D to te promienie miały przypisany pewien kąt który określał które kolumny pikseli były renderowane na podstawie jego danych, a więc nie było tak że 1ray = 1px. Proponuję też tak zrobić - po prostu w wyniku zaokrągleń niektóre promienie wyrenderują ci dwie kolumny, inne jedną. Dobrze to widać jak zmniejszysz gęstość promieni.

0
Świetny Kot napisał(a):

Jak klepałem klon Wolfensteina 3D to te promienie miały przypisany pewien kąt który określał które kolumny pikseli były renderowane na podstawie jego danych, a więc nie było tak że 1ray = 1px. Proponuję też tak zrobić - po prostu w wyniku zaokrągleń niektóre promienie wyrenderują ci dwie kolumny, inne jedną. Dobrze to widać jak zmniejszysz gęstość promieni.

Dziękuję za odpowiedź.

Dokładnie tak robię. Każdy promień odpowiada jednej kolumnie. Dlatego właśnie to pseudo-3D a nie prawdziwe 3D, bo cały świat ma uproszczoną geometrię (jednakowe sześciany). Silnikowi wystarczy pozycja obiektu, a resztę sam sobie "dopowiada" (wysokość obiektu, szerokość, kąty nachylenia jego ścian względem podłoża itd). Technologia, w której 1 pixel odpowiada 1 promieniowi to ray tracing i o ile mi wiadomo, nawet dziś nie ma komputera, który by to uciągnął w jakiejś grze, choć efekty daje zacne :).

title

Tyle, że mój problem nadal zostaje aktualny, bo w wyniku zaokrągleń - dokładnie tak jak piszesz - niektóre kolumny są przeskakiwane i nie wiem jak temu zaradzić. Próbowałem robić też tak, że liczba promieni była stała, a każdy promień miał przypisany swój stały kąt "wystrzeliwania" względem orientacji gracza. Np. mając pole widzenia 60 stopni, dzieliłem go przez liczbę promieni (u mnie 320, jak w oryginalnym Wolfensteinie 3D), a następnie każdemu promieniowi przypisywałem wyliczony w ten sposób kąt (obliczenia w radianach dla większej precyzji). No ale co z tego, skoro potem punkty końcowe i tak trzeba zaokrąglić do pełnych pixeli i wszystko się powtarzarzało (tj. powraca przeskakiwanie).

To jak sobie poradziłeś z tym problemem "przeskakiwania" kolumn? Przy teksturowaniu jest to niedopuszczalne.

0
Crow napisał(a):
Świetny Kot napisał(a):

Jak klepałem klon Wolfensteina 3D to te promienie miały przypisany pewien kąt który określał które kolumny pikseli były renderowane na podstawie jego danych, a więc nie było tak że 1ray = 1px. Proponuję też tak zrobić - po prostu w wyniku zaokrągleń niektóre promienie wyrenderują ci dwie kolumny, inne jedną. Dobrze to widać jak zmniejszysz gęstość promieni.

Dziękuję za odpowiedź.

Dokładnie tak robię. Każdy promień odpowiada jednej kolumnie. Dlatego właśnie to pseudo-3D a nie prawdziwe 3D, bo cały świat ma uproszczoną geometrię (jednakowe sześciany). Silnikowi wystarczy pozycja obiektu, a resztę sam sobie "dopowiada" (wysokość obiektu, szerokość, kąty nachylenia jego ścian względem podłoża itd). Technologia, w której 1 pixel odpowiada 1 promieniowi to ray tracing i o ile mi wiadomo, nawet dziś nie ma komputera, który by to uciągnął w jakiejś grze, choć efekty daje zacne :).

title

Tyle, że mój problem nadal zostaje aktualny, bo w wyniku zaokrągleń - dokładnie tak jak piszesz - niektóre kolumny są przeskakiwane i nie wiem jak temu zaradzić. Próbowałem robić też tak, że liczba promieni była stała, a każdy promień miał przypisany swój stały kąt "wystrzeliwania" względem orientacji gracza. Np. mając pole widzenia 60 stopni, dzieliłem go przez liczbę promieni (u mnie 320, jak w oryginalnym Wolfensteinie 3D), a następnie każdemu promieniowi przypisywałem wyliczony w ten sposób kąt (obliczenia w radianach dla większej precyzji). No ale co z tego, skoro potem punkty końcowe i tak trzeba zaokrąglić do pełnych pixeli i wszystko się powtarzarzało (tj. powraca przeskakiwanie).

To jak sobie poradziłeś z tym problemem "przeskakiwania" kolumn? Przy teksturowaniu jest to niedopuszczalne.

Zaokrąglałem to tak żeby nie było szczelin między kolejnymi paskami (jak siebie znam to pewnie zaokrąglałem w dół wszystko i nie renderowałem ostatniego piksela w zakresie bo to był region kolejnego paska). Przy odpowiedniej gęstości teksturowanie też wychodziło spoko (chociaż coś źle przeliczyłem i miałem przez pewien czas swastyki nie w tę stronę co trzeba). Przyznam szczerze że szczegółów nie pamiętam bo to było w okolicach 2010 roku ("po co komuś kontrola wersji" - głupszy dawny ja), ale jakieś zaokrąglenia na pewno rozwiązywały problem - pozostaje kombinować. Generalnie jak coś lekko się rozciągnie albo lekko skurczy to nie jest to wielka tragedia biorąc pod uwagę rozdzielczość tekstur z tamtych czasów.

0

No tylko jak to zaokrąglić?

Zrobiłem na szybko metodę z przesuwaniem promieni o pewien kąt i mam taki kod:

FUNKCJE:

function SetPointByAngle(Angle: Real): TPoint;
begin
  Result.X:= PlayerPos.X + Round(PlayerRadius * Cos(Angle));
  Result.Y:= PlayerPos.Y + Round(PlayerRadius * Sin(Angle));
end;

Podaję tylko kąt, a powyższy kod na podstawie pozycji gracza wystrzeliwuje promień o odpowiedniej długości (PlayerRadius - tutaj na stałe 200) pod tym właśnie katem i zwraca mi współrzędne końca tego promienia.

KOD WŁAŚCIWY:

Ustawienia początkowe:

AngleStep:= DegToRad(60) / 320;

AngleStep zawiera przeskok między kolejnymi promieniami. Skoro promienie mają pokryć pole widzenia 60 stopni i jest ich 320, to dzielę 60 na 320 (przeliczone na radiany) i mam wartość przeskoku między kolejnymi promieniami.

Przy wciśnięciu strzałki w prawo:

PlayerAngle:= PlayerAngle + DegToRad(1);
RayAngle:= PlayerAngle - DegToRad(30);

{Najpierw zwiększa kąt nachylenia gracza o 1 stopień (czyli mamy obrót w prawo o 1 stopień).
Następnie ustawia kąt dla pierwszego promienia od lewej (zawsze o 30 stopni miej niż obecna orientacja gracza).}

  for I:= 1 to 320 do
    begin
      Ray:= SetPointByAngle(RayAngle);
      RayAngle:= RayAngle + AngleStep;
    end;

{W pętli oblicza kąty dla wszystkich 320 promieni, gdzie każdy kolejny przyjmuje wartość poprzedniego, a następnie zostaje zwiększony o wartość przeskoku. Mając kąt każdego z promieni, wyznaczam współrzędne jego końca.}

Efekt jak na obrazku załączonym w pierwszym poście, czyli pełno luk. Jak temu zaradzić? Jak inaczej to mogę zaokrąglić?

0

Jak zrobisz realnie 1px == 1ray to nic nie trzeba chyba zaokrąglać...? Tylko że ten jeden piksel to musi być z obrazka wynikowego, nie z danych...

0
koszalek-opalek napisał(a):

Jak zrobisz realnie 1px == 1ray to nic nie trzeba chyba zaokrąglać...? Tylko że ten jeden piksel to musi być z obrazka wynikowego, nie z danych...

No właśnie trzeba. Bo przecież jeżeli mam pozycję gracza opisaną współrzędną (X, Y) i z niej wystrzeliwuję promień o określonej długości (tutaj na stałe 200) i pod określonym kątem, to ten promień będzie miał zawsze jakiś początek (tutaj zawsze w pozycji X, Y gracza) i jakiś koniec. No i ten właśnie koniec również wyrażony jest przez jakaś współrzędną (X, Y). No a skoro tak, to przecież nie obejdzie się bez zaokrąglenia do pełnego pixela, prawda?

Współrzędną końca promienia wyliczam z tej funkcji:

function SetPointByAngle(Angle: Real): TPoint;
begin
  Result.X:= PlayerPos.X + Round(PlayerRadius * Cos(Angle));
  Result.Y:= PlayerPos.Y + Round(PlayerRadius * Sin(Angle));
end;

Rachunki zawsze wychodzą z przecinkami, a przecież pixeli z przecinkami nie ma, więc trzeba zaokrąglać. Tu właśnie leży problem, że czasem 2 promienie uderzają w 1 pixel, potem w sąsiedni pixel nie uderza żaden promień, tylko dopiero w kolejny.

Widać to na tym obrazku poglądowym:

title

Żółtym kolorem oznaczyłem które pixele niebieskiego kwadratu zostaną narysowane. Widać wyraźnie, że jego odczytana powierzchnia ma sporo luk, bo trafienia są nieregularne (mimo że każdy promień dzieli dokładnie taka sama wartość przeskoku, równa 60 / 320 stopni). Wiem, że to można rozwiązać przez interpolację, ale to wymaga obliczeń dla wszystkich pixeli składowych każdego promienia, co byłoby strasznie wolne, nawet przy dzisiejszych komputerach. W obecnej wersji mojego algorytmu interesuje mnie tylko punkt końcowy promienia (wyliczany z funkcji powyżej), obliczona na jego podstawie funkcja liniowa dla tego promienia, a następnie ewentualne punkty przecięcia promienia z różnymi obiektami, które mogą mu potencjalnie stanąć na drodze.

0
Crow napisał(a):

Widać wyraźnie, że jego odczytana powierzchnia ma sporo luk, bo trafienia są nieregularne (mimo że każdy promień dzieli dokładnie taka sama wartość przeskoku,
równa 60 / 320 stopni). Wiem, że to można rozwiązać przez interpolację, ale to wymaga obliczeń dla wszystkich pixeli składowych każdego promienia, co byłoby strasznie wolne,
nawet przy dzisiejszych komputerach.

Chyba nie doceniasz dzisiejszych komputerów. Ani nawet takich 20-letnich. Inna sprawa czy takie uśrednienie wartości byłoby wizualnie ładne, ale to już trzeba by ekspermentalnie sprawdzić.

1

Myśle że masz złe podejście do problemu, generujesz X promieni co jakąś odległość przez co niektóre pixele nie są wypełniane. Spróbuj dla każdego pixela ustalić jaki jest jego promień. W ten sposób każdy pixel ma swój promień i siłą rzeczy musi w coś trafić, pozbędziesz sie luk.

Podobnie jest z algorytmem obrotu obrazka o kąt alfa, jeżeli weźmiemy docelowy obrazek i każdy jego piksel obrócimy, a następnie umieścimy w obrazku docelowym, to powstaną luki ponieważ niektóre pixele trafiają jeden na drugi. Jeżeli jednak weźmiemy obrazek docelowy i spróbujemy obrócić każdy jego pixel o kąt -alfa to uzyskamy jego pozycję w obrazku źródłowym, tym samym każdemu pixelowi docelowemu przypiszemy pixel ze źródła i pozbędziemy się luk.

Tutaj masz analogiczny problem.

0
xxx_xx_x napisał(a):

Myśle że masz złe podejście do problemu, generujesz X promieni co jakąś odległość przez co niektóre pixele nie są wypełniane. Spróbuj dla każdego pixela ustalić jaki jest jego promień. W ten sposób każdy pixel ma swój promień i siłą rzeczy musi w coś trafić, pozbędziesz sie luk.

Podobnie jest z algorytmem obrotu obrazka o kąt alfa, jeżeli weźmiemy docelowy obrazek i każdy jego piksel obrócimy, a następnie umieścimy w obrazku docelowym, to powstaną luki ponieważ niektóre pixele trafiają jeden na drugi. Jeżeli jednak weźmiemy obrazek docelowy i spróbujemy obrócić każdy jego pixel o kąt -alfa to uzyskamy jego pozycję w obrazku źródłowym, tym samym każdemu pixelowi docelowemu przypiszemy pixel ze źródła i pozbędziemy się luk.

Tutaj masz analogiczny problem.

Przy rotacji wiem jak to działa, tylko to raczej nie znajdzie zastosowania tutaj. Wtedy musiałbym rekonstruować promienie na podstawie ich wszystkich pixeli składowych i dodatkowo wykrywać kolizje z otoczeniem na zasadzie:

Czy ten pixel - wchodzący w skład promienia - w coś trafił?
TAK - odczytaj informację zwrotną
NIE - sprawdź następny pixel

I to powtórzone 320 razy (co najmniej, bo chciałbym spróbować przystosować tą metodę renderowania do wyższych rozdzielczości, a więc większej ilości promieni). Nie wspominając, że szczerze mówiąc nie wiem jak miałbym na podstawie pixela ustalać jego przynależność do danego promienia.

0

Nie o to chodzi, dla każdego ekranowego pixela jesteś w stanie wygenerować jego promień 3D i ten wektor staje się twoim promieniem do raycastu, reszta działania jest taka sama jak do tej pory.

Tutaj przykład jak można kliknięcie myszki na ekranie 2d przekształcić w wektor 3d.
https://gamedev.stackexchange.com/questions/8974/how-can-i-convert-a-mouse-click-to-a-ray

Jeszcze raz przeczytałem twój post i chyba źle cie zrozumiałem... nie chcesz robić silnika do raycastu tylko chcesz analizować widocznośc obiektów raycastem?

Raycast dla Wolfenstein był robiony na mapie 2d nie na obiektach 3d, http://lodev.org/cgtutor/raycasting.html#Introduction

0
xxx_xx_x napisał(a):

Nie o to chodzi, dla każdego ekranowego pixela jesteś w stanie wygenerować jego promień 3D i ten wektor staje się twoim promieniem do raycastu, reszta działania jest taka sama jak do tej pory.

Tutaj przykład jak można kliknięcie myszki na ekranie 2d przekształcić w wektor 3d.
https://gamedev.stackexchange.com/questions/8974/how-can-i-convert-a-mouse-click-to-a-ray

Jeszcze raz przeczytałem twój post i chyba źle cie zrozumiałem... nie chcesz robić silnika do raycastu tylko chcesz analizować widocznośc obiektów raycastem?

Raycast dla Wolfenstein był robiony na mapie 2d nie na obiektach 3d, http://lodev.org/cgtutor/raycasting.html#Introduction

Właśnie staram się zrobić coś jak w Wolfensteinie 3D (jeden promień to jedna kolumna obrazu). Tylko czy można to zrobić inaczej, niż przez ustalenie widoczności (tego w co promienie trafiają)?

1

Ten przykład, który podesłałem dokładnie pokazuje że dla każdej kolumny ekranu musi zostać wyznaczony promień. Nie będziesz w stanie wystrzelić X promieni i później ich zmapować na ekran bez dużej straty dokładności. Jeżeli chcesz mieć rozwiązanie jak w wolfensteinie musisz odwrócić logikę.

for(int x = 0; x < w; x++) . // każda kolumna ekranu 
    {
      //calculate ray position and direction
      double cameraX = 2*x/double(w)-1; //x-coordinate in camera space  <- przeniesienie kolumny ekranu na przestrzeń kamery "3d"
      double rayPosX = posX;
      double rayPosY = posY;
      double rayDirX = dirX + planeX*cameraX;
      double rayDirY = dirY + planeY*cameraX;
0
xxx_xx_x napisał(a):

Ten przykład, który podesłałem dokładnie pokazuje że dla każdej kolumny ekranu musi zostać wyznaczony promień. Nie będziesz w stanie wystrzelić X promieni i później ich zmapować na ekran bez dużej straty dokładności. Jeżeli chcesz mieć rozwiązanie jak w wolfensteinie musisz odwrócić logikę.

for(int x = 0; x < w; x++) . // każda kolumna ekranu 
    {
      //calculate ray position and direction
      double cameraX = 2*x/double(w)-1; //x-coordinate in camera space  <- przeniesienie kolumny ekranu na przestrzeń kamery "3d"
      double rayPosX = posX;
      double rayPosY = posY;
      double rayDirX = dirX + planeX*cameraX;
      double rayDirY = dirY + planeY*cameraX;

Spróbowałem to zrobić tak, jak opisali to w podlinkowanym przez ciebie arcie. To znaczy każdy promień zapisałem jako wektor, a potem dla każdego wykonałem rotację za pomocą macierzy obrotu. Oto efekt:

title

Czerwony trójkąt to wyjściowa siatka promieni. Zielony to siatka już po rotacji (na obrazku o 120 stopni).

TYPY:

{Promień}

type
  TRay = record
    P1, P2 :TPoint;
  end;

FUNKCJE:

{Odczytanie wektora na podstawie promienia}

function ReadVector(Ray: TRay): TPoint;
begin
  Result.X:= (Ray.P2.X - Ray.P1.X);
  Result.Y:= (Ray.P2.Y - Ray.P1.Y);
end;

{Macierz Obrotu}

function RotateVectorByAngle(Vector: TPoint; Angle: Integer): TPoint;
begin
  Result.X:= Round((Vector.X * Cos(DegToRad(Angle))) - (Vector.Y * Sin(DegToRad(Angle))));
  Result.Y:= Round((Vector.X * Sin(DegToRad(Angle))) + (Vector.Y * Cos(DegToRad(Angle))));
end;

{Wyznaczanie współrzędnych końca promienia za pomocą wektora}

function SetPointByVector(Vector: TPoint): TPoint;
begin
  Result.X:= Center.X + Vector.X;
  Result.Y:= Center.Y + Vector.Y;
  //Center to stała TPoint, zawierająca współrzędne środka układu.
end;

KOD WŁAŚCIWY:

procedure TForm1.Button1Click(Sender: TObject);
var
  Ray: array [1..220] of TRay;
  Vector: array [1..220] of TPoint;
  I: Integer;
  EndPoint_X: Integer;
begin
  
//BEFORE ROTATION

  EndPoint_X:= Center.X - (Length(Ray) div 2);

  for I:= 1 to 220 do
    begin
      Ray[I].P1:= Point(Center.X, Center.Y);
      Ray[I].P2:= Point(EndX, 100);

      Vector[I]:= ReadVector(Ray[I]);

      Inc(EndPoint_X, 1);
    end;

  //AFTER ROTATION

  for I:= 1 to 220 do
    begin
      Vector[I]:= RotateVectorByAngle(Vector[I], 120);
      Ray[I].P2:= SetPointByVector(Vector[I]);
    end;
end;

Z kodu wklejonego przez ciebie nie chcę korzystać, bo go po prostu nie rozumiem (zwłaszcza że jest w języku, którego nie ogarniam). A mi nie chodzi o to, żeby działało, tylko o to, żeby zrozumieć dlaczego i jak działa.

0
Crow napisał(a):

Właśnie staram się zrobić coś jak w Wolfensteinie 3D (jeden promień to jedna kolumna obrazu). Tylko czy można to zrobić inaczej, niż przez ustalenie widoczności (tego w co promienie trafiają)?

Jasne, że można to zrobić inaczej. Na przykład nie robić raycastingu tylko renderować obraz tak jak to robią prawie wszystkie gry 3D, czyli teksturować wielokąty z użyciem bufora głębi.
Nawet nie trzeba wiedzieć jak to dokładnie działa, bo Direct3D/OpenGL zrobi to za ciebie...

0
Azarien napisał(a):
Crow napisał(a):

Właśnie staram się zrobić coś jak w Wolfensteinie 3D (jeden promień to jedna kolumna obrazu). Tylko czy można to zrobić inaczej, niż przez ustalenie widoczności (tego w co promienie trafiają)?

Jasne, że można to zrobić inaczej. Na przykład nie robić raycastingu tylko renderować obraz tak jak to robią prawie wszystkie gry 3D, czyli teksturować wielokąty z użyciem bufora głębi.
Nawet nie trzeba wiedzieć jak to dokładnie działa, bo Direct3D/OpenGL zrobi to za ciebie...

No wiem, ale ja nie celuję w prawdziwe 3D, tylko właśnie pseudo 3D :).

0

Ok to inaczej, twoje zadanie to wykonanie projekcji kolumny ekranu na jej wektor.
Kolumna jest w 1D, wektor na który tłumaczysz jest w 2D. W tym celu trzeba wykonać odwrotność operacji jaką wykonujesz w momencie przenoszenia 2D na 1D.

Zwykle UPROSZCZONA formuła wygląda tak:
x' = width/2 - planeY * x/y;
Gdzie:
x' to kolumna ekranu,
width to szerokość ekranu
(x, y) to punkt 2D
planeY to odległość do płaszczyzny rzutowania.

Odwrotność tej formuły to :
x = y * (width/2 - x') / planeY

przykładowo (width = 320, planeY = 256) :
(20, 40) => x' = 160 - (256 * 20)/ 40 => x' = 32 <- to jest kolumna na ekranie

Teraz w drugą stronę mamy kolumnę : 32 parametry jak wyżej, potrzebujemy Y, możemy wybrać dowolną wartość np 40 co oznacza że w wyniku powinniśmy dostać 20.
x = 40 * (160 - 32) / 256 => x = 20

Konwersja z 1D do 2D działa.

Możemy teraz wykonać konwersje każdego punktu ekranu na wektor 2D, jako Y użyjemy długości promienia jaka nas interesuje np 100 (nie będzie to rzeczywista długość wektora!)


for(int x=0; x<width; x++) {
    double rayEndY = 100.0;
    double  rayEndX =  rayEndY * (width/2 - x) / 256.0;
    double rayStartX = 0.0;
    double rayStartY = 0.0;
}

Ok tylko te obliczenia zakładają że kamera znajduje się w pozycji (0,0) i patrzy w kierunku (0, 1);

Co w przypadku ruchomej kamery?
Składamy operacje i tyle

Kamera składa się z dwóch operacji

  1. Przesunięcia
  2. Rotacji

Czyli każdy punkt w naszym 2D zostaje potraktowany operacją:
P' = (P + T) * R;

Gdzie T to (-cameraPositionX, -cameraPositionY), natomiast R to rotacja o kont "alfa" kamery

Jeżeli chcemy przenieść nasz wektor do pozycji świata to musimy odwrócić formułę :
R' = rotacja o kont (-alfa)
T' = (cameraPositionX, cameraPositionY)
P = (P' * R') + T'

Po wykonani tych operacji nasze promienie znajdą się w przestrzeni świata. Na tak przekształconym promieniu wykonujemy test kolizji z interesującymi nas obiektami.
Jeżeli mamy więcej niż jedną kolizję to wybieramy najbliższą.
Tutaj uwaga(!) do rysowania nie możemy posłużyć się długością promienia ponieważ uzyskamy efekt w stylu "fish eye", musimy wykonać rzut promienia na wektor kamery za pomocą iloczynu skalarnego wektorów.
Dopiero długość tego wektora powinna zostać użyta do renderowania.

0
xxx_xx_x napisał(a):

Ok to inaczej, twoje zadanie to wykonanie projekcji kolumny ekranu na jej wektor.

Eeee....? Przecież każda kolumna ekranu jest tylko punktem, jak mam z niego zrobić wektor?

Kolumna jest w 1D, wektor na który tłumaczysz jest w 2D. W tym celu trzeba wykonać odwrotność operacji jaką wykonujesz w momencie przenoszenia 2D na 1D.

Ale po co mam przenosić ekran z 1D do 2D?

Chodzi o takie przeniesienie z rzutu 1D (na górze) do 2D (na dole)?

title

Z samego opisu nie jestem w stanie wywnioskować jaką operację masz na myśli.

Umiem wyrenderować klatkę gotowego obrazu (robiłem testy z nieruchomą kamerą, zawsze skierowaną pod kątem 90 stopni, gdzie promienie nie tworzą luk i wszystko działało poprawnie). Przeniesienie na ekran tego, w co trafiły promienie nie sprawia mi problemu, tylko właśnie nie wiem jak mam poprawnie przeliczać te trafienia. Na podstawie twojego opisu nie jestem w stanie wywnioskować, jak rzutowanie wektorów (jakiego na jaki?) ma mi w tym pomóc :(.

0

Tak jak napisałem wyżej jedna kolumna na ekranie przekłada sie na jeden wektor idący od kamery w przestrzeń 2D.
2D to przestrzeń, którą renderujesz. Jeżeli wyliczysz ten wektor to uzyskasz własnie prawidłowy raycast dla tej kolumny.

https://en.wikipedia.org/wiki/Ray_tracing_(graphics)

Eye Point - pozycja kamery
Siatka to ekran.
Zielony punkt na siatce to pixel ekranu, wektror V to to co musisz uzyskać - czyli ray dla tego pixela ekranu.

W twoim przypadku nie chcesz liczyć tego per pixel, tylko per kolumna (odpada ci jeden wymiar), ale zasada jest taka sama.

To co opisałem post wcześniej to przełożenie tego z ilustracji na przestrzeń 2D(imitacja przestrzeni 3D) i 1D (ekran - ponieważ bazujemy na jednym wymiarze ekranu - kolumnach).

0

Obrazek bardzo pomógł, chyba załapałem, dzięki :).

Napisałem sobie obrót planu o kąt w taki sposób:

title

Niebieska linia to oczywiście plan (o długości 320 pixeli). Obrót następuje przez rotację dwóch punktów (czerwone kwadraty), wokół osi (kwadrat różowy). Od osi do końcowych punktów planu prowadzę wektory (kolor zielony), a potem oba przemnażam przez macierz obrotu. Niestety ta metoda nie działa, bo plan się po prostu rozlatuje. To znaczy już po jednym obrocie o pełny kąt (360 stopni), jego długość maleje do około 300 jednostek, a potem jeszcze bardziej (aż całkowicie... imploduje).

Każdy obrót to kolejne zaokrąglenia i kicha. Wydaje mi się, że powinienem chyba zrobić to tak, że mam jakby literkę T, gdzie "daszkiem" jest mój plan, a "nóżką" kierunek, w jakim zwrócony jest gracz. Zakładam, że powinienem obracać tylko jeden wektor, to jest właśnie "nóżkę", a "daszek" (jako przyczepiony na stałe pod kątem 90 stopni), powinien się ruszać razem z nim. Tylko jak to zrobić.

Jak mogę wyznaczyć nowy kierunek wektora ("daszka"), bez obracania go o jakiś kąt, a jedynie mając jego dane przed obrotem, a także dane przed i po obrocie wektora "nóżki"? Po obrocie mogę wyznaczyć jego punkt początkowy i długość, ale co z kierunkiem? Wiem też, że iloczyn skalarny obu wektorów musi być przy prostopadłości równy 0, ale jakiś nie mogę tego poskładać w całość i cięgle mi czegoś brakuje ;/.

0

Prawdopodobnie za każdym razem zaokrąglasz wartości - czyli obracasz, zaokrąglasz, obracasz, zaokrąglasz i ci się zaokrąglenia kumulują.

0
Azarien napisał(a):

Prawdopodobnie za każdym razem zaokrąglasz wartości - czyli obracasz, zaokrąglasz, obracasz, zaokrąglasz i ci się zaokrąglenia kumulują.

Dokładnie tak. A każde zaokrąglenie, to kolejna utrata precyzji i jakiś "zjedzony" pixel. Dlatego zakładam, że muszę obrócić tylko 1 wektor, a potem na jego podstawie wyznaczać pozostałe (już bez obrotu - a więc i bez kolejnych zaokrągleń - tylko jakoś wyliczając ich przesunięcie). Tylko czy tak się da? Zastanawiam się jakie działania na wektorach mogę wykonać i jakoś nic mi nie przychodzi do głowy.

Żeby wyliczyć to z przekształconego wzoru na iloczyn skalarny, to muszę mieć obie współrzędne jednego wektora (mam) i przynajmniej jedną współrzędną drugiego wektora (nie mam żadnej, jedynie jego długość i punkt początkowy). Jest też inna wersja tego wzoru, ale ona z kolei wymaga uwzględnienia cosinusa z kąta między wektorami (tutaj 90 stopni), a to oznacza kolejne zaokrąglenia...

0

Wszystkie wzory masz kilka postów wcześniej. Problem jest taki że zapewne

  1. masz punkty p0, p1, ... pN
  2. Obracasz je o kont alfa1
  3. Dostajesz punkty p'0, p'1, .... p'N
  4. Teraz obracasz punkty p' o kont alfa2
  5. dostajesz punkty p''0, p''1, ... p''N
    Czyli za każdym razem obracasz punkty z poprzedniej iteracji o nowy kąt. Takie podejście powoduje narastanie błędu ponieważ każdy obrót dodaje ci kolejny błąd, aż błąd stanie się tak znaczący że wpływa na wartość wyniku.

Ten błąd łatwo wyeliminować, obracamy zawsze punkty z p0, p1, ... pN czyli punkty początkowe, akumulujemy kąty obrotu czyli powyższy schemat zamień na :

  1. masz punkty p0, p1, ... pN
  2. Obracasz je o kont alfa1
  3. Dostajesz punkty p'0, p'1, .... p'N
  4. Teraz obracasz punkty p0, ... pN o kont alfa1 + alfa2
  5. Uzyskujesz punkty p''0, p''1, ... p''N

Uzyskasz te same punkty p'' ale obarczone tylko jednym błędem a nie sumą błędów z dwóch iteracji. Każda kolejna iteracja powinna wyglądać tak samo, czyli zwiększasz kont obrotu i zawsze zaczynasz od punktów w pozycji 0.

Punkty 0, promieni możesz wyznaczyć raz na starcie, mają one taki samy Y(wybrany przez ciebie) i x mapowany na kolumny ekranu. Również masz podesłany algorytm jak wyznaczyć promienie w pozycji 0. Parę postów wyżej

0

Udało mi się napisać obrót planu w taki sposób, że jego długość waha się w przedziale 320-321 (zaokrąglenie do jednego pixela) czyli jest OK. Teraz staram się przypisać każdemu pixelowi planu jego własny promień (bo jak rozumiem, tak właśnie powinienem to zrobić).

Biorę więc plan (tutaj pod kątem 45 stopni) już po rotacji, obliczam jego długość (jak pisałem, wychodzi 319 lub 320 z przecinkiem, po zaokrągleniu do pełnego pixela 320 lub 321), a także wyznaczam wektor jednostkowy (czyli dzielę cały wektor na 320 części). Następnie przypisuję promień do pixela w taki sposób:

Wektor promienia = Wektor kierunkowy lewy (ten, który wyznacza granicę pola widzenia od lewej strony) + Wektor jednostkowy (320 / 1) pomnożony przez liczbę oznaczającą index promienia. Pierwszy od lewej ma index 0, kolejny 1, 2, 3 itd.

Oto efekt:

title

Na rysunku w ogóle nie widać wektora wyznaczającego plan, co oznacza (chyba), że operacja się udała, bo każdy pixel wchodzący w skład planu został "zamalowany" przez odpowiadający mu promień.

Tylko nadal nie rozumiem co na tym zyskałem. Owszem, teraz mam pewność, że odczytam dokładnie 320 informacji zwrotnych (bo każdy promień odpowiada dokładnie jednej kolumnie ekranu), tylko co z tego, skoro na załączonym obrazku widać, że obiekt nie zostanie narysowany w całości, lecz poszatkowany (uda się złapać jego co 2-3 kolumny). To oczywiście wynika z faktu, że im dalej od obserwatora, tym promienie bardziej się rozchodzą, ale co ja mogę z tym zrobić?

0

Nie możesz od d**y strony tego zrobić.

Zamiast od punktu w każdym kierunku, to wyznacz skrajne punkty i dla każdego punktu łączącego te dwa punkty zrób linie do punktu kropki.

0
Mały Mleczarz napisał(a):

Nie możesz od d**y strony tego zrobić.

Zamiast od punktu w każdym kierunku, to wyznacz skrajne punkty i dla każdego punktu łączącego te dwa punkty zrób linie do punktu kropki.

Przecież przez 2 punkty można poprowadzić jedną prostą. Co więc za różnica, czy poprowadzę wektor z A do B, czy z B do A? Zmieni się zwrot, ale kierunek pozostanie ten sam.

0

Zamiast od punktu w każdym kierunku, to wyznacz skrajne punkty i dla każdego punktu łączącego te dwa punkty zrób linie do punktu kropki.

Przecież przez 2 punkty można poprowadzić jedną prostą. Co więc za różnica, czy poprowadzę wektor z A do B, czy z B do A? Zmieni się zwrot, ale kierunek pozostanie ten sam.

Zamiast wyznaczać wektory od środka do celu co jakiś kąt (a co, jak widzisz, nie bardzo działa z powodu luk) wyznacz wektor dla każdego „piksela u celu” - ze środka do tego piksela.

0
Azarien napisał(a):

Zamiast od punktu w każdym kierunku, to wyznacz skrajne punkty i dla każdego punktu łączącego te dwa punkty zrób linie do punktu kropki.

Przecież przez 2 punkty można poprowadzić jedną prostą. Co więc za różnica, czy poprowadzę wektor z A do B, czy z B do A? Zmieni się zwrot, ale kierunek pozostanie ten sam.

Zamiast wyznaczać wektory od środka do celu co jakiś kąt (a co, jak widzisz, nie bardzo działa z powodu luk) wyznacz wektor dla każdego „piksela u celu” - ze środka do tego piksela.

Ja już nie obracam o kąt (to znaczy obracam, ale nie każdy promień z osoba, a jedynie wektor kierunku obserwacji i połączony z nim pod kątem 90 stopni plan obserwacji). Ów plan składa się z 320 pikseli i każdego wysyłam jeden promień (zapisany w postaci wektora, łączącego pozycję obserwatora z tym pikselem składowym planu) i wydaję mi się, że to działa OK. Precyzja nadal jednak jest pietą achillesową, bo to wymaga masy zaokrągleń. W końcu gdy dzieli się wektor długości ok. 320 na 320 części, to siłą rzeczy taki wyodrębniony fragmencik ma długość ok. 1 (zwykle 0 z przecinkiem, ale po wykonaniu całej algebry z dodawaniem wektorów i tak trzeba zaokrąglić wynik do pełnego piksela). Problem w tym, że przecież obiekt (cel trafienia) równie dobrze może się znajdować za planem, albo przed planem, gdzie - z racji rozchodzenia się promieni - powstają luki. Dobrze narysowane będzie tylko to, co z planem się przetnie (bo wtedy i tylko wtedy promienie tworzą pełną siatkę, bez żadnych luk). Reszta będzie wybrakowana.

Mój pierwotny pomysł był taki, żeby najpierw "oszacować" co może znajdować się w polu widzenia (udało mi się nawet sklecić działający algorytm tego typu, pozwalający mi badać pod kątem kolizji tylko te komórki mapy, które znajdują się w polu widzenia), a potem odwrócić cały proces, czyli z każdej kolumny potencjalnie widocznego obiektu (tj. wiem na 100%, że on tam jest, ale nie wiem na ile i czy w ogóle jest widoczny) wysyłać promień zwrotny w stronę obserwatora. Jak dotrze to znaczy, że ta kolumna składowa obiektu jest widoczna, jak nie, to nie.

Problematyczna wydaje mi się tu jednak wydajność. Patrząc na obrazek:

title

"Zapytania" o promienie zwrotne trzeba będzie wysłać do wszystkich obiektów ujętych w polu widzenia, także do kwadratów w kolorze niebieskim. Aż 4 z nich nie będą widoczne (są zablokowane przez kwadraty fioletowe), ale trzeba będzie poświęcić moc obliczeniową na ich "opromieniowanie" (a inaczej się chyba nie da, bo przy tej samej scence co na obrazku wystarczy zmienić kąt obserwacji i już niektóre z kolumn kwadratów niebieskich będą widoczne "zza placów" kwadratów fioletowych). Im więcej obiektów w polu widzenia, tym więcej promieni trzeba wystrzelić. No a potem trzeba to jeszcze poskładać w całość, by liczba trafień nigdy nie przekroczyła liczby kolumn ekranu. Doszedłem do wniosku, że to się nie sprawdzi i dlatego właśnie powstał ten wątek na forum, z potrzeby innej koncepcji.

1 użytkowników online, w tym zalogowanych: 0, gości: 1