Geometry Processing - Exam

Aufgabe 1)

Maschinelles Lernen für 3D-DatenAngewendet auf 3D-Daten ermöglicht maschinelles Lernen die Verarbeitung und Analyse komplexer geometrischer Strukturen. Zu den gängigen Techniken gehören PointNet, PointNet++ und DGCNN. Die Eingaben können aus Punktwolken, volumetrischen Daten oder Mesh-Daten bestehen. Anwendungen umfassen Objektklassifikation, Segmentierung und 3D-Rekonstruktion. Die Repräsentation solcher Daten erfolgt über Voxels, Octrees oder Signed Distance Functions (SDF). Wesentliche Verlustfunktionen sind die Chamfer Distance und die Earth Mover's Distance (EMD), während die Evaluation gängigerweise mittels Intersection over Union (IoU) und Mean Absolute Error (MAE) erfolgt. Zur Umsetzung solcher Modelle können Python-Bibliotheken wie TensorFlow, PyTorch und Open3D verwendet werden.

a)

a) Erkläre die Struktur und Funktionsweise von PointNet. Diskutiere, wie PointNet im Vergleich zu traditionellen CNNs für Bilddaten funktioniert und warum es speziell für Punktwolken geeignet ist.

Lösung:

• Einführung in PointNet:PointNet ist eine Deep-Learning-Architektur, die speziell für die Verarbeitung und Analyse von Punktwolken entwickelt wurde. Punktwolken sind eine Sammlung von Punkten im Raum, die typischerweise aus 3D-Scannern stammen. Diese Punkte können komplexe geometrische Strukturen im Raum darstellen.

• Struktur und Funktionsweise von PointNet:
  • 1. Input Transformation:Jede Punktwolke wird als Eingabe in das Netzwerk gegeben. Die Punkte werden durch einen MLP (Multilayer Perceptron) transformiert, der eine Transformation auf die Eingaben anwendet, um sie in einen höheren dimensionalen Raum zu projizieren.
  • 2. Point Feature Transformation:Ein zweiter MLP wird verwendet, um Punktmerkmale zu lernen. Diese Merkmale werden individuell für jeden Punkt berechnet.
  • 3. Symmetrische Funktion:Eine symmetrische Funktion wie das Maximum oder Mittelwert wird angewendet, um eine aggregierte Darstellung der Punktwolke zu erzeugen. Diese Funktion ermöglicht es, die Reihenfolge der Punkte zu ignorieren und invarianten Features zu erzeugen.
  • 4. Global Feature:Das aggregierte Feature repräsentiert die gesamte Punktwolke und kann für verschiedene Aufgaben wie Klassifikation oder Segmentierung verwendet werden.

• Vergleich von PointNet mit traditionellen CNNs:
  • 1. Datenstruktur:Im Gegensatz zu Bildern, die auf einer regelmäßigen Gitterstruktur basieren, sind Punktwolken unregelmäßig und unstrukturiert. Daher sind traditionelle CNNs, die für Gitterstrukturen (wie Bilder) ausgelegt sind, nicht direkt auf Punktwolken anwendbar.
  • 2. Invarianz gegenüber Permutation:PointNet ist so gestaltet, dass es invariant gegenüber der Reihenfolge der Punkte ist. Dies wird durch die symmetrische Aggregationsfunktion erreicht, die sicherstellt, dass die Reihenfolge der Eingabepunkte keinen Einfluss auf das Ergebnis hat.
  • 3. Translations- und Rotationsinvarianz:Durch die Anwendung von Transformationen und symmetrischen Funktionen ist PointNet robuster gegenüber Translationen und Rotationen der Punktwolke im Vergleich zu traditionellen CNNs.

• Warum PointNet speziell für Punktwolken geeignet ist:
  • 1. Direkte Verarbeitung:PointNet verarbeitet die Punktwolke direkt, ohne dass eine Umwandlung in eine andere Repräsentation (wie Voxel oder Mesh) erforderlich ist.
  • 2. Effizienz:Die direkte Verarbeitung führt zu einer effizienteren Modellierung der Daten, da der Rechenaufwand für die Umwandlung vermieden wird.
  • 3. Skalierbarkeit:PointNet ist skalierbar und kann auf große Punktwolken angewendet werden, indem nur eine Zufallsstichprobe (Subsampling) der Punkte verwendet wird.
  • 4. Anwendungsvielfalt:PointNet kann für eine Vielzahl von Anwendungen wie Objektklassifikation, Segmentierung und 3D-Rekonstruktion verwendet werden.

