Ray tracing is a computationally intensive rendering technique traditionally used in offline high-quality rendering. Powerful hardware accelerators have been recently developed which put real-time ray tracing even in the reach of mobile devices. However, rendering animated scenes remains difficult, as updating the acceleration trees for each frame is a memory-intensive process. This article proposes MergeTree, the first hardware architecture for Hierarchial Linear Bounding Volume Hierarchy (HLBVH) construction, designed to minimize memory traffic. For evaluation, the hardware constructor is synthesized on a 28nm CMOS process technology. Compared to a state-of-the-art binned SAH builder, the present work speeds up construction by a factor of 5, reduces build energy by a factor of 3.2, and memory traffic by a factor of 3. A software HLBVH builder on GPU requires 3.3 times more memory traffic. In order to take tree quality into account, a rendering accelerator is modeled alongside the builder. Given the use of a toplevel build to improve tree quality, the proposed builder reduces system energy per frame by an average 41% with primary rays and 13% with diffuse rays. In large (> 500K triangles) scenes, the difference is more pronounced, 62% and 35%, respectively.
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.
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.
T-junctions support merging or spreading out feature lines. This paper develops a new way to create smooth piecewise polynomial free-form spline surfaces that include T-junctions. The construction of caps smoothly extending bicubic splines across T-junctions is based on varying the parameterization. It does not require the global coordination of knot intervals and therefore applies to meshes with T-junctions that do not admit a smooth hierarchical or T-spline parameterization. A T-junction cap consists of patches of degree bi-4, framed by bi-3 patches. Numerous experiments show that the constructions yield good highlight line distribution where alternatives, such as Catmull-Clark subdivision, fail to preserve monotonicity, and hierarchical spline parameterizations cannot be C1.
Sampling is a core component of many applications including: imaging, rendering, geometry processing and visualization. Prior research has primarily focused on blue noise sampling with a single class of samples. Limited research has been done on multi-class sampling. Multi-class blue noise sampling is still a challenging problem when the density distribution of every class is non-uniform and different from each other. In this paper, we present a Wasserstein blue noise sampling algorithm for multi-class sampling by throwing samples as the Wasserstein barycenter of multiple density distributions. We employ a more general representation of the optimal transport problem to break up the partition necessary in other optimal sampling. Moreover, an adaptive blue noise distribution property for every individual class is guaranteed, as well as their combined class. The sampling efficiency is also improved by applying the Wasserstein distance with entropic constraints. Our method can be applied to multi-class sampling on the point set surface. We also demonstrate applications in object distribution and color stippling.
We present a new local descriptor for 3D shapes, directly applicable to a wide range of shape analysis problems such as point correspondences, semantic segmentation, affordance prediction, and shape-to-scan matching. The descriptor is produced by a convolutional network that is trained to embed geometrically and semantically similar points close to one another in descriptor space. The network processes surface neighborhoods around points on a shape that are captured at multiple scales by a succession of progressively zoomed out views, taken from carefully selected camera positions. We leverage two extremely large sources of data to train our network. First, since our network processes rendered views in the form of 2D images, we repurpose architectures pre-trained on massive image datasets. Second, we automatically generate a synthetic dense correspondence dataset by part-aware, non-rigid alignment of a massive collection of 3D models. As a result of these design choices, our network effectively encodes multi-scale local context and fine-grained surface detail. We demonstrate through several experiments that our learned local descriptors are more discriminative compared to state of the art alternatives, and are effective in a variety of shape analysis applications.
We study Markov Chain Monte Carlo (MCMC) methods operating in primary sample space and their interactions with multiple sampling techniques. We observe that incorporating the sampling technique into the state of the Markov Chain, as done in Multiplexed Metropolis Light Transport (MMLT), impedes the ability of the chain to properly explore path space, as transitions between sampling techniques lead to disruptive alterations of path samples. To address this issue, we reformulate Multiplexed MLT in the Reversible Jump MCMC framework (RJMCMC) and introduce inverse sampling techniques that turn light paths into the random numbers that produce them. This allows us to formulate a novel perturbation that can locally transition between sampling techniques, and we derive the correct acceptance probability using RJMCMC. We investigate how to generalize this concept to non-invertible sampling techniques commonly found in practice, and introduce probabilistic inverses that extend our perturbation to cover most sampling methods found in light transport simulations. Our theory reconciles the inverses with RJMCMC yielding an unbiased algorithm, which we call Reversible Jump MLT (RJMLT). We verify the correctness of our implementation in canonical and practical scenarios and demonstrate improved temporal coherence, decrease in structured artifacts, and faster convergence on a variety of scenes.
We present the first technique to create wide-angle, high-resolution looping panoramic videos. Starting with a 2D grid of registered videos acquired on a robotic mount, we formulate a combinatorial optimization to determine for each output pixel the source video and looping parameters that jointly maximize spatiotemporal consistency. This optimization is accelerated by reducing the set of source labels using a graph-coloring scheme. We parallelize the computation and implement it out-of-core by partitioning the domain along low-importance paths. The merged panorama is assembled using gradient-domain blending and stored as a hierarchy of video tiles. Finally, an interactive viewer adaptively preloads these tiles for responsive browsing and allows the user to interactively edit and improve local regions. We demonstrate these techniques on gigapixel-sized looping panoramas.
We present a fast, novel image-based technique, for reverse engineering the Bidirectional Texture Function (BTF) of woven fabrics. In order to recover our models, we estimate a depth map and a set of yarn parameters (yarn width, yarn crossovers and so on) from spatial and frequency domain cues. We solve for the woven fabric pattern, and from this build a volumetric data set. We use a combination of image space analysis, frequency domain analysis and in challenging cases match image statistics with those from previously captured known patterns. Our method determines, from a single digital image, the woven cloth structure, depth and albedo, thus removing the need for separately measured depth data. The focus of this work is on the rapid acquisition of woven cloth structure and therefore we use standard approaches to render the results. Our pipeline first estimates the weave pattern, yarn characteristics, albedo and noise statistics using a novel combination of low level image processing and Fourier Analysis. Next, we estimate a depth map for the fabric sample using a first order Markov chain and our estimated noise model as input. A volumetric BTF model is constructed from the recovered depth and albedo maps.
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.
Many graphics and vision problems are naturally expressed as optimizations with either linear or non-linear least squares objective functions over visual data, such as images and meshes. The mathematical descriptions of these functions are extremely concise, but their implementation in real code is tedious, especially when optimized for real-time performance in interactive applications. We propose a new language, Opt in which a user simply writes energy functions over image- or graph-structured unknowns, and a compiler automatically generates state-of-the-art GPU optimization kernels. The end result is a system in which real-world energy functions in graphics and vision applications are expressible in tens of lines of code. They compile directly into highly-optimized GPU solver implementations with performance competitive with the best published hand-tuned, application-specific GPU solvers, and 1--2 orders of magnitude beyond a general-purpose auto-generated solver.
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.