We present a computational framework for numerical homogenization of origami materials—thin sheets structured with periodic crease patterns that, once folded, exhibit diverse and often unusual mechanical properties. Whereas the in-plane stiffness of conventional sheet materials is typically orders of magnitude larger than their resistance to bending, origami-based folding introduces geometric structure that can drastically reshape both bending and stretching behavior. However, predicting how a particular crease pattern gives rise to effective macroscopic properties remains challenging due to the complex coupling of crease geometry, folding kinematics, and surface deformations. In this work, we introduce a computational framework that integrates simulation-based folding and numerical homogenization to explore the relationship between crease pattern and effective material behavior. To describe the macromechanical response of origami materials, we employ a quadratic energy model based on Classical Laminate Theory, together with a simplified treatment of crease plasticity. Our unified representation accommodates both straight- and curved-crease designs, revealing a rich space of origami materials with diverse behavior. In particular, we examine how pattern symmetry governs material symmetries, demonstrating examples that span the full spectrum from perfectly isotropic to highly anisotropic membrane and bending responses. Our framework further enables controlled exploration of parameter variations, illustrating how geometric features such as crease curvature shape macroscopic mechanical behavior. We showcase the potential of this approach through a broad set of examples, ranging from canonical straight-crease patterns such as Miura-ori to complex curved-crease tessellations. While a quantitative analysis is left for future work, we validate our homogenized descriptions against native-scale simulations and qualitatively compare deformation behaviors with real-world prototypes.

Numerous tasks in robotics and character animation involve solving combinations of inverse kinematics and motion planning problems that require the precise design of pose sequences to achieve desired motion objectives. Accounting for the complex interplay between body deformations and resulting motion, especially through interactions with the environment, poses significant challenges for the design of such pose sequences. We propose a computational framework to address these challenges in scenarios where the motion of a deformable body is entirely determined by dynamic changes of its shape. Complementing recent methods on the forward problem—mapping shape sequences to global motion trajectories based on a geometric formulation of locomotion—we address the inverse problem of optimizing shape sequences to achieve user-defined motion objectives. We demonstrate the effectiveness of our method through a diverse set of examples, producing realistic shape sequences that result in desired motion trajectories.

We introduce C-tubes , 3D tubular structures composed of developable surface strips. C-tubes can be understood as a generalization of Monge surfaces—a special class of sweep surfaces—towards the recently introduced conenets. This observation allows formulating a constructive algorithm to create tubular structures that ensures developability of the constituent surfaces, while significantly broadening the design space. Our novel form-finding tool enables design exploration by solving for the input variables of the constructive algorithm so that the C-tube best conforms to user-specified objectives. We discuss several case studies that illustrate the versatility of our approach for the design and fabrication of complex structures, with applications in architecture, furniture, and lighting design.

Bending-active structures are composed of elastic elements that deform to achieve a desired target shape. To support effective design, inverse algorithms have been proposed that optimize the geometry of each element specifically for each design. This makes it difficult to reuse elements across designs or gain efficiency in fabrication through mass production. We address this issue and propose a computational framework to rationalize bending-active structures into a sparse kit of parts. Our method solves for the optimal part geometry such that multiple input designs can be faithfully realized with the same kit of parts. Assigning parts to different assemblies leads to a combinatorial explosion that makes exhaustive search intractable. Instead, we propose a relaxed continuous optimization incorporating a physics-based simulation in its inner loop to model the elastic deformation of the bending-active structure accurately. Our algorithm allows analyzing different design trade-offs of a kit of parts to tune the balance between fabrication complexity and fidelity to the original designs. We demonstrate our method on three different classes of bending-active structures, showcasing the effectiveness of our approach for part reuse and sustainable practices in fabrication-driven design.

We study ensembles of elastic rods that are tensioned by a small set of inextensible cables. The cables induce forces that deform the initially straight, but flexible rods into 3D space curves at equilibrium. Rods can be open or closed, knotted, and arranged in arbitrary topologies. We specifically focus on equilibrium states with no contacts among rods. Our setup can thus be seen as a generalization of classical tensegrities that are composed of rigid rods and tensile cables, to also support rods that elastically deform. We show how this generalization leads to a rich design space, where complex target shapes can be achieved with a small set of elastic rods. To explore this space, we present an inverse design optimization algorithm that solves for the length and placement of cables such that the equilibrium state of the rod network best approximates a given set of input curves. We introduce appropriate sparsity terms to minimize the number of required cables, which significantly simplifies fabrication. Using our algorithm, we explore new classes of bending-active 3D structures, including elastic tensegrity knots that only require a few internal cables. We design and fabricate several physical models from basic materials that attain complex 3D shapes with unique structural properties.

Surface-based inflatables are composed of two thin layers of nearly inextensible sheet material joined together along carefully selected fusing curves. During inflation, pressure forces separate the two sheets to maximize the enclosed volume. The fusing curves restrict this expansion, leading to a spatially varying in-plane contraction and hence metric frustration. The inflated structure settles into a 3D equilibrium that balances pressure forces with the internal elastic forces of the sheets. We present a computational framework for analyzing and designing surface-based inflatable structures with arbitrary fusing patterns. Our approach employs numerical homogenization to characterize the behavior of parametric families of periodic inflatable patch geometries, which can then be combined to tessellate the sheet with smoothly varying patterns. We propose a novel parametrization of the underlying deformation space that allows accurate, efficient, and systematical analysis of the stretching and bending behavior of inflated patches with potentially open boundaries. We apply our homogenization algorithm to create a database of geometrically diverse fusing patterns spanning a wide range of material properties and deformation characteristics. This database is employed in an inverse design algorithm that solves for fusing curves to best approximate a given input target surface. Local patches are selected and blended to form a global network of curves based on a geometric flattening algorithm. These fusing curves are then further optimized to minimize the distance of the deployed structure to target surface. We show that this approach offers greater flexibility to approximate given target geometries compared to previous work while significantly improving structural performance.

We introduce a computational pipeline for simulating and designing C-shells , a new class of planar-to-spatial deployable linkage structures. A C-shell is composed of curved flexible beams connected at rotational joints that can be assembled in a stress-free planar configuration. When actuated, the elastic beams deform and the assembly deploys towards the target 3D shape. We propose two alternative computational design approaches for C-shells: (i) Forward exploration simulates the deployed shape from a planar beam layout provided by the user. Once a satisfactory overall shape is found, a subsequent design optimization adapts the beam geometry to reduce the elastic energy of the linkage while preserving the target shape. (ii) Inverse design is facilitated by a new geometric flattening method that takes a design surface as input and computes an initial layout of piecewise straight linkage beams. Our design optimization algorithm then calculates the smooth curved beams to best reproduce the target shape at minimal elastic energy. We find that C-shells offer a rich space for design and show several studies that highlight new shape topologies that cannot be achieved with existing deployable linkage structures.

We present an algorithmic approach to discover, study, and design multistable elastic knots. Elastic knots are physical realizations of closed curves embedded in 3-space. When endowed with the material thickness and bending resistance of a physical wire, these knots settle into equilibrium states that balance the forces induced by elastic deformation and self-contacts of the wire. In general, elastic knots can have many distinct equilibrium states, i.e. they are multistable mechanical systems. We propose a computational pipeline that combines randomized spatial sampling and physics simulation to efficiently find stable equilibrium states of elastic knots. Leveraging results from knot theory, we run our pipeline on thousands of different topological knot types to create an extensive data set of multistable knots. By applying a series of filters to this data, we discover new transformable knots with interesting geometric and physical properties. A further analysis across knot types reveals geometric and topological patterns, yielding constructive principles that generalize beyond the currently tabulated knot types. We show how multistable elastic knots can be used to design novel deployable structures and engaging recreational puzzles. Several physical prototypes at different scales highlight these applications and validate our simulation.

