Jak raytrace powierzchni Beziera?

Próbowałem tego pytania na matematyce.SE i zaskakująco odpowiedź brzmiała: „równania są zbyt paskudne, po prostu podaj tę funkcję numerycznej wyszukiwarce root”. Ale jeśli uważasz się za „faceta grafiki” takiego jak ja i grałeś intensywnie z krzywymi Beziera do prac projektowych, muszę uwierzyć, że lepiej można to zrobić. Istnieje opublikowany algorytm Kajiya, którego nie mam tła do zrozumienia (Sylvester Matrices), ale pokrewne porady dotyczące matematyki. SE było to, że wynikiem jest wielomian stopnia 18 wt, a ty nadal musisz go rozwiązać liczebnie. Miałem inny pomysł z podobnym rezultatem .

Czy zatem marzeniem jest całkowite pomalowanie rury algebraicznie rozwiązać przecięcie powierzchni Ray / Bezier, umożliwiając w ten sposób wyraźne kodowanie i zapewniając superszybką super-gładkość?

Z wyjątkiem tego, jaka jest najszybsza metoda wykonania tego obliczenia? Czy potrafisz „znaleźć wiggles”, aby uzyskać ścisłe powiązanie (i cel) dla rekurencyjnego podziału? Jeśli musisz skorzystać z numerycznej wyszukiwarki korzeni (westchnienie), jakich właściwości potrzebuje i czy jest najlepszy wybór dla szybkości?

Moja pierwotna myśl dotyczyła przygotowania się do określonej powierzchni, podobnej do ekspansji Laplace'a, jak opisano w odpowiedzi na moje inne matematyczne pytanie dotyczące trójkątów . Ale interesują mnie również ogólne metody. Myślę tylko o ustalonym zestawie kształtów, takich jak czajniczek z Utah . Byłbym jednak bardzo zainteresowany sposobami optymalizacji pod kątem spójności czasowej między animowanymi ramkami.

Po pierwsze, oto metoda Kajiya, o której myślę: Kajiya, Ray Tracing Parametric Patches , SIGGRAPH 82. Wersja raportu technicznego może być bardziej informacyjna.

Mam nadzieję, że z tego wyniknie to, że nie jest to niemożliwe i nie jest trudne koncepcyjnie, jeśli nie masz nic przeciwko brudzeniu sobie rąk algebraiczną geometrią i liczbami zespolonymi. Jednak robienie tego bezpośrednio jest absurdalnie drogie.

„Prawdziwe” znaczniki promieni zwykle łączą dwie rzeczy:

• Umieszczenie hierarchii granicznej (np. AABB) na łatce, aby uzyskać dobrą „wartość początkową” dla numerycznej wyszukiwarki root. Jeśli zrobisz to dobrze, możesz uniknąć problemu „zmarszczek”.
• Tesselating łatkę do skorup DDG i ray tracing je jak siatki wielokątów.

Ten ostatni punkt brzmi, jakby zabijał wymóg „super-gładkości”, ale nie jest aż tak zły, jak w przypadku różnicowych promieni . Dopasowanie poziomu teselacji do „rozmiaru” promienia ładnie ogranicza błąd. Poza tym prawdopodobnie i tak potrzebujesz różnic dla współrzędnych tekstury, więc równie dobrze możesz użyć jej do kontroli dokładności testu przecięcia.

Wykorzystanie spójności czasowej nie jest złym pomysłem, ale to, jak to zrobisz, zależy w dużej mierze od przedstawienia wykresu sceny. Możesz spojrzeć na spójność promienia. Zapytaj swoją ulubioną wyszukiwarkę o śledzenie pakietów ray i zmianę kolejności ray .

czy to marzenie o całkowitym potoku ma nadzieję na algebraiczne rozwiązanie przecięcia powierzchni Ray / Bezier

Tak, to fajny sen. Dwububowa łatka Beziera jest algebraiczną powierzchnią stopnia 18. Aby przeciąć promień z tą powierzchnią, musisz znaleźć pierwiastki wielomianu stopnia 18. Nie ma wzoru na te pierwiastki - musisz je znaleźć metodami numerycznymi . W rzeczywistości istnieją wyniki matematyczne ( twierdzenie Abla-Ruffiniego ), które mówią nam, że nigdy nie może być wzorów na pierwiastki równań powyżej stopnia 4. Matematyka nie mówi tylko, że formuły jeszcze nie zostały znalezione; mówi, że nigdy nie zostaną odnalezione, ponieważ nie mogą istnieć.

