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.