Mechanical metamaterials enable customizing the elastic properties of physical objects by altering their fine-scale structure. A broad gamut of effective material properties can be produced even from a single fabrication material by optimizing the geometry of a periodic microstructure tiling. Past work has extensively studied the capabilities of microstructures in the small-displacement regime, where periodic homogenization of linear elasticity yields computationally efficient optimal design algorithms. However, many applications involve flexible structures undergoing large deformations for which the accuracy of linear elasticity rapidly deteriorates due to geometric nonlinearities. Design of microstructures at finite strains involves a massive increase in computation and is much less explored; no computational tool yet exists to design metamaterials emulating target hyperelastic laws over finite regions of strain space. We make an initial step in this direction, developing algorithms to accelerate homogenization and metamaterial design for nonlinear elasticity and building a complete framework for the optimal design of planar metamaterials. Our nonlinear homogenization method works by efficiently constructing an accurate interpolant of a microstructure's deformation over a finite space of macroscopic strains likely to be endured by the metamaterial. From this interpolant, the homogenized energy density, stress, and tangent elasticity tensor describing the microstructure's effective properties can be inexpensively computed at any strain. Our design tool then fits the effective material properties to a target constitutive law over a region of strain space using a parametric shape optimization approach, producing a directly manufacturable geometry. We systematically test our framework by designing a catalog of materials fitting isotropic Hooke's laws as closely as possible. We demonstrate significantly improved accuracy over traditional linear metamaterial design techniques by fabricating and testing physical prototypes.

We present a computational inverse design framework for a new class of volumetric deployable structures that have compact rest states and deploy into bending-active 3D target surfaces. Umbrella meshes consist of elastic beams, rigid plates, and hinge joints that can be directly printed or assembled in a zero-energy fabrication state. During deployment, as the elastic beams of varying heights rotate from vertical to horizontal configurations, the entire structure transforms from a compact block into a target curved surface. Umbrella Meshes encode both intrinsic and extrinsic curvature of the target surface and in principle are free from the area expansion ratio bounds of past auxetic material systems. We build a reduced physics-based simulation framework to accurately and efficiently model the complex interaction between the elastically deforming components. To determine the mesh topology and optimal shape parameters for approximating a given target surface, we propose an inverse design optimization algorithm initialized with conformal flattening. Our algorithm minimizes the structure's strain energy in its deployed state and optimizes actuation forces so that the final deployed structure is in stable equilibrium close to the desired surface with few or no external constraints. We validate our approach by fabricating a series of physical models at various scales using different manufacturing techniques.

Abstract An assembly refers to a collection of parts joined together to achieve a specific form and/or functionality. Designing assemblies is a non‐trivial task as a slight local modification on a part's geometry or its joining method could have a global impact on the structural and/or functional performance of the whole assembly. Assemblies can be classified asstructuresthat transmit force to carry loads andmechanismsthat transfer motion and force to perform mechanical work. In this state‐of‐the‐art report, we focus on computational design of structures with rigid parts, which generally can be formulated as a geometric modeling and optimization problem. We broadly classify existing computational design approaches, mainly from the computer graphics community, according to high‐level design objectives, including fabricability, structural stability, reconfigurability, and tileability. Computational analysis of various aspects of assemblies is an integral component in these design approaches. We review different classes of computational analysis and design methods, discuss their strengths and limitations, make connections among them, and propose possible directions for future research.

We present Bistable Auxetic Surface Structures , a novel deployable material system based on optimized bistable auxetic cells. Such a structure can be flat-fabricated from elastic sheet material, then deployed towards a desired double-curved target shape by activating the bistable mechanism of its component cells. A unique feature is that the deployed model is by design in a stable state. This facilitates deployment without the need of complex external supports or boundary constraints. We introduce a computational solution for the inverse design of our Bistable Auxetic Surface Structures. Our algorithm first precomputes a library of bistable auxetic cells to cover a range of in-plane expansion / contraction ratios, while maximizing the bistability and stiffness of the cell to ensure robust deployment. We then use metric distortion analysis of the target surface to compute the planar fabrication state as a composition of cells that best matches the desired deployment deformation. As each cell expands or contracts during deployment, metric frustration forces the surface towards its target equilibrium state. We validate our method with several physical prototypes.

We present a computational inverse design method for a new class of surface-based inflatable structure. Our deployable structures are fabricated by fusing together two layers of inextensible sheet material along carefully selected curves. The fusing curves form a network of tubular channels that can be inflated with air or other fluids. When fully inflated, the initially flat surface assumes a programmed double-curved shape and becomes stiff and load-bearing. We present a method that solves for the layout of air channels that, when inflated, best approximate a given input design. For this purpose, we integrate a forward simulation method for inflation with a gradient-based optimization algorithm that continuously adapts the geometry of the air channels to improve the design objectives. To initialize this non-linear optimization, we propose a novel surface flattening algorithm. When a channel is inflated, it approximately maintains its length, but contracts transversally to its main direction. Our algorithm approximates this deformation behavior by computing a mapping from the 3D design surface to the plane that allows for anisotropic metric scaling within the bounds realizable by the physical system. We show a wide variety of inflatable designs and fabricate several prototypes to validate our approach and highlight potential applications.

In this paper we study Weingarten surfaces and explore their potential for fabrication-aware design in freeform architecture. Weingarten surfaces are characterized by a functional relation between their principal curvatures that implicitly defines approximate local congruences on the surface. These symmetries can be exploited to simplify surface paneling of double-curved architectural skins through mold re-use. We present an optimization approach to find a Weingarten surface that is close to a given input design. Leveraging insights from differential geometry, our method aligns curvature isolines of the surface in order to contract the curvature diagram from a 2D region into a 1D curve. The unknown functional curvature relation then emerges as the result of the optimization. We show how a robust and efficient numerical shape approximation method can be implemented using a guided projection approach on a high-order B-spline representation. This algorithm is applied in several design studies to illustrate how Weingarten surfaces define a versatile shape space for fabrication-aware exploration in freeform architecture. Our optimization algorithm provides the first practical tool to compute general Weingarten surfaces with arbitrary curvature relation, thus enabling new investigations into a rich, but as of yet largely unexplored class of surfaces.

Basket weaving is a traditional craft for creating curved surfaces as an interwoven array of thin, flexible, and initially straight ribbons. The three-dimensional shape of a woven structure emerges through a complex interplay of the elastic bending behavior of the ribbons and the contact forces at their crossings. Curvature can be injected by carefully placing topological singularities in the otherwise regular weaving pattern. However, shape control through topology is highly non-trivial and inherently discrete, which severely limits the range of attainable woven geometries. Here, we demonstrate how to construct arbitrary smooth free-form surface geometries by weaving carefully optimized curved ribbons. We present an optimization-based approach to solving the inverse design problem for such woven structures. Our algorithm computes the ribbons' planar geometry such that their interwoven assembly closely approximates a given target design surface in equilibrium. We systematically validate our approach through a series of physical prototypes to show a broad range of new woven geometries that is not achievable by existing methods. We anticipate our computational approach to significantly enhance the capabilities for the design of new woven structures. Facilitated by modern digital fabrication technology, we see potential applications in material science, bio- and mechanical engineering, art, design, and architecture.

We present a computational framework for modeling and optimizing complex assemblies using cone joints. Cone joints are integral joints that generalize traditional single-direction joints such as mortise and tenon joints to support a general cone of directions for assembly. This additional motion flexibility not just reduces the risk of deadlocking for complex joint arrangements, but also simplifies the assembly process, in particular for automatic assembly by robots. On the other hand, compared to planar contacts, cone joints restrict relative part movement for improved structural stability. Cone joints can be realized in the form of curved contacts between associated parts, which have demonstrated good mechanical properties such as reduced stress concentration. To find the best trade-off between assemblability and stability, we propose an optimization approach that first determines the optimal motion cone for each part contact and subsequently derives a geometric realization of each joint to match this motion cone. We demonstrate that our approach can optimize cone joints for assemblies with a variety of geometric forms, and highlight several application examples.

