Jak odsunąć czworokąt na prostokąt?

tl; dr: Problem matematyczny w geometrii rzutowej: Jak znaleźć matrycę kamery 4x4, która daje rzut, jak pokazano poniżej, tak, że punkty A, B, C, D znajdują się gdzieś na krawędziach pola jednostki (np. znormalizowane urządzenie OpenGL współrzędne), a rogi pola jednostki opadają gdzieś rozsądnie wzdłuż promieni EA, EB, EC, ED?

(Może to być szczególny przypadek homografii, perspektywy i / lub kolineacji. Nieznajomość terminologii).

opracowanie

Biorąc pod uwagę czworoboczny ABCD w obszarze wyświetlania, myślę, że istnieje unikalna (?) Transformacja, która odwzorowuje go z powrotem na prostokąt. Jak widać na poniższym obrazku: czworoboczny ABCD w rzutni działa jako fizyczne „okno”, a jeśli odwzorujemy go z powrotem na prostokąt, będzie on wyglądał na zniekształcony.

(pole po prawej stronie reprezentuje NDC, o którym mówię później)

Celem jest szybkie uzyskanie obrazu po prawej stronie. Możemy prześledzić każdy punkt, aby uzyskać obraz (co zrobiłem), ale wolałbym używać OpenGL lub innych technik projekcyjnych, ponieważ chciałem skorzystać z takich rzeczy jak mieszanie, prymitywy itp.

pierwsze podejscie

