Grundlagen der geometrischen Datenverarbeitung

Das Bild eines reellen Intervalls I (offen, geschlossen, halboffen, endlich, unendlich) unter einer stetigen, lokal injektiven Abbildung in den ℝ² oder ℝ³ heißt Kurve. Im ℝ² ergibt sich eine ebene Kurve, im ℝ³ i. allg. eine Raumkurve. Wird ein Ursprung O gewählt, so ist die Kurve eine Menge von Punkten P _i, deren Ortsvektoren P _i durch eine vektorwertige Funktion X = X(t) des Parameters t ∈ I beschrieben werden, die lokal eindeutig ist. Die Funktion X(t) wird eine Parameterdarstellung der Kurve genannt.

Wir konnten bei der Untersuchung der kubischen Splinekurven (Monome als Basisfunktionen) keine geometrische Deutung der Splinekoeffizienten herleiten. Es lassen sich aber andere polynomiale Basisfunktionen angeben, bei denen die Splinekoeffizienten b _i geometrische Bedeutung haben, d.h. z.B., daß die b _i den ungefähren Verlauf der Kurve (oder Fläche) festlegen oder daß aus der Lage der Splinekoeffizienten b _i auf geometrische Eigenschaften der Kurve (oder Fläche) geschlossen werden kann. Solche Basisfunktionen haben in der Praxis für das interaktive Arbeiten große Bedeutung, da alle Prozesse geometrisierbar sind. Wir werden im wesentlichen zwei Typen solcher Splinefunktionen betrachten

Den in den vorausgegehenden Kapiteln behandelten Splinekurven lag das Konzept der C^r-Stetigkeit aneinander anschließender Segmente, d.h. Übereinstimmung der ersten r Ableitungen in gemeinsamen Segmentrandpunkten, zugrunde. Dies ist aber ein recht formales Argument, das analytisch begründet ist und unter Umständen eine äußerst unbefriedigende Interpretation des Glättebegriffes wiedergibt, wie das Beispiel aus Fig. 5.1 veranschaulicht. Zudem erweist sich der C^r-Übergang für viele Anwendungen als zu steif. Einerseits kann die Interpolation ungleichmäßig verteilter Daten sehr ungünstig ausfallen, auch bei Verwendung einer nicht-äquidistanten Parametrisierung, zum Beispiel dann, wenn ein Segment große Krümmungsänderungen relativ zu den Nachbarsegmenten beinhaltet. Andererseits lassen sich bestimmte (Flächen-) Segmentkonfigurationen erst gar nicht C^r-stetig realisieren (s. Kap. 7). Zudem ist C^r-Stetigkeit nicht invariant bzgl. Reparametrisierungen, wird also durch eine Umparametrisierung zerstört. Umparametrisierungen können jedoch vielfälltig vorteilhaft eingesetzt werden, etwa

Nachdem wir uns bisher mit den Eigenschaften der (klassischen) Spline-Kurven, der Bézier-Spline-Kurven, der B-Splines und der geometrischen Spline-Kurven beschäftigt haben, wenden wir uns jetzt den Spline-Flächen zu.

Wir wollen nun die in Kap. 5 besprochenen geometrischen Übergänge für Kurven auf bivariate Darstellungen übertragen. Die Notwendigkeit hierfür geben sternförmige Segmentkonfigurationen (s. Fig. 7.1) oder auch das aneinander Anschließen verschiedenartiger Segmenttypen (s. Fig. 7.2), die nicht immer C^r-stetig realisierbar sind und daher allgemeine, mehr geometrische Übergangsbedingungen erfordern. Der geometrische Übergang wird gegenüber den C^r-Anschlüssen vor allem aber auch dadurch ausgezeichnet, daß er invariant bzgl. Parametertransformationen ist, da seine Definition vom Begriff der Berührordnung ausgeht.

Wir haben bisher Flächen des ℝ³ beschrieben über

