Publications

Abstractt-distributed Stochastic Neighbour Embedding (t-SNE) has become a standard for exploratory data analysis, as it is capable of revealing clusters even in complex data while requiring minimal user input. While its run-time complexity limited it to small datasets in the past, recent efforts improved upon the expensive similarity computations and the previously quadratic minimization. Nevertheless, t-SNE still has high runtime and memory costs when operating on millions of points. We present a novel method for executing the t-SNE minimization. While our method overall retains a linear runtime complexity, we obtain a significant performance increase in the most expensive part of the minimization. We achieve a significant improvement without a noticeable decrease in accuracy even when targeting a 3D embedding. Our method constructs a pair of spatial hierarchies over the embedding, which are simultaneously traversed to approximate many N-body interactions at once. We demonstrate an efficient GPGPU implementation and evaluate its performance against state-of-the-art methods on a variety of datasets.

AuthorsMark van de Ruit, Markus Billeter & Elmar Eisemann

Pre-print: Vis 2021 / TVCG

AbstractVoxels are a popular choice to encode complex geometry. Their regularity makes updates easy and enables random retrieval of values. The main limitation lies in the poor scaling with respect to resolution. Sparse voxel DAGs (Directed Acyclic Graphs) overcome this hurdle and offer high-resolution representations for real-time rendering but only handle static data. We introduce a novel data structure to enable interactive modifications of such compressed voxel geometry without requiring de- and recompression. Besides binary data to encode geometry, it also supports compressed attributes (e.g., color). We illustrate the usefulness of our representation via an interactive large-scale voxel editor (supporting carving, filling, copying, and painting).

(Note: find links to code and additional materials via the "More..." link)

AuthorsVictor Careil, Markus Billeter & Elmar Eisemann

Presentedat Eurographics

AbstractEye-tracking with gaze estimation is a key element in many applications, ranging from foveated rendering and user interaction to behavioural analysis and usage metrics. For virtual reality, eye-tracking typically relies on near-eye cameras that are mounted in the VR headset. Such methods usually involve an initial calibration to create a mapping from eye features to a gaze position. However, the accuracy based on the initial calibration degrades when the position of the headset relative to the users’ head changes; this is especially noticeable when users readjust the headset for comfort or even completely remove it for a short while. We show that a correction of such shifts can be achieved via 2D drift vectors in eye space. Our method estimates these drifts by extracting salient cues from the shown virtual environment to determine potential gaze directions. Our solution can compensate for HMD shifts, even those arising from taking off the headset, which enables us to eliminate reinitialization steps.

AuthorsPeiteng Shi, Markus Billeter & Elmar Eisemann

Publishedat Computers & Graphics

AbstractA camera’s shutter controls the incoming light that is reaching the camera sensor. Different shutters lead to wildly different results, and are often used as a tool in movies for artistic purpose, e.g., they can indirectly control the effect of motion blur. However, a physical camera is limited to a single shutter setting at any given moment. ShutterApp enables users to define spatio-temporally-varying virtual shutters that go beyond the options available in real-world camera systems. A user provides a sparse set of annotations that define shutter functions at selected locations in key frames. From this input, our solution defines shutter functions for each pixel of the video sequence using a suitable interpolation technique, which are then employed to derive the output video. Our solution performs in real-time on commodity hardware. Hereby, users can explore different options interactively, leading to a new level of expressiveness without having to rely on specialized hardware or laborious editing.

AuthorsNestor Z. Salamon, Markus Billeter & Elmar Eisemann

Presentedat Pacific Graphics

Abstract Shadow volumes are a popular technique to compute pixel-accurate hard shadows in 3D scenes. Many variants exist that trade off accuracy and efficiency. In this work, we present an artifact-free, efficient, and easy-to-implement stencil shadow volume method. We compare our method to established stencil shadow volume techniques and show that it outperforms the alternatives.

AuthorsBaran Usta, Leonardo Scandolo, Markus Billeter, Ricardo Marroquim & Elmar Eisemann

Presentedat High Performance Graphics

AbstractWe implement a massively parallel population Monte Carlo approximate Bayesian computation (PMC‐ABC) method for estimating diffusion coefficients, sizes and concentrations of diffusing nanoparticles in liquid suspension using confocal laser scanning microscopy and particle tracking. The method is based on the joint probability distribution of diffusion coefficients and the time spent by a particle inside a detection region where particles are tracked. We present freely available central processing unit (CPU) and graphics processing unit (GPU) versions of the analysis software, and we apply the method to characterize mono‐ and bidisperse samples of fluorescent polystyrene beads.

AuthorsMagnus Röding & Markus Billeter

Publishedat Journal of Microscopy