Wierzę, że mogę rozwiązać problem znalezienia matrycy kamery 3x4 , która powoduje, że jednorodna współrzędna 3 + 1 w 3-przestrzeni (po lewej) i rzutuje ją do jednorodnych współrzędnych wymiarowych 2 + 1 w przestrzeni 2-na prawo). Można to rozwiązać za pomocą bezpośredniej transformacji liniowej, aby uzyskać układ równań Ba=0dla nieznanych wpisów amatrycy kamery, i rozwiązać układ z wykorzystaniem rozkładu pojedynczej wartości (SVD). I would take the vectors EA, EB, EC, ED (where E is your physical eye or the camera in world-space) as points in the pre-image, and (0,0), (1,0), (1,1), (0,1) or something as the points in the post-image, and each pair of points would give a few linear equations to plug into the SVD. The resulting matrix would map EA->(0,0) etc. (assuming there are enough degrees of freedom i.e. if the solution is unique, which I'm not sure about, see note[a].)

Ale ku mojemu rozczarowaniu, nie tak działa OpenGL. OpenGL nie wyświetla bezpośrednio 3D na 2D z matrycą 3x4. OpenGL wymaga „znormalizowanych współrzędnych urządzenia” (NDC), które są punktami trójwymiarowymi. Po rzutowaniu na NDC rysuje się wszystko w polu „jednostek” od (-1, -1, -1,1) do (1,1,1,1); wszystko na zewnątrz jest obcinane (ponieważ mamy do czynienia z jednorodnymi współrzędnymi: dowolny punkt (x, y, z, w) pojawi się tylko na ekranie tylko wtedy, gdy pierwsze trzy współrzędne (x / w, y / w, z / w , 1) mieszczą się w polu jednostki od -1 do 1).

Powstaje więc pytanie: czy istnieje jakaś sensowna transformacja, która odwzorowuje dziwnie wyglądający prostopadłościan o jednorodnych współrzędnych (konkretnie prostopadłościan narysowany po lewej stronie, z ABCD (punkty przednie) i A'B'C'D '(punkty tylne, ukryte za punktami frontowymi)) do kostki jednostkowej, np. przy użyciu macierzy 4x4? Jak to zrobić?

co próbowałem

Próbowałem czegoś mocniejszego: sprawiłem, że ABCD i A'B'C'D 'wyglądają jak zwykła piramida frustrum (np. Fr frustrum) (tj. W tym hipotetycznym układzie obraz po lewej stronie miałby tylko czarny prostokąt nałożony na , a nie czworobok), a następnie zastosował DLT / bezpośrednią transformację liniową do rozwiązania domniemanej macierzy 4x4. Jednak kiedy spróbowałem, wydawało się, że nie ma wystarczających stopni swobody ... wynikowa macierz 4x4 nie odwzorowała każdego wektora wejściowego na każdy wektor wyjściowy. Używając A, B, C, D, A '(5 par wektorów przed transformacją i po transformacji), prawie / uzyskuję wynik, którego chcę ... wektory są poprawnie odwzorowane, ale na przykład B', C ', D' są mapowane na (3,3,1,1) zamiast (-1, -1,1,1) i są obcinane przez OpenGL. Jeśli spróbuję dodać szósty punkt (6 par punktów dla macierzy 4x4 do projektu), moje rozwiązanie wydaje się zdegenerowane (zera, nieskończoność). Z iloma stopniami swobody mam tu do czynienia i czy jest to możliwe dzięki macierzy 4x4 odwzorowującej zwykłe wektory 4 (wektory 3 + 1-wymiarowe jednorodne o współrzędnych), które znamy i kochamy?

przypadkowe drobne myśli

Zgaduję, że nie jest możliwe odwzorowanie dowolnego dowolnego prostopadłościanu na dowolny dowolny prostopadłościan z macierzą 4x4, chociaż jestem zdezorientowany, ponieważ myślałem, że możliwe jest odwzorowanie dowolnego wypukłego czworoboku na dowolny inny wypukły czworobok w 2D z pewną macierzą jak w , powiedzmy, Photoshop? ... czy nie można tego zrobić za pomocą transformacji projekcyjnej? I w jaki sposób uogólnia się na 3d? ...... Biorąc również pod uwagę nieudaną próbę znalezienia macierzy 4x4, algebra liniowa mówi, że nie powinniśmy oczekiwać, że macierz NxN odwzoruje więcej niż N liniowo niezależnych punktów na N punktów docelowych w najlepszym przypadku, ale wydaje mi się, że jest to jakoś jednorodne koordynuje to oszustwo, ponieważ dzieje się jakaś ukryta kolinearność? Nie sądzę?

inne rozwiązanie?

Sądzę, że można też zrobić następującą brzydką rzecz: użyć typowej frustralnej matrycy projekcyjnej kamery, znaleźć punkty 2d odpowiadające rogom, a następnie wykonać perspektywę 2D zniekształcić homografię, ale jeśli miałoby to nastąpić po renderowaniu pikseli (np. photoshop) wtedy pojawiałyby się problemy z rozdzielczością ... może hipotetycznie można by wymyślić matrycę do przeprowadzenia tej transformacji na płaszczyźnie XY w przestrzeni NDC, a następnie skomponować ją z normalną matrycą opartą na frustracji?

(uwaga [a]: stopień swobody: ABCD można dodatkowo ograniczyć do post-obrazu projekcji transformacji działającej na prostokąt, jeśli to konieczne ... to znaczy czarny prostokąt po lewej stronie może być wynik wyświetlania modelu clipart ramki na zdjęcia)

Myślę, że rozwiązaniem jest transformacja rzutowa, która poprawnie przekształca cztery punkty.

to znaczy

gdzie iy = [ y $x' = [x_0, x_1, 1]$$y = [\frac{y'_0}{y'_2}, \frac{y'_1}{y'_2}]$

$P$ jest matrycą 3x3 z 9 wpisami. Ze względu na ostateczną normalizację jest on unikalny aż do skalowania, pozostawiając 8 stopni swobody, które są jednoznacznie określone przez 8 równań podanych w korespondencji (2 na parę punktów).

Teraz możesz użyć do tego algebry lub po prostu użyć OpenCV getPerspectiveTransform:).

Sprawdź także jednorodne współrzędne na wikipedii, aby zapoznać się z tą koncepcją.

Rozwiązałem własne pytanie, wdrażając bezpośrednią transformację liniową . Sekcja przykładów na Wikipedii była moim przypadkiem użycia.

Aby uzyskać równania, podłącz macierze (np. [x1 x2 x3 x4; x5 x6 x7 x8; x9 x10 x11 x12]) Do swojego ulubionego komputerowego systemu algebry, takiego jak SageMath, a następnie Rozwiąż wymagane równanie macierz, jak pokazano, skopiuj i wklej rozwiązania w zakresie zmiennych do kodu i dostosuj formatowanie.

Następnie można dostosować rozwiązanie do własnego przypadku użycia, skalując lub ignorując odpowiednio określone wymiary (np. Zignoruj ​​współrzędną głębokości / z w macierzy znormalizowanych współrzędnych urządzenia odpowiednio do przypadku zastosowania).

Będziesz potrzebował funkcji lub biblioteki dekompozycji SVD w swoim języku.