We present X-shells , a new class of deployable structures formed by an ensemble of elastically deforming beams coupled through rotational joints. An X-shell can be assembled conveniently in a flat configuration from standard elastic beam elements and then deployed through force actuation into the desired 3D target state. During deployment, the coupling imposed by the joints will force the beams to twist and buckle out of plane to maintain a state of static equilibrium. This complex interaction of discrete joints and continuously deforming beams allows interesting 3D forms to emerge. Simulating X-shells is challenging, however, due to unstable equilibria at the onset of beam buckling. We propose an optimization-based simulation framework building on a discrete rod model that robustly handles such difficult scenarios by analyzing and appropriately modifying the elastic energy Hessian. This real-time simulation method forms the basis of a computational design tool for X-shells that enables interactive design space exploration by varying and optimizing design parameters to achieve a specific design intent. We jointly optimize the assembly state and the deployed configuration to ensure the geometric and structural integrity of the deployable X-shell. Once a design is finalized, we also optimize for a sparse distribution of actuation forces to efficiently deploy it from its flat assembly state to its 3D target state. We demonstrate the effectiveness of our design approach with a number of design studies that highlight the richness of the X-shell design space, enabling new forms not possible with existing approaches. We validate our computational model with several physical prototypes that show excellent agreement with the optimized digital models.

We study assemblies of convex rigid blocks regularly arranged to approximate a given freeform surface. Our designs rely solely on the geometric arrangement of blocks to form a stable assembly, neither requiring explicit connectors or complex joints, nor relying on friction between blocks. The convexity of the blocks simplifies fabrication, as they can be easily cut from different materials such as stone, wood, or foam. However, designing stable assemblies is challenging, since adjacent pairs of blocks are restricted in their relative motion only in the direction orthogonal to a single common planar interface surface. We show that despite this weak interaction, structurally stable, and in some cases, globally interlocking assemblies can be found for a variety of freeform designs. Our optimization algorithm is based on a theoretical link between static equilibrium conditions and a geometric, global interlocking property of the assembly---that an assembly is globally interlocking if and only if the equilibrium conditions are satisfied for arbitrary external forces and torques. Inspired by this connection, we define a measure of stability that spans from single-load equilibrium to global interlocking, motivated by tilt analysis experiments used in structural engineering. We use this measure to optimize the geometry of blocks to achieve a static equilibrium for a maximal cone of directions, as opposed to considering only self-load scenarios with a single gravity direction. In the limit, this optimization can achieve globally interlocking structures. We show how different geometric patterns give rise to a variety of design options and validate our results with physical prototypes.

Deployable structures are physical mechanisms that can easily transition between two or more geometric configurations; such structures enable industrial, scientific, and consumer applications at a wide variety of scales. This paper develops novel deployable structures that can approximate a large class of doubly-curved surfaces and are easily actuated from a flat initial state via inflation or gravitational loading. The structures are based on two-dimensional rigid mechanical linkages that implicitly encode the curvature of the target shape via a user-programmable pattern that permits locally isotropic scaling under load. We explicitly characterize the shapes that can be realized by such structures---in particular, we show that they can approximate target surfaces of positive mean curvature and bounded scale distortion relative to a given reference domain. Based on this observation, we develop efficient computational design algorithms for approximating a given input geometry. The resulting designs can be rapidly manufactured via digital fabrication technologies such as laser cutting, CNC milling, or 3D printing. We validate our approach through a series of physical prototypes and present several application case studies, ranging from surgical implants to large-scale deployable architecture.

Interlocking assemblies have a long history in the design of puzzles, furniture, architecture, and other complex geometric structures. The key defining property of interlocking assemblies is that all component parts are immobilized by their geometric arrangement, preventing the assembly from falling apart. Computer graphics research has recently contributed design tools that allow creating new interlocking assemblies. However, these tools focus on specific kinds of assemblies and explore only a limited space of interlocking configurations, which restricts their applicability for design. In this paper, we propose a new general framework for designing interlocking assemblies. The core idea is to represent part relationships with a family of base Directional Blocking Graphs and leverage efficient graph analysis tools to compute an interlocking arrangement of parts. This avoids the exponential complexity of brute-force search. Our algorithm iteratively constructs the geometry of assembly components, taking advantage of all existing blocking relations for constructing successive parts. As a result, our approach supports a wider range of assembly forms compared to previous methods and provides significantly more design flexibility. We show that our framework facilitates efficient design of complex interlocking assemblies, including new solutions that cannot be achieved by state of the art approaches.

We present a robust algorithm for personalizing a sphere-mesh tracking model to a user from a collection of depth measurements. Our core contribution is to demonstrate how simple geometric reasoning can be exploited to build a shape-space, and how its performance is comparable to shape-spaces constructed from datasets of carefully calibrated models. We achieve this goal by first re-parameterizing the geometry of the tracking template, and introducing a multi-stage calibration optimization. Our novel parameterization decouples the degrees of freedom for pose and shape, resulting in improved convergence properties. Our analytically differentiable multi-stage calibration pipeline optimizes for the model in the natural low-dimensional space of local anisotropic scalings, leading to an effective solution that can be easily embedded in other tracking/calibration algorithms. Compared to existing sphere-mesh calibration algorithms, quantitative experiments assess our algorithm possesses a larger convergence basin, and our personalized models allows to perform motion tracking with superior accuracy.

Abstract Understanding patterns of variation from raw measurement data remains a central goal of shape analysis. Such an understanding reveals which elements are repeated, or how elements can be derived as structured variations from a common base element. We investigate this problem in the context of 3D acquisitions of buildings. Utilizing a set of template models, we discover geometric similarities across a set of building elements. Each template is equipped with a deformation model that defines variations of a base geometry. Central to our algorithm is a simultaneous template matching and deformation analysis that detects patterns across building elements by extracting similarities in the deformation modes of their matching templates. We demonstrate that such an analysis can successfully detect structured variations even for noisy and incomplete data.

We introduce design transformations for rule-based procedural models, e.g., for buildings and plants. Given two or more procedural designs, each specified by a grammar, a design transformation combines elements of the existing designs to generate new designs. We introduce two technical components to enable design transformations. First, we extend the concept of discrete rule switching to rule merging, leading to a very large shape space for combining procedural models. Second, we propose an algorithm to jointly derive two or more grammars, called grammar co-derivation. We demonstrate two applications of our work: we show that our framework leads to a larger variety of models than previous work, and we show fine-grained transformation sequences between two procedural models.

We present a novel physics-based approach to facial animation. Contrary to commonly used generative methods, our solution computes facial expressions by minimizing a set of non-linear potential energies that model the physical interaction of passive flesh, active muscles, and rigid bone structures. By integrating collision and contact handling into the simulation, our algorithm avoids inconsistent poses commonly observed in generative methods such as blendshape rigs. A novel muscle activation model leads to a robust optimization that faithfully reproduces complex facial articulations. We show how person-specific simulation models can be built from a few expression scans with a minimal data acquisition process and an almost entirely automated processing pipeline. Our method supports temporal dynamics due to inertia or external forces, incorporates skin sliding to avoid unnatural stretching, and offers full control of the simulation parameters, which enables a variety of advanced animation effects. For example, slimming or fattening the face is achieved by simply scaling the volume of the soft tissue elements. We show a series of application demos, including artistic editing of the animation model, simulation of corrective facial surgery, or dynamic interaction with external forces and objects.

We present a new algorithm for real-time hand tracking on commodity depth-sensing devices. Our method does not require a user-specific calibration session, but rather learns the geometry as the user performs live in front of the camera, thus enabling seamless virtual interaction at the consumer level. The key novelty in our approach is an online optimization algorithm that jointly estimates pose and shape in each frame, and determines the uncertainty in such estimates. This knowledge allows the algorithm to integrate per-frame estimates over time, and build a personalized geometric model of the captured user. Our approach can easily be integrated in state-of-the-art continuous generative motion tracking software. We provide a detailed evaluation that shows how our approach achieves accurate motion tracking for real-time applications, while significantly simplifying the workflow of accurate hand performance capture. We also provide quantitative evaluation datasets at http://gfx.uvic.ca/datasets/handy

