Another experiment with generating semi-regular planar tilings of surfaces. The previous post featured meshes which were convex, which makes things much easier. I wanted to extend the technique to surfaces that have negative curvature, which is a trickier problem. There is a lovley paper from 2007 ("Constrained Planar Remeshing for Architecture" by Barbar Cutler and Emily Whiting) that I read a while ago that I couldn't find a copy of, and my recollection was that they do VSA, as I do, and then follow up with some kind of local tweaks of vertices to get the polygons to be planar. I decided instead use nonlinear optimization to tweak all the vertices to make the polygons planar, while remaining as close as possible to the original surface. It's similar to what Yang Liu, Helmut Pottman and the rest do in a paper from 2006 ("Geometric Modeling with Conical Meshes and Developable Surfaces"), except they are concerned with quad-dominant meshes.
The video makes it appear as though the optimization is essentially instantaneous, but it actually has to crank away for about 20 seconds. It generally gives good results, though sometimes it results in a few nasty looking polygons with long slivery bits, or interpenetrating polygons. Fiddling with the cost function would probably fix that.
Negative curvature will result in concave polygons. I wasn't sure if I liked the look of them at first, but they've grown on me.