Studentische Arbeiten

Diese Seminararbeit beschäftigt sich mit den Grundlagen der Fluid-Simulation. Zunächst wird die Navier-Stokes Gleichung hergeleitet und darauf aufbauend werden verschiedene Lösungsansätze diskutierter mit dem Fokus auf dem Marker and Cell (MAC) Ansatz, der zwei versetze Gitter für die Drücke und Geschwindigkeiten im Fluid verwendet. Mittels finiter Differenzen wird dann eine Diskretisierung beschrieben die effizient das Fluid simulieren kann und dabei über einen Projektionsmechanismus die Inkompressibilität der Flüssigkeit gewährt.

The gradient of a scalar function is a well-known tool of vector analysis and routinely used to analyze images or results of simulations or to enhance volume visualization. In these applications, the gradient is usually not known but has to be approximated from the values of the function which are commonly given on a discrete set of points in some space. If these points lie on a regular, orthogonal grid, approximation of the gradient can be easily done using divided differences. In the case of non-orthogonal meshes, this is not as simple. In this seminar, several methods will be presented which can overcome this problem.

 Volume raycasting without (left) and with (right) gradient hinting.

• The work in PDF format

The computation of geodesic paths and distances on triangle meshes is a common operation in many computer graphics applications. I will present several practical  algorithms for computing such geodesics from a source point to one or all other points efficiently. First, I will describe an implementation of the exact “single source,  all destination” algorithm presented by Mitchell, Mount, and Papadimitriou (MMP). I will show that the algorithm runs much faster in practice than suggested by worst case analysis. I will also show an algorithm (by V. And T. Surazhsky, D. Kirsanov, Steven J. Gortler and H. Hoppe) extended with a merging operation to obtain computationally efficient and accurate approximations with bounded error. Finally, to compute the shortest path between two given points, I will show how the authors used a lower-bound property of their approximate geodesic algorithm to efficiently prune the frontier of the MMP algorithm,  thereby obtaining an exact solution even more quickly.

Eine typische Aufgabe im Bereich Computer Vision besteht darin,
bestimmte Objekte und Objektteile in einem Bild zu erkennen
und zu jedem Objekt die Position und Orientierung relativ zu
einem Koordinatensystem zu bestimmen. Dieser Prozess wird als
Poseschätzung (engl. pose estimation) bezeichnet.

Die dabei benötigten Berechnungen lassen sich in den Rahmen der sog.
Geometrischen Algebra einbetten. Diese basiert auf der mathematischen
Theorie der Clifford Algebren und definiert Operationen, die es u.a.
ermöglichen, direkt mit Teilräumen eines Vektorraums zu rechnen.
Die Geometrische Algebra erweitert die Lineare Algebra, die traditionell
in der Computergraphik und Robotik eingesetzt wird und integriert dabei
andere dort angewandte Konzepte wie z.B. komplexe Zahlen,
Quaternionen und Plücker-Koordinaten.

Marc Christoph Vollmer hält einen Kurzvortrag zum Beginn seiner Masterarbeit mit dem Titel "Entwurf und Implementation einer haptischen Schnittstelle für YaDiV" Im Rahmen dieser Arbeit werden Methoden zur effektiven und stabilen Integration eines haptischen Eingabegeräts in das Programm YaDiv untersucht. Hinsichtlich der bisher zur Verfügung stehenden Eingabegeräte werden Mechanismen zur taktilen Wahrnehmung nicht behandelt. Diese Arbeit beschränkt ausschließlich auf die kinästhetische Wahrnehmung.

Mit der hier entwickelten haptischen Schnittstelle soll dem Benutzer die Möglichkeit gegeben werden, unter Verwendung eines entsprechenden Eingabegeräts, effektiver und realistischer im dreidimensionalen VR-Raum zu navigieren als es bisher mit einer zweidimensionalen Maus möglich ist. Neben dem haptischen Eingabegeräten wird auch die Erstellung eines Prototypen zur Benutzung eines Datenhandschuhs Bestandteil sein.

The rendering of realistic scenes in real time is an important goal of computer graphics. For a scene to appear realistic, the shadowing of the scene has to seem correct. There are several techniques to render real time shadows and Shadow Mapping is one of the most prominent of those. Many extensions of this technique have been developed to increase the quality of the resulting Shadows. This talk will give an overview of one of these extensions, the Convolution Shadow Mapping, which allows for better filtering of the shadows and thus increasing the image quality.

