Geometric multigrid (GMG) methods are a fundamental tool for efficiently solving large sparse linear systems. A requirement for GMG is a hierarchy of grids; however, many practical volumetric domains are available only as single, irregular tetrahedral meshes, making the construction of a multigrid hierarchy necessary. Existing approaches often trade off speed against hierarchy quality: remeshing- or coarsening-based methods can be expensive to construct, whereas graph-based techniques are fast but often yield weaker multigrid performance. We introduce GravoTet, which bridges this gap by combining geometric structure with graph-based efficiency to construct fast and effective multigrid hierarchies. GravoTet builds a vertex hierarchy and then generates graph-Voronoi diagrams whose dual cells define coarse tetrahedra, enabling rapid construction of multigrid levels. Boundary elements are explicitly prioritized during both sampling and tet generation to preserve boundary. In our evaluation, we solve Poisson and biharmonic problems on irregular tetrahedral meshes and compare GravoTet against state-of-the-art geometric multigrid, algebraic multigrid and direct solvers, demonstrating superior performance, particularly on large meshes.

Abstract We introduce stylized phase manifolds—a compact, interpretable latent representation that disentangles motion content (e.g. “jumping”, “walking”), the temporal structure (e.g. motion cycle frequency, gait timing), and style (i.e. how the motion is performed). Learned in an unsupervised manner and inherently low‐dimensional, the manifold offers intuitive and flexible editing. Building on this representation, we develop a diffusion‐based motion generator that enables fine‐grained control over semantic, temporal, and stylistic aspects of motion. To connect high‐level intent with low‐level motion, we treat the stylized manifold as an intermediate representation—a structured bridge between natural language and motion. By first mapping text into this manifold, our two‐stage pipeline improves the control over for text‐based motion generation, while producing high‐quality, diverse motion outputs.

We present an analytical framework for exploring the design space of hinged kirigami structures that deploy rigidly and uniformly. A hinged kirigami structure consists of rigid planar faces connected by hinges, and is deployable if the faces can rotate about the hinges without deformation. Such deployability depends on both the topology and the geometry, i.e., the combinatorial connectivity of the faces and their spatial embedding. Prior work studies geometric constraints for uniform deployability in restricted settings, most notably quadrilateral kirigami patterns and structures derived from 2-colorable planar graphs. However, existing analysis does not readily generalize to arbitrary kirigami structures, nor does it provide a systematic approach for constructing deployable kirigami from non-2-colorable planar graphs (e.g., graphs with non-manifold embeddings). Moreover, while geometric conditions for deployability have been partially investigated, the structure of the full deployable design space and its associated degrees of freedom remain largely unexplored. In this work, we propose a new framework that enables the derivation of hinged kirigami structures from arbitrary planar graphs, with the key feature that multiple distinct kirigami structures can be generated from the same graph. We derive geometric constraints that ensure uniform rigid deployability and analytically characterize the full design space of deployable embeddings, including its associated degrees of freedom. This characterization allows continuous navigation of the design space and provides a systematic foundation for the design of kirigami-based mechanical metamaterials.

Apparel is essential to human life, offering protection, mirroring cultural identities, and showcasing personal style. Yet, the creation of garments remains a time-consuming process, largely due to the manual work involved in designing them. To simplify this process, we introduce AIpparel, a multimodal foundation model for generating and editing sewing patterns. Our model fine-tunes state-of-the-art large multimodal models (LMMs) on a custom-curated large-scale dataset of over 120,000 unique garments, each with multimodal annotations including text, images, and sewing patterns. Additionally, we propose a novel tokenization scheme that concisely encodes these complex sewing patterns so that LLMs can learn to predict them efficiently. AIpparel achieves state-of-the-art performance in single-modal tasks, including text-to-garment and image-to-garment prediction, and enables novel multimodal garment generation applications such as interactive garment editing. The project website is at https: //georgenakayama.github.io/AIpparel/.

We present a computational framework for designing geometric metamaterials capable of approximating freeform 3D surfaces via rotationally deployable kirigami patterns. While prior inverse design methods typically rely on standard, well-studied patterns, such as equilateral triangles or quadrilaterals, we step back to examine the broader design space of the patterns themselves. Specifically, we derive principled rules to determine whether a given planar tiling can be cut into a rotationally deployable hinged kirigami structure with possible curvature adaptation. These insights allow us to generate and validate a broad family of novel tiling patterns beyond traditional examples. We further analyze two key deployment states of a general pattern: the commonly used maximal area expansion, and the maximal rotation angle reached just before face collisions occur, which we adopt as the default for inverse design as it allows for simple deployment in practice, i.e., rotating the faces to their natural limit. Finally, we solve the inverse problem: given a target 3D surface, we compute a planar tiling that, when cut and deployed to its maximal rotation angle, approximates the input geometry. We show that for a subset of patterns, the deployed configurations are hole-free, demonstrating that curvature can be achieved from planar sheets through local combinatorial changes. Our experiments, including physical fabrications, demonstrate the effectiveness of our approach and validate a wide range of previously unexplored patterns that are both physically realizable and geometrically expressive.

Abstract Vectorizing line drawings is a repetitive, yet necessary task that professional creatives must perform to obtain an easily editable and scalable digital representation of a raster sketch. State‐of‐the‐art automatic methods in this domain can create series of curves that closely fit the appearance of the drawing. However, they often neglect the line parameterization. Thus, their vector representation cannot be edited naturally by following the drawing order. We present a novel method for single‐line drawing vectorization that addresses this issue. Single‐line drawings consist of a single stroke, where the line can intersect itself multiple times, making the drawing order non‐trivial to recover. Our method fits a single parametric curve, represented as a Bézier spline, to approximate the stroke in the input raster image. To this end, we produce a graph representation of the input and employ geometric priors and a specially trained neural network to correctly capture and classify curve intersections and their traversal configuration. Our method is easily extended to drawings containing multiple strokes while preserving their integrity and order. We compare our vectorized results with the work of several artists, showing that our stroke order is similar to the one artists employ naturally. Our vectorization method achieves state‐of‐the‐art results in terms of similarity with the original drawing and quality of the vectorization on a benchmark of single‐line drawings. Our method's results can be refined interactively, making it easy to integrate into professional workflows. Our code and results are available at https://github.com/tanguymagne/SLD‐Vectorization.

We introduce TetWeave, a novel isosurface representation for gradient-based mesh optimization that jointly optimizes the placement of a tetrahedral grid used for Marching Tetrahedra and a novel directional signed distance at each point. TetWeave constructs tetrahedral grids on-the-fly via Delaunay triangulation, enabling increased flexibility compared to predefined grids. The extracted meshes are guaranteed to be watertight, two-manifold and intersection-free. The flexibility of TetWeave enables a resampling strategy that places new points where reconstruction error is high and allows to encourage mesh fairness without compromising on reconstruction error. This leads to high-quality, adaptive meshes that require minimal memory usage and few parameters to optimize. Consequently, TetWeave exhibits near-linear memory scaling relative to the vertex count of the output mesh — a substantial improvement over predefined grids. We demonstrate the applicability of TetWeave to a broad range of challenging tasks in computer graphics and vision, such as multi-view 3D reconstruction, mesh compression and geometric texture generation. Our code is available at https://github.com/AlexandreBinninger/TetWeave.

Low-resolution quantized imagery, such as pixel art, is seeing a revival in modern applications ranging from video game graphics to digital design and fabrication, where creativity is often bound by a limited palette of elemental units. Despite their growing popularity, the automated generation of quantized images from raw inputs remains a significant challenge, often necessitating intensive manual input. We introduce SD-$\pi$XL, an approach for producing quantized images that employs score distillation sampling in conjunction with a differentiable image generator. Our method enables users to input a prompt and optionally an image for spatial conditioning, set any desired output size $H \times W$, and choose a palette of $n$ colors or elements. Each color corresponds to a distinct class for our generator, which operates on an $H \times W \times n$ tensor. We adopt a softmax approach, computing a convex sum of elements, thus rendering the process differentiable and amenable to backpropagation. We show that employing Gumbel-softmax reparameterization allows for crisp pixel art effects. Unique to our method is the ability to transform input images into low-resolution, quantized versions while retaining their key semantic features. Our experiments validate SD-$\pi$XL's performance in creating visually pleasing and faithful representations, consistently outperforming the current state-of-the-art. Furthermore, we showcase SD-$\pi$XL's practical utility in fabrication through its applications in interlocking brick mosaic, beading and embroidery design.

Abstract A parameterization of a triangle mesh is a realization in the plane so that all triangles have positive signed area. Triangle mesh parameterizations are commonly computed by minimizing a distortion energy, measuring the distortions of the triangles as they are mapped into the parameter domain. It is assumed that the triangulation is fixed and the triangles are mapped affinely. We consider a more general setup and additionally optimize among the intrinsic triangulations of the piecewise linear input geometry. This means the distortion energy is computed for the same geometry, yet the space of possible parameterizations is enlarged. For minimizing the distortion energy, we suggest alternating between varying the parameter locations of the vertices and intrinsic flipping. We show that this process improves the mapping for different distortion energies at moderate additional cost. We also find intrinsic triangulations that are better starting points for the optimization of positions, offering a compromise between the full optimization approach and exploiting the additional freedom of intrinsic triangulations.

Abstract We present SENS, a novel method for generating and editing 3D models from hand‐drawn sketches, including those of abstract nature. Our method allows users to quickly and easily sketch a shape, and then maps the sketch into the latent space of a part‐aware neural implicit shape architecture. SENS analyzes the sketch and encodes its parts into ViT patch encoding, subsequently feeding them into a transformer decoder that converts them to shape embeddings suitable for editing 3D neural implicit shapes. SENS provides intuitive sketch‐based generation and editing, and also succeeds in capturing the intent of the user's sketch to generate a variety of novel and expressive 3D shapes, even from abstract and imprecise sketches. Additionally, SENS supports refinement via part reconstruction, allowing for nuanced adjustments and artifact removal. It also offers part‐based modeling capabilities, enabling the combination of features from multiple sketches to create more complex and customized 3D shapes. We demonstrate the effectiveness of our model compared to the state‐of‐the‐art using objective metric evaluation criteria and a user study, both indicating strong performance on sketches with a medium level of abstraction. Furthermore, we showcase our method's intuitive sketch‐based shape editing capabilities, and validate it through a usability study.

Abstract Garment alteration is a practical technique to adapt an existing garment to fit a target body shape. Typically executed by skilled tailors, this process involves a series of strategic fabric operations—removing or adding material—to achieve the desired fit on a target body. We propose an innovative approach to automate this process by computing a set of practically feasible modifications that adapt an existing garment to fit a different body shape. We first assess the garment's fit on a reference body; then, we replicate this fit on the target by deriving a set of pattern modifications via a linear program. We compute these alterations by employing an iterative process that alternates between global geometric optimization and physical simulation. Our method utilizes geometry‐based simulation of woven fabric's anisotropic behavior, accounts for tailoring details like seam matching, and incorporates elements such as darts or gussets. We validate our technique by producing digital and physical garments, demonstrating practical and achievable alterations.

Abstract Data driven and learning based solutions for modeling dynamic garments have significantly advanced, especially in the context of digital humans. However, existing approaches often focus on modeling garments with respect to a fixed parametric human body model and are limited to garment geometries that were seen during training. In this work, we take a different approach and model the dynamics of a garment by exploiting its local interactions with the underlying human body. Specifically, as the body moves, we detect local garment‐body collisions, which drive the deformation of the garment. At the core of our approach is a mesh‐agnostic garment representation and a manifold‐aware transformer network design, which together enable our method to generalize to unseen garment and body geometries. We evaluate our approach on a wide variety of garment types and motion sequences and provide competitive qualitative and quantitative results with respect to the state of the art.

Abstract Creating plausible motions for a diverse range of characters is a long‐standing goal in computer graphics. Current learning‐based motion synthesis methods rely on large‐scale motion datasets, which are often difficult if not impossible to acquire. On the other hand, pose data is more accessible, since static posed characters are easier to create and can even be extracted from images using recent advancements in computer vision. In this paper, we tap into this alternative data source and introduce a neural motion synthesis approach through retargeting, which generates plausible motion of various characters that only have pose data by transferring motion from one single existing motion capture dataset of another drastically different characters. Our experiments show that our method effectively combines the motion features of the source character with the pose features of the target character, and performs robustly with small or noisy pose data sets, ranging from a few artist‐created poses to noisy poses estimated directly from images. Additionally, a conducted user study indicated that a majority of participants found our retargeted motion to be more enjoyable to watch, more lifelike in appearance, and exhibiting fewer artifacts. Our code and dataset can be accessed here.

Abstract We formalize Italian smocking, an intricate embroidery technique that gathers flat fabric into pleats along meandering lines of stitches, resulting in pleats that fold and gather where the stitching veers. In contrast to English smocking, characterized by colorful stitches decorating uniformly shaped pleats, and Canadian smocking, which uses localized knots to form voluminous pleats, Italian smocking permits the fabric to move freely along the stitched threads following curved paths, resulting in complex and unpredictable pleats with highly diverse, irregular structures, achieved simply by pulling on the threads. We introduce a novel method for digital previewing of Italian smocking results, given the thread stitching path as input. Our method uses a coarse‐grained mass‐spring system to simulate the interaction between the threads and the fabric. This configuration guides the fine‐level fabric deformation through an adaptation of the state‐of‐the‐art simulator, C‐IPC [LKJ21]. Our method models the general problem of fabric‐thread interaction and can be readily adapted to preview Canadian smocking as well. We compare our results to baseline approaches and physical fabrications to demonstrate the accuracy of our method.

