Alla Sheffer

Ray-tracing has become an important technique used to generate photorealistic images in video games and movies. It is a technique in which straight rays of light traveling in a scene are simulated to produce realistic images. Signed Distance Fields are a class of mathematical functions used to describe 3D geometry. They allow for fast ray-object collision detection. While they are very well suited for simulating the trajectory a ray of light travels through in a scene, they lack explicit surface connectivity information. This makes it challenging to use existing methods that map the surface of the model into an image, also known as texture mapping. Thus, many applications either resort to hybrid approaches where both Signed Distance Fields and triangle meshes are used for different purposes, or texture mapping is not used. In these cases, it is assumed that objects have uniform material properties across large portions of their surface. We propose an algorithm that is capable of computing parametrizations (one of the most popular techniques for texture mapping) of Signed Distance Field data, that leverages an approach based on Dual Height Fields. We leverage the properties of Dual Height Fields, for efficient and effective texture mapping. We achieve this by meshing the model along the DHF direction, parametrizing the result, and then, at render time, using the DHF's natural parametrization to a plane to sample from a texture atlas. We show how our method suitably parametrizes surfaces with minimum distortion in many complex models and how it can be used for texture mapping.

View record

Many sketch processing applications target precise vector drawings with accurately specified stroke intersections, yet free-form artist drawn sketches are typically inexact: strokes that are intended to intersect often stop short of doing so. While human observers easily perceive the artist intended stroke connectivity, manually or even semi-manually correcting drawings to generate correctly-connected outputs is tedious and highly time consuming. We propose a novel, robust algorithm that extracts viewer-perceived stroke connectivity from inexact free-form vector drawings by leveraging observations about local and global factors that impact human perception of inter-stroke connectivity. We employ the identified local cues to train classifiers that assess the likelihood that pairs of strokes are perceived as forming end-to-end or T-junctions based on local context. We then use these classifiers within an incremental framework that combines classifier-provided likelihoods with a more global, contextual, and closure-based analysis. We demonstrate our method on over 95 diversely sourced inputs, and validate it via a series of perceptual studies; participants prefer our outputs over the closest alternative by a factor of 9 to 1.

View record

Concept sketches are common in the early stages of production design, as they require little time to produce and are effective at communicating both shape and volume information via carefully placed strokes. However, they are limited in their ability to convey material properties, and they do not help to envision a fully shaded product. Affording artists and designers the ability for fast sketching of shapes with rich visual shading can save a significant amount of time during the design refinement process, where shading is often done manually across multiple variations of lighting and material properties per iteration of ideas. To meet this need, CrossShade is an existing tool designed by Shao et al. for automatically shading line drawings. By leveraging specialized curves, in particular cross-section curves and the intersections between them, surface information of the curve-described geometry can be solved for via optimization of cross-section curve plane normals. Cross-section curves enforce a set of geometric constraints that aid viewers in lifting and interpreting concept sketches into 3D space, and so readily supplement regularity cues and perceptual constraints in a 3D reconstruction framework. We adopt the same regularity cues employed by CrossShade to estimate normals along cross-section curves in a new optimization routine, individually target curve networks constituting the whole of a line drawing sketch, and include a simple solution selection heuristic yielding more efficient, and robust results than previously reported. Accompanying our work is an updated sketch interface to make the drawing process more enjoyable for artists and designers.

View record

