NURBS surfaces are compact parametric representations widely used in Computer-Aided Design (CAD) modeling. Decomposing raw 3D data measurements into a set of such elements is a challenging problem that existing methods approach by learning from CAD databases to both segment synthetic data and fit parametric shapes on each segment. Unfortunately, these methods generalize poorly to raw data measurements, with low robustness to imperfect data and complex objects and low scalability. To address this issue, we propose NURBSFIT, an algorithm that fits NURBS surfaces to unorganized 3D point clouds, such as those generated by laser and photogrammetry acquisition systems. Starting with a fine configuration of planar patches that approximate the object geometry, our algorithm performs merging operations that progressively regroup pairs of adjacent patches into fewer, more expressive NURBS surfaces. This process is designed to be both robust and performant with a series of technical ingredients that include an energy that controls the global quality of a configuration of NURBS surfaces and an efficient ordering of the merging operations based on a cost-efficient quadric surface fitting analysis. We show the potential of our algorithm on both synthetic and real-world data and its efficiency against existing primitive fitting methods with results both simpler and geometrically more accurate. Our implementation is available at: https://github.com/lizOnly/nurbsfit

Abstract Visualizing large‐scale, time‐varying volumetric data using direct volume rendering remains a significant challenge in scientific visualization, particularly as data sizes and resolutions continue to increase. One promising direction for addressing this challenge is the use of tensor decompositions, which have proven to be a useful tool for the compact representation of large, high‐dimensional data. However, their integration into time‐dependent interactive visualization pipelines remains limited. We introduce TT4D, a memory‐ and time‐efficient lossy compression and decompression technique for four‐dimensional (4D) time‐varying volume data based on the tensor train (TT) decomposition. Our approach employs efficient subsampling during decomposition to reduce memory consumption and computational cost, enabling the processing of large datasets while avoiding unnecessarily large intermediate matrices and tensors. Beyond compression, TT4D provides a GPU‐based, on‐the‐fly decoding scheme that avoids reconstructing the entire 4D volume, supporting interactive visualization. At equivalent error levels, TT4D outperforms other transform‐based compressors at random‐access decompression across datasets up to 64GB. Exploiting the structure of TT cores, our approach enables adaptive multiresolution rendering, fast spatio‐temporal data exploration, and interactive filtering. Together, these capabilities make TT4D a scalable solution for interactive visualization of high‐resolution, time‐varying volume data.

Automated floor plan generation aims to create residential layouts by arranging rooms within a given boundary, balancing topological, geometric, and aesthetic considerations. The existing methods typically use a multi-step pipeline with intermediate representations to decompose the prediction process into several sub-tasks, limiting model flexibility and imposing predefined solution paths. This often results in unreasonable outputs when applied to data unsuitable for these predefined paths, making it challenging for these methods to match human designers, who do not restrict themselves to a specific set of design workflows. To address these limitations, we introduce CE2EPlan, a controllable end-to-end topology- and geometry-enhanced diffusion model that removes restrictions on the generative process of AI design tools. Instead, it enables the model to learn how to design floor plans directly from data, capturing a wide range of solution paths from input boundaries to complete layouts. Extensive experiments demonstrate that our method surpasses all existing approaches using the multi-step pipeline, delivering higher-quality results with enhanced user control and greater diversity in output, bringing AI design tools closer to the versatility of human designers.

The boundary-constrained floor plan generation problem aims to generate the topological and geometric properties of a set of rooms within a given boundary. Recently, learning-based methods have made significant progress in generating realistic floor plans. However, these methods involve a workflow of converting vector data into raster images, using image-based generative models, and then converting the results back into vector data. This process is complex and redundant, often resulting in information loss. Raster images, unlike vector data, cannot scale without losing detail and precision. To address these issues, we propose a novel deep learning framework called DiffPlanner for boundary-constrained floor plan generation, which operates entirely in vector space. Our framework is a Transformer-based conditional diffusion model that integrates an alignment mechanism in training, aligning the optimization trajectory of the model with the iterative design processes of designers. This enables our model to handle complex vector data, better fit the distribution of the predicted targets, accomplish the challenging task of floor plan layout design, and achieve user-controllable generation. We conduct quantitative comparisons, qualitative evaluations, ablation experiments, and perceptual studies to evaluate our method. Extensive experiments demonstrate that DiffPlanner surpasses existing state-of-the-art methods in generating floor plans and bubble diagrams in the creative stages, offering more controllability to users and producing higher-quality results that closely match the ground truths.

Abstract 3D surface reconstruction from point clouds is a key step in areas such as content creation, archaeology, digital cultural heritage and engineering. Current approaches either try to optimize a non‐data‐driven surface representation to fit the points, or learn a data‐driven prior over the distribution of commonly occurring surfaces and how they correlate with potentially noisy point clouds. Data‐driven methods enable robust handling of noise and typically either focus on a global or a local prior, which trade‐off between robustness to noise on the global end and surface detail preservation on the local end. We propose PPSurf as a method that combines a global prior based on point convolutions and a local prior based on processing local point cloud patches. We show that this approach is robust to noise while recovering surface details more accurately than the current state‐of‐the‐art. Our source code, pre‐trained model and dataset are available at https://github.com/cg‐tuwien/ppsurf .