AbstractRendering vector maps is a key challenge for high-quality geographic visualization systems. In this paper we present a novel approach to visualize vector maps over detailed terrain models in a pixel-precise way. Our method proposes a deferred line rendering technique to display vector maps directly in a screen-space shading stage over the 3D terrain visualization. Due to the absence of traditional geometric polygonal rendering, our algorithm is able to outperform conventional vector map rendering algorithms for geographic information systems, and supports advanced line antialiasing as well as slope distortion correction. Furthermore, our deferred line rendering enables interactively customizable advanced vector styling methods as well as a tool for interactive pixel-based editing operations.

AuthorsMatthias Thöny, Markus Billeter & Renato Pajarola

Publishedat Computer Graphics Forum

Abstract We propose the first system for live dynamic augmentation of human faces. Using projector-based illumination, we alter the appearance of human performers during novel performances. The key challenge of live augmentation is latency — an image is generated according to a specific pose, but is displayed on a different facial configuration by the time it is projected. Therefore, our system aims at reducing latency during every step of the process, from capture, through processing, to projection. In contrast to existing methods, the presented system is the first method which fully supports dynamic facial projection mapping without the requirement of any physical tracking markers and incorporates facial expressions.

AuthorsAmit Bermano, Markus Billeter, Daisuke Iwai & Anselm Grundhöfer

Publishedat Eurographics 2017

AbstractInteractive rendering of large scale vector maps is a key challenge for high-quality geographic visualization software systems. In this paper we present a novel approach for the visualization of large scale vector maps over detailed height-field terrains. Our method uses a deferred line shading approach to render large scale vector maps directly in a screen-space shading stage over a terrain visualization. The fact that there is no traditional geometric polygonal rendering involved allows our algorithm to outperform conventional vector map rendering algorithms for geographic information systems. Our flexible deferred line rendering approach allows a user to interactively customize and apply advanced vector styling methods, as well as the integration into a vector map level-of-detail system.

AuthorsMatthias Thöny, Markus Billeter & Renato Pajarola

Presentedat SIGGRAPH Asia 2016 - Symposium on Visualization (Honorable Mention Award)

Abstract We present a generic latency measurement device which can be used to accurately measure the overall end-to-end latency of camera-based AR systems with an accuracy below one millisecond. It comprises a LED-based time stamp generator displaying the time as a gray code on spatially and spectrally multiple locations. It is controlled by a micro-controller and sensed by an external camera device observing the output display as well as the LED device at the same time.

AuthorsMarkus Billeter, Gerhard Röthlin, Jan Wezel, Daisuke Iwai & Anselm Grundhöfer

Publishedat IEEE ISMAR 2016 (Adjunct Proceedings)

AbstractWe encode time-varying voxel data for efficient storage and streaming. We store the equivalent of a separate sparse voxel octree for each frame, but utilize both spatial and temporal coherence to reduce the amount of memory needed. We represent the time-varying voxel data in a single directed acyclic graph with one root per time step. In this graph, we avoid storing identical regions by keeping one unique instance and pointing to that from several parents. We further reduce the memory consumption of the graph by minimizing the number of bits per pointer and encoding the result into a dense bitstream.

AuthorsViktor Kämpe, Sverker Rasmuson, Markus Billeter, Erik Sintorn & Ulf Assarsson

Publishedat Interactive 3D Games and Graphics (I3D) 2016

AbstractRecently, several algorithms have been introduced that enable real-time performance for many lights in applications such as games. In this paper, we explore the use of hardware-supported virtual cube-map shadows to efficiently implement high-quality shadows from hundreds of light sources in real time and within a bounded memory footprint. In addition, we explore the utility of ray tracing for shadows from many lights and present a hybrid algorithm combining ray tracing with cube maps to exploit their respective strengths. Our solution supports real-time performance with hundreds of lights in fully dynamic high-detail scenes.

(Extended version of the I3D "Efficient Virtual Shadow Maps for Many Lights"-paper. Pre-print available below.)

AuthorsOla Olsson, Markus Billeter, Erik Sintorn, Viktor Kämpe & Ulf Assarsson

In: IEEE Transactions on Visualization and Computer Graphics

AbstractTerrain rendering is widely used in industry and research. GIS software packages and navigation systems make use of terrain rendering to visualize terrain information. Recent trends in research show that scientific terrain visualization is shifting more and more to serve as an interactive analysis tool. This allows domain specific users to perform visual analysis tasks within an interactive visual environment. Visual analysis tools are software package acting as a toolbox and providing functionality to support the work of domain specific users such as data exploration, data analysis and data presentation. Such software packages still suffer from limitations such as restricted or imprecise data and problems with large data handling. These challenges will also be at the core of research in scientific terrain visualization in the near future. In this paper we describe some open challenges for scientific terrain visualization in the acquisition, processing and rendering of terrain related geo-spatial information as well as new methods which could be used to address these challenges.

AuthorsMatthias Thöny, Markus Billeter & Renato Pajarola

