Abstract Real‐time rendering of dynamic line sets is relevant in many visualization tasks, including unsteady flow visualization and interactive white matter reconstruction from Magnetic Resonance Imaging. High‐quality global illumination and transparency are important for conveying the spatial structure of dense line sets, yet remain difficult to achieve at interactive rates. We propose an efficient voxel‐based ray‐tracing framework for rendering large dynamic line sets with ambient occlusion and ground‐truth transparency. We introduce a voxelization algorithm that supports efficient on‐the‐fly construction of acceleration structures for both voxel cone tracing and ray tracing. To further reduce per‐frame preprocessing cost, we propose a voxel‐based culling method that restricts acceleration structure construction to camera‐visible voxels. Together, these contributions enable real‐time rendering of large‐scale dynamic line sets with high quality and physically accurate transparency. We demonstrate that our method outperforms the state of the art in quality and performance when rendering (semi‐)opaque dynamic line sets.

Abstract The estimation of object orientation from RGB images is a core component in many modern computer vision pipelines. Traditional techniques mostly predict a single orientation per image, learning a one-to-one mapping between images and rotations. However, when objects exhibit rotational symmetries, they can appear identical from multiple viewpoints. This induces ambiguity in the estimation problem, making images map to rotations in a one-to-many fashion. In this paper, we explore several ways of addressing this problem. In doing so, we specifically consider algorithms that can map an image to a range of multiple rotation estimates, accounting for symmetry-induced ambiguity. Our contributions are threefold. Firstly, we create a data set with annotated symmetry information that covers symmetries induced through self-occlusion. Secondly, we compare and evaluate various learning strategies for multiple-hypothesis prediction models applied to orientation estimation. Finally, we propose to model orientation estimation as a binary classification problem. To this end, based on existing work from the field of shape reconstruction, we design a neural network that can be sampled to reconstruct the full range of ambiguous rotations for a given image. Quantitative evaluation on our annotated data set demonstrates its performance and motivates our design choices.

Abstract Efficiently simulating the full range of light effects in arbitrary input scenes that contain participating media is a difficult task. Unified points, beams and paths (UPBP) is an algorithm capable of capturing a wide range of media effects, by combining bidirectional path tracing (BPT) and photon density estimation (PDE) with multiple importance sampling (MIS). A computationally expensive task of UPBP is the MIS weight computation, performed each time a light path is formed. We derive an efficient algorithm to compute the MIS weights for UPBP, which improves over previous work by eliminating the need to iterate over the path vertices. We achieve this by maintaining recursive quantities as subpaths are generated, from which the subpath weights can be computed. In this way, the full path weight can be computed by only using the data cached at the two vertices at the ends of the subpaths. Furthermore, a costly part of PDE is the search for nearby photon points and beams. Previous work has shown that a spatial data structure for photon mapping can be implemented using the hardware‐accelerated bounding volume hierarchy of NVIDIA's RTX GPUs. We show that the same technique can be applied to different types of volumetric PDE and compare the performance of these data structures with the state of the art. Finally, using our new algorithm and data structures we fully implement UPBP on the GPU which we, to the best of our knowledge, are the first to do so.

Abstract Phase‐Contrast Magnetic Resonance Imaging (PC‐MRI) surpasses all other imaging methods in quality and completeness for measuring time‐varying volumetric blood flows and has shown potential to improve both diagnosis and risk assessment of cardiovascular diseases. However, like any measurement of physical phenomena, the data are prone to noise, artefacts and has a limited resolution. Therefore, PC‐MRI data itself do not fulfil physics fluid laws making it difficult to distinguish important flow features. For data analysis, physically plausible and high‐resolution data are required. Computational fluid dynamics provides high‐resolution physically plausible flows. However, the flow is inherently coupled to the underlying anatomy and boundary conditions, which are difficult or sometimes even impossible to adequately model with current techniques. We present a novel methodology using data assimilation techniques for PC‐MRI noise and artefact removal, generating physically plausible flow close to the measured data. It also allows us to increase the spatial and temporal resolution. To avoid sensitivity to the anatomical model, we consider and update the full 3D velocity field. We demonstrate our approach using phantom data with various amounts of induced noise and show that we can improve the data while preserving important flow features, without the need of a highly detailed model of the anatomy.