Abstract Manufacturing a 3D object by folding from a 2D material is typically done in four steps: 3D surface approximation, unfolding the surface into a plane, printing and cutting the outline of the unfolded shape, and refolding it to a 3D object. Usually, these steps are treated separately from each other. In this work we jointly address the first two pipeline steps by allowing the 3D representation to smoothly change while unfolding. This way, we increase the chances to overcome possible ununfoldability issues. To join the two pipeline steps, our work proposes and combines different surface flows with a Tabu Unfolder. We empirically investigate the effects that different surface flows have on the performance as well as on the quality of the unfoldings. Additionally, we demonstrate the ability to solve cases by approximation which comparable algorithms either have to segment or can not solve at all.

Abstract Displaying polygonal vector data is essential in various application scenarios such as geometry visualization, vector graphics rendering, CAD drawing and in particular geographic, or cartographic visualization. Dealing with static polygonal datasets that has a large scale and are highly detailed poses several challenges to the efficient and adaptive display of polygons in interactive geographic visualization applications. For linear vector data, only recently a GPU‐based level‐of‐detail (LOD) polyline simplification and rendering approach has been presented which can perform locally‐adaptive LOD visualization of large‐scale line datasets interactively. However, locally optimized LOD simplification and interactive display of large‐scale polygon data, consisting of filled vector line loops, remains still a challenge, specifically in 3D geographic visualizations where varying LOD over a scene is necessary. Our solution to this challenge is a novel technique for locally‐optimized simplification and visualization of 2D polygons over a 3D terrain which features a parallelized point‐inside‐polygon testing mechanism. Our approach is capable of employing any simplification algorithm that sequentially removes vertices such as Douglas‐Peucker and Wang‐Müller. Moreover, we generalized our technique to also visualizing polylines in order to have a unified method for displaying both data types. The results and performance analysis show that our new algorithm can handle large datasets containing polygons composed of millions of segments in real time, and has a lower memory demand and higher performance in comparison to prior methods of line simplification and visualization.

Abstract Analyzing the evolution of thunderstorms is critical in determining the potential for the development of severe weather events. Existing visualization systems for short‐term weather forecasting (nowcasting) allow for basic analysis and prediction of storm developments. However, they lack advanced visual features for efficient decision‐making. We developed a visual analytics tool for the detection of hazardous thunderstorms and their characterization, using a visual design centered on a reformulated expert task workflow that includes visual features to overview storms and quickly identify high‐impact weather events, a novel storm graph visualization to inspect and analyze the storm structure, as well as a set of interactive views for efficient identification of similar storm cells (known as analogs) in historical data and their use for nowcasting. Our tool was designed with and evaluated by meteorologists and expert forecasters working in short‐term operational weather forecasting of severe weather events. Results show that our solution suits the forecasters' workflow. Our visual design is expressive, easy to use, and effective for prompt analysis and quick decision‐making in the context of short‐range operational weather forecasting.

Abstract Recent years have seen a proliferation of new digital products for the efficient management of indoor spaces, with important applications like emergency management, virtual property showcasing and interior design. While highly innovative and effective, these products rely on accurate 3D models of the environments considered, including information on both architectural and non‐permanent elements. These models must be created from measured data such as RGB‐D images or 3D point clouds, whose capture and consolidation involves lengthy data workflows. This strongly limits the rate at which 3D models can be produced, preventing the adoption of many digital services for indoor space management. We provide a radical alternative to such data‐intensive procedures by presentingWalk2Map, a data‐driven approach to generate floor plans only from trajectories of a person walking inside the rooms. Thanks to recent advances in data‐driven inertial odometry, such minimalistic input data can be acquired from the IMU readings of consumer‐level smartphones, which allows for an effortless and scalable mapping of real‐world indoor spaces. Our work is based on learning the latent relation between an indoor walk trajectory and the information represented in a floor plan: interior space footprint, portals, and furniture. We distinguish between recovering area‐related (interior footprint, furniture) and wall‐related (doors) information and use two different neural architectures for the two tasks: an image‐based Encoder‐Decoder and a Graph Convolutional Network, respectively. We train our networks using scanned 3D indoor models and apply them in a cascaded fashion on an indoor walk trajectory at inference time. We perform a qualitative and quantitative evaluation using both trajectories simulated from scanned models of interiors and measured, real‐world trajectories, and compare against a baseline method for image‐to‐image translation. The experiments confirm that our technique is viable and allows recovering reliable floor plans from minimal walk trajectory data.

