Znormalizowany NURBS

[Kroopson]

Temat raczej do działu jakiegoś programistycznego ale jako że to co robię robię w Maya to pytam tutaj.

 

Zna ktoś jakiś w miarę szybki algorytm do obliczenia znormalizowanego NURBS'a? w sensie chcę pobrać położenie punktu na krzywej biorąc pod uwagę jej absolutną długość (czyli jak podaję U=.25 to zawsze dostaję 1/4 krzywej, niezależnie od położenie punktów kontrolnych, nawet jeśli 1 i 2 punkt kontrolny się pokrywają).

 

W tej chwili robię to tak że:

Sampluję krzywą dużą ilość razy i sumuję długości wszystkich wektorów T = Pn - P(n-1) (dżizas jak to się pisze jakoś po ludzku) żeby mieć długość odcinka krzywej.

Zapisuję sobie wszystkie te punkty razem z długościami korespondująch z nimi wektorów.

Następnie iteruję sobie po takiej tablicy i sprawdzam czy suma długości wektorów dla indeksów od 0 do aktualnego nie jest mniejsza niż szukana wartość. Robię jeszcze drobne czarymary i generalnie mam rządany wynik.

 

Wydaje mnie się to jednak trochę przekombinowane i nieefektywne obliczeniowo. Może ktoś coś takiego już kiedyś robił? (Barejko ratuj ;) )

 

PS. To nie jest pytanie o żaden istniejący node w Maya więc proszę bez porad w stylu "zrób sobie arcLengthDimension albo motionPath" ;)

 

PS2. Dla maksymalnego uproszczenia obliczeń krzywa ma tylko 4 punkty kontrolne.

 

PS3. Jeszcze dla jasności - sama krzywa też nie funkcjonuje jako majowy NURBS. Mam 4 wektory i liczę na ich podstawie odcinek krzywej, wypluwając sekwencję punktów.

[praetorian]

Cześć

Będę odpowiadał po omacku, bo matma krzywych jest mi obca i niemiła :)

 

_Wydaje mi się_, że nie ma dobrego sposobu, żeby to zrobić. Krzywe z natury są zdefiniowane w dziedzinie jednego parametru, który nijak nie jest powiązany z ich długością. Moża dałoby się coś osiągnąć, gdybyś zbudował krzywą jeszcze raz (zakładam, że działasz w C/API) z nowym wektorem parametrów (KNOT), gdzie każda kolejna wartość jest powiększona o długość poprzedniego segmentu krzywej, ewentualnie całość znormalizowana do 0-1.

Czyli jakoś tak:

 

1. obliczasz długość każdego segmentu krzywej, od węzła n do n-1 (uwaga na warunki brzegowe ;) )

2. wartość nowego węzła N, to suma długości segmentów od 0 do n-1

3. ewentualnie normalizujesz do 0-1

 

Długość węzła możesz obliczyć numerycznie, tak jak to robiłeś, albo analitycznie (polecam SISL, http://www.sintef.no/sisl)

Nie wiem czy cały koncept zadziała, ale jak mówiłem, ide na intuicję :) Oczywiście nowa parametryzacja wźmie w łeb jak ruszysz punktami kontrolnymi :/

Twój sposób też sie wydaje sensowny. Jeśli dobrze zrozumiałem, to masz szereg (ciąg sum) pochodnych po parametrze ?

 

Chyba lepiej będzie spytać na comp.graphics.algorithms

 

powodzenia :)

[beny]

Krupson, jak dla mnie to ta metoda co robisz jest jak najbardziej najefektywniejsza - czyli budujesz tablicę wektorów (trochę lepsza byłaby lista ze względu na ew. problemy z pamięcią jeżeli produkcyjnie robisz to narzędzie) tylko raz gdy krzywa jest modyfikowana. W ten sposób masz już posortowaną listę/tablicę więc wyszukiwanie jest banalne - proponuję quickSort'em ... szybciej wg. mnie się nie da - ew. z samego równania NURBSów wyliczać pozycję punktów, ale nie wiem na ile przyspieszy Ci to wyliczenia, jeżeli w ogóle przyspieszy.

