Approximate Program Smoothing Using Mean‐Variance Statistics,with Application to Procedural Shader Bandlimiting

We introduce a general method to approximate the convolution of a program with a Gaussian kernel. This results in the program being smoothed. Our compiler framework models intermediate values in the program as random variables, by using mean and variance statistics. We decompose the input program into atomic parts and relate the statistics of the different parts of the smoothed program. We give several approximate smoothing rules that can be used for the parts of the program. These include an improved variant of Dorn et al. [ DBLW15 ], a novel adaptive Gaussian approximation, Monte Carlo sampling, and compactly supported kernels. Our adaptive Gaussian approximation handles multivariate Gaussian distributed inputs, gives exact results for a larger class of programs than previous work, and is accurate to the second order in the standard deviation of the kernel for programs with certain analytic properties. Because each expression in the program can have multiple approximation choices, we use a genetic search to automatically select the best approximations. We apply this framework to the problem of automatically bandlimiting procedural shader programs. We evaluate our method on a variety of geometries and complex shaders, including shaders with parallax mapping, animation, and spatially varying statistics. The resulting smoothed shader programs outperform previous approaches both numerically and aesthetically.     

Procedural Modeling of a Building from a Single Image

Creating a virtual city is demanded for computer games, movies, and urban planning, but it takes a lot of time to create numerous 3D building models. Procedural modeling has become popular in recent years to overcome this issue, but creating a grammar to get a desired output is difficult and time consuming even for expert users. In this paper, we present an interactive tool that allows users to automatically generate such a grammar from a single image of a building. The user selects a photograph and highlights the silhouette of the target building as input to our method. Our pipeline automatically generates the building components, from large‐scale building mass to fine‐scale windows and doors geometry. Each stage of our pipeline combines convolutional neural networks (CNNs) and optimization to select and parameterize procedural grammars that reproduce the building elements of the picture. In the first stage, our method jointly estimates camera parameters and building mass shape. Once known, the building mass enables the rectification of the façades, which are given as input to the second stage that recovers the façade layout. This layout allows us to extract individual windows and doors that are subsequently fed to the last stage of the pipeline that selects procedural grammars for windows and doors. Finally, the grammars are combined to generate a complete procedural building as output. We devise a common methodology to make each stage of this pipeline tractable. This methodology consists in simplifying the input image to match the visual appearance of synthetic training data, and in using optimization to refine the parameters estimated by CNNs. We used our method to generate a variety of procedural models of buildings from existing photographs.     

Identifying Objects in Procedural Programs Using Clustering Neural Networks

This paper presents a general approach for the identification of objects in procedural programs. The approach is based on neural architectures that perform an unsupervised learning of clusters. We describe two such neural architectures, explain how to use them in identifying objects in software systems and briefly describe a prototype tool, which implements the clustering algorithms. With the aid of several examples, we explain how our approach can identify abstract data types as well as groups of routines which reference a common set of data. The clustering results are compared to the results of many other object identification techniques. Finally, several case studies were performed on existing programs to evaluate the object identification approach. Results concerning two representative programs and their generated clusters are discussed.     

Compositional verification of sequential programs with procedures

We present a method for algorithmic, compositional verification of control-flow-based safety properties of sequential programs with procedures. The application of the method involves three steps: (1) decomposing the desired global property into local properties of the components, (2) proving the correctness of the property decomposition by using a maximal model construction, and (3) verifying that the component implementations obey their local specifications. We consider safety properties of both the structure and the behaviour of program control flow. Our compositional verification method builds on a technique proposed by Grumberg and Long that uses maximal models to reduce compositional verification of finite-state parallel processes to standard model checking. We present a novel maximal model construction for the fragment of the modal μ-calculus with boxes and greatest fixed points only, and adapt it to control-flow graphs modelling components described in a sequential procedural language. We extend our verification method to programs with private procedures by defining an abstraction, presented as an inlining transformation. All algorithms have been implemented in a tool set automating all required verification steps. We validate our approach on an electronic purse case study.     

Learning Fuzzy Set Representations of Partial Shapes on Dual Embedding Spaces

Modeling relations between components of 3D objects is essential for many geometry editing tasks. Existing techniques commonly rely on labeled components, which requires substantial annotation effort and limits components to a dictionary of predefined semantic parts. We propose a novel framework based on neural networks that analyzes an uncurated collection of 3D models from the same category and learns two important types of semantic relations among full and partial shapes: complementarity and interchangeability. The former helps to identify which two partial shapes make a complete plausible object, and the latter indicates that interchanging two partial shapes from different objects preserves the object plausibility. Our key idea is to jointly encode both relations by embedding partial shapes as fuzzy sets in dual embedding spaces. We model these two relations as fuzzy set operations performed across the dual embedding spaces, and within each space, respectively. We demonstrate the utility of our method for various retrieval tasks that are commonly needed in geometric modeling interfaces.     

Local Editing of Procedural Models

