13.2.3 Algorithmus für die Kugelfilterung

Der Algorithmus des Kugelfilters dient zur Berechnung der Tiefe k in der eine Kugel über eine Fläche rollt, während eine feste Anzahl von Punkten in die Kugel eindringt. Der tiefste Punkt der Kugel beschreibt die zur Filterung verwendete Welligkeit der Fläche.
Es wäre möglich mit einem iterativen Algorithmus die Kugel über jeden Punkt der Meßfläche zu setzen, und so lange abzusenken, bis die geforderte Zahl von Punkten eingedrungen ist. Ein solcher Algorithmus erfordert aber eine unnötig hohe Rechenzeit, da für jeden Punkt der Meßfläche eine Iteration durchzuführen wäre. Hinzu kommt, daß iterative Methoden das Ergebnis nur näherungsweise berechnen. Eine schnellere und nicht iterative Methode wird im folgenden beschrieben.
In einem ersten Schritt wird eine neue Fläche in der x-y-Ebene generiert. Die z-Werte werden so berechnet, daß sich die Form eines Ausschnitts einer Kugel mit dem Radius R ergibt. Der tiefste Punkt der Kugel P1 liegt in der Mitte der Fläche. Die Größe der Kugelfläche hängt von Radius der Kugel, der Anzahl der eindringenden Punkte und der Rauheit der Topografie ab. Zu große Kugelflächen führen zu unnötig hohen Rechenzeiten. Wird eine zu kleine Fläche gewählt, dann ist es möglich, daß neben den Ausschnitt der eingesunkenen Kugel Spitzen überstehen, die bei größerem Kugelausschnitt noch in die Kugel eindringen würden. Um sicherzugehen sollte die Größe des Kugelausschnittes so gewählt werden, daß der minimale Abstand in z-Richtung von P1 zu jedem Punkt des Randes des Kugelausschnittes mindestens der Höhe St der Topografie entspricht. Damit wird sichergestellt, daß selbst bei voll in die Topografie eingesunkener Kugel, keine Spitzen über den Kugelrand ragen.
Der tiefste Punkt der Kugel P1 wird in einer ersten Programmschleife in konstanter Höhe z_K(P1) über jedem Punkt P2 der Meßfläche positioniert (Schleifenvariablen 0<i<i_max, 0<j<j_max). In einer darin verschachtelten zweiten Schleife (Schleifenvariablen 0<k<k_max, 0<l<l_max) wird für jeden Punkt der Kugelfläche P3 der Abstand zu dem darunterliegenden Punkt der Meßfläche P4 berechnet. Bei n eindringenden Punkten wird ein Vektor V der Dimension n+1 definiert, in den die berechneten Werte der Abstände der Größe nach einsortiert werden. Ist die zweite Schleife abgearbeitet, dann enthält der Vektor V die n+1 geringsten Abstände. Der n+1-te Wert dieses Vektors entspricht den n+1-geringsten Abstand, um den die Kugel abgesenkt werden muß, damit n Punkte in die Kugel eindringen. Der tiefste Punkt der abgesenkten Kugel, der dem z-Wert der Welligkeit z_W am Punkt i, j der Meßfläche entspricht, berechnet sich dann aus der Differenz der Höhe der nicht abgesenkten Kugel z_K(P1) und dem n+1-ten Wert des Vektors V.

z_W(i,j):
Die Höhe des Punktes des Welligkeitsprofils
z_K(P1):
Der tiefste Punkt der Kugel
min_n{}:
Der n-kleinste Wert der Menge {}
P3(k,l):
Die Höhe des Punktes der Kugel mit den Koordinaten x=k und y=l über der von x und y aufgespannten Ebene durch den tiefsten Punkt der Kugel
P4(i,j,k,l):
Die Höhe des Punktes der Meßfläche unter dem Punkt P3 der Kugel