Efficient collision detection for composite finite element simulation of cuts in deformable bodies

Composite finite elements (CFEs) based on a hexahedral discretization of the simulation domain have recently shown their effectiveness in physically based simulation of deformable bodies with changing topology. In this paper we present an efficient collision detection method for CFE simulation of cuts. Our method exploits the specific characteristics of CFEs, i.e., the fact that the number of simulation degrees of freedom is significantly reduced. We show that this feature not only leads to a faster deformation simulation, but also enables a faster collision detection. To address the non-conforming properties of geometric composition and hexahedral discretization, we propose a topology-aware interpolation approach for the computation of penetration depth. We show that this approach leads to accurate collision detection on complex boundaries. Our results demonstrate that by using our method cutting on high-resolution deformable bodies including collision detection and response can be performed at interactive rates.     

Realistic haptic rendering of interacting deformable objects in virtual environments

A new computer haptics algorithm to be used in general interactive manipulations of deformable virtual objects is presented. In multimodal interactive simulations, haptic feedback computation often comes from contact forces. Subsequently, the fidelity of haptic rendering depends significantly on contact space modeling. Contact and friction laws between deformable models are often simplified in up to date methods. They do not allow a "realistic" rendering of the subtleties of contact space physical phenomena (such as slip and stick effects due to friction or mechanical coupling between contacts). In this paper, we use Signorini's contact law and Coulomb's friction law as a computer haptics basis. Real-time performance is made possible thanks to a linearization of the behavior in the contact space, formulated as the so-called Delassus operator, and iteratively solved by a Gauss-Seidel type algorithm. Dynamic deformation uses corotational global formulation to obtain the Delassus operator in which the mass and stiffness ratio are dissociated from the simulation time step. This last point is crucial to keep stable haptic feedback. This global approach has been packaged, implemented, and tested. Stable and realistic 6D haptic feedback is demonstrated through a clipping task experiment.     

Incremental Deformation Subspace Reconstruction

Recalculating the subspace basis of a deformable body is a mandatory procedure for subspace simulation, after the body gets modified by interactive applications. However, using linear modal analysis to calculate the basis from scratch is known to be computationally expensive. In the paper, we show that the subspace of a modified body can be efficiently obtained from the subspace of its original version, if mesh changes are small. Our basic idea is to approximate the stiffness matrix by its low‐frequency component, so we can calculate new linear deformation modes by solving an incremental eigenvalue decomposition problem. To further handle nonlinear deformations in the subspace, we present a hybrid approach to calculate modal derivatives from both new and original linear modes. Finally, we demonstrate that the cubature samples trained for the original mesh can be reused in fast reduced force and stiffness matrix evaluation, and we explore the use of our techniques in various simulation problems. Our experiment shows that the updated subspace basis still allows a simulator to generate visual plausible deformation effects. The whole system is efficient and it is compatible with other subspace construction approaches.     

BADF: Bounding Volume Hierarchies Centric Adaptive Distance Field Computation for Deformable Objects on GPUs

We present a novel algorithm BADF (Bounding Volume Hierarchy Based Adaptive Distance Fields) for accelerating the construction of ADFs (adaptive distance fields) of rigid and deformable models on graphics processing units. Our approach is based on constructing a bounding volume hierarchy (BVH) and we use that hierarchy to generate an octree-based ADF. We exploit the coherence between successive frames and sort the grid points of the octree to accelerate the computation. Our approach is applicable to rigid and deformable models. Our GPU-based (graphics processing unit based) algorithm is about 20x--50x faster than current mainstream central processing unit based algorithms. Our BADF algorithm can construct the distance fields for deformable models with 60k triangles at interactive rates on an NVIDIA GTX GeForce 1060. Moreover, we observe 3x speedup over prior GPU-based ADF algorithms.     

Minimal surfaces based object segmentation

A geometric approach for 3D object segmentation and representation is presented. The segmentation is obtained by deformable surfaces moving towards the objects to be detected in the 3D image. The model is based on curvature motion and the computation of surfaces with minimal areas, better known as minimal surfaces. The space where the surfaces are computed is induced from the 3D image (volumetric data) in which the objects are to be detected. The model links between classical deformable surfaces obtained via energy minimization, and intrinsic ones derived from curvature based flows. The new approach is stable, robust, and automatically handles changes in the surface topology during the deformation     

3D Face Modeling from Perspective-Views and Contour-Based Generic-Model

Three-dimensional human head modeling is useful in video-conferencing or other virtual reality applications. However, manual construction of 3D models using CAD tools is often expensive and time-consuming. Here we present a robust and efficient method for the construction of a 3D human head model from perspective images viewing from different angles. In our system, a generic head model is first used, then three images of the head are required to adjust the deformable contours on the generic model to make it closer to the target head. Our contributions are as follows. Our system uses perspective images that are more realistic than orthographic projection approximations used in earlier works. Also, for shaping and positioning face organs, we present a method for estimating the camera focal length and the 3D coordinates of facial landmarks when the camera transformation is known. We also provide an alternative for the 3D coordinates estimation using epipolar geometry when the extrinsic parameters are absent. Our experiments demonstrate that our approach produces good and realistic results.     