When creating freeform drawings, artists routinely employ clusters of overdrawn strokes to convey intended, aggregate curves. The ability to algorithmically fit these intended curves to their corresponding clusters is central to many applications that use artist drawings as inputs. However, while human observers effortlessly envision the intended curves given stroke clusters as input, existing fitting algorithms lack robustness and frequently fail when presented with input stroke clusters with non-trivial geometry or topology. We present StrokeStrip, a new and robust method for fitting intended curves to vector-format stroke clusters. Our method generates fitting outputs consistent with viewer expectations across a vast range of input stroke cluster configurations. We observe that viewers perceive stroke clusters as continuous, varying-width strips whose paths are described by the intended curves. An arc length parameterization of these strips defines a natural mapping from a strip to its path. We recast the curve fitting problem as one of parameterizing the cluster strokes using a joint 1D parameterization that is the restriction of the natural arc length parameterization of this strip to the strokes in the cluster. We simultaneously compute the joint cluster parameterization and implicitly reconstruct the a priori unknown strip geometry by solving a variational problem using a discrete-continuous optimization framework. We use this parameterization to compute parametric aggregate curves whose shape reflects the geometric properties of the cluster strokes at the corresponding isovalues. We demonstrate StrokeStrip outputs to be significantly better aligned with observer preferences compared to those of prior art; in a perceptual study, viewers preferred our fitting outputs by a factor of 12:1 compared to alternatives. We further validate our algorithmic choices via a range of ablation studies; extend our framework to raster data; and illustrate applications that benefit from the parameterizations produced.

View record

Raster clip-art images, which consist of distinctly colored regions separated by sharp boundaries typically allow for a clear mental vector interpretation. Vectorizing these images can facilitate compact lossless storage and enable numerous processing operations. Despite recent progress, existing vectorization methods that target this data frequently produce vectorizations that fail to meet viewer expectations. We present PolyFit, a new clip-art vectorization method that produces outputs well aligned with human preferences. Since segmentation of such inputs into regions had been addressed successfully, we focus on fitting piecewise smooth vector curves to the raster input region boundaries, a task prior methods are particularly prone to fail on. While perceptual studies suggest the criteria humans are likely to use during mental boundary vectorization, they provide no guidance as to the exact interaction between them; learning these interactions directly is problematic due to the large size of the solution space. To obtain the desired solution, we first approximate the raster region boundaries with coarse intermediate polygons leveraging a combination of perceptual cues with observations from studies of human preferences. We then use these intermediate polygons as auxiliary inputs for computing piecewise smooth vectorizations. We define a finite set of potential polygon to curve primitive maps, and learn the mapping from the polygons to their best fitting primitive configurations from human annotations, arriving at a compact set of local raster and polygon properties whose combinations reliably predict human-expected primitive choices. We obtain the final vectorization by fitting the computed primitive sequence to the raster data. Comparative user studies show that our method outperforms state-of-the-art approaches on a wide range of data; our results are preferred three times as often as those of the closest competitor across inputs with various resolutions. On low-resolution color data, this preference grows to a ratio of more than 15:1.

View record

High-order accurate numerical discretization methods are attractive for their potential to significantly reduce the computational costs compared to the traditional second-order methods. Among the various unstructured higher-order discretization schemes, the k-exact reconstruction finite volume method is of interest for its straightforward mathematical formulation, and its compatibility with the current lower-order industrial solvers. However, current three-dimensional finite volume solvers are limited to the solution of inviscid and laminar viscous flow problems. Since three-dimensional turbulent flows appear in many industrial applications, the current thesis takes the first step towards the development of a three-dimensional higher-order finite volume solver for the solution of both inviscid and viscous turbulent steady-state flow problems. The k-exact finite volume formulation of the governing equations is rederived in a dimension-independent manner, where the negative Spalart-Allmaras turbulence model is employed. This one-equation model is reasonably accurate for many flow conditions, and its simplicity makes it a good starting point for the development of numerical algorithms. Then, the three-dimensional mesh preprocessing steps for a finite volume simulation are presented, including higher-order accurate numerical quadrature, and capturing the boundary curvature in highly anisotropic meshes. Also, the issues of k-exact reconstruction in handling highly anisotropic meshes are reviewed and addressed. Since three-dimensional problems can require much more memory than their two-dimensional counter-parts, solution methods that work in two dimensions might not be feasible in three dimensions anymore. As an attempt to overcome this issue, a practical and parallel scalable method for the solution of the discretized system of nonlinear equations is presented. Finally, the solution of four three-dimensional test problems are studied: Poisson’s equation in a cubic domain, inviscid flow over a sphere, turbulent flow over a flat plate, and turbulent flow over an extruded NACA 0012 airfoil. The solution is verified, and the resource consumption of the flow solver is measured. The results demonstrate the benefit and practicality of using higher-order methods for obtaining a certain level of accuracy.