Bei Anwendungen z.B. in der Geologie, Meteorologie, Kartographie aber auch beim Digitalisieren von Modelloberflächen können unregelmäßig verteilte Daten (scattered data) auftreten, die durch eine Fläche interpoliert oder approximiert werden sollen. Das zu lösende Interpolationsproblem lautet also: gegeben sind N+1 Abszissen x_i = (x_i, y_i) ∈ ℝ², i = 0(1) N, mit zugehörigen Ordinaten (z.B. Meßwerten) z_i, gesucht ist eine Funktion f(x) = f (x, y) derart, daß z_i = f(x_i, y_i) gilt. Das Approximations problerm kann als (weighted oder auch als moving) least square Problem I(f) = Σ ω_i(x) (f(x_i, y_i) − z_i)² → Min. behandelt werden, oder, was in jüngster Zeit immer häufiger geschieht, als smoothing Problem I(f) = Σ ω_i(x) (f(x_i, y_i) − z_i)²+ λ J(f) → Min., mit Glättungsparameter λ und “physikalischem Term” J(f), z.B. der Biegeenergie einer eingespannten, elastischen dünnen Platte, etc. Wobei bei der scattered data Interpolation bzw. Approximation jedoch, im Gegensatz zur Aufgabenstellung der vorausgehenden Kapitel, keine speziellen Forderungen an die Datenpunkte (x_i, y_i, z_i), insbesondere in Bezug auf Verteilungsanordnung und -dichte, gestellt werden. Wir wollen uns hier auf das Interpolationsproblem beschränken. Das Approximationsproblem wurde bereits in den Kap. 2.4, 2.5 und 4.4 angesprochen. Weiterhin sei auch verwiesen auf [DIE 81], [FARW 86], [FOL 87c], [FRA 87], [HAY 74], [HU 86], [MCLA 74, 76], [MCM 87], [LAN 79, 86], [SCHM 79, 83, 85], [SCHU 76], sowie auf die Literaturliste [FRA 87a]; zum Smoothing s. a. Kap. 13.

In den verschiedenen Modelliersystemen des Computer-aided design werden unterschiedliche Methoden zur mathematischen Beschreibung von Freiformkurven und Freiformflächen eingesetzt. So finden z.B. Monome (gewöhnliche Polynome) vom Grade 3, 5 bis zum Grade 19 Verwendung, aber auch Bernstein-Polynome unterschiedlichen Polynomgrades und B-Spline-Basisfunktionen unterschiedlicher Ordnung [BÖH 84]. Es werden oft aber auch Gordon-Coons-Flächen oder nichtlineare Basisfunktionen eingesetzt. Müssen nun zwischen verschiedenen Modelliersystemen Daten ausgetauscht werden, weil z.B. ein Zulieferer bestimmte im System des Herstellers generierte Teile mit seinem eigenen System bearbeiten muß, ist eine Konversion oder Transformation der Kurven- und Flächendarstellung notwendig. Dabei muß entweder auf unterschiedliche Polynomgrade oder aber von einer Darstellungsmethode (beschrieben durch einen bestimmten Typ von Basisfunktionen) in eine andere transformiert werden. Leider sind diese Transformationen im allgemeinen nicht exakt möglich, daher muß auf approximative Methoden zurückgegriffen werden. Damit entsteht ein zusätzliches Problem: Zu einem vorgegebenen Approximationsfehler soll eine gegebene Anzahl von Splineflächen nach der Transformation mit einer möglichst geringen Anzahl von Flächensegmenten (Patches) dargestellt werden, d.h. die gegebenen Flächenstücke müssen entweder zu neuen Flächensegmenten verschmolzen oder zusätzlich segmentiert werden.

Während sich das Interesse im Bereich des CAGD in der Vergangenheit hauptsächlich auf die Kurven- und Flächenbeschreibung und die Kurven- und Flächenverarbeitung beschränkte, gewinnen in jüngster Zeit auch höherdimensionale, multivariable Objekte wie Volumina und Hyperfläches des ℝⁿ (n > 3) immer mehr an Bedeutung. Anwendungsbeispiele multivariabler Objekte sind z.B. gegeben durch

(für weitere Details und Beispiele siehe [ALF 89], [CASA 85], [FARO 85a], [SED 85b, 86a]).

Bei vielen Anwendungen müssen die Schnittpunkte von (ebenen) Kurven oder auch Schnittkurven von Flächen ermittelt werden, etwa

Beim Interpolieren oder Approximieren von Kurven und Flächen mit Spline-kurven oder Splineflächen können sich unerwünschte Kurven- oder Flächenbereiche einstellen. So kann z.B. in bestimmten Situationen ein konvexes Kurvenoder Flächenstück gefordert werden (z.B. Automobil dach, Schiffsrumpf), durch die Interpolations- oder Approximationsdaten treten aber (u.U. nur leichte) “Welligkeiten” auf, die nach Durchlaufen des Interpolations- oder Approximationsprozesses noch nachträglich beseitigt werden müssen. Diese Beseitigung unerwünschter Krümmungsbereiche in Kurven- oder Flächendarstellungen wird als Glätten bezeichnet. Argumente für das Erfüllen gewisser Glattheitsforderungen an Kurven oder Flächen sind z.B.