Contributions published at Visualization and MultiMedia Lab (Renato Pajarola)

As modern high-resolution imaging devices allow to acquire increasingly large and complex volume data sets, their effective and compact representation for visualization becomes a challenging task. The Tucker decomposition has already confirmed higher-order tensor approximation (TA) as a viable technique for compressed volume representation; however, alternative decomposition approaches exist. In this work, we review the main TA models proposed in the literature on multiway data analysis and study their application in a visualization context, where reconstruction performance is emphasized along with reduced data representation costs. Progressive and selective detail reconstruction is a main goal for such representations and can efficiently be achieved by truncating an existing decomposition. To this end, we explore alternative incremental variations of the CANDECOMP/PARAFAC and Tucker models. We give theoretical time and space complexity estimates for every discussed approach and variant. Additionally, their empirical decomposition and reconstruction times and approximation quality are tested in both C++ and MATLAB implementations. Several scanned real-life exemplar volumes are used varying data sizes, initialization methods, degree of compression and truncation. As a result of this, we demonstrate the superiority of the Tucker model for most visualization purposes, while canonical-based models offer benefits only in limited situations.

This paper presents SymmSketch — a system for creating symmetric 3D free-form shapes from 2D sketches. The reconstruction task usually separates a 3D symmetric shape into two types of shape components, that is, the self-symmetric shape component and the mutual-symmetric shape components. Each type of them can be created in an intuitive manner. According to a uniform symmetry plane, the user first draws 2D sketch lines for each shape component on a sketching plane. The z- depth information of the hand-drawn input sketches can be calculated using their property of mirror symmetry to generate 3D constructive curves. In order to provide more freedom for controlling the local geometric features of the reconstructed free- form shapes (such as their cross sections will not be limited to be traditional circular), our modeling system will create each shape component from four constructive curves. With one pair of symmetric curves and one pair of general curves, an improved cross-sectional surface blending scheme is applied to generate a parametric surface for each component. The final symmetric free- form shape will be progressively created and be represented as 3D triangular mesh. Experimental results illustrate that our system can generate symmetric complex free-form shapes effectively and conveniently.

null

Interactive visualizations of large-scale datasets can greatly benefit from parallel rendering on a cluster with hardware accelerated graphics by assigning all rendering client nodes a fair amount of work each. However, interactivity regularly causes unpredictable distribution of workload, especially on large tiled displays. This requires a dynamic approach to adapt scheduling of rendering tasks to clients, while also considering data-locality to avoid expensive I/O operations. This article discusses a dynamic parallel rendering load balancing method based on work packages which define rendering tasks. In the presented system, the nodes pull work packages from a centralized queue that employs a locality-aware affinity model for work package assignment. Our method allows for fully adaptive workload distribution for both sort-first and sort-last parallel rendering.

Using 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.

We present a robust approach for reconstructing the main architectural structure of complex indoor environments given a set of cluttered 3D input range scans. Our method uses an efficient occlusion-aware process to extract planar patches as candidate walls, separating them from clutter and coping with missing data, and automatically extracts the individual rooms that compose the environment by applying a diffusion process on the space partitioning induced by the candidate walls. This diffusion process, which has a natural interpretation in terms of heat propagation, makes our method robust to artifacts and other imperfections that occur in typical scanned data of interiors. For each room, our algorithm reconstructs an accurate polyhedral model by applying methods from robust statistics. We demonstrate the validity of our approach by evaluating it on both synthetic models and real-world 3D scans of indoor environments.

We introduce a stochastic algorithm for pairwise affine registration of partially overlapping 3D point clouds with unknown point correspondences. The algorithm recovers the globally optimal scale, rotation, and translation alignment parameters and is applicable in a variety of difficult settings, including very sparse, noisy, and outlier-ridden datasets that do not permit the computation of local descriptors. The technique is based on a stochastic approach for the global optimization of an alignment error function robust to noise and resistant to outliers. At each optimization step, it alternates between stochastically visiting a generalized BSP-tree representation of the current solution landscape to select a promising transformation, finding point-to-point correspondences using a GPU-accelerated technique, and incorporating new error values in the BSP tree. In contrast to previous work, instead of simply constructing the tree by guided random sampling, we exploit the problem structure through a low-cost local minimization process based on analytically solving absolute orientation problems using the current correspondences. We demonstrate the quality and performance of our method on a variety of large point sets with different scales, resolutions, and noise characteristics.

Great advancements in commodity graphics hardware have favoured graphics processing unit (GPU)-based volume rendering as the main adopted solution for interactive exploration of rectilinear scalar volumes on commodity platforms. Nevertheless, long data transfer times and GPU memory size limitations are often the main limiting factors, especially for massive, time-varying or multi-volume visualization, as well as for networked visualization on the emerging mobile devices. To address this issue, a variety of level-of-detail (LOD) data representations and compression techniques have been introduced. In order to improve capabilities and performance over the entire storage, distribution and rendering pipeline, the encoding/decoding process is typically highly asymmetric, and systems should ideally compress at data production time and decompress on demand at rendering time. Compression and LOD pre-computation does not have to adhere to real-time constraints and can be performed off-line for high-quality results. In contrast, adaptive real-time rendering from compressed representations requires fast, transient and spatially independent decompression. In this report, we review the existing compressed GPU volume rendering approaches, covering sampling grid layouts, compact representation models, compression techniques, GPU rendering architectures and fast decoding techniques.

