Commits

Richard Bair committed e3a3977

Added implementation of MorphingPath. This is another approach to doing Path-based shape morphing. Not sure which we want to use (MorphingPath or MorphTransition) but I figured we'd add it and see how it goes. Guts of this class originally written by Jim Graham, I'm releasing these as sample code under BSD.

  • Participants
  • Parent commits e55acb3

Comments (0)

Files changed (1)

defender/src/main/java/com/fxexperience/games/defender/games/simple/animation/MorphingPath.java

+package com.fxexperience.games.defender.games.simple.animation;
+
+import javafx.beans.property.DoubleProperty;
+import javafx.beans.property.SimpleDoubleProperty;
+import javafx.collections.FXCollections;
+import javafx.collections.ObservableList;
+import javafx.geometry.Point2D;
+import javafx.scene.shape.*;
+
+import java.util.LinkedList;
+import java.util.List;
+import java.util.ListIterator;
+import java.util.Vector;
+
+/**
+ * Morphs one path into another.
+ */
+public class MorphingPath extends Path {
+    private final ObservableList<PathElement> fromElements = FXCollections.observableArrayList();
+    public final ObservableList<PathElement> getFromElements() { return fromElements; }
+
+    private final ObservableList<PathElement> toElements = FXCollections.observableArrayList();
+    public final ObservableList<PathElement> getToElements() { return toElements; }
+
+    private final DoubleProperty fraction = new SimpleDoubleProperty(this, "fraction", 0) {
+        @Override
+        protected void invalidated() {
+            morph();
+        }
+    };
+    public final double getFraction() { return fraction.get(); }
+    public final void setFraction(double value) { fraction.set(value); }
+    public final DoubleProperty fractionProperty() { return fraction; }
+
+    private Geometry geom0;
+    private Geometry geom1;
+
+    private void morph() {
+        // TODO logic for taking short cuts in the case that path elements / paths
+        // fromElements and toElements have not changed
+//        if (savedv0 != v0 || savedv1 != v1) {
+//            if (savedv0 == v1 && savedv1 == v0) {
+//                // Just swap the geometries
+//                Geometry gtmp = geom0;
+//                geom0 = geom1;
+//                geom1 = gtmp;
+//            } else {
+        geom0 = new Geometry(getFromElements());
+        geom1 = new Geometry(getToElements());
+        double tvals0[] = geom0.getTvals();
+        double tvals1[] = geom1.getTvals();
+        double masterTvals[] = mergeTvals(tvals0, tvals1);
+        geom0.setTvals(masterTvals);
+        geom1.setTvals(masterTvals);
+
+        // Now set up my path elements. Note that all the path elements
+        // are of type CubicCurveTo, except for the first MoveTo and last ClosePath.
+        List<PathElement> elements = new LinkedList<>();
+        elements.add(new MoveTo(geom0.getCoord(0), geom0.getCoord(1)));
+        int index = 2;
+        while (index < geom0.getNumCoords()) {
+            elements.add(new CubicCurveTo(
+                    geom0.getCoord(index),
+                    geom0.getCoord(index+1),
+                    geom0.getCoord(index+2),
+                    geom0.getCoord(index+3),
+                    geom0.getCoord(index+4),
+                    geom0.getCoord(index+5)
+            ));
+            index += 6;
+        }
+        elements.add(new ClosePath());
+        getElements().setAll(elements);
+
+//            }
+
+        // Now morph! All of my PathElements now are setup, and geom1 number of
+        // elements is a perfect match, so I just have to interpolate.
+        elements = getElements();
+        final double t = getFraction();
+        MoveTo moveTo = (MoveTo) elements.get(0);
+        moveTo.setX(interp(moveTo.getX(), geom1.getCoord(0), t));
+        moveTo.setY(interp(moveTo.getY(), geom1.getCoord(1), t));
+        index = 2;
+        for (int i=1; i<elements.size()-1; i++) {
+            CubicCurveTo to = (CubicCurveTo) elements.get(i);
+            to.setControlX1(interp(to.getControlX1(), geom1.getCoord(index), t));
+            to.setControlY1(interp(to.getControlY1(), geom1.getCoord(index + 1), t));
+            to.setControlX2(interp(to.getControlX2(), geom1.getCoord(index + 2), t));
+            to.setControlY2(interp(to.getControlY2(), geom1.getCoord(index + 3), t));
+            to.setX(interp(to.getX(), geom1.getCoord(index + 4), t));
+            to.setY(interp(to.getY(), geom1.getCoord(index + 5), t));
+            index += 6;
+        }
+    }
+
+    private static class Geometry {
+        static final double THIRD = (1.0 / 3.0);
+        static final double MIN_LEN = 0.001;
+        double bezierCoords[];
+        int numCoords;
+        double myTvals[];
+
+        public Geometry(ObservableList<PathElement> elements) {
+            // Multiple of 6 plus 2 more for initial move to
+            bezierCoords = new double[20];
+            if (elements.isEmpty()) {
+                // We will have 1 segment and it will be all zeros
+                // It will have 8 coordinates (2 for move to, 6 for cubic)
+                numCoords = 8;
+            }
+
+            final ListIterator<PathElement> pi = elements.listIterator();
+            PathElement e = pi.next();
+            if (!(e instanceof MoveTo)) {
+                // TODO or assume an implicit MoveTo of some kind? What does Path do?
+                throw new IllegalStateException("missing initial MoveTo");
+            }
+            double currentX, currentY, moveX, moveY;
+            MoveTo m = (MoveTo) e;
+            bezierCoords[0] = currentX = moveX = m.getX();
+            bezierCoords[1] = currentY = moveY = m.getY();
+            double newX, newY;
+            Vector<Point2D> savedPathEndPoints = new Vector<>();
+            numCoords = 2;
+            while (pi.hasNext()) {
+                e = pi.next();
+                if (e instanceof MoveTo) {
+                    if (currentX != moveX || currentY != moveY) {
+                        appendLineTo(currentX, currentY, moveX, moveY);
+                        currentX = moveX;
+                        currentY = moveY;
+                    }
+                    m = (MoveTo) e;
+                    newX = m.getX();
+                    newY = m.getY();
+                    if (currentX != newX || currentY != newY) {
+                        savedPathEndPoints.add(new Point2D(moveX, moveY));
+                        appendLineTo(currentX, currentY, newX, newY);
+                        currentX = moveX = newX;
+                        currentY = moveY = newY;
+                    }
+                } else if (e instanceof ClosePath) {
+                    if (currentX != moveX || currentY != moveY) {
+                        appendLineTo(currentX, currentY, moveX, moveY);
+                        currentX = moveX;
+                        currentY = moveY;
+                    }
+                } else if (e instanceof LineTo) {
+                    LineTo to = (LineTo) e;
+                    newX = to.getX();
+                    newY = to.getY();
+                    appendLineTo(currentX, currentY, newX, newY);
+                    currentX = newX;
+                    currentY = newY;
+                } else if (e instanceof QuadCurveTo) {
+                    QuadCurveTo to = (QuadCurveTo) e;
+                    double ctrlX = to.getControlX();
+                    double ctrlY = to.getControlY();
+                    newX = to.getX();
+                    newY = to.getY();
+                    appendQuadTo(currentX, currentY, ctrlX, ctrlY, newX, newY);
+                    currentX = newX;
+                    currentY = newY;
+                } else if (e instanceof CubicCurveTo) {
+                    CubicCurveTo to = (CubicCurveTo) e;
+                    appendCubicTo(to.getControlX1(), to.getControlY1(),
+                            to.getControlX2(), to.getControlY2(),
+                            to.getX(), to.getY());
+                }
+            }
+            // Add closing segment if either:
+            // - we only have initial moveto - expand it to an empty cubic
+            // - or we are not back to the starting point
+            if ((numCoords < 8) || currentX != moveX || currentY != moveY) {
+                appendLineTo(currentX, currentY, moveX, moveY);
+                currentX = moveX;
+                currentY = moveY;
+            }
+            // Now retrace our way back through all of the connecting
+            // inter-sub path segments
+            for (int i = savedPathEndPoints.size()-1; i >= 0; i--) {
+                Point2D p = savedPathEndPoints.get(i);
+                newX = p.getX();
+                newY = p.getY();
+                if (currentX != newX || currentY != newY) {
+                    appendLineTo(currentX, currentY, newX, newY);
+                    currentX = newX;
+                    currentY = newY;
+                }
+            }
+            // Now find the segment endpoint with the smallest Y coordinate
+            int minPt = 0;
+            double minX = bezierCoords[0];
+            double minY = bezierCoords[1];
+            for (int ci = 6; ci < numCoords; ci += 6) {
+                double x = bezierCoords[ci];
+                double y = bezierCoords[ci + 1];
+                if (y < minY || (y == minY && x < minX)) {
+                    minPt = ci;
+                    minX = x;
+                    minY = y;
+                }
+            }
+            // If the smallest Y coordinate is not the first coordinate,
+            // rotate the points so that it is...
+            if (minPt > 0) {
+                // Keep in mind that first 2 coords == last 2 coords
+                double newCoords[] = new double[numCoords];
+                // Copy all coordinates from minPt to the end of the
+                // array to the beginning of the new array
+                System.arraycopy(bezierCoords, minPt,
+                                 newCoords, 0,
+                                 numCoords - minPt);
+                // Now we do not want to copy 0,1 as they are duplicates
+                // of the last 2 coordinates which we just copied.  So
+                // we start the fromElements copy at index 2, but we still
+                // copy a full minPt coordinates which copies the two
+                // coordinates that were at minPt to the last two elements
+                // of the array, thus ensuring that thew new array starts
+                // and ends with the same pair of coordinates...
+                System.arraycopy(bezierCoords, 2,
+                                 newCoords, numCoords - minPt,
+                                 minPt);
+                bezierCoords = newCoords;
+            }
+            /* Clockwise enforcement:
+             * - This technique is based on the formula for calculating
+             *   the area of a Polygon.  The standard formula is:
+             *   Area(Poly) = 1/2 * sum(x[i]*y[i+1] - x[i+1]y[i])
+             * - The returned area is negative if the polygon is
+             *   "mostly clockwise" and positive if the polygon is
+             *   "mostly counter-clockwise".
+             * - One failure mode of the Area calculation is if the
+             *   Polygon is self-intersecting.  This is due to the
+             *   fact that the areas on each side of the self-intersection
+             *   are bounded by segments which have opposite winding
+             *   direction.  Thus, those areas will have opposite signs
+             *   on the acccumulation of their area summations and end
+             *   up canceling each other out partially.
+             * - This failure mode of the algorithm in determining the
+             *   exact magnitude of the area is not actually a big problem
+             *   for our needs here since we are only using the sign of
+             *   the resulting area to figure out the overall winding
+             *   direction of the path.  If self-intersections cause
+             *   different parts of the path to disagree as to the
+             *   local winding direction, that is no matter as we just
+             *   wait for the final answer to tell us which winding
+             *   direction had greater representation.  If the final
+             *   result is zero then the path was equal parts clockwise
+             *   and counter-clockwise and we do not care about which
+             *   way we order it as either way will require half of the
+             *   path to unwind and re-wind itself.
+             */
+            double area = 0;
+            // Note that first and last points are the same so we
+            // do not need to process coords[0,1] against coords[n-2,n-1]
+            currentX = bezierCoords[0];
+            currentY = bezierCoords[1];
+            for (int i = 2; i < numCoords; i += 2) {
+                newX = bezierCoords[i];
+                newY = bezierCoords[i + 1];
+                area += currentX * newY - newX * currentY;
+                currentX = newX;
+                currentY = newY;
+            }
+            if (area < 0) {
+                /* The area is negative so the shape was clockwise
+                 * in a Euclidean sense.  But, our screen coordinate
+                 * systems have the origin in the upper left so they
+                 * are flipped.  Thus, this path "looks" ccw on the
+                 * screen so we are flipping it to "look" clockwise.
+                 * Note that the first and last points are the same
+                 * so we do not need to swap them.
+                 * (Not that it matters whether the paths end up cw
+                 *  or ccw in the end as long as all of them are the
+                 *  same, but above we called this section "Clockwise
+                 *  Enforcement", so we do not want to be liars. ;-)
+                 */
+                // Note that [0,1] do not need to be swapped with [n-2,n-1]
+                // So first pair to swap is [2,3] and [n-4,n-3]
+                int i = 2;
+                int j = numCoords - 4;
+                while (i < j) {
+                    currentX = bezierCoords[i];
+                    currentY = bezierCoords[i + 1];
+                    bezierCoords[i] = bezierCoords[j];
+                    bezierCoords[i + 1] = bezierCoords[j + 1];
+                    bezierCoords[j] = currentX;
+                    bezierCoords[j + 1] = currentY;
+                    i += 2;
+                    j -= 2;
+                }
+            }
+        }
+
+        private void appendLineTo(double x0, double y0,
+                                  double x1, double y1)
+        {
+            appendCubicTo(// A third of the way from xy0 to xy1:
+                        interp(x0, x1, THIRD),
+                        interp(y0, y1, THIRD),
+                        // A third of the way from xy1 back to xy0:
+                        interp(x1, x0, THIRD),
+                        interp(y1, y0, THIRD),
+                        x1, y1);
+        }
+
+        private void appendQuadTo(double x0, double y0,
+                                  double ctrlx, double ctrly,
+                                  double x1, double y1)
+        {
+            appendCubicTo(// A third of the way from ctrlxy back to xy0:
+                        interp(ctrlx, x0, THIRD),
+                        interp(ctrly, y0, THIRD),
+                        // A third of the way from ctrlxy to xy1:
+                        interp(ctrlx, x1, THIRD),
+                        interp(ctrly, y1, THIRD),
+                        x1, y1);
+        }
+
+        private void appendCubicTo(double ctrlx1, double ctrly1,
+                                   double ctrlx2, double ctrly2,
+                                   double x1, double y1)
+        {
+            if (numCoords + 6 > bezierCoords.length) {
+                // Keep array size to a multiple of 6 plus 2
+                int newsize = (numCoords - 2) * 2 + 2;
+                double newCoords[] = new double[newsize];
+                System.arraycopy(bezierCoords, 0, newCoords, 0, numCoords);
+                bezierCoords = newCoords;
+            }
+            bezierCoords[numCoords++] = ctrlx1;
+            bezierCoords[numCoords++] = ctrly1;
+            bezierCoords[numCoords++] = ctrlx2;
+            bezierCoords[numCoords++] = ctrly2;
+            bezierCoords[numCoords++] = x1;
+            bezierCoords[numCoords++] = y1;
+        }
+
+        public int getNumCoords() {
+            return numCoords;
+        }
+
+        public double getCoord(int i) {
+            return bezierCoords[i];
+        }
+
+        public double[] getTvals() {
+            if (myTvals != null) {
+                return myTvals;
+            }
+
+            // assert(numCoords >= 8);
+            // assert(((numCoords - 2) % 6) == 0);
+            double tvals[] = new double[(numCoords - 2) / 6 + 1];
+
+            // First calculate total "length" of path
+            // Length of each segment is averaged between
+            // the length between the endpoints (a lower bound for a cubic)
+            // and the length of the control polygon (an upper bound)
+            double segx = bezierCoords[0];
+            double segy = bezierCoords[1];
+            double tlen = 0;
+            int ci = 2;
+            int ti = 0;
+            while (ci < numCoords) {
+                double prevx, prevy, newx, newy;
+                prevx = segx;
+                prevy = segy;
+                newx = bezierCoords[ci++];
+                newy = bezierCoords[ci++];
+                prevx -= newx;
+                prevy -= newy;
+                double len = Math.sqrt(prevx * prevx + prevy * prevy);
+                prevx = newx;
+                prevy = newy;
+                newx = bezierCoords[ci++];
+                newy = bezierCoords[ci++];
+                prevx -= newx;
+                prevy -= newy;
+                len += Math.sqrt(prevx * prevx + prevy * prevy);
+                prevx = newx;
+                prevy = newy;
+                newx = bezierCoords[ci++];
+                newy = bezierCoords[ci++];
+                prevx -= newx;
+                prevy -= newy;
+                len += Math.sqrt(prevx * prevx + prevy * prevy);
+                // len is now the total length of the control polygon
+                segx -= newx;
+                segy -= newy;
+                len += Math.sqrt(segx * segx + segy * segy);
+                // len is now sum of linear length and control polygon length
+                len /= 2;
+                // len is now average of the two lengths
+
+                /* If the result is zero length then we will have problems
+                 * below trying to do the math and bookkeeping to split
+                 * the segment or pair it against the segments in the
+                 * other shape.  Since these lengths are just estimates
+                 * to map the segments of the two shapes onto corresponding
+                 * segments of "approximately the same length", we will
+                 * simply modify the length of this segment to be at least
+                 * a minimum value and it will simply grow from zero or
+                 * near zero length to a non-trivial size as it morphs.
+                 */
+                if (len < MIN_LEN) {
+                    len = MIN_LEN;
+                }
+                tlen += len;
+                tvals[ti++] = tlen;
+                segx = newx;
+                segy = newy;
+            }
+
+            // Now set tvals for each segment to its proportional
+            // part of the length
+            double prevt = tvals[0];
+            tvals[0] = 0;
+            for (ti = 1; ti < tvals.length - 1; ti++) {
+                double nextt = tvals[ti];
+                tvals[ti] = prevt / tlen;
+                prevt = nextt;
+            }
+            tvals[ti] = 1;
+            return (myTvals = tvals);
+        }
+
+        public void setTvals(double newTvals[]) {
+            double oldCoords[] = bezierCoords;
+            double newCoords[] = new double[2 + (newTvals.length - 1) * 6];
+            double oldTvals[] = getTvals();
+            int oldci = 0;
+            double x0, xc0, xc1, x1;
+            double y0, yc0, yc1, y1;
+            x0 = xc0 = xc1 = x1 = oldCoords[oldci++];
+            y0 = yc0 = yc1 = y1 = oldCoords[oldci++];
+            int newci = 0;
+            newCoords[newci++] = x0;
+            newCoords[newci++] = y0;
+            double t0 = 0;
+            double t1 = 0;
+            int oldti = 1;
+            int newti = 1;
+            while (newti < newTvals.length) {
+                if (t0 >= t1) {
+                    x0 = x1;
+                    y0 = y1;
+                    xc0 = oldCoords[oldci++];
+                    yc0 = oldCoords[oldci++];
+                    xc1 = oldCoords[oldci++];
+                    yc1 = oldCoords[oldci++];
+                    x1 = oldCoords[oldci++];
+                    y1 = oldCoords[oldci++];
+                    t1 = oldTvals[oldti++];
+                }
+                double nt = newTvals[newti++];
+                // assert(nt > t0);
+                if (nt < t1) {
+                    // Make nt proportional to [t0 => t1] range
+                    double relt = (nt - t0) / (t1 - t0);
+                    newCoords[newci++] = x0 = interp(x0, xc0, relt);
+                    newCoords[newci++] = y0 = interp(y0, yc0, relt);
+                    xc0 = interp(xc0, xc1, relt);
+                    yc0 = interp(yc0, yc1, relt);
+                    xc1 = interp(xc1, x1, relt);
+                    yc1 = interp(yc1, y1, relt);
+                    newCoords[newci++] = x0 = interp(x0, xc0, relt);
+                    newCoords[newci++] = y0 = interp(y0, yc0, relt);
+                    xc0 = interp(xc0, xc1, relt);
+                    yc0 = interp(yc0, yc1, relt);
+                    newCoords[newci++] = x0 = interp(x0, xc0, relt);
+                    newCoords[newci++] = y0 = interp(y0, yc0, relt);
+                } else {
+                    newCoords[newci++] = xc0;
+                    newCoords[newci++] = yc0;
+                    newCoords[newci++] = xc1;
+                    newCoords[newci++] = yc1;
+                    newCoords[newci++] = x1;
+                    newCoords[newci++] = y1;
+                }
+                t0 = nt;
+            }
+            bezierCoords = newCoords;
+            numCoords = newCoords.length;
+            myTvals = newTvals;
+        }
+    }
+
+    private static double interp(double v0, double v1, double t) {
+        return (v0 + ((v1 - v0) * t));
+    }
+
+    private static double[] mergeTvals(double tvals0[], double tvals1[]) {
+        int count = sortTvals(tvals0, tvals1, null);
+        double newtvals[] = new double[count];
+        sortTvals(tvals0, tvals1, newtvals);
+        return newtvals;
+    }
+
+    private static int sortTvals(double tvals0[],
+                                 double tvals1[],
+                                 double newtvals[])
+    {
+        int i0 = 0;
+        int i1 = 0;
+        int numtvals = 0;
+        while (i0 < tvals0.length && i1 < tvals1.length) {
+            double t0 = tvals0[i0];
+            double t1 = tvals1[i1];
+            if (t0 <= t1) {
+                if (newtvals != null) newtvals[numtvals] = t0;
+                i0++;
+            }
+            if (t1 <= t0) {
+                if (newtvals != null) newtvals[numtvals] = t1;
+                i1++;
+            }
+            numtvals++;
+        }
+        return numtvals;
+    }
+}