Abstract Sobol's method is one of the most powerful and widely used frameworks for global sensitivity analysis, and it maps every possible combination of input variables to an associated Sobol index. However, these indices are often challenging to analyze in depth, due in part to the lack of suitable, flexible enough, and fast‐to‐query data access structures as well as visualization techniques. We propose a visualization tool that leverages tensor decomposition, a compressed data format that can quickly and approximately answer sophisticated queries over exponential‐sized sets of Sobol indices. This way, we are able to capture the complete global sensitivity information of high‐dimensional scalar models. Our application is based on a three‐stage visualization, to which variables to be analyzed can be added or removed interactively. It includes a novel hourglass‐like diagram presenting the relative importance for any single variable or combination of input variables with respect to any composition of the rest of the input variables. We showcase our visualization with a range of example models, whereby we demonstrate the high expressive power and analytical capability made possible with the proposed method.

Abstract Visualization of large vector line data is a core task in geographic and cartographic systems. Vector maps are often displayed at different cartographic generalization levels, traditionally by using several discrete levels‐of‐detail (LODs). This limits the generalization levels to a fixed and predefined set of LODs, and generally does not support smooth LOD transitions. However, fast GPUs and novel line rendering techniques can be exploited to integrate dynamic vector map LOD management into GPU‐based algorithms for locally‐adaptive line simplification and real‐time rendering. We propose a new technique that interactively visualizes large line vector datasets at variable LODs. It is based on the Douglas‐Peucker line simplification principle, generating an exhaustive set of line segments whose specific subsets represent the lines at any variable LOD. At run time, an appropriate and view‐dependent error metric supports screen‐space adaptive LOD levels and the display of the correct subset of line segments accordingly. Our implementation shows that we can simplify and display large line datasets interactively. We can successfully apply line style patterns, dynamic LOD selection lenses, and anti‐aliasing techniques to our line rendering.

Abstract Creating high‐level structured 3D models of real‐world indoor scenes from captured data is a fundamental task which has important applications in many fields. Given the complexity and variability of interior environments and the need to cope with noisy and partial captured data, many open research problems remain, despite the substantial progress made in the past decade. In this survey, we provide an up‐to‐date integrative view of the field, bridging complementary views coming from computer graphics and computer vision. After providing a characterization of input sources, we define the structure of output models and the priors exploited to bridge the gap between imperfect sources and desired output. We then identify and discuss the main components of a structured reconstruction pipeline, and review how they are combined in scalable solutions working at the building level. We finally point out relevant research issues and analyze research trends.

Memory and network bandwidth are decisive bottlenecks when handling high-resolution multidimensional data sets in visualization applications, and they increasingly demand suitable data compression strategies. We introduce a novel lossy compression algorithm for multidimensional data over regular grids. It leverages the higher-order singular value decomposition (HOSVD), a generalization of the SVD to three dimensions and higher, together with bit-plane, run-length and arithmetic coding to compress the HOSVD transform coefficients. Our scheme degrades the data particularly smoothly and achieves lower mean squared error than other state-of-the-art algorithms at low-to-medium bit rates, as it is required in data archiving and management for visualization purposes. Further advantages of the proposed algorithm include very fine bit rate selection granularity and the ability to manipulate data at very small cost in the compression domain, for example to reconstruct filtered and/or subsampled versions of all (or selected parts) of the data set.

Developing complex, real world graphics applications which leverage multiple GPUs and computers for interactive 3D rendering tasks is a complex task. It requires expertise in distributed systems and parallel rendering in addition to the application domain itself. We present a mature parallel rendering framework which provides a large set of features, algorithms and system integration for a wide range of real-world research and industry applications. Using the Equalizer parallel rendering framework, we show how a wide set of generic algorithms can be integrated in the framework to help application scalability and development in many different domains, highlighting how concrete applications benefit from the diverse aspects and use cases of Equalizer. We present novel parallel rendering algorithms, powerful abstractions for large visualization setups and virtual reality, as well as new experimental results for parallel rendering and data distribution.

Abstract While color plays a fundamental role in film design and production, existing solutions for film analysis in the digital humanities address perceptual and spatial color information only tangentially. We introduce VIAN, a visual film annotation system centered on the semantic aspects of film color analysis. The tool enables expert‐assessed labeling, curation, visualization and Classification of color features based on their perceived context and aesthetic quality. It is the first of its kind that incorporates foreground‐background information made possible by modern deep learning segmentation methods. The proposed tool seamlessly integrates a multimedia data management system, so that films can undergo a full color‐oriented analysis pipeline.

Histograms are a fundamental tool for multidimensional data analysis and processing, and many applications in graphics and visualization rely on computing histograms over large regions of interest (ROI). Integral histograms (IH) greatly accelerate the calculation in the case of rectangular regions, but come at a large extra storage cost. Based on the tensor train decomposition model, we propose a new compression and approximate retrieval algorithm to reduce the overall IH memory usage by several orders of magnitude at a user-defined accuracy. To this end we propose an incremental tensor decomposition algorithm that allows us to compress integral histograms of hundreds of gigabytes. We then encode the borders of any desired rectangular ROI in the IH tensor-compressed domain and reconstruct the target histogram at a high speed which is independent of the region size. We furthermore generalize the algorithm to support regions of arbitrary shape rather than only rectangles, as well as histogram field computation, i.e., recovering many histograms at once. We test our method with several multidimensional data sets and demonstrate that it radically speeds up costly histogram queries while avoiding storing massive, uncompressed IHs.

