Kolloquiumszyklus - previous dates

Multilevel representations and mesh reduction techniques have been used for accelerating the processing and the rendering of large datasets representing scalar or vector valued functions defined on complex 2 or 3 dimensional meshes. We present a method based on finite elements and hierarchical bases which combines these two approaches in a new and unique way that is conceptually simple and theoretically sound. Starting with a very coarse triangulation of the functional domain a hierarchy of highly non-uniform tetrahedral (or triangular in 2D) meshes is generated adaptively by local refinement. This process is driven by controlling the local error of the piecewise linear finite element approximation of the function (in the least-squares sense) on each mesh element. Flexibility in choosing the underlying error norm allows for gradient information to be included. A reliable and efficient a posteriori estimate of the global approximation error combined with a preconditioned conjugate gradient solver are the key components of the implementation. Many areas where the proposed method can by applied successfully are envisioned, such as mesh reduction of parameterized grids, visualization of scalar and vector volume data, physically based computer animation of extended bodies and global illumination algorithms. The example application we implemented in order to analyze the properties and advantages of the generated tetrahedral mesh is an iso-surface algorithm which combines the so far separated tasks of extraction acceleration and polygonal decimation in one single processing step. The quality of the iso-surface is measured based on a special geometric norm which does not require the full resolution surface.

Virtual engineering refers to various scenarios where several independent companies or partners must perform product development or production engineering tasks in co-operation - that is, engineering in a virtual enterprise. Common examples of virtual engineering include the producer-supplier scenario, where product and its subcontractor-made components must be designed simultaneously, the mass customization scenario, where a customized product is composed from basic modules and components from several companies, and the multi-supplier project scenario, where several manufacturers contribute to the engineering and construction of a large design such as an industrial plant. Similarly to the related concept "concurrent engineering", virtual engineering must support the inclusion of all life-cycle issues of a product during its design. However, virtual engineering recognises explicitly the fundamental differences between the life-cycle viewpoints to a product, and aims at solutions that can work also on the basis of distributed heterogeneous information and systems. The term is also intended to cover activities denoted by related expressions "virtual prototyping" and "virtual manufacturing". From the viewpoint of information technology, the research challenge of virtual engineering is to identify and develop computational tools that support co-operation, information sharing, and coordination of activities for engineering teams in a virtual organization. These tools must be capable of operating in a distributed, heterogeneous environment where direct data sharing by means of jointly used data repositories or like is impossible or impractical. Further challenges are posed by the potentially large volume of shared data and the ill-structuredness of some of the necessary information. In the presentation, I will first analyse the basic requirements that computational tools for virtual engineering should satisfy. Next, industrial requirements of virtual engineering are discussed on the basis of studying the business processes that underlie and delienate virtual engineering activities. Finally, three application case studies of virtual engineering are briefly discussed to study the suitability of the above techniques. They are

• Design Process and Rationale Capture and Deployment, where the focus is on sharing product information across design teams during novel design
• Computational Infrastructure for Life-Cycle Assessment, where the focus is on sharing and reusing product information across different engineering applications (including legacy systems) and company borders during variant design
• Virtual Engineering and Construction of Multi-Supplier Projects, the focus of which is on sharing engineering process information to coordinate the activities of cooperating companies and on using the shared models to study and visualise the process.

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.