Laboraufgabe 3

Aufgabe 3: Subdivision Surfaces

Schreiben Sie ein Programm mit grafischer Ausgabe und einem interaktiv zu betätigenden Schiebegregler, das Subdivision Surfaces nach Doo-Sabin demonstriert. Das Programm zeichnet auf dem Bildschirm folgende Figuren als parallel projizierte Drahtgitter: einen Würfel, darunter den Würfel nach einmaliger Anwendung der Unterteilung, darunter den Würfel nach zweimaliger Anwendung der Unterteilung. Der Schieberegler verändert eine Koordinate eines Eckpunkts des Würfels. Die beiden anderen, durch Unterteilung entstehenden Figuren passen sich an.

Gehen Sie so vor:

Legen Sie eine Klassenstruktur an, die aus Polygonen gebildete Körper als einfache Boundary Representation speichert:

Körper = Liste von Polygonen
Polygon = Liste von Nummern von Kanten
Kante = Paar von Nummern von Punkten

Obendrein brauchen Sie eine Liste, in der Koordinaten der Punkte stehen. Zur Beschleunigung können Sie vorsehen, dass Kanten zusätzlich speichern, in welchen Polygonen sie vorkommen, und dass Punkte zusätzlich speichern, in welchen Kanten sie vorkommen.

Schreiben Sie eine Funktion, die eine solche Struktur nach Doo-Sabin unterteilt und als Ausgabe wieder eine solche Struktur erzeugt.

Beispiele für funktionale Ergänzungen, um vier Punkte für das Programm zu erreichen:

Stellen Sie im Drahtgitter nur die Vorderseiten dar ("hidden line"); Rechnung vgl. "backface culling" bei gefüllten Flächen.
Sehen Sie eine Importfunktion vor, die z.B. raw-Dateien von 3D-Modellierungsprogrammen einliest (nur Vierecke!).

Nachtrag: Beispiel einer Möglichkeit, den Algorithmus auszulegen

// siehe getrennte Bilddatei.

// Schritt A

Für alle Kanten tue:
Bestimme den mittleren Punkt k der Kante.

Für alle Polygone des ursprünglichen Körpers tue:
    Bestimme den Mittelwert m (ein 3D-Vektor) aller Eckpunkte des jeweiligen Polygons.
    Für alle Eckpunkte des jeweiligen Polygons tue:
        Berechne den Mittelwert aus dem jeweiligen Eckpunkt, aus m und den mittleren Punkten k der beiden Kanten, die in ihm zusammenstoßen.
        Merke dir diesen 3D-Vektor als Partner des jeweiligen alten Eckpunkts.

// Diese soeben berechneten 3D-Vektoren sind die Eckpunkte des neuen, verfeinerten Körpers.
// Jetzt müssen wir die zu Polygonen verbinden. Dabei entstehen meist Vierecke, aber nicht ausschließlich!

// Schritt B

Für alle Polygone des ursprünglichen Körpers tue:
Verbinde die für dieses Polygon abgespeicherten neuen Punkte zu einem Polygon des verfeinerten Körpers.

// Schritt C

Für alle Kanten des ursprünglichen Körpers tue:
Verbinde die vier neu berechneten Punkte, die Nachbarn dieser Kante sind, zu einem Polygon des verfeinerten Körpers (immer ein Viereck).

// Schritt D

Für alle Eckpunkte des ursprünglichen Körpers tue:
Verbinde die neu berechneten Punkte, die Nachbarn dieses Eckpunkts sind, zu einem Polygon des verfeinerten Körpers.

// Die Datenstrukturen, die speichern, welche Fläche des neuen Körpers an eine bestimmte Kante des neuen Körpers grenzt etc., müssen dabei ebenfalls aufgebaut werden. Jede Kante darf weiterhin nur einmal in der Datenstruktur stehen.