Jeśli naprawdę chcesz wykonać analityczne (algebraiczne) śledzenie promieniowe kształtów krzywiznowych, możesz spróbować zastosować łatki Steiner . Mają one stopień 4, więc przecięcie promienia-łatki można obliczyć, znajdując pierwiastki kwartyku (tj. Wielomian stopnia 4). Istnieją formuły do ​​znajdowania pierwiastków kwartyki, ale są one dość nieprzyjemne i zaskakująco trudno jest napisać kod, który niezawodnie implementuje formuły.

Inną opcją, z której skorzystałem kilkadziesiąt lat temu (tak!), Jest użycie schematu Totha z 1985 roku, który wykorzystywał arytmetykę interwałów do zawężania przestrzeni poszukiwań. IIRC, ostatecznie ucieknie się do Newton-Rhapson, ale znowu IIRC, myślę, że rzadko wymagało więcej niż jednego lub dwóch kroków, aby znaleźć dobre rozwiązanie.

Chociaż na to nie spojrzałem (cóż, poza szybkim spojrzeniem) Mitchell opublikował trochę nowszych prac nad śledzeniem promieni za pomocą matematyki interwałowej.

(Powinienem dodać, że jeśli wykonujesz tylko powierzchnie Beziera, to metoda interwałowa może być nieco „przesadzona”, ponieważ możesz użyć sztuczek takich jak kwitnienie, aby uzyskać granice i pochodne. Jeśli jednak łączysz krzywe Beziera z innymi funkcjami, np. obrót wokół osi, wtedy jego ogólność jest bardziej przydatna).

https://www.shadertoy.com/results?query=bezier sortuj według wieku, w przypadku problemów ze zgodnością:

, ... pokazuje wiele rozwiązań wielu podzbiorów splajnu, albo zwracając odległość do splajnu 2d, albo śledząc łatkę 3d. Splajny i łatki występują w wielu formach. ciężki jest najprostszy, bezier jest prosty, a zakręty zbyt skomplikowane. Im więcej ograniczeń dodasz do splajnu, tym łatwiej będzie. NURBS to nadmierne rozszerzenie rozszerzenia; - jego nierównomierność ciężarów („NU”) zmniejsza wydajność w porównaniu z bardziej symetrycznymi splajnami - jej Ration-al-ness (R) również dodaje pewnej złożoności, do segmentowania (racjonowania) i mieszania z sąsiednimi segmentami (rekurencyjnie rozwiązany).

Bezier-patch-tracing jest rozwiązaniem rootowania, a tym samym kontekstowym priorytetem jest precyzja; w jakiej kolejności rozwiązać równanie kwadratowe. staje się to niepraktyczne na wyższych wykładnikach niż sześciennych, z powodu wykładniczej złożoności i utraty precyzji.

ray-marching == śledzenie kuli jest prostszym heurystycznym podejściem do rozwiązywania root, który wydaje się być prostym i najbardziej wydajnym rozwiązaniem do renderowania większości łat splajnów.

Reprezentacja Lagrange'a upraszcza śledzenie / marsz (ponieważ punkty L znajdują się NA splajnie, podczas gdy punkty ControlVector (dokładnie tego samego splajnu) rzadko znajdują się na splajnie)

Szczególny przypadek splajnu ciężkiego, w którym pierwsze pochodne stat i end są == 0. upraszcza ciągłość i wymaga mniejszych różnic (mniej odejmowania). Łata Heavyensine można skutecznie prześledzić w jednym przejściu: https://www.shadertoy.com/view/4djfW3, podczas gdy inne sześcienne (lub wyższe) splajny sprawiają, że heurystyczne podejście do śledzenia kul / marszowania promieni jest bardziej wydajne (i „ wystarczająco precyzyjny ”) niż odważny, aby analitycznie obliczyć wszystkie pierwiastki, aby zachować najmniejszy dodatni pierwiastek (z wykładniczo narastającymi błędami precyzji dla każdego pierwiastka).

W grafice komputerowej splajny i łaty zostały prawie całkowicie zastąpione przez Z-brushing do 2006 roku. Z-brushing wykorzystuje mapy przemieszczeń o jednorodnych współrzędnych, a nawet używając „typu”, który jest połączeniem sfery i odcinków linii (odcinki linii mają promień 0, kule mają długość 0, związek jest prosty i użyteczny). W przypadku niewielkiej utraty precyzji w celu uzyskania dużego wzrostu wydajności przy stosunkowo niskim koszcie pamięci dla tabeli przeglądowej, którą można łatwo zdynamizować na GPU.