International audience

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.

International audience

Abstract We introduce a Delaunay‐based algorithm for reconstructing the underlying surface of a given set of unstructured points in 3D. The implementation is very simple, and it is designed to work in a parameter‐free manner. The solution builds upon the fact that in the continuous case, a closed surface separates the set of maximal empty balls (medial balls) into an interior and exterior. Based on discrete input samples, our reconstructed surface consists of the interface between Voronoi balls, which approximate the interior and exterior medial balls. An initial set of Voronoi balls is iteratively processed, merging Voronoi‐ball pairs if they fulfil an overlapping error criterion. Our complete open‐source reconstruction pipeline performs up to two quick linear‐time passes on the Delaunay complex to output the surface, making it an order of magnitude faster than the state of the art while being competitive in memory usage and often superior in quality. We propose two variants (local and global), which are carefully designed to target two different reconstruction scenarios for watertight surfaces from accurate or noisy samples, as well as real‐world scanned data sets, exhibiting noise, outliers, and large areas of missing data. The results of the global variant are, by definition, watertight, suitable for numerical analysis and various applications (e.g., 3D printing). Compared to classical Delaunay‐based reconstruction techniques, our method is highly stable and robust to noise and outliers, evidenced via various experiments, including on real‐world data with challenges such as scan shadows, outliers, and noise, even without additional preprocessing.

Abstract We introduce an approach for converting pixel art into high‐quality vector images. While much progress has been made on automatic conversion, there is an inherent ambiguity in pixel art, which can lead to a mismatch with the artist's original intent. Further, there is room for incorporating aesthetic preferences during the conversion. In consequence, this work introduces an interactive framework to enable users to guide the conversion process towards high‐quality vector illustrations. A key idea of the method is to cast the conversion process into a spring‐system optimization that can be influenced by the user. Hereby, it is possible to resolve various ambiguities that cannot be handled by an automatic algorithm.

Abstract We introduce Delaunay Painting, a novel and easy‐to‐use method to flat‐colour contour‐sketches with gaps. Starting from a Delaunay triangulation of the input contours, triangles are iteratively filled with the appropriate colours, thanks to the dynamic update of flow values calculated from colour hints. Aesthetic finish is then achieved, through energy minimisation of contour‐curves and further heuristics enforcing the appropriate sharp corners. To be more efficient, the user can also make use of our colour diffusion framework, which automatically extends colouring to small, internal regions such as those delimited by hatches. The resulting method robustly handles input contours with strong gaps. As an interactive tool, it minimizes user's efforts and enables any colouring strategy, as the result does not depend on the order of interactions. We also provide an automatized version of the colouring strategy for quick segmentation of contours images, that we illustrate with applications to medical imaging and sketch segmentation.

We present a novel, interactive interface for the integrated cleanup, neatening, structuring and vectorization of sketch imagery. Converting scanned raster drawings into vector illustrations is a well-researched set of problems. Our approach is based on a Delaunay subdivision of the raster drawing. We algorithmically generate a colored grouping of Delaunay regions that users interactively refine by dragging and dropping colors. Sketch strokes defined as marking boundaries of different colored regions are automatically neatened using Bézier curves, and turned into closed regions suitable for fills, textures, layering and animation. We show that minimal user interaction using our technique enables better sketch vectorization than state of art automated approaches. A user study, further shows our interface to be simple, fun and easy to use, yet effectively able to process messy images with a mix of construction lines, noisy and incomplete curves, sketched with arbitrary stroke style.

Abstract Curve reconstruction from unstructured points in a plane is a fundamental problem with many applications that has generated research interest for decades. Involved aspects like handling open, sharp, multiple and non‐manifold outlines, run‐time and provability as well as potential extension to 3D for surface reconstruction have led to many different algorithms. We survey the literature on 2D curve reconstruction and then present an open‐sourced benchmark for the experimental study. Our unprecedented evaluation of a selected set of planar curve reconstruction algorithms aims to give an overview of both quantitative analysis and qualitative aspects for helping users to select the right algorithm for specific problems in the field. Our benchmark framework is available online to permit reproducing the results and easy integration of new algorithms.

Abstract We present an incremental Voronoi vertex labelling algorithm for approximating contours, medial axes and dominant points (high curvature points) from 2D point sets. Though there exist many number of algorithms for reconstructing curves, medial axes or dominant points, a unified framework capable of approximating all the three in one place from points is missing in the literature. Our algorithm estimates the normals at each sample point through poles (farthest Voronoi vertices of a sample point) and uses the estimated normals and the corresponding tangents to determine the spatial locations (inner or outer) of the Voronoi vertices with respect to the original curve. The vertex classification helps to construct a piece‐wise linear approximation to the object boundary. We provide a theoretical analysis of the algorithm for points non‐uniformly (ε‐sampling) sampled from simple, closed, concave and smooth curves. The proposed framework has been thoroughly evaluated for its usefulness using various test data. Results indicate that even sparsely and non‐uniformly sampled curves with outliers or collection of curves are faithfully reconstructed by the proposed algorithm.

Abstract Given a planar point set sampled from an object boundary, the process of approximating the original shape is called curve reconstruction. In this paper, a novel non‐parametric curve reconstruction algorithm based on Delaunay triangulation has been proposed and it has been theoretically proved that the proposed method reconstructs the original curve under ε‐sampling. Starting from an initial Delaunay seed edge, the algorithm proceeds by finding an appropriate neighbouring point and adding an edge between them. Experimental results show that the proposed algorithm is capable of reconstructing curves with different features like sharp corners, outliers, multiple objects, objects with holes, etc. The proposed method also works for open curves. Based on a study by a few users, the paper also discusses an application of the proposed algorithm for reconstructing hand drawn skip stroke sketches, which will be useful in various sketch based interfaces.