Distortion-minimizing surface parameterization is an essential step for computing 2D pieces necessary to fabricate a target 3D shape from flat material. Garment design and textile fabrication are a prominent application example. Common distortion measures quantify length, angle or area preservation in an isotropic manner, so that when applied to woven textile fabrication, they implicitly assume fabric behaves like paper, which is inextensible in all directions and does not permit shearing. However, woven fabric differs significantly from paper: it exhibits anisotropy along the yarn directions and allows for some degree of shearing. We propose a novel distortion energy based on Chebyshev nets that anisotropically penalizes shearing and stretching. Our energy formulation can be used as an optimization objective for surface parameterization and is simple to minimize via a local-global algorithm. We demonstrate its advantages in modeling nets or woven fabric behavior over the commonly used isotropic distortion energies.

We develop an optimization-based method to model smocking , a surface embroidery technique that provides decorative geometric texturing while maintaining stretch properties of the fabric. During smocking, multiple pairs of points on the fabric are stitched together, creating non-manifold geometric features and visually pleasing textures. Designing smocking patterns is challenging, because the outcome of stitching is unpredictable: The final texture is often revealed only when the whole smocking process is completed, necessitating painstaking physical fabrication and time consuming trial-and-error experimentation. This motivates us to seek a digital smocking design method. Straightforward attempts to compute smocked fabric geometry using surface deformation or cloth simulation methods fail to produce realistic results, likely due to the intricate structure of the designs, the large number of contacts and high-curvature folds. We instead formulate smocking as a graph embedding and shape deformation problem. We extract a coarse graph representing the fabric and the stitching constraints and then derive the graph structure of the smocked result. We solve for the three-dimensional embedding of this graph, which in turn reliably guides the deformation of the high-resolution fabric mesh. Our optimization based method is simple, efficient, and flexible, which allows us to build an interactive system for smocking pattern exploration. To demonstrate the accuracy of our method, we compare our results to real fabrications on a large set of smocking patterns.

We present a novel method for realizing freeform surfaces with pieces of flat fabric, where curvature is created by stitching together points on the fabric using a technique known as smocking. Smocking is renowned for producing intricate geometric textures with voluminous pleats. However, it has been mostly used to realize flat shapes or manually designed, limited classes of curved surfaces. Our method combines the computation of directional fields with continuous optimization of a Tangram graph in the plane, which together allow us to realize surfaces of arbitrary topology and curvature with smocking patterns of diverse symmetries. Given a target surface and the desired smocking pattern, our method outputs a corresponding 2D smocking pattern that can be fabricated by sewing specified points together. The resulting textile fabrication approximates the target shape and exhibits visually pleasing pleats. We validate our method through physical fabrication of various smocked examples.

The emergence of neural networks has revolutionized the field of motion synthesis. Yet, learning to unconditionally synthesize motions from a given distribution remains challenging, especially when the motions are highly diverse. In this work, we present MoDi - a generative model trained in an unsupervised setting from an extremely diverse, unstructured and unlabeled dataset. During inference, MoDi can synthesize high-quality, diverse motions. Despite the lack of any structure in the dataset, our model yields a well-behaved and highly structured latent space, which can be semantically clustered, constituting a strong motion prior that facilitates various applications including semantic editing and crowd animation. In addition, we present an encoder that inverts real motions into MoDi's natural motion manifold, issuing solutions to various ill-posed challenges such as completion from prefix and spatial editing. Our qualitative and quantitative experiments achieve state-of-the-art results that outperform recent SOTA techniques. Code and trained models are available at https://sigal-raab.github.io/MoDi.

Restoring the original, flat appearance of a printed document from casual photographs of bent and wrinkled pages is a common everyday problem. In this paper we propose a novel method for grid-based single-image document unwarping. Our method performs geometric distortion correction via a fully convolutional deep neural network that learns to predict the 3D grid mesh of the document and the corresponding 2D unwarping grid in a dual-task fashion, implicitly encoding the coupling between the shape of a 3D piece of paper and its 2D image. In order to allow unwarping models to train on data that is more realistic in appearance than the commonly used synthetic Doc3D dataset, we create and publish our own dataset, called UVDoc, which combines pseudo-photorealistic document images with physically accurate 3D shape and unwarping function annotations. Our dataset is labeled with all the information necessary to train our unwarping network, without having to engineer separate loss functions that can deal with the lack of ground-truth typically found in document in the wild datasets. We perform an in-depth evaluation that demonstrates that with the inclusion of our novel pseudo-photorealistic dataset, our relatively small network architecture achieves state-of-the-art results on the DocUNet benchmark. We show that the pseudo-photorealistic nature of our UVDoc dataset allows for new and better evaluation methods, such as lighting-corrected MS-SSIM. We provide a novel benchmark dataset that facilitates such evaluations, and propose a metric that quantifies line straightness after unwarping. Our code, results and UVDoc dataset are available at https://github.com/tanguymagne/UVDoc.

Abstract Despite recent advances in geometric modelling, 3D mesh modelling still involves a considerable amount of manual labour by experts. In this paper, we introduce Mesh Draping: a neural method for transferring existing mesh structure from one shape to another. The method drapes the source mesh over the target geometry and at the same time seeks to preserve the carefully designed characteristics of the source mesh. At its core, our method deforms the source mesh using progressive positional encoding (PE). We show that by leveraging gradually increasing frequencies to guide the neural optimization, we are able to achieve stable and high‐quality mesh transfer. Our approach is simple and requires little user guidance, compared to contemporary surface mapping techniques which rely on parametrization or careful manual tuning. Most importantly, Mesh Draping is a parameterization‐free method, and thus applicable to a variety of target shape representations, including point clouds, polygon soups and non‐manifold meshes. We demonstrate that the transferred meshing remains faithful to the source mesh design characteristics, and at the same time fits the target geometry well.

Abstract The standardized sizes used in the garment industry do not cover the range of individual differences in body shape for most people, leading to ill‐fitting clothes, high return rates and overproduction. Recent research efforts in both industry and academia, therefore, focus on virtual try‐on and on‐demand fabrication of individually fitting garments. We propose an interactive design tool for creating custom‐fit garments based on 3D body scans of the intended wearer. Our method explicitly incorporates transitions between various body poses to ensure a better fit and freedom of movement. The core of our method focuses on tools to create a 3D garment shape directly on an avatar without an underlying sewing pattern, and on the adjustment of that garment's rest shape while interpolating and moving through the different input poses. We alternate between cloth simulation and rest shape adjustment based on stretch to achieve the final shape of the garment. At any step in the real‐time process, we allow for interactive changes to the garment. Once the garment shape is finalized for production, established techniques can be used to parameterize it into a 2D sewing pattern or transform it into a knitting pattern.

Garment modeling is an essential task of the global apparel industry and a core part of digital human modeling. Realistic representation of garments with valid sewing patterns is key to their accurate digital simulation and eventual fabrication. However, little-to-no computational tools provide support for bridging the gap between high-level construction goals and low-level editing of pattern geometry, e.g., combining or switching garment elements, semantic editing, or design exploration that maintains the validity of a sewing pattern. We suggest the first DSL for garment modeling - GarmentCode - that applies principles of object-oriented programming to garment construction and allows designing sewing patterns in a hierarchical, component-oriented manner. The programming-based paradigm naturally provides unique advantages of component abstraction, algorithmic manipulation, and free-form design parametrization. We additionally support the construction process by automating typical low-level tasks like placing a dart at a desired location. In our prototype garment configurator, users can manipulate meaningful design parameters and body measurements, while the construction of pattern geometry is handled by garment programs implemented with GarmentCode. Our configurator enables the free exploration of rich design spaces and the creation of garments using interchangeable, parameterized components. We showcase our approach by producing a variety of garment designs and retargeting them to different body shapes using our configurator. The library and garment configurator are available at https://github.com/maria-korosteleva/GarmentCode.

We present GenMM, a generative model that "mines" as many diverse motions as possible from a single or few example sequences. In stark contrast to existing data-driven methods, which typically require long offline training time, are prone to visual artifacts, and tend to fail on large and complex skeletons, GenMM inherits the training-free nature and the superior quality of the well-known Motion Matching method. GenMM can synthesize a high-quality motion within a fraction of a second, even with highly complex and large skeletal structures. At the heart of our generative framework lies the generative motion matching module, which utilizes the bidirectional visual similarity as a generative cost function to motion matching, and operates in a multi-stage framework to progressively refine a random guess using exemplar motion matches. In addition to diverse motion generation, we show the versatility of our generative framework by extending it to a number of scenarios that are not possible with motion matching alone, including motion completion, key frame-guided generation, infinite looping, and motion reassembly.

We present a multi-sensor system for consistent 3D hand pose tracking and modeling that leverages the advantages of both wearable and optical sensors. Specifically, we employ a stretch-sensing soft glove and three IMUs in combination with an RGB-D camera. Different sensor modalities are fused based on the availability and confidence estimation, enabling seamless hand tracking in challenging environments with partial or even complete occlusion. To maximize the accuracy while maintaining high ease-of-use, we propose an automated user calibration that uses the RGB-D camera data to refine both the glove mapping model and the multi-IMU system parameters. Extensive experiments show that our setup outperforms the wearable-only approaches when the hand is in the field-of-view and outplays the camera-only methods when the hand is occluded.

We introduce pointwise map smoothness via the Dirich-let energy into the functional map pipeline, and propose an algorithm for optimizing it efficiently, which leads to highquality results in challenging settings. Specifically, we first formulate the Dirichlet energy of the pulled-back shape coordinates, as a way to evaluate smoothness of a pointwise map across discrete surfaces. We then extend the recently proposed discrete solver and show how a strategy based on auxiliary variable reformulation allows us to optimize pointwise map smoothness alongside desirable functional map properties such as bijectivity. This leads to an efficient map refinement strategy that simultaneously improves functional and point-to-point correspondences, obtaining smooth maps even on non-isometric shape pairs. Moreover, we demonstrate that several previously proposed methods for computing smooth maps can be reformulated as variants of our approach, which allows us to compare different formulations in a consistent framework. Finally, we compare these methods both on existing benchmarks and on a new rich dataset that we introduce, which contains non-rigid, non-isometric shape pairs with inter-category and cross-category correspondences. Our work leads to a general framework for optimizing and analyzing map smoothness both conceptually and in challenging practical settings.

Abstract We propose a method for the construction of a planar curve based on piecewise clothoids and straight lines that intuitively interpolates a given sequence of control points. Our method has several desirable properties that are not simultaneously fulfilled by previous approaches: Our interpolating curves are C2 continuous, their computation does not rely on global optimization and has local support, enabling fast evaluation for interactive modeling. Further, the sign of the curvature at control points is consistent with the control polygon; the curvature attains its extrema at control points and is monotone between consecutive control points of opposite curvature signs. In addition, we can ensure that the curve has self‐intersections only when the control polygon also self‐intersects between the same control points. For more fine‐grained control, the user can specify the desired curvature and tangent values at certain control points, though it is not required by our method. Our local optimization can lead to discontinuity w.r.t. the locations of control points, although the problem is limited by its locality. We demonstrate the utility of our approach in generating various curves and provide a comparison with the state of the art.

Solving partial differential equations (PDEs) on geometric domains is an important component of computer graphics, geometry processing, and many other fields. Typically, the given discrete mesh is the geometric representation and should not be altered for simulation purposes. Hence, accurately solving PDEs on general meshes is a central goal and has been considered for various differential operators over the last years. While it is known that using higher-order basis functions on simplicial meshes can substantially improve accuracy and convergence, extending these benefits to general surface or volume tessellations in an efficient fashion remains an open problem. Our work proposes variationally optimized piecewise quadratic shape functions for polygons and polyhedra, which generalize quadratic P 2 elements, exactly reproduce them on simplices, and inherit their beneficial numerical properties. To mitigate the associated cost of increased computation time, particularly for volumetric meshes, we introduce a custom two-level multigrid solver which significantly improves computational performance.

We introduce a code generator that converts unoptimized C++ code operating on sparse data into vectorized and parallel CPU or GPU kernels. Our approach unrolls the computation into a massive expression graph, performs redundant expression elimination, grouping, and then generates an architecture-specific kernel to solve the same problem, assuming that the sparsity pattern is fixed, which is a common scenario in many applications in computer graphics and scientific computing. We show that our approach scales to large problems and can achieve speedups of two orders of magnitude on CPUs and three orders of magnitude on GPUs, compared to a set of manually optimized CPU baselines. To demonstrate the practical applicability of our approach, we employ it to optimize popular algorithms with applications to physical simulation and interactive mesh deformation.

Neural implicit fields are quickly emerging as an attractive representation for learning based techniques. However, adopting them for 3D shape modeling and editing is challenging. We introduce a method for E diting I mplicit S hapes T hrough P art A ware G enera T ion, permuted in short as SPAGHETTI. Our architecture allows for manipulation of implicit shapes by means of transforming, interpolating and combining shape segments together, without requiring explicit part supervision. SPAGHETTI disentangles shape part representation into extrinsic and intrinsic geometric information. This characteristic enables a generative framework with part-level control. The modeling capabilities of SPAGHETTI are demonstrated using an interactive graphical interface, where users can directly edit neural implicit shapes. Our code, editing user interface demo and pre-trained models are available at github.com/amirhertz/spaghetti.

We present GANimator, a generative model that learns to synthesize novel motions from a single, short motion sequence. GANimator generates motions that resemble the core elements of the original motion, while simultaneously synthesizing novel and diverse movements. Existing data-driven techniques for motion synthesis require a large motion dataset which contains the desired and specific skeletal structure. By contrast, GANimator only requires training on a single motion sequence, enabling novel motion synthesis for a variety of skeletal structures e.g. , bipeds, quadropeds, hexapeds, and more. Our framework contains a series of generative and adversarial neural networks, each responsible for generating motions in a specific frame rate. The framework progressively learns to synthesize motion from random noise, enabling hierarchical control over the generated motion content across varying levels of detail. We show a number of applications, including crowd simulation, key-frame editing, style transfer, and interactive control, which all learn from a single input sequence. Code and data for this paper are at https://peizhuoli.github.io/ganimator.

