Automatic Cage Building with Quadric Error Metrics

Modern computer graphics applications usually require high resolution object models for realistic rendering.However,it is expensive and difficult to deform such models in real time.In order to reduce the computational cost during deformations,a dense model is often manipulated through a simplified structure,called cage,which envelops the model.However,cages are usually built interactively by users,which is tedious and time-consuming.In this paper,we introduce a novel method that can build cages automatically for both 2D polygons and 3D triangular meshes.The method consists of two steps:1) simplifying the input model with quadric error metrics and quadratic programming to build a coarse cage;2) removing the self-intersections of the coarse cage with Delaunay partitions.With this new method,a user can build a cage to envelop an input model either entirely or partially with the approximate vertex number the user specifies.Experimental results show that,compared to other cage building methods with the same number of vertex,cages built by our method are more similar to the input models.Thus,the dense models can be manipulated with higher accuracy through our cages.     

Augmented Lagrangian Method for Generalized TV-Stokes Model

In this paper, we propose a general form of TV-Stokes models and provide an efficient and fast numerical algorithm based on the augmented Lagrangian method. The proposed model and numerical algorithm can be used for a number of applications such as image inpainting, image decomposition, surface reconstruction from sparse gradient, direction denoising, and image denoising. Comparing with properties of different norms in regularity term and fidelity term, various results are investigated in applications. We numerically show that the proposed model recovers jump discontinuities of a data and discontinuities of the data gradient while reducing stair-case effect.     

A painting interface for interactive surface deformations

A long-standing challenge in geometric modeling is providing a natural, intuitive interface for making local deformations to 3D surfaces. Previous approaches have provided either interactive manipulation or physical simulation to control surface deformations. In this paper, we investigate combining these two approaches with a painting interface that gives the user direct, local control over a physical simulation. The “paint” a user applies to the model defines its instantaneous surface velocity. By interactively simulating this velocity, the user can effect surface deformations. We have found that this painting metaphor gives the user direct, local control over surface deformations for several applications: creating new models, removing noise from existing models, and adding geometric texture to an existing surface at multiple scales.     

A fast parametric deformation mechanism for virtual reality applications

Virtual reality technologies have been adopted in a wide variety of applications for its interactive ability and realistic senses. Despite early implementations regard VR only as a medium for lively animation; a practical VR work must deliver precise deformation on virtual objects based on real-time interactions. The exact ability is especially important for users who utilize VR to do collaborative design, for it will greatly reduce the amount of on-line computations on operating substance-based interactions, and consequently facilitates the collaboration. Therefore, this research will employ neural networks to memorize the deformation behavior of solid objects, and then perform instant and accurate deformations in the virtual environment. The proposed method also allows design variations for parametric features, and uses feature parameters as variable switches to adjust the deformation mechanism. There are three steps in the method: (1) For a sample object, generate force-induced deformations using the finite-element method; (2) memorize the surface displacements with artificial neural networks; and (3) convert the parametric deformation matrices into Behavioral Modules for the virtual reality engine. In the implementations, ANSYS is used to generate model deformations, and MATLAB is used to perform neural training. Finally, a virtual environment is built using Virtools where customized Building Blocks are created to present interactive deformation behavior. Experiments were carried out on an Intel XEON workstation with nVIDIA Quadro4 750GL display device. Sample workparts are tested to examine the ability of the method. The results show that both training accuracy and real-time capability are more than satisfactory.     

TeCo3D—Sharing Interactive and Dynamic 3D Models

In this paper we present a method for sharing interactive and dynamic 3D models that are collaboration-unaware, i.e., models that have not been designed to be used by multiple users at the same time. This functionality is an essential requirement for the inclusion of arbitrary 3D models, as generated by standard CAD or animation software, into teleconferencing sessions. A key aim of this work is to show that a large part of the required functionality can be developed in a way so that it is reusable for other applications such as shared whiteboards or networked computer games. Our method therefore consists of both an application dependent part that handles the specific tasks required for sharing 3D models, and of a number of generic services such as synchronization, scalable support for latecomers, and the ability to record and replay sessions. The generic services are based on an abstract media model and the RTP/I application level protocol for distributed interactive media. Any other application for a medium that shares this model and that uses RTP/I may reuse these generic services. We have implemented a prototype called TeCo3D demonstrating the feasibility of our approach.     

Interactive real-time physics: An intuitive approach to form-finding and structural analysis for design and education