b)

b) Gegeben sei eine Punktwolke \(P\) mit \(n\) Punkten. Implementiere einen einfachen Klassifikationsalgorithmus in Python mit TensorFlow unter Verwendung der Chamfer Distance als Verlustfunktion. Achte darauf, dass Deine Implementierung mindestens eine vollverbundene Schicht enthält.

import tensorflow as tfclass SimplePointNet(tf.keras.Model):    def __init__(self, num_classes):        super(SimplePointNet, self).__init__()        self.fc1 = tf.keras.layers.Dense(128, activation='relu')        self.fc2 = tf.keras.layers.Dense(64, activation='relu')        self.fc3 = tf.keras.layers.Dense(num_classes, activation='softmax')    def call(self, inputs):        x = self.fc1(inputs)        x = self.fc2(x)        return self.fc3(x)# Verlustfunktion (Chamfer Distance)def chamfer_distance(y_true, y_pred):    batch_size = tf.shape(y_true)[0]    y_true = tf.expand_dims(y_true, axis=1)    y_pred = tf.expand_dims(y_pred, axis=2)    distances = tf.norm(y_true - y_pred, axis=-1)    min_dist_true_to_pred = tf.reduce_min(distances, axis=-1)    min_dist_pred_to_true = tf.reduce_min(distances, axis=-2)    return (tf.reduce_mean(min_dist_true_to_pred) + tf.reduce_mean(min_dist_pred_to_true)) / 2# Modellinstanz und Kompilierungnum_classes = 10model = SimplePointNet(num_classes)model.compile(optimizer='adam', loss=chamfer_distance, metrics=['accuracy'])

Lösung:

• Gegebene Punktwolke und Python-Implementierung:In diesem Subexercise sollst Du einen einfachen Klassifikationsalgorithmus in Python mit TensorFlow unter Verwendung der Chamfer Distance als Verlustfunktion implementieren. Eine Punktwolke ist eine Sammlung von Punkten im 3D-Raum, und die Chamfer Distance hilft dabei, die Distanz zwischen zwei Punktwolken zu messen. Unten findest Du eine ausführliche Implementierung.

• Code-Darstellung:

  import tensorflow as tfclass SimplePointNet(tf.keras.Model):    def __init__(self, num_classes):        super(SimplePointNet, self).__init__()        self.fc1 = tf.keras.layers.Dense(128, activation='relu')        self.fc2 = tf.keras.layers.Dense(64, activation='relu')        self.fc3 = tf.keras.layers.Dense(num_classes, activation='softmax')    def call(self, inputs):        x = self.fc1(inputs)        x = self.fc2(x)        return self.fc3(x)# Verlustfunktion (Chamfer Distance)def chamfer_distance(y_true, y_pred):    batch_size = tf.shape(y_true)[0]    y_true = tf.expand_dims(y_true, axis=1)    y_pred = tf.expand_dims(y_pred, axis=2)    distances = tf.norm(y_true - y_pred, axis=-1)    min_dist_true_to_pred = tf.reduce_min(distances, axis=-1)    min_dist_pred_to_true = tf.reduce_min(distances, axis=-2)    return (tf.reduce_mean(min_dist_true_to_pred) + tf.reduce_mean(min_dist_pred_to_true)) / 2# Modellinstanz und Kompilierungnum_classes = 10model = SimplePointNet(num_classes)model.compile(optimizer='adam', loss=chamfer_distance, metrics=['accuracy'])

