17763521
High-Quality Splatting on Rectilinear Grids with Efficient Culling of Occluded Voxels
Splatting is a popular volume rendering algorithm that pairs good image quality with an efficient volume projection scheme. The current axis-aligned sheet-buffer approach, however, bears certain inaccuracies. The effect of these is less noticeable in still images, but clearly revealed in animated viewing, where disturbing popping of object brightness occurs at certain view angle transitions. In previous work, we presented a new variant of sheet-buffered splatting in which the compositing sheets are oriented parallel to the image plane. This scheme not only eliminates the condition for popping, but also produces images of higher quality. In this paper, we summarize this new paradigm and extend it in a number of ways. We devise a new solution to render rectilinear grids of equivalent cost to the traditional approach that treats the anisotropic volume as being warped into a cubic grid. This enables us to use the usual radially symmetric kernels, which can be projected without inaccuracies. Next, current splatting approaches necessitate the projection of all voxels in the iso-interval(s), although only a subset of these voxels may eventually be visible in the final image. To eliminate these wasteful computations we propose a novel front-to-back approach that employs an occlusion map to determine if a splat contributes to the image before it is projected, thus skipping occluded splats. Additional measures are presented for further speedups. In addition, we present an efficient list-based volume traversal scheme that facilitates the quick modification of transfer functions and iso-values.
2068223
Edge Preservation in Volume Rendering Using Splatting
This paper presents a method to preserve sharp edge details in splatting for volume rendering. Conventional splatting algorithms produce fuzzy images for views close to the volume model. The lack of details in such views greatly hinders study and manipulation of data sets using virtual navigation. Our method applies a non-linear warping to the footprints of conventional splat and builds a table of footprints for different possible edge positions and edge strengths. When rendering, we pick a footprint from the table for each splat, based on the relative position of the voxel to the closest edge. Encouraging results have been achieved both for synthetic data and medical data.
2129354
Visualization of neuronal fiber connections from DT-MRI with global optimization
Diffusion Tensor MRI (DT-MRI) provides valuable 3D data describing diffusion characteristics of water molecules in the human brain. From DT-MRI, it is hoped that neuronal fiber connections among cortical regions can be reliably extracted and adequately interpreted. To achieve this goal, several significant challenges persist. In this paper, by means of dynamic programming we have developed a global fiber reconstruction algorithm enabling efficient visualization of neuronal connections queried by both the start and end points on the fly. Besides an inherent ability to handle noisy datasets, our algorithm also naturally addresses situations where neuronal fibers branch or cross each other. We demonstrate the efficacy of our approach with visualization of neuronal connections among activated brain cortical regions detected by functional MRI (fMRI).
2569639
Visibility culling for time-varying volume rendering using temporal occlusion coherence
Typically there is a high coherence in data values between neighboring time steps in an iterative scientific software simulation; this characteristic similarly contributes to a corresponding coherence in the visibility of volume blocks when these consecutive time steps are rendered. Yet traditional visibility culling algorithms were mainly designed for static data, without consideration of such potential temporal coherency. We explore the use of temporal occlusion coherence (TOC) to accelerate visibility culling for time-varying volume rendering. In our algorithm, the opacity of volume blocks is encoded by means of plenoptic opacity functions (POFs). A coherence-based block fusion technique is employed to coalesce time-coherent data blocks over a span of time steps into a single, representative block. Then POFs need only be computed for these representative blocks. To quickly determine the subvolumes that do not require updates in their visibility status for each subsequent time step, a hierarchical "TOC tree" data structure is constructed to store the spans of coherent time steps. To achieve maximal culling potential, while remaining conservative, we have extended our previous POP into an optimized POP (OPOP) encoding scheme for this specific scenario. To test our general TOC and OPOF approach, we have designed a parallel time-varying volume rendering algorithm accelerated by visibility culling. Results from experimental runs on a 32-processor cluster confirm both the effectiveness and scalability of our approach.
6888787
Distributed data management for large volume visualization
We propose a distributed data management scheme for large data visualization that emphasizes efficient data sharing and access. To minimize data access time and support users with a variety of local computing capabilities, we introduce an adaptive data selection method based on an "enhanced time-space partitioning" (ETSP) tree that assists with effective visibility culling, as well as multiresolution data selection. By traversing the tree, our data management algorithm can quickly identify the visible regions of data, and, for each region, adaptively choose the lowest resolution satisfying user-specified error tolerances. Only necessary data elements are accessed and sent to the visualization pipeline. To further address the issue of sharing large-scale data among geographically distributed collaborative teams, we have designed an infrastructure for integrating our data management technique with a distributed data storage system provided by logistical networking (LoN). Data sets at different resolutions are generated and uploaded to LoN for wide-area access. We describe a parallel volume rendering system that verifies the effectiveness of our data storage, selection and access scheme.
36043890
Remote Visualization by Browsing Image Based Databases with Logistical Networking
400858
Toward good elimination orders for symbolic SAT solving
Fundamentally different from DPLL, a new approach to SAT has recently emerged that abandons search and enlists BDDs to symbolically represent clauses of the CNF. These BDDs are conjoined according to a schedule where some variables may be eliminated by quantification at each step to reduce the size of the intermediate BDDs. SAT solving then reduces to checking whether the final BDD is the zero constant. For this approach to be practical, finding a good quantification schedule is critical. We study the use of a variable elimination algorithm for this purpose, as well as two specific methods for the generation of good elimination orders based on CNF structure. While neither method appears to dominate, we show how one can heuristically select the better using the notion of width. We implement a symbolic SAT solver based on these techniques and evaluate its efficiency and robustness on a set of benchmarks against five other solvers, each having unique characteristics, including winners of the most recent SAT competition.
16485757
Reverse Engineering MAC
This paper reverse engineers backoff-based random-access MAC protocols in ad-hoc networks. We show that the contention resolution algorithm in such protocols is implicitly participating in a non-cooperative game. Each link attempts to maximize a selfish local utility function, whose exact shape is reverse engineered from the protocol description, through a stochastic subgradient method in which the link updates its persistence probability based on its transmission success or failure. We prove that existence of a Nash equilibrium is guaranteed in general. The minimum amount of backoff aggressiveness needed for uniqueness of Nash equilibrium and convergence of the best response strategy are established as a function of user density. Convergence properties and connection with the best response strategy are also proved for variants of the stochastic-subgradient-based dynamics of the game. Together with known results in reverse engineering TCP and BGP, this paper completes the recent efforts in reverse engineering the main protocols in layers 2-4.
15941775
Exploring Regression for Mining User Moving Patterns in a Mobile Computing System
In this paper, by exploiting the log of call detail records, we present a solution procedure of mining user moving patterns in a mobile computing system. Specifically, we propose algorithm LS to accurately determine similar moving sequences from the log of call detail records so as to obtain moving behaviors of users. By exploring the feature of spatial-temporal locality, we develop algorithm TC to group call detail records into clusters. In light of the concept of regression, we devise algorithm MF to derive moving functions of moving behaviors. Performance of the proposed solution procedure is analyzed and sensitivity analysis on several design parameters is conducted. It is shown by our simulation results that user moving patterns obtained by our solution procedure are of very high quality and in fact very close to real user moving behaviors.
11615380
A sigma-delta modulation based BIST scheme for mixed-signal circuits
In this work, we present the analysis of a built-in self-test (BIST) scheme for mixed-signal circuits that is intended to provide on-chip stimulus generation and response analysis. Based on the sigma-delta modulation principle, the proposed scheme can produce high-quality stimuli and obtain accurate measurements without the need of precise analog circuitry. Numerical simulations are conducted to validate our idea and the results show that the scheme is a promising BIST approach for mixed-signal circuits.
4778324
Pushing vertices in digraphs without long induced cycles
Given a digraph D and a subset X of vertices of D, pushing X in D means reversing the orientation of all arcs with exactly one end in X. We continue the study of deciding whether a digraph can be made acyclic using the push operation, focussing on special classes of well-structured digraphs. It is proved that the problem remains NP-complete even when restricted to the class of bipartite digraphs (i.e., oriented bipartite graphs). We characterize, in terms of two forbidden subdigraphs, the chordal digraphs which can be made acyclic using the push operation, and show that there is no similar characterization for the family of chordal bipartite digraphs. A polynomial algorithm, based on 2-SAT, for solving the problem for a subclass of the chordal bipartite digraphs is given. Finally, a characterization in terms of a finite number of forbidden subdigraphs, of the acyclically pushable bipartite permutation digraphs is given.