We propose a method for computing a sewing pattern of a given 3D garment model. Our algorithm segments an input 3D garment shape into patches and computes their 2D parameterization, resulting in pattern pieces that can be cut out of fabric and sewn together to manufacture the garment. Unlike the general state-of-the-art approaches for surface cutting and flattening, our method explicitly targets garment fabrication. It accounts for the unique properties and constraints of tailoring, such as seam symmetry, the usage of darts, fabric grain alignment, and a flattening distortion measure that models woven fabric deformation, respecting its anisotropic behavior. We bootstrap a recent patch layout approach developed for quadrilateral remeshing and adapt it to the purpose of computational pattern making, ensuring that the deformation of each pattern piece stays within prescribed bounds of cloth stress. While our algorithm can automatically produce the sewing patterns, it is fast enough to admit user input to creatively iterate on the pattern design. Our method can take several target poses of the 3D garment into account and integrate them into the sewing pattern design. We demonstrate results on both skintight and loose garments, showcasing the versatile application possibilities of our approach.

We introduce an algorithm to remesh triangle meshes representing developable surfaces to planar quad dominant meshes. The output of our algorithm consists of planar quadrilateral (PQ) strips that are aligned to principal curvature directions and closely approximate the curved parts of the input developable, and planar polygons representing the flat parts of the input that connect the PQ strips. Developable PQ-strip meshes are useful in many areas of shape modeling, thanks to the simplicity of fabrication from flat sheet material. Unfortunately, they are difficult to model due to their restrictive combinatorics. Other representations of developable surfaces, such as arbitrary triangle or quad meshes, are more suitable for interactive freeform modeling but generally have non-planar faces or are not aligned to principal curvatures. Our method leverages the modeling flexibility of non-ruling-based representations of developable surfaces while still obtaining developable, curvature-aligned PQ-strip meshes. Our algorithm optimizes for a scalar function on the input mesh, such that its isolines are extrinsically straight and align well to the locally estimated ruling directions. The condition that guarantees straight isolines is non-linear of high order and numerically difficult to enforce in a straightforward manner. We devise an alternating optimization method that makes our problem tractable and practical to compute. Our method works automatically on any developable input, including multiple patches and curved folds, without explicit domain decomposition. We demonstrate the effectiveness of our approach on a variety of developable surfaces and show how our remeshing can be used alongside handle-based interactive freeform modeling of developable shapes.

We propose a novel design of engineered, structured materials that leverages fast fabrication technologies, pushing them towards mass-fabrication. Specifically, our metamaterial is designed to be laser cut, to approximate the volumetric shape and allow for locally varying compliance. Traditional mechanical metamaterials consist of intricate cells arranged on a 3-dimensional grid, limiting them to 3D printing—which is slow. Our metamaterial is designed for laser cutting, which is drastically faster. Our structures are best described as ruffled strips of thin sheet material, such as paper, plastics, metals, etc. Users can interactively define the ruffles’ anisotropic stiffness directions and local density. Our computational design tool assists users by automatically optimizing the ruffle to fill the shape’s volume, and exporting the flat ruffle design ready for cutting. We demonstrate how such ruffled metamaterials can be utilized for, e.g., custom toys with locally varying compliance, custom packaging material, or lightweight formwork for architectural shells.

Neural implicit functions have emerged as a powerful representation for surfaces in 3D. Such a function can en-code a high quality surface with intricate details into the parameters of a deep neural network. However, optimizing for the parameters for accurate and robust reconstructions remains a challenge, especially when the input data is noisy or incomplete. In this work, we develop a hybrid neural surface representation that allows us to impose geometry-aware sampling and regularization, which significantly improves the fidelity of reconstructions. We propose to use iso-points as an explicit representation for a neural implicit function. These points are computed and updated on-the-fly during training to capture important geometric features and impose geometric constraints on the optimization. We demonstrate that our method can be adopted to improve state-of-the-art techniques for reconstructing neural implicit surfaces from multi-view images or point clouds. Quantitative and qualitative evaluations show that, compared with existing sampling and optimization methods, our approach allows faster convergence, better generalization, and accurate recovery of details and topology.

Multilayer-perceptrons (MLP) are known to struggle learning functions of high-frequencies, and in particular, instances of wide frequency bands.We present a progressive mapping scheme for input signals of MLP networks, enabling them to better fit a wide range of frequencies without sacrificing training stability or requiring any domain specific preprocessing. We introduce Spatially Adaptive Progressive Encoding (SAPE) layers, which gradually unmask signal components with increasing frequencies as a function of time and space. The progressive exposure of frequencies is monitored by a feedback loop throughout the neural optimization process, allowing changes to propagate at different rates among local spatial portions of the signal space. We demonstrate the advantage of our method on variety of domains and applications: regression of low dimensional signals and images, representation learning of occupancy networks, and a geometric task of mesh transfer between 3D shapes.

Abstract Approximating 3D shapes with piecewise developable surfaces is an active research topic, driven by the benefits of developable geometry in fabrication. Piecewise developable surfaces are characterized by having a Gauss image that is a 1D object – a collection of curves on the Gauss sphere. We present a method for developable approximation that makes use of this classic definition from differential geometry. Our algorithm is an iterative process that alternates between thinning the Gauss image of the surface and deforming the surface itself to make its normals comply with the Gauss image. The simple, local‐global structure of our algorithm makes it easy to implement and optimize. We validate our method on developable shapes with added noise and demonstrate its effectiveness on a variety of non‐developable inputs. Compared to the state of the art, our method is more general, tessellation independent, and preserves the input mesh connectivity.

Abstract Reading books or articles digitally has become accessible and widespread thanks to the large amount of affordable mobile devices and distribution platforms. However, little effort has been devoted to improving the digital book reading experience, despite studies showing disadvantages of digital text media consumption, such as diminished memory recall and enjoyment, compared to physical books. In addition, a vast amount of physical, printed books of interest exist, many of them rare and not easily physically accessible, such as out‐of‐print art books, first editions, or historical tomes secured in museums. Digital replicas of such books are typically either purely text based, or consist of photographed pages, where much of the essence of leafing through and experiencing the actual artifact is lost. In this work, we devise a method to recreate the experience of reading and interacting with a physical book in a digital 3D environment. Leveraging recent work on static modeling of freeform developable surfaces, which exhibit paper‐like properties, we design a method for dynamic physical simulation of such surfaces, accounting for gravity and handling collisions to simulate pages in a book. We propose a mix of 2D and 3D models, specifically tailored to represent books to achieve a computationally fast simulation, running in real time on mobile devices. Our system enables users to lift, bend and flip book pages by holding them at arbitrary locations and provides a holistic interactive experience of a virtual 3D book.

Animating a newly designed character using motion capture (mocap) data is a long standing problem in computer animation. A key consideration is the skeletal structure that should correspond to the available mocap data, and the shape deformation in the joint regions, which often requires a tailored, pose-specific refinement. In this work, we develop a neural technique for articulating 3D characters using enveloping with a pre-defined skeletal structure which produces high quality pose dependent deformations. Our framework learns to rig and skin characters with the same articulation structure ( e.g. , bipeds or quadrupeds), and builds the desired skeleton hierarchy into the network architecture. Furthermore , we propose neural blend shapes - a set of corrective pose-dependent shapes which improve the deformation quality in the joint regions in order to address the notorious artifacts resulting from standard rigging and skinning. Our system estimates neural blend shapes for input meshes with arbitrary connectivity, as well as weighting coefficients which are conditioned on the input joint rotations. Unlike recent deep learning techniques which supervise the network with ground-truth rigging and skinning parameters, our approach does not assume that the training data has a specific underlying deformation model. Instead, during training, the network observes deformed shapes and learns to infer the corresponding rig, skin and blend shapes using indirect supervision. During inference, we demonstrate that our network generalizes to unseen characters with arbitrary mesh connectivity, including unrigged characters built by 3D artists. Conforming to standard skeletal animation models enables direct plug-and-play in standard animation software, as well as game engines.

We propose a novel learnable representation for detail preserving shape deformation. The goal of our method is to warp a source shape to match the general structure of a target shape, while preserving the surface details of the source. Our method extends a traditional cage-based deformation technique, where the source shape is enclosed by a coarse control mesh termed cage, and translations prescribed on the cage vertices are interpolated to any point on the source mesh via special weight functions. The use of this sparse cage scaffolding enables preserving surface details regardless of the shape's intricacy and topology. Our key contribution is a novel neural network architecture for predicting deformations by controlling the cage. We incorporate a differentiable cage-based deformation module in our architecture, and train our network end-to-end. Our method can be trained with common collections of 3D models in an unsupervised fashion, without any cage-specific annotations. We demonstrate the utility of our method for synthesizing shape variations and deformation transfer.

Abstract Discrete Laplacians for triangle meshes are a fundamental tool in geometry processing. The so‐called cotan Laplacian is widely used since it preserves several important properties of its smooth counterpart. It can be derived from different principles: either considering the piecewise linear nature of the primal elements or associating values to the dual vertices. Both approaches lead to the same operator in the two‐dimensional setting. In contrast, for tetrahedral meshes, only the primal construction is reminiscent of the cotan weights, involving dihedral angles. We provide explicit formulas for the lesser‐known dual construction. In both cases, the weights can be computed by adding the contributions of individual tetrahedra to an edge. The resulting two different discrete Laplacians for tetrahedral meshes only retain some of the properties of their two‐dimensional counterpart. In particular, while both constructions have linear precision, only the primal construction is positive semi‐definite and only the dual construction generates positive weights and provides a maximum principle for Delaunay meshes. We perform a range of numerical experiments that highlight the benefits and limitations of the two constructions for different problems and meshes.

We introduce a novel deep learning framework for data-driven motion retargeting between skeletons, which may have different structure, yet corresponding to homeomorphic graphs. Importantly, our approach learns how to retarget without requiring any explicit pairing between the motions in the training set. We leverage the fact that different homeomorphic skeletons may be reduced to a common primal skeleton by a sequence of edge merging operations, which we refer to as skeletal pooling. Thus, our main technical contribution is the introduction of novel differentiable convolution, pooling, and unpooling operators. These operators are skeleton-aware , meaning that they explicitly account for the skeleton's hierarchical structure and joint adjacency, and together they serve to transform the original motion into a collection of deep temporal features associated with the joints of the primal skeleton. In other words, our operators form the building blocks of a new deep motion processing framework that embeds the motion into a common latent space, shared by a collection of homeomorphic skeletons. Thus, retargeting can be achieved simply by encoding to, and decoding from this latent space. Our experiments show the effectiveness of our framework for motion retargeting, as well as motion processing in general, compared to existing approaches. Our approach is also quantitatively evaluated on a synthetic dataset that contains pairs of motions applied to different skeletons. To the best of our knowledge, our method is the first to perform retargeting between skeletons with differently sampled kinematic chains, without any paired examples.

We present a new framework for sketch-based modeling and animation of 3D organic shapes that can work entirely in an intuitive 2D domain, enabling a playful, casual experience. Unlike previous sketch-based tools, our approach does not require a tedious part-based multi-view workflow with the explicit specification of an animation rig. Instead, we combine 3D inflation with a novel rigidity-preserving, layered deformation model, ARAP-L, to produce a smooth 3D mesh that is immediately ready for animation. Moreover, the resulting model can be animated from a single viewpoint --- and without the need to handle unwanted inter-penetrations, as required by previous approaches. We demonstrate the benefit of our approach on a variety of examples produced by inexperienced users as well as professional animators. For less experienced users, our single-view approach offers a simpler modeling and animating experience than working in a 3D environment, while for professionals, it offers a quick and casual workspace for ideation.

We present a novel linear solver for interactive parameterization tasks. Our method is based on the observation that quasi-conformal parameterizations of a triangle mesh are largely determined by boundary conditions. These boundary conditions are typically constructed interactively by users, who have to take several artistic and geometric constraints into account while introducing cuts on the geometry. Commonly, the main computational burden in these methods is solving a linear system every time new boundary conditions are imposed. The core of our solver is a novel approach to efficiently update the Cholesky factorization of the linear system to reflect new boundary conditions, thereby enabling a seamless and interactive workflow even for large meshes consisting of several millions of vertices.

We present an automatic tool to approximate curved geometries with piece-wise developable surfaces. At the center of our work is an algorithm that wraps a given 3D input surface with multiple developable patches, each modeled as a discrete orthogonal geodesic net. Our algorithm features a global optimization routine for effectively finding the placement of the developable patches. After wrapping the mesh, we use these patches and a non-linear projection step to generate a surface that approximates the original input, but is also amendable to simple and efficient fabrication techniques thanks to being piecewise developable. Our algorithm allows users to steer the trade-off between approximation power and the number of developable patches used. We demonstrate the effectiveness of our approach on a range of 3D shapes. Compared to previous approaches, our results exhibit a smaller or comparable error with fewer patches to fabricate.

We present a detail-driven deep neural network for point set upsampling. A high-resolution point set is essential for point-based rendering and surface reconstruction. Inspired by the recent success of neural image super-resolution techniques, we progressively train a cascade of patch-based upsampling networks on different levels of detail end-to-end. We propose a series of architectural design contributions that lead to a substantial performance boost. The effect of each technical contribution is demonstrated in an ablation study. Qualitative and quantitative experiments show that our method significantly outperforms the state-of-the-art learning-based and optimazation-based approaches, both in terms of handling low-resolution inputs and revealing high-fidelity details.

Existing deep learning approaches to single image super-resolution have achieved impressive results but mostly assume a setting with fixed pairs of high resolution and low resolution images. However, to robustly address realistic upscaling scenarios where the relation between high resolution and low resolution images is unknown, blind image super-resolution is required. To this end, we propose a solution that relies on three components: First, we use a degradation aware SR network to synthesize the HR image given a low resolution image and the corresponding blur kernel. Second, we train a kernel discriminator to analyze the generated high resolution image in order to predict errors present due to providing an incorrect blur kernel to the generator. Finally, we present an optimization procedure that is able to recover both the degradation kernel and the high resolution image by minimizing the error predicted by our kernel discriminator. We also show how to extend our approach to spatially variant degradations that typically arise in visual effects pipelines when compositing content from different sources and how to enable both local and global user interaction in the upscaling process.