• Erklärung der Implementierung:
  • 1. Modelldefinition:Hier definieren wir ein einfaches PointNet mit drei voll verbundenen Schichten (Dense Layers). Die erste Schicht hat 128 Einheiten, die zweite Schicht 64 Einheiten und die dritte Schicht (die Ausgabeschicht) hat so viele Einheiten wie es Klassen gibt (>num_classes<). Die Aktivierungsfunktionen sind 'relu' für die versteckten Schichten und 'softmax' für die Ausgabeschicht.
  • 2. Chamfer Distance:Die Chamfer Distance ist als Verlustfunktion implementiert. Sie misst die durchschnittliche Distanz zwischen den nächstgelegenen Punkten in zwei Punktwolken. Diese Loss-Funktion wird benutzt, um den Unterschied zwischen den vorhergesagten und den echten Punktwolken zu quantifizieren.
  • 3. Modellinstanz und Kompilierung:Eine Instanz von SimplePointNet wird für eine spezifische Anzahl an Klassen (>num_classes<) erstellt. Das Modell wird mit dem 'adam' Optimierer und der Chamfer Distance als Loss-Funktion kompiliert. Als Metrik verwenden wir die Genauigkeit ('accuracy').

Aufgabe 2)

In diesem Übungsteil sollst Du Dich mit der Verwendung von neuronalen Netzen für die Verarbeitung und Analyse von 3D-Daten beschäftigen. Dabei betrachten wir verschiedene 3D-Datenformate wie Punktwolken, Voxelgitter und Mesh-Representationen, untersuchen gängige Architekturen wie PointNet, PointNet++, VoxNet und MeshCNN, und diskutieren deren Anwendung in Bereichen wie Objekterkennung, Segmentierung und Rekonstruktion. Zudem sollst Du Techniken wie Datenaugmentation, Verlustfunktionen und Regularisierung verstehen und anwenden sowie Konzepte wie Invarianz gegenüber Transformationen und geometrische Merkmalsextraktion erklären.

a)

• Erläutere die drei gängigen 3D-Datenformate Punktwolken, Voxel und Meshes. Gehe dabei insbesondere auf die Vor- und Nachteile jeder Methode ein.
• Wähle eine der genannten Architekturen (PointNet, PointNet++, VoxNet oder MeshCNN) aus und erkläre deren Funktionsweise. Gehe dabei sowohl auf den allgemeinen Aufbau des Netzes als auch auf die spezielle Verarbeitung von 3D-Daten ein.
• Betrachte die Anwendung einer spezifischen Netzwerkarchitektur auf eine Aufgabe der 3D-Objekterkennung. Beschreibe den Prozess der Datenvorbereitung, die Wahl der passenden Verlustfunktion und mögliche Techniken zur Modellverbesserung.
• Gegeben ist eine Punktwolke eines 3D-Objekts mit insgesamt 1000 Punkten. Entwickle eine Methode zur Datenaugmentation für diese Punktwolke und erkläre, wie diese Augmentation die Leistung eines neuronalen Netzes verbessern kann.

Lösung:

• Punktwolken, Voxel und Meshes:
  • Punktwolken: Eine Punktwolke ist eine Sammlung von Punkten, die durch ihre xyz-Koordinaten definiert sind. Punktwolken bieten eine genaue Darstellung der Oberfläche eines 3D-Objekts und können direkt von 3D-Scannern generiert werden.Vorteile:
    • Genaue und detaillierte Erfassung der Oberfläche eines Objekts.
    • Effiziente Speicherung und geringe Dateigröße.
    Nachteile:
    • Keine expliziten Verbindungen zwischen den Punkten, was die Strukturierungsinformationen einschränkt.
    • Oft aufwendig in der Verarbeitung aufgrund der Vielzahl an Punkten.
  • Voxel: Voxel sind dreidimensionale Pixel, die in einem regelmäßigen Gitter angeordnet sind. Jedes Voxel repräsentiert ein Volumen im Raum und kann einen festen Wert, wie Dichte oder Intensität, speichern.Vorteile:
    • Gute Repräsentation von Volumeninformationen und inneren Strukturen eines Objekts.
    • Einfachere Verarbeitung für maschinelles Lernen und Visualisierungsalgorithmen.
    Nachteile:
    • Großer Speicherbedarf, insbesondere bei hoher Auflösung.
    • Kann weniger präzise sein als Punktwolken aufgrund der diskreten Natur.
  • Meshes: Ein Mesh besteht aus einer Sammlung von Polygonen, meist Dreiecken, die zusammen die Oberfläche eines 3D-Objekts bilden. Jedes Polygon wird durch seine Ecken (Vertices) definiert.Vorteile:
    • Gibt eine klare Struktur und Topologie der Objektoberfläche.
    • Effiziente Darstellung komplexer Geometrien mit weniger Speicherbedarf als Voxel.
    Nachteile:
    • Aufwändige Erstellung und Bearbeitung.
    • Braucht spezielle Algorithmen zur Verarbeitung und Manipulation.