Presentedat SIGSPATIAL 2015

AbstractRecently, several algorithms have been introduced that enable real-time performance for many lights in applications such as games. In this paper, we explore the use of hardware-supported virtual cube-map shadows to efficiently implement high-quality shadows from hundreds of light sources in real time and within a bounded memory footprint. In addition, we explore the utility of ray tracing for shadows from many lights and present a hybrid algorithm combining ray tracing with cube maps to exploit their respective strengths. Our solution supports real-time performance with hundreds of lights in fully dynamic high-detail scenes.

AuthorsOla Olsson, Erik Sintorn, Viktor Kämpe, Markus Billeter & Ulf Assarsson

Publishedat Interactive 3D Games and Graphics (I3D) 2014

AbstractThis paper presents and investigates Clustered Shading for deferred and forward rendering. In Clustered Shading, view samples with similar properties (e.g. 3D-position and/or normal) are grouped into clusters. This is comparable to tiled shading, where view samples are grouped into tiles based on 2D-position only. We show that Clustered Shading creates a better mapping of light sources to view samples than tiled shading, resulting in a significant reduction of lighting computations during shading. Additionally, Clustered Shading enables using normal information to perform per-cluster back-face culling of lights, again reducing the number of lighting computations. We also show that Clustered Shading not only outperforms tiled shading in many scenes, but also exhibits better worst case behaviour under tricky conditions (e.g. when looking at high-frequency geometry with large discontinuities in depth). Additionally, Clustered Shading enables real-time scenes with two to three orders of magnitudes more lights than previously feasible (up to around one million light sources).

AuthorsOla Olsson, Markus Billeter & Ulf Assarsson

Publishedat High Performance Graphics 2012

AbstractThis paper introduces a new GPU-based, real-time method for rendering volumetric lighting effects produced by scattering in a participating medium. The method includes support for indirect illumination by scattered light, high-quality single-scattered volumetric shadows, and approximate multiple scattered volumetric lighting effects in isotropic and homogeneous media. The method builds upon an improved propagation scheme for light propagation volumes. This scheme models scattering according to the radiative light transfer equation during propagation. The initial state of the light propagation volumes is based on single-scattered light identified with shadow maps; this allows generation of a high quality initial distribution of radiance. After propagation, the resulting distribution is used as a source of diffuse light during rendering and is also ray marched for volumetric effects from multiple scattering. Volumetric shadows from single-scattered light are rendered separately. We compare the new method to single-scattered volumetric shadows produced by contemporary techniques, plain light propagation volumes (which this new method extends), and a simple composition thereof.

AuthorsMarkus Billeter, Erik Sintorn & Ulf Assarsson

Publishedat Interactive 3D Graphics and Games (I3D) 2012

AbstractWe investigate the use of two-level nested grids as acceleration structure for ray tracing of dynamic scenes. We propose a massively parallel, sort-based construction algorithm and show that the two-level grid is one of the structures that is fastest to construct on modern graphics processors. The structure handles non-uniform primitive distributions more robustly than the uniform grid and its traversal performance is comparable to those of other high quality acceleration structures used for dynamic scenes. We propose a cost model to determine the grid resolution and improve SIMD utilization during ray-triangle intersection by employing a hybrid packetization strategy. The build times and ray traversal acceleration provide overall rendering performance superior to previous approaches for real time rendering of animated scenes on GPUs.

AuthorsJavor Kalojanov, Markus Billeter & Philipp Slusallek

Publishedat Eurographics 2011

AbstractThis paper presents a more efficient way of computing single scattering effects in homogeneous participating media for real-time purposes than the currently popular ray-marching based algorithms. These effects include halos around light sources, volumetric shadows and crepuscular rays. By displacing the vertices of a base mesh with the depths from a standard shadow map, we construct a polygonal mesh that encloses the volume of space that is directly illuminated by a light source. Using this volume we can calculate the airlight contribution for each pixel by considering only points along the eye-ray where shadow-transitions occur. Unlike previous ray-marching methods, our method calculates the exact airlight contribution, with respect to the shadow map resolution, at real time frame rates.

AuthorsMarkus Billeter, Erik Sintorn & Ulf Assarsson

Publishedat High Performance Graphics 2010

AbstractRecently, several algorithms have been introduced that enable real-time performance for many lights in applications such as games. In this paper, we explore the use of hardware-supported virtual cube-map shadows to efficiently implement high-quality shadows from hundreds of light sources in real time and within a bounded memory footprint. In addition, we explore the utility of ray tracing for shadows from many lights and present a hybrid algorithm combining ray tracing with cube maps to exploit their respective strengths. Our solution supports real-time performance with hundreds of lights in fully dynamic high-detail scenes.

AuthorsMarkus Billeter, Ola Olsson & Ulf Assarsson

Publishedat High Performance Graphics 2009