Graph-Based Synthesis for Skin Micro Wrinkles

We present a novel graph-based simulation approach for generating micro wrinkle geometry on human skin, which can easily scale up to the micro-meter range and millions of wrinkles. The simulation first samples pores on the skin and treats them as nodes in a graph. These nodes are then connected and the resulting edges become candidate wrinkles. An iterative optimization inspired by pedestrian trail formation is then used to assign weights to those edges, i.e., to carve out the wrinkles. Finally, we convert the graph to a detailed skin displacement map using novel shape functions implemented in graphics shaders. Our simulation and displacement map creation steps expose fine controls over the appearance at real-time framerates suitable for interactive exploration and design. We demonstrate the effectiveness of the generated wrinkles by enhancing state-of-art 3D reconstructions of real human subjects with simulated micro wrinkles, and furthermore propose an artist-driven design flow for adding micro wrinkles to fictional characters.     

通用三维服装模型的强约束动态仿真方法

随着三维游戏和虚拟试衣要求的不断提高,服装仿真已经从布料模拟向服装动态模拟的方向发展,具有真实性、实时性、通用性与交互性的服装仿真技术有很强的研究和实用价值。针对目前算法研究中普遍存在的实时性与通用性不足,提出了一种针对任意三维服装模型的实时仿真方法,将模型顶点和三角面映射为质点的弹簧模型,以克服传统的布料解算器对三维模型的网格限制。利用简便易行的Verlet积分器提高运算效率,并对质点间的形变进行强约束补偿,防止过拉伸(超弹)现象的发生,提高了系统的稳定性。通过实验验证了算法的高效性和可靠性,并可方便地以插件或模块形式与其它软件整合。     

Robust interactive cutting based on an adaptive octree simulation mesh

We present an adaptive octree based approach for interactive cutting of deformable objects. Our technique relies on efficient refine- and node split-operations. These are sufficient to robustly represent cuts in the mechanical simulation mesh. A high-resolution surface embedded into the octree is employed to represent a cut visually. Model modification is performed in the rest state of the object, which is accomplished by back-transformation of the blade geometry. This results in an improved robustness of our approach. Further, an efficient update of the correspondences between simulation elements and surface vertices is proposed. The robustness and efficiency of our approach is underlined in test examples as well as by integrating it into a prototype surgical simulator.     

Approximating global illumination on mesostructure surfaces with height gradient maps

Rendering global illumination for objects with mesostructure surfaces is a time-consuming task, and cannot presently be applied to interactive graphics. This paper presents a real-time rendering method based on a mesostructure height gradient map (MHGM) to exhibit lighting effects on meso-scale details in dynamic environments. We approximate global illumination using a lighting model including three components: incident ambient light, direct light and single bounce indirect light. MHGM is introduced to create local apex sets, which would help us to compute the three components adaptively. Our approach runs entirely on the graphics hardware, and uses deferred shading and the graphics pipeline to accelerate computation. We achieve high quality results which can render meso-scale details with approximate global illumination even for low-resolution geometric models. Moreover, our approach fully supports dynamic scenes and deformable objects.     

Discrete Sibson interpolation

Natural-neighbor interpolation methods, such as Sibson's method, are well-known schemes for multivariate data fitting and reconstruction. Despite its many desirable properties, Sibson's method is computationally expensive and difficult to implement, especially when applied to higher-dimensional data. The main reason for both problems is the method's implementation based on a Voronoi diagram of all data points. We describe a discrete approach to evaluating Sibson's interpolant on a regular grid, based solely on finding nearest neighbors and rendering and blending d-dimensional spheres. Our approach does not require us to construct an explicit Voronoi diagram, is easily implemented using commodity three-dimensional graphics hardware, leads to a significant speed increase compared to traditional approaches, and generalizes easily to higher dimensions. For large scattered data sets, we achieve two-dimensional (2D) interpolation at interactive rates and 3D interpolation (3D) with computation times of a few seconds.     

基于模型的头部运动估计和面部图像合成

文中讨论一种基于模型的头部运动估计和面部图像合成方法。首先建立了一个基于人脸几何模型的可变形三维面部模型,此模型可根据不同人脸图像特征修正特定人脸模型。为了使特定人脸模型与特定人脸图像相匹配,需根据变形模型修正人脸模型。文中采用自动调整与人机交互相结合的方法实现特定人脸模型匹配。在调整完模型形状之后,应用３个方向的面部图像进行纹理映射生成不同视点方向的面部图像。应用合成面部图像与输入面部图像最佳匹     

Maintaining large time steps in explicit finite element simulations using shape matching

