Large Computer-Aided Design (CAD) projects usually require collaboration across many different CAD systems as well as applications that interoperate with them for manufacturing, visualization, or simulation. A fundamental barrier to such collaborations is the ability to refer to parts of the geometry (such as a specific face) robustly under geometric and/or topological changes to the model. Persistent referencing schemes are a fundamental aspect of most CAD tools, but models that are shared across systems cannot generally make use of these internal referencing mechanisms, creating a challenge for collaboration. In this work, we address this issue by developing a novel learning-based algorithm that can automatically find correspondences between two CAD models using the standard representation used for sharing models across CAD systems: the Boundary-Representation (B-rep). Because our method works directly on B-reps it can be generalized across different CAD applications enabling collaboration.

Assembly modeling is a core task of computer aided design (CAD), comprising around one third of the work in a CAD workflow. Optimizing this process therefore represents a huge opportunity in the design of a CAD system, but current research of assembly based modeling is not directly applicable to modern CAD systems because it eschews the dominant data structure of modern CAD: parametric boundary representations (BREPs). CAD assembly modeling defines assemblies as a system of pairwise constraints, called mates , between parts, which are defined relative to BREP topology rather than in world coordinates common to existing work. We propose SB-GCN, a representation learning scheme on BREPs that retains the topological structure of parts, and use these learned representations to predict CAD type mates. To train our system, we compiled the first large scale dataset of BREP CAD assemblies, which we are releasing along with benchmark mate prediction tasks. Finally, we demonstrate the compatibility of our model with an existing commercial CAD system by building a tool that assists users in mate creation by suggesting mate completions, with 72.2% accuracy.

While collections of parametric shapes are growing in size and use, little progress has been made on the fundamental problem of shape-based matching and retrieval for parametric shapes in a collection. The search space for such collections is both discrete (number of shapes) and continuous (parameter values). In this work, we propose representing this space using descriptors that have shown to be effective for single shape retrieval. While single shapes can be represented as points in a descriptor space, parametric shapes are mapped into larger continuous regions. For smooth descriptors, we can assume that these regions are bounded low-dimensional manifolds where the dimensionality is given by the number of shape parameters. We propose representing these manifolds with a set of primitives, namely, points and bounded tangent spaces. Our algorithm describes how to define these primitives and how to use them to construct a manifold approximation that allows accurate and fast retrieval. We perform an analysis based on curvature, boundary evaluation, and the allowed approximation error to select between primitive types. We show how to compute decision variables with no need for empirical parameter adjustments and discuss theoretical guarantees on retrieval accuracy. We validate our approach with experiments that use different types of descriptors on a collection of shapes from multiple categories.

Abstract At each shade point, the spherical visibility function encodes occlusion from surrounding geometry, in all directions. Computing this function is difficult and point‐sampling approaches, such as ray‐tracing or hardware shadow mapping, are traditionally used to efficiently approximate it. We propose a semi‐analytic solution to the problem where the spherical silhouette of the visibility is computed using a search over a 4D dual mesh of the scene. Once computed, we are able to semi‐analytically integrate visibility‐masked spherical functions along the visibility silhouette, instead of over the entire hemisphere. In this way, we avoid the artefacts that arise from using point‐sampling strategies to integrate visibility, a function with unbounded frequency content. We demonstrate our approach on several applications, including direct illumination from realistic lighting and computation of pre‐computed radiance transfer data. Additionally, we present a new frequency‐space method for exactly computing all‐frequency shadows on diffuse surfaces. Our results match ground truth computed using importance‐sampled stratified Monte Carlo ray‐tracing, with comparable performance on scenes with low‐to‐moderate geometric complexity.

The facial performance of an individual is inherently rich in subtle deformation and timing details. Although these subtleties make the performance realistic and compelling, they often elude both motion capture and hand animation. We present a technique for adding fine-scale details and expressiveness to low-resolution art-directed facial performances, such as those created manually using a rig, via marker-based capture, by fitting a morphable model to a video, or through Kinect reconstruction using recent faceshift technology. We employ a high-resolution facial performance capture system to acquire a representative performance of an individual in which he or she explores the full range of facial expressiveness. From the captured data, our system extracts an expressiveness model that encodes subtle spatial and temporal deformation details specific to that particular individual. Once this model has been built, these details can be transferred to low-resolution art-directed performances. We demonstrate results on various forms of input; after our enhancement, the resulting animations exhibit the same nuances and fine spatial details as the captured performance, with optional temporal enhancement to match the dynamics of the actor. Finally, we show that our technique outperforms the current state-of-the-art in example-based facial animation.

