IT-lexikon › Programmering › Möller–Trumbore

Möller–Trumbore

Programmering In English → Uppdaterad: 2026-10-27

Standardalgoritmen för att avgöra om och var en stråle träffar en triangel, utan att först räkna ut triangelns plan.

Det naiva sättet är tvåstegs: skär strålen med triangelns plan och testa sedan om träffpunkten ligger innanför de tre kanterna. Tomas Möller och Ben Trumbore visade 1997 att man kan hoppa över planet helt. Strålen skrivs som en punkt plus en riktning, triangeln som ett hörn plus två kantvektorer, och ekvationssystemet löses med Cramers regel — ett par kryssprodukter och skalärprodukter. Ut kommer avståndet t och de barycentriska koordinaterna u och v på en gång.

Ingen förberäknad plandata behöver lagras per triangel, vilket var poängen när minnet var trångt. I dag sitter den i nästan varje mjukvarustrålspårare, i raycasting mot meshkolliderare och i plockning med musen. Tidiga utgångar på u och v gör att de flesta missar avbryts efter halva jobbet.

← Tillbaka till lexikonet