Jak zmapować punkt na zniekształconą siatkę

Question

Załóżmy, że masz zbiór punktów o współrzędnych na kartezjańskim układzie współrzędnych.

chcesz wykreślić kolejny punkt, a wiesz jego współrzędne w tym samym układzie kartezjańskim współrzędnych.

Jednak wykres, na którym rysujesz, jest zniekształcony w stosunku do oryginału. Wyobraź sobie, że bierzesz oryginalną płaszczyznę, drukujesz ją na gumowym prześcieradle, rozciągasz ją w niektórych miejscach i szczypiąc ją w innych, w sposób asymetryczny (bez nakładania się i niczego skomplikowanego).

(source)

Znasz rozciągnięte i nie rozciągniętymi współrzędne każdego zestawu punktów, ale nie funkcyjne odcinek bazowy. Znasz nieskończone współrzędne nowego punktu.

Jak można oszacować, gdzie należy narysować nowy punkt w rozciągniętych współrzędnych na podstawie rozciągniętych pozycji punktów pobliskich? Nie musi to być dokładne, ponieważ nie można określić rzeczywistej funkcji rozciągania z zestawu punktów remapowanych, chyba że masz więcej informacji.

inne możliwe słowa kluczowe: wypaczony zniekształcony siatki mesh płaszczyzna współrzędnych unwarp

Answer 1

Ok, więc brzmi to jak wypaczenia obrazu. To, co należy zrobić:

1. Tworzenie Delaunay triangulation swojego niedopasowanego sieci i korzystać z wiedzy o korespondencji pomiędzy siatką wypaczony i niedopasowanego do tworzenia triangulacji dla wypaczony siatki. Teraz znasz odpowiednie trójkąty na każdym obrazie, a ponieważ nie ma nakładających się na siebie, powinieneś być w stanie wykonać kolejny krok bez większych trudności.

2. Teraz, aby znaleźć odpowiedni punkt A w wypaczony obraz:

   1. Znajdź trójkąta A kłamstwa i stosowanie transformacji pomiędzy trianble w niedopasowanego siatki i wypaczony siatki, aby dowiedzieć się Nowa pozycja.

Jest to wyjaśnione w wyraźnej szczegółowo here.

Inną (znacznie bardziej skomplikowaną) metodą jest Thin Plate Spline (co wyjaśniono również na slajdach powyżej).

Answer 2

Wiele zależy od liczby istniejących punktów. Jeśli masz tylko jedną, niewiele możesz z nią zrobić - możesz zrównoważyć drugi punkt o tę samą wartość w tym samym kierunku, ale nie masz wystarczającej ilości danych, by naprawdę zrobić coś lepszego.

Jeśli masz dość wielu istniejących punktów, możesz wykonać dopasowanie powierzchni poprzez te punkty i użyć go do przybliżenia właściwej pozycji nowego punktu. Biorąc pod uwagę N punktów, zawsze możesz uzyskać idealne dopasowanie za pomocą wielomianu rzędu N, ale rzadko chcesz tego dokonać - zamiast tego zazwyczaj domyślasz się, że funkcja rozciągania jest funkcją dość niskiego rzędu (np. Kwadratową lub sześcienną) i pasuje powierzchnia do punktów na tej podstawie. Następnie umieść nowy punkt w oparciu o funkcję dopasowanej powierzchni.

Answer 3

Zrozumiałem, że masz powiązanie jeden-do-jednego między owiniętymi i nieopakowanymi punktami siatki. I zakładam, że deformacja nie jest tak ekstremalna, że ​​możesz przecinać linie siatki (jak obraz, który pokazujesz).

Strategia jest dokładnie taka, jak sugeruje Jacob: Trianguluj dwie siatki w taki sposób, że istnieje jedno-do-jednego powiązanie między trójkątami, zlokalizuj punkt, który ma być odwzorowany w triangulacji, a następnie użyj współrzędnych barycentrycznych w odpowiednim trójkącie do obliczenia nowa lokalizacja punktu.

Preprocesuj

1. Generowanie Delaunay triangulation z punktów owinięte siatką, nazwijmy to WT.
2. Dla każdego trójkąta w WT dodaj trójkąt między odpowiednimi wierzchołkami w nieopakowanej siatce. Daje to triangulację punktów nieopakowanych.

mapie punkt p do owinięty siatką

1. Znajdź trójkąt T(p1,p2,p3) w UWT który zawiera p.
2. Oblicz barycentric coordinates(b1,b2,b3) z p w T(p1,p2,p3)
3. Niech Tw(q1,q2,q3) być trójkąt w WT odpowiadający T(p1,p2,p3). Nowa pozycja to
   b1 * q1 + b2 * q2 + b3 * q3.

Uwagi Daje funkcję odkształcenia jako linear spline. Aby uzyskać bardziej płynne zachowanie, można zastosować tę samą triangulację, ale dokonać aproksymacji wyższego rzędu, co doprowadziłoby do nieco bardziej skomplikowanych obliczeń zamiast współrzędnych barycentrycznych.

Answer 4

Inne odpowiedzi są świetne. Dodam tylko, że warto przyjrzeć się Free form deformation jako sposobowi opisu deformacji.

Jeśli jest to użyteczne, to całkiem możliwe jest, aby dopasować siatkę deformacji/kratownicę do znanych par, a następnie masz bardzo szybką metodę deformowania przyszłych punktów.