It can be animated in any way -- for instance plain "morph target" animation as in Quake, where each frame of the animation specifies a position for the vertices, or any sort of procedural animation (via sin waves or whatever), pretty much anything non-rigid can invalidate the triangulation.
I'll attach an example picture -- obviously this is a bit contrived, but it illustrates the problem. In this case there is actually no static triangulation that works. Storing a triangulation with each keyframe also doesn't work, because the problems occur in-between the two keyframes rather than on keyframe boundaries. One solution would be to (in a preprocess) determine when the triangulation breaks and automatically insert a new keyframe at that point which copied the current shape but used a different triangulation. Sadly this solution can't be applied to anything reactive/physics-based though, because there's no easy way to tell "which keyframe you're on".
Another solution for this specific case is to add "steiner verts" along the bottom edge of the shape in order to allow a static triangulation that's always valid; as far as I can tell there's no way to automate this sort of "solution" -- it requires a person to figure out the solution via intuition, and it's not always this obvious. If you're planning on releasing tools to the public, it's the sort of thing you don't want them to have to screw around with for every shape they create!!
This is also something that i'm sure needed to be dealt with in loco-roco.
BUT: there's of course the possibility that i'm totally confused about this and overlooking something very simple and obvious.. please let me know
OH, it all makes sense now. Yes, every system I was discussing would be using steiner points, and I had been assuming that whatever you were thinking about would have them too ...
But yes, if you don't want steiner points, I guess you basically do have to re-triangulate every frame.
If you do have steiner points, you additionally probably want some algorithm that uses those points (or the triangles they form) as part of your calculation, so they also move in a plausible way determined by the system, since that will help keep them inside the shape and can also improve the accuracy of a simulation.
There are lots of good algorithms to automate placement of Steiner points. The basic idea of it is typically that you want a density of points such that the triangles are smaller than the surface features you'll need. As long as you have 'nice enough' triangles (often niceness is defined by how close they are to equilateral) which are packed densely enough, you should be able to handle a good range of deformations.
One such algorithm is to do a constrained Delaunay triangulation, and for each triangle with a circumcircle of radius greater than some size FeatureSize you specify, add a Steiner point at the center of that circle then recompute the constrained Delaunay triangulation.
A simpler way is to just throw down a regular grid, with edge length < FeatureSize, then cut away the bits that aren't inside the mesh, and connect the edge verts of your surface to the closest edge verts of grid.
An alternative approach I was thinking I'd apply for Bezier surfaces is to skip any proper triangulation at all, and instead just put down a relatively dense textured grid, with transparency (instead of polygon edges) defining the object border, and let movement of the much sparser Bezier control vertices dictate how the grid is squashed and stretched.