Artists explore the visual style of animated characters through 2D concept art, since it affords them a nearly unlimited degree of creative freedom. Realizing the desired visual style, however, within the 3D character animation pipeline is often impossible, since artists must work within the technical limitations of the pipeline toolset. In order to expand the range of possible visual styles for digital characters, our research aims to incorporate the expressiveness afforded by 2D concept painting into the computer animation pipeline as a core component of character authoring and animation. While prior 3D painting methods focus on static geometry or simple animations, we develop tools for the more difficult task of character animation. Our system shows how 3D stroke-based paintings can be deformed using standard rigging tools. We also propose a configuration-space keyframing algorithm for authoring stroke effects that depend on scene variables such as character pose or light position. During animation, our system supports stroke-based temporal keyframing for one-off effects. Our primary technical contribution is a novel interpolation scheme for configuration-space keyframing that ensures smooth, controllable results. We demonstrate several characters authored with our system that exhibit painted effects difficult to achieve with traditional animation tools.

We consider the problem of generalizing affine combinations in Euclidean spaces to triangle meshes: computing weighted averages of points on surfaces. We address both the forward problem , namely computing an average of given anchor points on the mesh with given weights, and the inverse problem , which is computing the weights given anchor points and a target point. Solving the forward problem on a mesh enables applications such as splines on surfaces, Laplacian smoothing and remeshing. Combining the forward and inverse problems allows us to define a correspondence mapping between two different meshes based on provided corresponding point pairs, enabling texture transfer, compatible remeshing, morphing and more. Our algorithm solves a single instance of a forward or an inverse problem in a few microseconds. We demonstrate that anchor points in the above applications can be added/removed and moved around on the meshes at interactive framerates, giving the user an immediate result as feedback.

Abstract We present a practical and inexpensive method for creating physical objects that cast different color shadow images when illuminated by prescribed lighting configurations. The input to our system is a number of lighting configurations and corresponding desired shadow images. Our approach computes attenuation masks, which are then printed on transparent materials and stacked to form a single multi‐layer attenuator. When illuminated with the input lighting configurations, this multi‐layer attenuator casts the prescribed color shadow images. Alternatively, our method can compute layers so that their permutations produce different prescribed shadow images under fixed lighting. Each multi‐layer attenuator is quick and inexpensive to produce, can generate multiple full‐color shadows, and can be designed to respond to different types of natural or synthetic lighting setups. We illustrate the effectiveness of our multi‐layer attenuators in simulation and in reality, with the sun as a light source.

Abstract ShadowPixare white surfaces that display several prescribed images formed by the self‐shadowing of the surface when lit from certain directions. The effect is surprising and not commonly seen in the real world. We present algorithms for constructingShadowPixthat allow up to four images to be embedded in a single surface. ShadowPixcan produce a variety of unusual effects depending on the embedded images: moving the light can animate or relight the object in the image, or three colored lights may be used to produce a single colored image. ShadowPixare easy to manufacture using a 3D printer and we present photographs, videos, and renderings demonstrating these effects.

Skinning transformations are a popular way to articulate shapes and characters. However, traditional animation interfaces require all of the skinning transformations to be specified explicitly, typically using a control structure (a rig). We propose a system where the user specifies only a subset of the degrees of freedom and the rest are automatically inferred using nonlinear, rigidity energies. By utilizing a low-order model and reformulating our energy functions accordingly, our algorithm runs orders of magnitude faster than previous methods without compromising quality. In addition to the immediate boosts in performance for existing modeling and real time animation tools, our approach also opens the door to new modes of control: disconnected skeletons combined with shape-aware inverse kinematics. With automatically generated skinning weights, our method can also be used for fast variational shape modeling.