Simulating (elastically) deformable models that can collide with each other and with the environment remains a challenging task. The resulting contact problems can be elegantly approached using Lagrange multipliers to represent the unknown magnitude of the response forces. Typical methods construct and solve a Linear Complementarity Problem (LCP) to obtain the response forces. This requires the inverse of the generalized mass matrix, which is generally hard to obtain for deformable-body problems. In this article, we tackle such contact problems by directly solving the Mixed Linear Complementarity Problem (MLCP) and omitting the construction of an LCP matrix. Since a convex quadratic program with linear constraints is equivalent to an MLCP, we propose to use a Conjugate Residual (CR) solver as the backbone of our collision response system. By dynamically updating the set of active constraints, the MLCP with inequality constraints can be solved efficiently. We also propose a simple yet efficient preconditioner that ensures faster convergence. Finally, our approach is faster than existing methods (at the same accuracy), and it allows accurate treatment of friction.

Computing skeletons of 2D shapes, and medial surface and curve skeletons of 3D shapes, is a challenging task. In particular, there is no unified framework that detects all types of skeletons using a single model, and also produces a multiscale representation which allows to progressively simplify, or regularize, all skeleton types. In this paper, we present such a framework. We model skeleton detection and regularization by a conservative mass transport process from a shape's boundary to its surface skeleton, next to its curve skeleton, and finally to the shape center. The resulting density field can be thresholded to obtain a multiscale representation of progressively simplified surface, or curve, skeletons. We detail a numerical implementation of our framework which is demonstrably stable and has high computational efficiency. We demonstrate our framework on several complex 2D and 3D shapes.

Medial representations have been widely used for many shape analysis and processing tasks. Large and complex 3D shapes are, in this context, a challenging case. Recently, several methods have been proposed that extract point-based medial surfaces with high accuracy and computational scalability. However, the resulting medial clouds are of limited use for shape processing due to the difficulty of computing refined medial features from such clouds. In this paper, we show how to bridge the gap between having a raw medial cloud and enriching this cloud with feature points, medial-point classification, medial axis decomposition into sheets, robust regularization, and Y-network extraction. We further show how such properties can be used to support several shape processing sample applications including edge detection and shape segmentation, for a wide range of complex 3D shapes.

Magnetic resonance diffusion tensor imaging (DTI) measures diffusion of water molecules and is used to characterize orientation of white matter fibers and connectivity of neurological structures. Segmentation and visualization of DT images is challenging, because of low data quality and complexity of anatomical structures. In this paper, we propose an interactive segmentation approach, based on a hierarchical representation of the input DT image through a tree structure. The tree is obtained by successively merging watershed regions, based on the morphological waterfall approach, hence the name watershed tree. Region merging is done according to a combined similarity and homogeneity criterion. We introduce filters that work on the proposed tree representation, and that enable region-based attribute filtering of DTI data. Linked views between the visualizations of the simplified DT image and the tree enable a user to visually explore both data and tree at interactive rates. The coupling of filtering, semiautomatic segmentation by labeling nodes in the tree, and various interaction mechanisms support the segmentation task. Our method is robust against noise, which we demonstrate on synthetic and real DTI data.

Abstract Modern MRI measurements deliver volumetric and time‐varying blood‐flow data of unprecedented quality. Visual analysis of these data potentially leads to a better diagnosis and risk assessment of various cardiovascular diseases. Recent advances have improved the speed and quality of the imaging data considerably. Nevertheless, the data remains compromised by noise and a lack of spatiotemporal resolution. Besides imaging data, also numerical simulations are employed. These are based on mathematical models of specific features of physical reality. However, these models require realistic parameters and boundary conditions based on measurements. We propose to use data assimilation to bring measured data and physically‐based simulation together, and to harness the mutual benefits. The accuracy and noise robustness of the coupled approach is validated using an analytic flow field. Furthermore, we present a comparative visualization that conveys the differences between using conventional interpolation and our coupled approach.

