Smooth transitions between two intersecting polygons (interesting problem)

Question

I have an interesting problem that I've been trying to solve for a while. There is no "right" solution to this, as there is no strict criteria for success. What I want to accomplish is a smooth transition between two simple polygons, from polygon A to polygon B. Polygon A is completely contained within polygon B.

My criteria for this transition are:

1. The transition is continuous in time and space
2. The area that is being "filled" from polygon A into polygon B should be filled in as if there was a liquid in A that was pouring out into the shape of B
3. It is important that this animation can be calculated either on the fly, or be defined by a set of parameters that require little space, say less than a few Kb.

Cheating is perfectly fine, any way to solve this so that it looks good is a possible solution.

Solutions I've considered, and mostly ruled out:

• Pairing up vertices in A and B and simply interpolate. Will not look good and does not work in the case of concave polygons.
• Dividing the area B-A into convex polygons, perhaps a Voronoi diagram, and calculate the discrete states of the polygon by doing a BFS on the smaller convex polygons. Then I interpolate between the discrete states. Note: If polygon B-A is convex, the transition is fairly trivial. I didn't go with this solution because dividing B-A into equally sized small convex polygons was surprisingly difficult
• Simulation: Subdivide polygon A. Move each vertex along the polygon line normal (outwards) in discrete but small steps. For each step, check if vertex is still inside B. If not, then move back to previous position. Repeat until A equals B. I don't like this solution because the check to see whether a vertex is inside a polygon is slow.

Does anybody have any different ideas?

Answer 1

If you want to keep this simple and somewhat fast, you could go ahead with your last idea where you consider scaling polygon A so that it gradually fills polygon B. You don't necessarily have to check if the scaled-outward vertices are still inside polygon B. Depending on what your code environment and API is like, you could mask the pixels of the expanding polygon A with the outline of polygon B.

In modern OpenGL, you could do this inside a fragment shader. You would have to render polygon B to a texture, send that texture to the shader, and then use that texture to look up if the current fragment being rendered maps to a texture value that has been set by polygon B. If it is not, the fragment gets discarded. You would need to have the texture be as large as the screen. If not, you would need to include some camera calculations in your shaders so you can "render" the fragment-to-test into the texture in the same way you rendered polygon B into that texture.