NOTIZEN ZU DEN VORTRÄGEN IM SEMINAR "Algorithmenanimation"

Dr. Stephan Diehl, Sommer 1998

• erste Algorithmenanimation: Video "Sorting Out Sorting" bei SIGGRAPH'81

Aus Betrachtung der XTango-Animationen:

Grafische Primitive: Kanten, Knoten, Boxen, Text
• Gibt es grafische Operationen auf hoeherem Abstraktionsniveau --> ja, fertige Views
• Granularitaet: Zustandsfolgen --> Uebergangsanimationen

ZEUS

• Programmtext (Code View)
• Interesting Events, Annotation von Programmpunkten
• Algorithmus ist First-Class-Citizen, aber sein Programmtext ist nicht zugreifbar, manipulierbar.
• Eventhandling und STEP, TRACE verzahnt
• Views
  Teilen sich Views und Algorithmus den gleichen Zustand, oder muss die View eine (Teil-)Kopie des Zustands selbst verwalten?
• Farbe, Sound

Warum 3D?

• Aesthetik (Menschen sind drei Dimensionen gewohnt)
• Datenstrukturen sind 3D, oder Algorithmus, e.g. Brown'sche Molekularbewegung
• 3D erlaubt zusaetzliche Information zu kodieren

POLKA-3D

• Views-Szenen-(AnimObject, Loc, ???) Analogie zum Theater: Buehne, Akt, Buehnenbild + Akteure
• Beispiele:
  kuerzeste Wege Z-Ache zeigt Kosten,
  kuerzester Weg, aufsteigender Pfad mit niedrigster Hoehe
  shortest pair: Z-Achse zeigt Rekursionstiefe
  Heapsort: Z-Achse=Wert, Invariante (Heapeigenschaft) = entlang jeden Pfades nimmt der Wert von unten nach oben zu
  K-Suchbaum: Z-Achse = Tiefe im Baum
  (2,4) Baeume: Z-Achse (Wolken) zeigen Zuordnung von einer Datenstruktur ( 2,4-Baum) auf andere (Rot/Schwarz-Baum)
• Animation: diskrete Zeitachse, an Zeitpunkte werden (Objekte,Aktion)-Paare gebunden (--> trace)

SAMBA

• Kommandozeilen
• parallele Berechnungen { }
• plattformunabhaengig

JCAT / CAT

• View wie bei Zeus = Fenster + Logik, gekoppelt ueber interesting events IE
• Views verteilt auf mehrere Rechner mit eigener interaktiver Kontrolle
• Lehrer-View / Lerner-View
• JCAT -> Java -> plattformunabhaengig
• IEs werden als Java-Schnittstelle spezifiziert
  Generator --> abstrakte Klassen -- Benutzer programmiert --> Klassen
• JCAT erlaubt im Gegensatz zu CAT nicht Selektion von Views durch Lerner.

GASP (geometrische Algorithmen)

• schreibe Algorithmus mit Operationen und Datenstrukturen des Systems --> Animation erhaelt man umsonst
• Animation = Folge von Zustaenden und weichen (smooth) Uebergaengen
• jedoch: Abbildung von geometrischen Datenstrukturen auf grafische Visualisierungen einfach
• Erzeugen von Videofilmen (MPEG)

FORMS3

• Visual-Programming Language mit Oneway-Constraints
• Spreadsheet-Paradigma (Zellen mit Formeln)
• deklarativ, responsiv
• Path-Transition Paradigma, aber gesteuert durch Reset-Event und Continue-Event Zellen Transition wird nicht aufgerufen, sondern durch diese Events an- und ausgeschaltet
• Neu: Animation wird durch zusaetzliche Constraints ohne Veraenderung des Algorithmus programmiert (tatsaechlich nur teilweise in FORMS3 erreicht, in Algorithmus zusaetzlicher Synchronisationscode enthalten "counter mod 11")

JELIOT

• Programmanimation statt Algorithmenanimation
• naeher am Programmcode, weniger abstrakt
• Programmcode wird in Webseite eingetragen, Animationsapplet auf Server erzeugt durch einfuegen selbstanimierende Datentypen und Aufruf ihrer Methoden
• Vergleich zu Interesting Events: Transformation statt Annotation

Evaluierung:

• Bisher keine klaren Ergebnisse
• Studien zu klein, Methoden fragwuerdig

Konzeptionelle Fragen:

• Wie verdeutlicht man Invarianten? Bei 3D-Heapsort sieht man Heap-Eigenschaft, entlang jeden Pfades werden die Saeulen groesser.
• Wie setzt man Fokus?
• Wie stellt man Rekursion dar? (z.B. durch Sound, Tonhoehe)
• Was soll ein System leisten? Leicht bedienbar, ueberschaubar, maechtig?
• Wie werden Algorithmus und Animation getrennt/gekoppelt?

Geschichte:

• Georgia Institute of Technologie: Stasko
  Xtango/Tango (1990)
  Polka + Samba(frontend)
  Polka3d (1992)
  
• MIT spaeter DEC SRC: Brown (und Najork)
  Balsa (1985), Balsa II (1988)
  Zeus (1992)
  Anim3D, Zeus3D (1993)
  CAT (WWW) (1996)
  JCAT (1997)
  
• Princeton: Dobkin und Tal
  GASP (ca. 1994) speziell fuer geometrische Algorithmen