We propose a hardware and software pipeline to fabricate flexible wearable sensors and use them to capture deformations without line-of-sight. Our first contribution is a low-cost fabrication pipeline to embed multiple aligned conductive layers with complex geometries into silicone compounds. Overlapping conductive areas from separate layers form local capacitors that measure dense area changes. Contrary to existing fabrication methods, the proposed technique only requires hardware that is readily available in modern fablabs. While area measurements alone are not enough to reconstruct the full 3D deformation of a surface, they become sufficient when paired with a data-driven prior. A novel semi-automatic tracking algorithm, based on an elastic surface geometry deformation, allows us to capture ground-truth data with an optical mocap system, even under heavy occlusions or partially unobservable markers. The resulting dataset is used to train a regressor based on deep neural networks, directly mapping the area readings to global positions of surface vertices. We demonstrate the flexibility and accuracy of the proposed hardware and software in a series of controlled experiments and design a prototype of wearable wrist, elbow, and biceps sensors, which do not require line-of-sight and can be worn below regular clothing.

We propose a stretch-sensing soft glove to interactively capture hand poses with high accuracy and without requiring an external optical setup. We demonstrate how our device can be fabricated and calibrated at low cost, using simple tools available in most fabrication labs. To reconstruct the pose from the capacitive sensors embedded in the glove, we propose a deep network architecture that exploits the spatial layout of the sensor itself. The network is trained only once, using an inexpensive off-the-shelf hand pose reconstruction system to gather the training data. The per-user calibration is then performed on-the-fly using only the glove. The glove's capabilities are demonstrated in a series of ablative experiments, exploring different models and calibration methods. Comparing against commercial data gloves, we achieve a 35% improvement in reconstruction accuracy.

We present a computational framework for interactive design and exploration of curved folded surfaces. In current practice, such surfaces are typically created manually using physical paper, and hence our objective is to lay the foundations for the digitalization of curved folded surface design. Our main contribution is a discrete binary characterization for folds between discrete developable surfaces, accompanied by an algorithm to simultaneously fold creases and smoothly bend planar sheets. We complement our algorithm with essential building blocks for curved folding deformations: objectives to control dihedral angles and mountain-valley assignments. We apply our machinery to build the first interactive freeform editing tool capable of modeling bending and folding of complicated crease patterns.

We propose Differentiable Surface Splatting (DSS), a high-fidelity differentiable renderer for point clouds. Gradients for point locations and normals are carefully designed to handle discontinuities of the rendering function. Regularization terms are introduced to ensure uniform distribution of the points on the underlying surface. We demonstrate applications of DSS to inverse rendering for geometry synthesis and denoising, where large scale topological changes, as well as small scale detail modifications, are accurately and robustly handled without requiring explicit connectivity, outperforming state-of-the-art techniques. The data and code are at https://github.com/yifita/DSS.

Despite recent developments towards on-demand, individualized garment design and fabrication, the majority of processes in the fashion industry are still inefficient and heavily dependent on manual work. A significant amount of recent research in this area has been focused on supporting designers to digitally create sewing patterns and shapes, but there is little work on textured fabrics. Aligning textile patterns like stripes or plaid along garment seams requires an experienced tailor and is thus reserved only for expensive, high-end garments. We present an interactive algorithm for automatically aligning repetitive textile patterns along seams for a given garment, allowing a user to make design choices at each step of our pipeline. Our approach is based on the 17 wallpaper groups and the symmetries they exhibit. We exploit these symmetries to optimize the alignment of the sewing pattern with the textured fabric for each of its pieces, determining where to cut the fabric. We optionally alter the sewing pattern slightly for a perfect fit along seams, without visibly changing the 3D shape of the garment. The pieces can then be cut automatically by a CNC or laser cutter. Our approach fits within the pipeline of digital garment design, eliminating the difficult, manual step of aligning and cutting the garment pieces by hand.

In this video we present soft self-sensing capacitive arrays and demonstrate their use in capturing dense surface deformations without requiring line of sight. The capacitive arrays are made of two electrode patterns embedded into a single silicone compound. The overlaps of the electrode strip patterns form local capacitors. As the sensor is stretched the local capacitance measurements change. We introduce a fabrication technique that allows to produce such sensors while only requiring hardware readily available in modern fablabs. The resulting sensors are able to densely capture area changes as they deform. Since they do not directly measure bend, a prior is required to fully reconstruct the underlying motion. We propose a deep neural network regressing the sensor geometry from the local area measurements. A motion capture system is used for training data acquisition. At runtime vertex positions are predicted and used as positional constraints to deform a mesh using a state-of-the-art elastic surface energy. The flexibility and accuracy of the introduced sensors is demonstrated in a series of controlled experiments and by fabricating a prototype sensor and applying it to capture deforming skeletal and non-skeletal objects.

Abstract We present a novel method to simulate Cosserat rods with Projective Dynamics (PD). The proposed method is both numerically robust and accurate with respect to the underlying physics, making it suitable for a variety of applications in computer graphics and related disciplines. Cosserat theory assigns an orientation frame to each point and is thus able to realistically simulate stretching and shearing effects, in addition to bending and twisting. Within the PD framework, it is possible to obtain accurate simulations given the implicit integration over time and its decoupling of the local‐global solve. In the proposed method, we start from the continuous formulation of the Cosserat theory and derive the constraints for the PD solver. We extend the standard definition of PD and add body orientations as system variables. Thus, we include the preservation of angular momentum, so that twisting and bending can be accurately simulated. Our formulation allows the simulation of different bending behaviors with respect to a user‐defined Young's modulus, the radius of the rod's cross‐section, and material density. We show how different material specifications in our simulations converge within a few iterations to a reference solution, generated with a high‐precision finite element method. Furthermore, we demonstrate mesh independence of our formulation: Refining the simulation mesh still results in the same characteristic motion, which is in contrast to previous position based methods.

Abstract Laser cutting is an appealing fabrication process due to the low cost of materials and extremely fast fabrication. However, the design space afforded by laser cutting is limited, since only flat panels can be cut. Previous methods for manufacturing from flat sheets usually roughly approximate 3D objects by polyhedrons or cross sections. Computational design methods for connecting, interlocking, or folding several laser cut panels have been introduced; to obtain a good approximation, these methods require numerous parts and long assembly times. In this paper, we propose a radically different approach: Our approximation is based on cutting thin, planar spirals out of flat panels. When such spirals are pulled apart, they take on the shape of a 3D spring whose contours are similar to the input object. We devise an optimization problem that aims to minimize the number of required parts, thus reducing costs and fabrication time, while at the same time ensuring that the resulting spring mimics the shape of the original object. In addition to rapid fabrication and assembly, our method enables compact packaging and storage as flat parts. We also demonstrate its use for creating armatures for sculptures and moulds for filling, with potential applications in architecture or construction.

We present a discrete theory for modeling developable surfaces as quadrilateral meshes satisfying simple angle constraints. The basis of our model is a lesser-known characterization of developable surfaces as manifolds that can be parameterized through orthogonal geodesics. Our model is simple and local, and, unlike in previous works, it does not directly encode the surface rulings. This allows us to model continuous deformations of discrete developable surfaces independently of their decomposition into torsal and planar patches or the surface topology. We prove and experimentally demonstrate strong ties to smooth developable surfaces, including a theorem stating that every sampling of the smooth counterpart satisfies our constraints up to second order. We further present an extension of our model that enables a local definition of discrete isometry. We demonstrate the effectiveness of our discrete model in a developable surface editing system, as well as computation of an isometric interpolation between isometric discrete developable shapes.

Discrete orthogonal geodesic nets (DOGs) are a quad mesh analogue of developable surfaces. In this work we study continuous deformations on these discrete objects. Our main theoretical contribution is the characterization of the shape space of DOGs for a given net connectivity. We show that generally, this space is locally a manifold of a fixed dimension, apart from a set of singularities, implying that DOGs are continuously deformable. Smooth flows can be constructed by a smooth choice of vectors on the manifold's tangent spaces, selected to minimize a desired objective function under a given metric. We show how to compute such vectors by solving a linear system, and we use our findings to devise a geometrically meaningful way to handle singular points. We base our shape space metric on a novel DOG Laplacian operator, which is proved to converge under sampling of an analytical orthogonal geodesic net. We further show how to extend the shape space of DOGs by supporting creases and curved folds and apply the developed tools in an editing system for developable surfaces that supports arbitrary bending, stretching, cutting, (curved) folds, as well as smoothing and subdivision operations.

Fabrication from developable parts is the basis for arts such as papercraft and needlework, as well as modern architecture and CAD in general, and it has inspired much research. We observe that the assembly of complex 3D shapes created by existing methods often requires first fabricating many small parts and then carefully following instructions to assemble them together. Despite its significance, this error prone and tedious process is generally neglected in the discussion. We present the concept of zippables - single , two dimensional, branching, ribbon-like pieces of fabric that can be quickly zipped up without any instructions to form 3D objects. Our inspiration comes from the so-called zipit bags [zipit 2017], which are made of a single, long ribbon with a zipper around its boundary. In order to "assemble" the bag, one simply needs to zip up the ribbon. Our method operates in the same fashion, but it can be used to approximate a wide variety of shapes. Given a 3D model, our algorithm produces plans for a single 2D shape that can be laser cut in few parts from fabric or paper. A zipper can then be attached along the boundary by sewing, or by gluing using a custom-built fastening rig. We show physical and virtual results that demonstrate the capabilities of our method and the ease with which shapes can be assembled.

We propose a UV mapping algorithm that jointly optimizes for cuts and distortion, sidestepping heuristics for placing the cuts. The energy we minimize is a state-of-the-art geometric distortion measure, generalized to take seams into account. Our algorithm is designed to support an interactive workflow: it optimizes UV maps on the fly, while the user can interactively move vertices, cut mesh parts, join seams, separate overlapping regions, and control the placement of the parameterization patches in the UV space. Our UV maps are of high quality in terms of both geometric distortion and cut placement, and compare favorably to those designed with traditional modeling tools. The UV maps can be created in a fraction of the time as existing methods, since our algorithm drastically alleviates the trial-and-error, iterative procedures that plague traditional UV mapping approaches.

We present a scalable approach for the optimization of flip-preventing energies in the general context of simplicial mappings and specifically for mesh parameterization. Our iterative minimization is based on the observation that many distortion energies can be optimized indirectly by minimizing a family of simpler proxy energies. Minimization of these proxies is a natural extension of the local/global minimization of the ARAP energy. Our algorithm is simple to implement and scales to datasets with millions of faces. We demonstrate our approach for the computation of maps that minimize a conformal or isometric distortion energy, both in two and three dimensions. In addition to mesh parameterization, we show that our algorithm can be applied to mesh deformation and mesh quality improvement.

Many algorithms on meshes require the minimization of composite objectives, i.e. , energies that are compositions of simpler parts. Canonical examples include mesh parameterization and deformation. We propose a second order optimization approach that exploits this composite structure to efficiently converge to a local minimum. Our main observation is that a convex-concave decomposition of the energy constituents is simple and readily available in many cases of practical relevance in graphics. We utilize such convex-concave decompositions to define a tight convex majorizer of the energy, which we employ as a convex second order approximation of the objective function. In contrast to existing approaches that largely use only local convexification, our method is able to take advantage of a more global view on the energy landscape. Our experiments on triangular meshes demonstrate that our approach outperforms the state of the art on standard problems in geometry processing, and potentially provide a unified framework for developing efficient geometric optimization algorithms.

Point sets generated by image-based 3D reconstruction techniques are often much noisier than those obtained using active techniques like laser scanning. Therefore, they pose greater challenges to the subsequent surface reconstruction (meshing) stage. We present a simple and effective method for removing noise and outliers from such point sets. Our algorithm uses the input images and corresponding depth maps to remove pixels which are geometrically or photometrically inconsistent with the colored surface implied by the input. This allows standard surface reconstruction methods (such as Poisson surface reconstruction) to perform less smoothing and thus achieve higher quality surfaces with more features. Our algorithm is efficient, easy to implement, and robust to varying amounts of noise. We demonstrate the benefits of our algorithm in combination with a variety of state-of-the-art depth and surface reconstruction methods.

Objects with thin features and fine details are challenging for most multi-view stereo techniques, since such features occupy small volumes and are usually only visible in a small portion of the available views. In this paper, we present an efficient algorithm to reconstruct intricate objects using densely sampled light fields. At the heart of our technique lies a novel approach to compute per-pixel depth values by exploiting local gradient information in densely sampled light fields. This approach can generate accurate depth values for very thin features, and can be run for each pixel in parallel. We assess the reliability of our depth estimates using a novel two-sided photoconsistency measure, which can capture whether the pixel lies on a texture or a silhouette edge. This information is then used to propagate the depth estimates at high gradient regions to smooth parts of the views efficiently and reliably using edge-aware filtering. In the last step, the per-image depth values and color information are aggregated in 3D space using a voting scheme, allowing the reconstruction of a globally consistent mesh for the object. Our approach can process large video datasets very efficiently and at the same time generates high quality object reconstructions that compare favorably to the results of state-of-the-art multi-view stereo methods.