View record

While folds and pleats add interest to garments and cloth objects, incorporating them into an existing design manually or using existing software requires expertise and time. This thesis presents FoldSketch, a new system that supports simple and intuitive fold and pleat design. FoldSketch users specify the fold or pleat configuration they seek using a simple schematic sketching interface; the system then algorithmically generates both the fold-enhanced 3D garment geometry that conforms to user specifications, and the corresponding 2D patterns that reproduce this geometry within a simulation engine. While previous work aspired to compute the desired patterns for a given target 3D garment geometry, the main algorithmic challenge here is that the target geometry is missing. Real-life garment folds have complex profile shapes, and their exact geometry and location on a garment are intricately linked to a range of physical factors; it is therefore virtually impossible to predict the 3D shape of a fold-enhanced garment using purely geometric means. At the same time, using physical simulation to model folds requires appropriate 2D patterns and initial drape, neither of which can be easily provided by the user.FoldSketch obtains both the 3D fold-enhanced garment and its corresponding patterns and initial drape via an alternating 2D-3D algorithm. We first expand the input patterns by allocating excess material for the expected fold formation; then we use these patterns to produce an estimated fold-enhanced target drape geometry that balances designer expectations against physical reproducibility. Next, we generate an initial reproducible output using the expanded patterns and the estimated target drape as input to a garment simulation engine. Then we improve the output's alignment with designer expectations by progressively refining the patterns and the estimated target drape, converging to a final fully physically reproducible fold-enhanced garment. The experiments confirm that FoldSketch reliably converges to a desired garment geometry and corresponding patterns and drape, and works well with different physical simulators. My collaborators and I demonstrate the versatility of this approach by showcasing a collection of garments augmented with diverse fold and pleat layouts specified via the FoldSketch interface, and further validate this approach via feedback from potential users.

View record

High-order accurate numerical discretization methods are attractive for their potential to significantly reduce the computational costs compared to the traditional second-order methods. Among the various unstructured higher-order discretization schemes, the k-exact reconstruction finite volume method is of interest for its straightforward mathematical formulation, and its compatibility with the current lower-order industrial solvers. However, current three-dimensional finite volume solvers are limited to the solution of inviscid and laminar viscous flow problems. Since three-dimensional turbulent flows appear in many industrial applications, the current thesis takes the first step towards the development of a three-dimensional higher-order finite volume solver for the solution of both inviscid and viscous turbulent steady-state flow problems. The k-exact finite volume formulation of the governing equations is rederived in a dimension-independent manner, where the negative Spalart-Allmaras turbulence model is employed. This one-equation model is reasonably accurate for many flow conditions, and its simplicity makes it a good starting point for the development of numerical algorithms. Then, the three-dimensional mesh preprocessing steps for a finite volume simulation are presented, including higher-order accurate numerical quadrature, and capturing the boundary curvature in highly anisotropic meshes. Also, the issues of k-exact reconstruction in handling highly anisotropic meshes are reviewed and addressed. Since three-dimensional problems can require much more memory than their two-dimensional counter-parts, solution methods that work in two dimensions might not be feasible in three dimensions anymore. As an attempt to overcome this issue, a practical and parallel scalable method for the solution of the discretized system of nonlinear equations is presented. Finally, the solution of four three-dimensional test problems are studied: Poisson’s equation in a cubic domain, inviscid flow over a sphere, turbulent flow over a flat plate, and turbulent flow over an extruded NACA 0012 airfoil. The solution is verified, and the resource consumption of the flow solver is measured. The results demonstrate the benefit and practicality of using higher-order methods for obtaining a certain level of accuracy.

View record

