28-Issue 8

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/150

Browse

Now showing 1 - 20 of 31

Fast Four-Way Parallel Radix Sorting on GPUs
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Ha, Linh; Krueger, Jens; Silva, Claudio T.
Efficient sorting is a key requirement for many computer science algorithms. Acceleration of existing techniques as well as developing new sorting approaches is crucial for many real-time graphics scenarios, database systems, and numerical simulations to name just a few. It is one of the most fundamental operations to organize and filter the ever growing massive amounts of data gathered on a daily basis. While optimal sorting models for serial execution on a single processor exist, efficient parallel sorting remains a challenge. In this paper, we present a hardware-optimized parallel implementation of the radix sort algorithm that results in a significant speed up over existing sorting implementations. We outperform all known General Processing Unit (GPU) based sorting systems by about a factor of two and eliminate restrictions on the sorting key space. This makes our algorithm not only the fastest, but also the first general GPU sorting solution.
Adaptive Interleaved Sampling for Interactive High-Fidelity Rendering
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Dubla, P.; Debattista, K.; Chalmers, A.
Recent advances have made interactive ray tracing (IRT) possible on consumer desktop machines. These advances have brought about the potential for interactive global illumination (IGI) with enhanced realism through physically based lighting. IGI, unlike IRT, has a much higher computational complexity. Furthermore, since non-primary rays constitute the majority of the computation, the rays are predominantly incoherent, making impractical many of the methods that have made IRT possible. Two methods that have already shown promise in decreasing the computational time of the GI solution are interleaved sampling and adaptive rendering. Interleaved sampling is a generalized sampling scheme that smoothly blends between regular and irregular sampling while maintaining coherence. Adaptive rendering algorithms adjust rendering quality, non-uniformally, using a guidance scheme. While adaptive rendering has shown to provide speed-up when used for off-line rendering it has not been utilized in IRT due to its naturally incoherent nature. In this paper, we combine adaptive rendering and interleaved sampling within a component-based solution into a new approach we term adaptive interleaved sampling. This allows us to tailor new adaptive heuristics for interleaved sampling of the individual components of the GI solution significantly improving overall performance. We present a novel component-based IGI framework for which we achieve interactive frame rates for a range of effects such as indirect diffuse lighting, soft shadows and single scatter homogeneous participating media.
A Framework for Interactive Hypertexture Modelling
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Gilet, G.; Dischler, J.M.
Hypertexturing can be a powerful way of adding rich geometric details to surfaces at low memory cost by using a procedural three-dimensional (3D) space distortion. However, this special kind of texturing technique still raises a major problem: the efficient control of the visual result. In this paper, we introduce a framework for interactive hypertexture modelling. This framework is based on two contributions. First, we propose a reformulation of the density modulation function. Our density modulation is based on the notion of shape transfer function. This function, which can be easily edited by users, allows us to control in an intuitive way the visual appearance of the geometric details resulting from the space distortion. Second, we propose to use a hybrid surface and volume-point-based representation in order to be able to dynamically hypertexture arbitrary objects at interactive frame rates. The rendering consists in a combined splat- and raycasting-based direct volume rendering technique. The splats are used to model the volumetric object while raycasting allows us to add the details. An experimental study on users shows that our approach improves the design of hypertextures and yet preserves their procedural nature.
GPU Rendering of Relief Mapped Conical Frusta
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Bhagvat, D.; Jeschke, S.; Cline, D.; Wonka, P.
This paper proposes to use relief-mapped conical frusta (cones cut by planes) to skin skeletal objects. Based on this representation, current programmable graphics hardware can perform the rendering with only minimal communication between the CPU and GPU. A consistent definition of conical frusta including texture parametrization and a continuous surface normal is provided. Rendering is performed by analytical ray casting of the relief-mapped frusta directly on the GPU. We demonstrate both static and animated objects rendered using our technique and compare to polygonal renderings of similar quality.
GIzMOs: Genuine Image Mosaics with Adaptive Tiling
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Pavic, D.; Ceumern, U.; Kobbelt, L.
We present a method that splits an input image into a set of tiles. Each tile is then replaced by another image from a large database such that, when viewed from a distance, the original image is reproduced as well as possible. While the general concept of image mosaics is not new, we consider our results as genuine image mosaics (or short GIzMOs) in the sense that the images from the database are not modified in any way. This is different from previous work, where the image tiles are usually colour shifted or overlaid with the high-frequency content of the input image. Besides the regular alignment of the tiles we propose a greedy approach for adaptive tiling where larger tiles are placed in homogenous image regions. By this we avoid the visual periodicity, which is induced by the equal spacing of the image tiles in the completely regular setting. Our overall system addresses also the cleaning of the image database by removing all unwanted images with no meaningful content. We apply differently sophisticated image descriptors to find the best matching image for each tile. For aesthetic and artistic reasons we classify each tile as feature or non-feature and then apply a suitable image descriptor. In a user study we have verified that our descriptors lead to mosaics that are significantly better recognizable than just taking, e.g. average colour values.
Robust and Efficient Surface Reconstruction From Range Data
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Labatut, P.; Pons, J.-P.; Keriven, R.
We describe a robust but simple algorithm to reconstruct a surface from a set of merged range scans. Our key contribution is the formulation of the surface reconstruction problem as an energy minimisation problem that explicitly models the scanning process. The adaptivity of the Delaunay triangulation is exploited by restricting the energy to inside/outside labelings of Delaunay tetrahedra. Our energy measures both the output surface quality and how well the surface agrees with soft visibility constraints. Such energy is shown to perfectly fit into the minimum s - t cuts optimisation framework, allowing fast computation of a globally optimal tetrahedra labeling, while avoiding the shrinking bias that usually plagues graph cuts methods.The behaviour of our method confronted to noise, undersampling and outliers is evaluated on several data sets and compared with other methods through different experiments: its strong robustness would make our method practical not only for reconstruction from range data but also from typically more difficult dense point clouds, resulting for instance from stereo image matching. Our effective modeling of the surface acquisition inverse problem, along with the unique combination of Delaunay triangulation and minimum s - t cuts, makes the computational requirements of the algorithm scale well with respect to the size of the input point cloud.
Wipe-Off: An Intuitive Interface for Exploring Ultra-Large Multi-Spectral Data Sets for Cultural Heritage Diagnostics
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Ponto, K.; Seracini, M.; Kuester, F.
A visual analytics technique for the intuitive, hands-on analysis of massive, multi-dimensional and multi-variate data is presented. This multi-touch-based technique introduces a set of metaphors such as wiping, scratching, sandblasting, squeezing and drilling, which allow for rapid analysis of global and local characteristics in the data set, accounting for factors such as gesture size, pressure and speed. A case study is provided for the analysis of multi-spectral image data of cultural artefacts. By aligning multi-spectral layers in a stack, users can apply different multi-touch metaphors to investigate features across different wavelengths. With this technique, flexibly definable regions can be interrogated concurrently without affecting surrounding data.
Erratum
(The Eurographics Association and Blackwell Publishing Ltd, 2009)
Instant Caching for Interactive Global Illumination
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Debattista, K.; Dubla, P.; Banterle, F.; Santos, L.P.; Chalmers, A.
The ability to interactively render dynamic scenes with global illumination is one of the main challenges in computer graphics. The improvement in performance of interactive ray tracing brought about by significant advances in hardware and careful exploitation of coherence has rendered the potential of interactive global illumination a reality. However, the simulation of complex light transport phenomena, such as diffuse interreflections, is still quite costly to compute in real time. In this paper we present a caching scheme, termed Instant Caching, based on a combination of irradiance caching and instant radiosity. By reutilising calculations from neighbouring computations this results in a speedup over previous instant radiosity-based approaches. Additionally, temporal coherence is exploited by identifying which computations have been invalidated due to geometric transformations and updating only those paths. The exploitation of spatial and temporal coherence allows us to achieve superior frame rates for interactive global illumination within dynamic scenes, without any precomputation or quality loss when compared to previous methods; handling of lighting and material changes are also demonstrated.
Semi-Uniform Adaptive Patch Tessellation
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Dyken, C.; Reimers, M.; Seland, J.
We present an adaptive tessellation scheme for surfaces consisting of parametric patches. The resulting tessellations are topologically uniform, yet consistent and watertight across boundaries of patches with different tessellation levels. Our scheme is simple to implement, requires little memory and is well suited for instancing, a feature available on current Graphical Processing Units that allows a substantial performance increase. We describe how the scheme can be implemented efficiently and give performance benchmarks comparing it to some other approaches.
Interactive Fibre Structure Visualization of the Heart
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Peeters, T. H. J. M.; Vilanova, A.; Romeny, B. M. ter Haar
The heart consists of densely packed muscle fibres. The orientation of these fibres can be acquired by using Diffusion Tensor Imaging (DTI) ex vivo. A good way to visualize the fibre structure in a cross section of the heart is by showing short line segments originating from the cross section and aligned with the local direction of the fibres. If the line segments are placed dense enough, one can see how the fibre orientations change. However, generation of the line segments takes time and thus the user has to wait for new geometry to be generated when the plane defining the cross section is changed. We present a new direct rendering method for the visualization of the 3D vector field in a 2D user-definable cross section of a heart. On the intersection of the plane with the vector field, the full 3D vectors are rendered as 3D line segments with a local ray casting approach. No preprocessing of the data is needed and no geometry is generated. This technique allows a fast inspection of the data to identify interesting areas where further analysis is necessary (e.g. quantification or generation of streamlines). We also show how the technique is generalized to other glyph shapes than line segments by implementing ellipsoids.
Tactics-Based Behavioural Planning for Goal-Driven Rigid Body Control
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Zickler, Stefan; Veloso, Manuela
Controlling rigid body dynamic simulations can pose a difficult challenge when constraints exist on the bodies goal states and the sequence of intermediate states in the resulting animation. Manually adjusting individual rigid body control actions (forces and torques) can become a very labour-intensive and non-trivial task, especially if the domain includes a large number of bodies or if it requires complicated chains of inter-body collisions to achieve the desired goal state. Furthermore, there are some interactive applications that rely on rigid body models where no control guidance by a human animator can be offered at runtime, such as video games.In this work, we present techniques to automatically generate intelligent control actions for rigid body simulations. We introduce sampling-based motion planning methods that allow us to model goal-driven behaviour through the use of non-deterministic Tactics that consist of intelligent, sampling-based control-blocks, called Skills. We introduce and compare two variations of a Tactics-driven planning algorithm, namely behavioural Kinodynamic Rapidly Exploring Random Trees (BK-RRT) and Behavioural Kinodynamic Balanced Growth Trees (BK-BGT). We show how our planner can be applied to automatically compute the control sequences for challenging physics-based domains and that is scalable to solve control problems involving several hundred interacting bodies, each carrying unique goal constraints.
Interactive Graphics for Computer Adaptive Testing
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Cheng, I.; Basu, A.
Interactive graphics are commonly used in games and have been shown to be successful in attracting the general audience. Instead of computer games, animations, cartoons, and videos being used only for entertainment, there is now an interest in using interactive graphics for innovative testing . Rather than traditional pen-and-paper tests, audio, video and graphics are being conceived as alternative means for more effective testing in the future. In this paper, we review some examples of graphics item types for testing. As well, we outline how games can be used to interactively test concepts; discuss designing chemistry item types with interactive 3D graphics; suggest approaches for automatically adjusting difficulty level in interactive graphics based questions; and propose strategies for giving partial marks for incorrect answers. We study how to test different cognitive skills, such as music, using multimedia interfaces; and also evaluate the effectiveness of our model. Methods for estimating difficulty level of a mathematical item type using Item Response Theory (IRT) and a molecule construction item type using Graph Edit Distance are discussed. Evaluation of the graphics item types through extensive testing on some students is described. We also outline the application of using interactive graphics over cell phones. All of the graphics item types used in this paper are developed by members of our research group.
Fast Inverse Reflector Design (FIRD)
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Mas, A.; Martin, I.; Patow, G.
This paper presents a new inverse reflector design method using a GPU-based computation of outgoing light distribution from reflectors. We propose a fast method to obtain the outgoing light distribution of a parametrized reflector, and then compare it with the desired illumination. The new method works completely in the GPU. We trace millions of rays using a hierarchical height-field representation of the reflector. Multiple reflections are taken into account. The parameters that define the reflector shape are optimized in an iterative procedure in order for the resulting light distribution to be as close as possible to the desired, user-provided one. We show that our method can calculate reflector lighting at least one order of magnitude faster than previous methods, even with millions of rays, complex geometries and light sources.
Robust and Optimized Algorithms for the Point-in-Polygon Inclusion Test without Pre-processing
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Jimenez, J. J.; Feito, F. R.; Segura, R. J.
In this work we present new point inclusion algorithms for non-convex polygons. These algorithms do not perform any pre-processing or any type of decomposition nor features classification, which makes them especially suitable for deformable or moving polygons. The algorithms are more accurate and robust than others in the sense that they consider the inclusion of the point in the vertices and edges of the polygon, and deal with the special cases correctly. In order to perform this inclusion test efficiently, they use the sign of the barycentric coordinates of the test point with regard to the triangles formed by the edges and an origin that depends on the test point. This set of triangles, which is a special simplicial covering of the polygon, is constructed after a transformation of the polygon that simplifies the calculations involved in the inclusion test. Then, an appropriate ordering of the rejection tests allows us to optimize this method. Our algorithms have been tested for robustness and compared with ray-crossing methods, showing a significant improvement.
A Bayesian Monte Carlo Approach to Global Illumination
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Brouillat, Jonathan; Bouville, Christian; Loos, Brad; Hansen, Charles; Bouatouch, Kadi
Most Monte Carlo rendering algorithms rely on importance sampling to reduce the variance of estimates. Importance sampling is efficient when the proposal sample distribution is well-suited to the form of the integrand but fails otherwise. The main reason is that the sample location information is not exploited. All sample values are given the same importance regardless of their proximity to one another. Two samples falling in a similar location will have equal importance whereas they are likely to contain redundant information. The Bayesian approach we propose in this paper uses both the location and value of the data to infer an integral value based on a prior probabilistic model of the integrand. The Bayesian estimate depends only on the sample values and locations, and not how these samples have been chosen. We show how this theory can be applied to the final gathering problem and present results that clearly demonstrate the benefits of Bayesian Monte Carlo.
Semi-Supervised Learning in Reconstructed Manifold Space for 3D Caricature Generation
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Liu, Junfa; Chen, Yiqiang; Miao, Chunyan; Xie, Jinjing; Ling, Charles X.; Gao, Xingyu; Gao, Wen
Recently, automatic 3D caricature generation has attracted much attention from both the research community and the game industry. Machine learning has been proven effective in the automatic generation of caricatures. However, the lack of 3D caricature samples makes it challenging to train a good model. This paper addresses this problem by two steps. First, the training set is enlarged by reconstructing 3D caricatures. We reconstruct 3D caricatures based on some 2D caricature samples with a Principal Component Analysis (PCA)-based method. Secondly, between the 2D real faces and the enlarged 3D caricatures, a regressive model is learnt by the semi-supervised manifold regularization (MR) method. We then predict 3D caricatures for 2D real faces with the learnt model. The experiments show that our novel approach synthesizes the 3D caricature more effectively than traditional methods. Moreover, our system has been applied successfully in a massive multi-user educational game to provide human-like avatars.
Replica Exchange Light Transport
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Kitaoka, Shinya; Kitamura, Yoshifumi; Kishino, Fumio
We solve the light transport problem by introducing a novel unbiased Monte Carlo algorithm called replica exchange light transport, inspired by the replica exchange Monte Carlo method in the fields of computational physics and statistical information processing. The replica exchange Monte Carlo method is a sampling technique whose operation resembles simulated annealing in optimization algorithms using a set of sampling distributions. We apply it to the solution of light transport integration by extending the probability density function of an integrand of the integration to a set of distributions. That set of distributions is composed of combinations of the path densities of different path generation types: uniform distributions in the integral domain, explicit and implicit paths in light (particle/photon) tracing, indirect paths in bidirectional path tracing, explicit and implicit paths in path tracing, and implicit caustics paths seen through specular surfaces including the delta function in path tracing. The replica-exchange light transport algorithm generates a sequence of path samples from each distribution and samples the simultaneous distribution of those distributions as a stationary distribution by using the Markov chain Monte Carlo method. Then the algorithm combines the obtained path samples from each distribution using multiple importance sampling. We compare the images generated with our algorithm to those generated with bidirectional path tracing and Metropolis light transport based on the primary sample space. Our proposing algorithm has better convergence property than bidirectional path tracing and the Metropolis light transport, and it is easy to implement by extending the Metropolis light transport.
Interactive Pixel-Accurate Free Viewpoint Rendering from Images with Silhouette Aware Sampling
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Hornung, A.; Kobbelt, L.
We present an integrated, fully GPU-based processing pipeline to interactively render new views of arbitrary scenes from calibrated but otherwise unstructured input views. In a two-step procedure, our method first generates for each input view a dense proxy of the scene using a new multi-view stereo formulation. Each scene proxy consists of a structured cloud of feature aware particles which automatically have their image space footprints aligned to depth discontinuities of the scene geometry and hence effectively handle sharp object boundaries and occlusions. We propose a particle optimization routine combined with a special parameterization of the view space that enables an efficient proxy generation as well as robust and intuitive filter operators for noise and outlier removal. Moreover, our generic proxy generation allows us to flexibly handle scene complexities ranging from small objects up to complete outdoor scenes. The second phase of the algorithm combines these particle clouds in real-time into a view-dependent proxy for the desired output view and performs a pixel-accurate accumulation of the colour contributions from each available input view. This makes it possible to reconstruct even fine-scale view-dependent illumination effects. We demonstrate how all these processing stages of the pipeline can be implemented entirely on the GPU with memory efficient, scalable data structures for maximum performance. This allows us to generate new output renderings of high visual quality from input images in real-time.
A Shape Grammar for Developing Glyph-based Visualizations
(The Eurographics Association and Blackwell Publishing Ltd, 2009) Karnick, P.; Jeschke, S.; Cline, D.; Razdan, A.; Wentz, E.; Wonka, P.
In this paper we address the question of how to quickly model glyph-based Geographic Information System visualizations. Our solution is based on using shape grammars to set up the different aspects of a visualization, including the geometric content of the visualization, methods for resolving layout conflicts and interaction methods. Our approach significantly increases modelling efficiency over similarly flexible systems currently in use.

Browse

Browsing 28-Issue 8 by Issue Date

Results Per Page

Sort Options