Abstract Rendering 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 anti‐aliasing 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.

Typically, relief generation from an input 3D scene is limited to either bas-relief or high-relief modeling. This paper presents a novel unified scheme for synthesizing reliefs guided by the geometric texture richness of 3D scenes; it can generate both basand high-reliefs. The type of relief and compression coefficient can be specified according to the user’s artistic needs. We use an energy minimization function to obtain the surface reliefs, which contains a geometry preservation term and an edge constraint term. An edge relief measure determined by geometric texture richness and edge z -depth is utilized to achieve a balance between these two terms. During relief generation, the geometry preservation term keeps local surface detail in the original scenes, while the edge constraint term maintains regions of the original models with rich geometric texture. Elsewhere, in highreliefs, the edge constraint term also preserves depth discontinuities in the higher parts of the original scenes. The energy function can be discretized to obtain a sparse linear system. The reliefs are obtained by solving it by an iterative process. Finally, we apply non-linear compression to the relief to meet the user’s artistic needs. Experimental results show the method’s effectiveness for generating both bas- and high-reliefs for complex 3D scenes in a unified manner.

Signal processing and filter operations are important tools for visual data processing and analysis. Due to GPU memory and bandwidth limitations, it is challenging to apply complex filter operators to large-scale volume data interactively. We propose a novel and fast multiscale compression-domain volume filtering approach integrated into an interactive multiresolution volume visualization framework. In our approach, the raw volume data is decomposed offline into a compact hierarchical multiresolution tensor approximation model. We then demonstrate how convolution filter operators can effectively be applied in the compressed tensor approximation domain. To prevent aliasing due to multiresolution filtering, our solution (a) filters accurately at the full spatial volume resolution at a very low cost in the compressed domain, and (b) reconstructs and displays the filtered result at variable level-of-detail. The proposed system is scalable, allowing interactive display and filtering of large volume datasets that may exceed the available GPU memory. The desired filter kernel mask and size can be modified online, producing immediate visual results.

Abstract Reconstructing the as‐built architectural shape of building interiors has emerged in recent years as an important and challenging research problem. An effective approach must be able to faithfully capture the architectural structures and separate permanent components from clutter (e.g. furniture), while at the same time dealing with defects in the input data. For many applications, higher‐level information on the environment is also required, in particular the shape of individual rooms. To solve this ill‐posed problem, state‐of‐the‐art methods assume constrained input environments with a 2.5D or, more restrictively, a Manhattan‐world structure, which significantly restricts their applicability in real‐world settings. We present a novel pipeline that allows to reconstruct general 3D interior architectures, significantly increasing the range of real‐world architectures that can be reconstructed and labeled by any interior reconstruction method to date. Our method finds candidate permanent components by reasoning on a graph‐based scene representation, then uses them to build a 3D linear cell complex that is partitioned into separate rooms through a multi‐label energy minimization formulation. We demonstrate the effectiveness of our method by applying it to a variety of real‐world and synthetic datasets and by comparing it to more specialized state‐of‐the‐art approaches.

Terrain rendering is widely used in industry and research. GIS software packages as well as 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 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 geospatial information as well as new methods which could be used to address these challenges.

We propose a new method to fill missing or invalid values in depth images generated from the Kinect depth sensor. To fill the missing depth values, we use a robust least median of squares (LMedS) approach. We apply our method for telepresence environments, where Kinects are used very often for reconstructing the captured scene in 3D. We introduce a modified 1D LMedS approach for efficient traversal of consecutive image frames. Our approach solves the unstable nature of depth values in static scenes that is perceived as flickering. We obtain very good result both for static and moving objects inside a scene.

Abstract We propose a new technique for in‐core and out‐of‐core GPU ray tracing using a generalization of hierarchical occlusion culling in the style of the CHC++ method. Our method exploits the rasterization pipeline and hardware occlusion queries in order to create coherent batches of work for localized shader‐based ray tracing kernels. By combining hierarchies in both ray space and object space, the method is able to share intermediate traversal results among multiple rays. We exploit temporal coherence among similar ray sets between frames and also within the given frame. A suitable management of the current visibility state makes it possible to benefit from occlusion culling for less coherent ray types like diffuse reflections. Since large scenes are still a challenge for modern GPU ray tracers, our method is most useful for scenes with medium to high complexity, especially since our method inherently supports ray tracing highly complex scenes that do not fit in GPU memory. For in‐core scenes our method is comparable to CUDA ray tracing and performs up to5.94× better than pure shader‐based ray tracing.

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 can be created in an intuitive manner. Using 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 construction curves. In order to provide more freedom for controlling the local geometric features of the reconstructed free-form shapes (e.g., non-circular cross-sections), our modeling system creates each shape component from four construction curves. Using 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 is progressively created, and is represented by 3D triangular mesh. Experimental results illustrate that our system can generate complex symmetric free-form shapes effectively and conveniently.

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.

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

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

