Discrete shading of three-dimensional objects from medial axis transform

In this paper, we present a discrete shading technique using medial axis transform (MAT) of 3D binary image data based on digital generalized octagonal distances. Our method is computationally attractive as it does not require the explicit computation of surface normals. We have compared our results with images rendered from voxel and octree representations while using analytical surface rendered images as bench marks. The quality of rendering by our method is certainly superior to those obtained from voxel and octree representations.     

A Symbolic Out-of-Core Solution Method for Markov Models

Despite considerable effort, the state-space explosion problem remains an issue in the analysis of Markov models. Given structure, symbolic representations can result in very compact encoding of the models. However, a major obstacle for symbolic methods is the need to store the probability vector(s) explicitly in main memory. In this paper, we present a novel algorithm which relaxes these memory limitations by storing the probability vector on disk. The algorithm has been implemented using an MTBDD-based data structure to store the matrix and an array to store the vector. We report on experimental results for two benchmark models, a Kanban manufacturing system and a flexible manufacturing system, with models as large as 133 million states.     

Memory‐Efficient Interactive Online Reconstruction From Depth Image Streams

We describe how the pipeline for 3D online reconstruction using commodity depth and image scanning hardware can be made scalable for large spatial extents and high scanning resolutions. Our modified pipeline requires less than 10% of the memory that is required by previous approaches at similar speed and resolution. To achieve this, we avoid storing a 3D distance field and weight map during online scene reconstruction. Instead, surface samples are binned into a high‐resolution binary voxel grid. This grid is used in combination with caching and deferred processing of depth images to reconstruct the scene geometry. For pose estimation, GPU ray‐casting is performed on the binary voxel grid. A one‐to‐one comparison to level‐set ray‐casting in a distance volume indicates slightly lower pose accuracy. To enable unlimited spatial extents and store acquired samples at the appropriate level of detail, we combine a hash map with a hierarchical tree representation.     

Capturing and rendering geometry details for BTF-mapped surfaces

Bidirectional texture functions, or BTFs, accurately model reflectance variation at a fine (meso-) scale as a function of lighting and viewing direction. BTFs also capture view-dependent visibility variation, also called masking or parallax, but only within surface contours. Mesostructure detail is neglected at silhouettes, so BTF-mapped objects retain the coarse shape of the underlying model. We augment BTF rendering to obtain approximate mesoscale silhouettes. Our new representation, the 4D mesostructure distance function (MDF), tabulates the displacement from a reference frame where a ray first intersects the mesoscale geometry beneath as a function of ray direction and ray position along that reference plane. Given an MDF, the mesostructure silhouette can be rendered with a per-pixel depth peeling process on graphics hardware, while shading and local parallax are handled by the BTF. Our approach allows real-time rendering, handles complex, non-height-field mesostructure, requires that no additional geometry be sent to the rasterizer other than the mesh triangles, is more compact than textured visibility representations used previously, and, for the first time, can be easily measured from physical samples. We also adapt the algorithm to capture detailed shadows cast both by and onto BTF-mapped surfaces. We demonstrate the efficiency of our algorithm on a variety of BTF data, including real data acquired using our BTF–MDF measurement system.     

Interactively Modifying Compressed Sparse Voxel Representations

Voxels are a popular choice to encode complex geometry. Their regularity makes updates easy and enables random retrieval of values. The main limitation lies in the poor scaling with respect to resolution. Sparse voxel DAGs (Directed Acyclic Graphs) overcome this hurdle and offer high-resolution representations for real-time rendering but only handle static data. We introduce a novel data structure to enable interactive modifications of such compressed voxel geometry without requiring de- and recompression. Besides binary data to encode geometry, it also supports compressed attributes (e.g., color). We illustrate the usefulness of our representation via an interactive large-scale voxel editor (supporting carving, filling, copying, and painting).     

Adaptive cell division for ray tracing

In ray tracing the two most commonly used data structures are the octree and uniform cell division. The octree structure allows efficient adaptive subdivision of space, while taking care of the spatial coherence of the objects in it; however, the tree structure locating the next node in the path of a ray is complex and time consuming. The cell structure, on the other hand, can be stored in a three-dimensional array, and each cell can be efficiently accessed by specifying three indices. However, such a uniform cell division does not take care of object coherence. The proposed data structure combines the positive features of the above data structures while minimising their disadvantages. The entire object space is implicitly assumed to be a three-dimensional grid of cells. Initially, the entire object space is a single voxel which later undergoes “adaptive cell division.” But, unlike in the octree structure, where each voxel is divided exactly at the middle of each dimension, in adaptive cell division, each voxel is divided at the nearest cell boundary. The result is that each voxel contains an integral number of cells along each axis. Corresponding to the implicit cell division we maintain a three-dimensional array, with each array element containing the voxel number which is used to index into the voxel array. The voxel array is used to store information about the structure of each voxel, in particular, the objects in each voxel. While a ray moves from one voxel to another we always keep track of the cell through which the ray is currently passing. Since only arrays are involved in accessing the next voxel in the path of the ray, the operation is very efficient.     

