Matt's Webcorner

Abstract: We present a method for synthesizing 3D object arrangements from examples. Our algorithm can synthesize a diverse set of plausible new scenes given only a few examples and requires no additional inputs from the user. These capabilities are enabled by three novel contributions. First, we introduce a probabilistic model for scenes based on Bayesian networks and Gaussian mixtures that can be trained from a small number of input examples. Second, we develop a clustering algorithm that groups objects occurring in a database of scenes according to their local scene neighborhoods. These contextual categories allow the synthesis process to treat a wider variety of objects as interchangeable. Third, we train our probabilistic model on a mix of user-provided examples and relevant scenes retrieved from the database. This mixed model learning process can be controlled to introduce additional variety into the synthesized scenes. We evaluate our algorithm through qualitative results and a perceptual study in which participants judged synthesized scenes to be highly plausible, as compared to hand-created scenes.

Abstract: Patterns with pleasing structure are common in art, video games, and virtual worlds. We describe a method for synthesizing new patterns of tiles on a regular grid that are similar in appearance to a set of example patterns. Exemplars are used both to specify valid tile arrangements and to emphasize multi-tile structures. We model a pattern as a probabilistic graphical model called a factor graph. Factors represent the hard logical constraints between tiles, the soft statistical relationships that determine style, and the local dependencies between tiles at neighboring sites. We describe a simple method for learning factor functions from a small exemplar. We then synthesize new patterns through a stochastic search method that is inspired by MC-SAT. Efficient synthesis is challenging because of the combination of hard and soft constraints. Our synthesis algorithm, called BLOCKSS, scales linearly with the number of tiles and the hardness of the problem. We use our technique to model building facades, cities, and decorative patterns.

Abstract: Modeling virtual environments is a time consuming and expensive task that is becoming increasingly popular for both professional and casual artists. The model density and complexity of the scenes representing these virtual environments is rising rapidly. This trend suggests that data-mining a 3D scene corpus to facilitate collaborative content creation could be a very powerful tool enabling more efficient scene design. In this paper, we show how to represent scenes as graphs that encode models and their semantic relationships. We then define a kernel between these relationship graphs that compares common virtual substructures in two graphs and captures the similarity between their corresponding scenes. We apply this framework to several scene modeling problems, such as finding similar scenes, relevance feedback, and context-based model search. We show that incorporating structural relationships allows our method to provide a more relevant set of results when compared against previous approaches to model context search.

Abstract: Large corpora of 3D models, such as Google 3D Warehouse, are now becoming available on the web. It is possible to search these databases using a keyword search. This makes it possible for designers to easily include existing content into new scenes. In this paper, we describe a method for context-based search of 3D scenes. We first downloaded a large set of scene graphs from Google 3D Warehouse. These scene graphs were segmented into individual objects. We also extracted tags from the names of the models. Given the object shape, tags, and spatial relationship between pairs of objects, we can predict the strength of a relationship between a candidate model and an existing object in the scene. Using this function, we can perform context-based queries. The user specifies a region in the scene they are modeling using a 3D bounding box, and the system returns a list of related objects. We show that context-based queries perform better than keyword queries alone, and that without any keywords our algorithm still returns a relevant set of models.

Abstract: We present DiagSplit, a highly parallel algorithm for adaptively tessellating displaced parametric surfaces into high-quality, crack free micropolygon meshes. DiagSplit modifies the split-dice tessellation algorithm to make splits using non-isoparametric cuts in the surface's parametric domain, and uses a dicing scheme that supports unique tessellation factors for each subpatch edge. Splitting and edge tessellation factor computations use only information local to subpatch edges. These modifications allow all subpatches generated by DiagSplit to be processed independently without introducing T-junctions or mesh cracks and without incurring the tessellation overhead of binary dicing. We demonstrate that DiagSplit produces output that is better (in terms of image quality and number of micropolygons produced) than existing parallel tessellation schemes, and as good as highly adaptive, but hard to parallelize, split-dice implementations.

Abstract: Tangent vector fields are an essential ingredient in controlling surface appearance for applications ranging from anisotropic shading to texture synthesis and non-photorealistic rendering. To achieve a desired effect one is typically interested in smoothly varying fields that satisfy a sparse set of user-provided constraints. Using tools from Discrete Exterior Calculus, we present a simple and efficient algorithm for designing such fields over arbitrary triangle meshes. By representing the field as scalars over mesh edges (i.e., discrete 1-forms), we obtain an intrinsic, coordinate-free formulation in which field smoothness is enforced through discrete Laplace operators. Unlike previous methods, such a formulation leads to a linear system whose sparsity permits efficient pre-factorization. Constraints are incorporated through weighted least squares and can be updated rapidly enough to enable interactive design, as we demonstrate in the context of anisotropic texture synthesis.

Abstract: The discrete Laplace-Beltrami operator plays a prominent role in many Digital Geometry Processing applications ranging from denoising to parameterization, editing, and physical simulation. The standard discretization uses the cotangents of the angles in the immersed mesh which leads to a variety of numerical problems. We advocate use of the intrinsic Laplace-Beltrami operator. It satisfies a local maximum principle, guaranteeing, e.g., that no flipped triangles can occur in parameterizations. It also leads to better conditioned linear systems. The intrinsic Laplace-Beltrami operator is based on an intrinsic Delaunay triangulation of the surface. We give an incremental algorithm to construct such triangulations together with an overlay structure which captures the relationship between the extrinsic and intrinsic triangulations. Using a variety of example meshes we demonstrate the numerical benefits of the intrinsic Laplace-Beltrami operator.

Abstract: We present an algorithm for geometric mapping from range scans captured over significant spatial extents and augmented with calibrated images. Because the input range scans and images are taken over a large area in complex environments, significant errors may be introduced during their calibration and we present several techniques to account for this. The output is a textured mesh that can then answer location queries given input images taken in the scanned area. In the query phase, we use a hidden markov model to localize a camera in the scanned environment by matching it against the geometric map. We present the results of our work on a dataset gathered in a very cluttered environment.

Abstract: Establishing corresponding regions between two surfaces is an important part of many problems in surface registration, reconstruction, medical imaging, and object recognition. We present a method that uses diffusion to propagate local feature descriptors across a surface to create a robust signature which can be used for similarity comparisons at varying scales. To collect the local signatures around a point we use an oriented grid which we search using an approximate nearest neighbor search algorithm. We use this method to compute a dense set of correspondences between two surfaces that conveys both point and local rigid coordinate frame matches. We present several techniques for aggressively pruning these correspondences to keep only those that are consistent over significant regions.