9 results
Search Results
Now showing 1 - 9 of 9
Item Massively Parallel Batch Neural Gas for Bounding Volume Hierarchy Construction(The Eurographics Association, 2014) Weller, René; Mainzer, David; Srinivas, Abhishek; Teschner, Matthias; Zachmann, Gabriel; Jan Bender and Christian Duriez and Fabrice Jaillet and Gabriel ZachmannOrdinary bounding volume hierarchy (BVH) construction algorithms create BVHs that approximate the boundary of the objects. In this paper, we present a BVH construction that instead approximates the volume of the objects with successively finer levels. It is based on Batch Neural Gas (BNG), a clustering algorithm that is known from machine learning. Additionally, we present a novel massively parallel version of this BNG-based hierarchy construction that runs completely on the GPU. It reduces the theoretical complexity of the sequential algorithm from O(nlogn) to O(log2 n) and also our CUDA implementation outperforms the CPU version significantly in practice.Item GPU Collision Detection in Conformal Geometric Space(The Eurographics Association, 2021) Roa, Eduardo; Theoktisto, Víctor; Fairén, Marta; Navazo, Isabel; Silva, F. and Gutierrez, D. and Rodríguez, J. and Figueiredo, M.We derive a conformal algebra treatment unifying all types of collisions among points, vectors, areas (defined by bivectors and trivectors) and 3D solid objects (defined by trivectors and quadvectors), based in a reformulation of collision queries from R3 to conformal R4,1 space. The algebraic formulation in this 5D space is then implemented in GPU to allow faster parallel computation queries. Results show expected orders of magnitude improvements computing collisions among known mesh models, allowing interactive rates without using optimizations and bounding volume hierarchies.Item Streaming Approach to In Situ Selection of Key Time Steps for Time-Varying Volume Data(The Eurographics Association and John Wiley & Sons Ltd., 2022) Wu, Mengxi; Chiang, Yi-Jen; Musco, Christopher; Borgo, Rita; Marai, G. Elisabeta; Schreck, TobiasKey time steps selection, i.e., selecting a subset of most representative time steps, is essential for effective and efficient scientific visualization of large time-varying volume data. In particular, as computer simulations continue to grow in size and complexity, they often generate output that exceeds both the available storage capacity and bandwidth for transferring results to storage, making it indispensable to save only a subset of time steps. At the same time, this subset must be chosen so that it is highly representative, to facilitate post-processing and reconstruction with high fidelity. The key time steps selection problem is especially challenging in the in situ setting, where we can only process data in one pass in an online streaming fashion, using a small amount of main memory and fast computation. In this paper, we formulate the problem as that of optimal piece-wise linear interpolation. We first apply a method from numerical linear algebra to compute linear interpolation solutions and their errors in an online streaming fashion. Using that method as a building block, we can obtain a global optimal solution for the piece-wise linear interpolation problem via a standard dynamic programming (DP) algorithm. However, this approach needs to process the time steps in multiple passes and is too slow for the in situ setting. To address this issue, we introduce a novel approximation algorithm, which processes time steps in one pass in an online streaming fashion, with very efficient computing time and main memory space both in theory and in practice. The algorithm is suitable for the in situ setting. Moreover, we prove that our algorithm, which is based on a greedy update rule, has strong theoretical guarantees on the approximation quality and the number of time steps stored. To the best of our knowledge, this is the first algorithm suitable for in situ key time steps selection with such theoretical guarantees, and is the main contribution of this paper. Experiments demonstrate the efficacy of our new techniques.Item Location-dependent Generalization of Road Networks Based on Equivalent Destinations(The Eurographics Association and John Wiley & Sons Ltd., 2016) Dijk, Thomas C. van; Haunert, Jan-Henrik; Oehrlein, Johannes; Kwan-Liu Ma and Giuseppe Santucci and Jarke van WijkSuppose a user located at a certain vertex in a road network wants to plan a route using a wayfinding map. The user's exact destination may be irrelevant for planning most of the route, because many destinations will be equivalent in the sense that they allow the user to choose almost the same paths. We propose a method to find such groups of destinations automatically and to contract the resulting clusters in a detailed map to achieve a simplified visualization. We model the problem as a clustering problem in rooted, edge-weighted trees. Two vertices are allowed to be in the same cluster if and only if they share at least a given fraction of their path to the root. We analyze some properties of these clusterings and give a linear-time algorithm to compute the minimum-cardinality clustering. This algorithm may have various other applications in network visualization and graph drawing, but in this paper we apply it specifically to focus-and-context map generalization. When contracting shortestpath trees in a geographic network, the computed clustering additionally provides a constant-factor bound on the detour that results from routing using the generalized network instead of the full network. This is a desirable property for wayfinding maps.Item Using K-Means Clustering for a Spatial Analysis of Multivariate and Time-Varying Microclimate Data(The Eurographics Association, 2013) Häb, Kathrin; Middel, Ariane; Hagen, Hans; O. Kolditz and K. Rink and G. ScheuermannIn this study, we propose a k-means clustering algorithm combined with glyph-based encoding method to analyze the spatial distribution and dependence of multivariate, time-varying 3D microclimate data. We obtained five climate variables, i.e. air and surface temperature, specific humidity, direct shortwave radiation and sensible heat flux, from an ENVI-met R simulation of a residential neighborhood in Phoenix, AZ. In a preprocessing step, we aggregated the 3D gridded simulation data by adding up value differences between two consecutive time steps for each grid cell over the entire simulation time to get a highly compressed view of the data without losing the spatial context. K-means clustering was then conducted in coordinate space by weighting each grid cell based on its difference to the spatial mean of temporal value differences. To reduce occlusion and to encode additional cluster member information, the visualization focused on the k-means cluster centroids. Resulting images show that the applied technique is suitable to provide a first insight into the spatial relationship of features based on their temporal variability.Item Visual Analysis of Confocal Raman Spectroscopy Data using Cascaded Transfer Function Design(The Eurographics Association and John Wiley & Sons Ltd., 2017) Schikora, Christoph Markus; Plack, Markus; Bornemann, Rainer; Bolívar, Peter Haring; Kolb, Andreas; Heer, Jeffrey and Ropinski, Timo and van Wijk, Jarke2D Confocal Raman Microscopy (CRM) data consist of high dimensional per-pixel spectral data of 1000 bands and allows for complex spectral and spatial-spectral analysis tasks, i.e., in material discrimination, material thickness, and spatial material distributions. Currently, simple integral methods are commonly applied as visual analysis solutions to CRM data which exhibit restricted discrimination power in various regards. In this paper we present a novel approach for the visual analysis of 2D multispectral CRM data using multi-variate visualization techniques. Due to the large amount of data and the demand of an explorative approach without a-priori restriction, our system allows for arbitrary interactive (de)selection of varaibles w/o limitation and an unrestricted online definition/construction of new, combined properties. Our approach integrates CRM specific quantitative measures and handles material-related features for mixed materials in a quantitative manner. Technically, we realize the online definition/construction of new, combined properties as semi-automatic, cascaded, 1D and 2D multidimensional transfer functions (MD-TFs). By interactively incorporating new (raw or derived) properties, the dimensionality of the MD-TF space grows during the exploration procedure and is virtually unlimited. The final visualization is achieved by an enhanced color mixing step which improves saturation and contrast.Item Towards a Taxonomy for Display Processors(The Eurographics Association, 1989) Schneider, Bengt-Olaf; Richard Grimsdale and Wolfgang StrasserImage generation for raster displays proceeds in two main steps: geometry processing and pixel processing. The snbsystem performing the pixel processing is called display processor.In the paper a model for the displa.y processor is developed that takes into account both function and timing properties. The model identifies scan conversion, hidden surface removal, shading and anti-aliasing as tile key functions of the display processor. The timing model is expressed in an inequation being fundamental for all display processor architectures.On the basis of that model a taxonomy is presented which classifies display processors according to four main criteria: function, partitioning, a.rchitecture and performance.The taxonomy is applied to five real display processors: Pixel-planes, SLAM, PROOF, the Ray-Casting Machine and the Structured Frame Store System.Investigation of existing display processor architectures on the basis of the devel oped taxonomy revealed a potential new architecture. This architecture partitions the image generation process ill image space and employs a. tree topology.Item Vector Field k-Means: Clustering Trajectories by Fitting Multiple Vector Fields(The Eurographics Association and Blackwell Publishing Ltd., 2013) Ferreira, Nivan; Klosowski, James T.; Scheidegger, Carlos E.; Silva, Cláudio T.; B. Preim, P. Rheingans, and H. TheiselScientists study trajectory data to understand trends in movement patterns, such as human mobility for traffic analysis and urban planning. In this paper, we introduce a novel trajectory clustering technique whose central idea is to use vector fields to induce a notion of similarity between trajectories, letting the vector fields themselves define and represent each cluster. We present an efficient algorithm to find a locally optimal clustering of trajectories into vector fields, and demonstrate how vector-field k-means can find patterns missed by previous methods. We present experimental evidence of its effectiveness and efficiency using several datasets, including historical hurricane data, GPS tracks of people and vehicles, and anonymous cellular radio handoffs from a large service provider.Item Content-Addressable Memories for Quadtree-8ased Images(The Eurographics Association, 1988) Oldfield, J.V.; Williams, R.D.; Wiseman, N.E.; Brûlé, M.R.; A. A. M.KuijkQuadtrees are attractive for storing and processing mages with area coherence, but performance has been limited by software overheads. A Content-Addressable Memory (CAM) with ternary storage allows single-cycle searches by pixel coordinate, quadrant or rectangle. To use thiS feature effectively the authors have reviewed a range of quadtree processing functions relevant to computer graphics and Image processing, and some new algorithms have been discovere. The proposed VLSI chip has microcoded logic on each row, as well as its CAM cells. This architecture has been simulated in fine detail with the aid of the Connection Machine as well as by much slower, conventional computers. The combination of quadtrees and CAMs offers significant improvement in performance for display systems and image processing.