CageR: Cage‐Based Reverse Engineering of Animated 3D Shapes

We present CageR: A novel framework for converting animated 3D shape sequences into compact and stable cage‐based representations. Given a raw animated sequence with one‐to‐one point correspondences together with an initial cage embedding, our algorithm automatically generates smoothly varying cage embeddings which faithfully reconstruct the enclosed object deformation. Our technique is fast, automatic, oblivious to the cage coordinate system, provides controllable error and exploits a GPU implementation. At the core of our method, we introduce a new algebraic algorithm based on maximum volume sub‐matrices (maxvol) to speed up and stabilize the deformation inversion. We also present a new spectral regularization algorithm that can apply arbitrary regularization terms on selected subparts of the inversion spectrum. This step allows to enforce a highly localized cage regularization, guaranteeing its smooth variation along the sequence. We demonstrate the speed, accuracy and robustness of our framework on various synthetic and acquired data sets. The benefits of our approach are illustrated in applications such as animation compression and post‐editing.     

Normal-Based Bas-Relief Modelling via Near-Lighting Photometric Stereo

We present a n ear- l ighting p hotometric s tereo (NL-PS) system to produce digital bas-reliefs from a physical object (set) directly. Unlike both the 2D image and 3D model-based modelling methods that require complicated interactions and transformations, the technique using NL-PS is easy to use with cost-effective hardware, providing users with a trade-off between abstract and representation when creating bas-reliefs. Our algorithm consists of two steps: normal map acquisition and constrained 3D reconstruction. First, we introduce a lighting model, named the q uasi- p oint l ighting m odel (QPLM), and provide a two-step calibration solution in our NL-PS system to generate a dense normal map. Second, we filter the normal map into a detail layer and a structure layer, and formulate detail- or structure-preserving bas-relief modelling as a constrained surface reconstruction problem of solving a sparse linear system. The main contribution is a WYSIWYG (i.e. what you see is what you get) way of building new solvers that produces multi-style bas-reliefs with their geometric structures and/or details preserved. The performance of our approach is experimentally validated via comparisons with the state-of-the-art methods.     

A Ray Tracing Approach to Diffusion Curves

Diffusion curves [ [OBW*08] ] provide a flexible tool to create smooth‐shaded images from curves defined with colors. The resulting image is typically computed by solving a Poisson equation that diffuses the curve colors to the interior of the image. In this paper we present a new method for solving diffusion curves by using ray tracing. Our approach is analogous to final gathering in global illumination, where the curves define source radiance whose visible contribution will be integrated at a shading pixel to produce a color using stochastic ray tracing. Compared to previous work, the main benefit of our method is that it provides artists with extended flexibility in achieving desired image effects. Specifically, we introduce generalized curve colors called shaders that allow for the seamless integration of diffusion curves with classic 2D graphics including vector graphics (e.g. gradient fills) and raster graphics (e.g. patterns and textures). We also introduce several extended curve attributes to customize the contribution of each curve. In addition, our method allows any pixel in the image to be independently evaluated, without having to solve the entire image globally (as required by a Poisson‐based approach). Finally, we present a GPU‐based implementation that generates solution images at interactive rates, enabling dynamic curve editing. Results show that our method can easily produce a variety of desirable image effects.     

Inverse Modelling of Incompressible Gas Flow in Subspace

This paper advocates a novel method for modelling physically realistic flow from captured incompressible gas sequence via modal analysis in frequency‐constrained subspace. Our analytical tool is uniquely founded upon empirical mode decomposition (EMD) and modal reduction for fluids, which are seamlessly integrated towards a powerful, style‐controllable flow modelling approach. We first extend EMD, which is capable of processing 1D time series but has shown inadequacies for 3D graphics earlier, to fit gas flows in 3D. Next, frequency components from EMD are adopted as candidate vectors for bases of modal reduction. The prerequisite parameters of the Navier–Stokes equations are then optimized to inversely model the physically realistic flow in the frequency‐constrained subspace. The estimated parameters can be utilized for re‐simulation, or be altered toward fluid editing. Our novel inverse‐modelling technique produces real‐time gas sequences after precomputation, and is convenient to couple with other methods for visual enhancement and/or special visual effects. We integrate our new modelling tool with a state‐of‐the‐art fluid capturing approach, forming a complete pipeline from real‐world fluid to flow re‐simulation and editing for various graphics applications.     

Camera Control in Computer Graphics

