Search

Keeping up with rapidly growing research fields, especially when there are multiple interdisciplinary sources, requires substantial effort for researchers, program managers, or venture capital investors. Current theories and tools are directed at finding a paper or website, not gaining an understanding of the key papers, authors, controversies, and hypotheses. This report presents an effort to integrate statistics, text analytics, and visualization in a multiple coordinated window environment that supports exploration. Our prototype system, Action Science Explorer ( ASE), provides an environment for demonstrating principles of coordination and conducting iterative usability tests of them with interested and knowledgeable users. We developed an understanding of the value of reference management, statistics, citation text extraction, natural language summarization for single and multiple documents, filters to interactively select key papers, and network visualization to see citation patterns and identify clusters. A three-phase usability study guided our revisions to ASE and led us to improve the testing methods. [ABSTRACT FROM AUTHOR]

Image editing is a commonly studied problem in computer graphics. Despite the presence of many advanced editing tools, there is no satisfactory solution to controllably update the position of the sun using a single image. This problem is made complicated by the presence of clouds, complex landscapes, and the atmospheric effects that must be accounted for. In this paper, we tackle this problem starting with only a single photograph. With the user clicking on the initial position of the sun, our algorithm performs several estimation and segmentation processes for finding the horizon, scene depth, clouds, and the sky line. After this initial process, the user can make both fine‐ and large‐scale changes on the position of the sun: it can be set beneath the mountains or moved behind the clouds practically turning a midday photograph into a sunset (or vice versa). We leverage a precomputed atmospheric scattering algorithm to make all of these changes not only realistic but also in real‐time. We demonstrate our results using both clear and cloudy skies, showing how to add, remove, and relight clouds, all the while allowing for advanced effects such as scattering, shadows, light shafts, and lens flares. [ABSTRACT FROM AUTHOR]

Summary: Stable image matching is still a pursuit goal in the communities of computer vision and graphics because of many potential applications such as 3D reconstruction, object recognition, and visual tracking. In the case of 3D reconstruction, modern structure‐from‐motion methods depend heavily on image‐matching methods for recovering geometric models. Existing methods have tried to exploit various strategies to generate correct feature correspondences for 3D reconstruction. However, there are no efficient methods that can work well in the wild. To defend this drawback, in this paper, we design a stable image‐matching method for 3D reconstruction. The method consists of feature point detection, descriptor extraction, feature matching, and matching verification. Besides, we try to choose a stable algorithm for each module of the proposed method, in which the adopted algorithms are implemented in an optimized approach for acceleration. Finally, we conduct a systematic experiment on several benchmarking datasets to assess the performance of the proposed method. Experimental results show that the proposed method has both high matching precision and fast speed. [ABSTRACT FROM AUTHOR]

Abstract: This paper describes a general algorithm and a system for load balancing sparse fluid simulations. Automatically distributing sparse fluid simulations efficiently is challenging because the computational load varies across the simulation domain and time. A key challenge with load balancing is that optimal decision making requires knowing the fluid distribution across partitions for future time steps, but computing this state for an arbitrary simulation requires running the simulation itself. The key insight of this paper is that it is possible to predict future load by running a speculative low resolution simulation in parallel. We mathematically formulate the problem of load balancing over multiple time steps and present a polynomial time algorithm to compute an approximate solution to it. Our experimental results show that distributing and speculatively load balancing sparse FLIP simulations over 8 nodes speeds them up by 5.3× to 7.9×, and that speculative load balancing generates assignments that perform within 20% of optimal. [ABSTRACT FROM AUTHOR]

3D shape recognition has been actively investigated in the field of computer graphics. With the rapid development of deep learning, various deep models have been introduced and achieved remarkable results. Most 3D shape recognition methods are supervised and learn only from the large amount of labeled shapes. However, it is expensive and time consuming to obtain such a large training set. In contrast to these methods, this paper studies a semi‐supervised learning framework to train a deep model for 3D shape recognition by using both labeled and unlabeled shapes. Inspired by the co‐training algorithm, our method iterates between model training and pseudo‐label generation phases. In the model training phase, we train two deep networks based on the point cloud and multi‐view representation simultaneously. In the pseudo‐label generation phase, we generate the pseudo‐labels of the unlabeled shapes using the joint prediction of two networks, which augments the labeled set for the next iteration. To extract more reliable consensus information from multiple representations, we propose an uncertainty‐aware consistency loss function to combine the two networks into a multimodal network. This not only encourages the two networks to give similar predictions on the unlabeled set, but also eliminates the negative influence of the large performance gap between the two networks. Experiments on the benchmark ModelNet40 demonstrate that, with only 10% labeled training data, our approach achieves competitive performance to the results reported by supervised methods. [ABSTRACT FROM AUTHOR]