With better and faster acquisition devices comes a demand for fast robust reconstruction algorithms, but no L 1 -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.

Abstract Interactive visual analysis of large and complex volume datasets is an ongoing and challenging problem. We tackle this challenge in the context of state‐of‐the‐art out‐of‐core multiresolution volume rendering by introducing a novel hierarchical tensor approximation (TA) volume visualization approach. The TA framework allows us (a) to use a rank‐truncated basis for compact volume representation, (b) to visualize features at multiple scales, and (c) to visualize the data at multiple resolutions. In this paper, we exploit the special properties of the TA factor matrix bases and define a novel multiscale and multiresolution volume rendering hierarchy. Different from previous approaches, to represent one volume dataset we use but one set of global bases (TA factor matrices) to reconstruct at all resolution levels and feature scales. In particular, we propose a coupling of multiscalable feature visualization and multiresolution DVR through the properties of global TA bases. We demonstrate our novel TA multiresolution hierarchy based volume representation and visualization on a number of μCT volume datasets.

The articles in this special section contain selected papers from the Eurographics Symposium on Parallel Graphics and Visualization (EGPGV).

Direct volume rendering has become a popular method for visualizing volumetric datasets. Even though computers are continually getting faster, it remains a challenge to incorporate sophisticated illumination models into direct volume rendering while maintaining interactive frame rates. In this paper, we present a novel approach for advanced illumination in direct volume rendering based on GPU ray-casting. Our approach features directional soft shadows taking scattering into account, ambient occlusion and color bleeding effects while achieving very competitive frame rates. In particular, multiple dynamic lights and interactive transfer function changes are fully supported. Commonly, direct volume rendering is based on a very simplified discrete version of the original volume rendering integral, including the development of the original exponential extinction into a-blending. In contrast to a-blending forming a product when sampling along a ray, the original exponential extinction coefficient is an integral and its discretization a Riemann sum. The fact that it is a sum can cleverly be exploited to implement volume lighting effects, i.e. soft directional shadows, ambient occlusion and color bleeding. We will show how this can be achieved and how it can be implemented on the GPU.

Large scale and structurally complex volume datasets from high-resolution 3D imaging devices or computational simulations pose a number of technical challenges for interactive visual analysis. In this paper, we present the first integration of a multiscale volume representation based on tensor approximation within a GPU-accelerated out-of-core multiresolution rendering framework. Specific contributions include (a) a hierarchical brick-tensor decomposition approach for pre-processing large volume data, (b) a GPU accelerated tensor reconstruction implementation exploiting CUDA capabilities, and (c) an effective tensor-specific quantization strategy for reducing data transfer bandwidth and out-of-core memory footprint. Our multiscale representation allows for the extraction, analysis and display of structural features at variable spatial scales, while adaptive level-of-detail rendering methods make it possible to interactively explore large datasets within a constrained memory footprint. The quality and performance of our prototype system is evaluated on large structurally complex datasets, including gigabyte-sized micro-tomographic volumes.

Shape simplification and re-sampling of underlying point-sampled surfaces under user-defined error bounds is an important and challenging issue. Based on the regular triangulation of the Gaussian sphere and the surface normals mapping onto the Gaussian sphere, a Gaussian sphere based re-sampling scheme is presented that generates a non-uniformly curvature-aware simplification of the given point-sampled model. Owing to the theoretical analysis of shape isophotic error metric for did that Gaussian sphere based sampling, the proposed simplification scheme provides a convenient way to control the re-sampling results under a user-specified error metric bound. The novel algorithm has been implemented and demonstrated on several examples.

We present a novel, incompressible fluid simulation method based on the Lagrangian Smoothed Particle Hydrodynamics (SPH) model. In our method, incompressibility is enforced by using a prediction-correction scheme to determine the particle pressures. For this, the information about density fluctuations is actively propagated through the fluid and pressure values are updated until the targeted density is satisfied. With this approach, we avoid the computational expenses of solving a pressure Poisson equation, while still being able to use large time steps in the simulation. The achieved results show that our predictive-corrective incompressible SPH (PCISPH) method clearly outperforms the commonly used weakly compressible SPH (WCSPH) model by more than an order of magnitude while the computations are in good agreement with the WCSPH results.

Continuing improvements in CPU and GPU performances as well as increasing multi-core processor and cluster-based parallelism demand for flexible and scalable parallel rendering solutions that can exploit multipipe hardware accelerated graphics. In fact, to achieve interactive visualization, scalable rendering systems are essential to cope with the rapid growth of data sets. However, parallel rendering systems are non-trivial to develop and often only application specific implementations have been proposed. The task of developing a scalable parallel rendering framework is even more difficult if it should be generic to support various types of data and visualization applications, and at the same time work efficiently on a cluster with distributed graphics cards. In this paper we introduce a novel system called Equalizer, a toolkit for scalable parallel rendering based on OpenGL which provides an application programming interface (API) to develop scalable graphics applications for a wide range of systems ranging from large distributed visualization clusters and multi-processor multipipe graphics systems to single-processor single-pipe desktop machines. We describe the system architecture, the basic API, discuss its advantages over previous approaches, present example configurations and usage scenarios as well as scalability results.

