adaptive sampling

I got an interesting idea today.

As you may already know, I’ve been making models of Klein bottles an’ stuff; heretofore they’ve all been in the form of bent rods, but where possible I’d prefer a continuous surface. (A hollow body must have holes so that unused powder can be shaken out; but not all of my designs have enclosed spaces.) How to place a minimum number of vertices so that deviations from the abstract shape are within the resolution of the process? That’s less obvious with more degrees of freedom.

So, today’s idea. Start with an arbitrary set of sample nodes (in the abstract space of the parametric variables, rather than on the target surface itself), and their Delaunay triangulation. Along each edge of the triangulation, measure the deviation of the surface from a straight line; this gives the edge a weight. Move each node to the weighted average of its neighbors (with a bit of noise); thus, an edge whose image is strongly curved gets shorter.

After the movement phase, each edge ought to be checked, whether it’s still a Delaunay edge or needs to be replaced by the other diagonal of the quadrilateral formed by its two triangles. I don’t yet have criteria for adding nodes where existing nodes are too far apart, or merging them if they become redundant.