Research in the area of collision detection permeates most of the literature on simulations, interaction and agents planning, being commonly regarded as one of the main bottlenecks for large‐scale systems. To this day, despite its importance, most subareas of collision detection lack a common ground to test and validate solutions, reference implementations and widely accepted benchmark suites. In this paper, we delve into the broad‐phase of collision detection systems, providing both an open‐source framework, named Broadmark, to test, compare and validate algorithms, and an in‐deep analysis of the main techniques used so far to tackle the broad‐phase problem. The technical challenges of building this framework from the software and hardware perspectives are also described. Within our framework, several original and state‐of‐the‐art implementations of CPU and GPU algorithms are bundled, alongside three benchmark scenes to stress algorithms under several conditions. Furthermore, the system is designed to be easily extensible. We use our framework to bring out an extensive performance comparison among assembled solutions, detailing the current CPU and GPU state‐of‐the‐art on a common ground. We believe that Broadmark encompasses the principal insights and tools to derive and evaluate novel algorithms, thus greatly facilitating discussion about successful broad‐phase collision detection solutions. [ABSTRACT FROM AUTHOR]

Extracting a faithful and compact representation of an animated surface mesh is an important problem for computer graphics. However, the surface‐based methods have limited approximation power for volume preservation when the animated sequences are extremely simplified. In this paper, we introduce Deformable Medial Axis Transform (DMAT), which is deformable medial mesh composed of a set of animated spheres. Starting from extracting an accurate and compact representation of a static MAT as the template and partitioning the vertices on the input surface as the correspondences for each medial primitive, we present a correspondence‐based approximation method equipped with an As‐Rigid‐As‐Possible (ARAP) deformation energy defined on medial primitives. As a result, our algorithm produces DMAT with consistent connectivity across the whole sequence, accurately approximating the input animated surfaces. [ABSTRACT FROM AUTHOR]

This paper presents the evolution of a data structures and algorithms course based on a specific computer graphics problem, namely, photon mapping, as the teaching medium. The paper reports development of the course through several iterations and evaluations, dating back 5 years. The course originated as a problem-based graphics course requiring sophomore students to implement Hoppe et al.'s algorithm for surface reconstruction from unorganized points found in their SIGGRAPH '92 paper of the same title. Although the solution to this problem lends itself well to an exploration of data structures and code modularization, both of which are traditionally taught in early computer science courses, the algorithm's complexity was reflected in students' overwhelmingly negative evaluations. Subsequently, because implementation of the kd-tree was seen as the linchpin data structure, it was again featured in the problem of ray tracing trees consisting of more than 250 000 000 triangles. Eventually, because the tree rendering was thought too specific a problem, the photon mapper was chosen as the semester-long problem considered to be a suitable replacement. This paper details the resultant course description and outline, from its now three semesters of teaching. [ABSTRACT FROM AUTHOR]

Interactive rigid body simulation is an important part of many modern computer tools, which no authoring tool nor game engine can do without. Such high-performance computer tools open up new possibilities for changing how designers, engineers, modelers and animators work with their design problems. This paper is a self contained state-of-the-art report on the physics, the models, the numerical methods and the algorithms used in interactive rigid body simulation all of which have evolved and matured over the past 20 years. Furthermore, the paper communicates the mathematical and theoretical details in a pedagogical manner. This paper is not only a stake in the sand on what has been done, it also seeks to give the reader deeper insights to help guide their future research. [ABSTRACT FROM AUTHOR]

In this paper we present a new method for improving the performance of the widely used Bounding Volume Hierarchies for collision detection. The major contribution of our work is a culling algorithm that serves as a generalization of the Separating Axis Theorem for non parallel axes, based on the well-known concept of support planes. We also provide a rigorous definition of support plane mappings and implementation details regarding the application of the proposed method to commonly used bounding volumes. The paper describes the theoretical foundation and an overall evaluation of the proposed algorithm. It demonstrates its high culling efficiency and in its application, significant improvement of timing performance with different types of bounding volumes and support plane mappings for rigid body simulations. [ABSTRACT FROM AUTHOR]

This paper considers the problem of interactively finding the cutting contour to extract components from a given mesh. Some existing methods support cuts of arbitrary shape but require careful and tedious input from the user. Others need little user input however they are sensitive to user input and need a postprocessing step to smooth the generated jaggy cutting contours. The popular geometric snake can be used to optimize the cutting contour, but it cannot deal with the topology change. In this paper, we propose a geodesic curvature flow based framework to overcome all these problems. Since in many cases the meaningful cutting contour on a 3D mesh is locally shortest in the sense of some weighted curve length, the geodesic curvature flow is an ideal tool for our problem. It evolves the cutting contour to the nearby local minimum. We should mention that the previous numerical scheme, discretized geodesic curvature flow (dGCF) is too slow and has not been applied to mesh segmentation. With a careful observation to dGCF, we devise here a fast computation scheme called fast geodesic curvature flow (FGCF), which only needs to solve a smaller and easier problem. The initial cutting contour is generated by a variant of random walks algorithm, which is very fast and gives reasonable cutting result with little user input. Experiment results on the benchmark mesh segmentation data set show that our proposed framework is robust to user input and capable of producing good results reflecting geometric features and human shape perception. [ABSTRACT FROM AUTHOR]