• Architektur-Erklärung: PointNet: PointNet ist eine Architektur, die speziell zur Verarbeitung von Punktwolken entwickelt wurde. Es arbeitet direkt mit den xyz-Koordinaten der Punkte und nutzt eine Mischung aus MLPs (Multilayer Perceptrons) und Max-Pooling-Schichten.Allgemeiner Aufbau:
  • Die Eingabe ist eine Punktwolke, oft bestehend aus N Punkten mit jeweils 3 Koordinaten (xyz).
  • Jedem Punkt wird durch die MLPs eine höhere Dimensionsrepräsentation zugeordnet.
  • Ein globales Feature wird durch max-pooling aus den Punkterepräsentationen extrahiert, das die gesamte Punktwolke zusammenfasst.
  • Dieser globale Ausdrucksvektor wird für verschiedene Aufgaben wie Klassifizierung und Segmentierung verwendet.
  Verarbeitung von 3D-Daten:
  • Keine Notwendigkeit, die Punktwolke in ein anderes Format zu konvertieren (wie z.B. Voxel oder Mesh).
  • Verbessert die Invarianz gegenüber Permutationen und Transformationen der Punktwolken durch geeignete Netzwerkteilungen.
  • Einfachheit und Effizienz bei der Verarbeitung großer Mengen an 3D-Daten.
• Anwendung auf 3D-Objekterkennung:
  • Datenvorbereitung: Die Punktwolken müssen normalisiert und, falls nötig, zentriert werden. Dazu gehört auch das Sampling, um die Punktanzahl zu standardisieren.
  • Verlustfunktion: Für die Klassifizierung wird häufig die Kreuzentropieverlustfunktion verwendet. Bei Segmentierungsaufgaben kann der Dice-Loss oder die Kombination von Cross-Entropy und IoU (Intersection over Union) Loss sinnvoll sein.
  • Modellverbesserungstechniken:
    • Datenaugmentation: Rotation, Skalierung, Jittering der Punktwolken.
    • Regularisierung: Dropout, Gewichtsnormierung und Datenaugmentation zur Vermeidung von Overfitting.
    • Hyperparameter-Tuning: Optimierung der Lernrate, Batch-Größe und Anzahl der Epochen.
• Methode zur Datenaugmentation:
  • Rotation: Zufällige Rotation der Punktwolke um verschiedene Achsen.
  • Skalierung: Multiplikation der Punktkoordinaten mit einem Zufallswert, um die Größe zu verändern.
  • Jittering: Hinzufügen von kleinem Rauschen zu den Punktkoordinaten, um geringfügige Änderungen zu erzeugen.
  • Spiegelung: Spiegelung der Punktwolke entlang einer oder mehrere Achsen.
  Verbeserung der Netwerkleistung:
  • Durch die Datenaugmentation wird das Modell robuster gegenüber Variationen in den Eingabedaten.
  • Das Netz lernt invariant gegenüber Transformationen zu werden, was zu einer besseren Generalisierung führt.
  • Vermehrte Trainingsdaten führen häufig zu besseren Ergebnissen und robusteren Modellen.

Aufgabe 3)

Betrachte einen 3D-Datensatz eines Objekts, der für eine geometrische Verarbeitung vorbereitet werden soll. Der Datensatz enthält sowohl Rohdaten als auch einige durch Augmentation erzeugte Daten. Ziel ist es, die Datenqualität und -quantität zu verbessern, um die Genauigkeit einer 3D-Rekonstruktionsanwendung zu optimieren.

a)

