We introduce RibbonSculpt, the first method for interactive freeform shape design in VR through progressive sketching of sparse, oriented ribbons. Instead of reconstructing a surface from a fully drawn VR sketch, our method allows the real-time creation and progressive refinement of a closed surface of any topological genus, thanks to the continuous update of a volumetric proxy. The latter corresponds to a filtered subset of the Voronoi balls defined by the user-sketched ribbons. At each visualization step, a mesh extracted from the proxy is beautified through Laplacian-based energy minimization, yielding a smooth surface that interpolates the ribbons. Guided by this surface, users can easily refine their design by adding or removing ribbons, which sculpts, in return, the set of Voronoi balls forming the proxy. Our results, supported by user studies, show that RibbonSculpt allows VR users to easily and quickly draft the 3D shapes they have in mind.

Abstract Although intuitive, sketching a closed 3D shape directly in an immersive environment results in an unordered set of arbitrary strokes, which can be difficult to assemble into a closed surface. We tackle this challenge by introducing VRSurf, a surfacing method inspired by a balloon inflation metaphor: Seeded in the sparse scaffold formed by the strokes, a smooth, closed surface is inflated to progressively interpolate the input strokes, sampled into lists of points. These are treated in a divide‐and‐conquer manner, which allows for automatically triggering some additional balloon inflation followed byfusion ifthe current inflation stops due to a detected concavity. While the input strokes are intended to belong to the same smooth 3D shape, our method is robust to coarse VR input and does not require strokes to be aligned. We simply avoid intersecting strokes that might give an inconsistent surface position due to the roughness of the VR drawing. Moreover, no additional topological information is required, and all the user needs to do is specify the initial seeding location for the first balloon. The results show that VRsurf can efficiently generate smooth surfaces that interpolate sparse sets of unoriented strokes. Validation includes a side‐by‐side comparison with other reconstruction methods on the same input VR sketch. We also check that our solution matches the user's intent by applying it to strokes that were sketched on an existing 3D shape and comparing what we get to the original one.

Abstract This paper is devoted to a category of metamaterials called auxetics, identified by their negative Poisson's ratio. Our work consists in exploring geometrical strategies to generate irregular auxetic structures. More precisely we seek to reduce the Poisson's ratio ν, by pruning an irregular network based solely on geometric criteria. We introduce a strategy combining a pure geometric pruning algorithm followed by a physics‐based testing phase to determine the resulting Poisson's ratio of our structures. We propose an algorithm that generates sets of irregular auxetic networks. Our contributions include geometrical characterization of auxetic networks, development of a pruning strategy, generation of auxetic networks with low Poisson's ratio, as well as validation of our approach. We provide statistical validation of our approach on large sets of irregular networks, and we additionally laser‐cut auxetic networks in sheets of rubber. The findings reported here show that it is possible to reduce the Poisson's ratio by geometric pruning, and that we can generate irregular auxetic networks at lower processing times than a physics‐based approach.

Abstract Fashion design often starts with hand‐drawn, expressive sketches that communicate the essence of a garment over idealized human bodies. We propose an approach to automatically dress virtual characters from such input, previously complemented with user‐annotations. In contrast to prior work requiring users to draw garments with accurate proportions over each virtual character to be dressed, our method follows a style transfer strategy : the information extracted from a single, annotated fashion sketch can be used to inform the synthesis of one to many new garment(s) with similar style, yet different proportions. In particular, we define the style of a loose garment from its silhouette and folds, which we extract from the drawing. Key to our method is our strategy to extract both shape and repetitive patterns of folds from the 2D input. As our results show, each input sketch can be used to dress a variety of characters of different morphologies, from virtual humans to cartoon‐style characters.

Abstract Contour trees are extensively used in scalar field analysis. The contour tree is a data structure that tracks the evolution of level set topology in a scalar field. Scalar fields are typically available as samples at vertices of a mesh and are linearly interpolated within each cell of the mesh. A more suitable way of representing scalar fields, especially when a smoother function needs to be modeled, is via higher order interpolants. We propose an algorithm to compute the contour tree for such functions. The algorithm computes a local structure by connecting critical points using a numerically stable monotone path tracing procedure. Such structures are computed for each cell and are stitched together to obtain the contour tree of the function. The algorithm is scalable to higher degree interpolants whereas previous methods were restricted to quadratic or linear interpolants. The algorithm is intrinsically parallelizable and has potential applications to isosurface extraction.

