Kolloquiumszyklus - previous dates

Visibility problems are central to many computer graphics applications. The most common examples include hidden-part removal for view computation, shadow boundaries, mutual visibility of pairs of points, etc. In this document, we first present a theoretical study of 3D visibility properties in the space of light rays. We group rays that see the same object; this defines the 3D visibility complex. The boundaries of these groups of rays correspond to the visual events of the scene (limits of shadows, disappearance of an object when the viewpoint is moved, etc.). We simplify this structure into a graph in line-space which we call the visibility skeleton. Visual events are the arcs of this graph, and our construction algorithm avoids the intricate treatment of the corresponding 1D sets of lines. We simply compute the extremities (lines with 0 degrees of freedom) of these sets, and we topologically deduce the visual events using a catalogue of adjacencies. Our implementation shows that the skeleton is more general, more efficient and more robust than previous techniques. Applied to lighting simulation, the visibility skeleton permits more accurate and more rapid simulations. We have also developed an occlusion culling preprocess for the display of very complex scenes. We compute the set of potentially visible objects with respect to a volumetric region. In this context, our method is the first which handles the cumulative occlusion due to multiple blockers. Our occlusion tests are performed in planes using extended projections, which makes them simple, efficient and robust. In the second part of the document, we present a vast survey of work related to visibility in various domains.

Visibility determination is a key requirement in a wide range of graphics applications. This work introduces a new approach to the computation of volumetric visibility, the detection of occluded portions of space as seen from a given region. The method is conservative and classifies regions as occluded only then they are guatanteed to be invisible. It operates on a discrete representation of space and uses the opaque interior of objects as occluders. This choice of occluders facilitates their extension into opaque regions of space, in essence maximizing their size and impact. Out method efficiently detects and represents the regions of space hidden by such occluders and is the first one to use the property that occluders can also be extended into empty space provides that space is itself occluded as seen from the viewing volume. This proves extremely effective for computing the occlusion by a set of occluders, effectively realizing occluder fusion. An auxiliary data structure represents occlusion in the scene, which can then be querried to answer volume visibility questions. We demonstrate the applicability to visibility preprocessing for real-time walkthroughs anbd to shadow-ray acceleration for extended light sources in ray tracing, with significant speed-up in all cases.

This talk aims at presenting the research and development on Augmented Reality at Siemens Corporate Research. Due to lack of time I only present one application, Camera Augmented Mobile C-arm (CAMC), in detail. The rest of the presentation provides an overview of our other research activities. I also present a series of live demos.

