Our first homework was to do "some kind of simulation." Spring-mass systems are "too boring," so we did a FEM simulation of cloth. We wrote everything from scratch, only using OpenGL to render, and a math library to store vectors, and perform matrix multiplication/inverses.

Here are some examples of what we did.

We implemented a FEM (finite element method) simulation, which is a continuum-based formulation. Spring-mass systems are "simple" and "boring."

To do this, we wrote a script to generate a 2D mesh of a cloth, literally
creating a uniform grid of vertices, then connecting them with triangles.
This mesh was stored in two coordinate frames, one for *world space*,
and another for *material space*. World space is where each vertex of
the cloth actually *is*, and material space is the original definition
of the cloth. We assumed the cloth was infinitely thin, so our material space was in
2D. Our world space is obviously in 3D. In our simulations, we jitter
the vertices out-of-plane sometimes slightly, and sometimes not-so-slightly
to give us more interesting simulations.

At each timestep, we loop through the triangles and compute the stress due to strain and strain rate, and store forces that act upon each vertex. Of course, each triangle shares vertices with other triangles, so the force is collectively added up per timestep.

After the forces are calculated, we use *explicit integration*,
taking some small timestep forward, and approximating the velocity due to
our newly-calculated force, and the new position that results from this
velocityh.

Collision detection is done by using *edge-triangle intersection*.
An edge here is defined by the vector from the old position to the
new position, defined by the integration of velocity. If this vector
intersects any triangle, then a collision is detected.

To accelerate the triangle detection, we created a grid over the world, where each vertex is inside a single node in the grid. We first size the grid by using the world's axis-aligned bounding box, then subidividing it into a user-specified resolution (we used 10x10x10). Each vertex is reassigned a bin when being updated, and each triangle that contains this vertex is added to a list corresponding to the bin of the vertex. (This means each triangle can potentially be listed in 3 different bins.) When testing for intersection, we test only the bins that the position change vector can reach. We assumed that the bins would be at least one-third of the largest triangle dimension, and that our time-steps were sufficiently small, so that we would only have to check the bins containing the start and end of our position change.

We tried multiple ways to deal with this. Our first attempt was to set
the position as constant, but this would mean that our cloth would be made
of tape, and super sticky. Our next attempt was to set *velocity* to
zero, and this works reasonably *ok* in most cases. Our last attempt,
which we are still working on, uses penalty forces, but it is difficult
to determine the inside-outside of a *thin-shell cloth*.

Finally, we use OpenGL/GLSL to render the image.

We didn't implement strain limiting, and it really shows in the following images:

We also *almost* got collision detection working with the cloth and itself, but there are
still a few self intersections. We hope that *most* self-penetrations
were caught and fixed.

Additionally, our simulation uses Green strain instead of a rotationally invariant Green-Cauchy strain linearization, which requires our simulation to take smaller time steps than if we did. This was done in the interest of time, so that we could make sure our project was finished in time.