Real-time physics simulation has been extensively used in computer games, but its potential has yet to be fully realized in design and education. We present an interactive 3D physics engine with a wide variety of applications.In common with traditional FEM, the use of a local element stiffness matrix is retained. However, unlike typical non-linear FEM routines elements forces, moments and inertia are appropriately lumped at nodes following the dynamic relaxation method. A semi-implicit time integration scheme updates linear and angular momentum, and subsequently the local coordinate frames of the nodes. A co-rotational approach is used to compute the resultant field of displacements in global coordinates including the effect of large deformations. The results obtained compare well against established commercial software.We demonstrate that the method presented allows the making of interactive structural models that can be used in teaching to develop an intuitive understanding of structural behaviour. We also show that the same interactive physics framework allows real-time optimization that can be used for geometric and structural design applications.     

A hyper elasticity method for interactive virtual design of hearing aids

We present a computational efficient method for isotropic hyper elasticity based on functional analysis. By selecting a class of shape functions, we arrive at a computational scheme which yields very sparse tensors. This enables fast computations of the hyper elastic energy potential and its derivatives. We achieve efficiency and performance through the use of shape functions that are linear in their parameters and through rotation into the eigenspace of the right Cauchy–Green strain tensor. This makes near real time evaluation of hyper elasticity of complex meshes on CPU relatively easy to implement. The approach does not rely on a specific shape function or material model but offers a general framework for isotropic hyper elasticity. The method is aimed at interactive and accurate non-linear hyper elastic modeling for a wide range of industrial virtual design applications, which we exemplify by insertion of hearing aid domes into the ear canal. We validate the method for tetrahedral meshes with linear shape functions with an Ogden material model by comparing simulations to deformations of real material. We illustrate the use of other shape functions and models using uniform cubic B-splines in combination with Riemannian elasticity.     

Jacobians and Hessians of mean value coordinates for closed triangular meshes

Mean value coordinates provide an efficient mechanism for the interpolation of scalar functions defined on orientable domains with a nonconvex boundary. They present several interesting features, including the simplicity and speed that yield from their closed-form expression. In several applications though, it is desirable to enforce additional constraints involving the partial derivatives of the interpolated function, as done in the case of the Green coordinates approximation scheme (Ben-Chen, Weber, Gotsman, ACM Trans. Graph.:1–11, 2009) for interactive 3D model deformation. In this paper, we introduce the analytic expressions of the Jacobian and the Hessian of functions interpolated through mean value coordinates. We provide these expressions both for the 2D and 3D case. We also provide a thorough analysis of their degenerate configurations along with accurate approximations of the partial derivatives in these configurations. Extensive numerical experiments show the accuracy of our derivation. In particular, we illustrate the improvements of our formulae over a variety of finite differences schemes in terms of precision and usability. We demonstrate the utility of this derivation in several applications, including cage-based implicit 3D model deformations (i.e., variational MVC deformations). This technique allows for easy and interactive model deformations with sparse positional, rotational, and smoothness constraints. Moreover, the cages produced by the algorithm can be directly reused for further manipulations, which makes our framework directly compatible with existing software supporting mean value coordinates based deformations.     

Efficient prime-based method for interactive mining of frequent patterns

Over the past decade, an increasing number of efficient algorithms have been proposed to mine frequent patterns by satisfying the minimum support threshold. Generally, determining an appropriate value for minimum support threshold is extremely difficult. This is because the appropriate value depends on the type of application and expectation of the user. Moreover, in some real-time applications such as web mining and e-business, finding new correlations between patterns by changing the minimum support threshold is needed. Since rerunning mining algorithms from scratch is very costly and time-consuming, researchers have introduced interactive mining of frequent patterns. Recently, a few efficient interactive mining algorithms have been proposed, which are able to capture the content of transaction database to eliminate possibility of the database rescanning. In this paper, we propose a new method based on prime number and its characteristics mainly for interactive mining of frequent patterns. Our method isolates the mining model from the mining process such that once the mining model is constructed; it can be frequently used by mining process with various minimum support thresholds. During the mining process, the mining algorithm reduces the number of candidate patterns and comparisons by using a new candidate set called candidate head set and several efficient pruning techniques. The experimental results verify the efficiency of our method for interactive mining of frequent patterns.     

Flexible bones for the haptic prototyping of deformable objects