Camera Augmented Mobile C-arm (CAMC) consists of an optical camera attached to a mobile X-ray C-arm. This was originally introduced for dynamic calibration of X-ray C-arm for 3D tomographic reconstruction(MICCAI'99). We compare the CAMC reconstruction results with the one obtained using an external tracking system (Polaris from Northern digital) for dynamic calibration(CVPR'00-1). We then add a double mirror system in order to create similar geometry for both X-ray and optical imaging systems. This results in the first real-time integration of X-ray and optical images. Finally, we run our Visual Servoing Based Precise Needle Placement(CVPR'00-2) under X-ray augmented video control. This introduces a new visualization tool and reduces the X-ray exposure to both patient and physician.

A series of demonstrations present other areas of research and development in our augmented reality group (WACV'98, IWAR'99, CVPR'00, ICME'00). In particular, we present a software called CyliCon for 3D reconstruction and AR applications in industrial environment.

Related Publications:

• MICCAI'99: N. Navab and M. Mitschke and O. Schuetz, "Camera augmented Mobile C-arm (CAMC) Application: 3D reconstruction using a low-cost mobile C-arm", Proceeding of the Second International Conference on Medical Image Computing and Computer-Assisted Intervention, Cambridge, England, September 1999.
• CVPR'00-1: M. Mitschke and N. Navab, "Recovering projection geometry: how a cheap camera can outperform an expensive stereo system", CVPR, Hilton Head Island, SC, USA, June 2000.
• CVPR'00-2: N. Navab and B. Bascle and M. H. Loser and B. Geiger and R. H. Taylor, "Visual servoing for Automatic and uncalibrated needle placement for percutaneous procedures", CVPR, Hilton Head Island, SC, USA, June 2000.
• CVPR'00-3: N. Navab, Y. Genc, and M. Appel. "Lines in one orthographic and two perspective views", CVPR, Hilton Head Island, SC, USA, June 2000.
• CVPR'00-4: B. Thirion, B. Bascle, V. Ramesh, and N. Navab, "Fusion of Color, Shading and Boundary Information For Factory Pipe Segmentation", CVPR, Hilton Head Island, SC, USA, June 2000.
• ICME'00: X. Zhang, N. Navab, S. Liou, 'E-Commerce Direct Marketing using Augmented Reality', IEEE International Conference on Multimedia and Expo, Jul. 30 - Aug. 2, 2000, New York City.
• IWAR'99: N. Navab, B. Bascle, M. Appel, and E. Cubillo. "Scene augmentation via the fusion of industrial drawings and uncalibrated images with a view to marker-less calibration". In Proc. IEEE International Workshop on Augmented Reality, San Francisco, CA, USA, October 1999.

Haptic visualization refers to perception of information through the haptic sense. Haptic devices capable of teleoperation often use a force-feedback control scheme that plays an important role in human-computer interactions. The talk will describe several projects currently investigated at our HCI Laboratory using the PHANTOM device. These include haptic visualization, FFB enhanced manipulation and application in computational chemistry. Open problems will be mentioned like: haptic tracking, FFB stability, haptic hints and haptic textures.

Scientific visualization penetrates into new applications in order to give the user better possibility to interpret application specific data. Our research has been concentrated on technological processes in power plants. Simulation and visualization of some processes could be covered by some existing software but some specific processes are not covered at all. The software used is mostly based on complex mathematical theories what results in computationaly demanding calculations. The target of our research was to create simulation and visualization tools that could be used in education. The algorithms developed will be generally less accurate in comparison with complex algorithms currently used but they will provide results in a very fast way. This will allow the students to get a feeling of behavior of some specific processes in a short time. The algorithms developed during our research were mostly based on particle systems and include simulation and visualization of the following processes:

• air polution
• combustion processes
• coal transport
• hot fluid gas filtering
• coal drying
• etc.

The algoritms developed are subject of improvement and verification based on real data obtained from measurements in real power plants.

The experimental system DILEWA utilizing virtual reality for educational purposes will be described. The main difference from commonly used systems for distributed VR (like Blaxxun) is that DILEWA users can act in three different roles - tutor, dependent, and independent participant. Within one shared virtual world, a single user acts as a tutor and the others can either watch the world through his/her eyes or work independently. Such a system does not need visible avatars, but a distribution of all activities of a tutor to the audience. The pilot version of DILEWA has been implemented using VRML, EAI, and Java.

Discrete time dynamical systems represented by the iteration of noninvertible maps may exhibit attracting sets and basins of attraction with topological structures which are more complex than the ones arising in other kinds of dynamical systems, such as those represented by the iteration of diffeomorphisms or those in continuous time, represented by ordinary differential equations.

Noninvertible map means "many-to-one". Geometrically, this can be expressed by saying that the phase space is "folded" by the application of the map, so that distinct points are mapped into the same point. This is equivalently stated by saying that a point has several distinct preimages, i.e. several inverses are defined, and these inverses ``unfold'' the phase space.

The mathematical treatment of these dynamical systems is still not well developed, and a significant part of the rich dynamic phenomena numerically observed is not well understood. Their study, often motivated by the problems arising in applications, have not yet converged to a systematic theory, and numerical experiments are crucial in both exploration and understanding of the rich dynamical phenomena and global bifurcations observed. In recent years, interesting results in this field have been obtained by the method of critical sets, a powerful tool through which several global properties and bifurcations, which are typical of such type of maps, are explained (see [1-3]).

The creation, destruction and the qualitative changes of the boundaries of chaotic attractors, as well as the qualitative changes in the structure of the basins' boundaries, are often explained in terms of contacts between repelling invariant sets and critical sets. These contact bifurcations may be important to understand two different routes to complexity: one related to the creation of more and more complex attractors, and one related to more and more complex structures of the basins. Both these routes to complexity may be important in the study of dynamical models met in applications (see e.g. [4-6]).

The study of such contact bifurcations is generally based on both theoretical and computational methods, and the graphical visualization becomes crucial in the discovery and explanation of new dynamic scenarios and their parameter dependence.

References

• [1] I. Gumowski and C. Mira 1#1 Chaotique, Cepadues Editions, Toulose 1980..
• [2] C. Mira, L. Gardini, A. Barugola and J.C. Cathala Chaotic Dynamics in Two-Dimensional Noninvertible Maps, World Scientific, Singapore, 1996.
• [3] R. Abraham, L. Gardini and C. Mira Chaos in Discrete Dynamical Systems (a visual introduction in two Dimensions) Springer-Verlag, 1997.
• [4] G.I. Bischi, L. Stefanini and L. Gardini ``Synchronization, intermittency and critical curves in duopoly games'', Mathematics and Computers in Simulations, 44, 559-585 (1998).
• [5] G.I. Bischi and L. Gardini ``Role of invariant and minimal absorbing areas in chaos synchronization'', Physical Review E, 58, 5710-5719 (1998).
• [6] G.I. Bischi, L. Gardini and M. Kopel ``Analysis of Global Bifurcations in a Market Share Attraction Model'', Journal of Economic Dynamics and Control (in press)

Advances in image synthesis techniques allow us to simulate the distribution of light energy in a scene with great precision. Unfortunately, this does not ensure that the displayed image will have authentic visual appearance. Reasons for this include the limited dynamic range of displays, and any residual shortcomings of the rendering process. Furthermore, it is unclear to what extend human vision will encode such departures from perfect physical realism. This leads to a need for including the human observer in any process which attempts to evaluate the perceptual significance of any errors in reproduction. Our psychophysical studies address this need.

This talk provides an introduction to the application of psychophysics to the evaluation and advancement of computer graphics with respect to the real scenes they are intended to depict. It covers the fundamentals of the design and organisation of psychophysical experiments, data collection and analysis and the application of results to rendering algorithms. The emphasis of this seminar is on the practical issues which must be addressed so that human subjects may easily make perceptual evaluations between the real and synthetic scenes. Case studies, involving comparing a test environment consisting of a small room containing complex objects to its rendered counterpart, will also be discussed.

Virtual Reality (VR) appears a natural medium for computer supported collaborative work (CSCW). However immersive Virtual Reality separates the user from the real world and their traditional tools. An alternative approach is through Augmented Reality (AR), the overlaying of virtual objects on the real world. This allows users to see each other and the real world at the same time as the virtual images, facilitating a high bandwidth of communication between users and intuitive manipulation of the virtual information. We review AR techniques for developing CSCW interfaces and describe lessons learned from developing a variety of collaborative Augmented Reality interfaces for both face to face and remote collaboration. Our recent work involves the use of computer vision techniques for accurate AR registration. We describe this and identify areas for future research.

Erstmals wurden von Hans Berger zur Jahrhundertwende elektrische Spannungsschwankungen des Gehirns vom intakten Schädel des Menschen registriert. Seither hat sich das "EEG" einen bedeutenden Platz in der Diagnostik von Gehirnerkrankungen, insbesondere Epilepsieen erobert. Dennoch ist dessen Natur noch weitgehend unbekannt. Fest steht allerdings, daß es Ausdruck komplexer kooperativer elektrischer Prozesse im Gehirn ist. Angesichts der noch immer verbreiteten Meinung, das Gehirn sei elektrisch nichts anderes als ein Volumsleiter, wurde das EEG lange Zeit als eine Art "elektrischer Hirnlärm" ohne jede funktionelle Bedeutung aufgefaßt. Nachdem aber in den vergangenen Jahren immer mehr Hinweise auf geistige Prozesse auftauchten, die sich im EEG widerspiegeln, hat das EEG zunehmend Interesse für das Studium von Denkvorgängen gefunden. Der Vortrag zeigt die proteusartige Phänomenologie des EEGs, wenn man es auf der Makro-Ebene (am Schädel), der Mikroebene (im Nervenzellverband) und auf der Ebene einzelner Nervenzellen studiert. Er zeigt weiters, daß ein Optimum an Information aus dem EEG dann zu gewinnen ist, wenn es als Ausdruck der funktionellen Zusammenhänge in einem komplexen elektrischen Netzwerk aufgefaßt wird.

Ray shooting is one of the most important problems for computer graphics. The efficiency of the algorithms for ray shooting has great impact on the performance of many global illumination algorithms. In this talk we give a short survey to various methods developed for ray shooting from the perspective of computational geometry and computer graphics. Particularly, we will focus on the concepts of orthogonal Kd-trees more often referred to as BSP trees in computer graphics. Recent developments in ray shooting will be discussed.

I will introduce a classification of visibility problems in three dimensions that is based on the dimension of the space of lines involved in the problem. In particular the following three classes will be discussed: visibility along a line, visibility from a point, and visibility from a region. Further, I will present a conservative hierarchical visibility algorithm for a moving viewpoint that is suitable for real time visibility culling. The algorithm uses occlusion tree that is a modification of the shadow volume BSP tree. Finally, I will mention some general refinements that make use of spatial and temporal coherence in the scope of hierarchical visibility algorithms.

Die Wunderkammer ist als Teil einer kollaborativen elektronischen Arbeitsumgebung für Architekten, Landschaftsplaner und andere design-orientierte Professionen gedacht. Sie wird gegenwärtig im Rahmen des Esprit LTR Projekts DESARTE entwickelt. Die Wunderkammer ist ein multi-mediales Archiv, das das Sammeln und Entdecken inspirationaler Objekte und ihre Darstellung unterstützt. Topographie und Erscheidungsbild sollen der visuellen Kultur der jeweiligen Designdisziplin entsprechen, und beispielweise als modular aufgebauter, symbolischer Stadtraum oder als fliessende Abfolge von Landschaftsformationen gestaltet sein. Feldarbeit im Architekturbüro gibt Aufschluß über die Bedeutung inspirationaler Objekte (dies mögen Bilder, Skizzen, metaphorische Beschreibungen, Filmausschnitte usw. sein) sowohl für die Entwurfsarbeit selbst, als auch für die Kommunikation von Projektideen nach aussen. BenutzerInnen sollen in der Wunderkammer ihre eigene Sammlung anlegen und diese mit anderen teilen können. Es sollen verschiedene Modi des Bereisens und Entdeckens sowie des erzählenden Zusammenfügens von Objekten (als Collage, Animation, Film usw.) unterstützt werden. Sie sollen letztlich ihre eigene Wunderkammer-Welt gestalten können. 

A mathematical model for shading analysis developed for purposes of solar engineering is described. Closed form expressions giving the position of the shadow as a function of time for an isolated point are derived. It was found that these expressions define second-order planar curves. Furthermore, the developed equations can be expressed in generalized parametric form enabling a smooth transition between different curves of the same class. Feasibility of these expressions for computer graphics should be further investigated.

Since the introduction of the radiosity method for image synthesis in 1984, many improvements to it have been proposed. Some of these, such as the computation of form factors using the hemicube algorithm and Southwell iterations for solving the radiosity set of equations, have made that the radiosity method begins to emerge in commercial rendering software systems. These techniques appeared in scientific literature more than 10 years ago.

In this talk, I will give an overview of techniques that appeared since then to make the radiosity method more efficient, user friendly and reliable. Two of these, hierarchical refinement, based on wavelet theory, and the solution of the radiosity system of equations by using Monte Carlo simulation, will be discussed in more detail. A combination of hierarchical refinement and Monte Carlo promises to make radiosity feasible for complex models, even on low cost platforms.

I will describe work to depict, explore, and understand large scale to very large scale data. For data of this size, one cannot just consider visualization techniques alone but must consider them in conjunction with issues of data organization, interactivity, data paging and memory management, efficient visual representation, overall detail management, and techniques for exploration and discovery. Efficiency becomes predominant, time is of the essence, and exploration is key (since nobody will know, in detail, what a very large dataset contains). I will show that these issues are not just important for the applications presented but have much wider applicability.

Ein zentrales Problem der Graphischen Datenverarbeitung ist das ständig wachsende Datenaufkommen. Mit der zunehmenden Verfügbarkeit komplexer Modellierungs- und Simulationswerkzeuge und mit der zunehmenden Verbreitung hochaufgelöster 3D-Scanner wird sich dieses Problem in Zukunft weiter verschärfen.

Aus diesem Grund scheinen sich hierarchische Methoden, Mehrfachauflösungen und Wavelets im Augenblick zu einer Schlüsseltechnik für 3D-Graphikanwendungen zu entwickeln. Durch ihre Verwendung wird es möglich, komplexe Funktionen und große Datensätze mit wenigen Koeffizienten gut zu approximieren. Dies führt zu neuartigen Kompressionsalgorithmen und effizienten Berechnungen unter Ausnutzung von Glattheit und Kohärenz. Der Vortrag bespricht grundlegende Anwendungen hierarchischer Methoden in folgenden Teilgebieten der Graphischen Datenverarbeitung:

• Kurven und Flächenmodellierung,
• Effiziente Polygonnetze,
• Globale Beleuchtungsberechnung.

Konkrete Beispiele aus laufenden Implementierungen an der Universität Erlangen illustrieren die zugrundeliegenden Konzepte und unterstreichen die Tragfähigkeit des vorgestellten Ansatzes.