В лекция 9 споменахме, че структурата за ускорено пресичане с релефни карти може да се оптимизира.

Задачата ви е точно това - оптимзирайте времето за рендериране на сцената heightfield.qmdg, като изследвате къде се губи време и ускорете сметките в горещите места.

Оценяването на решенията ви ще бъде по обективни критерии, по следната скала:

• Ускорение 5-10%: 6т
• Ускорение 10-15%: 7т
• Ускорение 15-20%: 8т
• Ускорение над 20%: 9т

Измерването ще се прави на моята домашна машина (gcc 4.8, AMD Phenom II X6, 3.2 GHz), като решенията ви ще се пускат трикратно и ще се взима най-доброто време за рендериране.

Като идеи какво може да се оптимизира:

1. while цикълът в ядрото на алгоритъма за най-бързото спускане (в блока "useOptimization") може да се замени с двоично търсене;
2. смятането на min() всеки път, в този цикъл, може да се избегне;
3. getHighest() прави куп проверки за входните координати, които в случая се повтарят ненужно - направете ги само веднъж и после ползвайте директно highMap[][]
4. Има и други хитри идеи, но нека да не ви ги издавам всичките - забавлявайте се със задачата :)