Accurate modelling of the compliance characteristics of solid models is an important rendering task for increasing the realism of virtual environments. The ability to feel the force and moment stress resultants that cause the bending, twisting, shearing and/or fracture of physically-based models is useful for a large number of application areas including medical training, CAD environments, computer animation and games. An important element of compliance rendering is the mechanics engine that solves the equations governing the deformations and stresses in solid models. The development of such engines has to carefully balance the needs for haptic (not just graphical) realism with the needs for real time processing at rates in the range of 500-1000 Hz. In this paper we describe methods and techniques we have developed for such an engine, and demonstrate their characteristics in a number of applications including design of compliant mechanisms, animation and solid modelling.     

An atmospheric visual analysis and exploration system

Meteorological research involves the analysis of multi-field, multi-scale, and multi-source data sets. In order to better understand these data sets, models and measurements at different resolutions must be analyzed. Unfortunately, traditional atmospheric visualization systems only provide tools to view a limited number of variables and small segments of the data. These tools are often restricted to two-dimensional contour or vector plots or three-dimensional isosurfaces. The meteorologist must mentally synthesize the data from multiple plots to glean the information needed to produce a coherent picture of the weather phenomenon of interest. In order to provide better tools to meteorologists and reduce system limitations, we have designed an integrated atmospheric visual analysis and exploration system for interactive analysis of weather data sets. Our system allows for the integrated visualization of 1D, 2D, and 3D atmospheric data sets in common meteorological grid structures and utilizes a variety of rendering techniques. These tools provide meteorologists with new abilities to analyze their data and answer questions on regions of interest, ranging from physics-based atmospheric rendering to illustrative rendering containing particles and glyphs. In this paper, we will discuss the use and performance of our visual analysis for two important meteorological applications. The first application is warm rain formation in small cumulus clouds. Here, our three-dimensional, interactive visualization of modeled drop trajectories within spatially correlated fields from a cloud simulation has provided researchers with new insight. Our second application is improving and validating severe storm models, specifically the Weather Research and Forecasting (WRF) model. This is done through correlative visualization of WRF model and experimental Doppler storm data.     

A Deterministic Algorithm for Reconstructing Images with Interacting Discontinuities

The most common approach for incorporating discontinuities in visual reconstruction problems makes use of Bayesian techniques, based on Markov random field models, coupled with stochastic relaxation and simulated annealing. Despite their convergence properties and flexibility in exploiting a priori knowledge on physical and geometric features of discontinuities, stochastic relaxation algorithms often present insurmountable computational complexity. Recently, considerable attention has been given to suboptimal deterministic algorithms, which can provide solutions with much lower computational costs. These algorithms consider the discontinuities implicitly rather than explicitly and have been mostly derived when there are no interactions between two or more discontinuities in the image model. In this paper we propose an algorithm that allows for interacting discontinuities, in order to exploit the constraint that discontinuities must be connected and thin. The algorithm, called E-GNC, can be considered an extension of the graduated nonconvexity (GNC), first proposed by Blake and Zisserman for noninteracting discontinuities. When applied to the problem of image reconstruction from sparse and noisy data, the method is shown to give satisfactory results with a low number of iterations.     

Data‐Driven Shape Interpolation and Morphing Editing

Shape interpolation has many applications in computer graphics such as morphing for computer animation. In this paper, we propose a novel data‐driven mesh interpolation method. We adapt patch‐based linear rotational invariant coordinates to effectively represent deformations of models in a shape collection, and utilize this information to guide the synthesis of interpolated shapes. Unlike previous data‐driven approaches, we use a rotation/translation invariant representation which defines the plausible deformations in a global continuous space. By effectively exploiting the knowledge in the shape space, our method produces realistic interpolation results at interactive rates, outperforming state‐of‐the‐art methods for challenging cases. We further propose a novel approach to interactive editing of shape morphing according to the shape distribution. The user can explore the morphing path and select example models intuitively and adjust the path with simple interactions to edit the morphing sequences. This provides a useful tool to allow users to generate desired morphing with little effort. We demonstrate the effectiveness of our approach using various examples.     

Nonlinear Deformation Synthesis via Sparse Principal Geodesic Analysis

This paper introduces the construction of a low-dimensional nonlinear space capturing the variability of a non-rigid shape from a data set of example poses. The core of the approach is a Sparse Principal Geodesic Analysis (SPGA) on the Riemannian manifold of discrete shells, in which a pose of a non-rigid shape is a point. The SPGA is invariant to rigid body motions of the poses and supports large deformation. Since the Riemannian metric measures the membrane and bending distortions of the shells, the sparsity term forces the modes to describe largely decoupled and localized deformations. This property facilitates the analysis of articulated shapes. The modes often represent characteristic articulations of the shape and usually come with a decomposing of the spanned subspace into low-dimensional widely decoupled subspaces. For example, for human models, one expects distinct, localized modes for the bending of elbow or knee whereas some more modes are required to represent shoulder articulation. The decoupling property can be used to construct useful starting points for the computation of the nonlinear deformations via a superposition of shape submanifolds resulting from the decoupling. In a preprocessing stage, samples of the individual subspaces are computed, and, in an online phase, these are interpolated multilinearly. This accelerates the construction of nonlinear deformations and makes the method applicable for interactive applications. The method is compared to alternative approaches and the benefits are demonstrated on different kinds of input data.     