[Kroopson]

Eh. Dla mnie to jest trochę taki brute force ale działa.

 

W samym kodzie zrobiłem nie tablicę wektorów ale tablicę wskaźników do structów z których każdy struct zawiera:

 

struct curvePoint{
    MPoint point;
    MVector direction;
    double length;
}

 

Jako że zapełniam tą tablicę dla n elementów inkrementalnie samplując nurbs'a z równania to sortowanie mam "za darmo".

Później dla każdego szukanego punktu na krzywej wykonuję pętlę:

 

double desiredPoint = .4; //parametr U dla szukanego punktu
int tablen; // tu mam ilość wpisów w tablice curvePointów
double currentLength;
MPoint point;
for (int i; i      currentLength += curvePoints[i]->length;
    if (currentLength >= desiredPoint){
        point = curvePoints[i].point;
        break;
    }
}

 

To taki pseudo kod, piszę z pamięci bo nie mam tego przy sobie :)

 

 

praetorian - tak też zrobiłem i to działa. Szukam teraz metody optymalizacji. Jak zaimplementuję w nodzie wszystki funkcjonalności to się pochwalę na forum co też wymyśliłem ;)

[praetorian]

Jak zaimplementuję w nodzie wszystki funkcjonalności to się pochwalę na forum co też wymyśliłem ;)

 

Czekam z niecierpliwością :)

Skoro już sobie gadamy o kodowaniu, to tez się pochwalę

https://bitbucket.org/mfratczak/partio43delight

[beny]

...

Jako że zapełniam tą tablicę dla n elementów inkrementalnie samplując nurbs'a z równania to sortowanie mam "za darmo".

Później dla każdego szukanego punktu na krzywej wykonuję pętlę:

...

 

quickSort jest to metoda wyszukiwania elementów (i wstawiania) w posortowaną już tablicę. Dlatego Ci ją proponowałem właśnie żebyś NIE robił tak jak zrobiłeś wyszukiwanie :) teraz przelatując przez wszystkie elementy tablicy Twój czas wyszukiwania zajmuja O(n) czyli najwolniejszy możliwy. Używając quicksorta będziesz miał wykładniczo niższy. Chodzi o to żeby nie przelatywać przez wszystkie elementy tylko łapiesz pierwszy, potem środkowy - jeżeli środkowy za duży to łapiesz w połowie wcześniejszego ciągu, jak za mały to w większej połowie ciągu ... w ten sposób bez sensu nie lecisz po wszystkich elementach skoro wiesz że są posortowane. Co więcej, jeżeli wiesz ile masz wektorów na krzywej i wiesz jakiego punktu potrzebujesz - u Ciebie w przykładzie punkt 0.4, to najszybciej jest znaleźć Twój wektor tak:

 

indexTwojegoSzukanegoWektora = floor(0.4*ileWektorow)

 

W ten sposób bez żadnego loopa dostaniesz index vektora najbliżej punktu 0.4.

[Kroopson]

Coś w tym jest - jak znajdę czas to zaimplementuję :)

[beny]

Ok, jeżeli wektory są różnych długości to można mój powyższy post olać bo ani wyszukiwanie Ci nic nie da bo de facto tablica nie jest posortowana, ani ten wzór nic nie da. Chyba pozostaje Ci tylko taki sposób jak zrobiłeś :( czyli brute force.

[Kroopson]

Trochę mnie natchnęliście i zoptymalizowałem nieco cały algorytm.

 

Generalnie efekt końcowy chciałbym osiągnąć mniej więcej taki:

http://www.youtube.com/watch?v=dvXU4_KodhM

Przy czym niektóre rzeczy akurat w tym setupie mi się nie podobają, no i chcę mieć to zamknięte w jednym nodzie, bez używania krzywych majowych.

 

Teraz na celowniku jest squash i stretch. :)