In this paper, we present an extension of dynamic mesh compression techniques based on PCA. Such representation allows very compact representation of moving 3D surfaces; however, it requires some side information to be transmitted along with the main data. The biggest part of this information is the PCA basis, and since the data can be encoded very efficiently, the size of the basis cannot be neglected when considering the overall performance of a compression algorithm. We present a new work in this area, as none of the papers about PCA based compression really addresses this issue. We will show that for an efficient and accurate encoding there are better choices than even sophisticated algorithms such as LPC. We will present results showing that our approach can reduce the size of the basis by 90% with respect to direct encoding, which can lead to approximately 25% increase of performance of the compression algorithm without any significant loss of accuracy. Such improvement moves the performance of the PCA encoder beyond the performance of current state of the art dynamic mesh compression algorithms, such as the recently adopted MPEG standard, FAMC. [ABSTRACT FROM AUTHOR]

Voxel traversing along a line in a uniformly divided voxel space is frequently needed in different applications of computer graphics. The paper presents a new integer one-pass algorithm for this problem. In 2D, the proposed approach is based on a modification of the well-known Bresenham algorithm. The algorithm is then extended in 3D where a special case may occur. It is characterized by a simple discriminator. A derivation for this discriminator given in the paper confirms that all calculations can be realized using only integer arithmetic. In this way, the accumulation of rounding errors is completely eliminated, and a robust and compact implementation can be easily achieved. One of the main advantages of the proposed algorithm is that it visits 1–3 voxels during each iteration thus assuring its efficiency. The algorithm has been compared with other algorithms for voxel traversing by measuring spent CPU time. For comparison, Cleary & Wyvill's, Amanatides & Woo's, and Code-based algorithm have been used. The proposed algorithm is faster than the referenced algorithms. [ABSTRACT FROM AUTHOR]

Line clipping against a polygon is widely used in computer graphics such as the hidden line problem. A new line–clipping algorithm against a general polygon is presented in this paper. The basic idea of this algorithm is to change the line to be clipped into a horizontal line by shearing transformation. Then each edge of the polygonal window is transformed by a shearing transformation with the same parameters as those used to the line. Each edge of the polygon is processed against a horizontal line, which makes the clipping process simpler. The result in this paper shows that less calculation is needed for the new algorithm with a higher speed compared to existing algorithms. [ABSTRACT FROM AUTHOR]

This paper presents a method for modelling graphics scenes consisting of multiple volumetric objects. A two-level hierarchical representation is employed, which enables the reduction of the overall storage consumption as well as rendering time. With this approach, different objects can be derived from the same volumetric dataset, and 2D images can be trivially integrated into a scene. The paper also describes an efficient algorithm for rendering such scenes on ordinary workstations, and addresses issues concerning memory requirements and disk swapping. [ABSTRACT FROM AUTHOR]

Symmetry is a common characteristic in natural and man-made objects. Its ubiquitous nature can be exploited to facilitate the analysis and processing of computational representations of real objects. In particular, in computer graphics, the detection of symmetries in 3D geometry has enabled a number of applications in modeling and reconstruction. However, the problem of symmetry detection in incomplete geometry remains a challenging task. In this paper, we propose a vote-based approach to detect symmetry in 3D shapes, with special interest in models with large missing parts. Our algorithm generates a set of candidate symmetries by matching local maxima of a surface function based on the heat diffusion in local domains, which guarantee robustness to missing data. In order to deal with local perturbations, we propose a multi-scale surface function that is useful to select a set of distinctive points over which the approximate symmetries are defined. In addition, we introduce a vote-based scheme that is aware of the partiality, and therefore reduces the number of false positive votes for the candidate symmetries. We show the effectiveness of our method in a varied set of 3D shapes and different levels of partiality. Furthermore, we show the applicability of our algorithm in the repair and completion of challenging reassembled objects in the context of cultural heritage. [ABSTRACT FROM AUTHOR]

This paper studies the Voronoi diagrams on 2-manifold meshes based on geodesic metric (a.k.a. geodesic Voronoi diagrams or GVDs), which have polyline generators. We show that our general setting leads to situations more complicated than conventional 2D Euclidean Voronoi diagrams as well as point-source based GVDs, since a typical bisector contains line segments, hyperbolic segments and parabolic segments. To tackle this challenge, we introduce a new concept, called local Voronoi diagram (LVD), which is a combination of additively weighted Voronoi diagram and line-segment Voronoi diagram on a mesh triangle. We show that when restricting on a single mesh triangle, the GVD is a subset of the LVD and only two types of mesh triangles can contain GVD edges. Based on these results, we propose an efficient algorithm for constructing the GVD with polyline generators. Our algorithm runs in O(nNlogN) time and takes O(nN) space on an n-face mesh with m generators, where N = max{m, n}. Computational results on real-world models demonstrate the efficiency of our algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we propose a novel shape descriptor that is robust in differentiating intrinsic symmetric points on geometric surfaces. Our motivation is that even the state-of-theart shape descriptors and non-rigid surface matching algorithms suffer from symmetry flips. They cannot differentiate surface points that are symmetric or near symmetric. Hence a left hand of one human model may be matched to a right hand of another. Our Symmetry Robust Descriptor (SRD) is based on a signed angle field, which can be calculated from the gradient fields of the harmonic fields of two point pairs. Experiments show that the proposed shape descriptor SRD results in much less symmetry flips compared to alternative methods. We further incorporate SRD into a stand-alone algorithm to minimize symmetry flips in finding sparse shape correspondences. SRD can also be used to augment other modern non-rigid shape matching algorithms with ease to alleviate symmetry confusions. [ABSTRACT FROM AUTHOR]

