Root Finder - podsumowanie

Najgorzej sprawuje się metoda Secant, która potrafi zrenderować niepoprawnie torus. Pozostałe metody renderują go bezbłędnie. Miejsca w których metody nie polegające na pochodnej zawodzą to renderowanie prosto ze wzoru brył typu superelipsoida, supertoroid, superegg. Wydaje się, że o wiele lepiej powinny się tam sprawdzić metody polegające na pochodnej.

Porównanie czasów renderowania typowej sceny, w której funkcja dana jest wielomianem (intersekcja z torusem):

Bisection: 7.9
Modified Regula Falsi: 7.4
Secant: 7.7
Newton: 7.4
Halley: 7.7

Widzimy więc, że najszybsza metoda Modified Regula Falsi jest zarazem tą najmniej problematyczną - zawsze znajduje rozwiązanie. Po zaimplementowaniu bryły Superquadric mogłem trochę dokładniej przetestować algorytmy znajdowania miejsc zerowych. Okazało się, że Newton i Halley i prawdopodobnie wszystkie oparte na analizie pochodnych nie działają. Raz, że nie powinny, gdyż bryła ta nie ma powierzchni ciągłej. Dwa, że Root Finder-y tego typu bardzo łatwo potrafią wyskoczyć z lokalnego minimum i zacząć aproksymować do sąsiedniego miejsca zerowego. Na razie je zostawiłem, ale generalnie nie nadają się one w tej chwili do niczego. Próbowałem także zaimplementować Root Finder, który możemy nazwać Brute Forcem. Idziemy co krok rzędu 1e-4 i jeśli namierzymy zmianę znaku to szukamy w takim małym przedziale miejsca zerowego. Działa, ale jest niezwykle wolny, niepraktyczny.

Wszystkie metody znajdowania miejsc zerowych wykorzystują bezwzględny test na przerwanie iteracji. Test względny wymagał by znajomości wielkości obiektu. W moim przypadku większość renderowanych brył jest ograniczona w małym przedziale, typowo (-1,1), dzięki czemu RootFinder-y nie wymagają podawania względnych warunków na zakończenie testów.