|
Podstawy dla początkujących Autor: Mirosław Kozioł |
||||
|
1. Ściana Ściana składająca się z trzech wierzchołków:
Ściana składająca się z sześciu wierzchołków:
2. Składowanie danych ściany Dane dla ściany składowane są
przeważnie jako tablica punktów i tablica wskaźników do nich tzw. łączników.
Dla ścian składających się z trzech wierzchołków
wygląd tych tablic jest następujący:
łącznik1 = tablica łączników[
numer ściany*3 ]
numer ściany - to numer kolejnego trójkąta
do odczytu czyli kolejno 0,1,2, ... itd. Później adresując się po tablicy wierzchołków z wykorzystaniem łączników pobieramy współrzędne wierzchołków:
x1 = tablica punktów[łącznik1].x
x2 = tablica punktów[łącznik2].x
x3 = tablica punktów[łącznik3].x
5. Wektor Odcinek skierowany którego współrzędne wyznaczamy następująco: xa ya za Wektor A = [ x2 - x1, y2 - y1, z2 - z1 ] xb yb zb Wektor B = [ x3 - x1, y3 - y1, z3 - z1 ]
6. Długość wektora Wyznaczamy ją ze wzoru: Długość wektora A = || A || = sqrt ( A.x*A.x + A.y*A.y + A.z*A.z ) gdzie sqrt to pierwiastek kwadratowy
7. Normalizacja Polega na sprowadzeniu długości wektora do jedności Normalizujemy dzieląc składowe wektora przez jego długość Wektor znormalizowany A = A / || A || = [ A.x / ||A||, A.y / || A ||, A.z / || A || ] Normalizacja najczęściej zapisywana jest w postaci funkcji o nazwie Normalize Noramlize( A ) to normalizacja wektora A
8. Iloczyn skalarny Jest liczbą wyznaczaną dla wektorów składowych ze wzoru: Iloczyn skalarny wektorów A i B = A o B = xa*xb + ya*yb + za*zb Iloczyn skalarny wektorów A i B = A o B = || A || * || B || * cos(A,B) Gdy A i B są znormalizowane to A o B = cos(A,B) czyli iloczyn skalarny jest równy cosinusowi kąta pomiędzy wektorami A i B. Iloczyn skalarny najczęściej zapisywany jest w postaci funkcji o nazwie DotProduct A o B = DotProduct( A, B )
9. Iloczyn wektorowy Jest wektorem prostopadłym do wektorów składowych którego współrzędne wyznaczane są ze wzoru: xw yw zw Iloczyn wektorowy wektorów A i B = A x B = [ya*zb - yb*za, xb*za - xa*zb, xa*yb - xb*ya]
Iloczyn wektorowy najczęściej zapisywany jest w postaci funkcji o nazwie CrossProduct A x B = CrossProduct( A, B )
10. Wektor normalny Jest wektorem prostopadłym do płaszczyzny i jest wyznaczany z iloczynu wektorowego. Jest wektorem znormalizowanym czyli ma długość równą 1. A x B = CrossProduct( A, B ) Wektor normalny N = Normalize( A x B )
11. Płaszczyzna Jest określona przez równanie płaszczyzny wzorem:
Ax + By + Cz + D = 0 to równanie płaszczyzny
gdzie: A = N.x B = N.y C = N.z D = -DotProduct( P, N )
P to dowolny z wierzchołków ściany leżącej na płaszczyźnie. N to wektor normalny płaszczyzny wyznaczony np. z wierzchołków ściany leżącej na tej płaszczyźnie. D to przesunięcie płaszczyzny. Płaszczyznę przechowujemy w postaci wektora normalnego N i przesunięcia D
12. Płaszczyzna prostopadła do krawędzi ściany Musimy posiadać wektor R wyznaczony z punktów tej krawędzi oraz wektor normalny N ściany. Wtedy mamy:
SN = CrossProduct(R, N) Normalize(SN) SD = -DotProduct( P, SN )
SD, SN to odpowiednio przesunięcie oraz wektor normalny szukanej płaszczyzny prostopadłej do krawędzi wyznaczonej przez wektor R. P to jeden z wierzchołków krawędzi ściany np. pierwszy.
13. Duży portal Jest ścianą której wierzchołki należy znaleźć posiadając równanie płaszczyzny na której leży szukana ściana. Poniżej przedstawiam algorytm pozwalający wyznaczyć cztery wierzchołki dużego portala.Jest to algorytm tworzenia ściany na płaszczyźnie określonej przez wektor normalny N i przesunięcie D.
Tworzymy wektory U i R czyli Up i Right (góra, prawo): U = [0,1,0] R = [1,0,0] oraz tablicę określającą wielkość dużego portala w 2D:
wymiary[1].x = -20000 wymiary[1].y = -20000
wymiary[2].x = 20000 wymiary[2].y = -20000
wymiary[3].x = 20000 wymiary[3].y = 20000
wymiary[4].x = -20000 wymiary[4].y = 20000
Wartość 20000 przyjąłem orientacyjnie. Wielkość dużego portala powinna być ustalana dynamicznie w taki sposób aby jego wymiary były dużo większe od wymiarów sceny lub dopasowane do wymiarów sześcianu ograniczającego scenę.
Wyznaczamy wektory kierunkowe W1 i W2 oraz wektor przesunięcia WD: Jeżeli |N.x| > |N.y| to {W1 = CrossProduct( N, U );} w przeciwnym wypadku {W1 = CrossProduct( N, R );} W2 = CrossProduct( N, W1 ); Normalize(W1); Normalize(W2); WD = [ D*N.x, D*N.y, D*N.z ] |N.x| i |N.y| to odpowiednio moduł z N.x i moduł z N.y
Wyliczamy i zapisujemy wierzchołki dla dużego portala: Dla każdego punktu od 1 do 4 wyznaczamy jego składowe x, y, z:
duży portal[punkt] = [W1.x * wymiary[punkt].x + W2.x * wymiary[punkt].y + WD.x, W1.y * wymiary[punkt].x + W2.y * wymiary[punkt].y + WD.y, W1.z * wymiary[punkt].x + W2.z * wymiary[punkt].y + WD.z ]
14. Sprawdzenie położenia punktu P względem płaszczyzny Płaszczyzna określona jest poprzez: N = [N.x, N.y, N.z] wektor normalny płaszczyzny D przesunięcie płaszczyzny
Sprawdzenie polega na policzeniu wartości wyrażenia DotProduct( N, P ) + D i sprawdzeniu znaku wyniku.Gdy wynik jest równy zero to punkt leży na płaszczyźnie gdy dodatni bądź ujemny to leży po jednej ze stron płaszczyzny. Wyrażenie DotProduct( N, P ) + D to nic innego tylko podstawienie współrzędnych punktu P do równania płaszczyzny
15. Sprawdzenie położenia ściany względem płaszczyzny Polega na sprawdzeniu położenia jej punktów Gdy wszystkie leżą na płaszczyźnie to ściana leży na płaszczyźnie Gdy wszystkie leżą po jednej ze stron płaszczyzny to ściana leży po jednej ze stron płaszczyzny Gdy część leży po jednej a część po drugiej stronie płaszczyzny to ściana jest przecinana przez płaszczyznę
16. Sprawdzenie zwrotu ściany
Polega w przestrzeni 3D na sprawdzeniu wartości wyrażenia: DotProduct(P3, CrossProduct(P1, P2)) = P3.x*(P1.z*P2.y - P1.y*P2.z)+ P3.y*(P1.x*P2.z - P1.z*P2.x)+ P3.z*(P1.y*P2.x - P1.x*P2.y) gdzie P1, P2, P3 to współrzędne trzech pierwszych wierzchołków ściany P1 = (x, y, z) P2 = (x, y, z) P3 = (x, y, z)
Polega w przestrzeni 2D na sprawdzeniu wartości wyrażenia: (P1.x-P2.x)*(P3.y-P2.y)-(P1.y-P2.y)*(P3.x-P2.x) gdzie P1, P2, P3 to współrzędne trzech pierwszych wierzchołków ściany na ekranie P1 = (x, y) P2 = (x, y) P3 = (x, y)
Jeżeli wartość wynikowa jest dodatnia lub ujemna to ściana jest obrócona przodem lub tyłem do obserwatora. Jeżeli wartość wynikowa jest równa zero to ściana jest prostopadła do obserwatora.
17. Usunięcie ścian niewidocznych (ang. cull face) Polega na sprawdzeniu zwrotu wszystkich ścian które chcemy wyświetlić i usunięciu tych które są ustawione tyłem do obserwatora
18. Punkt przecięcia płaszczyzny i odcinka Płaszczyzna jest dana poprzez wektor normalny N i przesunięcie D Odcinek jest dany poprzez punkt początkowy PP i końcowy KP Wyznaczamy wektor kierunkowy V = PP - KP
Szukamy punktu P' przecięcia płaszczyzny i odcinka: Wyznaczamy współczynnik W W = (DotProduct( N, KP ) + D)/DotProduct( N, V ) Wyznaczamy punkt przecięcia P' P' = KP - V*W Współrzędnych wektora V nie normalizujemy.
Przykład wykrywania kolizji: W rozdziale Kolizje przedstawiłem opisowo przykładowe metody wykrywania kolizji. Tutaj przedstawię opis metody wykrywania kolizji na przejście punktu przez ścianę z odwołaniami do teorii.
Metoda wykrywania kolizji na przejście punktu przez ścianę Polega na podstawieniu współrzędnych obserwatora do równania płaszczyzny na której leży ściana a następnie sprawdzeniu znaku wyniku. Gdy stwierdzimy że znak otrzymany dla współrzędnych obserwatora przed ruchem jest różny od znaku otrzymanego po ruchu to istnieje możliwość kolizji. Należy wtedy wyznaczyć punkt przecięcia prostej przechodzącej przez współrzędne obserwatora z płaszczyzną ściany którą testowaliśmy. Gdy mamy punkt przecięcia należy sprawdzić czy leży on wewnątrz ściany czy nie.Jeżeli leży wewnątrz to wystąpiła kolizja.
Realizacja: Obserwator jest w punkcie A(x, y, z) i wykonał ruch do punktu B(x, y, z) Testujemy ścianę o wierzchołkach w1,w2,w3,w4 dla której mamy policzone:
równania czterech płaszczyzn (p1,p2,p3,p4) prostopadłych do krawędzi ściany zapisanych w postaci N1,D1 N2,D2 N3,D3 N4,D4 Sprawdzamy czy wystąpiła kolizja: Sprawdzenie czy wystąpiła kolizja polega na policzeniu dla punktów A i B wyrażenia :( DotProduct( N, A ) + D ) * ( DotProduct( N, B ) + D ) Gdy znak wyniku jest mniejszy od zera to oba punkty leżą po przeciwnych stronach płaszczyzny wyznaczonej dla ściany (wyznaczamy z punktu 14) czyli istnieje możliwość wystąpienia kolizji.Należy wtedy wyznaczyć punkt przecięcia odcinka (A, B) z płaszczyzną ściany (wyznaczamy z punktu 18)
V = A - B P = B W = (DotProduct( N, P ) + D)/DotProduct( N, V ) Wyznaczamy punkt przecięcia P' P' = P - V*W
Teraz pozostało nam już sprawdzenie czy wyznaczony punkt przecięcia P' leży wewnątrz ściany. Dla każdej z płaszczyzn prostopadłych do krawędzi ściany sprawdzamy czy punkt P' leży po tej samej stronie. Jeżeli leży po tej samej stronie dla wszystkich płaszczyzn p1,p2,p3,p4 to wystąpiła kolizja (wyznaczamy z punktu 14). Przy realizacji należy zwrócić uwagę na kolejność wierzchołków ściany.
|
