Most Useful Math

[jemidiah]

I looked at your code, which seems pretty reasonable. Of course I haven't checked every piece of reasoning, but only got a general idea of how everything works. To outline the algorithm...

0. Start with two slices. Each slice ("Polygon" in the code) contains some number of non-self-intersecting polygons ("Contours" in the code). I'll use the code's wording instead of math's wording when they conflict. None of the contours intersect each other inside a given polygon, either.

1. Invert the orientation of each contour in each polygon, if needed, so that everything has a consistent clockwise orientation.

2. Renumber the vertices in each contour in each polygon in such a way that first vertices of different contours are in approximately the "same" location on their contour, relatively speaking. The algorithm used takes the x-midpoint of the contour (the point on the x axis halfway between the farthest left and farthest right points on that contour). It intersects the vertical line passing through that midpoint with the edges of the contour and adds the topmost point of intersection to that contour. Vertices are renumbered so that this intersection is point number 1 and the clockwise ordering is kept.

3. The contours are resampled in such a way that the number of vertices on every contour is the same. This is done by sampling at a high enough rate to guarantee that the shortest edge will still have at least one point. (Actually, I think there's a bug that's causing the sampling rate to be even higher than it should be, though aside from speed this isn't really a problem. The length calculation was too high when I looked at a couple of triangles. I also think there's another bug causing some points to be taken several times, which sometimes causes distorted and eventually self-intersecting interpolations.)

4. Every contour in the first polygon is interpolated with every contour in the second polygon. That is, a new contour made out of somehow combining the two contours is generated. For n contours in the first polygon and m in the second polygon, this generates n*m new contours--which is of course very wrong. The actual interpolation used is quite simple. Since the contours all have the same number of points and each point is at approximately the same "place" on every contour from renumbering, a simple linear interpolation is used on pairs of same-numbered vertices from each contour in the interpolation. This generates a very smooth transition between contours.


First, aside from bugs, the interpolation part of this algorithm seems pretty good to me. There's some bias involved in choosing the number 1 vertex as described above, but not a whole lot, and something had to be chosen, somehow, regardless. Perhaps there are some annoying edge cases where this would become a problem, but improving the number 1 choice algorithm doesn't seem like it would net a large gain. So, steps 1-3 seem fine.

Step 4 is the real culprit, especially in your difficulty with handling multiple contours. I would suggest a different approach in determining which pairs of contours should be interpolated.

First, calculate the center of mass of every contour in both polygons. Formulas for discrete center of mass calculations can be found online. You would assume that the polygon bounds a mass of uniform density and find the center of that mass. If you wanted to approximate this instead, you could more easily take the average of the vectors describing the edges of the contour. Physically, this would assume that all of your mass is uniformly distributed at only the vertices of a contour.

Second, determine which contours in the first slice should morph into which contours in the second slice. The most reasonable thing I can think of here is for each contour in the first slice, find the closest center of mass for a contour in the second slice. If Contour A in the first slice has its center of mass located 10, 20, and 30 units away from Contours 1, 2, and 3 in the second slice, then only interpolate between Contour A and Contour 1. Don't include the interpolations between Contour A and Contours 2 or 3.

A slight problem crops up when contours aren't uniquely paired off. For instance, you might have Contours A and B both morphing into Contour 1 if Contour B is close to Contour 1 and far from Contours 2 and 3. Only a slight modification of this algorithm should be needed here. We generate Contours A1 and B1 using the existing linear interpolation scheme. We should then simply polygon union A1 and B1. If A1 and B1 don't intersect each other, this will not affect them. If A1 and B1 do intersect each other, we would want to be sure we cut out the edges that accidentally stay internal to the polygon.

Another slight problem happens when a contour in one slice has no corresponding contour in another slice. It seems reasonable to me to simply shrink the given contour down to nothing in such a case. Shrinking would be done by scaling using the center of mass as the center of scaling. However, if slices are taken sufficiently close to each other, this shouldn't happen.


What did you mean when you said, "Also, if the cross sections are overlapping each other I don't know how to proceed."?