We present a computational method for interactive 3D design and rationalization of surfaces via auxetic materials, i.e., flat flexible material that can stretch uniformly up to a certain extent. A key motivation for studying such material is that one can approximate doubly-curved surfaces (such as the sphere) using only flat pieces, making it attractive for fabrication. We physically realize surfaces by introducing cuts into approximately inextensible material such as sheet metal, plastic, or leather. The cutting pattern is modeled as a regular triangular linkage that yields hexagonal openings of spatially-varying radius when stretched. In the same way that isometry is fundamental to modeling developable surfaces, we leverage conformal geometry to understand auxetic design. In particular, we compute a global conformal map with bounded scale factor to initialize an otherwise intractable non-linear optimization. We demonstrate that this global approach can handle non-trivial topology and non-local dependencies inherent in auxetic material. Design studies and physical prototypes are used to illustrate a wide range of possible applications.

Modern systems for real-time hand tracking rely on a combination of discriminative and generative approaches to robustly recover hand poses. Generative approaches require the specification of a geometric model. In this paper, we propose a the use of sphere-meshes as a novel geometric representation for real-time generative hand tracking. How tightly this model fits a specific user heavily affects tracking precision. We derive an optimization to non-rigidly deform a template model to fit the user data in a number of poses. This optimization jointly captures the user's static and dynamic hand geometry, thus facilitating high-precision registration. At the same time, the limited number of primitives in the tracking template allows us to retain excellent computational performance. We confirm this by embedding our models in an open source real-time registration algorithm to obtain a tracker steadily running at 60Hz. We demonstrate the effectiveness of our solution by qualitatively and quantitatively evaluating tracking precision on a variety of complex motions. We show that the improved tracking accuracy at high frame-rate enables stable tracking of extended and complex motion sequences without the need for per-frame re-initialization. To enable further research in the area of high-precision hand tracking, we publicly release source code and evaluation datasets.

Abstract The goal of example‐based texture synthesis methods is to generate arbitrarily large textures from limited exemplars in order to fit the exact dimensions and resolution required for a specific modeling task. The challenge is to faithfully capture all of the visual characteristics of the exemplar texture, without introducing obvious repetitions or unnatural looking visual elements. While existing non‐parametric synthesis methods have made remarkable progress towards this goal, most such methods have been demonstrated only on relatively low‐resolution exemplars. Real‐world high resolution textures often contain texture details at multiple scales, which these methods have difficulty reproducing faithfully. In this work, we present a new general‐purpose and fully automatic self‐tuning non‐parametric texture synthesis method that extends Texture Optimization by introducing several key improvements that result in superior synthesis ability. Our method is able to self‐tune its various parameters and weights and focuses on addressing three challenging aspects of texture synthesis: (i) irregular large scale structures are faithfully reproduced through the use of automatically generated and weighted guidance channels; (ii) repetition and smoothing of texture patches is avoided by new spatial uniformity constraints; (iii) a smart initialization strategy is used in order to improve the synthesis of regular and near‐regular textures, without affecting textures that do not exhibit regularities. We demonstrate the versatility and robustness of our completely automatic approach on a variety of challenging high‐resolution texture exemplars.

Abstract We present a robust method for capturing articulated hand motions in realtime using a single depth camera. Our system is based on a realtime registration process that accurately reconstructs hand poses by fitting a 3D articulated hand model to depth images. We register the hand model using depth, silhouette, and temporal information. To effectively map low‐quality depth maps to realistic hand poses, we regularize the registration with kinematic and temporal priors, as well as a data‐driven prior built from a database of realistic hand poses. We present a principled way of integrating such priors into our registration optimization to enable robust tracking without severely restricting the freedom of motion. A core technical contribution is a new method for computing tracking correspondences that directly models occlusions typical of single‐camera setups. To ensure reproducibility of our results and facilitate future research, we fully disclose the source code of our implementation.

A shape grammar defines a procedural shape space containing a variety of models of the same class, e.g. buildings, trees, furniture, airplanes, bikes, etc. We present a framework that enables a user to interactively design a probability density function (pdf) over such a shape space and to sample models according to the designed pdf. First, we propose a user interface that enables a user to quickly provide preference scores for selected shapes and suggest sampling strategies to decide which models to present to the user to evaluate. Second, we propose a novel kernel function to encode the similarity between two procedural models. Third, we propose a framework to interpolate user preference scores by combining multiple techniques: function factorization, Gaussian process regression, autorelevance detection, and l 1 regularization. Fourth, we modify the original grammars to generate models with a pdf proportional to the user preference scores. Finally, we provide evaluations of our user interface and framework parameters and a comparison to other exploratory modeling techniques using modeling tasks in five example shape spaces: furniture, low-rise buildings, skyscrapers, airplanes, and vegetation.

We present a complete pipeline for creating fully rigged, personalized 3D facial avatars from hand-held video. Our system faithfully recovers facial expression dynamics of the user by adapting a blendshape template to an image sequence of recorded expressions using an optimization that integrates feature tracking, optical flow, and shape from shading. Fine-scale details such as wrinkles are captured separately in normal maps and ambient occlusion maps. From this user- and expression-specific data, we learn a regressor for on-the-fly detail synthesis during animation to enhance the perceptual realism of the avatars. Our system demonstrates that the use of appropriate reconstruction priors yields compelling face rigs even with a minimalistic acquisition system and limited user assistance. This facilitates a range of new applications in computer animation and consumer-level online communication based on personalized avatars. We present realtime application demos to validate our method.

Abstract Many man‐made objects, in particular building facades, exhibit dominant structural relations such as symmetry and regularity. When editing these shapes, a common objective is to preserve these relations. However, often there are numerous plausible editing results that all preserve the desired structural relations of the input, creating ambiguity. We propose an interactive facade editing framework that explores this structural ambiguity. We first analyze the input in a semi‐automatic manner to detect different groupings of the facade elements and the relations among them. We then provide an incremental editing process where a set of variations that preserve the detected relations in a particular grouping are generated at each step. Starting from one input example, our system can quickly generate various facade configurations.

Abstract Procedural modeling allows for the generation of innumerable variations of models from a parameterized, conditional or stochastic rule set. Due to the abstractness, complexity and stochastic nature of rule sets, it is often very difficult to have an understanding of the diversity of models that a given rule set defines. We address this problem by presenting a novel system to automatically generate, cluster, rank, and select a series of representative thumbnail images out of a rule set. We introduce a set of ‘view attributes’ that can be used to measure the suitability of an image to represent a model, and allow for comparison of different models derived from the same rule set. To find the best thumbnails, we exploit these view attributes on images of models obtained by stochastically sampling the parameter space of the rule set. The resulting thumbnail gallery gives a representative visual impression of the procedural modeling potential of the rule set. Performance is discussed by means of a number of distinct examples and compared to state‐of‐the‐art approaches.

We present a new method for implicit time integration of physical systems. Our approach builds a bridge between nodal Finite Element methods and Position Based Dynamics, leading to a simple, efficient, robust, yet accurate solver that supports many different types of constraints. We propose specially designed energy potentials that can be solved efficiently using an alternating optimization approach. Inspired by continuum mechanics, we derive a set of continuum-based potentials that can be efficiently incorporated within our solver. We demonstrate the generality and robustness of our approach in many different applications ranging from the simulation of solids, cloths, and shells, to example-based simulation. Comparisons to Newton-based and Position Based Dynamics solvers highlight the benefits of our formulation.