Countershading is a common technique for local image contrast manipulations, and is widely used both in automatic settings, such as image sharpening and tonemapping, as well as under artistic control, such as in paintings and interactive image processing software. Unfortunately, countershading is a double-edged sword: while correctly chosen parameters for a given viewing condition can significantly improve the image sharpness or trick the human visual system into perceiving a higher contrast than physically present in an image, wrong parameters, or different viewing conditions can result in objectionable halo artifacts. In this paper we investigate the perception of countershading in the context of a novel mask-based contrast enhancement algorithm and analyze the circumstances under which the resulting profiles turn from image enhancement to artifact for a range of parameters and viewing conditions. Our experimental results can be modeled as a function of the width of the countershading profile. We employ this empirical function in a range of applications such as image resizing, view dependent tone mapping, and countershading analysis in photographs and works of fine art. [ABSTRACT FROM AUTHOR]

Rigging an arbitrary 3D character by creating an animation skeleton is a time-consuming process even for experienced animators. In this paper, we present an algorithm that automatically creates animation rigs for multi-component 3D models, as they are typically found in online shape databases. Our algorithm takes as input a multi-component model and an input animation skeleton with associated motion data. It then creates a target skeleton for the input model, calculates the rigid skinning weights, and a mapping between the joints of the target skeleton and the input animation skeleton. The automatic approach does not need additional semantic information, such as component labels or user-provided correspondences, and succeeds on a wide range of models where the number of components is significantly different. It implicitly handles large scale and proportional differences between input and target skeletons and can deal with certain morphological differences, e.g., if input and target have different numbers of limbs. The output of our algorithm can be directly used in a retargeting system to create a plausible animated character. [ABSTRACT FROM AUTHOR]

In mechanical engineering and architecture, structural elements with low material consumption and high load-bearing capabilities are essential for light-weight and even self-supporting constructions. This paper deals with so called point-folding elements - non-planar, pyramidal panels, usually formed from thin metal sheets, which exploit the increased structural capabilities emerging from folds or creases. Given a triangulated free-form surface, a corresponding point-folding structure is a collection of pyramidal elements basing on the triangles. User-specified or material-induced geometric constraints often imply that each individual folding element has a different shape, leading to immense fabrication costs. We present a rationalization method for such structures which respects the prescribed aesthetic and production constraints and finds a minimal set of molds for the production process, leading to drastically reduced costs. For each base triangle we compute and parametrize the range of feasible folding elements that satisfy the given constraints within the allowed tolerances. Then we pose the rationalization task as a geometric intersection problem, which we solve so as to maximize the re-use of mold dies. Major challenges arise from the high precision requirements and the non-trivial parametrization of the search space. We evaluate our method on a number of practical examples where we achieve rationalization gains of more than 90%. [ABSTRACT FROM AUTHOR]

3D transformation widgets allow constrained manipulations of 3D objects and are commonly used in many 3D applications for fine-grained manipulations. Since traditional transformation widgets have been mainly designed for mouse-based systems, they are not user friendly for multitouch screens. There is little research on how to use the extra input bandwidth of multitouch screens to ease constrained transformation of 3D objects. This paper presents a small set of multitouch gestures which offers a seamless control of manipulation constraints (i.e., axis or plane) and modes (i.e., translation, rotation or scaling). Our technique does not require any complex manipulation widgets but candidate axes, which are for visualization rather than direct manipulation. Such design not only minimizes visual clutter but also tolerates imprecise touch-based inputs. To further expand our axis-based interaction vocabulary, we introduce intuitive touch gestures for relative manipulations, including snapping and borrowing axes of another object. A preliminary evaluation shows that our technique is more effective than a direct adaption of standard transformation widgets to the tactile paradigm. [ABSTRACT FROM AUTHOR]

This paper presents an analysis of the irradiance estimator often used in photon mapping algorithms and concludes that the classical approach with a constant kernel overestimates the correct value. We propose a new estimator that solves this problem and provide both theoretical and empirical studies to verify it. [ABSTRACT FROM AUTHOR]