In computer graphics and especially in virtual reality it is not only important to represent rigid objects, but also to simulate deformable materials.  Curves, surfaces, or solids should deform according to interaction with other objects and react in a natural way.  A wide variety of techniques have been developed for modeling and animation of deformable objects.  One possible approach is to model the underlying physics by solving differential equations that balance externally applied forces with the object’s inertial mass as well as the damping force and an elastic force resulting from deformation.  The computation of the required deformation energy is derived from differential geometry and can be simplified for real-time simulation.  In this work the elastically deformable models are distinguished from other techniques and the basic equations and computations are described.

Segmentation is a problem in many areas of research and application. Therefore many different approaches exist to find regions of interest in images. A widely used approach employs so-called "Atlases" to which the image of interest is mapped. This seminar will give an overview of the technique and describe a general non-rigid registration technique and similarity measure which are used to find the mapping between atlas and image.

A family of discrete isometric bending models (IBMs) for triangulated surfaces in 3-space will be presented. It will be shown that these linear models for discrete mean curvature from which bending energies are assembled are very efficient. Under the assumption of isometric surface deformations it is also shown the formulated energies are quadratic in surface positions. The corresponding linear energy gradients and constant energy Hessians constitute an efficient model for computing bending forces and their derivatives, enabling fast time-integration of cloth dynamics with a two- to three-fold net speedup over existing nonlinear methods.

In diesem Vortrag wird ein Überblick über die Forschung im Bereich der "Angewandten Geometrie und Visualisierung" am MATHEON gegeben und über die Aktivitäten der Berlin Mathematical School (BMS) berichtet. Der Vortrag wird ausgewählte Themen aus dem Schwerpunkt "Visualisierung" des MATHEON vorstellen und das innovative Wechselspiel zwischen mathematischer Theorie und industrieller Praxis analysieren. Hierzu gehören Fallbeispiele aus der Diskreten Differentialgeometrie, der Mathematischen Visualisierung, der medizinischen Bildverarbeitung, dem CAD/CAM und Algorithmen für die Filmindustrie in Hollywood. Das DFG Forschungszentrum MATHEON entwickelt angewandte Mathematik für Schlüsseltechnologien. Die BMS ist eine Graduiertenschule, die im Rahmen der Exzellenzinitiative des Bundes gefördert wird. Beide Einrichtungen werden von den drei Berliner Universitäten (FU, HU und TU) zusammen mit dem Weierstrass- und Zuse Institut gemeinsam getragen.

• Homepage von Prof. Polthier
• Homepage von MATHEON
• Homepage der Berlin Mathematical School

Das Modellieren und die physikalische Simulation von Frisuren in virtuellen Umgebungen ist ein Themengebiet, das häufig in seiner Relevanz und Schwierigkeit unterschätzt wird. Dabei finden u.a. in der Film- oder Computerspieleindustrie viele unterschiedliche Verfahren Anwendung, die jeweils anderen Kriterien und Einschränkungen genügen müssen. In diesem Seminarvortrag soll ein Überblick über die Klassen von gebräuchlichen Algorithmen geboten werden, wobei eines dieser Verfahren genauer vorgestellt wird.

The Medial Axis is an important geometric concept related to the Voronoi
diagram and other distance-sets. Even though its definition is easily
stated and intuitive, the computation of the Medial Axis for non-trivial
sets is difficult and time-consuming. The computation of the Voronoi
diagram in contrast is well understood and there exist stable
algorithms. This is the first of two talks presenting the approximation
of the Medial Axis from the Voronoi diagram.

The Medial Axis is an important geometric concept related to the Voronoi
diagram and other distance-sets. Even though its definition is easily
stated and intuitive, the computation of the Medial Axis for non-trivial
sets is difficult and time-consuming. The computation of the Voronoi
diagram in contrast is well understood and there exist stable
algorithms. This is the first of two talks presenting the approximation
of the Medial Axis from the Voronoi diagram.

Traditionally, research on computer graphics is centered around the quest for visual realism. But looking at even older techniques of illustration one notices that there is a need for non-photorealistic drawings, for example in the area of medical imaging and for educational purposes. Here an image should display the relevant features of an object rather than rendering it photorealistically. We present a method to (semi-)automatically generate such representations from a given polygonal model of the object. The technique is based on calculating lines of intersection along a skeleton of the object model.