Recent progress in modelling, animation and rendering means that rich, high fidelity virtual worlds are found in many interactive graphics applications. However, the viewer's experience of a 3D world is dependent on the nature of the virtual cinematography, in particular, the camera position, orientation and motion in relation to the elements of the scene and the action. Camera control encompasses viewpoint computation, motion planning and editing. We present a range of computer graphics applications and draw on insights from cinematographic practice in identifying their different requirements with regard to camera control. The nature of the camera control problem varies depending on these requirements, which range from augmented manual control (semi‐automatic) in interactive applications, to fully automated approaches. We review the full range of solution techniques from constraint‐based to optimization‐based approaches, and conclude with an examination of occlusion management and expressiveness in the context of declarative approaches to camera control.     

Flow Curves: an Intuitive Interface for Coherent Scene Deformation

Effective composition in visual arts relies on the principle of movement, where the viewer's eye is directed along subjective curves to a center of interest. We call these curves subjective because they may span the edges and/or center‐lines of multiple objects, as well as contain missing portions which are automatically filled by our visual system. By carefully coordinating the shape of objects in a scene, skilled artists direct the viewer's attention via strong subjective curves. While traditional 2D sketching is a natural fit for this task, current 3D tools are object‐centric and do not accommodate coherent deformation of multiple shapes into smooth flows. We address this shortcoming with a new sketch‐based interface called Flow Curves which allows coordinating deformation across multiple objects. Core components of our method include an understanding of the principle of flow, algorithms to automatically identify subjective curve elements that may span multiple disconnected objects, and a deformation representation tailored to the view‐dependent nature of scene movement. As demonstrated in our video, sketching flow curves requires significantly less time than using traditional 3D editing workflows.     

GeoBrush: Interactive Mesh Geometry Cloning

We propose a method for interactive cloning of 3D surface geometry using a paintbrush interface, similar to the continuous cloning brush popular in image editing. Existing interactive mesh composition tools focus on atomic copy‐and‐paste of preselected feature areas, and are either limited to copying surface displacements, or require the solution of variational optimization problems, which is too expensive for an interactive brush interface. In contrast, our GeoBrush method supports real‐time continuous copying of arbitrary high‐resolution surface features between irregular meshes, including topological handles. We achieve this by first establishing a correspondence between the source and target geometries using a novel generalized discrete exponential map parameterization. Next we roughly align the source geometry with the target shape using Green Coordinates with automatically‐constructed cages. Finally, we compute an offset membrane to smoothly blend the pasted patch with C continuity before stitching it into the target. The offset membrane is a solution of a bi‐harmonic PDE, which is computed on the GPU in real time by exploiting the regular parametric domain. We demonstrate the effectiveness of GeoBrush with various editing scenarios, including detail enrichment and completion of scanned surfaces.     

Visibility Editing For All‐Frequency Shadow Design

We present an approach for editing shadows in all‐frequency lighting environments. To support artistic control, we propose to decouple shadowing from lighting and focus on providing intuitive controls to edit the former. To accomplish this task, we precompute and store scene visibility information separately from lighting and BRDFs and allow artists to edit visibility directly, by providing operations to select shadows and edit their shape. To facilitate a wider range of editing operations, we generalize visibility from binary to three‐channel oating point quantities and introduce a novel shadow representation based on computation of visibility ratios between the original render and the edited one. We demonstrate our results for diffuse and glossy surfaces, still scenes and animations.     

Surface Patches from Unorganized Space Curves

Recent 3D sketch tools produce networks of three‐space curves that suggest the contours of shapes. The shapes may be non‐manifold, closed three‐dimensional, open two‐dimensional, or mixed. We describe a system that automatically generates intuitively appealing piecewise‐smooth surfaces from such a curve network, and an intelligent user interface for modifying the automatically chosen surface patches. Both the automatic and the semi‐automatic parts of the system use a linear algebra representation of the set of surface patches to track the topology. On complicated inputs from ILoveSketch [ [BBS08] ], our system allows the user to build the desired surface with just a few mouse‐clicks.     

Experiences in parallelising FLITE3D on the Cray T3D

FLITE3D is an unstructured multigrid Euler-CFD code, originally written by Imperial College, London, and Swansea University, and now developed by British Aerospace. In this paper we present our experiences at EPCC in porting FLITE3D to the Cray T3D MPP system. We discuss the operational requirements of a parallel production CFD code, and introduce the PUL-SM static mesh runtime library. We present performance results for the parallel FLITE3D Euler flow solver running on the UK National Supercomputing Service T3D, and echo our belief that massively parallel systems are a natural tool for commercial CFD modelling today.     