A fast interactive reverse-engineering system

A new method of reverse engineering for fast, simple and interactive acquisition and reconstruction of a virtual three-dimensional (3D) model is presented. We propose an active stereo acquisition system, which makes use of two infrared cameras and a wireless active-pen device, supported by a reconstruction method based on subdivision surfaces. In the 3D interactive hand sketching process the user draws and refines the 3D style-curves, which characterize the shape to be constructed, by simply dragging the active-pen device; then the system automatically produces a low-resolution mesh that is naturally refined through subdivision surfaces. Several examples demonstrate the ability of the proposed advanced design methodology to produce complex 3D geometric models by the interactive and iterative process that provides the user with a real-time visual feedback on the ongoing work.     

Succinct Palette and Color Model Generation and Manipulation Using Hierarchical Representation

We propose a new method to obtain the representative colors and their distributions of an image. Our intuition is that it is possible to derive the global model from the local distributions. Beginning by sampling pure colors, we build a hierarchical representation of colors in the image via a bottom‐up approach. From the resulting hierarchy, we can obtain satisfactory palettes/color models automatically without a predefined size. Furthermore, we provide interactive operations to manipulate the results which allow the users to reflect their intention directly. In our experiment, we show that the proposed method produces more succinct results that faithfully represent all the colors in the image with an appropriate number of components. We also show that the proposed interactive approach can improve the results of applications such as recoloring and soft segmentation.     

Focus+Context visualization with distortion minimization

The need to examine and manipulate large surface models is commonly found in many science, engineering, and medical applications. On a desktop monitor, however, seeing the whole model in detail is not possible. In this paper, we present a new, interactive Focus+Context method for visualizing large surface models. Our method, based on an energy optimization model, allows the user to magnify an area of interest to see it in detail while deforming the rest of the area without perceivable distortion. The rest of the surface area is essentially shrunk to use as little of the screen space as possible in order to keep the entire model displayed on screen. We demonstrate the efficacy and robustness of our method with a variety of models.     

Partitioning and Handling Massive Models for Interactive Collision Detection

We describe an approach for interactive collision detection and proximity computations on massive models composed of millions of geometric primitives. We address issues related to interactive data access and processing in a large geometric database, which may not fit into main memory of typical desktop workstations or computers. We present a new algorithm using overlap graphs for localizing the "regions of interest" within a massive model, thereby reducing runtime memory requirements. The overlap graph is computed off-line, pre-processed using graph partitioning algorithms, and modified on the fly as needed. At run time, we traverse localized sub-graphs to check the corresponding geometry for proximity and pre-fetch geometry and auxiliary data structures. To perform interactive proximity queries, we use bounding-volume hierarchies and take advantage of spatial and temporal coherence. Based on the proposed algorithms, we have developed a system called IMMPACT and used it for interaction with a CAD model of a power plant consisting of over 15 million triangles. We are able to perform a number of proximity queries in real-time on such a model. In terms of model complexity and application to large models, we have improved the performance of interactive collision detection and proximity computation algorithms by an order of magnitude.     

Physics-based character skinning using multidomain subspace deformations

In this extended version of our Symposium on Computer Animation paper, we describe a domain-decomposition method to simulate articulated deformable characters entirely within a subspace framework. We have added a parallelization and eigendecomposition performance analysis, and several additional examples to the original symposium version. The method supports quasistatic and dynamic deformations, nonlinear kinematics and materials, and can achieve interactive time-stepping rates. To avoid artificial rigidity, or “locking,” associated with coupling low-rank domain models together with hard constraints, we employ penaltybased coupling forces. The multidomain subspace integrator can simulate deformations efficiently, and exploits efficient subspace-only evaluation of constraint forces between rotated domains using a novel Fast Sandwich Transform (FST). Examples are presented for articulated characters with quasistatic and dynamic deformations, and interactive performance with hundreds of fully coupled modes. Using our method, we have observed speedups of between 3 and 4 orders of magnitude over full-rank, unreduced simulations.