LineSpace

Speziell im Bereich des Raytracings brauchen wir eine Datenstruktur, die uns richtungsabhängige Abfragen ermöglicht (Schattenfühler, vorderster Schnittpunkt oder Sortierung von Objekten entlang einer Richtung). Bestehende Datenstrukturen unterteilen den Raum in Teilräume, um diese Abfrage zu beschleunigen; sie erfordern aber nach wie vor eine Traversierung dieser Teilräume. Der LineSpace unterteilt die Teilräumen schließlich in Richtungen.