Repeated structures are ubiquitous in urban facades. Such repetitions lead to ambiguity in establishing correspondences across sets of unordered images. A decoupled structure-from-motion reconstruction followed by symmetry detection often produces errors: outputs are either noisy and incomplete, or even worse, appear to be valid but actually have a wrong number of repeated elements. We present an optimization framework for extracting repeated elements in images of urban facades, while simultaneously calibrating the input images and recovering the 3D scene geometry using a graph-based global analysis. We evaluate the robustness of the proposed scheme on a range of challenging examples containing widespread repetitions and nondistinctive features. These image sets are common but cannot be handled well with state-of-the-art methods. We show that the recovered symmetry information along with the 3D geometry enables a range of novel image editing operations that maintain consistency across the images.

We present a computational approach for designing wire meshes , i.e., freeform surfaces composed of woven wires arranged in a regular grid. To facilitate shape exploration, we map material properties of wire meshes to the geometric model of Chebyshev nets . This abstraction is exploited to build an efficient optimization scheme. While the theory of Chebyshev nets suggests a highly constrained design space, we show that allowing controlled deviations from the underlying surface provides a rich shape space for design exploration. Our algorithm balances globally coupled material constraints with aesthetic and geometric design objectives that can be specified by the user in an interactive design session. In addition to sculptural art, wire meshes represent an innovative medium for industrial applications including composite materials and architectural façades. We demonstrate the effectiveness of our approach using a variety of digital and physical prototypes with a level of shape complexity unobtainable using previous methods.

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 present a new algorithm for computational caustic design. Our algorithm solves for the shape of a transparent object such that the refracted light paints a desired caustic image on a receiver screen. We introduce an optimal transport formulation to establish a correspondence between the input geometry and the unknown target shape. A subsequent 3D optimization based on an adaptive discretization scheme then finds the target surface from the correspondence map. Our approach supports piecewise smooth surfaces and non-bijective mappings, which eliminates a number of shortcomings of previous methods. This leads to a significantly richer space of caustic images, including smooth transitions, singularities of infinite light density, and completely black areas. We demonstrate the effectiveness of our approach with several simulated and fabricated examples.

This paper discusses how realtime face tracking and performance-based animation can facilitate new ways of interaction for computer gaming and other online applications. We identify a number of requirements for realtime face capture and animation systems, and show how recent progress in tracking algorithms advances towards satisfying these requirements. Performance-based animation has the potential to significantly enrich the emotional experience of in-game communication through live avatars that are controlled directly by the facial expressions of a recorded user. We briefly outline other potential use scenarios of realtime face tracking systems and conclude with a discussion of future research challenges.

Abstract Rigid registration of two geometric data sets is essential in many applications, including robot navigation, surface reconstruction, and shape matching. Most commonly, variants of the Iterative Closest Point (ICP) algorithm are employed for this task. These methods alternate between closest point computations to establish correspondences between two data sets, and solving for the optimal transformation that brings these correspondences into alignment. A major difficulty for this approach is the sensitivity to outliers and missing data often observed in 3D scans. Most practical implementations of the ICP algorithm address this issue with a number of heuristics to prune or reweight correspondences. However, these heuristics can be unreliable and difficult to tune, which often requires substantial manual assistance. We propose a new formulation of the ICP algorithm that avoids these difficulties by formulating the registration optimization using sparsity inducing norms. Our new algorithm retains the simple structure of the ICP algorithm, while achieving superior registration results when dealing with outliers and incomplete data. The complete source code of our implementation is provided at http://lgg.epfl.ch/sparseicp .

Abstract Mesh editing under constraints is a challenging task with numerous applications in geometric modeling, industrial design, and architectural form finding. Recent methods support constraint‐based exploration of meshes with fixed connectivity, but commonly lack local control. Because constraints are often globally coupled, a local modification by the user can have global effects on the surface, making iterative design exploration and refinement difficult. Simply fixing a local region of interest a priori is problematic, as it is not clear in advance which parts of the mesh need to be modified to obtain an aesthetically pleasing solution that satisfies all constraints. We propose a novel framework for exploring local modifications of constrained meshes. Our solution consists of three steps. First, a user specifies target positions for one or more vertices. Our algorithm computes a sparse set of displacement vectors that satisfies the constraints and yields a smooth deformation. Then we build a linear subspace to allow realtime exploration of local variations that satisfy the constraints approximately. Finally, after interactive exploration, the result is optimized to fully satisfy the set of constraints. We evaluate our framework on meshes where each face is constrained to be planar.

Abstract The concept of symmetry has received significant attention in computer graphics and computer vision research in recent years. Numerous methods have been proposed to find, extract, encode and exploit geometric symmetries and high‐level structural information for a wide variety of geometry processing tasks. This report surveys and classifies recent developments in symmetry detection. We focus on elucidating the key similarities and differences between existing methods to gain a better understanding of a fundamental problem in digital geometry processing and shape understanding in general. We discuss a variety of applications in computer graphics and geometry processing that benefit from symmetry information for more effective processing. An analysis of the strengths and limitations of existing algorithms highlights the plenitude of opportunities for future research both in terms of theory and applications.

Abstract We propose a computational design approach to generate 3D models composed of interlocking planar pieces. We show how intricate 3D forms can be created by sliding the pieces into each other along straight slits, leading to a simple construction that does not require glue, screws, or other means of support. To facilitate the design process, we present an abstraction model that formalizes the main geometric constraints imposed by fabrication and assembly, and incorporates conditions on the rigidity of the resulting structure. We show that the tight coupling of constraints makes manual design highly nontrivial and introduce an optimization method to automate constraint satisfaction based on an analysis of the constraint relation graph. This algorithm ensures that the planar parts can be fabricated and assembled. We demonstrate the versatility of our approach by creating 3D toy models, an architectural design study, and several examples of functional furniture.

We present a new algorithm for realtime face tracking on commodity RGB-D sensing devices. Our method requires no user-specific training or calibration, or any other form of manual assistance, thus enabling a range of new applications in performance-based facial animation and virtual interaction at the consumer level. The key novelty of our approach is an optimization algorithm that jointly solves for a detailed 3D expression model of the user and the corresponding dynamic tracking parameters. Realtime performance and robust computations are facilitated by a novel subspace parameterization of the dynamic facial expression space. We provide a detailed evaluation that shows that our approach significantly simplifies the performance capture workflow, while achieving accurate facial tracking for realtime applications.

Mechanical figures that mimic human motions continue to entertain us and capture our imagination. Creating such automata requires expertise in motion planning, knowledge of mechanism design, and familiarity with fabrication constraints. Thus, automaton design remains restricted to only a handful of experts. We propose an automatic algorithm that takes a motion sequence of a humanoid character and generates the design for a mechanical figure that approximates the input motion when driven with a single input crank. Our approach has two stages. The motion approximation stage computes a motion that approximates the input sequence as closely as possible while remaining compatible with the geometric and motion constraints of the mechanical parts in our design. Then, in the layout stage, we solve for the sizing parameters and spatial layout of all the elements, while respecting all fabrication and assembly constraints. We apply our algorithm on a range of input motions taken from motion capture databases. We also fabricate two of our designs to demonstrate the viability of our approach.

Reconstructing realistic 3D hair geometry is challenging due to omnipresent occlusions, complex discontinuities and specular appearance. To address these challenges, we propose a multi-view hair reconstruction algorithm based on orientation fields with structure-aware aggregation. Our key insight is that while hair's color appearance is view-dependent, the response to oriented filters that captures the local hair orientation is more stable. We apply the structure-aware aggregation to the MRF matching energy to enforce the structural continuities implied from the local hair orientations. Multiple depth maps from the MRF optimization are then fused into a globally consistent hair geometry with a template refinement procedure. Compared to the state-of-the-art color-based methods, our method faithfully reconstructs detailed hair structures. We demonstrate the results for a number of hair styles, ranging from straight to curly, and show that our framework is suitable for capturing hair in motion.