Procedural function-based modelling of volumetric microstructures

We propose a new approach to modelling heterogeneous objects containing internal volumetric structures with size of details orders of magnitude smaller than the overall size of the object. The proposed function-based procedural representation provides compact, precise, and arbitrarily parametrized models of coherent microstructures, which can undergo blending, deformations, and other geometric operations, and can be directly rendered and fabricated without generating any auxiliary representations (such as polygonal meshes and voxel arrays). In particular, modelling of regular lattices and cellular microstructures as well as irregular porous media is discussed and illustrated. We also present a method to estimate parameters of the given model by fitting it to microstructure data obtained with magnetic resonance imaging and other measurements of natural and artificial objects. Examples of rendering and digital fabrication of microstructure models are presented.     

Topological spines: a structure-preserving visual representation of scalar fields

We present topological spines--a new visual representation that preserves the topological and geometric structure of a scalar field. This representation encodes the spatial relationships of the extrema of a scalar field together with the local volume and nesting structure of the surrounding contours. Unlike other topological representations, such as contour trees, our approach preserves the local geometric structure of the scalar field, including structural cycles that are useful for exposing symmetries in the data. To obtain this representation, we describe a novel mechanism based on the extraction of extremum graphs--sparse subsets of the Morse-Smale complex that retain the important structural information without the clutter and occlusion problems that arise from visualizing the entire complex directly. Extremum graphs form a natural multiresolution structure that allows the user to suppress noise and enhance topological features via the specification of a persistence range. Applications of our approach include the visualization of 3D scalar fields without occlusion artifacts, and the exploratory analysis of high-dimensional functions.     

Sorted Deferred Shading for Production Path Tracing

Ray‐traced global illumination (GI) is becoming widespread in production rendering but incoherent secondary ray traversal limits practical rendering to scenes that fit in memory. Incoherent shading also leads to intractable performance with production‐scale textures forcing renderers to resort to caching of irradiance, radiosity, and other values to amortize expensive shading. Unfortunately, such caching strategies complicate artist workflow, are difficult to parallelize effectively, and contend for precious memory. Worse, these caches involve approximations that compromise quality. In this paper, we introduce a novel path‐tracing framework that avoids these tradeoffs. We sort large, potentially out‐of‐core ray batches to ensure coherence of ray traversal. We then defer shading of ray hits until we have sorted them, achieving perfectly coherent shading and avoiding the need for shading caches.     

Discrete ray tracing

Discrete ray tracing, or 3-D raster ray tracing (RRT), which, unlike existing ray tracing methods that use geometric representation for the 3-D scene employs a 3-D discrete raster of voxels for representing the 3-D scene in the same way a 2-D raster of pixels represents a 2-D image, is discussed. Each voxel is a small quantum unit of volume that has numeric values associated with it representing some measurable properties or attributes of the real object or phenomenon at that voxel. It is shown that RRT operates in two phases: preprocessing voxel and discrete ray tracing. In the voxel phase, the geometric model is digitized using 3-D scan-conversion algorithms that convert the continuous representation of the model into a discrete representation within the 3-D raster. In the second phase, RRT employs a discrete variation of the conventional recursive ray tracer in which 3-D discrete rays are traversed through the 3-D raster to find the first surface voxel. Encountering a nontransparent voxel indicates a ray-surface hit. Results obtained by running the RRT software one one 20-MIPS (25-GHz) processor of a Silicon Graphics 4D/240GTX are presented in terms of CPU time     

Geometry and Attribute Compression for Voxel Scenes

Voxel‐based approaches are today's standard to encode volume data. Recently, directed acyclic graphs (DAGs) were successfully used for compressing sparse voxel scenes as well, but they are restricted to a single bit of (geometry) information per voxel. We present a method to compress arbitrary data, such as colors, normals, or reflectance information. By decoupling geometry and voxel data via a novel mapping scheme, we are able to apply the DAG principle to encode the topology, while using a palette‐based compression for the voxel attributes, leading to a drastic memory reduction. Our method outperforms existing state‐of‐the‐art techniques and is well‐suited for GPU architectures. We achieve real‐time performance on commodity hardware for colored scenes with up to 17 hierarchical levels (a 128K³voxel resolution), which are stored fully in core.     

