In shape analysis and matching, it is often important to encode information about the relation between a given point and other points on a shape, namely its context. To this aim we propose a theoretically sound and efficient approach for the simulation of a discrete time evolution process that runs through all the possible geodesic paths between pairs of points on a surface represented as a triangle mesh in the discrete setting. We demonstrate how this construction can be used to efficiently construct a multiscale point descriptor, called Discrete time Evolution Process Descriptor, which robustly encodes the structure of geodesic neighborhoods of a point across multiple scales. Our work is closely related to the methods based on diffusion geometry, and derived signatures such as the HKS or the WKS, and provides information that is complementary to these descriptors. We demonstrate through extensive experimental evaluation that our descriptor shows promising results in both shape matching and shape segmentation scenarios. Our approach outperforms similar methods especially when comparing shapes undergoing large non-isometric deformations and in the presence of missing parts.
The depth resolution achieved by a continuous wave time-of-flight (C-ToF) imaging system is determined by the coding (modulation and demodulation) functions that it uses. Almost all current C-ToF systems use sinusoid or square coding functions, resulting in a limited depth resolution. In this paper, we present a mathematical framework for exploring and characterizing the space of C-ToF coding functions in a geometrically intuitive space. Using this framework, we design families of novel coding functions that are based on Hamiltonian cycles on hypercube graphs. Given a fixed total source power and acquisition time, the new Hamiltonian coding scheme can achieve up to an order of magnitude higher resolution as compared to the current state-of-the art methods, especially in low SNR settings. We also develop a comprehensive physically-motivated simulator for C-ToF cameras that can be used to evaluate various coding schemes prior to a real hardware implementation. Since most off-the-shelf C-ToF sensors use sinusoid or square functions, we develop a hardware prototype that can implement a wide range of coding functions. Using this prototype and our software simulator, we demonstrate the performance advantages of the proposed Hamiltonian coding functions in a wide range of imaging settings.
A conformal flattening maps a curved surface to the plane without distorting angles---such maps have become a fundamental building block for problems in geometry processing, numerical simulation, and computational design. Yet existing methods provide little direct control over the shape of the flattened domain, or else demand expensive nonlinear optimization. Boundary first flattening (BFF) is a linear method for conformal parameterization which is faster than traditional linear methods, yet provides control and quality comparable to sophisticated nonlinear schemes. The key insight is that boundary data can be efficiently constructed via the Cherrier formula together with a pair of Poincare-Steklov operators; once the boundary is known, the map is easily extended over the rest of the domain. Since computation demands only a single factorization of the real Laplacian, the amortized cost is about 50x less than any previous technique for boundary-controlled conformal flattening. BFF therefore opens the door to real-time editing or fast optimization of high-resolution maps, with direct control over boundary length or angle. We apply this method to maps with sharp corners, cone singularities, minimal area distortion, and uniformization; we also demonstrate for the first time how a surface can be conformally flattened directly onto any given target shape.
Distributing a simulation across many machines can drastically speed up computations and increase detail. The computing cloud provides tremendous computing resources, but weak service guarantees force programs to manage significant system complexity: nodes, networks, and storage occasionally perform poorly or fail. We describe Halo, a system that automatically distributes grid-based and hybrid simulations across cloud computing nodes. The main simulation loop is written as simple sequential code and launches distributed computations across many cores. The simulation on each core runs as if it is stand-alone: Halo automatically stitches these multiple simulations into a single, larger one. To do this efficiently, Halo introduces a four-layer data model that translates between the contiguous, geometric objects used by simulation libraries and the replicated, fine-grained objects managed by its underlying cloud computing runtime. Using PhysBAM particle level-set fluid simulations, we demonstrate that Halo can run higher detail simulations faster, distribute simulations on up to 512 cores and run enormous simulations ($1024^3$ cells). Halo automatically manages these distributed simulations, balancing load across nodes and recovering from failures. Implementations of PhysBAM water and smoke simulations as well as an open source heat-diffusion simulations show Halo is general and can support complex simulations.
We present an integral framework for training sketch simplification networks that convert challenging rough sketches into clean line drawings. Our approach augments a simplification network with a discriminator network, training both networks jointly so that the discriminator network discerns whether a line drawing is a real training data or the output of the simplification network, which in turn tries to fool it. This approach not only encourages the output sketches to be more similar in appearance to the training sketches, but allows training with additional unsupervised data. By training with additional rough sketches and line drawings that are not corresponding to each other, we can improve the quality of the sketch simplification. Our models that significantly outperform the state of the art in the sketch simplification task, and show we can also optimize for a single image, which improves accuracy at the cost of additional computation time. Using the same framework, it is possible to train the network to perform pencil drawing generation, which is not possible using the standard mean squared error loss. We validate our framework with two user tests, where our approach is preferred to the state of the art in sketch simplification 88.9% of the time.
We present the first computational tool to help ordinary users create trans- forming pop-up books. In each transforming pop-up, when the user pulls a tab, an initial flat 2D pattern, i.e. a 2D shape with a superimposed picture, such as an airplane, turns into a new 2D pattern, such as a robot, standing up from the page. Given the two 2D patterns, our approach automatically computes a 3D pop-up mechanism that transforms one pattern into the oth- er; it also outputs a design blueprint, allowing the user to easily make the final model. We also present a theoretical analysis of basic transformation mechanisms; combining these basic mechanisms allows more flexibility of final designs. Using our approach, inexperienced users can create models in a short time; previously, even experienced artists often took weeks to man- ually create them. We demonstrate our method on a variety of real world examples.
Endowing 3D objects with realistic surface appearance is a challenging and time-demanding task, since real world surfaces typically exhibit a plethora of spatially variant geometric and photometric detail. Not surprisingly, computer artists commonly use images of real world objects as an inspiration and a reference for their digital creations. However, despite two decades of research on image-based modeling, there are still no tools available for automatically extracting the detailed appearance (micro-geometry and texture) of a 3D surface from a single image. In this paper, we present a novel user-assisted approach for quickly and easily extracting a non-parametric appearance model from a single photograph of a reference object with a proxy, whose geometry roughly approximates that of the object in the photo. Once extracted, the appearance model may then be applied to various 3D shapes, whose large scale geometry may differ considerably from that of the original reference object. Thus, our approach makes it possible to construct an appearance library, allowing users to easily enrich detail-less 3D shapes with realistic geometric detail and surface texture.
We propose an algorithm for generating novel 3D tree model variations from existing ones via geometric and structural blending. Our approach is to treat botanical trees as elements of a tree-shape space equipped with a proper metric that quantifies geometric and structural deformations. Geodesics, or shortest paths under the metric, between two points in the tree-shape space correspond to optimal deformations that align one tree onto another, including the possibility of growing, adding or removing branches and parts. Central to our approach is a mechanism for computing correspondences between trees that have different structures and different number of branches. The ability to compute geodesics and their lengths enables us to compute continuous blending between botanical trees, which in turn facilitates statistical analysis such as the computation of averages of tree structures. We show a variety of 3D tree models generated with our approach from 3D trees exhibiting complex geometric and structural differences. We also demonstrate the application of the framework in reflection symmetry analysis and symmetrization of botanical trees.
We present a new time integration method featuring excellent stability and energy conservation properties, making it particularly suitable for real-time physics. The commonly used Backward Euler method is stable, but introduces artificial damping. Methods such as Implicit Midpoint do not suffer from artificial damping but are unstable in many common simulation scenarios. We propose an algorithm which blends between the Implicit Midpoint and Forward/Backward Euler integrators such that the resulting simulation is stable while introducing only minimal artificial damping. We achieve this by tracking the total energy of the simulated system, taking into account energy-changing events: damping and forcing. To facilitate real-time simulations we propose a local/global solver, similar to Projective Dynamics, as an alternative to Newton's method. Compared to the original Projective Dynamics, which is derived from Backward Euler, our final method introduces much less numerical damping at the cost of minimal computing overhead. Stability guarantees of our method are derived from the stability of Backward Euler, whose stability is a widely accepted empirical fact. However, to our knowledge, theoretical guarantees have so far only been proven for linear ODEs. We provide preliminary theoretical results proving the stability of Backward Euler also for certain cases of non-linear potential functions.
We introduce FontCode, an information embedding technique for text documents. Provided a text document with specific fonts, our method embeds user-specified information in the text by perturbing the glyphs of text characters while preserving the text content. We devise an algorithm to choose unobtrusive yet machine-recognizable glyph perturbations, leveraging a recently developed generative model that alters the glyphs of each character continuously on a font manifold. We then introduce an algorithm that embeds a user-provided message in the text document and produces an encoded document whose appearance is minimally perturbed from the original document. We also present a glyph recognition method that recovers the embedded information from an encoded document stored as a vector graphic or pixel image, or even on a printed paper. In addition, we introduce a new error-correction coding scheme that rectifies a certain number of recognition errors. Lastly, we demonstrate that our technique enables a wide array of applications, using it as a text document metadata holder, an unobtrusive optical barcode, a cryptographic message embedding scheme, and a text document signature.