We propose a novel approach to digital character animation, combining the benefits of tangible input devices and sophisticated rig animation algorithms. A symbiotic software and hardware approach facilitates the animation process for novice and expert users alike. We overcome limitations inherent to all previous tangible devices by allowing users to directly control complex rigs using only a small set (5-10) of physical controls. This avoids oversimplification of the pose space and excessively bulky device configurations. Our algorithm derives a small device configuration from complex character rigs, often containing hundreds of degrees of freedom, and a set of sparse sample poses. Importantly, only the most influential degrees of freedom are controlled directly, yet detailed motion is preserved based on a pose interpolation technique. We designed a modular collection of joints and splitters, which can be assembled to represent a wide variety of skeletons. Each joint piece combines a universal joint and two twisting elements, allowing to accurately sense its configuration. The mechanical design provides a smooth inverse kinematics-like user experience and is not prone to gimbal locking. We integrate our method with the professional 3D software Autodesk Maya ® and discuss a variety of results created with characters available online. Comparative user experiments show significant improvements over the closest state-of-the-art in terms of accuracy and time in a keyframe posing task.

We propose a method to fabricate textured 3D models using thermoforming. Differently from industrial techniques, which target mass production of a specific shape, we propose a combined hardware and software solution to manufacture customized, unique objects. Our method simulates the forming process and converts the texture of a given digital 3D model into a pre-distorted image that we transfer onto a plastic sheet. During thermoforming, the sheet deforms to create a faithful physical replica of the digital model. Our hardware setup uses off-the-shelf components and can be calibrated with an automatic algorithm that extracts the simulation parameters from a single calibration object produced by the same process.

Precise object segmentation in image data is a fundamental problem with various applications, including 3D object reconstruction. We present an efficient algorithm to automatically segment a static foreground object from highly cluttered background in light fields. A key insight and contribution of our article is that a significant increase of the available input data can enable the design of novel, highly efficient approaches. In particular, the central idea of our method is to exploit high spatio-angular sampling on the order of thousands of input frames, for example, captured as a hand-held video, such that new structures are revealed due to the increased coherence in the data. We first show how purely local gradient information contained in slices of such a dense light field can be combined with information about the camera trajectory to make efficient estimates of the foreground and background. These estimates are then propagated to textureless regions using edge-aware filtering in the epipolar volume. Finally, we enforce global consistency in a gathering step to derive a precise object segmentation in both 2D and 3D space, which captures fine geometric details even in very cluttered scenes. The design of each of these steps is motivated by efficiency and scalability, allowing us to handle large, real-world video datasets on a standard desktop computer. We demonstrate how the results of our method can be used for considerably improving the speed and quality of image-based 3D reconstruction algorithms, and we compare our results to state-of-the-art segmentation and multiview stereo methods.

Abstract In the digital world, assigning arbitrary colors to an object is a simple operation thanks to texture mapping. However, in the real world, the same basic function of applying colors onto an object is far from trivial. One can specify colors during the fabrication process using a color 3D printer, but this does not apply to already existing objects. Paint and decals can be used during post‐fabrication, but they are challenging to apply on complex shapes. In this paper, we develop a method to enable texture mapping of physical objects, that is, we allow one to map an arbitrary color image onto a three‐dimensional object. Our approach builds upon hydrographics, a technique to transfer pigments printed on a sheet of polymer onto curved surfaces. We first describe a setup that makes the traditional water transfer printing process more accurate and consistent across prints. We then simulate the transfer process using a specialized parameterization to estimate the mapping between the planar color map and the object surface. We demonstrate that our approach enables the application of detailed color maps onto complex shapes such as 3D models of faces and anatomical casts.

Abstract Diffusion curves allow creating complex, smoothly shaded images by diffusing colours defined at curves. These methods typically require the solution of a global optimization problem (over either the pixel grid or an intermediate tessellated representation) to produce the final image, making fully parallel implementation challenging. An alternative approach, inspired by global illumination, uses 2D ray tracing to independently compute each pixel value. This formulation allows trivial parallelism, but it densely computes values even in smooth regions and sacrifices support for instancing and layering. We describe a sparse, ray traced, multi‐layer framework that incorporates many complementary benefits of these existing approaches. Our solution avoids the need for a global solve and trivially allows parallel GPU implementation. We leverage an intermediate triangular representation with cubic patches to synthesize smooth images faithful to the per‐pixel solution. The triangle mesh provides a resolution–independent, vectorial representation and naturally maps diffusion curve images to a form natively supported by standard vector graphics and triangle rasterization pipelines. Our approach supports many features which were previously difficult to incorporate into a single system, including instancing, layering, alpha blending, texturing, local blurring, continuity control and parallel computation. We also show how global diffusion curves can be combined with local painted strokes in one coherent system.

Abstract Renderings of animation sequences with physics‐based Monte Carlo light transport simulations are exceedingly costly to generate frame‐by‐frame, yet much of this computation is highly redundant due to the strong coherence in space, time and among samples. A promising approach pursued in prior work entails subsampling the sequence in space, time, and number of samples, followed by image‐based spatio‐temporal upsampling and denoising. These methods can provide significant performance gains, though major issues remain: firstly, in a multiple scattering simulation, the final pixel color is the composite of many different light transport phenomena, and this conflicting information causes artifacts in image‐based methods. Secondly, motion vectors are needed to establish correspondence between the pixels in different frames, but it is unclear how to obtain them for most kinds of light paths (e.g. an object seen through a curved glass panel). To reduce these ambiguities, we propose a general decomposition framework, where the final pixel color is separated into components corresponding to disjoint subsets of the space of light paths. Each component is accompanied by motion vectors and other auxiliary features such as reflectance and surface normals. The motion vectors of specular paths are computed using a temporal extension of manifold exploration and the remaining components use a specialized variant of optical flow. Our experiments show that this decomposition leads to significant improvements in three image‐based applications: denoising, spatial upsampling, and temporal interpolation.

Editing materials in photos opens up numerous opportunities like turning an unappealing dirt ground into luscious grass and creating a comfortable wool sweater in place of a cheap t-shirt. However, such edits are challenging. Approaches such as 3D rendering and BTF rendering can represent virtually everything, but they are also data intensive and computationally expensive, which makes user interaction difficult. Leaner methods such as texture synthesis are more easily controllable by artists, but also more limited in the range of materials that they handle, for example, grass and wool are typically problematic because of their non-Lambertian reflectance and numerous self-occlusions. We propose a new approach for editing of complex materials in photographs. We extend the texture-by-numbers approach with ideas from texture interpolation. The inputs to our method are coarse user annotation maps that specify the desired output, such as the local scale of the material and the illumination direction. Our algorithm then synthesizes the output from a discrete set of annotated exemplars. A key component of our method is that it can cope with missing data, interpolating information from the available exemplars when needed. This enables production of satisfying results involving materials with complex appearance variations such as foliage, carpet, and fabric from only one or a couple of exemplar photographs.

We present a novel approach to remesh a surface into an isotropic triangular or quad-dominant mesh using a unified local smoothing operator that optimizes both the edge orientations and vertex positions in the output mesh. Our algorithm produces meshes with high isotropy while naturally aligning and snapping edges to sharp features. The method is simple to implement and parallelize, and it can process a variety of input surface representations, such as point clouds, range scans and triangle meshes. Our full pipeline executes instantly (less than a second) on meshes with hundreds of thousands of faces, enabling new types of interactive workflows. Since our algorithm avoids any global optimization, and its key steps scale linearly with input size, we are able to process extremely large meshes and point clouds, with sizes exceeding several hundred million elements. To demonstrate the robustness and effectiveness of our method, we apply it to hundreds of models of varying complexity and provide our cross-platform reference implementation in the supplemental material.

Computing similarities or distances between 3D shapes is a crucial building block for numerous tasks, including shape retrieval, exploration and classification. Current state-of-the-art distance measures mostly consider the overall appearance of the shapes and are less sensitive to fine changes in shape structure or geometry. We presentshape edit distance(SHED) that measures the amount of effort needed to transform one shape into the other, in terms of re-arranging the parts of one shape to match the parts of the other shape, as well as possibly adding and removing parts. The shape edit distance takes into account both the similarity of the overall shape structure and the similarity of individual parts of the shapes. We show that SHED is favorable to state-of-the-art distance measures in a variety of applications and datasets, and is especially successful in scenarios where detecting fine details of the shapes is important, such as shape retrieval and exploration.

We present a framework for designing curl-free tangent vector fields on discrete surfaces. Such vector fields are gradients of locally-defined scalar functions, and this property is beneficial for creating surface parameterizations, since the gradients of the parameterization coordinate functions are then exactly aligned with the designed fields. We introduce a novel definition for discrete curl between unordered sets of vectors (PolyVectors), and devise a curl-eliminating continuous optimization that is independent of the matchings between them. Our algorithm naturally places the singularities required to satisfy the user-provided alignment constraints, and our fields are the gradients of an inversion-free parameterization by design.

We propose an interactive quadrangulation method based on a large collection of patterns that are learned from models manually designed by artists. The patterns are distilled into compact quadrangulation rules and stored in a database. At run-time, the user draws strokes to define patches and desired edge flows, and the system queries the database to extract fitting patterns to tessellate the sketches' interiors. The quadrangulation patterns are general and can be applied to tessellate large regions while controlling the positions of the singularities and the edge flow. We demonstrate the effectiveness of our algorithm through a series of live retopology sessions and an informal user study with three professional artists.

Abstract We introduce N‐PolyVector fields, a generalization of N‐RoSy fields for which the vectors are neither necessarily orthogonal nor rotationally symmetric. We formally define a novel representation for N‐PolyVectors as the root sets of complex polynomials and analyze their topological and geometric properties. A smooth N‐PolyVector field can be efficiently generated by solving a sparse linear system without integer variables. We exploit the flexibility of N‐PolyVector fields to design conjugate vector fields, offering an intuitive tool to generate planar quadrilateral meshes.

Abstract We present a method to automatically segment indoor scenes by detecting repeated objects. Our algorithm scales to datasets with 198 million points and does not require any training data. We propose a trivially parallelizable preprocessing step, which compresses a point cloud into a collection of nearly‐planar patches related by geometric transformations. This representation enables us to robustly filter out noise and greatly reduces the computational cost and memory requirements of our method, enabling execution at interactive rates. We propose a patch similarity measure based on shape descriptors and spatial configurations of neighboring patches. The patches are clustered in a Euclidean embedding space based on the similarity matrix to yield the segmentation of the input point cloud. The generated segmentation can be used to compress the raw point cloud, create an object database, and increase the clarity of the point cloud visualization.

Abstract We present an interactive method to restore severely damaged historical parchments. When damaged by heat in a fire, such manuscripts undergo a complex deformation and contain various geometric distortions such as wrinkling, buckling, and shrinking, rendering them nearly illegible. They cannot be physically flattened due to the risk of further damage. We propose a virtual restoration framework to estimate the non‐rigid deformation the parchment underwent and to revert it, making reading the text significantly easier whilst maintaining the veracity of the textual content. We estimate the deformation by combining automatically extracted constraints with user‐provided hints informed by domain knowledge. We demonstrate that our method successfully flattens and straightens the text on a variety of pages scanned from a 17th century document which fell victim to fire damage.

Abstract We propose an algorithm to quadrangulate an N‐sided patch (2 ≤ N ≤ 6) with prescribed numbers of edge subdivisions at its boundary. Our algorithm is guaranteed to succeed for arbitrary valid input, which is proved using a canonical simplification of the input and a small set of topological patterns that are sufficient for supporting all possible cases. Our algorithm produces solutions with minimal number of irregular vertices by default, but it also allows the user to choose other feasible solutions by solving a set of small integer linear programs. We demonstrate the effectiveness of our algorithm by integrating it into a sketch‐based quad remeshing system. A reference C++ implementation of our algorithm is provided as a supplementary material.

Abstract In the context of real‐time, GPU‐based rendering of animated skinned meshes, we propose a new algorithm to compute surface normals with minimal overhead both in terms of the memory footprint and the required per‐vertex operations. By accounting for the variation of the skinning weights over the surface, we achieve a higher visual quality compared to the standard approximation ubiquitously used in video‐game engines and other real‐time applications. Our method supports Linear Blend Skinning and Dual Quaternion Skinning. We demonstrate the advantages of our technique on a variety of datasets and provide a complete open‐source implementation, including GLSL shaders.

The facial performance of an individual is inherently rich in subtle deformation and timing details. Although these subtleties make the performance realistic and compelling, they often elude both motion capture and hand animation. We present a technique for adding fine-scale details and expressiveness to low-resolution art-directed facial performances, such as those created manually using a rig, via marker-based capture, by fitting a morphable model to a video, or through Kinect reconstruction using recent faceshift technology. We employ a high-resolution facial performance capture system to acquire a representative performance of an individual in which he or she explores the full range of facial expressiveness. From the captured data, our system extracts an expressiveness model that encodes subtle spatial and temporal deformation details specific to that particular individual. Once this model has been built, these details can be transferred to low-resolution art-directed performances. We demonstrate results on various forms of input; after our enhancement, the resulting animations exhibit the same nuances and fine spatial details as the captured performance, with optional temporal enhancement to match the dynamics of the actor. Finally, we show that our technique outperforms the current state-of-the-art in example-based facial animation.

Articulation of 3D characters requires control over many degrees of freedom: a difficult task with standard 2D interfaces. We present a tangible input device composed of interchangeable, hot-pluggable parts. Embedded sensors measure the device's pose at rates suitable for real-time editing and animation. Splitter parts allow branching to accommodate any skeletal tree. During assembly, the device recognizes topological changes as individual parts or pre-assembled subtrees are plugged and unplugged. A novel semi-automatic registration approach helps the user quickly map the device's degrees of freedom to a virtual skeleton inside the character. User studies report favorable comparisons to mouse and keyboard interfaces for the tasks of target acquisition and pose replication. Our device provides input for character rigging and automatic weight computation, direct skeletal deformation, interaction with physical simulations, and handle-based variational geometric modeling.

