IT-lexikon › Programmering › Ytarea-heuristik (SAH)

Ytarea-heuristik (SAH)

Programmering In English → Uppdaterad: 2026-10-26

En kostnadsmodell som väljer var ett accelerationsträd ska delas genom att väga sannolikheten att en stråle träffar varje gren mot antalet objekt i den.

När man bygger en BVH eller ett kd-träd måste varje nod delas någonstans. SAH väljer delningen som minimerar förväntad traverseringskostnad: sannolikheten att en slumpmässig stråle träffar en barnnod är proportionell mot nodens yta, så kostnaden blir ytans andel gånger antalet objekt i barnet, summerat över barnen.

Idén går tillbaka till Goldsmith och Salmon (1987) och blev standard för strålspårning. Att utvärdera alla möjliga delningar är dyrt, så byggare använder binning — man sorterar objekten i några få fack och testar bara gränserna mellan dem. Resultatet är träd som är märkbart snabbare att traversera än naiva mitt-delningar.

← Tillbaka till lexikonet