Abstract We present a method for extracting complex manifolds with an arbitrary number of (self‐) intersections from unoriented point clouds containing large amounts of noise. Manifolds are formed in a three‐step process. First, small flat neighbourhoods of all possible orientations are created around all points. Next, neighbourhoods are assembled into larger quasi‐flat patches, whose overlaps give the global connectivity structure of the point cloud. Finally, curved manifolds are extracted from the patch connectivity graph via a multiple‐source flood fill. The manifolds can be reconstructed into meshed surfaces using standard existing surface reconstruction methods. We demonstrate the speed and robustness of our method on several point clouds, with applications in point cloud segmentation, denoising and medial surface reconstruction.

We present a GPU-based framework for extracting surface and curve skeletons of 3D shapes represented as large polygonal meshes. We use an efficient parallel search strategy to compute point-cloud skeletons and their distance and feature transforms (FTs) with user-defined precision. We regularize skeletons by a new GPU-based geodesic tracing technique which is orders of magnitude faster and more accurate than comparable techniques. We reconstruct the input surface from skeleton clouds using a fast and accurate image-based method. We also show how to reconstruct the skeletal manifold structure as a polygon mesh and the curve skeleton as a polyline. Compared to recent skeletonization methods, our approach offers two orders of magnitude speed-up, high-precision, and low-memory footprints. We demonstrate our framework on several complex 3D models.

The level-set method is one of the most popular techniques for capturing and tracking deformable interfaces. Although level sets have demonstrated great potential in visualization and computer graphics applications, such as surface editing and physically based modeling, their use for interactive simulations has been limited due to the high computational demands involved. In this paper, we address this computational challenge by leveraging the increased computing power of graphics processors, to achieve fast simulations based on level sets. Our efficient, sparse GPU level-set method is substantially faster than other state-of-the-art, parallel approaches on both CPU and GPU hardware. We further investigate its performance through a method for surface reconstruction, based on GPU level sets. Our novel multiresolution method for surface reconstruction from unorganized point clouds compares favorably with recent, existing techniques and other parallel implementations. Finally, we point out that both level-set computations and rendering of level-set surfaces can be performed at interactive rates, even on large volumetric grids. Therefore, many applications based on level sets can benefit from our sparse level-set method.

The Discrete Wavelet Transform (DWT) has a wide range of applications from signal processing to video and image compression. We show that this transform, by means of the lifting scheme, can be performed in a memory and computation-efficient way on modern, programmable GPUs, which can be regarded as massively parallel coprocessors through NVidia's CUDA compute paradigm. The three main hardware architectures for the 2D DWT (row-column, line-based, block-based) are shown to be unsuitable for a CUDA implementation. Our CUDA-specific design can be regarded as a hybrid method between the row-column and block-based methods. We achieve considerable speedups compared to an optimized CPU implementation and earlier non-CUDA-based GPU DWT methods, both for 2D images and 3D volume data. Additionally, memory usage can be reduced significantly compared to previous GPU DWT methods. The method is scalable and the fastest GPU implementation among the methods considered. A performance analysis shows that the results of our CUDA-specific design are in close agreement with our theoretical complexity analysis.

A physically motivated method for surface reconstruction is proposed that can recover smooth surfaces from noisy and sparse data sets. No orientation information is required. By a new technique based on regularized-membrane potentials the input sample points are aggregated, leading to improved noise tolerability and outlier removal, without sacrificing much with respect to detail (feature) recovery. After aggregating the sample points on a volumetric grid, a novel, iterative algorithm is used to classify grid points as exterior or interior to the surface. This algorithm relies on intrinsic properties of the smooth scalar field on the grid which emerges after the aggregation step. Second, a mesh-smoothing paradigm based on a mass-spring system is introduced. By enhancing this system with a bending-energy minimizing term we ensure that the final triangulated surface is smoother than piecewise linear. In terms of speed and flexibility, the method compares favorably with respect to previous approaches. Most parts of the method are implemented on modern graphics processing units (GPUs). Results in a wide variety of settings are presented, ranging from surface reconstruction on noise-free point clouds to grayscale image segmentation.