a) Beschreibe die Schritte der Datenvorverarbeitung, die Du anwenden würdest, um die Rohdaten für die 3D-Rekonstruktion vorzubereiten. Stelle sicher, dass Du die Begriffe Bereinigung, Normalisierung und Transformation in Deine Antwort einbeziehst.

Lösung:

Um die Rohdaten für die 3D-Rekonstruktion vorzubereiten, müssen mehrere Schritte der Datenvorverarbeitung durchgeführt werden. Diese Schritte umfassen die Datenbereinigung, Normalisierung und Transformation. Hier sind die Schritte im Detail:

• Datenbereinigung: Zuerst müssen die Rohdaten auf Fehler, Ausreißer und fehlende Werte überprüft werden. Dies kann das Entfernen von Rauschen und irrelevanten Datenpunkten beinhalten. Zum Beispiel:
• Fehlende Werte können durch Interpolation oder durch statistische Methoden wie den Mittelwert oder Median der Nachbarpunkte aufgefüllt werden.
• Ausreißer können identifiziert und entfernt werden, indem man z.B. Punkte, die eine bestimmte Standardabweichung überschreiten, ausschließt.
• Daten-Normalisierung: Nachdem die Daten bereinigt wurden, ist der nächste Schritt die Normalisierung. Hierbei wird der Datensatz skaliert, um in einen bestimmten Wertebereich zu passen. Die Normalisierung sorgt dafür, dass alle Datenpunkte einen einheitlichen Maßstab haben. Zum Beispiel:
• Die Punkte können so skaliert werden, dass sie innerhalb eines Einheitswürfels liegen (z.B. \text{[0,1]}).
• Man kann auch eine z-Score-Normalisierung anwenden, bei der die Daten so skaliert werden, dass sie einen Mittelwert von 0 und eine Standardabweichung von 1 haben.
• Daten-Transformation: Der letzte Schritt besteht in der Transformation der Daten, um sie in eine geeignete Form für die 3D-Rekonstruktion zu bringen. Transformationen können verschiedene Formen annehmen, wie z.B.:
• Rotation und Translation, um die Daten in einem konsistenten Bezugssystem auszurichten.
• Verdichten der Punktwolke, um eine gleichmäßige Punktverteilung zu erreichen.
• Glätten der Oberfläche durch Algorithmen wie den Laplace-Glättungsfilter, um Rauschen weiter zu reduzieren.

Durch diese Schritte der Bereinigung, Normalisierung und Transformation wird die Qualität der Daten verbessert, was zu präziseren Ergebnissen in der 3D-Rekonstruktion führt.

b)

b) Angenommen, Du hast einen Datensatz von 500 Bildern eines Objektes. Du entscheidest Dich für Datenaugmentation, um die Robustheit Deines Modells zu verbessern. Beschreibe mindestens drei verschiedene Techniken der Datenaugmentation und erläutere, wie jede Technik die Datenmenge erhöht und zur Verbesserung des Modells beiträgt.

Lösung:

Um die Robustheit Deines Modells zu verbessern, kannst Du verschiedene Techniken der Datenaugmentation anwenden. Hier sind drei Techniken der Datenaugmentation und ihre Beiträge zur Verbesserung des Modells:

• Rotation: Durch die Rotation der Bilder um verschiedene Winkel (z.B. 90, 180, 270 Grad) kann man neue Trainingsdaten generieren. Diese Technik sorgt dafür, dass das Modell verschiedene Perspektiven des Objekts lernt und so widerstandsfähiger gegen Rotationen wird. Zum Beispiel, durch Rotation jedes Bildes um 90 Grad können 4 neue Bilder (einschließlich der Originalrotation) erzeugt werden, was die Datenmenge vervierfacht.
• Skalierung: Skalierung bedeutet, die Größe des Objekts in den Bildern zu verändern, während das Seitenverhältnis beibehalten wird. Diese Technik hilft dem Modell, unterschiedliche Größen desselben Objekts zu erkennen und führt zu einer robusteren Generali¬sierung. Die Bilder können vergrößert oder verkleinert werden, wodurch eine größere Variabilität innerhalb des Datensatzes entsteht.
• Hinzufügen von Rauschen: Das Einfügen von Rauschen in die Bilder ist eine weitere wichtige Augmentierungstechnik. Dies kann durch das Hinzufügen von zufälligem Pixelrauschen oder durch Verwischen erreicht werden. Diese Technik hilft dem Modell, robust gegen reale Bildfehler und Bildstörungen zu sein, die in Praxis auftreten können. Mit Rauschen versehene Bilder erweitern den Datensatz und verbessern die Fähigkeit des Modells, in realen Szenarien korrekt zu funktionieren.