This course instructs students in the software and hardware strategies needed for real-time visualization and interaction with massive models. Seven international researchers and practitioners are the instructors. The general form of the course will be lecture with live demos.

Abstract We present a new method for the simulation of melting and solidification in a unified particle model. Our technique uses the Smoothed Particle Hydrodynamics (SPH) method for the simulation of liquids, deformable as well as rigid objects, which eliminates the need to define an interface for coupling different models. Using this approach, it is possible to simulate fluids and solids by only changing the attribute values of the underlying particles. We significantly changed a prior elastic particle model to achieve a flexible model for melting and solidification. By using an SPH approach and considering a new definition of a local reference shape, the simulation of merging and splitting of different objects, as may be caused by phase change processes, is made possible. In order to keep the system stable even in regions represented by a sparse set of particles we use a special kernel function for solidification processes. Additionally, we propose a surface reconstruction technique based on considering the movement of the center of mass to reduce rendering errors in concave regions. The results demonstrate new interaction effects concerning the melting and solidification of material, even while being surrounded by liquids. Copyright © 2007 John Wiley & Sons, Ltd.

Representing a triangulated two manifold using a single triangle strip is an NP-complete problem. By introducing a few Steiner vertices, recent works find such a single-strip and hence a linear ordering of edge-connected triangles of the entire triangulation. In this paper, we highlight and exploit this linear order in efficient triangle-strip management for high-performance rendering. We present new algorithms to generate weighted single-strip representations that respect different constraint-based clustering of triangles. These functional constraints can be application dependent; for example, normal-based constraints for efficient visibility culling or spatial constraints for highly coherent vertex-caching. We also present a hierarchical single-strip-management strategy for high-performance interactive 3D rendering.

With the growing size of captured 3D models it has become increasingly important to provide basic efficient processing methods for large unorganized raw surface-sample point data sets. In this paper we introduce a novel stream-based (and out-of-core) point processing framework. The proposed approach processes points in an orderly sequential way by sorting them and sweeping along a spatial dimension. The major advantages of this new concept are: (1) support of extensible and concatenate local operators called stream operators, (2) low main-memory usage and (3) applicability to process very large data sets out-of-core.

In this paper we explore the algorithmic space in which stripification, simplification and geometric compression of triangulated 2-manifolds overlap. Edge-collapse/uncollapse based geometric simplification algorithms develop a hierarchy of collapses such that during uncollapse the reverse order has to be maintained. We show that restricting the simplification and refinement operations only to, what we call, the collapsible edges creates hierarchyless simplification in which the operations on one edge can be performed independent of those on another. Although only a restricted set of edges is used for simplification operations, we prove topological results to show that, with minor retriangulation, any triangulated 2-manifold can be reduced to either a single vertex or a single edge using the hierarchyless simplification, resulting in extreme simplification. The set of collapsible edges helps us analyze and relate the similarities between simplification, stripification and geometric compression algorithms. We show that the maximal set of collapsible edges implicitly describes a triangle strip representation of the original model. Further, these strips can be effortlessly maintained on multiresolution models obtained through any sequence of hierarchyless simplifications on these collapsible edges. Due to natural relationship between stripification and geometric compression, these multi-resolution models can also be efficiently compressed using traditional compression algorithms. We present algorithms to find the maximal set of collapsible edges and to reorganize these edges to get the minimum number of connected components of these edges. An order-independent simplification and refinement of these edges is achieved by our novel data structure and we show the results of our implementation of view-dependent, dynamic, hierarchyless simplification. We maintain a single triangle strip across all multi-resolution models created by the view-dependent simplification process. We present a new algorithm to compress the models using the triangle strips implicitly defined by the collapsible edges.

Although there is a remarkable pace in the advance of computational resources and storage for real-time visualization the immensity of the input data continues to outstrip any advances. The task for interactively visualizing such a massive terrain is to render a triangulated mesh using a view-dependent error tolerance, thus intelligently and perceptually managing the scene’s geometric complexity. At any particular instance in time (i.e. displayed frame), this level-of-detail (LOD) terrain surface consists of a mesh composed of hundreds of thousands of dynamically selected triangles. The triangles are selected using the current time-step’s view parameters and the view-dependent error tolerance. Massive terrain data easily exceeds main memory storage capacity such that out-of-core rendering must be performed. This further complicates the triangle selection and terrain rendering owing to tertiary storage’s relatively poor performance.