3D printing technology is rapidly maturing and becoming ubiquitous. One of the remaining obstacles to wide-scale adoption is that the object to be printed must fit into the working volume of the 3D printer. We propose a framework, called Chopper, to decompose a large 3D object into smaller parts so that each part fits into the printing volume. These parts can then be assembled to form the original object. We formulate a number of desirable criteria for the partition, including assemblability, having few components, unobtrusiveness of the seams, and structural soundness. Chopper optimizes these criteria and generates a partition either automatically or with user guidance. Our prototype outputs the final decomposed parts with customized connectors on the interfaces. We demonstrate the effectiveness of Chopper on a variety of non-trivial real-world objects.

Light scattering in a participating medium is responsible for several important effects we see in the natural world. In the presence of occluders, computing single scattering requires integrating the illumination scattered towards the eye along the camera ray, modulated by the visibility towards the light at each point. Unfortunately, incorporating volumetric shadows into this integral, while maintaining real-time performance, remains challenging.

We present a method for rendering 3D paintings by compositing brush strokes embedded in space. The challenge in compositing 3D brush strokes is reconciling conflicts between their z -order in 3D and the order in which the strokes were painted, while maintaining temporal and spatial coherence. Our algorithm smoothly transitions between compositing closer strokes over those farther away and compositing strokes painted later over those painted earlier. It is efficient, running in O ( n log n ) time, and simple to implement. We demonstrate its effectiveness on a variety of 3D paintings.

We present a method for automatically converting a digital 3D model into a multilayer model : a parallel stack of high-resolution 2D images embedded within a semi-transparent medium. Multilayer models can be produced quickly and cheaply and provide a strong sense of an object's 3D shape and texture over a wide range of viewing directions. Our method is designed to minimize visible cracks and other artifacts that can arise when projecting an input model onto a small number of parallel planes, and avoid layer transitions that cut the model along important surface features. We demonstrate multilayer models fabricated with glass and acrylic tiles using commercially available printers.

Object deformation with linear blending dominates practical use as the fastest approach for transforming raster images, vector graphics, geometric models and animated characters. Unfortunately, linear blending schemes for skeletons or cages are not always easy to use because they may require manual weight painting or modeling closed polyhedral envelopes around objects. Our goal is to make the design and control of deformations simpler by allowing the user to work freely with the most convenient combination of handle types. We develop linear blending weights that produce smooth and intuitive deformations for points, bones and cages of arbitrary topology. Our weights, called bounded biharmonic weights, minimize the Laplacian energy subject to bound constraints. Doing so spreads the influences of the controls in a shape-aware and localized manner, even for objects with complex and concave boundaries. The variational weight optimization also makes it possible to customize the weights so that they preserve the shape of specified essential object features. We demonstrate successful use of our blending weights for real-time deformation of 2D and 3D shapes.

Abstract Clothoid splines are gaining popularity as a curve representation due to their intrinsically pleasing curvature, which varies piecewise linearly over arc length. However, constructing them from hand‐drawn strokes remains difficult. Building on recent results, we describe a novel algorithm for approximating a sketched stroke with a fair (i.e., visually pleasing) clothoid spline. Fairness depends on proper segmentation of the stroke into curve primitives — lines, arcs, and clothoids. Our main idea is to cast the segmentation as a shortest path problem on a carefully constructed weighted graph. The nodes in our graph correspond to a vastly overcomplete set of curve primitives that are fit to every subsegment of the sketch, and edges correspond to transitions of a specified degree of continuity between curve primitives. The shortest path in the graph corresponds to a desirable segmentation of the input curve. Once the segmentation is found, the primitives are fit to the curve using non‐linear constrained optimization. We demonstrate that the curves produced by our method have good curvature profiles, while staying close to the user sketch.

Volumetric effects such as beams of light through participating media are an important component in the appearance of the natural world. Many such effects can be faithfully modeled by a single scattering medium. In the presence of shadows, rendering these effects can be prohibitively expensive: current algorithms are based on ray marching, i.e., integrating the illumination scattered towards the camera along each view ray, modulated by visibility to the light source at each sample. Visibility must be determined for each sample using shadow rays or shadow-map lookups. We observe that in a suitably chosen coordinate system, the visibility function has a regular structure that we can exploit for significant acceleration compared to brute force sampling. We propose an efficient algorithm based on partial sum trees for computing the scattering integrals in a single-scattering homogeneous medium. On a CPU, we achieve speedups of 17--120x over ray marching.