This paper presents a 3D-mesh segmentation algorithm based on a learning approach. A large database of manually segmented 3D-meshes is used to learn a boundary edge function. The function is learned using a classifier which automatically selects from a pool of geometric features the most relevant ones to detect candidate boundary edges. We propose a processing pipeline that produces smooth closed boundaries using this edge function. This pipeline successively selects a set of candidate boundary contours, closes them and optimizes them using a snake movement. Our algorithm was evaluated quantitatively using two different segmentation benchmarks and was shown to outperform most recent algorithms from the state-of-the-art. [ABSTRACT FROM AUTHOR]

Realistic terrain models are required in many applications, especially in computer games. Commonly, procedural models are applied to generate the corresponding models and let users experience a wide variety of new environments. Existing algorithms generate landscapes immediately with view-dependent resolution and without preprocessing. Unfortunately, landscapes generated by such algorithms lack river networks and therefore appear unnatural. Algorithms that integrate realistic river networks are computationally expensive and cannot be used to generate a locally adaptive high resolution landscape during a fly-through. In this paper, we propose a novel algorithm to generate realistic river networks. Our procedural algorithm creates complete planets and landscapes with realistic river networks within seconds. It starts with a coarse base geometry of a planet without further preprocessing and user intervention. By exploiting current graphics hardware, the proposed algorithm is able to generate adaptively refined landscape geometry during fly-throughs. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

In this paper, we propose an improvement of an algorithm of Aurenhammer, Hoffmann and Aronov to find a least square matching between a probability density and finite set of sites with mass constraints, in the Euclidean plane. Our algorithm exploits the multiscale nature of this optimal transport problem. We iteratively simplify the target using Lloyd's algorithm, and use the solution of the simplified problem as a rough initial solution to the more complex one. This approach allows for fast estimation of distances between measures related to optimal transport (known as Earth-mover or Wasserstein distances). We also discuss the implementation of these algorithms, and compare the original one to its multiscale counterpart. [ABSTRACT FROM AUTHOR]

Despite the large amount of work devoted in recent years to the problem of non-rigid shape matching, practical methods that can successfully be used for arbitrary pairs of shapes remain elusive. In this paper, we study the hardness of the problem of shape matching, and introduce the notion of the shape condition number, which captures the intuition that some shapes are inherently more difficult to match against than others. In particular, we make a connection between the symmetry of a given shape and the stability of any method used to match it while optimizing a given distortion measure. We analyze two commonly used classes of methods in deformable shape matching, and show that the stability of both types of techniques can be captured by the appropriate notion of a condition number. We also provide a practical way to estimate the shape condition number and show how it can be used to guide the selection of landmark correspondences between shapes. Thus we shed some light on the reasons why general shape matching remains difficult and provide a way to detect and mitigate such difficulties in practice. [ABSTRACT FROM AUTHOR]

In this paper, a new method for deformable 3D shape registration is proposed. The algorithm computes shape transitions based on local similarity transforms which allows to model not only as-rigid-as-possible deformations but also local and global scale. We formulate an ordinary differential equation (ODE) which describes the transition of a source shape towards a target shape. We assume that both shapes are roughly pre-aligned (e.g., frames of a motion sequence). The ODE consists of two terms. The first one causes the deformation by pulling the source shape points towards corresponding points on the target shape. Initial correspondences are estimated by closest-point search and then refined by an efficient smoothing scheme. The second term regularizes the deformation by drawing the points towards locally defined rest positions. These are given by the optimal similarity transform which matches the initial (undeformed) neighborhood of a source point to its current (deformed) neighborhood. The proposed ODE allows for a very efficient explicit numerical integration. This avoids the repeated solution of large linear systems usually done when solving the registration problem within general-purpose non-linear optimization frameworks. We experimentally validate the proposed method on a variety of real data and perform a comparison with several state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

In this paper we review the traversal algorithms for kd-trees for ray tracing. Ordinary traversal algorithms such as sequential, recursive, and those with neighbour-links have different limitations, which led to several new developments within the last decade. We describe algorithms exploiting ray coherence and algorithms designed with specific hardware architecture limitations such as memory latency and consumption in mind. We also discuss the robustness of traversal algorithms as one issue that has been neglected in previous research. [ABSTRACT FROM AUTHOR]

This paper presents efficient algorithms for free path sampling in heterogeneous participating media defined either by high-resolution voxel arrays or generated procedurally. The method is based on the concept of mixing 'virtual' material or particles to the medium, augmenting the extinction coefficient to a function for which the free path can be sampled in a straightforward way. The virtual material is selected such that it modifies the volume density but does not alter the radiance. We define the total extinction coefficient of the real and virtual particles by a low-resolution grid of super-voxels that are much larger than the real voxels defining the medium. The computational complexity of the proposed method depends just on the resolution of the super-voxel grid and does not grow with the resolution above the scale of super-voxels. The method is particularly efficient to render large, low-density, heterogeneous volumes, which should otherwise be defined by enormously high resolution voxel grids and where the average free path length would cross many voxels. [ABSTRACT FROM AUTHOR]