This thesis presents FlowRep, an algorithm for extracting descriptive compact 3D curve networks from meshes of free-form man-made shapes. FlowRep output networks provide a concise visual description of the underlying surface, and can be used as a compact proxy for shape compression, editing and manipulation. While artists routinely and successfully create descriptive curve networks to depict complex 3D shapes in 3D space or on 2D media, the method described here is the first to achieve this goal algorithmically. FlowRep infers the desired compact curve network from complex 3D geometries by using a series of insights derived from perception, computer graphics, and design literature which point to two sets of geometric properties that such networks should satisfy. These sources suggest that visually descriptive networks are cycle-descriptive, i.e their cycles unambiguously describe the geometry of the surface patches they surround. They also indicate that such networks are designed to be projectable, or easy to envision when observed from a static general viewpoint; in other words, 2D projections of the network should be strongly indicative of its 3D geometry. Research suggests that both properties are best achieved by using networks dominated by flowlines, surface curves aligned with principal curvature directions across anisotropic regions and strategically extended across sharp-features and isotropic areas. The algorithm leverages these observations in the construction of a compact descriptive curve network. Starting with a curvature aligned quad dominant mesh I first extract sequences of mesh edges that form long, well-shaped and reliable flowlines by leveraging directional similarity between nearby meaningful flowline directions. This process overcomes topological noise, and inaccuracies and singularities in the underlying curvature field. I then use the extracted flowlines and the model's sharp-feature, or trim, curves to form a projectable network which describes the underlying surface. Finally, I simplify this network while preserving its descriptive power to obtain the final result. My co-authors and I validate our method by demonstrating a range of networks computed from diverse inputs, using them for surface reconstruction, and showing extensive comparisons with prior work and artist generated networks.

View record

This work presents a novel technique for generating a plausible rest shape to cloth animations which have none, and adding dynamic folds and wrinkles to them inreal-time. The nature of real-time animations makes this task very challenging. The models used are typically very coarse, and the animations used are often nonphysical and exhibit poor temporal and spatial coherence. Since animations can move and deform in non-physical ways, the notion of a valid rest shape or reference shape is not well defined. Instead, we utilize a graph-cut framework to smoothly and consistently measure temporally local deformation in the animation, and use that to construct a per-triangle temporally adaptive pseudo-reference shape. From this shape we compute a stretch tensor field whose eigenvectors can be used to trace plausible dynamic wrinkle paths. We then harness the GPU tessellation unit to refine and deform the cloth along these paths to create wrinkle geometry. Our method runs in real-time on a variety of data sets.

View record

Folds and wrinkles are an important visual cue in the recognition of realistically dressed characters in virtual environments. Wrinkles must, however, move dynamically within the context of an animation to retain much of this realism. Adding wrinkles to real-time cloth visualization proves challenging, as the animations used in games, pre-render visualization, and other such applications, often have no reference shape, an extremely low triangle count, and poor temporal and spatial coherence. I contribute approaches towards the persistence of wrinkles over time, and the creation and rendering of wrinkle geometry in a real-time context, towards a novel real-time method for adding believable, dynamic wrinkles to coarse cloth animations. With this method we trace spatially and temporally coherent wrinkle paths and overcomes the inaccuracies and noise in low-end cloth animation. We employ a two stage stretch tensor estimation process, first detecting regions of consistent surface behaviour, and then using these regions to construct a per-triangle, temporally adaptive reference shape and a stretch tensor based on it. We use this tensor to dynamically generate new wrinkle geometry on coarse cloth meshes through use of the GPU tessellation unit. Our algorithm produces plausible fine wrinkles on real-world data sets at real-time frame rates, and is suitable for the current generation of consoles and PC graphics cards.

View record

This work presents a novel, design-driven quadrangulating method for closed 3Dcurves. While the quadrangulation of existing surfaces has been well studied for along time, there are few works that can successfully construct a quad-mesh relyingsolely on 3D curves, as the shape of the surface interior is not uniquely defined.I observe that, in most cases, viewers can complete the intended shape by envisioninga dense network of smooth, gradually changing flow-lines across a pair ofinput curve segments with similar orientation and shape. The method proposedhere mimics this behavior.This algorithm begins by segmenting the input closed curves into pairs ofmatching segments. I interpolate the input curves by a network of quadrilateralcycles whose iso-lines define the desired flow line network. I proceed to interpolatethese networks with all-quad meshes that convey designer intents. I evaluatemy results by showing convincing quadrangulations of complex and diverse curvenetworks with concave, non-planar cycles, and validate my approach by comparingmy results to artist generated interpolating meshes.My algorithm is suitable for use in sketch-based modeling systems as well asin other applications where artist curves can be created.