We present a novel hybrid method to allow large time steps in explicit integrations for the simulation of deformable objects. In explicit integration schemes, the time step is typically limited by the size and the shape of the discretization elements as well as by the material parameters. We propose a two-step strategy to enable large time steps for meshes with elements potentially destabilizing the integration. First, the necessary time step for a stable computation is identified per element using modal analysis. This allows determining which elements have to be handled specially given a desired simulation time step. The identified critical elements are treated by a geometric deformation model, while the remaining ones are simulated with a standard deformation model (in our case, a corotational linear Finite Element Method). In order to achieve a valid deformation behavior, we propose a strategy to determine appropriate parameters for the geometric model. Our hybrid method allows taking much larger time steps than using an explicit Finite Element Method alone. The total computational costs per second are significantly lowered. The proposed scheme is especially useful for simulations requiring interactive mesh updates, such as for instance cutting in surgical simulations.     

A realistic elastic rod model for real-time simulation of minimally invasive vascular interventions

Simulating intrinsic deformation behaviors of guidewire and catheters for interventional radiology (IR) procedures, such as minimally invasive vascular interventions is a challenging task. Especially real-time simulations for interactive training systems require not only the accuracy of guidewire manipulations, but also the efficiency of computations. The insertion of guidewires and catheters is an essential task for IR procedures and the success of these procedures depends on the accurate navigation of guidewires in complex 3D blood vessel structures to a clinical target, whilst avoiding complications or mistakes of damaging vital tissues and blood vessel walls. In this paper, a novel elastic model for modeling guidewires is presented and evaluated. Our interactive guidewire simulator models the medical instrument as thin flexible elastic rods with arbitrary cross sections, treating the centerline as dynamic and the deformation as quasi-static. Constraints are used to enforce inextensibility of guidewires, providing an efficient computation for bending and twisting modes of the physically-based simulation model. We demonstrate the effectiveness of the new model with a number of simulation examples.     

A generic and scalable pipeline for GPU tetrahedral grid rendering

Recent advances in algorithms and graphics hardware have opened the possibility to render tetrahedral grids at interactive rates on commodity PCs. This paper extends on this work in that it presents a direct volume rendering method for such grids which supports both current and upcoming graphics hardware architectures, large and deformable grids, as well as different rendering options. At the core of our method is the idea to perform the sampling of tetrahedral elements along the view rays entirely in local barycentric coordinates. Then, sampling requires minimum GPU memory and texture access operations, and it maps efficiently onto a feed-forward pipeline of multiple stages performing computation and geometry construction. We propose to spawn rendered elements from one single vertex. This makes the method amenable to upcoming Direct3D 10 graphics hardware which allows to create geometry on the GPU. By only modifying the algorithm slightly it can be used to render per-pixel iso-surfaces and to perform tetrahedral cell projection. As our method neither requires any pre-processing nor an intermediate grid representation it can efficiently deal with dynamic and large 3D meshes.     

Hybrid Geometric — Image Based Rendering

We present a Hybrid Geometric‐Image Based Rendering (HGIBR) system for displaying very complex geometrical models at interactive frame rates. Our approach replaces distant geometry with a combination of image‐based representations and geometry, while rendering nearby objects from geometry. Reference images are computed on demand, which means that no pre‐processing, or additional storage are necessary. We present results for a massive model of a whole offshore gas platform, to demonstrate that interactive frame rates can be maintained using the HGIBR approach. Our implementation runs on a pair of PCs, using commodity graphics hardware for fast 3D warping.     

Interactive Geometric Simulation of 4D Cities

We present a simulation system that can simulate a three-dimensional urban model over time. The main novelty of our approach is that we do not rely on land-use simulation on a regular grid, but instead build a complete and inherently geometric simulation that includes exact parcel boundaries, streets of arbitrary orientation, street widths, 3D street geometry, building footprints, and 3D building envelopes. The second novelty is the fast simulation time and user interaction at interactive speed of about 1 second per time step.     

Building a Large Database of Facial Movements for Deformation Model‐Based 3D Face Tracking

We introduce a new markerless 3D face tracking approach for 2D videos captured by a single consumer grade camera. Our approach takes detected 2D facial features as input and matches them with projections of 3D features of a deformable model to determine its pose and shape. To make the tracking and reconstruction more robust we add a smoothness prior for pose and deformation changes of the faces. Our major contribution lies in the formulation of the deformation prior which we derive from a large database of facial animations showing different (dynamic) facial expressions of a fairly large number of subjects. We split these animation sequences into snippets of fixed length which we use to predict the facial motion based on previous frames. In order to keep the deformation model compact and independent from the individual physiognomy, we represent it by deformation gradients (instead of vertex positions) and apply a principal component analysis in deformation gradient space to extract the major modes of facial deformation. Since the facial deformation is optimized during tracking, it is particularly easy to apply them to other physiognomies and thereby re‐target the facial expressions. We demonstrate the effectiveness of our technique on a number of examples.