We propose an efficient method to model paper tearing in the context of interactive modeling. The method uses geometrical information to automatically detect potential starting points of tears. We further introduce a new hybrid geometrical and physical-based method to compute the trajectory of tears while procedurally synthesizing high resolution details of the tearing path using a texture based approach. The results obtained are compared with real paper and with previous studies on the expected geometric paths of paper that tears.

This paper presents a multilevel analysis of 2D shapes and uses it to find similarities between the different parts of a shape. Such an analysis is important for many applications such as shape comparison, editing, and compression. Our robust and stable method decomposes a shape into parts, determines a parts hierarchy, and measures similarity between parts based on a salience measure on the medial axis, the Weighted Extended Distance Function, providing a multi-resolution partition of the shape that is stable across scale and articulation. Comparison with an extensive user study on the MPEG-7 database demonstrates that our geometric results are consistent with user perception.

In this paper we present the 2D Shape Structure database, a public, user-generated dataset of 2D shape decompositions into a hierarchy of shape parts with geometric relationships retained. It is the outcome of a large-scale user study obtained by crowdsourcing, involving over 1200 shapes in 70 shape classes, and 2861 participants. A total of 41,953 annotations has been collected with at least 24 annotations per shape. For each shape, user decompositions into main shape, one or more levels of parts, and a level of details are available. This database reinforces a philosophy that understanding shape structure as a whole, rather than in the separated categories of parts decomposition, parts hierarchy, and analysis of relationships between parts, is crucial for full shape understanding. We provide initial statistical explorations of the data to determine representative (“mean”) shape annotations and to determine the number of modes in the annotations. The primary goal of the paper is to make this rich and complex database openly available (through the website http://2dshapesstructure.github.io/index.html), providing the shape community with a ground truth of human perception of holistic shape structure.

Abstract A popular mode of shape synthesis involves mixing and matching parts from different objects to form a coherent whole. The key challenge is to efficiently synthesize shape variations that are plausible, both locally and globally. A major obstacle is to assemble the objects with local consistency, i.e., all the connections between parts are valid with no dangling open connections. The combinatorial complexity of this problem limits existing methods in geometric and/or topological variations of the synthesized models. In this work, we introducereplaceable substructuresas arrangements of parts that can be interchanged while ensuring boundary consistency. The consistency information is extracted from part labels and connections in the original source models. We present a polynomial time algorithm that discovers such substructures by working on a dual of the original shape graph that encodes inter‐part connectivity. We demonstrate the algorithm on a range of test examples producing plausible shape variations, both from a geometric and from a topological viewpoint.

We present the first sketch-based modeling method for developable surfaces with pre-designed folds, such as garments or leather products. The main challenge we address for building folded surfaces from sketches is that silhouette strokes on the sketch correspond to discontinuous sets of non-planar curves on the 3D model. We introduce a new zippering algorithm for progressively identifying silhouette edges on the model and tying them to silhouette strokes. Our solution ensures that the strokes are fully covered and optimally sampled by the model. This new method, interleaved with developability optimization steps, is implemented in a multiview sketching system where the user can sketch the contours of internal folds in addition to the usual silhouettes, borders, and seam lines. All strokes are interpreted as hard constraints, while developability is only optimized. The developability error map we provide then enables users to add local seams or darts where needed and progressively improve their design. This makes our method robust, even to coarse input for which no fully developable solution exists.

We present the first method to animate sheets of paper at interactive rates, while automatically generating a plausible set of sharp features when the sheet is crumpled. The key idea is to interleave standard physically based simulation steps with procedural generation of a piecewise continuous developable surface. The resulting hybrid surface model captures new singular points dynamically appearing during the crumpling process, mimicking the effect of paper fiber fracture. Although the model evolves over time to take these irreversible damages into account, the mesh used for simulation is kept coarse throughout the animation, leading to efficient computations. Meanwhile, the geometric layer ensures that the surface stays almost isometric to its original 2D pattern. We validate our model through measurements and visual comparison with real paper manipulation, and show results on a variety of crumpled paper configurations.

This paper presents a new technique for detecting sharp features on point-sampled geometry. Sharp features of different nature and possessing angles varying from obtuse to acute can be identified without any user interaction. The algorithm works directly on the point cloud, no surface reconstruction is needed. Given an unstructured point cloud, our method first computes a Gauss map clustering on local neighborhoods in order to discard all points which are unlikely to belong to a sharp feature. As usual, a global sensitivity parameter is used in this stage. In a second stage, the remaining feature candidates undergo a more precise iterative selection process. Central to our method is the automatic computation of an adaptive sensitivity parameter, increasing significantly the reliability and making the identification more robust in the presence of obtuse and acute angles. The algorithm is fast and does not depend on the sampling resolution, since it is based on a local neighbor graph computation.

Moving garments and other cloth objects exhibit dynamic, complex wrinkles. Generating such wrinkles in a virtual environment currently requires either a time-consuming manual design process, or a computationally expensive simulation, often combined with accurate parameter-tuning requiring specialized animator skills. Our work presents an alternative approach for wrinkle generation which combines coarse cloth animation with a post-processing step for efficient generation of realistic-looking fine dynamic wrinkles. Our method uses the stretch tensor of the coarse animation output as a guide for wrinkle placement. To ensure temporal coherence, the placement mechanism uses a space-time approach allowing not only for smooth wrinkle appearance and disappearance, but also for wrinkle motion, splitting, and merging over time. Our method generates believable wrinkle geometry using specialized curve-based implicit deformers. The method is fully automatic and has a single user control parameter that enables the user to mimic different fabrics.

Abstract Generating plausible deformations of a character skin within the standard production pipeline is a challenge. This paper presents a volume preservation method dedicated to skinned characters. As usual, the character is defined by a skin mesh at some rest pose and an animation skeleton. At each animation step, skin deformations are first computed using standard SSD. Our method corrects the result using a set of local deformations which model the fold‐over‐free, constant volume behavior of soft tissues. This is done geometrically, without the need of any physically‐based simulation. To make the method easily applicable, we also provide automatic ways to extract the local regions where volume is to be preserved and to compute adequate skinning weights, both based on the character's morphology.

Although deforming surfaces are frequently used in numerous domains (scientific applications, games...), only few works have been proposed until now for simplifying such data. However, these time-varying surfaces are generally represented as oversampled triangular meshes with a static connectivity, involving a large number of unnecessary details for some frames. Among the related works, some methods provide globally good results, but fine details appearing during the animation are not always well-preserved, because of a static geometry sampling. We propose a new simplification method for deforming surfaces based on a dynamic geometry sampling. The idea is to compute one coarse version at the first frame, and then to progressively update the coarse sampling for the subsequent frames. In order to optimally approximate each frame, vertices are added or removed following the appearance or disappearance of fine details in the frames. Our approach is fast, easy to implement, and produces good quality time-varying approximations with well-preserved fine details, at any given frame.

Abstract Geometric constraints have proved to be efficient for enhancing the realism of shape animation. The present paper addresses the computation and the preservation of the volume enclosed by multiresolution meshes. A wavelet based representation allows the mesh to be handled at any level of resolution. The key contribution is the calculation of the volume as a trilinear form with respect to the multiresolution coefficients. Efficiency is reached thanks to the pre‐processing of a sparse 3D data structure involving the transposition of the filters while represented as a lifting scheme. A versatile and interactive method for preserving the volume during a deformation process is then proposed. It is based on a quadratic minimization subject to a linearization of the volume constraint. A closed form of the solution is derived.

We present a method for deforming piecewise linear 3D curves with constant length constraint. We show how this constraint can be integrated into a multiresolution editing tool allowing an intuitive control of the deformation’s extent and aspect. The constraint is enforced following two steps. A first step consists in approximating the initial length by modifying the multiresolution decomposition at some specified scale. In a second step the constraint is exactly enforced by constrained minimization of a smoothness criterion. This process then provides the core of an integrated wrinkling tool for soft tissues modelling. A curve on the mesh is deformed, providing a deformation profile which is propagated in a user-defined neighbourhood on the surface.

The recent ability to measure quickly and inexpensively dense sets of points on physical objects has deeply influenced the way engineers represent shapes in CAD systems, animation software or in the game industry. Many researchers advocated to completely bypass smooth surface representations, and to stick to a dense mesh model throughout the design process. Yet smooth analytic representations are still required in standard CAD systems and animation software, for reasons of compactness, control, appearance and manufacturability. In this paper we present a new method for fitting a smooth adoptively refinable triangular spline surface of arbitrary topology to an arbitrary dense triangular mesh. The key ingredient in our solution is that adaptive fitting is achieved by 4-splitting triangular surface patches locally therefore no particular attention has to be paid the validity of an underlying subdivided mesh. Furthermore, the final surface is composed of low-degree polynomial patches that always join with Gl-continuity. The ability to adoptively refine the model allows to achieve a given approximation error with a minimal number of patches.

Smooth parametric surfaces interpolating triangular meshes are very useful for modeling surfaces of arbitrary topology. Several interpolants based on these kind of surfaces have been developed over the last fifteen years. However, with current 3D acquisition equipments, models are becoming more and more complex. Since previous interpolation methods lack a local refinement property, there is no way to locally adapt the level of detail. In this article, we introduce a hierarchical triangular surface model. The surface is overall tangent plane continuous and is defined parametrically as a piecewise quintic polynomial. It can be adaptively refined while preserving the overall tangent plane continuity. This model enables designers to create a complex smooth surface of arbitrary topology composed of a small number of patches to which details can be added by locally refining the patches until an arbitrary small size is reached. It is implemented as a hierarchical data structure where the top layer describes a coarse, smooth base surface and the lower levels encode the details in local frame coordinates.

Triangular Bezier patches are an important tool for defining smooth surfaces over arbitrary triangular meshes. The previously introduced 4-split method interpolates the vertices of a 2-manifold triangle mesh by a set of tangent plane continuous triangular Bezier patches of degree five. The resulting surface has an explicit closed form representation and is defined locally. In this paper, we introduce a new method for visually smooth interpolation of arbitrary triangle meshes based on a regular 4-split of the domain triangles. Ensuring tangent plane continuity of the surface is not enough for producing an overall fair shape. Interpolation of irregular control-polygons, be that in 1D or in 2D, often yields unwanted undulations. Note that this undulation problem is not particular to parametric interpolation, but also occurs with interpolatory subdivision surfaces. Our new method avoids unwanted undulations by relaxing the constraint of the first derivatives at the input mesh vertices: The tangent directions of the boundary curves at the mesh vertices are now completely free. Irregular triangulations can be handled much better in the sense that unwanted undulations due to flat triangles in the mesh are now avoided.

Polyhedral meshes are used for visualization, computer graphics or geometric modeling purposes and result from many applications like iso-surface extraction, surface reconstruction or CAD/CAM. The paper introduces a method for constructing smooth surfaces from a triangulated polyhedral mesh of arbitrary topology. It presents a new algorithm which generalizes and improves the triangle 4-split method (S. Hahmann and G.-P. Bonneau) in the crucial point of boundary curve network construction. This network is then filled in by a visual smooth surface from which an explicit closed form parametrization is given. Furthermore, the method becomes now completely local and can interpolate normal vector input at the mesh vertices.

In CAD/CAM technology, the design of free form surfaces is the beginning of a chain of operations, which ends with the numerically controlled (NC) production of the designed object. An important part of this chain is shape analysis. We present a stability concept for surfaces based on infinitesimal bendings. The infinitesimal rigidity is enforced by certain boundary conditions.

In the last five years, there has been numerous applications of wavelets and multiresolution analysis in many fields of computer graphics as different as geometric modelling, volume visualization or illumination modelling. Classical multiresolution analysis is based on the knowledge of a nested set of functional spaces in which the successive approximations of a given function converge to that function, and can be efficiently computed. This paper first proposes a theoretical framework which enables multiresolution analysis even if the functional spaces are not nested, as long as they still have the property that the successive approximations converge to the given function. Based on this concept, we finally introduce a new multiresolution analysis with exact reconstruction for large data sets defined on uniform grids. We construct a one-parameter family of multiresolution analyses which is a blending of Haar and linear multiresolution, using BLaC (Blending of Linear and Constant) wavelets.

Abstract The generation of technical smooth surfaces from a mesh of three‐dimensional data points is an important problem in geometric modelling. In this publication we give a survey of some new techniques based on a calculus of variation approach. Apart from the pure construction of these surfaces, the analysis of their quality is equally important in the design and manufacturing process. Generalized focal surfaces are presented here as a new surface interrogation tool.

The generation of smooth surfaces from a mesh of three-dimensional data points is an important problem in geometric modeling. Apart from the pure construction of these curves and surfaces, the analysis of their quality is equally important in the design and manufacturing process. Generalized focal surfaces are presented as a new surface interrogation tool.>