Spring Systems

Computer graphics project

 

by: Uri Juhasz & Sivan Bercovici

supervised by: Gershon Elber

 

 

Content

 

Introduction

    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.

Overview

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 mi are the point masses, vi are the point velocities, ki are the spring stiffness coefficients, xi are the spring displacement vectors and li are the springs’ rest lengths.

The total work done by external forces is calculated as  where Fi 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). 

 

Usage :

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 );

 

Interface

7 library modules are provided:

Code

The library code includes all the mentioned modules as well as the MAKEFILE for the windows and unix platform.

Download the library code

Libray usage demonstration

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.

Real-time demonstration

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.

POV Film maker

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.

Creating an input file

The input file should contain the following information (in the exact appearing order):

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.

Download the POV Film maker

Movies

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:

 

Future directions

    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:

 

    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.

Bibliography