Surface Area Heuristic

Споменахме, че има и по-добри подходи за избиране на оптимална разделяща равнина при стоежа на 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, респективно.

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

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

Като бонусче, можете да реализирате и termination критерия: ако f_split е по-голямо от f без значение каква разделяща равнина избираме, то най-добре да спрем дотук и да обявим възела за листо (повече детайли относно SAH има в статията на Jacco Bikker: http://devmaster.net/posts/raytracing-theory-implementation-part-7-kd-tr... (втората половина))
В ревизия 252 съм добавил и специална сцена с много тежък обект (станфордския дракон, 100 000 триъгълника). След като си изготвите прототипа върху meshes.fmiray и работи добре, ползвайте дракона за сравнения; при добре реализиран SAH трябва да постигнете ускорение между 10% и 30% в пресичането (строежа на дървото ще е доста по-бавен, но това не бива да ви притеснява).