Global Illumination Using Well‐Separated Pair Decomposition

Instant radiosity methods rely on using a large number of virtual point lights (VPLs) to approximate global illumination. Efficiency considerations require grouping the VPLs into a small number of clusters that are treated as individual lights with respect to each point to be shaded. Two examples of clustering algorithms are Lightcuts [WFA*05] and LightSlice [OP11]. In this work, we use the notion of geometric separatedness of point sets as a basis for a data structure for pre‐computing and compactly storing a set of candidate VPL clusterings. Our data structure is created prior to rendering, is view‐independent and relies only on geometric and radiometric information. For any point to be shaded, we show that a suitable clustering of the VPLs can be efficiently extracted from this data structure. We develop the above framework into an accurate and efficient clustering algorithm based on well‐separated pair decompositions which outperforms earlier work in speed and/or quality for diffuse scenes.     

A Statistical Approach to Material Classification Using Image Patch Exemplars

In this paper, we investigate material classification from single images obtained under unknown viewpoint and illumination. It is demonstrated that materials can be classified using the joint distribution of intensity values over extremely compact neighborhoods (starting from as small as 3times3 pixels square) and that this can outperform classification using filter banks with large support. It is also shown that the performance of filter banks is inferior to that of image patches with equivalent neighborhoods. We develop novel texton-based representations which are suited to modeling this joint neighborhood distribution for Markov random fields. The representations are learned from training images and then used to classify novel images (with unknown viewpoint and lighting) into texture classes. Three such representations are proposed and their performance is assessed and compared to that of filter banks. The power of the method is demonstrated by classifying 2,806 images of all 61 materials present in the Columbia-Utrecht database. The classification performance surpasses that of recent state-of-the-art filter bank-based classifiers such as Leung and Malik (IJCV 01), Cula and Dana (IJCV 04), and Varma and Zisserman (IJCV 05). We also benchmark performance by classifying all of the textures present in the UIUC, Microsoft Textile, and San Francisco outdoor data sets. We conclude with discussions on why features based on compact neighborhoods can correctly discriminate between textures with large global structure and why the performance of filter banks is not superior to that of the source image patches from which they were derived.     

Shape-enhanced maximum intensity projection

Maximum intensity projection (MIP) displays the voxel with the maximum intensity along the viewing ray, and this offers simplicity in usage, as it does not require a complex transfer function, the specification of which is a highly challenging and time-consuming process in direct volume rendering (DVR). However, MIP also has its inherent limitation, the loss of spatial context and shape information. This paper proposes a novel technique, shape-enhanced maximum intensity projection (SEMIP), to resolve this limitation. Inspired by lighting in DVR to emphasize surface structures, SEMIP searches a valid gradient for the maximum intensity of each viewing ray, and applies gradient-based shading to improve shape and depth perception of structures. As SEMIP may result in the pixel values over the maximum intensity of the display device, a tone reduction technique is introduced to compress the intensity range of the rendered image while preserving the original local contrast. In addition, depth-based color cues are employed to enhance the visual perception of internal structures, and a focus and context interaction is used to highlight structures of interest. We demonstrate the effectiveness of the proposed SEMIP with several volume data sets, especially from the medical field.     

Improved Half Vector Space Light Transport

In this paper, we present improvements to half vector space light transport (HSLT) [ KHD14 ], which make this approach more practical, robust for difficult input geometry, and faster. Our first contribution is the computation of half vector space ray differentials in a different domain than the original work. This enables a more uniform stratification over the image plane during Markov chain exploration. Furthermore, we introduce a new multi chain perturbation in half vector space, which, if combined appropriately with half vector perturbation, makes the mutation strategy both more robust to geometric configurations with fine displacements and faster due to reduced number of ray casts. We provide and analyze the results of improved HSLT and discuss possible applications of our new half vector ray differentials.     

Discriminative compact pyramids for object and scene recognition