Durch die Anwendung dieser Augmentierungstechniken wird die Datenmenge signifikant erhöht. Dies führt zu einer vielfältigeren Trainingsbasis und ermöglicht es dem Modell, allgemeiner und robuster gegenüber verschiedenen Bildverzerrungen und Szenarien zu sein.

c)

c) Ein wesentlicher Teil der Datenvorverarbeitung ist das Entfernen von Ausreißern. Gegeben sei eine Punktwolke, die die Koordinatenpunkte \[ (1,2,3), (2,3,4), (100,200,300), (3,4,5), (4,5,6) \] umfasst. Entwickle eine Methode, um den Ausreißer zu identifizieren und zu entfernen. Begründe mathematisch, warum Dein Ansatz sinnvoll ist, und beschreibe die zugehörigen Schritte in Pseudocode.

'pseudocodefunction remove_outliers(pointcloud):    mean = calculate_mean(pointcloud)    std_dev = calculate_std_dev(pointcloud)    threshold = mean + 2 * std_dev    clean_pointcloud = []    for point in pointcloud:        if distance(point, mean) < threshold:            clean_pointcloud.append(point)    return clean_pointcloudend function'

Lösung:

Ein wesentlicher Teil der Datenvorverarbeitung ist das Entfernen von Ausreißern. Betrachten wir die gegebene Punktwolke mit den Koordinatenpunkten \[ (1,2,3), (2,3,4), (100,200,300), (3,4,5), (4,5,6) \]

Hier ist ein mathematischer und programmatischer Ansatz, um den Ausreißer zu identifizieren und zu entfernen:

• Mathematischer Ansatz:
  • Berechne den Mittelwert (\text{mean}) der Punktwolke in jeder Dimension (x, y, z).
  • Berechne die Standardabweichung (\text{std\_dev}) der Punktwolke in jeder Dimension.
  • Setze für jede Dimension einen Schwellenwert (\text{threshold}) als: \(\text{threshold} = \text{mean} + 2 \times \text{std\_dev}\)
  • Ein Punkt wird als Ausreißer identifiziert, wenn seine Koordinate in einer oder mehreren Dimensionen diesen Schwellenwert überschreitet.
• Begründung: Diese Methode ist sinnvoll, da sie Punkte identifiziert, die weit außerhalb des erwarteten Bereichs liegen. Die meisten Datenpunkte liegen innerhalb von zwei Standardabweichungen vom Mittelwert, was bei einer normalen Verteilung etwa 95% der Daten abdeckt.

Hier ist der zugehörige Pseudocode:

'function remove_outliers(pointcloud):    mean_x = calculate_mean([p[0] for p in pointcloud])    mean_y = calculate_mean([p[1] for p in pointcloud])    mean_z = calculate_mean([p[2] for p in pointcloud])    std_dev_x = calculate_std_dev([p[0] for p in pointcloud])    std_dev_y = calculate_std_dev([p[1] for p in pointcloud])    std_dev_z = calculate_std_dev([p[2] for p in pointcloud])    threshold_x = mean_x + 2 * std_dev_x    threshold_y = mean_y + 2 * std_dev_y    threshold_z = mean_z + 2 * std_dev_z    clean_pointcloud = []    for point in pointcloud:        if (abs(point[0] - mean_x) < threshold_x) and            (abs(point[1] - mean_y) < threshold_y) and            (abs(point[2] - mean_z) < threshold_z):            clean_pointcloud.append(point)    return clean_pointcloudend function'

Nun beschreiben wir die Schritte im Detail:

1. Mittelwert berechnen: Der Mittelwert der Koordinatenpunkte wird in jeder Dimension (x, y, z) separat berechnet. Für die Punkte \[ (1,2,3), (2,3,4), (100,200,300), (3,4,5), (4,5,6) \] sind die Mittelwerte: \(\text{mean}_x = \frac{1+2+100+3+4}{5} = 22 \ \ \text{mean}_y = \frac{2+3+200+4+5}{5} = 42.8 \ \text{mean}_z = \frac{3+4+300+5+6}{5} = 63.6 \)
2. Standardabweichung berechnen: Die Standardabweichung wird in jeder Dimension (x, y, z) separat berechnet, um die Streuung der Punkte um den Mittelwert zu bestimmen.
3. Schwellenwert festlegen: Der Schwellenwert wird auf den Mittelwert plus das Zweifache der Standardabweichung gesetzt, um die Bereich der normalen Punkte abzudecken.
4. Ausreißer identifizieren und entfernen: Jeder Punkt wird überprüft. Wenn die absolute Differenz eines Punktes zum Mittelwert in jeder Dimension kleiner als der Schwellenwert ist, wird der Punkt zur bereinigten Punktwolke hinzugefügt. Andernfalls wird er entfernt.

Durch diese Methode wird der Ausreißer \((100,200,300)\) erkannt und entfernt, was zu einer qualitativ besseren Punktwolke führt.

Aufgabe 4)

Betrachte ein einfaches polygonales Netz, das aus 10 Knoten, 15 Kanten und 7 Flächen in einer topologisch geschlossenen Form besteht. Dies soll dazu verwendet werden, verschiedene Eigenschaften und Verarbeitungsschritte zu analysieren und anzuwenden.

Beachte dabei die zentrale Rolle der Euler-Charakteristik, die Datenstrukturen wie die Halbkantendatenstruktur und essentielle Operationen wie Simplifikation und Subdivision.

a)

Teilaufgabe 1: Verifiziere die Euler-Charakteristik dieses Netzes. Berechne den Geschlechtsparameter (genus) des Netzes anhand der gegebenen Anzahl an Knoten, Kanten und Flächen. Überprüfe anschließend, ob das Netz die Topologie einer 2D-Kugeloberfläche (also genus=0) oder eines Torus (also genus=1) hat.

Hinweis: Verwende die Formel der Euler-Charakteristik:

\[ V - E + F = 2(1 - g) \]

Lösung:

Um die Euler-Charakteristik des Netzes zu verifizieren und den Geschlechtsparameter (genus) zu berechnen, folgen wir diesen Schritten:

• Bestimme die Anzahl der Knoten (\textbf{V}), Kanten (\textbf{E}) und Flächen (\textbf{F}).
• Verwende die Formel der Euler-Charakteristik:

Die Formel der Euler-Charakteristik lautet:

\[ V - E + F = 2(1 - g) \]

Hierbei steht V für die Anzahl der Knoten, E für die Anzahl der Kanten, F für die Anzahl der Flächen und g für den Geschlechtsparameter.

• Schritt 1: Setzen wir die gegebenen Werte in die Formel ein:

Wir haben:

• \( V = 10 \) (Anzahl der Knoten),
• \( E = 15 \) (Anzahl der Kanten),
• \( F = 7 \) (Anzahl der Flächen)

Setzen wir diese in die Formel ein:

\[ 10 - 15 + 7 = 2(1 - g) \]

Berechnen wir die linke Seite der Gleichung:

\[ 10 - 15 + 7 = 2 \]

\[ 2 = 2(1 - g) \]

Teilen wir beide Seiten durch 2, um g zu finden:

\[ 1 = 1 - g \]

Subtrahieren wir 1 von beiden Seiten:

\[ 0 = -g \]

Das ergibt:

\[ g = 0 \]

• Schritt 2: Überprüfe, ob das Netz die Topologie einer 2D-Kugeloberfläche (genus = 0) oder eines Torus (genus = 1) hat:

Da der berechnete Geschlechtsparameter \( g = 0 \) ist, hat das Netz die Topologie einer 2D-Kugeloberfläche.

Somit haben wir die Euler-Charakteristik des Netzes verifiziert und den Geschlechtsparameter korrekt berechnet.