Normal estimation is an important topic for processing point cloud data and surface reconstruction in computer graphics. In this paper we consider the problem of estimating normals for a (unknown) submanifold of a Euclidean space of codimension 1 from random points on the manifold. We propose a kernel-based learning algorithm in an unsupervised form of gradient learning. The algorithm can be implemented by solving a linear algebra problem. Error analysis is conducted under conditions on the true normals of the manifold and the sampling distribution. Copyright © 2010 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This paper presents a diffusion method for generating terrains from a set of parameterized curves that characterize the landform features such as ridge lines, riverbeds or cliffs. Our approach provides the user with an intuitive vector-based feature-oriented control over the terrain. Different types of constraints (such as elevation, slope angle and roughness) can be attached to the curves so as to define the shape of the terrain. The terrain is generated from the curve representation by using an efficient multigrid diffusion algorithm. The algorithm can be efficiently implemented on the GPU, which allows the user to interactively create a vast variety of landscapes. [ABSTRACT FROM AUTHOR]

Real-time rendering of models with high polygon count is still an important issue in interactive computer graphics. A common way to improve rendering performance is to generate different levels of detail of a model. These are mostly computed using polygonal simplification techniques, which aim to reduce the number of polygons without significant loss of visual fidelity. Most existing algorithms use geometric error bounds, which are well-suited for silhouette preservation. They ignore the fact that a much more aggressive simplification is possible in low-contrast areas inside the model. The main contribution of this paper is an efficient simplification algorithm based on the human visual system. The key idea is to move the domain of error computation from image-space to vertex-space to avoid a costly per-pixel comparison. This way the error estimation of a simplification operation can be accelerated significantly. To account for the human vision, we introduce a perceptually based metric depending on the contrast and spatial frequency of the model at a single vertex. Finally, we validate our approach with a user study. [ABSTRACT FROM AUTHOR]

Empty-space skipping is an essential acceleration technique for volume rendering. Image-order empty-space skipping is not well suited to GPU implementation, since it must perform checks on, essentially, a per-sample basis, as in kd-tree traversal, which can lead to a great deal of divergent branching at runtime, which is very expensive in a modern GPU pipeline. In contrast, object-order empty-space skipping is extremely fast on a GPU and has negligible overheads compared with approaches without empty-space skipping, since it employs the hardware unit for rasterisation. However, previous object-order algorithms have been able to skip only exterior empty space and not the interior empty space that lies inside or between volume objects. In this paper, we address these issues by proposing a multi-layer depth-peeling approach that can obtain all of the depth layers of the tight-fitting bounding geometry of the isosurface by a single rasterising pass. The maximum count of layers peeled by our approach can be up to thousands, while maintaining 32-bit float-point accuracy, which was not possible previously. By raytracing only the valid ray segments between each consecutive pair of depth layers, we can skip both the interior and exterior empty space efficiently. In comparisons with 3 state-of-the-art GPU isosurface rendering algorithms, this technique achieved much faster rendering across a variety of data sets. [ABSTRACT FROM AUTHOR]

This paper proposes two variants of a simple but efficient algorithm for structure-preserving halftoning. Our algorithm extends Floyd-Steinberg error diffusion; the goal of our extension is not only to produce good tone similarity but also to preserve structure and especially contrast, motivated by our intuition that human perception is sensitive to contrast. By enhancing contrast we attempt to preserve and enhance structure also. Our basic algorithm employs an adaptive, contrast-aware mask. To enhance contrast, darker pixels should be more likely to be chosen as black pixels while lighter pixels should be more likely to be set as white. Therefore, when the positive error is diffused to nearby pixels in a mask, the dark pixels absorb less error and the light pixels absorb more. Conversely, negative error is distributed preferentially to dark pixels. We also propose using a mask with values that drop off steeply from the centre, intended to promote good spatial distribution. It is a very fast method whose speed mainly depends on the size of the mask. But this method suffers from distracting patterns. We then propose a variant on the basic idea which overcomes the first algorithm's shortcomings while maintaining its advantages through a priority-aware scheme. Rather than proceeding in random or raster order, we sort the image first; each pixel is assigned a priority based on its up-to-date distance to black or to white, and pixels with extreme intensities are processed earlier. Since we use the same mask strategy as before, we promote good spatial distribution and high contrast. We use tone similarity, structure similarity, and contrast similarity to validate our algorithm. Comparisons with recent structure-aware algorithms show that our method gives better results without sacrificing speed. [ABSTRACT FROM AUTHOR]

In this paper, we propose an automatic method for generating roads based on a weighted anisotropic shortest path algorithm. Given an input scene, we automatically create a path connecting an initial and a final point. The trajectory of the road minimizes a cost function that takes into account the different parameters of the scene including the slope of the terrain, natural obstacles such as rivers, lakes, mountains and forests. The road is generated by excavating the terrain along the path and instantiating generic parameterized models. [ABSTRACT FROM AUTHOR]