This paper is concerned with a multiresolution representation for maximum intensity projection (MIP) volume rendering based on morphological pyramids which allows progressive refinement. We consider two algorithms for progressive rendering from the morphological pyramid: one which projects detail coefficients level by level, and a second one, called streaming MIP, which resorts the detail coefficients of all levels simultaneously with respect to decreasing magnitude of a suitable error measure. The latter method outperforms the level-by-level method, both with respect to image quality with a fixed amount of detail data, and in terms of flexibility of controlling approximation error or computation time. We improve the streaming MIP algorithm, present a GPU implementation for both methods, and perform a comparison with existing CPU and GPU implementations.

We propose a novel, geometrically adaptive method for surface reconstruction from noisy and sparse point clouds, without orientation information. The method employs a fast convection algorithm to attract the evolving surface towards the data points. The force field in which the surface is convected is based on generalized Coulomb potentials evaluated on an adaptive grid (i.e., an octree) using a fast, hierarchical algorithm. Formulating reconstruction as a convection problem in a velocity field generated by Coulomb potentials offers a number of advantages. Unlike methods which compute the distance from the data set to the implicit surface, which are sensitive to noise due to the very reliance on the distance transform, our method is highly resilient to shot noise since global, generalized Coulomb potentials can be used to disregard the presence of outliers due to noise. Coulomb potentials represent long-range interactions that consider all data points at once, and thus they convey global information which is crucial in the fitting process. Both the spatial and temporal complexities of our spatially-adaptive method are proportional to the size of the reconstructed object, which makes our method compare favorably with respect to previous approaches in terms of speed and flexibility. Experiments with sparse as well as noisy data sets show that the method is capable of delivering crisp and detailed yet smooth surfaces.

We present a novel, physically-motivated method for surface reconstruction that can recover smooth surfaces from noisy and sparse data sets, without using orientation information. A new volumetric technique based on regularized-membrane potentials for aggregating the input sample points is introduced, which manages improved noise tolerability and outlier removal, without sacrificing much with respect to detail (feature) recovery. In this method, sample points are first aggregated on a volumetric grid. A labeling algorithm that relies on intrinsic properties of the smooth scalar field emerging after aggregation is used to classify grid points as exterior or interior to the surface. We also introduce a mesh-smoothing paradigm based on a mass-spring system, enhanced with a bending-energy minimizing term to ensure that the final triangulated surface is smoother than piecewise linear. The method compares favorably with respect to previous approaches in terms of speed and flexibility.

A multiscale, morphological method for the purpose of shape-based object recognition is presented. A connected operator similar to the morphological hat-transform is defined, and two scale-space representations are built, using the curvature function as the underlying one-dimensional signal. Each peak and valley of the curvature is extracted and described by its maximum and average heights and by its extent and represents an entry in the top or bottom hat-transform scale spaces. We demonstrate object recognition based on hat-transform scale spaces for three large data sets, a set of diatom contours, the set of silhouettes from the MPEG-7 database and the set of two-dimensional views of three-dimensional objects from the COIL-20 database. Our approach outperforms other methods for which comparative results exist.

A novel, physically motivated deformable model for shape recovery and segmentation is presented. The model, referred to as the charged-particle model (CPM), is inspired by classical electrodynamics and is based on a simulation of charged particles moving in an electrostatic field. The charges are attracted towards the contours of the objects of interest by an electrostatic field, whose sources are computed based on the gradient-magnitude image. The electric field plays the same role as the potential forces in the snake model, while internal interactions are modeled by repulsive Coulomb forces. We demonstrate the flexibility and potential of the model in a wide variety of settings: shape recovery using manual initialization, automatic segmentation, and skeleton computation. We perform a comparative analysis of the proposed model with the active contour model and show that specific problems of the latter are surmounted by our model. The model is easily extendable to 3D and copes well with noisy images.

In this paper we present a multiscale morphological method for use in texture classification. A connected operator similar to the morphological hat-transform is defined, and two scale-space representations are built. The most important features are extracted from the scale spaces by unsupervised cluster analysis, and the resulting pattern vectors provide the input of a decision tree classifier. We obtain 93.5 % correct classification for the Brodatz texture database.