Sketching in Gestalt Space: Interactive Shape Abstraction through Perceptual Reasoning

We present an interactive method that allows users to easily abstract complex 3D models with only a few strokes. The key idea is to employ well‐known Gestalt principles to help generalizing user inputs into a full model abstraction while accounting for form, perceptual patterns and semantics of the model. Using these principles, we alleviate the user's need to explicitly define shape abstractions. We utilize structural characteristics such as repetitions, regularity and similarity to transform user strokes into full 3D abstractions. As the user sketches over shape elements, we identify Gestalt groups and later abstract them to maintain their structural meaning. Unlike previous approaches, we operate directly on the geometric elements, in a sense applying Gestalt principles in 3D. We demonstrate the effectiveness of our approach with a series of experiments, including a variety of complex models and two extensive user studies to evaluate our framework.     

Constructing predicate mappings for goal-dependent abstraction

In theorem proving with abstraction, it is required for system designers to provide a useful abstraction. However, such a task is so difficult that it would be worth studying an automatic construction of abstraction. In this paper, we propose a new framework of Goal-Dependent Abstraction in which an appropriate abstraction is selected according to each goal to be proved. Towards Goal-Dependent Abstraction, we present an algorithm for constructing an appropriate abstraction for a given goal. The appropriateness is defined in terms of Upward-Property and Downward-Property. Since our abstraction is based on predicate mapping, the algorithm in fact computes predicate mappings based on which appropriate abstractions can be constructed. Given a goal, candidate predicate mappings are generated and then tested for their appropriateness for the goal. In order to find appropriate mappings efficiently, we present a property to prune useless candidate generations. The numbers of pruned candidates are evaluated in the best and worst cases. Furthermore some experimental results show that many useless candidates can be pruned with the property and the obtained appropriate predicate mappings (abstractions) fit our intuition. From the experimental results, we could expect our study in this paper to contribute to the fields of analogical reasoning and case-based reasoning as well as theorem-proving. This revised version was published online in June 2006 with corrections to the Cover Date.     

Interactive design of 2D car profiles with aerodynamic feedback

The design of car shapes requires a delicate balance between aesthetic and performance. While fluid simulation provides the means to evaluate the aerodynamic performance of a given shape, its computational cost hinders its usage during the early explorative phases of design, when aesthetic is decided upon. We present an interactive system to assist designers in creating aerodynamic car profiles. Our system relies on a neural surrogate model to predict fluid flow around car shapes, providing fluid visualization and shape optimization feedback to designers as soon as they sketch a car profile. Compared to prior work that focused on time-averaged fluid flows, we describe how to train our model on instantaneous, synchronized observations extracted from multiple pre-computed simulations, such that we can visualize and optimize for dynamic flow features, such as vortices. Furthermore, we architectured our model to support gradient-based shape optimization within a learned latent space of car profiles. In addition to regularizing the optimization process, this latent space and an associated encoder-decoder allows us to input and output car profiles in a bitmap form, without any explicit parameterization of the car boundary. Finally, we designed our model to support pointwise queries of fluid properties around car shapes, allowing us to adapt computational cost to application needs. As an illustration, we only query our model along streamlines for flow visualization, we query it in the vicinity of the car for drag optimization, and we query it behind the car for vortex attenuation.     

Conceptual design, manufacturability evaluation and preliminary process planning using function-form relationships in stamped metal parts

A large number of design decisions are made during the conceptual design of a part. However, there are few representation and reasoning tools for decision support during conceptual design. The conceptual design stage is characterized by a lack of complete geometric information. Existing geometric modelers require complete geometric information, while a functional reasoning methodology using a <verb, noun > representation is typically too terse. In this paper, we present a new representation called sketching abstraction for conceptual design, using the function-form relations in a design. The functionally critical part of the geometry is presented using a set of functional features, while the rest of the geometry is abstracted as a set of linkages. Part functionality is correlated with the sketching abstraction using data structures called function-form matrices. The sketching abstraction is annotated using a set of primitives, and a set of grammar rules are used to extract canonical relationships between the functional features. The sketching abstraction can be used for extracting designs that are geometrically dissimilar but functionally similar, thus providing the designer with ideas for design alternatives. The sketching abstraction can also be used to carry out domain-dependent manufacturability evaluation checks. A further use of sketching abstractions is to initiate the development of a process plan for manufacturing. Sketching abstractions are related to the solid model of a part. Thus, this representation provides a link between pure functional and pure geometric representations. The domain of application is stamped metal parts. We present the part functionality and the features used in this domain. We also illustrate the use of sketching abstractions for conceptual design, manufacturability evaluation and preliminary process planning.     