Spatial pyramids have been successfully applied to incorporating spatial information into bag-of-words based image representation. However, a major drawback is that it leads to high dimensional image representations. In this paper, we present a novel framework for obtaining compact pyramid representation. First, we investigate the usage of the divisive information theoretic feature clustering (DITC) algorithm in creating a compact pyramid representation. In many cases this method allows us to reduce the size of a high dimensional pyramid representation up to an order of magnitude with little or no loss in accuracy. Furthermore, comparison to clustering based on agglomerative information bottleneck (AIB) shows that our method obtains superior results at significantly lower computational costs. Moreover, we investigate the optimal combination of multiple features in the context of our compact pyramid representation. Finally, experiments show that the method can obtain state-of-the-art results on several challenging data sets.     

Parameterization,Feature Extraction and Binary Encoding for the Visualization of Tree-Like Structures

The study of vascular structures, using medical 3D models, is an active field of research. Illustrative visualizations have been applied to this domain in multiple ways. Researchers made the geometric properties of vasculature more comprehensive and augmented the surface with representations of multivariate clinical data. Techniques that head beyond the application of colour-maps or simple shading approaches require a surface parameterization, that is, texture coordinates, in order to overcome locality. When extracting 3D models, the computation of texture coordinates on the mesh is not always part of the data processing pipeline. We combine existing techniques to a simple parameterization approach that is suitable for tree-like structures. The parameterization is done w.r.t. to a pre-defined source vertex. For this, we present an automatic algorithm, that detects the tree root. The parameterization is partly done in screen-space and recomputed per frame. However, the screen-space computation comes with positive features that are not present in object-space approaches. We show how the resulting texture coordinates can be used for varying hatching, contour parameterization, display of decals, as additional depth cues and feature extraction. A further post-processing step based on parameterization allows for a segmentation of the structure and visualization of its tree topology.     

Order‐Independent Transparency for Programmable Deferred Shading Pipelines

In this paper, we present a flexible and efficient approach for the integration of order‐independent transparency into a deferred shading pipeline. The intermediate buffers for storing fragments to be shaded are extended with a dynamic and memory‐efficient storage for transparent fragments. The transparency of an object is not fixed and remains programmable until fragment processing, which allows for the implementation of advanced materials effects, interaction techniques or adaptive fade‐outs. Traversing costs for shading the transparent fragments are greatly reduced by introducing a tile‐based light‐culling pass. During deferred shading, opaque and transparent fragments are shaded and composited in front‐to‐back order using the retrieved lighting information and a physically‐based shading model. In addition, we discuss various configurations of the system and further enhancements. Our results show that the system performs at interactive frame rates even for complex scenarios.     

Particle systems for efficient and accurate high-order finite element visualization

Visualization has become an important component of the simulation pipeline, providing scientists and engineers a visual intuition of their models. Simulations that make use of the high-order finite element method for spatial subdivision, however, present a challenge to conventional isosurface visualization techniques. High-order finite element isosurfaces are often defined by basis functions in reference space, which give rise to a world-space solution through a coordinate transformation, which does not necessarily have a closed-form inverse. Therefore, world-space isosurface rendering methods such as marching cubes and ray tracing must perform a nested root finding, which is computationally expensive. We thus propose visualizing these isosurfaces with a particle system. We present a framework that allows particles to sample an isosurface in reference space, avoiding the costly inverse mapping of positions from world space when evaluating the basis functions. The distribution of particles across the reference space isosurface is controlled by geometric information from the world-space isosurface such as the surface gradient and curvature. The resulting particle distributions can be distributed evenly or adapted to accommodate world-space surface features. This provides compact, efficient, and accurate isosurface representations of these challenging data sets.     

视点相关的层次采样:一种硬件加速体光线投射算法

光线投射是一种高质量的体绘制方法.它以图像空间为序,逐根光线遍历和采样体数据.因此,传统上,它只能在CPU上实现,因而速度慢,交互性不好.提出了一个新的视点相关的层次采样VDLS (view dependent layer sampling)结构,VDLS将光线上的所有采样点重新组织成一系列层,并简化为两个视点相关的几何缓冲器,进而在GPU(graphics processing unit)中用两个动态纹理表示.利用GPU的可编程性,光线投射算法的6个步骤(光线生成、光线遍历、插值、分类、着色和颜色合成)得以完全在GPU中实现.在此基础上,提出两个基于体空间和图像空间连贯性的加速技巧,快速剔除无效的光线.结合其他与渲染和颜色合成有关的技巧,VDLS将面向多边形绘制的图形引擎转化为体光线投射算法引擎,在透视投影方式下,每秒能处理1.5亿个插值、后分类与着色的光线采样点.实验结果表明,提出的方法能用于医学可视化、真实物理现象模拟、材质检测中灰度体数据快速交互的可视化与漫游.