Abstract We introduce a unified optimization framework for geometry processing based on shape constraints. These constraints preserve or prescribe the shape of subsets of the points of a geometric data set, such as polygons, one‐ring cells, volume elements, or feature curves. Our method is based on two key concepts: a shape proximity function and shape projection operators. The proximity function encodes the distance of a desired least‐squares fitted elementary target shape to the corresponding vertices of the 3D model. Projection operators are employed to minimize the proximity function by relocating vertices in a minimal way to match the imposed shape constraints. We demonstrate that this approach leads to a simple, robust, and efficient algorithm that allows implementing a variety of geometry processing applications, simply by combining suitable projection operators. We show examples for computing planar and circular meshes, shape space exploration, mesh quality improvement, shape‐preserving deformation, and conformal parametrization. Our optimization framework provides a systematic way of building new solvers for geometry processing and produces similar or better results than state‐of‐the‐art methods.

Abstract We introduce a novel framework for image‐based 3D reconstruction of urban buildings based on symmetry priors. Starting from image‐level edges, we generate a sparse and approximate set of consistent 3D lines. These lines are then used to simultaneously detect symmetric line arrangements while refining the estimated 3D model. Operating both on 2D image data and intermediate 3D feature representations, we perform iterative feature consolidation and effective outlier pruning, thus eliminating reconstruction artifacts arising from ambiguous or wrong stereo matches. We exploit non‐local coherence of symmetric elements to generate precise model reconstructions, even in the presence of a significant amount of outlier image‐edges arising from reflections, shadows, outlier objects, etc. We evaluate our algorithm on several challenging test scenarios, both synthetic and real. Beyond reconstruction, the extracted symmetry patterns are useful towards interactive and intuitive model manipulations.

We present a novel shape completion technique for creating temporally coherent watertight surfaces from real-time captured dynamic performances. Because of occlusions and low surface albedo, scanned mesh sequences typically exhibit large holes that persist over extended periods of time. Most conventional dynamic shape reconstruction techniques rely on template models or assume slow deformations in the input data. Our framework sidesteps these requirements and directly initializes shape completion with topology derived from the visual hull. To seal the holes with patches that are consistent with the subject's motion, we first minimize surface bending energies in each frame to ensure smooth transitions across hole boundaries. Temporally coherent dynamics of surface patches are obtained by unwarping all frames within a time window using accurate interframe correspondences. Aggregated surface samples are then filtered with a temporal visibility kernel that maximizes the use of nonoccluded surfaces. A key benefit of our shape completion strategy is that it does not rely on long-range correspondences or a template model. Consequently, our method does not suffer error accumulation typically introduced by noise, large deformations, and drastic topological changes. We illustrate the effectiveness of our method on several high-resolution scans of human performances captured with a state-of-the-art multiview 3D acquisition system.

Many tasks in graphical user interfaces require users to interact with elements at various levels of precision. We present FingerGlass, a bimanual technique designed to improve the precision of graphical tasks on multitouch screens. It enables users to quickly navigate to different locations and across multiple scales of a scene using a single hand. The other hand can simultaneously interact with objects in the scene. Unlike traditional pan-zoom interfaces, FingerGlass retains contextual information during the interaction. We evaluated our technique in the context of precise object selection and translation and found that FingerGlass significantly outperforms three state-of-the-art baseline techniques in both objective and subjective measurements: users acquired and translated targets more than 50% faster than with the second-best technique in our experiment.

This paper presents a system for performance-based character animation that enables any user to control the facial expressions of a digital avatar in realtime. The user is recorded in a natural environment using a non-intrusive, commercially available 3D sensor. The simplicity of this acquisition device comes at the cost of high noise levels in the acquired data. To effectively map low-quality 2D images and 3D depth maps to realistic facial expressions, we introduce a novel face tracking algorithm that combines geometry and texture registration with pre-recorded animation priors in a single optimization. Formulated as a maximum a posteriori estimation in a reduced parameter space, our method implicitly exploits temporal coherence to stabilize the tracking. We demonstrate that compelling 3D facial dynamics can be reconstructed in realtime without the use of face markers, intrusive lighting, or complex scanning hardware. This makes our system easy to deploy and facilitates a range of new applications, e.g. in digital gameplay or social interactions.

The emergence of large-scale freeform shapes in architecture poses big challenges to the fabrication of such structures. A key problem is the approximation of the design surface by a union of patches, so-called panels, that can be manufactured with a selected technology at reasonable cost, while meeting the design intent and achieving the desired aesthetic quality of panel layout and surface smoothness. The production of curved panels is mostly based on molds. Since the cost of mold fabrication often dominates the panel cost, there is strong incentive to use the same mold for multiple panels. We cast the major practical requirements for architectural surface paneling, including mold reuse, into a global optimization framework that interleaves discrete and continuous optimization steps to minimize production cost while meeting user-specified quality constraints. The search space for optimization is mainly generated through controlled deviation from the design surface and tolerances on positional and normal continuity between neighboring panels. A novel 6-dimensional metric space allows us to quickly compute approximate inter-panel distances, which dramatically improves the performance of the optimization and enables the handling of complex arrangements with thousands of panels. The practical relevance of our system is demonstrated by paneling solutions for real, cutting-edge architectural freeform design projects.

We introduce a method for generating facial blendshape rigs from a set of example poses of a CG character. Our system transfers controller semantics and expression dynamics from a generic template to the target blendshape model, while solving for an optimal reproduction of the training poses. This enables a scalable design process, where the user can iteratively add more training poses to refine the blendshape expression space. However, plausible animations can be obtained even with a single training pose. We show how formulating the optimization in gradient space yields superior results as compared to a direct optimization on blendshape vertices. We provide examples for both hand-crafted characters and 3D scans of a real actor and demonstrate the performance of our system in the context of markerless art-directable facial tracking.

This paper addresses the fundamental problem of computing stable medial representations of 3D shapes. We propose a spatially adaptive classification of geometric features that yields a robust algorithm for generating medial representations at different levels of abstraction. The recently introduced continuous scale axis transform serves as the mathematical foundation of our algorithm. We show how geometric and topological properties of the continuous setting carry over to discrete shape representations. Our method combines scaling operations of medial balls for geometric simplification with filtrations of the medial axis and provably good conversion steps to and from union of balls, to enable efficient processing of a wide variety shape representations including polygon meshes, 3D images, implicit surfaces, and point clouds. We demonstrate the robustness and versatility of our algorithm with an extensive validation on hundreds of shapes including complex geometries consisting of millions of triangles.

We demonstrate how the scale axis transform can be used to compute a parameterized family of shape skeletons. The skeletons gradually represent only the most important features of a shape, in a scale-adaptive manner. Here a shape O is any bounded open subset of the plane R2. The scale axis for scale value $s$ is the medial axis of the multiplicatively grown shape O_s, where Os is the union of medial balls of O with radii scaled by the factor s.

We introduce the scale axis transform, a new skeletal shape representation for bounded open sets O ⊂ Rd. The scale axis transform induces a family of skeletons that captures the important features of a shape in a scale-adaptive way and yields a hierarchy of successively simplified skeletons. Its definition is based on the medial axis transform and the simplification of the shape under multiplicative scaling: the s-scaled shape Os is the union of the medial balls of O with radii scaled by a factor of s. The s-scale axis transform of O is the medial axis transform of Os, with radii scaled back by a factor of 1/s. We prove topological properties of the scale axis transform and we describe the evolution s → Os by defining the multiplicative distance function to the shape and studying properties of the corresponding steepest ascent flow. All our theoretical results hold for any dimension. In addition, using a discrete approximation, we present several examples of two-dimensional scale axis transforms that illustrate the practical relevance of our new framework.