Direct shape optimization for strengthening 3D printable objects

Recently there has been an increasing demand for software that can help designers create functional 3D objects with required physical strength. We introduce a generic and extensible method that directly optimizes a shape subject to physical and geometric constraints. Given an input shape, our method optimizes directly its input mesh representation until it can withstand specified external forces, while remaining similar to the original shape. Our method performs physics simulation and shape optimization together in a unified framework, where the physics simulator is an integral part of the optimizer. We employ geometric constraints to preserve surface details and shape symmetry, and adapt a second‐order method with analytic gradients to improve convergence and computation time. Our method provides several advantages over previous work, including the ability to handle general shape deformations, preservation of surface details, and incorporation of user‐defined constraints. We demonstrate the effectiveness of our method on a variety of prinTable 3D objects through detailed simulations as well as physical validations.     

Knowledge-based spatiotemporal linear abstraction

We present a theoretical framework and a case study for reusing the same conceptual and computational methodology for both temporal abstraction and linear (unidimensional) space abstraction, in a domain (evaluation of traffic-control actions) significantly different from the one (clinical medicine) in which the method was originally used. The method, known asknowledge-based temporal abstraction, abstracts high-level concepts and patterns from time-stamped raw data using a formal theory of domain-specific temporal-abstraction knowledge. We applied this method, originally used to interpret time-oriented clinical data, to the domain of traffic control, in which the monitoring task requires linear pattern matching along both space and time. First we reused the method for creation of unidimensional spatial abstractions over highways, given sensor measurements along each highway measured at the same time point. Second, we reused the method to create temporal abstractions of the traffic behaviour, for the same space segments, but during consecutive time points. We defined the corresponding temporal-abstraction and spatial-abstraction domain-specific knowledge. Our results suggest that (1) the knowledge-base temporal-abstraction method is reusable over time and unidimensional space as well as over significantly different domains; (2) the method can be generalised into a knowledge-based linear-abstraction method, which solves tasks requiring abstraction of data along any linear distance measure; and (3) a spatiotemporal-abstraction method can be assembled, from two copies of the generalised method and a spatial-decomposition mechanism, and is applicable to tasks requiring abstraction of time-oriented data into meaningful spatiotemporal patterns over a linear, decomposable space, such as traffic over a set of highways.     

Abstraction as a means for end-user computing in creative applications

End-user computing is needed in creative artistic applications or integrated editing environments, where the activity cannot be planned in advance. Following the paper by Orlarey et al., concrete abstractions (abstractions from examples) are suggested as a new mode for function definition, appropriate for end-user editor programmability. For certain applications, the direct, associative, not planned in advance character of concrete abstraction plays a qualitative role in the mere ability to specify abstractions. In this paper, we propose to use concrete abstraction as a general tool for end-user programmability in editors. We distinguish two kinds of abstractions: value abstraction and structure abstraction, and explain how they can be combined. We describe a framework of historical editing that is based on a double view, in which the two abstraction kinds are combined. Finally, BOOMS, an implemented prototype for such an editing framework, is described. BOOMS is a domain-independent toolkit, with three sample instantiations. We believe that the proposed framework captures the conceptualization operation that characterizes creative, associative work types and addresses the needs for end-user computing in integrated environments.     

The impact of distributed programming abstractions on application energy consumption

With battery capacities remaining a key physical constraint for mobile devices, energy efficiency has become an important software design consideration. Distributed programming abstractions (e.g., sockets, RPC, messages, etc.) are an essential component of modern software, but their energy consumption characteristics are poorly understood. The programmer has few practical guidelines to choose the right abstraction for energy-constrained scenarios. In this article, we report on the findings of a systematic study we conducted to compare and contrast major distributed programming abstractions in terms of their energy consumption patterns. By varying the abstractions with the rest of the functionality fixed, we measure and analyze the impact of distributed programming abstractions on application energy consumption. Based on our findings, we present a set of practical guidelines for the programmer to select an abstraction that satisfies the energy consumption constraints in place. Our other guidelines can steer future efforts in creating energy efficient distributed programming abstractions.     

Abstraction-guided synthesis of synchronization

