Surface Area Heuristic (SAH)

Споменахме, че има и по-добри подходи за избиране на оптимална разделяща равнина при стоежа на K-d дървото. Един от тях се нарича Surface Area Heuristic (SAH); той цели да отдели несиметрично разположени триъгълници (например, концентрирани в единия край на Bounding Box-а) от свободните пространства, като взима под внимание не само броя триъгълници във всяко подпространство, ами и относителната големина на подпространството. "Големината" определяме чрез площта на повърхнината на bounding box-a (т.е. при bounding box WxHxL, S = 2 * (W*H + W*L + H*L))

Формално, нещата изглеждат така: оценката f за единично пространство е:

f := costIntersect * numTriangles * surfaceArea,

докато, ако пространството разделим на две, цената е

f_split := costSplit + f(left) + f(right)
         := costSplit + costIntersect * numTrianglesLeft * surfaceAreaLeft + costIntersect * numTrianglesRight * surfaceAreaRight

където costSplit и costIntersect са относителните "цени" за, респективно, обхождане на възел от дървото, и за пресичане с възел (Jacco Bikker предлага 0.3 и 1.0, респективно), a площите (surfaceArea, surfaceAreaLeft и surfaceAreaRight) са "относителни": напр., surfaceAreaLeft се определя като отношението на истинската площ на лявото подпространство спрямо истинската площ на цялото. Т.е., за самите сравнения, surfaceArea е винаги 1, а surfaceAreaLeft и surfaceAreaRight са дробни числа, по-малки от 1.

Целта е да намерим разделяща равнина, която минимизира тази оценка (f_split). Това е една тежка оптимизационна задача, но можете да намерите приблизително решение чрез някой от следните два подхода:

1) Разделяте интервала между левия и десния край на BBox-а на равномерни подинтервали (например 20 стъпки) и пресмятате SAH в тези 20 позиции; накрая взимате най-добрата
2) Ползвате троично търсене между левия и десния край (http://en.wikipedia.org/wiki/Ternary_search)

Като бонусче, можете да реализирате и termination критерия: ако f_split е по-голямо от f без значение каква разделяща равнина избираме, то най-добре да спрем дотук и да обявим възела за листо (повече детайли относно SAH има в статията на Jacco Bikker: http://devmaster.net/posts/2842/raytracing-theory-implementation-part-7-... (втората половина))
В tag homework9 съм добавил и специална сцена с много тежък обект (станфордския дракон, 100 000 триъгълника, data/hw9/dragon.trinity). Ползвайте дракона за сравнения; при добре реализиран SAH трябва да постигнете ускорение между 10% и 30% в пресичането (строежа на дървото ще е доста по-бавен, но това не бива да ви притеснява).
Сцената с винената чаша (testmesh.trinity) също е добра сцена (с тежка геометрия), но там подобрението ще е по-малко (триъгълните мрежи са по-симетрични и с по-слабо изразени струпвания на триъгълници - там SAH не показва истинската си сила спрямо тривиалното "деление на 2")