View record

This work presents an automatic creation of 3D models from single view design sketches. We observe that these sketches typically employ networks of trim curves and cross-sections to convey shape. Combined together these curves define the representative flow-lines of the model, reflecting principal curvature and feature lines across the target surface. Artists design these lines to serve as a visual proxy of the 3D object and to effectively convey all surface details. Cross-sections, in particular, are known to impose a set of geometric constraints on the imagined surface, that help position the surface in 3D. We formulate the problem of reconstructing believ- able 3D curve geometry from design sketches via an optimization framework that leverages the geometric properties of flow-line networks, the constraints imposed by cross-section curves, and observations on how people perceive and sketch such networks. This algorithm utilizes these criteria to simultaneously construct the 3D curves and correct for inevitable inaccuracies in free-hand sketches, which if retained would hinder constraint satisfaction and may lead to noticeable artifacts in the reconstructed 3D models. We validate our framework by producing believable 3D curve networks and surfaces from design sketches based on cross-section and trim curves, conducting a qualitative comparison to artist-estimated models, and visual validation by designers.

View record

This work is concerned with computer-assisted generation of text art. Specifically, we consider an artistic style known as micrography, in which complex images are constructed from lines of tiny, readable text. Traditionally created by trained scribes and requiring immense amounts of effort, micrography has in recent years crossed over into the digital domain, with modern artists adapting the style in various ways and using it to convey their own message. Unfortunately, creating micrography with standard digital graphic design techniques remains a tedious and frustrating exercise.The method proposed here is capable of automating the work-intensive aspects of micrography, while still keeping the designer in control of the overall look and feel of the result. For artists, this means they can now rapidly experiment with different designs in a way that would be infeasible using traditional digital techniques.We begin with an analysis of the aesthetic properties of text flow that make for a visually appealing micrography. Observing that some of these requirements are shared with well-studied problems in computer graphics such as parameterization and quadrangulation, we base our solution on the popular framework of smooth fields, augmenting it with a novel approach to boundary constraint design for planar shapes. The result is a system that lets artists generate beautiful micrography in a matter of minutes, automatically optimizing for aesthetic appeal and readability while also allowing for intuitive manual intervention.

View record

We present a novel algorithm for space-time reconstruction of deforming meshes. Based on partial meshes at every frame, and sparse optical flow information between frames, we reconstruct a globally consistent, crossparameterized, and hole filled sequence of meshes. Our method is based on pair-wise merging of frame sequences while correcting for changes in topology, filling in missing geometry, and repairing inconsistencies. We also introduce a robust method for filling in missing geometry in each frame of the sequence using geometry from another frame. Using this method we can propagate geometry over the full frame sequence, correcting errors and filling in holes even in regions of the object that are not observed in the input meshes for extended periods of time. Unlike other approaches, our method does not require template geometry, nor is it limited to narrow classes of objects or purely isometric deformations.

View record

Cloth modeling has become an important research topic in computer graphics, as garments are ubiquitous in virtual environments used in movies or games. While recent studies can successfully capture the general shape of cloth as well as a continuous cloth motion, they usually lose high frequency details such as wrinkles or folds. This work provides a method of recovering high frequency details for captured cloth animation sequences without any aids of additional information. The method analyzes the stretch/shrinkage tensor fields in 4D space-time domain for the original cloth animation sequences. Based on the assumption of cloth developability, the stretch/shrinkage information is utilized to recover fold shapes and directions. Finally, a space-time consistent deformation method is applied to recover the high frequency folds. The work is generally applicable to most of the cloth capture methods applied either on scanned point clouds or video sequences.

View record