Vega: Non‐Linear FEM Deformable Object Simulator

This practice and experience paper describes a robust C++ implementation of several non‐linear solid three‐dimensional deformable object strategies commonly employed in computer graphics, named the Vega finite element method (FEM) simulation library. Deformable models supported include co‐rotational linear FEM elasticity, Saint–Venant Kirchhoff FEM model, mass–spring system and invertible FEM models: neo‐Hookean, Saint–Venant Kirchhoff and Mooney–Rivlin. We provide several timestepping schemes, including implicit Newmark and backward Euler integrators, and explicit central differences. The implementation of material models is separated from integration, which makes it possible to employ our code not only for simulation, but also for deformable object control and shape modelling. We extensively compare the different material models and timestepping schemes. We provide practical experience and insight gained while using our code in several computer animation and simulation research projects.     

Transparent and Specular Object Reconstruction

This state of the art report covers reconstruction methods for transparent and specular objects or phenomena. While the 3D acquisition of opaque surfaces with Lambertian reflectance is a well‐studied problem, transparent, refractive, specular and potentially dynamic scenes pose challenging problems for acquisition systems. This report reviews and categorizes the literature in this field. Despite tremendous interest in object digitization, the acquisition of digital models of transparent or specular objects is far from being a solved problem. On the other hand, real‐world data is in high demand for applications such as object modelling, preservation of historic artefacts and as input to data‐driven modelling techniques. With this report we aim at providing a reference for and an introduction to the field of transparent and specular object reconstruction. We describe acquisition approaches for different classes of objects. Transparent objects/phenomena that do not change the straight ray geometry can be found foremost in natural phenomena. Refraction effects are usually small and can be considered negligible for these objects. Phenomena as diverse as fire, smoke, and interstellar nebulae can be modelled using a straight ray model of image formation. Refractive and specular surfaces on the other hand change the straight rays into usually piecewise linear ray paths, adding additional complexity to the reconstruction problem. Translucent objects exhibit significant sub‐surface scattering effects rendering traditional acquisition approaches unstable. Different classes of techniques have been developed to deal with these problems and good reconstruction results can be achieved with current state‐of‐the‐art techniques. However, the approaches are still specialized and targeted at very specific object classes. We classify the existing literature and hope to provide an entry point to this exiting field.     

保持区域平滑的3维动画形状高效编辑

目的 基于控制单元的形状编辑效果受各个控制单元对应权重的影响,而计算闭合形式的控制点权重方法难以有效地处理控制骨骼权重。针对3维空间的控制骨骼提出了一种虚拟控制单元插入算法和骨骼关节点标架变换方法,以保持骨骼控制区域的形状,从而得到过渡平滑、形状保持的良好编辑效果。方法 选择C²连续的线性权值计算方法,在用户输入相应的控制单元后,根据控制单元的支持度插入满足条件的虚拟控制点,实现了对动画形状平滑高效的编辑。首先采用离散化的方式,近似求解输入形状构成的封闭域中任意两点之间的内部距离,然后进行Voronoi区域分解,初步获得每个控制单元的控制区域。如果控制点的支持度约束不符合要求,则通过插入虚拟控制点的方式进行调整,并根据邻接关系计算实控制点对虚拟控制点的权重实现实控制点对虚拟控制点的控制。由于算法计算权值和编辑更新顶点可以并行,因此引入图形处理器（graphics processing unit,GPU）实行并行化处理。结果 实验对比了算法在编辑细节以及对不同网格模型的适应性和编辑效率方面的表现,结果表明本文算法在局部细节处不发生过度形变且保持平滑,对非三角网格和多个封闭区域叠加的网格模型依然适用,且本文算法不需要迭代,又有GPU并行计算,编辑时间显著下降。结论 本文算法易于实现,编辑效果过渡平滑,保留细节特征;GPU并行计算极大提高效率,达到实时交互效果。     

Smart Scribbles for Sketch Segmentation

We present ‘Smart Scribbles’—a new scribble‐based interface for user‐guided segmentation of digital sketchy drawings. In contrast to previous approaches based on simple selection strategies, Smart Scribbles exploits richer geometric and temporal information, resulting in a more intuitive segmentation interface. We introduce a novel energy minimization formulation in which both geometric and temporal information from digital input devices is used to define stroke‐to‐stroke and scribble‐to‐stroke relationships. Although the minimization of this energy is, in general, an NP‐hard problem, we use a simple heuristic that leads to a good approximation and permits an interactive system able to produce accurate labellings even for cluttered sketchy drawings. We demonstrate the power of our technique in several practical scenarios such as sketch editing, as‐rigid‐as‐possible deformation and registration, and on‐the‐fly labelling based on pre‐classified guidelines.     

