По-бързо трасиране на релефни карти

В лекция 9 (слайд 43) казахме, че алгоритъмът "най-бързо спускане" може да се реализира със сложност O(log N), но текущата ни реализация е с O(log² N). Задачата е да разкараме този ²!

За какво става дума: нека разгледаме как върви трасирането на един типичен лъч.

1. Лъчът се премества до пресичане с BBox-а на релефната карта;
2. Намира се най-голямото разстояние, което може да се измине безопасно, без да се ударим в някой връх (търсенето става линейно по нивата - тук е вътрешният logN от сложността). Вероятно в началото ще можем да прескочим огромно разстояние - ще се възползваме от ниво k и ще прескочим 2^k;
3. Преместили сме се, намираме най-голямото разстояние, което можем да прескочим вече от новата позиция. Вероятно то ще е само едно ниво по-малко от предходната стъпка - ниво k, и ще прескочим 2^{k - 1};
4. По аналогия с точки 2 и 3, алгоритъмът ще сваля k с 1 (понякога повече) на всяка стъпка, докато стигне до k = 0 и там намери истинската пресечна точка. Външният while цикъл следователно се завърта също logN пъти, като на всяка итерация се търси (с вътрешния while цикъл) кое е правилното ниво - и оттам идва O(log² N) сложността

Очевидно - глупаво е да търсим линейно най-доброто k на всяка стъпка — може, естествено, да се замени с двоично търсене, но има и по-добра идея — вместо това, може да пробваме да тръгнем от предходно намереното k и да увеличаваме/намаляваме (според случая), докато условието стане изпълнено. Така, в общия случай, вътрешният while цикъл ще се съкрати - от logN операции, до 1-2 (средно).

Допълнителна оптимизация е да видите дали лъчът върви нагоре или надолу, и вместо да смятате min(p.y, p.y + ray.dir.y * (1 << k)), просто да се ползва едното от двете, което е гарантирано по-малко.

Очакваната полза от ускорението е 5-10% на heightfield.retrace. За по-прецизно измерване, заменете разположението на камерата с "top view" (вижте коментарите в сценовия файл).