This paper presents a novel framework for elliptical weighted average (EWA) surface splatting with time-varying scenes. We extend the theoretical basis of the original framework by replacing the 2D surface reconstruction filters by 3D kernels which unify the spatial and temporal component of moving objects. Based on the newly derived mathematical framework we introduce a rendering algorithm that supports the generation of high-quality motion blur for point-based objects using a piecewise linear approximation of the motion. The rendering algorithm applies ellipsoids as rendering primitives which are constructed by extending planar EWA surface splats into the temporal dimension along the instantaneous motion vector. Finally, we present an implementation of the proposed rendering algorithm with approximated occlusion handling using advanced features of modern GPUs and show its capability of producing motion-blurred result images at interactive frame rates. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel method to compute Boolean operations on polygonal meshes. Given a Boolean expression over an arbitrary number of input meshes we reliably and efficiently compute an output mesh which faithfully preserves the existing sharp features and precisely reconstructs the new features appearing along the intersections of the input meshes. The term “hybrid” applies to our method in two ways: First, our algorithm operates on a hybrid data structure which stores the original input polygons (surface data) in an adaptively refined octree (volume data). By this we combine the robustness of volumetric techniques with the accuracy of surface-oriented techniques. Second, we generate a new triangulation only in a close vicinity around the intersections of the input meshes and thus preserve as much of the original mesh structure as possible (hybrid mesh). Since the actual processing of the Boolean operation is confined to a very small region around the intersections of the input meshes, we can achieve very high adaptive refinement resolutions and hence very high precision. We demonstrate our method on a number of challenging examples. [ABSTRACT FROM AUTHOR]

The Bidirectional Texture Function (BTF) is becoming widely used for accurate representation of real-world material appearance. In this paper a novel BTF compression model is proposed. The model resamples input BTF data into a parametrization, allowing decomposition of individual view and illumination dependent texels into a set of multi-dimensional conditional probability density functions. These functions are compressed in turn using a novel multi-level vector quantization algorithm. The result of this algorithm is a set of index and scale code-books for individual dimensions. BTF reconstruction from the model is then based on fast chained indexing into the nested stored code-books. In the proposed model, luminance and chromaticity are treated separately to achieve further compression. The proposed model achieves low distortion and compression ratios 1:233–1:2040, depending on BTF sample variability. These results compare well with several other BTF compression methods with predefined compression ratios, usually smaller than 1:200. We carried out a psychophysical experiment comparing our method with LPCA method. BTF synthesis from the model was implemented on a standard GPU, yielded interactive framerates. The proposed method allows the fast importance sampling required by eye-path tracing algorithms in image synthesis. [ABSTRACT FROM AUTHOR]

This paper presents a fast, high-quality, GPU-based isosurface rendering pipeline for implicit surfaces defined by a regular volumetric grid. GPUs are designed primarily for use with polygonal primitives, rather than volume primitives, but here we directly treat each volume cell as a single rendering primitive by designing a vertex program and fragment program on a commodity GPU. Compared with previous raycasting methods, ours has a more effective memory footprint (cache locality) and better coherence between multiple parallel SIMD processors. Furthermore, we extend and speed up our approach by introducing a new view-dependent sorting algorithm to take advantage of the early-z-culling feature of the GPU to gain significant performance speed-up. As another advantage, this sorting algorithm makes multiple transparent isosurfaces rendering available almost for free. Finally, we demonstrate the effectiveness and quality of our techniques in several real-time rendering scenarios and include analysis and comparisons with previous work. [ABSTRACT FROM AUTHOR]

Efficient sorting is a key requirement for many computer science algorithms. Acceleration of existing techniques as well as developing new sorting approaches is crucial for many real-time graphics scenarios, database systems, and numerical simulations to name just a few. It is one of the most fundamental operations to organize and filter the ever growing massive amounts of data gathered on a daily basis. While optimal sorting models for serial execution on a single processor exist, efficient parallel sorting remains a challenge. In this paper, we present a hardware-optimized parallel implementation of the radix sort algorithm that results in a significant speed up over existing sorting implementations. We outperform all known General Processing Unit (GPU) based sorting systems by about a factor of two and eliminate restrictions on the sorting key space. This makes our algorithm not only the fastest, but also the first general GPU sorting solution. [ABSTRACT FROM AUTHOR]

High-quality video editing usually requires accurate layer separation in order to resolve occlusions. However, most of the existing bilayer segmentation algorithms require either considerable user intervention or a simple stationary camera configuration with known background, which is difficult to meet for many real world online applications. This paper demonstrates that various visually appealing montage effects can be online created from a live video captured by a rotating camera, by accurately retrieving the camera state and segmenting out the dynamic foreground. The key contribution is that a novel fast bilayer segmentation method is proposed which can effectively extract the dynamic foreground under rotational camera configuration, and is robust to imperfect background estimation and complex background colors. Our system can create a variety of live visual effects, including but not limited to, realistic virtual object insertion, background substitution and blurring, non-photorealistic rendering and camouflage effect. A variety of challenging examples demonstrate the effectiveness of our method. [ABSTRACT FROM AUTHOR]