In this paper, we present an efficient (topology preserving) multiresolution meshing framework for interactive level-of-detail (LOD) generation and rendering of large triangle meshes. More specifically, the presented approach, called FastMesh, provides view-dependent LOD generation and real-time mesh simplification that minimizes visual artifacts. Multiresolution triangle mesh representations are an important tool for reducing triangle mesh complexity in interactive rendering environments. Ideally, for interactive visualization, a triangle mesh is simplified to the maximal tolerated visible error and, thus, mesh simplification is view-dependent. This paper introduces an efficient hierarchical multiresolution triangulation framework based on a half-edge triangle mesh data structure and presents optimized implementations of several view-dependent or visual mesh simplification heuristics within that framework. Despite being optimized for performance, these error heuristics provide conservative error bounds. The presented framework is highly efficient both in space and time cost and needs only a fraction of the time required for rendering to perform the error calculations and dynamic mesh updates.

In this paper, we present Confetti, a novel point-based rendering approach based on object-space point interpolation of densely sampled surfaces. We introduce the concept of a transformation-invariant covariance matrix of a set of points which can efficiently be used to determine splat sizes in a multiresolution point hierarchy. We also analyze continuous point interpolation in object-space and we define a new class of parameterized blending kernels as well as a normalization procedure to achieve smooth blending. Furthermore, we present a hardware accelerated rendering algorithm based on texture mapping and alpha-blending as well as programmable vertex and pixel-shaders.

DStrips is a simple and efficient method to dynamically manage and generate triangle trips for real-time view dependent multiresolution meshing and rendering. Progressive view-dependent triangle mesh simplification and rendering is an important concept for interactive visualization environments. To minimize the rendering cost, triangle meshes are simplified to the maximal tolerated perceptual error. A further savings can be gained by using hardware optimized rendering primitives such as triangle strips. However, triangle strips have been rarely used successfully in interactive multiresolution meshes due to the costs involved with maintaining the coherency of the strips n the changing mesh. This paper introduces a new dynamic triangle stripping data structure and algorithm. DStrips, that is practical for use with multiresolution meshes. DStrips is aimed at preserving pre-computed triangle strips through changes in the mesh and generating reasonably good triangle strips in real-time. Furthermore, this data structure and algorithm can be easily adapted to any multiresolution mesh which has a face-to-edge/edge-to-face mapping. The presented approach is implemented on top of a real-time view-dependent meshing and rendering framework based on a half-edge data structure using progressive edge collapses and vertex splits. Direct comparisons are made to previous methods in triangle stripification of dynamic and static meshes.

We present a novel point-based rendering approach based on object-space point interpolation. We introduce the concept of a transformation-invariant covariance matrix of a set of points to efficiently determine splat sizes in a multiresolution hierarchy. We analyze continuous point interpolation in object-space, and define a new class of parametrized blending kernels to achieve smooth blending. Furthermore, we present a hardware accelerated rendering algorithm based on α-texture mapping and α-blending.

We present a novel disk-based multiresolution triangle mesh data structure that supports paging and view-dependent rendering of very large meshes at interactive frame rates from external memory. Our approach, called XFastMesh, is based on a view-dependent mesh simplification framework that represents half-edge collapse operations in a binary hierarchy known as a merge-tree forest. The proposed technique partitions the merge-tree forest into so-called detail blocks, which consist of binary subtrees, that are stored on disk. We present an efficient external memory data structure and file format that stores all detail information of the multiresolution triangulation method using significantly less storage then previously reported approaches. Furthermore, we present a paging algorithm that provides efficient loading and interactive rendering of large meshes from external memory at varying and view-dependent level-of-detail. The presented approach is highly efficient both in terms of space cost and paging performance.

Interactive visualization of large digital elevation models is of continuing interest in scientific visualization, GIS, and virtual reality applications. Taking advantage of the regular structure of grid digital elevation models, efficient hierarchical multiresolution triangulation and adaptive level-of-detail (LOD) rendering algorithms have been developed for interactive terrain visualization. Despite the higher triangle count, these approaches generally outperform mesh simplification methods that produce irregular triangulated network (TIN) based LOD representations. In this project we combine the advantage of a TIN based mesh simplification preprocess with high-performance quadtree based LOD triangulation and rendering at run-time. This approach, called QuadTIN, generates an efficient quadtree triangulation hierarchy over any irregular point set that may originate from irregular terrain sampling or from reducing oversampling in high-resolution grid digital elevation models.

The article presents an optimized view-dependent meshing framework for adaptive and continuous level-of-detail (LOD) rendering in real-time. Multiresolution triangle mesh representations are an important tool for adapting triangle mesh complexity in real-time rendering environments. Ideally, for interactive visualization, a triangle mesh is simplified to the maximal tolerated perceptual error, and thus mesh simplification is view-dependent. The paper introduces an efficient hierarchical multiresolution triangulation framework based on a half-edge triangle mesh data structure, and presents an optimized computation of several view-dependent error metrics within that framework, providing conservative error bounds. The presented approach called FastMesh, is highly efficient both in space and time cost, and it spends only a fraction of the time required for rendering to perform the error calculations and dynamic mesh updates.

