Quadrantized fastest descent search

Както споменахме на лекцията за heightfield-овете, една възможна оптимизация на алгоритъма на най-бързото спускане е да модифицираме getHeight() да взима под внимание само квадранта, в който се намира посоката на лъча. По-формално, нещата изглеждат така:

Квадрантът (0..3) се определя от знаците на ray.dir.x и ray.dir.z (номерирайте си квадрантите както намерите за добре)
getHeight(x, y, 2^k, quadrant) връща най-високия връх в квадрата с големина 2^kx2^k, който "започва" от (x, y), и е в "посока" на дадения квадрант.

Трябва да модифицирате Heightfield::buildStruct(), така че да пресмята правилно новата структура; ето ви пример за пресмятане на getHeight(x, y, 2², 0)
(ако приемем, че квадрант 0 е +X +Y):

Т.е. за да пресметнем най-високата стойност в квадратче 4х4, започващо от (x, y) и "вървящо" нагоре и надясно, трябва да вземем максималната стойност от четирите 2х2 подквадратчета A, B, C и D.

Модификацията на Heightfield::intersect() е само да се ползва правилния квадрант при извикванията на getHeight().

За тестове, ползвайте heightfield.fmiray сцената, като, за да стане ефекта от оптимизацията по-видим, увеличете скалирането на Heightfield-да от 20 на 40 (и нивото на водата от 7 на 14; можете и да разкарате осветлението (lightIntensity (0, 0, 0)). При тази сцена можете да очаквате ускорение от около 5-10% за тази оптимизация.