We present a novel framework for automatic inference of efficient synchronization in concurrent programs, a task known to be difficult and error-prone when done manually. Our framework is based on abstract interpretation and can infer synchronization for infinite state programs. Given a program, a specification, and an abstraction, we infer synchronization that avoids all (abstract) interleavings that may violate the specification, but permits as many valid interleavings as possible. Combined with abstraction refinement, our framework can be viewed as a new approach for verification where both the program and the abstraction can be modified on-the-fly during the verification process. The ability to modify the program, and not only the abstraction, allows us to remove program interleavings not only when they are known to be invalid, but also when they cannot be verified using the given abstraction. We implemented a prototype of our approach using numerical abstractions and applied it to verify several example programs.     

SketchSoup: Exploratory Ideation Using Design Sketches

A hallmark of early stage design is a number of quick‐and‐dirty sketches capturing design inspirations, model variations and alternate viewpoints of a visual concept. We present SketchSoup, a workflow that allows designers to explore the design space induced by such sketches. We take an unstructured collection of drawings as input, along with a small number of user‐provided correspondences as input. We register them using a multi‐image matching algorithm, and present them as a 2D interpolation space. By morphing sketches in this space, our approach produces plausible visualizations of shape and viewpoint variations despite the presence of sketch distortions that would prevent standard camera calibration and 3D reconstruction. In addition, our interpolated sketches can serve as inspiration for further drawings, which feed back into the design space as additional image inputs. SketchSoup thus fills a significant gap in the early ideation stage of conceptual design by allowing designers to make better informed choices before proceeding to more expensive 3D modelling and prototyping. From a technical standpoint, we describe an end‐to‐end system that judiciously combines and adapts various image processing techniques to the drawing domain—where the images are dominated not by colour, shading and texture, but by sketchy stroke contours.     

Table design in dynamic programming

Dynamic Programming solves combinatorial optimization problems by recursive decomposition and tabulation of intermediate results. The first step in the design of a dynamic programming algorithm is to decide on the set of tables that will hold optimal solutions to subproblems. This step predetermines the shape of the dynamic programming recurrences as well as the asymptotic efficiency of the algorithm in time and space. We study dynamic programming in a formal framework where design of tables and problem decomposition can be done independently. Our main result shows that choosing a good table design for a given decomposition is an NP-complete problem. A heuristic or approximate approach is therefore needed to automate good table design. We report on a strategy that combines user annotation and a brute force algorithm, which is shown to perform well in a large application.     

Divergent exploration in design with a dynamic multiobjective optimization formulation

Formulation space exploration is a new strategy for multiobjective optimization that facilitates both divergent exploration and convergent optimization during the early stages of design. The formulation space is the union of all variable and design objective spaces identified by the designer as being valid and pragmatic problem formulations. By extending a computational search into the formulation space, the solution to an optimization problem is no longer predefined by any single problem formulation, as it is with traditional optimization methods. Instead, a designer is free to change, modify, and update design objectives, variables, and constraints and explore design alternatives without requiring a concrete understanding of the design problem a priori. To facilitate this process, we introduce a new vector/matrix-based definition for multiobjective optimization problems, which is dynamic in nature and easily modified. Additionally, we provide a set of exploration metrics to help guide designers while exploring the formulation space. Finally, we provide an example to illustrate the use of this new, dynamic approach to multiobjective optimization.     

Constrained space deformation techniques for design optimization

We present a novel shape deformation method for its use in design optimization tasks. Our space deformation technique based on moving least squares approximation improves upon existing approaches in crucial aspects: It offers the same level of modeling flexibility as surface-based deformations, but it is independent of the underlying geometry representation and therefore highly robust against defects in the input data. It overcomes the scalability limitations of existing space deformation techniques based on globally supported radial basis functions while providing the same high level of deformation quality. Finally, unlike existing space deformation approaches, our technique directly incorporates geometric constraints–such as preservation of critical feature lines, circular couplings, planar or cylindrical construction parts–into the deformation, thereby fostering the exploration of more favorable and producible shape variations during the design optimization process.     

Automated Compositional Abstraction Refinement for Concurrent C Programs: A Two-Level Approach

The state space explosion problem in model checking remains the chief obstacle to the practical verification of real-world distributed systems. We attempt to address this problem in the context of verifying concurrent (message-passing) C programs against safety specifications. More specifically, we present a fully automated compositional framework which combines two orthogonal abstraction techniques (operating respectively on data and events) within a counterexample-guided abstraction refinement (CEGAR) scheme. In this way, our algorithm incrementally increases the granularity of the abstractions until the specification is either established or refuted. Our explicit use of compositionality delays the onset of state space explosion for as long as possible. To our knowledge, this is the first compositional use of CEGAR in the context of model checking concurrent C programs. We describe our approach in detail, and report on some very encouraging preliminary experimental results obtained with our tool MAGIC.     