An ideal triangle mesh compression technology would simultaneously support the following objectives: (1) progressive refinements of the received mesh during decompression, (2) nearly optimal compression ratios for both geometry and connectivity, and (3) in-line, real-time decompression algorithms for hardware or software implementations. Because these three objectives impose contradictory constraints, previously reported efforts have focused primarily on one (sometimes two) of these objectives. The SQUEEZE technique introduced in this paper addresses all three constraints simultaneously, and attempts to provide the best possible compromise. For a mesh of T triangles, SQUEEZE compresses the connectivity to 3.7T bits, which is competitive with the best progressive compression techniques reported so far. The geometric prediction error encoding technique introduced in this paper leads to a geometry compression that is improved by 20% over that of previous schemes. Our initial implementation on a 300-MHz CPU achieved a decompression rate of up to 46,000 triangles per second. SQUEEZE downloads a model through a number of successive refinement stages, providing the benefit of progressivity.

Multiresolution methods are becoming increasingly important tools for the interactive visualization of very large data sets. Multiresolution isosurface visualization allows the user to explore volume data using simplified and coarse representations of the isosurface for overview images, and finer resolution in areas of high interest or when zooming into the data. Ideally, a coarse isosurface should have the same topological structure as the original. The topological genus of the isosurface is one important property which is often neglected in multiresolution algorithms. This results in uncontrolled topological changes which can occur whenever the level-of-detail is changed. The scope of this paper is to propose an efficient technique which allows preservation of topology as well as controlled topology simplification in multiresolution isosurface extraction.

The maintenance of large raster images under spatial operations is still a major performance bottleneck. For reasons of storage space, images in a collection, such as satellite pictures in geographic information systems, are maintained in compressed form. Instead of performing a spatially selective operation on an image by first decompressing the compressed version, we propose to perform queries directly on the compressed version of the image. We suggest a compression technique that allows for the subsequent use of a spatial index structure to guide a spatial search. In response to a window query, our algorithm delivers a compressed partial image, or the exact uncompressed requested image region. In addition to the support of spatial queries on compressed continuous tone images, the new compression algorithm is even competitive in terms of the compression ratio that it achieves, compared to other standard lossless compression techniques.

Most systems that support visual interaction with 3D models use shape representations based on triangle meshes. The size of these representations imposes limits on applications for which complex 3D models must be accessed remotely. Techniques for simplifying and compressing 3D models reduce the transmission time. Multiresolution formats provide quick access to a crude model and then refine it progressively. Unfortunately, compared to the best nonprogressive compression methods, previously proposed progressive refinement techniques impose a significant overhead when the full resolution model must be downloaded. The CPM (compressed progressive meshes) approach proposed here eliminates this overhead. It uses a new technique, which refines the topology of the mesh in batches, which each increase the number of vertices by up to 50 percent. Less than an amortized total of 4 bits per triangle encode where and how the topological refinements should be applied. We estimate the position of new vertices from the positions of their topological neighbors in the less refined mesh using a new estimator that leads to representations of vertex coordinates that are 50 percent more compact than previously reported progressive geometry compression techniques.

Irregular tetrahedral meshes, which are popular in many engineering and scientific applications, often contain a large number of vertices. A mesh of V vertices and T tetrahedra requires 48 V bits or less to store the vertex coordinates, 4/spl middot/T/spl middot/log/sub 2/(V) bits to store the tetrahedra-vertex incidence relations, also called connectivity information, and kV bits to store the k-bit value samples associated with the vertices. Given that T is 5 to 7 times larger than V and that V often exceeds 32/sup 3/, the storage space required for the connectivity is larger than 300 V bits and thus dominates the overall storage cost. Our "implants spray" compression approach introduced in the paper reduces this cost to about 30 V bits or less-a 10:1 compression ratio. Furthermore, implant spray supports the progressive refinement of a crude model through a series of vertex-splits operations.

Advocates a desktop virtual reality (VR) interface to a geographic information system (GIS). The navigational capability to explore large topographic scenes is a powerful metaphor and a natural way of interacting with a GIS. VR systems succeed in providing visual realism and real-time navigation and interaction, but fail to cope with very large amounts of data and to provide the general functionality of information systems. We suggest a way to overcome these problems. We describe a prototype system, called ViRGIS (Virtual Reality GIS), that integrates two system platforms: a client that runs the VR component interacts via a (local or wide area) network with a server that runs an object-oriented database containing geographic data. For the purpose of accessing data efficiently, we describe how to integrate a geometric index into the database, and how to perform the operations that are requested in a real-time trip through the virtual world.

Real-time rendering of triangulated surfaces has attracted growing interest in the last few years. However, interactive visualization of very large scale grid digital elevation models is still difficult. The graphics load must be controlled by adaptive surface triangulation and by taking advantage of different levels of detail. Furthermore, management of the visible scene requires efficient access to the terrain database. We describe an all-in-one visualization system which integrates adaptive triangulation, dynamic scene management and spatial data handling. The triangulation model is based on the restricted quadtree triangulation. Furthermore, we present new algorithms of restricted quadtree triangulation. These include among others exact error approximation, progressive meshing, performance enhancements and spatial access.