Home C++ Lua GitHub Games Math Myself Contact



Spacetime Constraints
The following was the web page for the final project of a graphics class I took. Since my school page is down, I'll just copy it all as is here:

Spacetime Constraints
Summary:

The purpose of this project is to find solutions to problems of physical systems meeting a specified set of constraints. Physical systems consist of one or many objects represented by rigid or articulated bodies. Integration and collision detection is handled by the Open Dynamics Engine (http://www.ode.org). Constraints can be represented in many different ways. These include specified initial, final, and intermediate positions, collision surfaces, and many others.

References:

[1] Spacetime Constraints, Andrew Witkins, Michael Kass
[2] Spacetime Constraints Revisited, J. Thomas Ngo, Joe Marks
[3] Motion from Spacetime Constraints, Matt Ahrens, Brett Levin © 2001
[4] Spacetime Constraints Attempted, Taylor Shaw © 2001
[5] Spacetime Constraints for Biomechanical Movements, David C. Brogan, Kevin P. Granata, Pradip N. Sheth
[6] Automatic Control for Animation, Ron Metoyer © 2004
[7] Efficient Generation of Motion Transitions Using Spacetime Constraints, Charles Rose, Brian Guenter, Bobby Bodenheimer, Michael F. Cohen
[8] N-Body Spacetime Constraints, Diane Tang, J. Thomas Ngo, Joe Marks © 1994
[9] Sampling Plausible Solutions to Multi-body Constraint Problems, Stephen Chenney, D. A. Forsyth

Description:

The problem at hand is finding a set of inputs that minimizes a certain objective function, satisfying some desired conditions. Problems can range from simple to complex. Simple problems involve finding the forces needed to push objects from one location to another. Complex problems include finding the torques required for a swinger to maximize his height off of the ground.
Objective functions can be measured in many different ways. They can rate the difference between an object's current position and rotation, and its desired position and rotation. They can also be used to minimize the forces or torques required of the physical system. The inputs can represent several different values within the physical system. Most commonly they are used to represent the forces or torques applied to different locations on the objects within a problem, yet the designer can use them for much more than this.

I originally intended to design systems for the purpose of learning basic physical movements, such a standing, walking, or jumping. I planned on implementing this using a genetic algorithm, possibly followed with different nonlinear optimization methods such as possibly neural networks, gradient descent methods, or the illustrious Markov Chain Monte Carlo algorithm described in one of my sources.

I broke the program down into several core components: problems, solvers, solutions, and populations. Problem objects are a description of a physical system which the user wants to solve. Solver objects optimize solutions for problems.

Solution objects represent possible solutions to problems. They contain an array of floating point values, sized according to the problem's desire. They also contain a fitness value, which is the value of the problem's objective function using this solution's set of input data.

Populations are collections of solutions. Solutions within a population were organized in a grid, for ease of display and for compatibility with my attempted genetic algorithm solver [2]. Populations are useful for optimization algorithms which evaluate multiple solutions at once, such as genetic algorithms. They are also useful for storing multiple possible solutions to a problem.

I designed the program with the idea of modularity in mind. The problem was represented by a abstract class responsible for several different tasks: creating and destroying the physical system, initializing a simulation, updating a simulation, and rendering the problem current state.

From this abstraction several problems were created: one which computed the forces that are needed to push a sphere from one location to another; one to do the same with a cube; one to maximize the height of a swinging physically constructed human; and one to minimize the convergence of multiple particles upon multiple destinations. I had desires to write several other problems, such as joining motion between BVH sequences, morphing between meshes, and simulating some very rough skeletal movement.

The solver was also abstracted. The sole task it was responsible for was to update a given population of solutions. I created only a genetic algorithm implementation of a solver. I had begun working on a quasi-Newton method, but did not finish its implementation. The interface is set up to allow the user to switch between running either solver on a problem.

The genetic algorithm solver was based off of the description of the Spacetime Constraints Revisited paper [2]. However adjustments needed to be made, considering that the genetic algorithm of that paper was implemented on a computer containing 4096 processors running in parallel. Instead this genetic algorithm cycles through each solution in the population and performs its optimization for that iteration.
The optimizations-per-iteration are as follows: first the data of the gene is randomly mutated five times, and the fitness of each set of mutated data is evaluated. The best fitness valued data set of the six solutions is kept. Mutation occurs by cycling through each input variable within the solution and permuting the value a small random amount.
Next, the crossing operation is performed. From the position within the grid that the current solution is located, a certain number of steps are taken over the tiles of the population grid. As each step is taken, the fitness of the solution at that tile is recorded. Over the course of stepping, the solution with the best fitness is chosen to cross with the currently evaluated unit. If the currently evaluated unit contains the best fitness then no crossover is performed.
Crossing occurs in one of two method: either randomly or pivot-based. The method of crossing is chosen at random. Random crossing occurs by cycling through the input variables of both parents, swapping them at random, and storing the results within two new children. Pivot based crossing occurs by choosing certain indexes within the input variable array, placing all points before the pivot from the first parent into the child, and placing all the points after the pivot from the second parent into the child.
From the cross operation, two new children are created. The fitness of each new solution is evaluated and the best fit solution of the children replaces the currently evaluated gene.

In my dreams I see a simulation suite in which the user can load model skeletons, specify physical properties, and from there can generate various forms of movement using constraints. Movements could include standing, walking, running, jumping, climbing, or many others.
From this the user could load an environment, such as the inside of a building or an outdoors street corner. The user could then place different objects within the scene, such as pedestrians walking or cars driving, avoiding one another through an objective function.
To complete the vision, such a physically simulated scene could be taken advantage of for designing scenes within movies. One example could be a car-chase scene driving through a crowd of pedestrians. The optimization function could search for the least collisions (ideally, none) between the chasee and chasers and the characters of the population.
Such simulations would be so complex that they would take hours for fitness evaluations to take place. To add to this, the current methods of optimization would be close to useless. Genetic algorithms operate far too slow to converge upon any solution. Gradient descent methods would be impossible since such systems would contain an incredible number of discontinuities. In the end it would be much easier to design such physical systems by hand.
Translation:
E - Move Forward
D - Move Backwards
S - Move Left
F - Move Right
R - Move Up
V - Move Down

Rotation:
I - Turn Down
K - Turn Up
J - Turn Left
L - Turn Right
U - Roll Left
O - Roll Right
New: - Create a New Population
Load: - Open a Population File
Save: - Save a Population File
The GA Button - Evaluate the system with the genetic algorithm
The "N" Button - Evaluate the system using the non-working quasi-Newton algorithm
The "1" Button - Execute problem #1: Moving a cube from one location to another
The "2" Button - Execute problem #2: Pushing a swinger as high as it can go
The "3" Button - Execute problem #3: Converging particles on the vertices of a mesh
Play - Plays the currently selected solution
Pause - Pauses a playback of a solution
Stop - Stops the playback of a solution
The Solution Grid - Displays all the solutions within the population. Greyer units are less fit relative to the population while more colorful units are relatively more fit. Bluer units are globally less fit, and redder units are globally better fit. Click a unit to select it for playback.
I did not ever get the convergence working for bodies as complex as I would have liked. I also did not get convergence working as fast as I would have liked to. I also originally wanted to finish the implementation to a quasi-Netwon solver, but this did not happen.
I would say I only accomplished 30% of what I originally intended to do. This is mostly because my concept of how challenging it would be to implement spacetime constraints was very naive, considering how new I was to the topic.

Demo:







Powerpoint Slides
Download

Code Usage:

The code was written in Microsoft Visual Studio .NET 2003 in C++. I have found that attempts to compile this under some earlier version of Microsoft Visual C++ may result in a handful of "variable redefined" errors. In each case, all that needs to be done is to delete the typename before each variable.

Comments:

I enjoyed every topic covered within the class. On one hand I would've liked to cover much more ground than we had within the class, but on the other I also enjoyed the detail that we were able to go into each of the topics that we did go over within the class. One thing that may be interesting to add to the class is more variation within the project requirements. To allow more optional features for the students to choose from when designing the projects. This also seems to come at a trade-off since the more variation within a project, the harder it is to define criteria to grade.

Progress:

Download the Project Here
Download the Powerpoint Slides Here