Understanding and Using Context

Context is a poorly used source of information in our computing environments. As a result, we have an impoverished understanding of what context is and how it can be used. In this paper, we provide an operational definition of context and discuss the different ways in which context can be used by context-aware applications. We also present the Context Toolkit, an architecture that supports the building of these context-aware applications. We discuss the features and abstractions in the toolkit that make the task of building applications easier. Finally, we introduce a new abstraction, a situation which we believe will provide additional support to application designers.     

Interactive design exploration for constrained meshes

In architectural design, surface shapes are commonly subject to geometric constraints imposed by material, fabrication or assembly. Rationalization algorithms can convert a freeform design into a form feasible for production, but often require design modifications that might not comply with the design intent. In addition, they only offer limited support for exploring alternative feasible shapes, due to the high complexity of the optimization algorithm.We address these shortcomings and present a computational framework for interactive shape exploration of discrete geometric structures in the context of freeform architectural design. Our method is formulated as a mesh optimization subject to shape constraints. Our formulation can enforce soft constraints and hard constraints at the same time, and handles equality constraints and inequality constraints in a unified way. We propose a novel numerical solver that splits the optimization into a sequence of simple subproblems that can be solved efficiently and accurately.Based on this algorithm, we develop a system that allows the user to explore designs satisfying geometric constraints. Our system offers full control over the exploration process, by providing direct access to the specification of the design space. At the same time, the complexity of the underlying optimization is hidden from the user, who communicates with the system through intuitive interfaces.     

A Projective Framework for Polyhedral Mesh Modelling

We present a novel framework for polyhedral mesh editing with face‐based projective maps that preserves planarity by definition. Such meshes are essential in the field of architectural design and rationalization. By using homogeneous coordinates to describe vertices, we can parametrize the entire shape space of planar‐preserving deformations with bilinear equations. The generality of this space allows for polyhedral geometric processing methods to be conducted with ease. We demonstrate its usefulness in planar‐quadrilateral mesh subdivision, a resulting multi‐resolution editing algorithm, and novel shape‐space exploration with prescribed transformations. Furthermore, we show that our shape space is a discretization of a continuous space of conjugate‐preserving projective transformation fields on surfaces. Our shape space directly addresses planar‐quad meshes, on which we put a focus, and we further show that our framework naturally extends to meshes with faces of more than four vertices as well.     

Dynamic temporal interpretation contexts for temporal abstraction

Temporal abstraction is the task of abstracting higher‐level concepts from time‐stamped data in a context‐sensitive manner. We have developed and implemented a formal knowledge‐based framework for decomposing and solving that task that supports acquisition, maintenance, reuse, and sharing of temporal‐abstraction knowledge. We present the logical model underlying the representation and runtime formation of interpretation contexts. Interpretation contexts are relevant for abstraction of time‐oriented data and are induced by input data, concluded abstractions, external events, goals of the temporal‐abstraction process, and certain combinations of interpretation contexts. Knowledge about interpretation contexts is represented as a context ontology and as a dynamic induction relation over interpretation contexts and other proposition types. Induced interpretation contexts are either basic, composite, generalized, or nonconvex. We provide two examples of applying our model using an implemented system; one in the domain of clinical medicine (monitoring of diabetes patients) and one in the domain of traffic engineering (evaluation of traffic‐control actions). We discuss several distinct advantages to the explicit separation of interpretation‐context propositions from the propositions inducing them and from the abstractions created within them. This revised version was published online in June 2006 with corrections to the Cover Date.     

Automated generation of dynamics-based runtime certificates for high-level control

This paper addresses the problem of synthesizing controllers for reactive missions carried out by dynamical systems operating in environments of known physical geometry but consisting of uncontrolled elements that the system must react to at execution time. Such problems have value in semi-structured industrial automation settings, especially those in which robots must behave collaboratively yet safely with their human counterparts. The proposed synthesis framework addresses cases where there exists no satisfying controller for the mission, given the dynamical system and the environment’s assumed behaviors. We introduce an approach that leverages information about an abstraction of the dynamical system to automatically generate a concise set of revisions to such specifications. We provide a graphical visualization tool as a design aid, allowing the revisions to be conveyed to the user interactively and added to the specification at the user’s discretion. Any accepted statements become certificates that, if satisfied at runtime, provide guarantees for the current mission on the given dynamics. Our approach is cast into a general framework that works with various discrete representations (i.e. abstractions) of the system dynamics. We present case studies that illustrate application of our approach to controller synthesis for two example robotic missions employing different abstractions of the system.