Self-supporting structures are prominent in historical and contemporary architecture due to advantageous structural properties and efficient use of material. Computer graphics research has recently contributed new design tools that allow creating and interactively exploring self-supporting freeform designs. However, the physical construction of such freeform structures remains challenging, even on small scales. Current construction processes require extensive formwork during assembly, which quickly leads to prohibitively high construction costs for realizations on a building scale. This greatly limits the practical impact of the existing freeform design tools. We propose to replace the commonly used dense formwork with a sparse set of temporary chains. Our method enables gradual construction of the masonry model in stable sections and drastically reduces the material requirements and construction costs. We analyze the input using a variational method to find stable sections, and devise a computationally tractable divide-and-conquer strategy for the combinatorial problem of finding an optimal construction sequence. We validate our method on 3D printed models, demonstrate an application to the restoration of historical models, and create designs of recreational, collaborative self-supporting puzzles.

We consider the problem of reproducing the look and the details of a 3D object on a surface that is confined to a given volume. Classic examples of such "appearance-mimicking" surfaces are bas-reliefs: decorations and artwork depicting recognizable 3D scenes using only a thin volumetric space. The design of bas-reliefs has fascinated humankind for millennia and it is extensively used on coins, medals, pottery and other art forms. We propose a unified framework to create surfaces that depict certain shapes from prescribed viewpoints, as a generalization of bas-reliefs. Given target shapes, viewpoints and space restrictions, our method finds a globally optimal surface that delivers the desired appearance when observed from the designated viewpoints, while guaranteeing exact, per-vertex depth bounds. We use 3D printing to validate our approach and demonstrate our results in a variety of applications, ranging from standard bas-reliefs to optical illusions and carving of complex geometries.

Spinning tops and yo-yos have long fascinated cultures around the world with their unexpected, graceful motions that seemingly elude gravity. We present an algorithm to generate designs for spinning objects by optimizing rotational dynamics properties. As input, the user provides a solid 3D model and a desired axis of rotation. Our approach then modifies the mass distribution such that the principal directions of the moment of inertia align with the target rotation frame. We augment the model by creating voids inside its volume, with interior fill represented by an adaptive multi-resolution voxelization. The discrete voxel fill values are optimized using a continuous, nonlinear formulation. Further, we optimize for rotational stability by maximizing the dominant principal moment. We extend our technique to incorporate deformation and multiple materials for cases where internal voids alone are insufficient. Our method is well-suited for a variety of 3D printed models, ranging from characters to abstract shapes. We demonstrate tops and yo-yos that spin surprisingly stably despite their asymmetric appearance.

We introduce frame fields, which are a non-orthogonal and non-unit-length generalization of cross fields. Frame fields represent smoothly varying linear transformations on tangent spaces of a surface. We propose an algorithm to create discrete, dense frame fields that satisfy a sparse set of constraints. By computing a surface deformation that warps a frame field into a cross field, we generalize existing quadrangulation algorithms to generate anisotropic and non-uniform quad meshes whose elements shapes match the frame field. With this, our framework enables users to control not only the alignment but also the density and anisotropy of the elements' distribution, resulting in high-quality adaptive quad meshing.

We introduce a meta-representation that represents the essence of a family of shapes. The meta-representation learns the configurations of shape parts that are common across the family, and encapsulates this knowledge with a system of geometric distributions that encode relative arrangements of parts. Thus, instead of predefined priors, what characterizes a shape family is directly learned from the set of input shapes. The meta-representation is constructed from a set of co-segmented shapes with known correspondence. It can then be used in several applications where we seek to preserve the identity of the shapes as members of the family. We demonstrate applications of the meta-representation in exploration of shape repositories, where interesting shape configurations can be examined in the set; guided editing, where models can be edited while maintaining their familial traits; and coupled editing, where several shapes can be collectively deformed by directly manipulating the distributions in the meta-representation. We evaluate the efficacy of the proposed representation on a variety of shape collections.

We present a new approach for generating global illumination renderings of hand-drawn characters using only a small set of simple annotations. Our system exploits the concept of bas-relief sculptures, making it possible to generate 3D proxies suitable for rendering without requiring side-views or extensive user input. We formulate an optimization process that automatically constructs approximate geometry sufficient to evoke the impression of a consistent 3D shape. The resulting renders provide the richer stylization capabilities of 3D global illumination while still retaining the 2D hand-drawn look-and-feel. We demonstrate our approach on a varied set of hand-drawn images and animations, showing that even in comparison to ground-truth renderings of full 3D objects, our bas-relief approximation is able to produce convincing global illumination effects, including self-shadowing, glossy reflections, and diffuse color bleeding.

Data acquisition, numerical inaccuracies, and sampling often introduce noise in measurements and simulations. Removing this noise is often necessary for efficient analysis and visualization of this data, yet many denoising techniques change the minima and maxima of a scalar field. For example, the extrema can appear or disappear, spatially move, and change their value. This can lead to wrong interpretations of the data, e.g., when the maximum temperature over an area is falsely reported being a few degrees cooler because the denoising method is unaware of these features. Recently, a topological denoising technique based on a global energy optimization was proposed, which allows the topology-controlled denoising of 2D scalar fields. While this method preserves the minima and maxima, it is constrained by the size of the data. We extend this work to large 2D data and medium-sized 3D data by introducing a novel domain decomposition approach. It allows processing small patches of the domain independently while still avoiding the introduction of new critical points. Furthermore, we propose an iterative refinement of the solution, which decreases the optimization energy compared to the previous approach and therefore gives smoother results that are closer to the input. We illustrate our technique on synthetic and real-world 2D and 3D data sets that highlight potential applications.

Abstract We introduce a single unifying framework for a wide range of content‐aware image warping tasks using a finite element method (FEM). Existing approaches commonly define error terms over vertex finite differences and can be expressed as a special case of our general FEM model. In this work, we exploit the full generality of FEMs, gaining important advantages over prior methods. These advantages include arbitrary mesh connectivity allowing for adaptive meshing and efficient large‐scale solutions, a well‐defined continuous problem formulation that enables clear analysis of existing warping error functions and allows us to propose improved ones, and higher order basis functions that allow for smoother warps with fewer degrees of freedom. To support per‐element basis functions of varying degree and complex mesh connectivity with hanging nodes, we also introduce a novel use of discontinuous Galerkin FEM. We demonstrate the utility of our method by showing examples in video retargeting and camera stabilization applications, and compare our results with previous state of the art methods.

Abstract Geometric meshes that model animated characters must be designed while taking into account the deformations that the shape will undergo during animation. We analyze an input sequence of meshes with point‐to‐point correspondence, and we automatically produce a quadrangular mesh that fits well the input animation. We first analyze the local deformation that the surface undergoes at each point, and we initialize a cross field that remains as aligned as possible to the principal directions of deformation throughout the sequence. We then smooth this cross field based on an energy that uses a weighted combination of the initial field and the local amount of stretch. Finally, we compute a field‐aligned quadrangulation with an off‐the‐shelf method. Our technique is fast and very simple to implement, and it significantly improves the quality of the output quad mesh and its suitability for character animation, compared to creating the quad mesh based on a single pose. We present experimental results and comparisons with a state‐of‐the‐art quadrangulation method, on both sequences from 3D scanning and synthetic sequences obtained by a rough animation of a triangulated model.

Abstract Decades of research have culminated in a robust geometry processing pipeline for surfaces. Most steps in this pipeline, like deformation, smoothing, subdivision and decimation, may create self‐intersections. Volumetric processing of solid shapes then becomes difficult, because obtaining a correct volumetric discretization is impossible: existing tet‐meshing methods require watertight input. We propose an algorithm that produces a tetrahedral mesh that overlaps itself consistently with the self‐intersections in the input surface. This enables volumetric processing on self‐intersecting models. We leverage conformalized mean‐curvature flow, which removes self‐intersections, and define an intrinsically similar reverse flow, which prevents them. We tetrahedralize the resulting surface and map the mesh inside the original surface. We demonstrate the effectiveness of our method with applications to automatic skinning weight computation, physically based simulation and geodesic distance computation.

Abstract Mappings and deformations are ubiquitous in geometry processing, shape modeling, and animation. Numerous deformation energies have been proposed to tackle problems like mesh parameterization and volumetric deformations. We present an algorithm that modifies any deformation energy to guarantee a locally injective mapping, i.e., without inverted elements. Our formulation can be used to compute continuous planar or volumetric piecewise‐linear maps and it uses a barrier term to prevent inverted elements. Differently from previous methods, we carefully design both the barrier term and the associated numerical techniques to be able to provide immediate feedback to the user, enabling interactive manipulation of inversion‐free mappings. Stress tests show that our method robustly handles extreme deformations where previous techniques converge very slowly or even fail. We demonstrate that enforcing local injectivity increases fidelity of the results in applications such as shape deformation and parameterization.

Modern camera calibration and multiview stereo techniques enable users to smoothly navigate between different views of a scene captured using standard cameras. The underlying automatic 3D reconstruction methods work well for buildings and regular structures but often fail on vegetation, vehicles, and other complex geometry present in everyday urban scenes. Consequently, missing depth information makes Image-Based Rendering (IBR) for such scenes very challenging. Our goal is to provide plausible free-viewpoint navigation for such datasets. To do this, we introduce a new IBR algorithm that is robust to missing or unreliable geometry, providing plausible novel views even in regions quite far from the input camera positions. We first oversegment the input images, creating superpixels of homogeneous color content which often tends to preserve depth discontinuities. We then introduce a depth synthesis approach for poorly reconstructed regions based on a graph structure on the oversegmentation and appropriate traversal of the graph. The superpixels augmented with synthesized depth allow us to define a local shape-preserving warp which compensates for inaccurate depth. Our rendering algorithm blends the warped images, and generates plausible image-based novel views for our challenging target scenes. Our results demonstrate novel view synthesis in real time for multiple challenging scenes with significant depth complexity, providing a convincing immersive navigation experience.

Solid shapes in computer graphics are often represented with boundary descriptions, e.g. triangle meshes, but animation, physically-based simulation, and geometry processing are more realistic and accurate when explicit volume representations are available. Tetrahedral meshes which exactly contain (interpolate) the input boundary description are desirable but difficult to construct for a large class of input meshes. Character meshes and CAD models are often composed of many connected components with numerous self-intersections, non-manifold pieces, and open boundaries, precluding existing meshing algorithms. We propose an automatic algorithm handling all of these issues, resulting in a compact discretization of the input's inner volume. We only require reasonably consistent orientation of the input triangle mesh. By generalizing the winding number for arbitrary triangle meshes, we define a function that is a perfect segmentation for watertight input and is well-behaved otherwise. This function guides a graphcut segmentation of a constrained Delaunay tessellation (CDT), providing a minimal description that meets the boundary exactly and may be fed as input to existing tools to achieve element quality. We highlight our robustness on a number of examples and show applications of solving PDEs, volumetric texturing and elastic simulation.

We consider the problem of generalizing affine combinations in Euclidean spaces to triangle meshes: computing weighted averages of points on surfaces. We address both the forward problem , namely computing an average of given anchor points on the mesh with given weights, and the inverse problem , which is computing the weights given anchor points and a target point. Solving the forward problem on a mesh enables applications such as splines on surfaces, Laplacian smoothing and remeshing. Combining the forward and inverse problems allows us to define a correspondence mapping between two different meshes based on provided corresponding point pairs, enabling texture transfer, compatible remeshing, morphing and more. Our algorithm solves a single instance of a forward or an inverse problem in a few microseconds. We demonstrate that anchor points in the above applications can be added/removed and moved around on the meshes at interactive framerates, giving the user an immediate result as feedback.

We present a complete design pipeline that allows non-expert users to design and analyze masonry structures without any structural knowledge. We optimize the force layouts both geometrically and topologically, finding a self-supported structure that is as close as possible to a given target surface. The generated structures are tessellated into hexagonal blocks with a pattern that prevents sliding failure. The models can be used in physically plausible virtual environments or 3D printed and assembled without reinforcements.

Imbalance suggests a feeling of dynamism and movement in static objects. It is therefore not surprising that many 3D models stand in impossibly balanced configurations. As long as the models remain in a computer this is of no consequence: the laws of physics do not apply. However, fabrication through 3D printing breaks the illusion: printed models topple instead of standing as initially intended. We propose to assist users in producing novel, properly balanced designs by interactively deforming an existing model. We formulate balance optimization as an energy minimization, improving stability by modifying the volume of the object, while preserving its surface details. This takes place during interactive editing: the user cooperates with our optimizer towards the end result. We demonstrate our method on a variety of models. With our technique, users can produce fabricated objects that stand in one or more surprising poses without requiring glue or heavy pedestals.

Coarse quad meshes are the preferred representation for animating characters in movies and video games. In these scenarios, artists want explicit control over the edge flows and the singularities of the quad mesh. Despite the significant advances in recent years, existing automatic quad remeshing algorithms are not yet able to achieve the quality of manually created remeshings. We present an interactive system for manual quad remeshing that provides the user with a high degree of control while avoiding the tediousness involved in existing manual tools. With our sketch-based interface the user constructs a quad mesh by defining patches consisting of individual quads. The desired edge flow is intuitively specified by the sketched patch boundaries, and the mesh topology can be adjusted by varying the number of edge subdivisions at patch boundaries. Our system automatically inserts singularities inside patches if necessary, while providing the user with direct control of their topological and geometrical locations. We developed a set of novel user interfaces that assist the user in constructing a curve network representing such patch boundaries. The effectiveness of our system is demonstrated through a user evaluation with professional artists. Our system is also useful for editing automatically generated quad meshes.