Abstract We present a geometry processing framework that allows direct manipulation or preservation of positional, metric, and curvature constraints anywhere on the surface of a geometric model. Target values for these properties can be specified point‐wise or as integrated quantities over curves and surface patches embedded in the shape. For example, the user can draw several curves on the surface and specify desired target lengths, manipulate the normal curvature along these curves, or modify the area or principal curvature distribution of arbitrary surface patches. This user input is converted into a set of non‐linear constraints. A global optimization finds the new deformed surface that best satisfies the constraints, while minimizing adaptable measures for metric and curvature distortion that provide explicit control of the deformation semantics. We illustrate how this approach enables flexible surface processing and shape editing operations not available in current systems.

We present a framework and algorithms for robust geometry and motion reconstruction of complex deforming shapes. Our method makes use of a smooth template that provides a crude approximation of the scanned object and serves as a geometric and topological prior for reconstruction. Large-scale motion of the acquired object is recovered using a novel space-time adaptive, non-rigid registration method. Fine-scale details such as wrinkles and folds are synthesized with an efficient linear mesh deformation algorithm. Subsequent spatial and temporal filtering of detail coefficients allows transfer of persistent geometric detail to regions not observed by the scanner. We show how this two-scale process allows faithful recovery of small-scale shape and motion features leading to a high-quality reconstruction. We illustrate the robustness and generality of our algorithm on a variety of examples composed of different materials and exhibiting a large range of dynamic deformations.

"To them, I said, the truth would be literally nothing but the shadows of the images." - Plato, The Republic Shadow art is a unique form of sculptural art where the 2D shadows cast by a 3D sculpture are essential for the artistic effect. We introduce computational tools for the creation of shadow art and propose a design process where the user can directly specify the desired shadows by providing a set of binary images and corresponding projection information. Since multiple shadow images often contradict each other, we present a geometric optimization that computes a 3D shadow volume whose shadows best approximate the provided input images. Our analysis shows that this optimization is essential for obtaining physically realizable 3D sculptures. The resulting shadow volume can then be modified with a set of interactive editing tools that automatically respect the often intricate shadow constraints. We demonstrate the potential of our system with a number of complex 3D shadow art sculptures that go beyond what is seen in contemporary art pieces.

Abstract We propose a framework for 3D geometry processing that provides direct access to surface curvature to facilitate advanced shape editing, filtering, and synthesis algorithms. The central idea is to map a given surface to the curvature domain by evaluating its principle curvatures, apply filtering and editing operations to the curvature distribution, and reconstruct the resulting surface using an optimization approach. Our system allows the user to prescribe arbitrary principle curvature values anywhere on the surface. The optimization solves a nonlinear least‐squares problem to find the surface that best matches the desired target curvatures while preserving important properties of the original shape. We demonstrate the effectiveness of this processing metaphor with several applications, including anisotropic smoothing, feature enhancement, and multi‐scale curvature editing.

Abstract We present a registration algorithm for pairs of deforming and partial range scans that addresses the challenges of non‐rigid registration within a single non‐linear optimization. Our algorithm simultaneously solves for correspondences between points on source and target scans, confidence weights that measure the reliability of each correspondence and identify non‐overlapping areas, and a warping field that brings the source scan into alignment with the target geometry. The optimization maximizes the region of overlap and the spatial coherence of the deformation while minimizing registration error. All optimization parameters are chosen automatically; hand‐tuning is not necessary. Our method is not restricted to part‐in‐whole matching, but addresses the general problem of partial matching, and requires no explicit prior correspondences or feature points. We evaluate the performance and robustness of our method using scan data acquired by a structured light scanner and compare our method with existing non‐rigid registration algorithms.

Tourist maps are essential resources for visitors to an unfamiliar city because they visually highlight landmarks and other points of interest. Yet, hand-designed maps are static representations that cannot adapt to the needs and tastes of the individual tourist. In this paper we present an automated system for designing tourist maps that selects and highlights the information that is most important to tourists. Our system determines the salience of map elements using bottom-up vision-based image analysis and top-down web-based information extraction techniques. It then generates a map that emphasizes the most important elements, using a combination of multiperspective rendering to increase visibility of streets and landmarks, and cartographic generalization techniques such as simplification, deformation, and displacement to emphasize landmarks and de-emphasize less important buildings. We show a number of automatically generated tourist maps of San Francisco and compare them to existing automated and manual approaches.

We introduce a computational framework for discovering regular or repeated geometric structures in 3D shapes. We describe and classify possible regular structures and present an effective algorithm for detecting such repeated geometric patterns in point- or meshbased models. Our method assumes no prior knowledge of the geometry or spatial location of the individual elements that define the pattern. Structure discovery is made possible by a careful analysis of pairwise similarity transformations that reveals prominent lattice structures in a suitable model of transformation space. We introduce an optimization method for detecting such uniform grids specifically designed to deal with outliers and missing elements. This yields a robust algorithm that successfully discovers complex regular structures amidst clutter, noise, and missing geometry. The accuracy of the extracted generating transformations is further improved using a novel simultaneous registration method in the spatial domain. We demonstrate the effectiveness of our algorithm on a variety of examples and show applications to compression, model repair, and geometry synthesis.

We illustrate a simple algorithm for approximating the medial axis of a 2D shape with smooth boundary from a sample of this boundary. The algorithm is compared to a more general approximation method that builds on the same idea, namely, to approximate the shape by a union of balls. While not as general, our algorithm is simpler, faster and numerically more stable. Both algorithms are visualized using the Mesecina tool, which is also described.

Abstract We propose a new adaptive space deformation method for interactive shape modeling. A novel energy formulation based on elastically coupled volumetric cells yields intuitive detail preservation even under large deformations. By enforcing rigidity of the cells, we obtain an extremely robust numerical solver for the resulting nonlinear optimization problem. Scalability is achieved using an adaptive spatial discretization that is decoupled from the resolution of the embedded object. Our approach is versatile and easy to implement, supports thin‐shell and solid deformations of 2D and 3D objects, and is applicable to arbitrary sample‐based representations, such as meshes, triangle soups, or point clouds.

We present novel adaptive sampling algorithms for particle-based fluid simulation. We introduce a sampling condition based on geometric local feature size that allows focusing computational resources in geometrically complex regions, while reducing the number of particles deep inside the fluid or near thick flat surfaces. Further performance gains are achieved by varying the sampling density according to visual importance. In addition, we propose a novel fluid surface definition based on approximate particle-to-surface distances that are carried along with the particles and updated appropriately. The resulting surface reconstruction method has several advantages over existing methods, including stability under particle resampling and suitability for representing smooth flat surfaces. We demonstrate how our adaptive sampling and distance-based surface reconstruction algorithms lead to significant improvements in time and memory as compared to single resolution particle simulations, without significantly affecting the fluid flow behavior.

We present a symmetrization algorithm for geometric objects. Our algorithm enhances approximate symmetries of a model while minimally altering its shape. Symmetrizing deformations are formulated as an optimization process that couples the spatial domain with a transformation configuration space, where symmetries can be expressed more naturally and compactly as parametrized point-pair mappings. We derive closed-form solution for the optimal symmetry transformations, given a set of corresponding sample pairs. The resulting optimal displacement vectors are used to drive a constrained deformation model that pulls the shape towards symmetry. We show how our algorithm successfully symmetrizes both the geometry and the discretization of complex 2D and 3D shapes and discuss various applications of such symmetrizing deformations.

We present an algorithm that generates natural and intuitive deformations via direct manipulation for a wide range of shape representations and editing scenarios. Our method builds a space deformation represented by a collection of affine transformations organized in a graph structure. One transformation is associated with each graph node and applies a deformation to the nearby space. Positional constraints are specified on the points of an embedded object. As the user manipulates the constraints, a nonlinear minimization problem is solved to find optimal values for the affine transformations. Feature preservation is encoded directly in the objective function by measuring the deviation of each transformation from a true rotation. This algorithm addresses the problem of "embedded deformation" since it deforms space through direct manipulation of objects embedded within it, while preserving the embedded objects' features. We demonstrate our method by editing meshes, polygon soups, mesh animations, and animated particle systems.

