Roberts-Algorithmus

Der Roberts-Algorithmus ist ein Verfahren aus der Computergrafik zur Verdeckungsberechnung von Polyedern. Er wurde 1963 von Larry Roberts veröffentlicht und ist damit der älteste Algorithmus zur Verdeckungsberechnung.

Prinzip

Der Roberts-Algorithmus verarbeitet Polygonkanten und setzt voraus, dass diese zu konvexen Polyedern (Polygonnetzen) gehören. Konkave Körper müssen erst in mehrere konvexe aufgeteilt werden.

Der Roberts-Algorithmus wendet zunächst Backface Culling an, um zu nicht sichtbaren Polygonen gehörende Kanten zu entfernen. Anschließend wird jede verbleibende Kante nach und nach gegen jedes Polyeder, das sie verdecken könnte, getestet. Durch einfache Vergleiche der Koordinaten lassen sich viele Kanten trivial eliminieren.

Beim Vergleich einer Kante mit der durch einen Polyeder aufgespannten Fläche könnten drei Fälle auftreten:

1. Anfangs- und Endpunkt liegen vor der Fläche: in diesem Fall wird die Kante nicht verdeckt.
2. Anfangs- und Endpunkt liegen hinter der Fläche: hier müssen zunächst die Schnittpunkte mit allen Kanten der Fläche ermittelt werden, um den Teil der Kante zu ermitteln, der innerhalb der Fläche liegt und somit gelöscht werden kann. Falls es keine Schnittpunkte gibt, liegt die Kante entweder komplett innerhalb oder komplett außerhalb des getesteten Polyeders.
3. Anfangs- und Endpunkt liegen auf unterschiedlichen Seiten der Ebene: auch hier muss der Schnittpunkt ermittelt werden, an dem die Kante geteilt wird. Mit den entstehenden zwei Teilkanten wird wie oben beschrieben verfahren.

Der Sichtbarkeitstest des Roberts-Algorithmus verwendet lineare Optimierung, um die Werte der Geradengleichung zu ermitteln, für die der Projektionsstrahl durch ein Polyeder verläuft und somit der entsprechende Punkt verdeckt ist.

Da jede Kante gegen jedes Polyeder getestet wird, hat der Roberts-Algorithmus theoretisch quadratische Laufzeit. Dies und das größere Interesse an bildpräzisen Verfahren zur Verdeckungsberechnung führte dazu, dass der Roberts-Algorithmus wenig beachtet wurde. Er lässt sich jedoch durch eine vorausgehende Sortierung nach den z-Koordinaten und einfache Bounding-Volume-Tests so verbessern, dass er eine nahezu lineare Laufzeit aufweist.

Literatur

• Lawrence G. Roberts: Machine Perception Of Three-Dimensional Solids. Lincoln Laboratory, TR 315, MIT, Cambridge 1963 (Online)
• David F. Rogers: Procedural Elements for Computer Graphics. WCB/McGraw-Hill, Boston 1998, ISBN 0-07-053548-5