In the last twenty years many approaches for contact-free measurement techniques for object surfaces and approaches for 3d object reconstruction have been proposed; but often they still require complex and expensive equipment. Not least due to the rapidly increasing number of efficient 3d hard- and software system components, alternative low-cost solutions are in great demand. We propose such a low-cost system for 3d data acquisition and fast pairwise surface registration. The only hardware requirements are a simple commercial hand-held laser and a standard grayscale camera.

Voronoi-Diagramme finden seit ihrer Einführung durch Georgi Voronoi 1905 in sehr vielen Bereichen der Wissenschaft, wie Biologie, Medizin und natürlich auch Mathematik und Informatik verschiedenste Anwendungen. Sie liefern auf natürliche Weise eine Partitionierung des umgebenden Raums in Bezug auf den Abstand zu gegebenen Referenzobjekten (meistens Punkte).

In dieser Arbeit werden Voronoi-Diagramme in dreidimensionalen metrischen Räumen berechnet. Der Abstandsbegriff wird hier durch das Konzept der Metrik verallgemeinert. Dabei wird die gegebene Metrik durch den Abstandsbegriff auf einer im vierdimensionalen eingebetteten dreidimensionalen Höhenfläche induziert. Schwerpunkt der Arbeit ist die Entwicklung eines Verfahrens zur Berechnung von geodätischen Voronoi-Diagrammen, das ohne Verschneidungsalgorithmen auskommt. Dies wird durch ein Perturbationsverfahren erreicht, das die Berechnung der Knoten, d.h. der Punkte des Voronoi-Diagramms, zu denen mindestens vier Referenzpunkte gleichen Abstand haben, ermöglicht. Dabei wird eine homotope Deformation der euklidischen Metrik hin zur gegebenen Metrik durchgeführt.

Spherical Harmonic lighting (SH lighting) is a technique for calculating the lighting on 3D models from area light sources that allows us to capture, relight and display global illumination style images in real time. The talk gives an overview of this technique starting from the definition of global illumination to the interreflectance between objects.

Resampling raw surface meshes is one of the most fundamental operations used by nearly all digital geometry processing systems. The vast majority of this work has focused on triangular remeshing, yet quadrilateral meshes are preferred for many surface PDE problems, especially fluid dynamics, and are best suited for defining Catmull-Clark subdivision surfaces. We describe a fundamentally new approach to the quadrangulation of manifold polygon meshes using Laplacian eigenfunctions, the natural harmonics of the surface. These surface functions distribute their extrema evenly across a mesh, which connect via gradient flow into a quadrangular base mesh. An iterative relaxation algorithm simultaneously refines this initial complex to produce a globally smooth parameterization of the surface.  From this, we can construct a well-shaped quadrilateral mesh with very few extraordinary vertices.The quality of this mesh relies on the initial choice of eigenfunction, for which we describe algorithms and heuristics to efficiently and effectively select the harmonic most appropriate for the intended application.

Volumenvisualisierung basiert darauf zwei verwandte Integralgleichungen zu lösen, eine Radon-Transformation und eine inverse Radon-Transformation. Dies ist sehr rechenaufwendig und kann durch hardware-implementiertes Texture-Mapping beschleunigt werden. Literatur:

• Brian Cabral, Nancy Cam, and Jim Foran. Accelerated volume rendering and tomographic reconstruction using texture mapping hardware. In VolVis '94, pages 91--98. ACM Press, 1994.

Die Shear-Warp Transformation beschreibt eine sehr schnelle Faktorisierung der Sichttransformation verbunden mit einer scanline-basierten Abtastung des Volumens. Dieses Verfahren ist eine sehr schnelle und genaue Möglichkeit, Volumina ohne Hardwareunterstützung zu visualisieren. Literatur:

• Lacroute, P., and Levoy, M. Fast Volume Rendering Using a Shear-Warp Factorization of the Viewing Transformation. Proc. SIGGRAPH. ACM, Orlando, FL, 1994, pp. 451-458.

Shape from Shading (SFS) deals with the recovery of shape from a gradual variation of shading in an image. This is particularly important in applications where direct surface measurements are not possible. The basic problems of SFS and three different approaches for a solution are presented in the seminar.