Animations of characters with flexible bodies such as jellyfish, snails, and, hearts are difficult to design using traditional skeleton-based approaches. A standard approach is keyframing, but adjusting the shape of the flexible body for each key frame is tedious. In addition, the character cannot dynamically adjust its motion to respond to the environment or user input. This paper introduces a new procedural deformation framework (ProcDef) for designing and driving animations of such flexible objects. Our approach is to synthesize global motions procedurally by integrating local deformations. ProcDef provides an efficient design scheme for local deformation patterns; the user can control the orientation and magnitude of local deformations as well as the propagation of deformation signals by specifying line charts and volumetric fields. We also present a fast and robust deformation algorithm based on shape-matching dynamics and show some example animations to illustrate the feasibility of our framework. [ABSTRACT FROM AUTHOR]

Color transfer is an image processing technique which can produce a new image combining one source image's contents with another image's color style. While being able to produce convincing results, however, Reinhard et al.'s pioneering work has two problems—mixing up of colors in different regions and the fidelity problem. Many local color transfer algorithms have been proposed to resolve the first problem, but the second problem was paid few attentions. In this paper, a novel color transfer algorithm is presented to resolve the fidelity problem of color transfer in terms of scene details and colors. It's well known that human visual system is more sensitive to local intensity differences than to intensity itself. We thus consider that preserving the color gradient is necessary for scene fidelity. We formulate the color transfer problem as an optimization problem and solve it in two steps—histogram matching and a gradient-preserving optimization. Following the idea of the fidelity in terms of color and gradient, we also propose a metric for objectively evaluating the performance of example-based color transfer algorithms. The experimental results show the validity and high fidelity of our algorithm and that it can be used to deal with local color transfer. [ABSTRACT FROM AUTHOR]

We developed an interactive system to design a customized cover for a given three-dimensional (3D) object such as a camera, teapot, or car. The system first computes the convex hull of the input geometry. The user segments it into several cloth patches by drawing on the 3D surface. This paper provides two technical contributions. First, it introduces a specialized flattening algorithm for cover patches. It makes each two-dimensional edge in the flattened pattern equal to or longer than the original 3D edge; a smaller patch would fail to cover the object, and a larger patch would result in extra wrinkles. Second, it introduces a mechanism to verify that the user-specified opening would be large enough for the object to be removed. Starting with the initial configuration, the system virtually “pulls” the object out of the cover while avoiding excessive stretching of cloth patches. We used the system to design real covers and confirmed that it functions as intended. [ABSTRACT FROM AUTHOR]

This paper proposes a method for refining existing mesh segmentations, employing a novel extension of the active contour approach to meshes. Given a segmentation, produced either by an automatic segmentation method or interactively, our algorithm propagates the segment boundaries to more appropriate locations. In addition, unlike most segmentation algorithms, our method allows the boundaries to pass through the mesh faces, resulting in smoother curves, particularly visible on coarse meshes. The method is also capable of changing the number of segments, by enabling splitting and merging of boundary curves during the process. Finally, by changing the propagation rules, it is possible to segment the mesh by a variety of criteria, for instance geometric-meaningful segmentations, texture-based segmentations, or constriction-based segmentations. [ABSTRACT FROM AUTHOR]

This paper presents a novel algorithm for hierarchical random accessible mesh decompression. Our approach progressively decompresses the requested parts of a mesh without decoding less interesting parts. Previous approaches divided a mesh into independently compressed charts and a base coarse mesh. We propose a novel hierarchical representation of the mesh. We build this representation by using a boundary-based approach to recursively split the mesh in two parts, under the constraint that any of the two resulting submeshes should be reconstructible independently. In addition to this decomposition technique, we introduce the concepts of opposite vertex and context dependant numbering. This enables us to achieve seemingly better compression ratios than previous work on quad and higher degree polygonal meshes. Our coder uses about 3 bits per polygon for connectivity and 14 bits per vertex for geometry using 12 bits quantification. [ABSTRACT FROM AUTHOR]

This paper proposes a deterministic importance sampling algorithm that is based on the recognition that delta-sigma modulation is equivalent to importance sampling. We propose a generalization for delta-sigma modulation in arbitrary dimensions, taking care of the curse of dimensionality as well. Unlike previous sampling techniques that transform low-discrepancy and highly stratified samples in the unit cube to the integration domain, our error diffusion sampler ensures the proper distribution and stratification directly in the integration domain. We also present applications, including environment mapping and global illumination rendering with virtual point sources. [ABSTRACT FROM AUTHOR]

Efficiently computing robust soft shadows is a challenging and time consuming task. On the one hand, the quality of image-based shadows is inherently limited by the discrete property of their framework. On the other hand, object-based algorithms do not exhibit such discretization issues but they can only efficiently deal with triangles having a constant transmittance factor. This paper addresses this limitation. We propose a general algorithm for the computation of robust and accurate soft shadows for triangles with a spatially varying transmittance. We then show how this technique can be efficiently included into object-based soft shadow algorithms. This results in unified object-based frameworks for computing robust direct shadows for both standard and perforated triangles in fully animated scenes. [ABSTRACT FROM AUTHOR]