[Kroopson]

Dobra - pierwsza odsłona tej zabaweczki:

 

 

Przy okazji kręcenia tego filmiku zauważyłem jedno ustawienie krzywej przy której flipuje mnie się upvector :(

 

Jeszcze trochę roboty zostało ale zabawa jest. Najgorsza jest to że już widzę że powinienem skasować wszystko i zacząć od początku bo dopiero teraz wiem jak przeliczać to wszystko dużo szybciej (ale i tak jest to demon w porównaniu z setupem na nodach i krzywych robionym).

 

Pozdrówka

Kroops

[beny]

Nooo stary! Dałeś czadu. Wygląda zarąbiście!

[SYmek]

O fajne! Nie znam się na riggowaniu, czy to jest to, co się nazywa Bones from Curve w H?

 

Co do NURBSów, to o ile mi wiadomo, nie ma metody analitycznej na licznie jego rzeczywistej długości. Trzeba to robić numerycznie, czyli mniej więcej tak jak robiłeś. Bardziej zaawansowana metoda to rozbicie krzywej na segmenty i całkowanie mniejszych kawałków (prostsze wielomiany) jakimiś tajemniczymi metodami aproksymacji całek . Szkoda zachodu, o ile nie masz do tego narzędzi. Nie masz w API czegoś takiego, czy chciałeś zostać w MELU?

[Kroopson]

Mam w API. W MFnNurbsCurve jest funkcja length() i kilka innych ciekawych funkcji ale bardzo zależało mi na tym żeby nie używać dodatkowych node'ów, dzięki czemu całość zamknięta jest w jednym nodziku. To samo zrobione przy użyciu nurbs'a generowałoby już:

transform node dla krzywej

shape dla krzywej

4 clustery

4 deformer sety

4 cluster handles

czyli 14 node'ów które trzeba zapisać w pliku .ma. Jak masz np 10 postaci w scenie to się robi niezły hardcore, zwłaszcza z deformer setami.

 

Cały ten setup to 1 node rozkładający sześciany po krzywej, 4 node'y do kontroli start/end (poly cube'y) plus 4 ich transformy, jeden node obliczający twist i tyle node'ów ile jest vertibrów (czyli te punkty na krzywej). Całość zamknięta jest w grupie i zablokowana dzięki czemu jest nad tym większa kontrola.

 

Jak będę miał znów wolną chwilę to muszę przemyśleć obliczanie rotacji żeby mi się nie twistowało tak brzydko przy dużych wychyleniach punktów kontrolnych.

[beny]

Przecież jakbyś zrobił swoją funkcję dobierania się do krzywych dziedziczącą po MFnNurbsCurve to mógłbyś przeciążyć konstruktory krzywej i w ten sposób miałbyś 1 node ... czy nie? Wiem że tak robiłem z lokatorem, żeby rysować w viewporcie i w ten sposób nie miałem shape noda. Myślę, że to by zadziałało, żeby mieć jeden czyściutki nodzik.

 

ps. Nie wiedziałem że MFnNurbsCurve tworzy tyle śmieci - deformer sety i cluster handles musiały być dodane jakoś niedawno żeby móc animować pojedyncze punkty krzywych bez konieczności modyfikacji deformerami - innej przyczyny nie widzę po co to miałoby być dodawane z defaultu.

[legomir]

No ja jedynie informuję, że daje repa i zostałem zmotywowany tym żeby ruszyć dupę i w końcu poduczyć się MEL i API ;)

[SYmek]

Mam w API. W MFnNurbsCurve jest funkcja length() i kilka innych ciekawych funkcji ale bardzo zależało mi na tym żeby nie używać dodatkowych node'ów, dzięki czemu całość zamknięta jest w jednym nodziku.

 

Jasne, to ma sens :).