"Symmetry is a complexity-reducing concept [...]; seek it every-where." - Alan J. PerlisMany natural and man-made objects exhibit significant symmetries or contain repeated substructures. This paper presents a new algorithm that processes geometric models and efficiently discovers and extracts a compact representation of their Euclidean symmetries. These symmetries can be partial, approximate, or both. The method is based on matching simple local shape signatures in pairs and using these matches to accumulate evidence for symmetries in an appropriate transformation space. A clustering stage extracts potential significant symmetries of the object, followed by a verification step. Based on a statistical sampling analysis, we provide theoretical guarantees on the success rate of our algorithm. The extracted symmetry graph representation captures important high-level information about the structure of a geometric model which in turn enables a large set of further processing operations, including shape compression, segmentation, consistent editing, symmetrization, indexing for retrieval, etc.

In this article we present a new multiscale surface representation based on point samples. Given an unstructured point cloud as input, our method first computes a series of point-based surface approximations at successively higher levels of smoothness, that is, coarser scales of detail, using geometric low-pass filtering. These point clouds are then encoded relative to each other by expressing each level as a scalar displacement of its predecessor. Low-pass filtering and encoding are combined in an efficient multilevel projection operator using local weighted least squares fitting.Our representation is motivated by the need for higher-level editing semantics which allow surface modifications at different scales. The user would be able to edit the surface at different approximation levels to perform coarse-scale edits on the whole model as well as very localized modifications on the surface detail. Additionally, the multiscale representation provides a separation in geometric scale which can be understood as a spectral decomposition of the surface geometry. Based on this observation, advanced geometric filtering methods can be implemented that mimic the effects of Fourier filters to achieve effects such as smoothing, enhancement, or band-bass filtering.

We present efficient data structures and caching schemes to accelerate ray-surface intersections for deforming point-sampled surfaces.By exploiting spatial and temporal coherence of the deformation during the animation, we are able to improve rendering performance by a factor of two to three compared to existing techniques.Starting from a tight bounding sphere hierarchy for the undeformed object, we use a lazy updating scheme to adapt the hierarchy to the deformed surface in each animation step.In addition, we achieve a significant speedup for ray-surface intersections by caching per-ray intersection points.We also present a technique for rendering sharp edges and corners in point-sampled models by introducing a novel surface clipping algorithm.

We present a new meshless animation framework for elastic and plastic materials that fracture. Central to our method is a highly dynamic surface and volume sampling method that supports arbitrary crack initiation, propagation, and termination, while avoiding many of the stability problems of traditional mesh-based techniques. We explicitly model advancing crack fronts and associated fracture surfaces embedded in the simulation volume. When cutting through the material, crack fronts directly affect the coupling between simulation nodes, requiring a dynamic adaptation of the nodal shape functions. We show how local visibility tests and dynamic caching lead to an efficient implementation of these effects based on point collocation. Complex fracture patterns of interacting and branching cracks are handled using a small set of topological operations for splitting, merging, and terminating crack fronts. This allows continuous propagation of cracks with highly detailed fracture surfaces, independent of the spatial resolution of the simulation nodes, and provides effective mechanisms for controlling fracture paths. We demonstrate our method for a wide range of materials, from stiff elastic to highly plastic objects that exhibit brittle and/or ductile fracture.

We present a new scheme for digital watermarking of point-sampled geometry based on spectral analysis. By extending existing algorithms designed for polygonal data to unstructured point clouds, our method is particularly suited for scanned models, where the watermark can be directly embedded in the raw data obtained from the 3D acquisition device. To handle large data sets efficiently, we apply a fast hierarchical clustering algorithm that partitions the model into a set of patches. Each patch is mapped into the space of eigenfunctions of an approximate Laplacian operator to obtain a decomposition of the patch surface into discrete frequency bands. The watermark is then embedded into the low frequency components to minimize visual artifacts in the model geometry. During extraction, the target model is resampled at optimal resolution using an MLS projection. After extracting a watermark from this model, the corresponding bit stream is analyzed using statistical methods based on correlation. We have applied our method to a number of point-sampled models of different geometric and topological complexity. These experiments show that our watermarking scheme is robust against numerous attacks, including low-pass filtering, resampling, affine transformations, cropping, additive random noise, and combinations of the above.

Abstract We present a new technique for extracting line‐type features on point‐sampled geometry. Given an unstructuredpoint cloud as input, our method first applies principal component analysis on local neighborhoods toclassify points according to the likelihood that they belong to a feature. Using hysteresis thresholding, we thencompute a minimum spanning graph as an initial approximation of the feature lines. To smooth out the featureswhile maintaining a close connection to the underlying surface, we use an adaptation of active contour models.Central to our method is a multi‐scale classification operator that allows feature analysis at multiplescales, using the size of the local neighborhoods as a discrete scale parameter. This significantly improves thereliability of the detection phase and makes our method more robust in the presence of noise. To illustrate theusefulness of our method, we have implemented a non‐photorealistic point renderer to visualize point‐sampledsurfaces as line drawings of their extracted feature curves.

We present a versatile and complete free-form shape modeling framework for point-sampled geometry. By combining unstructured point clouds with the implicit surface definition of the moving least squares approximation, we obtain a hybrid geometry representation that allows us to exploit the advantages of implicit and parametric surface models. Based on this representation we introduce a shape modeling system that enables the designer to perform large constrained deformations as well as boolean operations on arbitrarily shaped objects. Due to minimum consistency requirements, point-sampled surfaces can easily be re-structured on the fly to support extreme geometric deformations during interactive editing. In addition, we show that strict topology control is possible and sharp features can be generated and preserved on point-sampled objects. We demonstrate the effectiveness of our system on a large set of input models, including noisy range scans, irregular point clouds, and sparsely as well as densely sampled models.

We introduce, analyze and quantitatively compare a number of surface simplification methods for point-sampled geometry. We have implemented incremental and hierarchical clustering, iterative simplification, and particle simulation algorithms to create approximations of point-based models with lower sampling density. All these methods work directly on the point cloud, requiring no intermediate tesselation. We show how local variation estimation and quadric error metrics can be employed to diminish the approximation error and concentrate more samples in regions of high curvature. To compare the quality of the simplified surfaces, we have designed a new method for computing numerical and visual error estimates for point-sampled surfaces. Our algorithms are fast, easy to implement, and create high-quality surface approximations, clearly demonstrating the effectiveness of point-based surface simplification.

We present a system for interactive shape and appearance editing of 3D point-sampled geometry. By generalizing conventional 2D pixel editors, our system supports a great variety of different interaction techniques to alter shape and appearance of 3D point models, including cleaning, texturing, sculpting, carving, filtering, and resampling. One key ingredient of our framework is a novel concept for interactive point cloud parameterization allowing for distortion minimal and aliasing-free texture mapping. A second one is a dynamic, adaptive resampling method which builds upon a continuous reconstruction of the model surface and its attributes. These techniques allow us to transfer the full functionality of 2D image editing operations to the irregular 3D point setting. Our system reads, processes, and writes point-sampled models without intermediate tesselation. It is intended to complement existing low cost 3D scanners and point rendering pipelines for efficient 3D content creation.

We present a new framework for processing point-sampled objects using spectral methods. By establishing a concept of local frequencies on geometry, we introduce a versatile spectral representation that provides a rich repository of signal processing algorithms. Based on an adaptive tesselation of the model surface into regularly resampled displacement fields, our method computes a set of windowed Fourier transforms creating a spectral decomposition of the model. Direct analysis and manipulation of the spectral coefficients supports effective filtering, resampling, power spectrum analysis and local error control. Our algorithms operate directly on points and normals, requiring no vertex connectivity information. They are computationally efficient, robust and amenable to hardware acceleration. We demonstrate the performance of our framework on a selection of example applications including noise removal, enhancement, restoration and subsampling.