I was wondering if anyone knows of some software (or an algorithm) for warping/interpolating

I was wondering if anyone knows of some software (or an algorithm) for warping/interpolating 2D polygons? I’ve become a big fan of printing gcode generated by a python script without having to torture a pile of poor helpless triangles. I’m working on a print whose source shapes aren’t completely continuous, so I want to be able to interpolate some intermediate layers in a visually appealing way. This is similar to a loft operation in CAD, but the key is that it ‘looks good’, whatever that means.

The first algorithm I tried would find the centroid of the target polygon and sweep a ray from the centroid to points on the target polygon and find the corresponding point in the source polygon then interpolate along line that connects the points. This somewhat worked on simple prints, but doesn’t work with what I’m looking to print now (think fractals).

I need a smarter method of picking corresponding points and something better then a simple linear interpolation of the corresponding points. I suspect I need something that interpolates linearly in area, so one polyline will grow/shrink into the other more organically. Any ideas?

For reference, I attached some images of my earlier attempts at generated gcode.

One possible technique would be to drop the polygons temporarily - convert both polys to a bitmap at a sufficient resolution, blend the two with a varying degree of transparency, and then use tracing techniques to follow the outline of a particular darkness level and return it to polygonal form.

Having thought of that off the top of my head, I went searching for something and found that a very similar technique is used in GIS software to move between polygons at different levels of resolution - http://resources.arcgis.com/en/help/main/10.1/index.html#//0031000000q8000000

Not quite the same thing, but it demonstrates the basic idea. Interpolating between two bitmap heightmaps is a more solved problem. Does not do your suggestion about preserving the area, but it does avoid any kinking due to poor choices of matching points.

Also, here is a technique that works only for wholly convex polygons, but prevents intersections:


Funny you should recommend doing it with image processing. I have played around with generating boundary scan prints using one pixel per step. It isn’t that bad, only 225MBytes for an 8bit ultimaker slice. But I did that mostly because I have a background in image processing and it was a convenient hammer. But maybe I should give it a try again.

The second link seems like an interesting idea. When generating these prints I tend to way oversample and then simplify to the printers resolution just prior to generating the gcode. It will be interesting to see how that algorithm behaves with a large number of points.

Well, probably it was in my head because I had been considering something similar as an attempt at doing something interesting with STL files - basically, convert the STL file into a volume of voxels, then run an iterative evolutionary algorithm against it using simple solids, producing voxel models of the CSG output of the solids and differencing them to get the fitness function for the evolutionary algorithm, combined with a fitness function on the inverse of the quantity of solids, in an attempt to get an ‘as simple as possible but no simpler’ CSG model that could be converted into OpenSCAD code.