Abstract Functions that optimize Laplacian‐based energies have become popular in geometry processing, e.g. for shape deformation, smoothing, multiscale kernel construction and interpolation. Minimizers of Dirichlet energies, or solutions of Laplace equations, are harmonic functions that enjoy the maximum principle, ensuring no spurious local extrema in the interior of the solved domain occur. However, these functions are only C0at the constrained points, which often causes smoothness problems. For this reason, many applications optimize higher‐order Laplacian energies such as biharmonic or triharmonic. Their minimizers exhibit increasing orders of continuity but lose the maximum principle and show oscillations. In this work, we identify characteristic artifacts caused by spurious local extrema, and provide a framework for minimizing quadratic energies on manifolds while constraining the solution to obey the maximum principle in the solved region. Our framework allows the user to specify locations and values of desired local maxima and minima, while preventing any other local extrema. We demonstrate our method on the smoothness energies corresponding to popular polyharmonic functions and show its usefulness for fast handle‐based shape deformation, controllable color diffusion, and topologically‐constrained data smoothing.

Abstract We propose the space of axis‐aligned deformations as the meaningful space for content‐aware image retargeting. Such deformations exclude local rotations, avoiding harmful visual distortions, and they are parameterized in 1D. We show that standard warping energies for image retargeting can be minimized in the space of axis‐aligned deformations while guaranteeing that bijectivity constraints are satisfied, leading to high‐quality, smooth and robust retargeting results. Thanks to the 1D parameterization, our method only requires solving a small quadratic program, which can be done within a few milliseconds on the CPU with no precomputation overhead. We demonstrate how the image size and the saliency map can be changed in real time with our approach, and present results on various input images, including the RetargetMebenchmark. We compare our results with six other algorithms in a user study to demonstrate that the space of axis‐aligned deformations is suitable for the problem at hand.

Skinning transformations are a popular way to articulate shapes and characters. However, traditional animation interfaces require all of the skinning transformations to be specified explicitly, typically using a control structure (a rig). We propose a system where the user specifies only a subset of the degrees of freedom and the rest are automatically inferred using nonlinear, rigidity energies. By utilizing a low-order model and reformulating our energy functions accordingly, our algorithm runs orders of magnitude faster than previous methods without compromising quality. In addition to the immediate boosts in performance for existing modeling and real time animation tools, our approach also opens the door to new modes of control: disconnected skeletons combined with shape-aware inverse kinematics. With automatically generated skinning weights, our method can also be used for fast variational shape modeling.

Current approaches to skeletally-controlled character articulation range from real-time, closed-form skinning methods to offline, physically-based simulation. In this paper, we seek a closed-form skinning method that approximates nonlinear elastic deformations well while remaining very fast. Our contribution is two-fold: (1) we optimize skinning weights for the standard linear and dual quaternion skinning techniques so that the resulting deformations minimize an elastic energy function. We observe that this is not sufficient to match the visual quality of the original elastic deformations and therefore, we develop (2) a new skinning method based on the concept of joint-based deformers . We propose a specific deformer which is visually similar to nonlinear variational deformation methods. Our final algorithm is fully automatic and requires little or no input from the user other than a rest-pose mesh and a skeleton. The runtime complexity requires minimal memory and computational overheads compared to linear blend skinning, while producing higher quality deformations than both linear and dual quaternion skinning.

We present a method for consistent automatic transfer of edits applied to one image to many other images of the same object or scene. By introducing novel, content-adaptive weight functions we enhance the non-rigid alignment framework of Lucas-Kanade to robustly handle changes of view point, illumination and non-rigid deformations of the subjects. Our weight functions are content-aware and possess high-order smoothness, enabling to define high-quality image warping with a low number of parameters using spatially-varying weighted combinations of affine deformations. Optimizing the warp parameters leads to subpixel-accurate alignment while maintaining computation efficiency. Our method allows users to perform precise, localized edits such as simultaneous painting on multiple images in real-time, relieving them from tedious and repetitive manual reapplication to each individual image.

Abstract Image‐based rendering (IBR) techniques allow capture and display of 3D environments using photographs. Modern IBR pipelines reconstruct proxy geometry using multi‐view stereo, reproject the photographs onto the proxy and blend them to create novel views. The success of these methods depends on accurate 3D proxies, which are difficult to obtain for complex objects such as trees and cars. Large number of input images do not improve reconstruction proportionally; surface extraction is challenging even from dense range scans for scenes containing such objects. Our approach does not depend on dense accurate geometric reconstruction; instead we compensate for sparse 3D information by variational image warping. In particular, we formulatesilhouette‐awarewarps that preserve salient depth discontinuities. This improves the rendering of difficult foreground objects, even when deviating from view interpolation. We use a semi‐automatic step to identify depth discontinuities and extract a sparse set of depth constraints used to guide the warp. Our framework is lightweight and results in good quality IBR for previously challenging environments.

Abstract 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.

While often a requirement for geometric models, there has been little research in resolving the interaction of deforming surfaces during real-time modeling sessions. To address this important topic, we introduce an interference algorithm specifically designed for the domain of geometric modeling. This algorithm is general, easily working within existing modeling paradigms to maintain their important properties. Our algorithm is fast, and is able to maintain interactive rates on complex deforming meshes of over 75K faces, while robustly removing intersections. Lastly, our method is controllable, allowing fine-tuning to meet the specific needs of the user. This includes support for minimum separation between surfaces and control over the relative rigidity of interacting objects.

Object deformation with linear blending dominates practical use as the fastest approach for transforming raster images, vector graphics, geometric models and animated characters. Unfortunately, linear blending schemes for skeletons or cages are not always easy to use because they may require manual weight painting or modeling closed polyhedral envelopes around objects. Our goal is to make the design and control of deformations simpler by allowing the user to work freely with the most convenient combination of handle types. We develop linear blending weights that produce smooth and intuitive deformations for points, bones and cages of arbitrary topology. Our weights, called bounded biharmonic weights, minimize the Laplacian energy subject to bound constraints. Doing so spreads the influences of the controls in a shape-aware and localized manner, even for objects with complex and concave boundaries. The variational weight optimization also makes it possible to customize the weights so that they preserve the shape of specified essential object features. We demonstrate successful use of our blending weights for real-time deformation of 2D and 3D shapes.

Skeleton-based linear blend skinning (LBS) remains the most popular method for real-time character deformation and animation. The key to its success is its simple implementation and fast execution. However, in addition to the well-studied elbow-collapse and candy-wrapper artifacts, the space of deformations possible with LBS is inherently limited. In particular, blending with only a scalar weight function per bone prohibits properly handling stretching, where bones change length, and twisting, where the shape rotates along the length of the bone. We present a simple modification of the LBS formulation that enables stretching and twisting without changing the existing skeleton rig or bone weights. Our method needs only an extra scalar weight function per bone, which can be painted manually or computed automatically. The resulting formulation significantly enriches the space of possible deformations while only increasing storage and computation costs by constant factors.

We present a method to globally parameterize a surface represented by height maps over a set of planes (range images). In contrast to other parametrization techniques, we do not start with a manifold mesh. The parametrization we compute defines a manifold structure, it is seamless and globally smooth, can be aligned to geometric features and shows good quality in terms of angle and area preservation, comparable to current parametrization techniques for meshes. Computing such global seamless parametrization makes it possible to perform quad remeshing, texture mapping and texture synthesis and many other types of geometry processing operations. Our approach is based on a formulation of the Poisson equation on a manifold structure defined for the surface by the range images. Construction of such global parametrization requires only a way to project surface data onto a set of planes, and can be applied directly to implicit surfaces, nonmanifold surfaces, very large meshes, and collections of range scans. We demonstrate application of our technique to all these geometry types.

The key to high-quality video resizing is preserving the shape and motion of visually salient objects while remaining temporally-coherent. These spatial and temporal requirements are difficult to reconcile, typically leading existing video retargeting methods to sacrifice one of them and causing distortion or waving artifacts. Recent work enforces temporal coherence of content-aware video warping by solving a global optimization problem over the entire video cube. This significantly improves the results but does not scale well with the resolution and length of the input video and quickly becomes intractable. We propose a new method that solves the scalability problem without compromising the resizing quality. Our method factors the problem into spatial and time/motion components: we first resize each frame independently to preserve the shape of salient regions, and then we optimize their motion using a reduced model for each pathline of the optical flow. This factorization decomposes the optimization of the video cube into sets of sub-problems whose size is proportional to a single frame's resolution and which can be solved in parallel. We also show how to incorporate cropping into our optimization, which is useful for scenes with numerous salient objects where warping alone would degenerate to linear scaling. Our results match the quality of state-of-the-art retargeting methods while dramatically reducing the computation time and memory consumption, making content-aware video resizing scalable and practical.

We introduce a template fitting method for 3D surface meshes. A given template mesh is deformed to closely approximate the input 3D geometry. The connectivity of the deformed template model is automatically adjusted to facilitate the geometric fitting and to ascertain high quality of the mesh elements. The template fitting process utilizes a specially tailored Laplacian processing framework, where in the first, coarse fitting stage we approximate the input geometry with a linearized biharmonic surface (a variant of LS-mesh), and then the fine geometric detail is fitted further using iterative Laplacian editing with reliable correspondence constraints and a local surface flattening mechanism to avoid foldovers. The latter step is performed in the dual mesh domain, which is shown to encourage near-equilateral mesh elements and significantly reduces the occurrence of triangle foldovers, a well-known problem in mesh fitting. To experimentally evaluate our approach, we compare our method with relevant state-of-the-art techniques and confirm significant improvements of results. In addition, we demonstrate the usefulness of our approach to the application of consistent surface parameterization (also known as cross-parameterization).

Abstract Many problems in geometric modeling can be described using variational formulations that define the smoothness of the shape and its behavior w.r.t. the posed modeling constraints. For example, high‐quality C2 surfaces that obey boundary conditions on positions, tangents and curvatures can be conveniently defined as solutions of high‐order geometric PDEs; the advantage of such a formulation is its conceptual representation‐independence. In practice, solving high‐order problems efficiently and accurately for surfaces approximated by meshes is notoriously difficult. For modeling applications, the preferred approach is to use discrete geometric schemes which are efficient and robust, but their convergence properties are less well understood compared to higher‐order FEM. In this paper, we explore discretizations of common geometric PDEs on meshes using mixed finite elements, where additional variables for the derivatives in the problem are introduced. Such formulations use first‐order derivatives only, allowing a discretization with simple linear elements. Various boundary conditions can be naturally discretized in this setting. We formalize continuous region constraints commonly used in modeling applications, and show that these seamlessly fit into the mixed framework. We demonstrate that some of the commonly used discrete geometric discretizations can be regarded as a particular case of mixed finite elements. We study the convergence behavior of our discretizations, and how they can be applied to implement common modeling tasks.

Abstract Data sets coming from simulations or sampling of real‐world phenomena often contain noise that hinders their processing and analysis. Automatic filtering and denoising can be challenging: when the nature of the noise is unknown, it is difficult to distinguish between noise and actual data features; in addition, the filtering process itself may introduce “artificial” features into the data set that were not originally present. In this paper, we propose a smoothing method for 2D scalar fields that gives the user explicit control over the data features. We define features as critical points of the given scalar function, and the topological structure they induce (i.e., the Morse‐Smale complex). Feature significance is rated according to topological persistence. Our method allows filtering out spurious features that arise due to noise by means of topological simplification, providing the user with a simple interface that defines the significance threshold, coupled with immediate visual feedback of the remaining data features. In contrast to previous work, our smoothing method guarantees a C 1 ‐continuous output scalar field with the exact specified features and topological structures.

The numerous works on media retargeting call for a methodological approach for evaluating retargeting results. We present the first comprehensive perceptual study and analysis of image retargeting. First, we create a benchmark of images and conduct a large scale user study to compare a representative number of state-of-the-art retargeting methods. Second, we present analysis of the users' responses, where we find that humans in general agree on the evaluation of the results and show that some retargeting methods are consistently more favorable than others. Third, we examine whether computational image distance metrics can predict human retargeting perception. We show that current measures used in this context are not necessarily consistent with human rankings, and demonstrate that better results can be achieved using image features that were not previously considered for this task. We also reveal specific qualities in retargeted media that are more important for viewers. The importance of our work lies in promoting better measures to assess and guide retargeting algorithms in the future. The full benchmark we collected, including all images, retargeted results, and the collected user data, are available to the research community for further investigation at http://people.csail.mit.edu/mrub/retargetme.

The modeling of volumetric objects is still a difficult problem. Solid texture synthesis methods enable the design of volumes with homogeneous textures, but global features such as smoothly varying colors seen in vegetables and fruits are difficult to model. In this paper, we propose a representation called diffusion surfaces (DSs) to enable modeling such objects. DSs consist of 3D surfaces with colors defined on both sides, such that the interior colors in the volume are obtained by diffusing colors from nearby surfaces. A straightforward way to compute color diffusion is to solve a volumetric Poisson equation with the colors of the DSs as boundary conditions, but it requires expensive volumetric meshing which is not appropriate for interactive modeling. We therefore propose to interpolate colors only locally at user-defined cross-sections using a modified version of the positive mean value coordinates algorithm to avoid volumetric meshing. DSs are generally applicable to model many different kinds of objects with internal structures. As a case study, we present a simple sketch-based interface for modeling objects with rotational symmetries that can also generate random variations of models. We demonstrate the effectiveness of our approach through various DSs models with simple non-photorealistic rendering techniques enabled by DSs.

We introduce a video retargeting method that achieves high-quality resizing to arbitrary aspect ratios for complex videos containing diverse camera and dynamic motions. Previous content-aware retargeting methods mostly concentrated on spatial considerations, attempting to preserve the shape of salient objects in each frame by removing or distorting homogeneous background content. However, sacrificeable space is fundamentally limited in video, since object motion makes foreground and background regions correlated, causing waving and squeezing artifacts. We solve the retargeting problem by explicitly employing motion information and by distributing distortion in both spatial and temporal dimensions. We combine novel cropping and warping operators, where the cropping removes temporally-recurring contents and the warping utilizes available homogeneous regions to mask deformations while preserving motion. Variational optimization allows to find the best balance between the two operations, enabling retargeting of challenging videos with complex motions, numerous prominent objects and arbitrary depth variability. Our method compares favorably with state-of-the-art retargeting systems, as demonstrated in the examples and widely supported by the conducted user study.

