30-Issue 7

Permanent URI for this collection

https://diglib.eg.org/handle/10.2312/167

Browse

Now showing 1 - 20 of 28

Asynchronous Evolution for Fully-Implicit and Semi-Implicit Time Integration
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Schroeder, Craig; Kwatra, Nipun; Zheng, Wen; Fedkiw, Ron; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
We propose a series of techniques for hybridizing implicit and semi-implicit time integration methods in a manner that retains much of the speed of the implicit method without sacrificing all of the higher quality vibrations one obtains with methods that handle elastic forces explicitly. We propose our scheme in the context of asynchronous methods, where different parts of the mesh are evolved at different time steps. Whereas traditional asynchronous methods evolve each element independently, we partition all of our elements into two groups: one group evolved at the frame rate using a fully implicit scheme, and another group which takes a number of substeps per frame using a scheme that is implicit on damping forces and explicit on the elastic forces. This allows for a straightforward coupling between the implicit and semi-implicit methods at frame boundaries for added stability. As has been stressed by various authors, asynchronous schemes take some of the pressure off of mesh generation, allowing time evolution to remain efficient even in the face of sliver elements. Finally, we propose a force distributing projection method which allows one to redistribute the forces felt on boundaries between implicit and semi-implicit regions of the mesh in a manner that yields improved visual quality.
Authoring Hierarchical Road Networks
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Galin, Eric; Peytavie, Adrien; Guérin, Eric; Benes, Bedrich; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
We present a procedural method for generating hierarchical road networks connecting cities, towns and villages over large terrains. Our approach relies on an original geometric graph generation algorithm based on a non- Euclidean metric combined with a path merging algorithm that creates junctions between the different types of roads. Unlike previous work, our method allows high level user control by manipulating the density and the pattern of the network. The geometry of the highways, primary and secondary roads as well as the interchanges and intersections are automatically created from the graph structure by instantiating generic parameterized models.
Bipartite Polar Classification for Surface Reconstruction
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Chen, Yi-Ling; Lee, Tung-Ying; Chen, Bing-Yu; Lai, Shang-Hong; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
In this paper, we propose bipartite polar classification to augment an input unorganized point set P with two disjoint groups of points distributed around the ambient space of P to assist the task of surface reconstruction. The goal of bipartite polar classification is to obtain a space partitioning of P by assigning pairs of Voronoi poles into two mutually invisible sets lying in the opposite sides of P through direct point set visibility examination. Based on the observation that a pair of Voronoi poles are mutually invisible, spatial classification is accomplished by carving away visible exterior poles with their counterparts simultaneously determined as interior ones. By examining the conflicts of mutual invisibility, holes or boundaries can also be effectively detected, resulting in a hole-aware space carving technique. With the classified poles, the task of surface reconstruction can be facilitated by more robust surface normal estimation with global consistent orientation and off-surface point specification for variational implicit surface reconstruction. We demonstrate the ability of the bipartite polar classification to achieve robust and efficient space carving on unorganized point clouds with holes and complex topology and show its application to surface reconstruction.
Computing 3D Shape Guarding and Star Decomposition
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Yu, Wuyi; Li, Xin; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
This paper proposes an effective framework to compute the visibility guarding and star decomposition of 3D solid shapes. We propose a progressive integer linear programming algorithm to solve the guarding points that can visibility cover the entire shape; we also develop a constrained region growing scheme seeded on these guarding points to get the star decomposition. We demonstrate this guarding/decomposition framework can benefit graphics tasks such as shape interpolation and shape matching/retrieval
Creating Fluid Animation from a Single Image using Video Database
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Okabe, Makoto; Anjyo, Ken; Onai, Rikio; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
We present a method for synthesizing fluid animation from a single image, using a fluid video database. The user inputs a target painting or photograph of a fluid scene along with its alpha matte that extracts the fluid region of interest in the scene. Our approach allows the user to generate a fluid animation from the input image and to enter a few additional commands about fluid orientation or speed. Employing the database of fluid examples, the core algorithm in our method then automatically assigns fluid videos for each part of the target image. Our method can therefore deal with various paintings and photographs of a river, waterfall, fire, and smoke. The resulting animations demonstrate that our method is more powerful and efficient than our prior work.
Discriminative Sketch-based 3D Model Retrieval via Robust Shape Matching
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Shao, Tianjia; Xu, Weiwei; Yin, Kangkang; Wang, Jingdong; Zhou, Kun; Guo, Baining; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
We propose a sketch-based 3D shape retrieval system that is substantially more discriminative and robust than existing systems, especially for complex models. The power of our system comes from a combination of a contourbased 2D shape representation and a robust sampling-based shape matching scheme. They are defined over discriminative local features and applicable for partial sketches; robust to noise and distortions in hand drawings; and consistent when strokes are added progressively. Our robust shape matching, however, requires dense sampling and registration and incurs a high computational cost. We thus devise critical acceleration methods to achieve interactive performance: precomputing kNN graphs that record transformations between neighboring contour images and enable fast online shape alignment; pruning sampling and shape registration strategically and hierarchically; and parallelizing shape matching on multi-core platforms or GPUs. We demonstrate the effectiveness of our system through various experiments, comparisons, and user studies.
Edge-Optimized À-Trous Wavelets for Local Contrast Enhancement with Robust Denoising
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Hanika, Johannes; Dammertz, Holger; Lensch, Hendrik; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
In this paper we extend the edge-avoiding à-trous wavelet transform for local contrast enhancement while avoiding common artifacts such as halos and gradient reversals. We show that this algorithm is a highly efficient and robust tool for image manipulation based on multi-scale decompositions. It can achieve comparable results to previous high-quality methods while being orders of magnitude faster and simpler to implement. Our method is much more robust than previously known fast methods by avoiding aliasing and ringing which is achieved by introducing a data-adaptive edge weight. Operating on multi-scale, our algorithm can directly include the BayesShrink method for denoising. For moderate noise levels our edge-optimized technique consistently improves separation of signal and noise.
Efficient Opacity Specification Based on Feature Visibilities in Direct Volume Rendering
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Wang, Yunhai; Zhang, Jian; Chen, Wei; Zhang, Huai; Chi, Xuebin; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Due to 3D occlusion, the specification of proper opacities in direct volume rendering is a time-consuming and unintuitive process. The visibility histograms introduced by Correa and Ma reflect the effect of occlusion by measuring the influence of each sample in the histogram to the rendered image. However, the visibility is defined on individual samples, while volume exploration focuses on conveying the spatial relationships between features. Moreover, the high computational cost and large memory requirement limits its application in multi-dimensional transfer function design. In this paper, we extend visibility histograms to feature visibility, which measures the contribution of each feature in the rendered image. Compared to visibility histograms, it has two distinctive advantages for opacity specification. First, the user can directly specify the visibilities for features and the opacities are automatically generated using an optimization algorithm. Second, its calculation requires only one rendering pass with no additional memory requirement. This feature visibility based opacity specification is fast and compatible with all types of transfer function design. Furthermore, we introduce a two-step volume exploration scheme, in which an automatic optimization is first performed to provide a clear illustration of the spatial relationship and then the user adjusts the visibilities directly to achieve the desired feature enhancement. The effectiveness of this scheme is demonstrated by experimental results on several volumetric datasets.
Exposure Fusion for Time-Of-Flight Imaging
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Hahne, Uwe; Alexa, Marc; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
This work deals with the problem of automatically choosing the correct exposure (or integration) time for timeof- flight depth image capturing. We apply methods known from high dynamic range imaging to combine depth images taken with differing integration times in order to produce high quality depth maps. We evaluate the quality of these depth maps by comparing the performance in reconstruction of planar textured patches and in the 3D reconstruction of an indoor scene. Our solution is fast enough to capture the images at interactive frame rates and also flexible to deal with any amount of exposures.
Flexible Splicing of Upper-Body Motion Spaces on Locomotion
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Basten, Ben J. H. van; Egges, Arjan; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
This paper presents an efficient technique for synthesizing motions by stitching, or splicing, an upper-body motion retrieved from a motion space on top of an existing lower-body locomotion of another motion. Compared to the standard motion splicing problem, motion space splicing imposes new challenges as both the upper and lower body motions might not be known in advance. Our technique is the first motion (space) splicing technique that propagates temporal and spatial properties of the lower-body locomotion to the newly generated upper-body motion and vice versa. Whereas existing techniques only adapt the upper-body motion to fit the lower-body motion, our technique also adapts the lower-body locomotion based on the upper body task for a more coherent full-body motion. In this paper, we will show that our decoupled approach is able to generate high-fidelity full-body motion for interactive applications such as games.
A Graph-based Approach to Continuous Line Illustrations with Variable Levels of Detail
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Wong, Fernando J.; Takahashi, Shigeo; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
This paper introduces a method for automatically generating continuous line illustrations, drawings consisting of a single line, from a given input image. Our approach begins by inferring a graph from a set of edges extracted from the image in question and obtaining a path that traverses through all edges of the said graph. The resulting path is then subjected to a series of post-processing operations to transform it into a continuous line drawing. Moreover, our approach allows us to manipulate the amount of detail portrayed in our line illustrations, which is particularly useful for simplifying the overall illustration while still retaining its most significant features. We also present several experimental results to demonstrate that our approach can automatically synthesize continuous line illustrations comparable to those of some contemporary artists.
Heat Walk: Robust Salient Segmentation of Non-rigid Shapes
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Benjamin, William; Polk, Andrew Wood; Vishwanathan, S. V. N.; Ramani, Karthik; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Segmenting three dimensional objects using properties of heat diffusion on meshes aim to produce salient results. The few existing algorithms based on heat diffusion do not use the full knowledge that can be gained from heat diffusion and are sensitive to varying kinds of perturbations. Our simple algorithm, Heat Walk, converts the implicit information in the heat kernel to explicit knowledge about the pathways for maximum heat flow capacity. We develop a two stage strategy for segmentation. In the first stage we quickly identify regions which are dominated by heat accumulators by employing a greedy algorithm. The second stage partitions out dissipative regions from the previously discovered accumulative regions by using a KL-divergence based criterion. The resulting algorithm is both independent of human intervention and fast because of the globally aware directed walk along the maximal heat flow capacity. Extensive experimental evidence shows the method is robust to a variety of noise factors including topological short circuits, surface holes, pose variations, variations in tessellation, missing features, scaling, as well as normal and shot noise. Comparison with the Princeton Segmentation Benchmark (PSB) shows that our method is comparable with state of the art segmentation methods and has additional advantages of being robust and self contained. Based upon theoretical insight the convergence and stability of the Heat Walk is shown.
An Illustrative Visualization Framework for 3D Vector Fields
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Chen, Cheng-Kai; Yan, Shi; Yu, Hongfeng; Max, Nelson; Ma, Kwan-Liu; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Most 3D vector field visualization techniques suffer from the problem of visual clutter, and it remains a challenging task to effectively convey both directional and structural information of 3D vector fields. In this paper, we present a novel visualization framework that combines the advantages of clustering methods and illustrative rendering techniques to generate a concise and informative depiction of complex flow structures. Given a 3D vector field, we first generate a number of streamlines covering the important regions based on an entropy measurement. Then we decompose the streamlines into different groups based on a categorization of vector information, wherein the streamline pattern in each group is ensured to be coherent or nearly coherent. For each group, we select a set of representative streamlines and render them in an illustrative fashion to enhance depth cues and succinctly show local flow characteristics. The results demonstrate that our approach can generate a visualization that is relatively free of visual clutter while facilitating perception of salient information of complex vector fields.
Improving Performance and Accuracy of Local PCA
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Gassenbauer, Václav; Krivánek, Jaroslav; Bouatouch, Kadi; Bouville, Christian; Ribardière, Mickaël; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Local Principal Component Analysis (LPCA) is one of the popular techniques for dimensionality reduction and data compression of large data sets encountered in computer graphics. The LPCA algorithm is a variant of kmeans clustering where the repetitive classification of high dimensional data points to their nearest cluster leads to long execution times. The focus of this paper is on improving the efficiency and accuracy of LPCA. We propose a novel SortCluster LPCA algorithm that significantly reduces the cost of the point-cluster classification stage, achieving a speed-up of up to 20. To improve the approximation accuracy, we investigate different initialization schemes for LPCA and find that the k-means++ algorithm [AV07] yields best results, however at a high computation cost. We show that similar ideas that lead to the efficiency of our SortCluster LPCA algorithm can be used to accelerate k-means++. The resulting initialization algorithm is faster than purely random seeding while producing substantially more accurate data approximation.
Intelligent GPGPU Classification in Volume Visualization: A framework based on Error-Correcting Output Codes
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Escalera, Sergio; Puig, Anna; Amoros, Oscar; Salamó, Maria; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
In volume visualization, the definition of the regions of interest is inherently an iterative trial-and-error process finding out the best parameters to classify and render the final image. Generally, the user requires a lot of expertise to analyze and edit these parameters through multi-dimensional transfer functions. In this paper, we present a framework of intelligent methods to label on-demand multiple regions of interest. These methods can be split into a two-level GPU-based labelling algorithm that computes in time of rendering a set of labelled structures using the Machine Learning Error-Correcting Output Codes (ECOC) framework. In a pre-processing step, ECOC trains a set of Adaboost binary classifiers from a reduced pre-labelled data set. Then, at the testing stage, each classifier is independently applied on the features of a set of unlabelled samples and combined to perform multi-class labelling. We also propose an alternative representation of these classifiers that allows to highly parallelize the testing stage. To exploit that parallelism we implemented the testing stage in GPU-OpenCL. The empirical results on different data sets for several volume structures shows high computational performance and classification accuracy.
Interactive Indirect Illumination Using Voxel Cone Tracing
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Crassin, Cyril; Neyret, Fabrice; Sainz, Miguel; Green, Simon; Eisemann, Elmar; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Indirect illumination is an important element for realistic image synthesis, but its computation is expensive and highly dependent on the complexity of the scene and of the BRDF of the involved surfaces. While off-line computation and pre-baking can be acceptable for some cases, many applications (games, simulators, etc.) require real-time or interactive approaches to evaluate indirect illumination. We present a novel algorithm to compute indirect lighting in real-time that avoids costly precomputation steps and is not restricted to low-frequency illumination. It is based on a hierarchical voxel octree representation generated and updated on the fly from a regular scene mesh coupled with an approximate voxel cone tracing that allows for a fast estimation of the visibility and incoming energy. Our approach can manage two light bounces for both Lambertian and glossy materials at interactive framerates (25-70FPS). It exhibits an almost scene-independent performance and can handle complex scenes with dynamic content thanks to an interactive octree-voxelization scheme. In addition, we demonstrate that our voxel cone tracing can be used to efficiently estimate Ambient Occlusion.
Motion Deblurring from a Single Image using Circular Sensor Motion
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Bando, Yosuke; Chen, Bing-Yu; Nishita, Tomoyuki; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Image blur caused by object motion attenuates high frequency content of images, making post-capture deblurring an ill-posed problem. The recoverable frequency band quickly becomes narrower for faster object motion as high frequencies are severely attenuated and virtually lost. This paper proposes to translate a camera sensor circularly about the optical axis during exposure, so that high frequencies can be preserved for a wide range of in-plane linear object motion in any direction within some predetermined speed. That is, although no object may be photographed sharply at capture time, differently moving objects captured in a single image can be deconvolved with similar quality. In addition, circular sensor motion is shown to facilitate blur estimation thanks to distinct frequency zero patterns of the resulting motion blur point-spread functions. An analysis of the frequency characteristics of circular sensor motion in relation to linear object motion is presented, along with deconvolution results for photographs captured with a prototype camera.
Motion Retrieval Using Low-Rank Subspace Decomposition of Motion Volume
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Sun, Chuan; Junejo, Imran; Foroosh, Hassan; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
This paper proposes a novel framework that allows for a flexible and an efficient retrieval of motion capture data in huge databases. The method first converts an action sequence into a novel representation, i.e. the Self-Similarity Matrix (SSM), which is based on the notion of self-similarity. This conversion of the motion sequences into compact and low-rank subspace representations greatly reduces the spatiotemporal dimensionality of the sequences. The SSMs are then used to construct order-3 tensors, and we propose a low-rank decomposition scheme that allows for converting the motion sequence volumes into compact lower dimensional representations, without losing the nonlinear dynamics of the motion manifold. Thus, unlike existing linear dimensionality reduction methods that distort the motion manifold and lose very critical and discriminative components, the proposed method performs well even when inter-class differences are small or intra-class differences are large. In addition, the method allows for an efficient retrieval and does not require the time-alignment of the motion sequences. We evaluate the performance of our retrieval framework on the CMU mocap dataset under two experimental settings, both demonstrating promising retrieval rates.
Optimized Topological Surgery for Unfolding 3D Meshes
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Takahashi, Shigeo; Wu, Hsiang-Yun; Saw, Seow Hui; Lin, Chun-Cheng; Yen, Hsu-Chun; Bing-Yu Chen, Jan Kautz, Tong-Yee Lee, and Ming C. Lin
Constructing a 3D papercraft model from its unfolding has been fun for both children and adults since we can reproduce virtual 3D models in the real world. However, facilitating the papercraft construction process is still a challenging problem, especially when the shape of the input model is complex in the sense that it has large variation in its surface curvature. This paper presents a new heuristic approach to unfolding 3D triangular meshes without any shape distortions, so that we can construct the 3D papercraft models through simple atomic operations for gluing boundary edges around the 2D unfoldings. Our approach is inspired by the concept of topological surgery, where the appearance of boundary edges of the unfolded closed surface can be encoded using a symbolic representation. To fully simplify the papercraft construction process, we developed a genetic-based algorithm for unfolding the 3D mesh into a single connected patch in general, while optimizing the usage of the paper sheet and balance in the shape of that patch. Several examples together with user studies are included to demonstrate that the proposed approach works well for a broad range of 3D triangular meshes.
Preface and Table of Contents
(The Eurographics Association and Blackwell Publishing Ltd., 2011) Bing-Yu Chen and Jan Kautz and Tong-Yee Lee and Ming C. Lin

Browse

Browsing 30-Issue 7 by Title

Results Per Page

Sort Options