Procedural modeling is used across many industries for rapid 3D content creation. However, professional procedural tools often lack artistic control, requiring manual edits on baked results, diminishing the advantages of a procedural modeling pipeline. Previous approaches to enable local artistic control require special annotations of the procedural system and manual exploration of potential edit locations. Therefore, we propose a novel approach to discover meaningful and non‐redundant good edit locations (GELs). We introduce a bottom‐up algorithm for finding GELs directly from the attributes in procedural models, without special annotations. To make attribute edits at GELs persistent, we analyze their local spatial context and construct a meta‐locator to uniquely specify their structure. Meta‐locators are calculated independently per attribute, making them robust against changes in the procedural system. Functions on meta‐locators enable intuitive and robust multi‐selections. Finally, we introduce an algorithm to transfer meta‐locators to a different procedural model. We show that our approach greatly simplifies the exploration of the local edit space, and we demonstrate its usefulness in a user study and multiple real‐world examples.     

Packing Irregular Objects in 3D Space via Hybrid Optimization

Packing problems arise in a wide variety of practical applications. The basic problem is that of placing as many objects as possible in a non‐overlapping configuration within a given container. Problems involving irregular shapes are the most challenging cases. In this paper, we consider the most general forms of irregular shape packing problems in 3D space, where both the containers and the objects can be of any shapes, and free rotations of the objects are allowed. We propose a heuristic method for efficiently packing irregular objects by combining continuous optimization and combinatorial optimization. Starting from an initial placement of an appropriate number of objects, we optimize the positions and orientations of the objects using continuous optimization. In combinatorial optimization, we further reduce the gaps between objects by swapping and replacing the deployed objects and inserting new objects. We demonstrate the efficacy of our method with experiments and comparisons.     

Sparse representation of terrains for procedural modeling

In this paper, we present a simple and efficient method to represent terrains as elevation functions built from linear combinations of landform features (atoms). These features can be extracted either from real world data‐sets or procedural primitives, or from any combination of multiple terrain models. Our approach consists in representing the elevation function as a sparse combination of primitives, a concept which we call Sparse Construction Tree, which blends the different landform features stored in a dictionary. The sparse representation allows us to represent complex terrains using combinations of atoms from a small dictionary, yielding a powerful and compact terrain representation and synthesis tool. Moreover, we present a method for automatically learning the dictionary and generating the Sparse Construction Tree model. We demonstrate the efficiency of our method in several applications: inverse procedural modeling of terrains, terrain amplification and synthesis from a coarse sketch.     

Fiber‐Level On‐the‐Fly Procedural Textiles

Procedural textile models are compact, easy to edit, and can achieve state‐of‐the‐art realism with fiber‐level details. However, these complex models generally need to be fully instantiated (aka. realized ) into 3D volumes or fiber meshes and stored in memory, We introduce a novel realization‐minimizing technique that enables physically based rendering of procedural textiles, without the need of full model realizations. The key ingredients of our technique are new data structures and search algorithms that look up regular and flyaway fibers on the fly, efficiently and consistently. Our technique works with compact fiber‐level procedural yarn models in their exact form with no approximation imposed. In practice, our method can render very large models that are practically unrenderable using existing methods, while using considerably less memory (60–200× less) and achieving good performance.     

The Specification of Assemblers

The problem of applying formal techniques of program specification and verification to large complex programs is considered. It is argued that a practical solution requires a variety of techniques, including both procedural and nonprocedural specifications, hierarchical program organization, and the use of program transformations. In particular, a case is made for flexible problem-oriented choice of specification techniques and languages. These ideas are expanded by specifying a load-and-go assembler in three parts: a transduction grammar describing the correspondence between concrete and abstract syntax for assembly language programs; a set of transformations of the abstract form; and a nonconstructive axiomatic specification of the result of core assembly and loading of transformed abstract programs.     

Accurate Synthesis of Multi‐Class Disk Distributions

While analysing and synthesising 2D distributions of points has been applied both to the generation of textures with discrete elements and for populating virtual worlds with 3D objects, the results are often inaccurate since the spatial extent of objects cannot be expressed. We introduce three improvements enabling the synthesis of more general distributions of elements. First, we extend continuous pair correlation function (PCF) algorithms to multi‐class distributions using a dependency graph, thereby capturing interrelationships between distinct categories of objects. Second, we introduce a new normalised metric for disks, which makes the method applicable to both point and possibly overlapping disk distributions. The metric is specifically designed to distinguish perceptually salient features, such as disjoint, tangent, overlapping, or nested disks. Finally, we pay particular attention to convergence of the mean PCF as well as the validity of individual PCFs, by taking into consideration the variance of the input. Our results demonstrate that this framework can capture and reproduce real‐life distributions of elements representing a variety of complex semi‐structured patterns, from the interaction between trees and the understorey in a forest to droplets of water. More generally, it applies to any category of 2D object whose shape is better represented by bounding circles than points.     

Using simplified geometric models in skill-based manipulation

