Spring Systems
Computer graphics project
by: Uri Juhasz & Sivan Bercovici
supervised by: Gershon Elber
Content
The project's main goal is to provide a basic library for creating and solving complex spring systems. Easy startup utility functions are also provided in the form of a spring graph factory (adds a mesh to a spring graph). Furthermore, external forces can also be supplied to a simulation (gravity is supplied as an example).
Along with the library, three types of demonstrations are provided. A real-time demonstration showing that on small, simple models, the solver can achieve real-time speed. A POV movie maker provides an easy to use film maker based on the spring graph simulation library. A third application example is provided for first-time library users as a tutorial for using the simulator (simulation library).
This web-site is divided into three main sections. The first part reviews the library structure and provides a full-detailed documentation for the design and interface of the library (Overview, Library usage and library interface sections). The second main section describes three different demonstrations of applications that use the simulation library. This section also includes some results in a form of films. The last section examines possible future directions and also provides a bibliography list.
Structural decomposition:
The library implements 2 main structures: SpringGraph and Solver.
SpringGraph:
A SpringGraph holds a complete snapshot of a mass-spring system at a given time: Masses, springs, positions, velocities, stiffnesses and damping coefficients.
The structure allows for iteration over the values but not for modification.
A SpringGraph has 2 modes: one for construction and one for use.
· In construction mode data (masses and springs) are added but are not visible until the SpringGraph is compiled.
· Once all primitives have been added the graph is compiled and then it is in use mode. Compilation may be time consuming.
Solver:
A Solver holds the information needed to advance the state of one graph to the next point in time efficiently. It is also able to register an external force callback and a vertex collision callback.
Building (or resetting) a solver may be time consuming.
A solver has one important function: advance. This function gets a time step (∆t) and adjusts the graph to that time.
Collisions:
Collisions are handled by a callback registered with the solver.
The callback determines, for each vertex, how far it can travel In a given direction and, if it collides, what amount of velocity is preserved ( reversed ).
Forces:
Forces are handled by a callback registered with the solver.
The callback determines, for each vertex, what force acts on it. The function should be continuous and not too steep (too steep is defined by the object’s size and stiffness) if the function is not smooth it should use the collision mechanism to force smaller time steps.
Spring Breakage:
Each spring has a minimum and maximum break length. If spring breaking is enabled then a spring will break (it’s stiffness reduced to zero) if exceeds it’s limits. There is a callback function for spring breakage that is registered with the solver and called each time a spring is broken.
Mesh Factory:
There is a function for creating a spring graph from a mesh.
The factory creates a mass point for each vertex in the mesh, and a spring for each mesh edge, each edge between two adjacent triangles and each pair of points nearer than a given threshold.
Implementation :
SpringGraph:
The SpringGraph is implemented as arrays of positions, velocities, masses, and spring and topological data.
When constructed the data is stored in linked lists and when compiled it is transferred to arrays.
Solver:
The solver is time adaptive so that it keeps stability (in the energy sense) as long as numerical stability allows it (and external forces and collisions are well behaved).
Energy stability means that the system does not gain any energy in any time step. If no external forces, collisions nor damping are active it means that the energy is constantly increasing (because we use first order approximations). If damping is active we will get a constant decrease in energy.
The solver acts by dividing each time step to smaller sub steps that each keep stability.
We achieve that by calculating our gain in energy at each sub step and making sure it is negative by decreasing our time step until it is indeed decreasing or we have reached the limit of numerical stability.
The total energy of a mass-spring system is:
Where m_{i} are the point masses, v_{i} are the point velocities, k_{i }are the spring stiffness coefficients, x_{i }are the spring displacement vectors and l_{i }are the springs’ rest lengths.
The total work done by external forces is calculated as where F_{i} is the forces acting on each vertex.
As long as the external force is not dissipative, (and is sampled at sufficient resolution) The energy gained will be monotonously increasing in ∆t so we just have to find a ∆t such that the total energy gain minus the work done by external forces is negative ( or actually non positive ).
We start by using the previous_∆t * DT_FACTOR (defaults to 2.0), and whenever we gain energy we divide ∆t by DT_FACTOR until we get to MIN_DT which is the numerical stability limit.
Calculating the energy is expensive because it is O(V) + O(E) where V and E are the numbers of vertices and edges. The most expensive part is calculating the square root for calculating spring energy (because it is nonlinear – nonzero rest length) We reuse this calculation for calculating spring forces.
We pre-calculate mass reciprocals for saving divisions (at the price of memory and cache size).
For using the library one has to construct a SpringGraph :
#include "SpringGraph.h"
GMSprSpringGraphStruct* spring_graph;
springGraph = GMSprCreateSpringGraph();
The it has to be constructed :
GMSprPositionType position;
GMSprVelocityType velocity;
GMSprMassType mass;
Int fixed;
…
GMSprAddVertex( spring_graph, position, velocity, mass, fixed );
…
GMSprVIDType v0, v1;
GMSprStiffnessType k;
GMSprDampingType d;
GMSprLengthType l;
GMSprLengthType l_min;
GMSprLengthType l_max;
GMSprAddSpring( spring_graph, v0, v1, k, d );
…
GMSprAddSpringDetailed( spring_graph, v0, v1, k, l, d, l_min, l_max );
…
And compiled :
GMSprCompile( spring_graph );
Then a solver has to be created :
#include "SpringSystemSolver.h"
GMSprSolverType solver;
solver = GMSprCreateSolver( spring_graph );
Then the solver can be used :
GMSprAdvance( solver );
And results can be read from the graph :
GMSprVIDType i;
for ( i = GMSprGetFirstVertex( spring_graph );
GMSprIsValidVertex( spring_graph, i );
i = GMSprGetNextVertex( spring_graph, i ) )
{
Vector X, V;
GMSprGetVertexPosition( g, i, &X );
GMSprGetVertexVelocity( g, i, &V );
…
}
GMSprSIDType i;
for ( i = GMSprGetFirstSpring( spring_graph );
GMSprIsValidSpring( spring_graph, i );
i = GMSprGetNextSpring( spring_graph, i ) )
{
VID v1, v2;
V1 = GMSprGetSpringVertex1( g, i );
V2 = GMSprGetSpringVertex2( g, i );
…
}
At the end solver and graph must be destroyed :
GMSprDestroySolver( solver );
GMSprDestroySpringGraph( spring_graph );
7 library modules are provided:
The library code includes all the mentioned modules as well as the MAKEFILE for the windows and unix platform.
A simple example of an application using the spring system library was written in C. The goal of this example is to show how to actually use the library features.
Several samples taken from a single simulation of a
bouncing sphere using the library's application example.
The union of the samples is shown from 4 different view points.
The application enables a user to load a triangular IRIT model, construct a spring-system for the loaded objects (using the library's factory) and simulate the system while dumping spring system state, again, as an IRIT model (named "output#.irit", where # stands for the sample number). The simulation runs until the system's kinetic energy goes bellow a defined threshold, or the watch-dog timer expires.
The application example exposes all simulation parameters, allowing a user to affect simulation behavior. These parameters are available to be played with in the code as well as from the command-line:
Factory parameters (used during the construction of the spring graph):
Parameter Name | Command Line | Description |
DefaultStretchStiffness | -SS | The default stretch spring stifness |
DefaultBendStiffness | -BS | The default bend spring stifness |
DefaultStretchDamping | -SD | The default stretch spring damping |
DefaultBendDamping | -BD | The default bend spring damping |
Mass | -M | The mass each vertex |
VicinityConstant | -V | A parameter used for constructed of springs according to the vicinity of the vertices (as explained in the manual) |
Simulation parameters (used to define the constrains for the simulation):
Parameter Name | Command Line | Description |
energyThresh | -T | Define a breakpoint for the simulation. When the kinetic energy is below this parameter, the simulation ends (and the model is considered stable) |
dT | -DT | The time delta between frames (which are dumped under the name output#.irit) |
minTime | -MINT | A minimum time frame in which the system may advance without even testing for stability |
maxTime | -MAXT | A positive maximum time bound after which the stabilization process is ended |
For example, a user can invoke the demo application as follows:
"SpringAppEx faced.itd -SS=1500 -BS=1500 -SD=4.0 -BD=3.0 -M=0.5 -v=0.30 -t=0.01 T=0.03 -MinT=0.1 -maxT=15.3
resulting in the following output
Notice that the input file name must be the first parameters, while all other parameters (such as spring stiffness, etc.) may be supplied by the user. In case one of the values is not supplied, the corresponding missing parameter will receive a default value (as set inside the SpringAppEx.c code). Also notice that the input models must be triangular IRIT model files.
When modifying simulation parameters, the user must supply them in the MKS (Meter/Kilogram/Seconds) unit system.
The example application requires the library, which is explained (and supplied) in the code section.
The previous sphere snapshoot was created using the sphere.itd model as an input. One can review the results of the simulation by examining the dumped simulation states which are also in the IRIT file format.
This demo demonstrates real time spring
systems.
The demo consists of an object falling on a surface under the effect
of gravity.
There are two versions : one for
un-extended OpenGL and the other with several visual enhancements that require
:
EXT_MIRRORED_REPEAT
ARB_VERTEX_PROGRAM
ARB_FRAGMENT_PROGRAM
And
uses tri-linear filtering.
The demo accepts the full name of a 3ds file
on the command line (not including the .3ds suffix).
Keys :
F1 :
Hide/display vertices.
F2 : Hide/display edges.
F3 : Hide/display energy
in edges.
F4 : Hide/display faces.
F5 : Enable/disable texture.
r :
Reverse gravity.
s : Stop.
g : Enable/disable gravity.
This demo
requires glut and OpenGL.
The POV film maker provides an easy to use tool for creating spring system simulation results using POV scenes as the initial state of the system. During the simulation, the automatically constructed spring-graph are simulated along with a gravity force (9.8N) and inter-object collisions (intra-object collision is not supported).
The film maker support POV version 3.5, and works only on objects that are defined as mesh2 objects.
The #include directive is not supported, so all the information should be provided in a single file.
In order to use the file maker, the POV file should be modified and an input file should be created.
The POV film maker takes the input file as a parameter.
Modification inside the POV file
Each object (mesh2) in the scene is either fixed or not fixed. The fixed objects should look as follows:
#declare SomeObjext =
mesh2
{
#local
spring_system_fixed =
true;
vertex_vectors
{
....
defining the local variable "#local spring_system_fixed = true" is a must inside an object which is fixed.
In order to define a non-fixed object, the following information should appear:
#declare SomeObject2= mesh2
{
#local spring_system_ks = 600;
#local spring_system_kb = 600;
#local spring_system_ds = 2;
#local spring_system_db = 2;
#local spring_system_mass = 3;
#local spring_system_vicinity = 0.1;
#local spring_system_fixed = false;
The user may must supply K stretch and bend spring constants, damping factors (for both stretch and bend springs), the mass of the object as well as a vicinity factor for the spring-graph factory. The last variable indicates that the object is not fixed.
The input file should contain the following information (in the exact appearing order):
POV engine path (including the execution file name)
POV source file (the initial state of the simulation)
Simulation time step
Time boundary
"true"/"false" (should the file maker try to render using the supplied POV rendering engine)
Resulting picture height
Resulting picture width
Result picture base name (to which indexing numbers are added)
The best way to use the film maker is to set the render option to false, thus creating multiple POV files, which in turn could be used by the POV renderer in order to view the results. No tool for creating a movie from the resulting pictures is provided.
Following are a number of example for movies created using the POV film maker:
Source POV file: Map
Source POV file: Bounce
Source POV file: Shapes
Source POV file: Map on table
Source POV file: Bounce hard
Source POV file: Boing
The following movies were created by a sub-version of the POV film maker. This sub-version demonstrate the use of fixed points in the spring-graph:
4 Fixed points:
2 Fixed points:
Collisions
Currently, collision handling is not a standard part of the library but rather only the interface is supplied. Implementing numerous collision detection and handling modules would enable the user to choose between fast results (for real-time usage) and accurate results (for movie making).
External forces
Along with the library, a basic gravity force is implemented as an example of an external force. Further forces can be implemented according to the GMSprForceStruct interface structure. Implementing more forces will enrich the results, simulating forces such as electric force, wind and water resistance.
Factory
The library provides the interface for the factory, yet the implementation can be extended to support per object iso-mass distribution and various spring graph construction methods other than the provided ones. Constructing a better spring-graph might result in both better performance and more appealing results.
Solver
The solver can be optimized as follows:
Because velocity is linear in time in one time step the energy is quadratic so we could calculate 3 factors ahead and then have an O(1) calculation for kinetic energy.
A rougher approximation for the square root could be provided
High level solver
The high level solver provides a stabilization function which simulate a whole a scene until a maximum time is reached, or the whole system is stabilized. Currently, The solver works on a single spring graph resolution. Working parallel with numerous spring graph will enable the user to create more attractive and complex scenes. Further "high-level" functions might help to run the simulation to different interesting events.
Adi Bar-Lev, "Virual Marionettes", 15-16,
2002
William H. Press, Brain P. Flannery, Saul A. Teukolsky, William T. Vetterling,
"Numerical Recipes in C: The Art of Scientific Computing", 710-722, 16, 1992