A Unified Framework for Constraint-Based Modeling

Abstract

Constraint-based modeling techniques are emerging as an effective computer graphics approach for modeling and designing objects and their behaviors. In this thesis, computer graphics constraint techniques are unified into a single conceptual framework. The central themes of the thesis are methods to partition an arbitrary constraint problem in different domains and at different levels, and to provide a language and computational environment for modeling with constraints. Using partitioning and composition schemes, complex simulations can be built hierarchically from simpler simulations by "plugging" together separate modules. Fundamental and basic structures are designed and implemented to provide an "Assembly Language" for simulation systems. These structures are put together through a collection of interfaces, much like multiple languages that use the same assembler on a computer. We use strategies called refinement and partitioning to integrate seemingly disparate constraint techniques. We present Temporal Sequencing as an approach to design complex time behaviors of simulation systems. Refinement is a top-down approach of transforming high level representations of a constraint modeling problem into representations that are closer to the basic solution mechanisms available in the constraint environment, such as numerical solution methods. Partitioning is the decomposition of one constraint problem into multiple simpler constraint problems that are then studied separately. Temporal Sequencing is a methodology to design the time behavior of a simulation system by composing time behaviors of the system over subintervals of time. Using the above partitioning schemes for the solution and specification of a general constraint problem, we create a unified constraint environment with the capability to both solve constraint problem instances and to create specialized constraint systems. New methods of constraint specification and solution can be added into the same constraint framework as new methods are developed. Based on the above approach, a modeling system called "Our Constraint Environment" (OCE) has been implemented. A programming language as an extension to C++ has been designed to provide an interface to OCE. The language provides the constructs for the partitioning schemes discussed above. Simulations created using OCE have shown the efficacy of our design approach. Constraint-based modeling techniques are emerging as an effective computer graphics approach for modeling and designing objects and their behaviors. In this thesis, computer graphics constraint techniques are unified into a single conceptual framework. The central themes of the thesis are methods to partition an arbitrary constraint problem in different domains and at different levels, and to provide a language and computational environment for modeling with constraints. Using partitioning and composition schemes, complex simulations can be built hierarchically from simpler simulations by "plugging" together separate modules. Fundamental and basic structures are designed and implemented to provide an "Assembly Language" for simulation systems. These structures are put together through a collection of interfaces, much like multiple languages that use the same assembler on a computer. We use strategies called refinement and partitioning to integrate seemingly disparate constraint techniques. We present Temporal Sequencing as an approach to design complex time behaviors of simulation systems. Refinement is a top-down approach of transforming high level representations of a constraint modeling problem into representations that are closer to the basic solution mechanisms available in the constraint environment, such as numerical solution methods. Partitioning is the decomposition of one constraint problem into multiple simpler constraint problems that are then studied separately. Temporal Sequencing is a methodology to design the time behavior of a simulation system by composing time behaviors of the system over subintervals of time. Using the above partitioning schemes for the solution and specification of a general constraint problem, we create a unified constraint environment with the capability to both solve constraint problem instances and to create specialized constraint systems. New methods of constraint specification and solution can be added into the same constraint framework as new methods are developed. Based on the above approach, a modeling system called "Our Constraint Environment" (OCE) has been implemented. A programming language as an extension to C++ has been designed to provide an interface to OCE. The language provides the constructs for the partitioning schemes discussed above. Simulations created using OCE have shown the efficacy of our design approach.

Files

Additional details