Transferring existing mesh deformation from one character to another is a simple way to accelerate the laborious process of mesh animation. In many cases, it is useful to preserve the semantic characteristics of the motion instead of its literal deformation. For example, when applying the walking motion of a human to a flamingo, the knees should bend in the opposite direction. Semantic deformation transfer accomplishes this task with a shape space that enables interpolation and projection with standard linear algebra. Given several example mesh pairs, semantic deformation transfer infers a correspondence between the shape spaces of the two characters. This enables automatic transfer of new poses and animations.

We describe a system for high-resolution capture of moving 3D geometry, beginning with dynamic normal maps from multiple views. The normal maps are captured using active shape-from-shading (photometric stereo), with a large lighting dome providing a series of novel spherical lighting configurations. To compensate for low-frequency deformation, we perform multi-view matching and thin-plate spline deformation on the initial surfaces obtained by integrating the normal maps. Next, the corrected meshes are merged into a single mesh using a volumetric method. The final output is a set of meshes, which were impossible to produce with previous methods. The meshes exhibit details on the order of a few millimeters, and represent the performance over human-size working volumes at a temporal resolution of 60Hz.

Details in mesh animations are difficult to generate but they have great impact on visual quality. In this work, we demonstrate a practical software system for capturing such details from multi-view video recordings. Given a stream of synchronized video images that record a human performance from multiple viewpoints and an articulated template of the performer, our system captures the motion of both the skeleton and the shape. The output mesh animation is enhanced with the details observed in the image silhouettes. For example, a performance in casual loose-fitting clothes will generate mesh animations with flowing garment motions. We accomplish this with a fast pose tracking method followed by nonrigid deformation of the template to fit the silhouettes. The entire process takes less than sixteen seconds per frame and requires no markers or texture cues. Captured meshes are in full correspondence making them readily usable for editing operations including texturing, deformation transfer, and deformation model learning.

Animating an articulated 3D character currently requires manual rigging to specify its internal skeletal structure and to define how the input motion deforms its surface. We present a method for animating characters automatically. Given a static character mesh and a generic skeleton, our method adapts the skeleton to the character and attaches it to the surface, allowing skeletal motion data to animate the character. Because a single skeleton can be used with a wide range of characters, our method, in conjunction with a library of motions for a few skeletons, enables a user-friendly animation system for novices and children. Our prototype implementation, called Pinocchio, typically takes under a minute to rig a character on a modern midrange PC.

We consider a general model for representing and manipulating parametric curves, in which a curve is specified by a black box mapping a parameter value between 0 and 1 to a point in Euclidean d-space. In this model, we consider the nearest-point-on-curve and farthest-point-on-curve problems: given a curve C and a point p, find a point on C nearest to p or farthest from p. In the general black-box model, no algorithm can solve these problems. Assuming a known bound on the speed of the curve (a Lipschitz condition),the answer can be estimated up to an additive error of ε using O(1/ε) samples, and this bound is tight in theworst case. However, many instances can be solved with substantially fewer samples, and we give algorithms that adapt to the inherent difficulty of the particular instance, up to a logarithmic factor. More precisely, if OPT(C,p,ε)is the minimum number of samples of C that every correct algorithm must perform to achieve tolerance ε, then our algorithm performs O(OPT(C,p,ε)log(ε-1/OPT(C,p,ε))) samples. Furthermore, any algorithm requires Ω(klog(ε-1/k))samples for some instance C' with OPT(C',p,ε) = k; except that, for the nearest-point-on-curve problem when the distance between C and p is less than ε, OPT is 1 but the upper and lower bounds on the number of samples are both Θ(1/ε). When bounds on relative error are desired, we give algorithms that perform O(OPT log(2+(1+ε-1)) m-1/OPT))samples (where m is the exact minimum or maximum distance from p to C) and prove that Ω(OPT log(1/ε)) samples are necessary on some problem instances.