3-D stereo reconstruction, a technique that estimates per-pixel depth in a scene, is still a challenging problem mainly due to some prohibitive factors that limit its performance and computational ability. The aim of this paper is to present a new hardware-efficient disparity map computation, which is based on disparity space image processing using discrete dynamic systems. The hardware architecture of the proposed system was implemented on a high-end field programmable gate array (FPGA) device, offering real-time 3-D reconstruction speeds using a hardware aware architecture based on parallelism and process pipelining. The proposed architecture fulfills the requirements of real-world applications regarding resource usage, frame rates, and disparity resolution, while its implementation on an Altera Stratix IV family FPGA device can extract disparity maps of up to 1280 × 1024 pixels with up to 128 disparity levels under real-time or near real-time conditions at a clock rate of 168 MHz. Qualitative and quantitative results also demonstrate its performance and improvement over previous hardware-related studies, making our approach a suitable candidate for applications in which timing and processing constraints are critical.

This thesis presents the Sapana Viewer. The Sapana Viewer is an educational model viewer that teaches the principles of 3D model rendering. The Sapana Viewer is meant as an addition to traditional computer graphics lecturing. It tries to explain certain concepts that are hard to teach using traditional approaches. This thesis first analyzes the requirements students have regarding the Sapana Viewer. Based on these findings the design of the GUI is presented. The software architecture of the Sapana Viewer is described and finally, the implementation of the Sapana Viewer prototype is documented.

Reconstructing the architectural shape of interiors is a problem that is gaining increasing attention in the field of computer graphics. Some solutions have been proposed in recent years, but cluttered environments with multiple rooms and non-vertical walls still represent a challenge for state-of-the-art methods. We propose an occlusions- aware pipeline that extends current solutions to work with complex environments with arbitrary wall orientations.

null

We present a method to automatically segment indoor scenes by detecting repeated objects. Our algorithm scales to datasets with 198 million points and does not require any training data. We propose a trivially parallelizable preprocessing step, which compresses a point cloud into a collection of nearly-planar patches related by geometric transformations. This representation enables us to robustly filter out noise and greatly reduces the computational cost and memory requirements of our method, enabling execution at interactive rates. We propose a patch similarity measure based on shape descriptors and spatial configurations of neighboring patches. The patches are clustered in a Euclidean embedding space based on the similarity matrix to yield the segmentation of the input point cloud. The generated segmentation can be used to compress the raw point cloud, create an object database, and increase the clarity of the point cloud visualization.

With better and faster acquisition devices comes a demand for fast robust reconstruction algorithms, but no L1-based technique has been fast enough for online use so far. In this paper, we present a novel continuous formulation of the weighted locally optimal projection (WLOP) operator based on a Gaussian mixture describing the input point density. Our method is up to 7 times faster than an optimized GPU implementation of WLOP, and achieves interactive frame rates for moderately sized point clouds. We give a comprehensive quality analysis showing that our continuous operator achieves a generally higher reconstruction quality than its discrete counterpart. Additionally, we show how to apply our continuous formulation to spherical mixtures of normal directions, to also achieve a fast robust normal reconstruction.

We present a robust approach for reconstructing the architectural structure of complex indoor environments given a set of cluttered input scans. Our method first uses an efficient occlusion-aware process to extract planar patches as candidate walls, separating them from clutter and coping with missing data. Using a diffusion process to further increase its robustness, our algorithm is able to reconstruct a clean architectural model from the candidate walls. To our knowledge, this is the first indoor reconstruction method which goes beyond a binary classification and automatically recognizes different rooms as separate components. We demonstrate the validity of our approach by testing it on both synthetic models and real-world 3D scans of indoor environments.

Fractal algorithms and self similar object geometry have gained currency in computer science. Considering security issues, on computational numerics and computer graphics, there are many applications. A common field in computer graphics is the usage of fractal algorithms for the dynamic generation of large complex models and natural objects with great variability but strong self-similarity. One type of these algorithms, which are based on mathematical self similar objects are called L-Systems and can contain any kind of randomly changing model parts that can be used for many different applications, as for example the dynamic generation of vegetation, plants, random generation of a terrain height field or even for randomized texturing of objects. The core of this thesis is a new library through which a dynamic generation of agricultural crops can be dealt with similar to existing predefined grammars and operations. Very much like a blueprint it is possible to define patterns for a special kind of plant in the new built L-Systems language.

Algorithms and data structures are an essential foundation in computer science, but students struggle to understand them. Serious games seem very well suited for teaching them, yet they are relatively sparsly used in computer science education. Hence, we developed a serious game to help students comprehend basic sorting algorithms, and assess the effects of this tool on their learning success. Our serious game features a interactive, well-explained algorithm visualisations to both teach and challenge the users, as well as questions that require the user to sort code snippets. Different sources of motivation are provided. Preliminary user test suggest that both the visualisation as well as the coding questions are beneficial to user learning, and that the primary motivation of players may be the challenge itself.

null

In this course, we will introduce the basic concepts of tensor approximation (TA) – a higher-order generalization of the SVD and PCA methods – as well as its applications to visual data representation, analysis and visualization, and bring the TA framework closer to visualization and computer graphics researchers and practitioners. The course will cover the theoretical background of TA methods, their properties and how to compute them, as well as practical applications of TA methods in visualization and computer graphics contexts. In a first theoretical part, the attendees will be instructed on the necessary mathematical background of TA methods to learn the basics skills of using and applying these new tools in the context of the representation of large multidimensional visual data. Specific and very noteworthy features of the TA framework are highlighted which can effectively be exploited for spatio-temporal multidimensional data representation and visualization purposes. In two application oriented sessions, compact TA data representation in scientific visualization and computer graphics as well as decomposition and reconstruction algorithms will be demonstrated. At the end of the course, the participants will have a good basic knowledge of TA methods along with a practical understanding of its potential application in visualization and graphics related projects.