BendyLights: Artistic Control of Direct Illumination by Curving Light Rays

In computer cinematography, artists routinely use non‐physical lighting models to achieve desired appearances. This paper presents BendyLights, a non‐physical lighting model where light travels nonlinearly along splines, allowing artists to control light direction and shadow position at different points in the scene independently. Since the light deformation is smoothly defined at all world‐space positions, the resulting non‐physical lighting effects remain spatially consistent, avoiding the frequent incongruences of many non‐physical models. BendyLights are controlled simply by reshaping splines, using familiar interfaces, and require very few parameters. BendyLight control points can be keyframed to support animated lighting effects. We demonstrate BendyLights both in a realtime rendering system for editing and a production renderer for final rendering, where we show that BendyLights can also be used with global illumination.     

Taylor Prediction for Mesh Geometry Compression

In this paper, we introduce a new formalism for mesh geometry prediction. We derive a class of smooth linear predictors from a simple approach based on the Taylor expansion of the mesh geometry function. We use this method as a generic way to compute weights for various linear predictors used for mesh compression and compare them with those of existing methods. We show that our scheme is actually equivalent to the Modified Butterfly subdivision scheme used for wavelet mesh compression. We also build new efficient predictors that can be used for connectivity‐driven compression in place of other schemes like Average/Dual Parallelogram Prediction and High Degree Polygon Prediction. The new predictors use the same neighbourhood, but do not make any assumption on mesh anisotropy. In the case of Average Parallelogram Prediction, our new weights improve compression rates from 3% to 18% on our test meshes. For Dual Parallelogram Prediction, our weights are equivalent to those of the previous Freelence approach, that outperforms traditional schemes by 16% on average. Our method effectively shows that these weights are optimal for the class of smooth meshes. Modifying existing schemes to make use of our method is free because only the prediction weights have to be modified in the code.     

Component‐wise Controllers for Structure‐Preserving Shape Manipulation

Recent shape editing techniques, especially for man‐made models, have gradually shifted focus from maintaining local, low‐level geometric features to preserving structural, high‐level characteristics like symmetry and parallelism. Such new editing goals typically require a pre‐processing shape analysis step to enable subsequent shape editing. Observing that most editing of shapes involves manipulating their constituent components, we introduce component‐wise controllers that are adapted to the component characteristics inferred from shape analysis. The controllers capture the natural degrees of freedom of individual components and thus provide an intuitive user interface for editing. A typical model usually results in a moderate number of controllers, allowing easy establishment of semantic relations among them by automatic shape analysis supplemented with user interaction. We propose a component‐wise propagation algorithm to automatically preserve the established inter‐relations while maintaining the defining characteristics of individual controllers and respecting the user‐specified modeling constraints. We extend these ideas to a hierarchical setup, allowing the user to adjust the tool complexity with respect to the desired modeling complexity. We demonstrate the effectiveness of our technique on a wide range of man‐made models with structural features, often containing multiple connected pieces.     

Translational Covering of Closed Planar Cubic B-Spline Curves

Spline curves are useful in a variety of geometric modeling and graphics applications and covering problems abound in practical settings. This work defines a class of covering decision problems for shapes bounded by spline curves. As a first step in addressing these problems, this paper treats translational spline covering for planar, uniform, cubic B‐splines. Inner and outer polygonal approximations to the spline regions are generated using enclosures that are inside two different types of piecewise‐linear envelopes. Our recent polygonal covering technique is then applied to seek translations of the covering shapes that allow them to fully cover the target shape. A feasible solution to the polygonal instance provides a feasible solution to the spline instance. We use our recent proof that 2D translational polygonal covering is NP‐hard to establish NP‐hardness of our planar translational spline covering problem. Our polygonal approximation strategy creates approximations that are tight, yet the number of vertices is only a linear function of the number of control points. Using recent results on B‐spline curve envelopes, we bound the distance from the spline curve to its approximation. We balance the two competing objectives of tightness vs. number of points in the approximation, which is crucial given the NP‐hardness of the spline problem. Examples of the results of our spline covering work are provided for instances containing as many as six covering shapes, including both convex and nonconvex regions. Our implementation uses the LEDA and CGAL C++ libraries of geometric data structures and algorithms.