Man-made objects are largely dominated by a few typical features that carry special characteristics and engineered meanings. State-of-the-art deformation tools fall short at preserving such characteristic features and global structure. We introduce iWIRES, a novel approach based on the argument that man-made models can be distilled using a few special 1D wires and their mutual relations. We hypothesize that maintaining the properties of such a small number of wires allows preserving the defining characteristics of the entire object. We introduce an analyze-and-edit approach, where prior to editing, we perform a light-weight analysis of the input shape to extract a descriptive set of wires. Analyzing the individual and mutual properties of the wires, and augmenting them with geometric attributes makes them intelligent and ready to be manipulated. Editing the object by modifying the intelligent wires leads to a powerful editing framework that retains the original design intent and object characteristics. We show numerous results of manipulation of man-made shapes using our editing technique.

Most existing image content has low dynamic range (LDR), which necessitates effective methods to display such legacy content on high dynamic range (HDR) devices. Reverse tone mapping operators (rTMOs) aim to take LDR content as input and adjust the contrast intelligently to yield output that recreates the HDR experience. In this paper we show that current rTMO approaches fall short when the input image is not exposed properly. More specifically, we report a series of perceptual experiments using a Brightside HDR display and show that, while existing rTMOs perform well for under-exposed input data, the perceived quality degrades substantially with over-exposure, to the extent that in some cases subjects prefer the LDR originals to images that have been treated with rTMOs. We show that, in these cases, a simple rTMO based on gamma expansion avoids the errors introduced by other methods, and propose a method to automatically set a suitable gamma value for each image, based on the image key and empirical data. We validate the results both by means of perceptual experiments and using a recent image quality metric, and show that this approach enhances visible details without causing artifacts in incorrectly-exposed regions. Additionally, we perform another set of experiments which suggest that spatial artifacts introduced by rTMOs are more disturbing than inaccuracies in the expanded intensities. Together, these findings suggest that when the quality of the input data is unknown, reverse tone mapping should be handled with simple, non-aggressive methods to achieve the desired effect.

Temporal coherence is crucial in content-aware video retargeting. To date, this problem has been addressed by constraining temporally adjacent pixels to be transformed coherently. However, due to the motion-oblivious nature of this simple constraint, the retargeted videos often exhibit flickering or waving artifacts, especially when significant camera or object motions are involved. Since the feature correspondence across frames varies spatially with both camera and object motion, motion-aware treatment of features is required for video resizing. This motivated us to align consecutive frames by estimating interframe camera motion and to constrain relative positions in the aligned frames. To preserve object motion, we detect distinct moving areas of objects across multiple frames and constrain each of them to be resized consistently. We build a complete video resizing framework by incorporating our motion-aware constraints with an adaptation of the scale-and-stretch optimization recently proposed by Wang and colleagues. Our streaming implementation of the framework allows efficient resizing of long video sequences with low memory cost. Experiments demonstrate that our method produces spatiotemporally coherent retargeting results even for challenging examples with complex camera and object motion, which are difficult to handle with previous techniques.

We present a "scale-and-stretch" warping method that allows resizing images into arbitrary aspect ratios while preserving visually prominent features. The method operates by iteratively computing optimal local scaling factors for each local region and updating a warped image that matches these scaling factors as closely as possible. The amount of deformation of the image content is guided by a significance map that characterizes the visual attractiveness of each pixel; this significance map is computed automatically using a novel combination of gradient and salience-based measures. Our technique allows diverting the distortion due to resizing to image regions with homogeneous content, such that the impact on perceptually important features is minimized. Unlike previous approaches, our method distributes the distortion in all spatial directions, even when the resizing operation is only applied horizontally or vertically, thus fully utilizing the available homogeneous regions to absorb the distortion. We develop an efficient formulation for the nonlinear optimization involved in the warping function computation, allowing interactive image resizing.

This survey reviews the recent advances in linear variational mesh deformation techniques. These methods were developed for editing detailed high-resolution meshes, like those produced by scanning real-world objects. The challenge of manipulating such complex surfaces is three-fold: the deformation technique has to be sufficiently fast, robust, and intuitive and easy to control to be useful for interactive applications. An intuitive, and thus predictable, deformation tool should provide physically plausible and aesthetically pleasing surface deformations, which in particular requires its geometric details to be preserved. The methods we survey generally formulate surface deformation as a global variational optimization problem that addresses the differential properties of the edited surface. Efficiency and robustness are achieved by linearizing the underlying objective functional, such that the global optimization amounts to solving a sparse linear system of equations. We review the different deformation energies and detail preservation techniques that were proposed in the recent years, together with the various techniques to rectify the linearization artifacts. Our goal is to provide the reader with a systematic classification and comparative description of the different techniques, revealing the strengths and weaknesses of each approach in common editing scenarios.

Abstract We describe a system for the animation of a skeleton‐controlled articulated object that preserves the fine geometric details of the object skin and conforms to the characteristic shapes of the object specified through a set of examples. The system provides the animator with an intuitive user interface and produces compelling results even when presented with a very small set of examples. In addition it is able to generalize well by extrapolating far beyond the examples.

This paper presents a system for designing freeform surfaces with a collection of 3D curves. The user first creates a rough 3D model by using a sketching interface. Unlike previous sketching systems, the user-drawn strokes stay on the model surface and serve as handles for controlling the geometry. The user can add, remove, and deform these control curves easily, as if working with a 2D line drawing. The curves can have arbitrary topology; they need not be connected to each other. For a given set of curves, the system automatically constructs a smooth surface embedding by applying functional optimization. Our system provides real-time algorithms for both control curve deformation and the subsequent surface optimization. We show that one can create sophisticated models using this system, which have not yet been seen in previous sketching or functional optimization systems.

We present a method for inhomogeneous 2D texture mapping guided by a feature mask, that preserves some regions of the image, such as foreground objects or other prominent parts. The method is able to arbitrarily warp a given image while preserving the shape of its features by constraining their deformation to be a similarity transformation. In particular, our method allows global or local changes to the aspect ratio of the texture without causing undesirable shearing to the features. The algorithmic core of our method is a particular formulation of the Laplacian editing technique, suited to accommodate similarity constraints on parts of the domain. The method is useful in digital imaging, texture design and any other applications involving image warping, where parts of the image have high familiarity and should retain their shape after modification.

Abstract Surface representation and processing is one of the key topics in computer graphics and geometric modeling, since it greatly affects the range of possible applications. In this paper we will present recent advances in geometry processing that are related to the Laplacian processing framework and differential representations. This framework is based on linear operators defined on polygonal meshes, and furnishes a variety of processing applications, such as shape approximation and compact representation, mesh editing, watermarking and morphing. The core of the framework is the definition of differential coordinates and new bases for efficient mesh geometry representation, based on the mesh Laplacian operator.

Harmonic colors are sets of colors that are aesthetically pleasing in terms of human visual perception. In this paper, we present a method that enhances the harmony among the colors of a given photograph or of a general image, while remaining faithful, as much as possible, to the original colors. Given a color image, our method finds the best harmonic scheme for the image colors. It then allows a graceful shifting of hue values so as to fit the harmonic scheme while considering spatial coherence among colors of neighboring pixels using an optimization technique. The results demonstrate that our method is capable of automatically enhancing the color "look-and-feel" of an ordinary image. In particular, we show the results of harmonizing the background image to accommodate the colors of a foreground image, or the foreground with respect to the background, in a cut-and-paste setting. Our color harmonization technique proves to be useful in adjusting the colors of an image composed of several parts taken from different sources.

This article presents an algebraic analysis of a mesh-compression technique called high-pass quantization [Sorkine et al. 2003]. In high-pass quantization, a rectangular matrix based on the mesh topological Laplacian is applied to the vectors of the Cartesian coordinates of a polygonal mesh. The resulting vectors, called δ-coordinates, are then quantized. The applied matrix is a function of the topology of the mesh and the indices of a small set of mesh vertices (anchors) but not of the location of the vertices. An approximation of the geometry can be reconstructed from the quantized δ-coordinates and the spatial locations of the anchors. In this article, we show how to algebraically bound the reconstruction error that this method generates. We show that the small singular value of the transformation matrix can be used to bound both the quantization error and the rounding error which is due to the use of floating-point arithmetic. Furthermore, we prove a bound on this singular value. The bound is a function of the topology of the mesh and of the selected anchors. We also propose a new anchor-selection algorithm, inspired by this bound. We show experimentally that the method is effective and that the computed upper bound on the error is not too pessimistic.

We introduce a rigid motion invariant mesh representation based on discrete forms defined on the mesh. The reconstruction of mesh geometry from this representation requires solving two sparse linear systems that arise from the discrete forms: the first system defines the relationship between local frames on the mesh, and the second encodes the position of the vertices via the local frames. The reconstructed geometry is unique up to a rigid transformation of the mesh. We define surface editing operations by placing user-defined constraints on the local frames and the vertex positions. These constraints are incorporated in the two linear reconstruction systems, and their solution produces a deformed surface geometry that preserves the local differential properties in the least-squares sense. Linear combination of shapes expressed with our representation enables linear shape interpolation that correctly handles rotations. We demonstrate the effectiveness of the new representation with various detail-preserving editing operators and shape morphing.

In this paper we present a method for the intuitive editing of surface meshes by means of view-dependent sketching. In most existing shape deformation work, editing is carried out by selecting and moving a handle , usually a set of vertices. Our system lets the user easily determine the handle, either by silhouette selection and cropping, or by sketching directly onto the surface. Subsequently, an edit is carried out by sketching a new, view-dependent handle position or by indirectly influencing differential properties along the sketch. Combined, these editing and handle metaphors greatly simplify otherwise complex shape modeling tasks.

We introduce a new class of shape approximation techniques for irregular triangular meshes. Our method approximates the geometry of the mesh using a linear combination of a small number of basis vectors. The basis vectors are functions of the mesh connectivity and of the mesh indices of a number of anchor vertices. There is a fundamental difference between the bases generated by our method and those generated by geometry-oblivious methods, such as Laplacian-based spectral methods. In the latter methods, the basis vectors are functions of the connectivity alone. The basis vectors of our method, in contrast, are geometry-aware since they depend on both the connectivity and on a binary tagging of vertices that are "geometrically important" in the given mesh (e.g., extrema). We show that, by defining the basis vectors to be the solutions of certain least-squares problems, the reconstruction problem reduces to solving a single sparse linear least-squares problem. We also show that this problem can be solved quickly using a state-of-the-art sparse-matrix factorization algorithm. We show how to select the anchor vertices to define a compact effective basis from which an approximated shape can be reconstructed. Furthermore, we develop an incremental update of the factorization of the least-squares system. This allows a progressive scheme where an initial approximation is incrementally refined by a stream of anchor points. We show that the incremental update and solving the factored system are fast enough to allow an online refinement of the mesh geometry.

One of the main challenges in editing a mesh is to retain the visual appearance of the surface after applying various modifications. In this paper we advocate the use of linear differential coordinates as means to preserve the high-frequency detail of the surface. The differential coordinates represent the details and are defined by a linear transformation of the mesh vertices. This allows the reconstruction of the edited surface by solving a linear system that satisfies the reconstruction of the local details in least squares sense. Since the differential coordinates are defined in a global coordinate system they are not rotation-invariant. To compensate for that, we rotate them to agree with the rotation of an approximated local frame. We show that the linear least squares system can be solved fast enough to guarantee interactive response time thanks to a precomputed factorization of the coefficient matrix. We demonstrate that our approach enables to edit complex detailed meshes while keeping the shape of the details in their natural orientation.

In this paper we introduce least-squares meshes: meshes with a prescribed connectivity that approximate a set of control points in a least-squares sense. The given mesh consists of a planar graph with arbitrary connectivity and a sparse set of control points with geometry. The geometry of the mesh is reconstructed by solving a sparse linear system. The linear system not only defines a surface that approximates the given control points, but it also distributes the vertices over the surface in a fair way. That is, each vertex lies as close as possible to the center of gravity of its immediate neighbors. The least-squares meshes (LS-meshes) are a visually smooth and fair approximation of the given control points. We show that the connectivity of the mesh contains geometric information that affects the shape of the reconstructed surface. Finally, we discuss the applicability of LS-meshes to approximation of given surfaces, smooth completion and mesh editing.

From-region visibility culling is considered harder than from-point visibility culling, since it is inherently four-dimensional. We present a conservative occlusion culling method based on factorizing the 4D visibility problem into horizontal and vertical components. The visibility of the two components is solved asymmetrically: the horizontal component is based on a parameterization of the ray space, and the visibility of the vertical component is solved by incrementally merging umbrae. The technique is designed so that the horizontal and vertical operations can be efficiently realized together by modern graphics hardware. Similar to image-based from-point methods, we use an occlusion map to encode visibility; however, the image-space occlusion map is in the ray space rather than in the primal space. Our results show that the culling time and the size of the computed potentially visible set depend on the size of the viewcell. For moderate viewcells, conservative occlusion culling of large urban scenes takes less than a second, and the size of the potentially visible set is only about two times larger than the size of the exact visible set.

Many computer graphics operations, such as texture mapping, 3D painting, remeshing, mesh compression, and digital geometry processing, require finding a low-distortion parameterization for irregular connectivity triangulations of arbitrary genus 2-manifolds. This paper presents a simple and fast method for computing parameterizations with strictly bounded distortion. The new method operates by flattening the mesh onto a region of the 2D plane. To comply with the distortion bound, the mesh is automatically cut and partitioned on-the-fly. The method guarantees avoiding global and local self-intersections, while attempting to minimize the total length of the introduced seams. To our knowledge, this is the first method to compute the mesh partitioning and the parameterization simultaneously and entirely automatically, while providing guaranteed distortion bounds. Our results on a variety of objects demonstrate that the method is fast enough to work with large complex irregular meshes in interactive applications.