Dexterous manipulation plays an important role in working robots. Manipulator tasks such as assembly and disassembly can generally be divided into several motion primitives. We call these 'skills' and explain how most manipulator tasks can be composed of skill sequences. Skills are also used to compensate for errors both in the geometric model and in manipulator motions. There are dispensable data in the shapes, positions and orientations of objects when achieving skill motions in a task. Therefore, we can simplify geometric models by considering the dispensable data in a skill motion. We call such robust and simplified models 'false models'. This paper describes our definition of false models used in planning and visual sensing, and shows the effectiveness of our method using examples of tasks involving the manipulation of mechanical and electronic parts. Furthermore, we show the application of false models to objects of indefinite sizes and shapes using examples of the same tasks.     

Cable Joints

Robustly and efficiently simulating cables and ropes that are part of a larger system such as cable driven machines, cable cars or tendons in a human or robot is a challenging task. To be able to adapt to the environment, cables are typically modeled as a large number of small segments that are connected via joints. The two main difficulties with this approach are to satisfy the inextensibility constraint and to handle the typically large mass ratio between the small segments and the larger objects they connect. In this paper we present a new approach which solves these problems in a simple and effective way. Our method is based on the idea to simulate the effect of the cables instead of the cables themselves. To this end we propose a new special type of distance constraint we call cable joint that changes both its attachment points and its rest length dynamically. A cable connecting a series of objects is then modeled as a sequence of cable joints which reduces the complexity of the simulation from the order of the number of segments to just the number of connected objects. This makes simulations both faster and more robust as we will demonstrate on a variety of examples.     

Expressing checkable properties of dynamic systems: the Bandera Specification Language

Research on how to reason about correctness properties of software systems using model checking is advancing rapidly. Work on extracting finite-state models from program source code and on abstracting those models is focused on enabling the tractable checking of program properties such as freedom from deadlock and assertion violations. For the most part, the problem of specifying more general program properties has not been considered. In this paper, we report on the support for specifying properties of dynamic multi-threaded Java programs that we have built into the Bandera system. Bandera extracts finite-state models, in the input format of several existing model checkers, from Java code based on the property to be checked. The Bandera Specification Language (BSL) provides a language for defining general assertions and pre/post conditions on methods. It also supports the definition of observations that can be made of the state of program objects and the incorporation of those observations as predicates that can be instantiated in the scope of object quantifiers and used in describing common forms of state/event sequencing properties. We illustrate how BSL can be used to formulate a variety of system correctness properties for several multi-threaded Java applications. Published online: 2 October 2002     

Deep Video‐Based Performance Synthesis from Sparse Multi‐View Capture

We present a deep learning based technique that enables novel‐view videos of human performances to be synthesized from sparse multi‐view captures. While performance capturing from a sparse set of videos has received significant attention, there has been relatively less progress which is about non‐rigid objects (e.g., human bodies). The rich articulation modes of human body make it rather challenging to synthesize and interpolate the model well. To address this problem, we propose a novel deep learning based framework that directly predicts novel‐view videos of human performances without explicit 3D reconstruction. Our method is a composition of two steps: novel‐view prediction and detail enhancement. We first learn a novel deep generative query network for view prediction. We synthesize novel‐view performances from a sparse set of just five or less camera videos. Then, we use a new generative adversarial network to enhance fine‐scale details of the first step results. This opens up the possibility of high‐quality low‐cost video‐based performance synthesis, which is gaining popularity for VA and AR applications. We demonstrate a variety of promising results, where our method is able to synthesis more robust and accurate performances than existing state‐of‐the‐art approaches when only sparse views are available.     

Symmetric structure in logic programming

It is argued that some symmetric structure in logic programs could be taken into account when implementing semantics in logic programming. This may enhance the declarative ability or expressive power of the semantics. The work presented here may be seen as representative examples along this line. The focus is on the derivation of negative information and some other classic semantic issues. We first define a permutation group associated with a given logic program. Since usually the canonical models used to reflect the common sense or intended meaning are minimal or completed models of the program, we expose the relationships between minimal models and completed models of the original program and its so-called G-reduced form newly-derived via the permutation group defined. By means of this G-reduced form, we introduce a rule to assume negative information termed G-CWA, which is actually a generalization of the GCWA. We also develop the notions of G-definite, G-hierarchical and G-stratified logic programs,     

Learning goal hierarchies from structured observations and expert annotations

We describe a relational learning by observation framework that automatically creates cognitive agent programs that model expert task performance in complex dynamic domains. Our framework uses observed behavior and goal annotations of an expert as the primary input, interprets them in the context of background knowledge, and returns an agent program that behaves similar to the expert. We map the problem of creating an agent program on to multiple learning problems that can be represented in a “supervised concept learning’’ setting. The acquired procedural knowledge is partitioned into a hierarchy of goals and represented with first order rules. Using an inductive logic programming (ILP) learning component allows our framework to naturally combine structured behavior observations, parametric and hierarchical goal annotations, and complex background knowledge. To deal with the large domains we consider, we have developed an efficient mechanism for storing and retrieving structured behavior data. We have tested our approach using artificially created examples and behavior observation traces generated by AI agents. We evaluate the learned rules by comparing them to hand-coded rules. Editor: Rui Camacho