Publications

Filter: allpaperstalksother
  • 2021
  • An Efficient Dual-Hierarchy t-SNE Minimization

    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

  • 2020
  • Interactively Modifying Compressed Sparse Voxel Representations

    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

  • SalientGaze: Saliency-Based Gaze Correction in Virtual Reality

    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

  • 2019
  • ShutterApp: Spatio-temporal Exposure Control for Videos

    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

  • A Practical and Efficient Approach for Correct Z-Pass Stencil Shadows Volumes

    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

  • 2018
  • Massively parallel approximate Bayesian computation for estimating nanoparticle diffusion coefficients, sizes and concentrations using confocal laser scanning microscopy

    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

  • Tutorial - Voxel DAGs and Multiresolution Hierarchies: From Large-Scale Scenes to Pre-computed Shadows

    AbstractIn this tutorial, we discuss voxel DAGs and multiresolution hierarchies, which are representations that can encode large volumes of data very efficiently. Despite a significant compression ration, an advantage of these structures is that their content can be efficiently accessed in real-time. This property enables various applications. We begin the tutorial by introducing the concepts of sparsity and of coherency in voxel structures, and explain how a directed acyclic graph (DAG) can be used to represent voxel geometry in a form that exploits both aspects, while remaining usable in its compressed from for e.g. ray casting. In this context, we also discuss extensions that cover the time domain or consider an advanced encoding strategies exploiting symmetries and entropy. We then move on to voxel attributes, such as colors, and explain how to integrate such information with the voxel DAGs. We will provide implementation details and present methods for efficiently constructing the DAGs and also cover how to efficiently access the data structures with e.g. GPU-based ray tracers. The course will be rounded of with a segment on applications. We highlight a few examples and show their results, and delve into one special application: compressed pre-computed shadows.

    (Slides available for download via the "More..." link.)

    AuthorsUlf Assarsson, Markus Billeter, Dan Dolonius, Elmar Eisemann, Alberto Jaspe, Leonardo Scandolo & Erik Sintorn

    Presentedat Eurographics 2018

  • 2017
  • Large-Scale Pixel-Precise Deferred Vector Maps

    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

  • Makeup Lamps: Live Augmentation of Human Faces via Projection

    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

  • 2016
  • Deferred Vector Map Visualization

    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)

  • A LED-Based IR/RGB End-to-End Latency Measurement Device

    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)

  • Exploiting Coherence in Time-Varying Voxel Data

    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

  • 2015
  • Course - Real-Time Many-Light Management and Shadows with Clustered Shading

    AbstractUsing many lights in real-time applications has been an important goal for many years. The games industry, in particular, has strived to increase the number of lights to provide enhanced visual quality and realism. Today, high-end games often make use of hundreds of lights in each frame, and the number of lights is likely to expand in the future. The ability to efficiently manage and shade large numbers of lights presents many possibilities, apart from simply allowing light to be cast from many dynamic objects. It can also support visualizing global illumination solutions, or enable detailed artistic light direction.

    This course presents an in-depth exploration of many-light management, starting with background and progressing to state-of-the-art research, including recent results on supporting shadows. The course combines production experience from game developers with the latest research into efficient many-light algorithms for both desktop and mobile hardware.

    (Slides available for download via the "More..." link.)

    AuthorsOla Olsson, Emil Persson & Markus Billeter

    Presentedat SIGGRAPH 2015

  • More Efficient Virtual Shadow Maps for Many Lights

    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

  • The Future of Scientific Terrain Visualization

    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

  • 2014
  • Course - Efficient Real-Time Shading with Many Lights

    AbstractUsing many lights in real-time applications has been an important goal for many years. The games industry in particular has strived to increase the number of lights to provide enhanced visual quality and realism. Today, high-end games often make use of hundreds of lights in each frame, and this is likely to be pushed further in the future. The ability to efficiently manage and shade large numbers of lights brings many possibilities, apart from simply allowing light to be cast from many dynamic objects. In addition, it can support visualizing global illumination solutions, or enable detailed artistic light direction. Thus, efficient real-time shading with many lights, represents a potential for solving many of the problems facing the development of next generation high-end games. To achieve the level of performance needed to make this possible, the way which light management and shading is performed has undergone dramatically development in recent years. Both industry and academia has invested great effort pursuing this goal, which has resulted in a large number of new and sometimes competing techniques.

    This course presents an in-depth exploration of this topic, starting with background and leading up to state of the art research, including recent results on supporting shadows. The course combines production experience from game developers with the latest research into efficient many-light algorithms for both desktop and mobile hardware.

    (Slides available for download via the "More..." link.)

    AuthorsOla Olsson, Emil Persson & Markus Billeter

    Presentedat SIGGRAPH Asia 2014

  • Implementing Efficient Virtual Shadow Maps for Many Lights

    AbstractIn the past few years, several techniques have been presented that enable real-time shading using many hundreds or thousands of lights [Harada et al. 2013]. However, only recently has a comprehensive study including shadows been presented by Olsson et al. [2014], where real-time performance is achieved for several hundred light sources with high quality and controllable memory footprint. The new algorithm uses many modern features of OpenGL and contains many design choices only described very briefly in the paper. We present additional details and focus on the practical implementation aspects of the system, in order to facilitate the implementation of the algorithm for the game development community.

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

    Presentedat SIGGRAPH 2014 Talks

  • PhD Thesis - Real-Time GPU Techniques for Advanced Lighting Phenomena

    AbstractIn the real world, the visual perception of an object is completely determined by the object's interactions with light. One large application of computer graphics is to visualize virtual objects and worlds in a fashion that is familiar to humans. Successfully emulating light and its effects on virtual objects therefore plays a central role. The papers included in this thesis mainly explore improved methods of computing the effects of light in various settings. The focus is on doing so in real-time for interactive applications. Two papers target capturing the visual effects of light traveling through a participating medium (a medium such as fog or smog). Next, two papers explore real-time rendering with many light sources. Graphics Processing Units (GPUs) play a central role in all these techniques. Thus, the very first paper included in this thesis discusses efficient implementations of fundamental building blocks for programming GPUs.

    AuthorsMarkus Billeter

    Defendedat Chalmers University of Technology, Department of Computer Science and Engineering (Division of Computer Engineering) in May 2014

  • Efficient Virtual Shadow Maps for Many Lights

    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

  • 2013
  • Tiled Forward Shading

    AbstractIn this chapter we explore the tiled forward shading algorithm. Tiled forward shading is an extension/modification of tiled deferred shading, which improves upon traditional deferred shading methods.

    Tiled forward shading attempts to combine some of the advantages normally associated with deferred shading with the advantages of forward shading, namely the capability to use alpha blending for transparency and various hardware-assisted multi-sampling schemes.

    AuthorsMarkus Billeter, Ola Olsson & Ulf Assarsson

    Includedin GPU Pro 4 - Advanced Rendering Techniques, Volume 4

  • 2012
  • Tiled and Clustered Forward Shading

    AbstractTiled and Clustered Forward Shading are new techniques that enable support for thousands of lights, while eliminating many of the drawbacks of deferred techniques. This talk shows how these techniques can be used and extended to support transparency with high efficiency.

    AuthorsOla Olsson, Markus Billeter & Ulf Assarsson

    Presentedat SIGGRAPH 2012 Talks

  • Clustered Deferred and Forward Shading

    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

  • Real-Time Multiple Scattering with Light Propagation Volumes

    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

  • 2011
  • Licentiate Thesis - Real-Time GPU Algorithms: Parallel Primitives and Rendering of Participating Media

    AbstractModern Graphics Processing Units (GPUs) present an immense resource of computational power, which however remains challenging to fully harness. This thesis explores four algorithms and methods that attempt to take full advantage of the resources provided by a GPU. The algorithms focus on efficient implementations that perform well enough to be considered for real-time applications.

    AuthorsMarkus Billeter

    Presentedat Chalmers University of Technology, Department of Computer Science and Engineering (Division of Computer Engineering) in October 2011

  • Two-Level Grids for Ray Tracing on GPUs

    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

  • 2010
  • Real Time Volumetric Shadows using Polygonal Light Volumes

    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

  • 2009
  • Efficient Stream Compaction on Wide SIMD Many-Core Architectures

    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

  • GPU Primitives - Case Study: Hair Rendering

    AbstractCase study that talks about GPU primitives and their application in rendering. Specifically, our sorting was used to accelerate the hair rendering implemented by Erik Sintorn.

    AuthorsUlf Assarsson, Markus Billeter, Ola Olsson & Erik Sintorn

    Presentedat Beyond Programmable Shading Course, SIGGRAPH 2009