b)

Teilaufgabe 2: Beschreibe die Schritte der Loop Subdivision für das gegebene Netz. Zeichne die resultierenden Positionen der neuen Knoten und erläutere, wie die Halbkantendatenstruktur verwendet wird, um die Konnektivität zu wahren. Erläutere die Vorteile dieser Methode insbesondere im Bereich der Glättung von polygonalen Netzen.

Hinweis: Gehe dabei auf die Rolle der neuen Knoten und deren Gewichtung im Subdivision-Verfahren ein.

Lösung:

Loop Subdivision Methode für das gegebene Netz

Die Loop Subdivision Methode ist ein Verfahren zur Glättung und Verfeinerung polygonaler Netze. Dabei werden neue Knoten hinzugefügt und bestehende Knoten verschoben, um eine glattere Oberfläche zu erzeugen. Folgende Schritte beschreiben dieses Verfahren detailliert:

Schritte der Loop Subdivision:

• Schritt 1: Neue Knoten an Kanten erzeugen Für jede Kante im Netz wird ein neuer Knoten hinzugefügt. Die Position des neuen Knotens basiert auf den Positionen der beiden Endpunkte der Kante und der benachbarten Punkte, die ein Viereck um die Kante bilden.
• Schritt 2: Position der neuen Knoten berechnen Die Position eines neuen Knotens, der durch eine Kante zwischen den Punkten \(V_1\) und \(V_2\) sowie deren benachbarten Punkten \(V_3\) und \(V_4\) erzeugt wird, berechnet sich mit der Formel:

\[ V' = \, \frac{3}{8} \, (V_1 + V_2) \, + \, \frac{1}{8} \, (V_3 + V_4) \]

• Schritt 3: Bestehende Knoten anpassen Die Position der bestehenden Knoten wird aktualisiert, indem ein Gewichtungsparameter verwendet wird. Die Formel lautet:

• \[ V'_i = (1 - n \cdot \beta_n) \, V_i \, + \, \beta_n \sum V_j \]

  wobei \(n\) die Anzahl der benachbarten Knoten ist und \(\beta_n\) typischerweise \(\beta_n = \frac{3}{8n}\) beträgt.

• Schritt 4: Netz neu triangulieren Nach dem Einfügen der neuen Knoten und der Anpassung der bestehenden Knoten wird das Netz neu trianguliert, um die ursprüngliche Struktur zu erhalten.

Verwendung der Halbkantendatenstruktur

Die Halbkantendatenstruktur ist entscheidend, um die Konnektivität im Netz während der Loop Subdivision beizubehalten. Sie ermöglicht eine effiziente Verwaltung von Kanten- und Knotenverbindungen und erleichtert so das Auffinden benachbarter Knoten und Kanten.

Vorteile der Halbkantendatenstruktur:

• Konnektivität: Detaillierte und effiziente Verwaltung der Beziehungen zwischen Knoten und Kanten.
• Lokalität: Erleichtert das Auffinden und Berechnen benachbarter Knoten, was für die Gewichtung und Positionierung wichtig ist.
• Einfachheit: Unterstützt die Implementierung des Subdivision-Verfahrens durch Strukturierung der Netzdaten.

Vorteile der Loop Subdivision Methode

• Die Loop Subdivision erzeugt glattere und feinere Oberflächen, die visuell ansprechender sind.
• Die Methode erhält die Grundtopologie des Netzes, sodass keine drastischen Veränderungen an der Struktur erfolgen.
• Das Verfahren ist relativ einfach zu implementieren und bietet dennoch hohe Effizienz und Genauigkeit im Ergebnis.

Zusammenfassung

Die Loop Subdivision Methode ist ein wirkungsvolles Verfahren zur Glättung von polygonalen Netzen. Durch Hinzufügen neuer Knoten und Anpassen vorhandener Knotenpositionen bietet sie eine hochgradig glatte und ästhetisch ansprechende Netzoberfläche. Die Halbkantendatenstruktur spielt dabei eine zentrale Rolle, um die Konnektivität zu wahren und die Subdivision effizient zu implementieren.