views:

133

answers:

3

I'd like to write a program that lets me arbitrarily distort a textured polygon by dragging its vertices. I want the texture to distort fluidly and without overlap, assuming the new polygon doesn't intersect itself. I should also be able to repeat the process with the new shape, and with a minimum amount of loss.

Are there any algorithms for doing this?

A: 

The simplest method I can think of is to triangulate the input polygon (using an ear clipping method, or something similarly good) and then move the points. Then you can use a barycentric mapping from the original polygon to the new space.

If you're looking for something more robust, you might look at mean value coordinates.

tfinniga
+1  A: 

It sounds like you might want a variation on the Schwarz-Christoffel mapping. This is a type of conformal mapping that can be used to warp a polygon to and from a simpler region, like a disk; although I have not implemented it, apparently it is computationally tractable.

For your application, you would set up a map from the original polygon to the simpler region, and compute the inverse map to the modified polygon; combining the two should give you a nice conformal mapping from the original to the modified polygon.

Conformal mappings are nice and smooth, but they can sometimes behave in unintuitive ways; I can imagine that an animated version might yield some entertaining "slidy" effects. The conformal mapping will preserve local angles in the interior of the polygon; this means that the size distortion very near a modified vertex can be severe.

comingstorm
+1  A: 

People have been working on solutions to this problem for the past decade or two, and the state of the art keeps on getting better and better (but the math gets harder as well). A good place to start (and sort of where I stopped following it) is the work http://www.cs.technion.ac.il/~weber/Publications/Complex-Coordinates/

Read the paper there, and look up the papers in the references. One of them should give you an algorithm that you're willing to implement.

brainjam