Kolloquiumszyklus - previous dates

Fortgeschrittene Anwendungsszenarien, wie z. B. die Simulation chirurgischer Eingriffe, erfordern computergestuetzte Modelle, welche ueber die in der Graphischen Datenverarbeitung ueblicherweise eingesetzten geometrischen Ansaetze hinausgehen. Insbesondere ist es notwendig, Oberflaechen und Volumina des Weichteilgewebes phsikalische Eigenschaften zuzuordnen. Zur Loesung der daraus resultierenden Funktionale kann die Methode der finiten Elemente gewinnbringend eingesetzt werden.

Der folgende Vortrag vermittelt einen Einblick in die Vielschichtigkeit der Problemstellungen bei der Konstruktion von Simulatoren fuer die Gesichtschirurgie. Dazu werden zunaechst Verfahren zur Datenaufbereitung und Geometrie-Extraktion diskutiert, welche auf CT Volumendaten des Patienten operieren. Darauf aufbauend koennen Oberflaechen stueckweise durch global C1 stetige Finite Elemente Funktionen definiert und berechnet werden. Innerhalb des Volumens genuegen Elemente mit geringeren Stetigkeitsanforderungen. Auf Basis der vorliegenden Beschreibungen koennen interaktiv Eingriffe, wie z. B. Repositionierungen des Knochens, vorgenommen und dem physikalischen Modell zugefuehrt werden. Die resultierende Gesichtsform errechnet sich durch Loesung eines Variationsfunktionals im Raum der finiten Elemente. Im Zuge einer Fallstudie illustrieren simulierte Eingriffe basierend auf dem Visible Human Datensatz die Anwendbarkeit des vorgestellten Prototypen.

Entgegen der Monte Carlo Methode, bei der Integrale durch zufaellige Entscheidungen geschaetzt werden, erlaubt die deterministische Wahl von Abtastpunkten schnellere Konvergenzraten als die Monte Carlo-Methode. Niederdiskrepanzfolgen sind solche deterministische Stuetzstellen, die speziell fuer Zwecke der Optimierung und Integration entwickelt wurden. Im Vortrag werden neue, schnelle Algorithmen, die auf der Quasi-Monte Carlo Integration mittels Niederdiskrepanzfolgen beruhen, fuer spezielle Probleme der Computergraphik vorgestellt.

Parallel implementation of sequential algorithms not only brings changes into the structure of programs, but also forces programmers to move their interest towards specific hardware platforms. Already known "best sequential" algorithms have to be sometimes changed so that their efficiency is reduced by additional overhead needed for synchronization and communication among processes. Unfortunately the ray-tracing algorithm is very time consuming and the cost of the computation of different parts of the images is not the same. There have been some approaches developed in the last years as space subdivision and image subdivision. Naturally they have some advantages and disadvantages and therefore the researches have tried to go further and decrease the shortcomings of parallel solutions. In this lecture the traditional approaches with their results will be outlined. Then the lecture will be devoted to the reasearch performed recently on ray-tracing of large scenes using data prefetching. The results achieved in our research team in Prague will be presented as well.

Constraints have been used from the early 60's and now they are a common feature of todays professional graphics modeling systems. Constraints define the relations between objects which have to be satisfied. With the growing speed of computer hardware, new algorithms for solving sets of constrains are developed, especially for geometric constraints. There have been developed some new approaches during the last years which nearly reach interactive speed. Faster algorithms for solving the CSP (Constraint solution problem) use additional information obtained by analyzing properties of the used constraints or by analyzing the graph structure of the CSP. Traditional approaches will be outlined in the lecture. Then we will talk about our new algorithm for solving constraints - the minimal change method. The lecture will cover some ideas to speed up the solving process using the analyzed graph of the CSP.

Bei der Implementierung von (semi-)numerischen Algorithmen hat man zu beachten, dass durch die endliche Rechengenauigkeit beliebig falsche Resultate entstehen koennen, selbst wenn die Input-Daten im verwendeten Maschinenzahlen-Raster exakt darstellbar sind. Auch das Erkennen und korrekte Behandeln von Sonderfaellen (degenerate input data), in letzter Zeit gerade fuer geometrsiche Algorithmen im Mittelpunkt des Interesses, gestalten sich schwierig.

Um korrekte Aussagen bzw. Werte zu erhalten, koennen verschiedene Methoden Anwendung finden: Verwendung einer exakten Integer-Arithmetik, symbolisches Rechnen, die von Edelsbrunner/Muecke vorgeschlagene Technik "Simulation of Simplicity" oder Rechnen mit Einschliessungsmengen. Diese oder andere Verfahren, die auch hybrid eingesetzt werden, arbeiten selbst nur unter gewissen Voraussetzungen teilweise oder durchgaengig erfolgreich, was ihre Bedeutung jedoch nicht schmaelert.

Im Vortrag wird eine weitere Methode vorgeschlagen, die an das Rechnen mit Einschliessungsmengen anschliesst, um Algorithmen, die unter Verwendug einer exakten Zahlendarstellung, Arithmetik und Auswertung von Standardfunktionen korrekte Resultate liefern wuerden, durch Transformationen zu implementieren. Die Transformationen haben als Grundbausteine Regeln zu Umwandlung von Ergibtanweisungen, Sequenzen, if-then-else-Anweisungen und while-Schleifen und setzen sich induktiv aus diesen zusammen. Wenn der transformierte Algorithmus Werte liefert, so sind dies garantierte Einschliessungen der gesuchten exakten. Bricht er waehrend seiner Laufzeit unterwegs ab, so kann er mitteilen, warum dies so ist. An Beispielen wird die Praktikabilitaet demonstriert.

In der Computergraphik wird von einer Modellierung der Szene ausgegangen und Bilder dieser Szene werden errechnet. Im Bildverstehen ist die Vorgangsweise dazu genau invers: (reale) Bilder sind die Eingabedaten fuer nachfolgende Prozessketten, das Ergebnis ist eine Beschreibung der aufgenommenen Szene. Diese Dualitaet zwischen "maschinellem Sehen" und "maschinellem Darstellen" aus der Sicht des Bildverstehens steht im Zentrum des Vortrages. In vielen Systemen kann der Kreis heute immer enger geschlossen werden, etwa wenn zum Testen von Bildanalyse-Algorithmen mit Hilfe von Computergraphik simulierte Bilder benutzt werden, oder in augmented reality Systemen, wo Bildanalyse zum positionsgenauen Verfolgen von bewegten Objekten benutzt wird. Der Vortrag wird reich illustriert durch aktuelle Arbeiten des Grazer Institutes aus den Bereichen Computergraphik, Objektrekonstruktion und Computer Vision.