Den kürzesten Weg zwischen zwei Punkten auf einer vollständigen Fläche im dreidimensionalen Raum zu finden ist allein deswegen schon so schwierig, weil dieser Weg unter Umständen nicht eindeutig ist. Beispiele dafür lassen sich sehr leicht mit gewissen Symmetriebedingungen erzeugen. Das in der Studienarbeit erzeugte Verfahren zur Berechnung eines solchen kürzesten Weges beruht auf der Berechnung der lokalen medialen Achse der zwei Punkte auf der Fläche. Man kann zeigen, dass der kürzeste Weg diese Mediale Achse in einem gewissen Punkt senkrecht schneidet. Solche Punkte muss man demnach suchen. Bei der Suche muss man die geodätischen Differentialgleichungen sowie die Jacobi-Gleichungen beachten, um zum Ziel zu kommen.

Cloth modeling has been an important topic studied by computer graphics people since the mid of 1980s. Beside the visual pleasantness of a fabric, the hand or feel of the fabric plays an important role in the perception of a fabric.

Roughness and friction are important parameters for the haptic simulation of fabrics. In this talk a DFFT based correlation-restoration method to model the surface roughness and friction coefficient of a given fabric is described.

Im Rahmen eines Projektes soll die Integration haptischer Wahrnehmungen in eine bestehende VR-Umgebung untersucht werden. Die Zielvorstellung umfaßt die Erzeugung von Signalen für ein Gerät zur Simulation haptischer Eindrücke auf Basis eines Grauwertbildes zu einem gegebenen Material. Das Ziel dieser Diplomarbeit war die Klassifikation symmetrischer Anteile als wesentliches Charakteristikum von Materialien anhand eines Grauwertbildes. Den zentralen Aspekt bildete dabei der Entwurf und die Entwicklung von Methoden und Verfahren zur Differenzierung symmetrischer Anteile.

Bei der Konstruktion industrieller Bauteile, z. B. im Fahrzeugbau, entwerfen die Ingenieure geometrische Objekte mit CAD-Systemen, indem sie diese durch eine Vielzahl von Freiformflächen beschreiben.

Diese Geometriedaten sind in der Praxis oft ungeeignet für eine weitere Verarbeitung. Sie enthalten Löcher, überlappungen und Degenerierungen. Weiterhin sind die Zusammenhangseigenschaften nicht bekannt. Das Problem besteht nun darin, eine geeignetere Darstellung des Objektes zu finden, in der die genannten Probleme korrigiert sind. In der Diplomarbeit wird nun ein Verfahren entworfen, das durch eine Projektionsmethode die Objektgeometrie erfaßt und das Objekt durch nur wenige Flächen mit bekannten Zusammenhangseigenschaften beschreibt.

Bevor die Serienproduktion von Fahrzeugen beginnt, müssen die einzelnen Bauteile eines Fahrzeugs eine Qualitätskontrolle durchlaufen. Jedes Bauteil muß dafür vorgegebenen Fehlertoleranzen genügen. Darüber hinaus muß das Zusammenspiel der Einzelteile beurteilt werden, da sonst Fehler in Fugen- und Kantenverläufen nicht erkannt werden können. Ein Meisterbock ist ein Gerüst, an dem die in der Vorserienproduktion entstandenen Bauteile zu einem Prototyp zusammengebaut werden. Anhand des Meisterbocks können dann Fehler der Produktion im Vergleich zu den CAD-Solldaten gefunden und behoben werden.Der Aufbau eines Meisterbocks nimmt 2-6 Wochen in Anspruch und muß oft wiederholt werden bevor die Serienproduktion begonnen werden kann. Ziel dieser Arbeit ist, einen virtuellen Meisterbock zu erstellen. Der virtuelle Meisterbock soll Iterationen des realen Meisterbocks einsparen, indem Fehler in der Produktion in einem VR-System sichtbar gemacht werden. Der virtuelle Meisterbock wird ausgehend von den CAD-Solldaten unter Berücksichtigung von Meßdaten des produzierten Bauteils erzeugt.

Janus ist ein Visualisierungs und Modellier-System, dass am Lehrstuhl Graphische Datenverarbeitung der Universität Hannover entwickelt wurde.