Paper: On improving kd-trees for ray shooting

Omdat de paper "On building fast kd-trees for ray tracing, and on doing that in O(N log N)" nogal zware kost lijkt op het eerste gezicht ben ik begonnen met iets lichter. Dat iets lichter is de paper "On improving kd-trees for ray shooting" van Vlastimil Havran et al.

Ik schets hier slecht een kort overzicht geen samenvatting, om alles te weten moet je de paper zelf eens bekijken. De paper behandelt 2 methodes om kd-trees te verbeteren:

1. Een automatisch stopcriterium (Automatic Termination Criteria , ATC) voor het bouwen van een kd-tree. Normaal wordt de diepte en het aantal objecten per leaf door 2 ad-hoc constanten bepaald, voor deze constanten is geen wetenschappelijk argument. Meestal worden deze gekozen door experimenteren. Het ATC probeert het minimum van de globale kostenfunctie te benaderen en te stoppen als dit min of meer bereikt is.
2. Het split clipping algoritme splitst de bounding box van een object in 2 kleinere bounding boxes wanneer het snijdt met een split plane.

ATC geeft een maximale verbetering van 20% en worst case een verslechtering van 10%. Split clipping geeft gemiddeld een verbetering van 9%.

Havran geeft zelf toe dat de resultaten niet spectaculair zijn maar zegt dat dit een eerste stap is in het construeren van data structuren zonder ad-hoc constanten van de gebruiker.

Voor mijn thesis zijn deze resultaten niet echt heel belangrijk (denk ik). Voor mij persoonlijk was het vooral belangrijk om wat meer feeling te krijgen met kd-trees.