/*

 * Copyright (c) 2007, 2017, Oracle and/or its affiliates. All rights reserved.

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * This code is free software; you can redistribute it and/or modify it

 * under the terms of the GNU General Public License version 2 only, as

 * published by the Free Software Foundation.  Oracle designates this

 * particular file as subject to the "Classpath" exception as provided

 * by Oracle in the LICENSE file that accompanied this code.

 *

 * This code is distributed in the hope that it will be useful, but WITHOUT

 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

 * version 2 for more details (a copy is included in the LICENSE file that

 * accompanied this code).

 *

 * You should have received a copy of the GNU General Public License version

 * 2 along with this work; if not, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 */

package sun.java2d.marlin;

import java.util.Arrays;

// TODO: some of the arithmetic here is too verbose and prone to hard to

// debug typos. We should consider making a small Point/Vector class that

// has methods like plus(Point), minus(Point), dot(Point), cross(Point)and such

final class DStroker implements DPathConsumer2D, MarlinConst {

    private static final int MOVE_TO = 0;

    private static final int DRAWING_OP_TO = 1; // ie. curve, line, or quad

    private static final int CLOSE = 2;

    /**

     * Constant value for join style.

     */

    public static final int JOIN_MITER = 0;

    /**

     * Constant value for join style.

     */

    public static final int JOIN_ROUND = 1;

    /**

     * Constant value for join style.

     */

    public static final int JOIN_BEVEL = 2;

    /**

     * Constant value for end cap style.

     */

    public static final int CAP_BUTT = 0;

    /**

     * Constant value for end cap style.

     */

    public static final int CAP_ROUND = 1;

    /**

     * Constant value for end cap style.

     */

    public static final int CAP_SQUARE = 2;

    // pisces used to use fixed point arithmetic with 16 decimal digits. I

    // didn't want to change the values of the constant below when I converted

    // it to floating point, so that's why the divisions by 2^16 are there.

    private static final double ROUND_JOIN_THRESHOLD = 1000.0d/65536.0d;

    private static final double C = 0.5522847498307933d;

    private static final int MAX_N_CURVES = 11;

    private DPathConsumer2D out;

    private int capStyle;

    private int joinStyle;

    private double lineWidth2;

    private double invHalfLineWidth2Sq;

    private final double[] offset0 = new double[2];

    private final double[] offset1 = new double[2];

    private final double[] offset2 = new double[2];

    private final double[] miter = new double[2];

    private double miterLimitSq;

    private int prev;

    // The starting point of the path, and the slope there.

    private double sx0, sy0, sdx, sdy;

    // the current point and the slope there.

    private double cx0, cy0, cdx, cdy; // c stands for current

    // vectors that when added to (sx0,sy0) and (cx0,cy0) respectively yield the

    // first and last points on the left parallel path. Since this path is

    // parallel, it's slope at any point is parallel to the slope of the

    // original path (thought they may have different directions), so these

    // could be computed from sdx,sdy and cdx,cdy (and vice versa), but that

    // would be error prone and hard to read, so we keep these anyway.

    private double smx, smy, cmx, cmy;

    private final PolyStack reverse;

    // This is where the curve to be processed is put. We give it

    // enough room to store all curves.

    private final double[] middle = new double[MAX_N_CURVES * 6 + 2];

    private final double[] lp = new double[8];

    private final double[] rp = new double[8];

    private final double[] subdivTs = new double[MAX_N_CURVES - 1];

    // per-thread renderer context

    final DRendererContext rdrCtx;

    // dirty curve

    final DCurve curve;

    /**

     * Constructs a <code>DStroker</code>.

     * @param rdrCtx per-thread renderer context

     */

    DStroker(final DRendererContext rdrCtx) {

        this.rdrCtx = rdrCtx;

        this.reverse = new PolyStack(rdrCtx);

        this.curve = rdrCtx.curve;

    }

    /**

     * Inits the <code>DStroker</code>.

     *

     * @param pc2d an output <code>DPathConsumer2D</code>.

     * @param lineWidth the desired line width in pixels

     * @param capStyle the desired end cap style, one of

     * <code>CAP_BUTT</code>, <code>CAP_ROUND</code> or

     * <code>CAP_SQUARE</code>.

     * @param joinStyle the desired line join style, one of

     * <code>JOIN_MITER</code>, <code>JOIN_ROUND</code> or

     * <code>JOIN_BEVEL</code>.

     * @param miterLimit the desired miter limit

     * @return this instance

     */

    DStroker init(DPathConsumer2D pc2d,

              double lineWidth,

              int capStyle,

              int joinStyle,

              double miterLimit)

    {

        this.out = pc2d;

        this.lineWidth2 = lineWidth / 2.0d;

        this.invHalfLineWidth2Sq = 1.0d / (2.0d * lineWidth2 * lineWidth2);

        this.capStyle = capStyle;

        this.joinStyle = joinStyle;

        double limit = miterLimit * lineWidth2;

        this.miterLimitSq = limit * limit;

        this.prev = CLOSE;

        rdrCtx.stroking = 1;

        return this; // fluent API

    }

    /**

     * Disposes this stroker:

     * clean up before reusing this instance

     */

    void dispose() {

        reverse.dispose();

        if (DO_CLEAN_DIRTY) {

            // Force zero-fill dirty arrays:

            Arrays.fill(offset0, 0.0d);

            Arrays.fill(offset1, 0.0d);

            Arrays.fill(offset2, 0.0d);

            Arrays.fill(miter, 0.0d);

            Arrays.fill(middle, 0.0d);

            Arrays.fill(lp, 0.0d);

            Arrays.fill(rp, 0.0d);

            Arrays.fill(subdivTs, 0.0d);

        }

    }

    private static void computeOffset(final double lx, final double ly,

                                      final double w, final double[] m)

    {

        double len = lx*lx + ly*ly;

        if (len == 0.0d) {

            m[0] = 0.0d;

            m[1] = 0.0d;

        } else {

            len = Math.sqrt(len);

            m[0] =  (ly * w) / len;

            m[1] = -(lx * w) / len;

        }

    }

    // Returns true if the vectors (dx1, dy1) and (dx2, dy2) are

    // clockwise (if dx1,dy1 needs to be rotated clockwise to close

    // the smallest angle between it and dx2,dy2).

    // This is equivalent to detecting whether a point q is on the right side

    // of a line passing through points p1, p2 where p2 = p1+(dx1,dy1) and

    // q = p2+(dx2,dy2), which is the same as saying p1, p2, q are in a

    // clockwise order.

    // NOTE: "clockwise" here assumes coordinates with 0,0 at the bottom left.

    private static boolean isCW(final double dx1, final double dy1,

                                final double dx2, final double dy2)

    {

        return dx1 * dy2 <= dy1 * dx2;

    }

    private void drawRoundJoin(double x, double y,

                               double omx, double omy, double mx, double my,

                               boolean rev,

                               double threshold)

    {

        if ((omx == 0.0d && omy == 0.0d) || (mx == 0.0d && my == 0.0d)) {

            return;

        }

        double domx = omx - mx;

        double domy = omy - my;

        double len = domx*domx + domy*domy;

        if (len < threshold) {

            return;

        }

        if (rev) {

            omx = -omx;

            omy = -omy;

            mx  = -mx;

            my  = -my;

        }

        drawRoundJoin(x, y, omx, omy, mx, my, rev);

    }

    private void drawRoundJoin(double cx, double cy,

                               double omx, double omy,

                               double mx, double my,

                               boolean rev)

    {

        // The sign of the dot product of mx,my and omx,omy is equal to the

        // the sign of the cosine of ext

        // (ext is the angle between omx,omy and mx,my).

        final double cosext = omx * mx + omy * my;

        // If it is >=0, we know that abs(ext) is <= 90 degrees, so we only

        // need 1 curve to approximate the circle section that joins omx,omy

        // and mx,my.

        final int numCurves = (cosext >= 0.0d) ? 1 : 2;

        switch (numCurves) {

        case 1:

            drawBezApproxForArc(cx, cy, omx, omy, mx, my, rev);

            break;

        case 2:

            // we need to split the arc into 2 arcs spanning the same angle.

            // The point we want will be one of the 2 intersections of the

            // perpendicular bisector of the chord (omx,omy)->(mx,my) and the

            // circle. We could find this by scaling the vector

            // (omx+mx, omy+my)/2 so that it has length=lineWidth2 (and thus lies

            // on the circle), but that can have numerical problems when the angle

            // between omx,omy and mx,my is close to 180 degrees. So we compute a

            // normal of (omx,omy)-(mx,my). This will be the direction of the

            // perpendicular bisector. To get one of the intersections, we just scale

            // this vector that its length is lineWidth2 (this works because the

            // perpendicular bisector goes through the origin). This scaling doesn't

            // have numerical problems because we know that lineWidth2 divided by

            // this normal's length is at least 0.5 and at most sqrt(2)/2 (because

            // we know the angle of the arc is > 90 degrees).

            double nx = my - omy, ny = omx - mx;

            double nlen = Math.sqrt(nx*nx + ny*ny);

            double scale = lineWidth2/nlen;

            double mmx = nx * scale, mmy = ny * scale;

            // if (isCW(omx, omy, mx, my) != isCW(mmx, mmy, mx, my)) then we've

            // computed the wrong intersection so we get the other one.

            // The test above is equivalent to if (rev).

            if (rev) {

                mmx = -mmx;

                mmy = -mmy;

            }

            drawBezApproxForArc(cx, cy, omx, omy, mmx, mmy, rev);

            drawBezApproxForArc(cx, cy, mmx, mmy, mx, my, rev);

            break;

        default:

        }

    }

    // the input arc defined by omx,omy and mx,my must span <= 90 degrees.

    private void drawBezApproxForArc(final double cx, final double cy,

                                     final double omx, final double omy,

                                     final double mx, final double my,

                                     boolean rev)

    {

        final double cosext2 = (omx * mx + omy * my) * invHalfLineWidth2Sq;

        // check round off errors producing cos(ext) > 1 and a NaN below

        // cos(ext) == 1 implies colinear segments and an empty join anyway

        if (cosext2 >= 0.5d) {

            // just return to avoid generating a flat curve:

            return;

        }

        // cv is the length of P1-P0 and P2-P3 divided by the radius of the arc

        // (so, cv assumes the arc has radius 1). P0, P1, P2, P3 are the points that

        // define the bezier curve we're computing.

        // It is computed using the constraints that P1-P0 and P3-P2 are parallel

        // to the arc tangents at the endpoints, and that |P1-P0|=|P3-P2|.

        double cv = ((4.0d / 3.0d) * Math.sqrt(0.5d - cosext2) /

                            (1.0d + Math.sqrt(cosext2 + 0.5d)));

        // if clockwise, we need to negate cv.

        if (rev) { // rev is equivalent to isCW(omx, omy, mx, my)

            cv = -cv;

        }

        final double x1 = cx + omx;

        final double y1 = cy + omy;

        final double x2 = x1 - cv * omy;

        final double y2 = y1 + cv * omx;

        final double x4 = cx + mx;

        final double y4 = cy + my;

        final double x3 = x4 + cv * my;

        final double y3 = y4 - cv * mx;

        emitCurveTo(x1, y1, x2, y2, x3, y3, x4, y4, rev);

    }

    private void drawRoundCap(double cx, double cy, double mx, double my) {

        final double Cmx = C * mx;

        final double Cmy = C * my;

        emitCurveTo(cx + mx - Cmy, cy + my + Cmx,

                    cx - my + Cmx, cy + mx + Cmy,

                    cx - my,       cy + mx);

        emitCurveTo(cx - my - Cmx, cy + mx - Cmy,

                    cx - mx - Cmy, cy - my + Cmx,

                    cx - mx,       cy - my);

    }

    // Return the intersection point of the lines (x0, y0) -> (x1, y1)

    // and (x0p, y0p) -> (x1p, y1p) in m[off] and m[off+1]

    private static void computeMiter(final double x0, final double y0,

                                     final double x1, final double y1,

                                     final double x0p, final double y0p,

                                     final double x1p, final double y1p,

                                     final double[] m, int off)

    {

        double x10 = x1 - x0;

        double y10 = y1 - y0;

        double x10p = x1p - x0p;

        double y10p = y1p - y0p;

        // if this is 0, the lines are parallel. If they go in the

        // same direction, there is no intersection so m[off] and

        // m[off+1] will contain infinity, so no miter will be drawn.

        // If they go in the same direction that means that the start of the

        // current segment and the end of the previous segment have the same

        // tangent, in which case this method won't even be involved in

        // miter drawing because it won't be called by drawMiter (because

        // (mx == omx && my == omy) will be true, and drawMiter will return

        // immediately).

        double den = x10*y10p - x10p*y10;

        double t = x10p*(y0-y0p) - y10p*(x0-x0p);

        t /= den;

        m[off++] = x0 + t*x10;

        m[off]   = y0 + t*y10;

    }

    // Return the intersection point of the lines (x0, y0) -> (x1, y1)

    // and (x0p, y0p) -> (x1p, y1p) in m[off] and m[off+1]

    private static void safeComputeMiter(final double x0, final double y0,

                                         final double x1, final double y1,

                                         final double x0p, final double y0p,

                                         final double x1p, final double y1p,

                                         final double[] m, int off)

    {

        double x10 = x1 - x0;

        double y10 = y1 - y0;

        double x10p = x1p - x0p;

        double y10p = y1p - y0p;

        // if this is 0, the lines are parallel. If they go in the

        // same direction, there is no intersection so m[off] and

        // m[off+1] will contain infinity, so no miter will be drawn.

        // If they go in the same direction that means that the start of the

        // current segment and the end of the previous segment have the same

        // tangent, in which case this method won't even be involved in

        // miter drawing because it won't be called by drawMiter (because

        // (mx == omx && my == omy) will be true, and drawMiter will return

        // immediately).

        double den = x10*y10p - x10p*y10;

        if (den == 0.0d) {

            m[off++] = (x0 + x0p) / 2.0d;

            m[off]   = (y0 + y0p) / 2.0d;

            return;

        }

        double t = x10p*(y0-y0p) - y10p*(x0-x0p);

        t /= den;

        m[off++] = x0 + t*x10;

        m[off] = y0 + t*y10;

    }

    private void drawMiter(final double pdx, final double pdy,

                           final double x0, final double y0,

                           final double dx, final double dy,

                           double omx, double omy, double mx, double my,

                           boolean rev)

    {

        if ((mx == omx && my == omy) ||

            (pdx == 0.0d && pdy == 0.0d) ||

            (dx == 0.0d && dy == 0.0d))

        {

            return;

        }

        if (rev) {

            omx = -omx;

            omy = -omy;

            mx  = -mx;

            my  = -my;

        }

        computeMiter((x0 - pdx) + omx, (y0 - pdy) + omy, x0 + omx, y0 + omy,

                     (dx + x0) + mx, (dy + y0) + my, x0 + mx, y0 + my,

                     miter, 0);

        final double miterX = miter[0];

        final double miterY = miter[1];

        double lenSq = (miterX-x0)*(miterX-x0) + (miterY-y0)*(miterY-y0);

        // If the lines are parallel, lenSq will be either NaN or +inf

        // (actually, I'm not sure if the latter is possible. The important

        // thing is that -inf is not possible, because lenSq is a square).

        // For both of those values, the comparison below will fail and

        // no miter will be drawn, which is correct.

        if (lenSq < miterLimitSq) {

            emitLineTo(miterX, miterY, rev);

        }

    }

    @Override

    public void moveTo(double x0, double y0) {

        if (prev == DRAWING_OP_TO) {

            finish();

        }

        this.sx0 = this.cx0 = x0;

        this.sy0 = this.cy0 = y0;

        this.cdx = this.sdx = 1.0d;

        this.cdy = this.sdy = 0.0d;

        this.prev = MOVE_TO;

    }

    @Override

    public void lineTo(double x1, double y1) {

        double dx = x1 - cx0;

        double dy = y1 - cy0;

        if (dx == 0.0d && dy == 0.0d) {

            dx = 1.0d;

        }

        computeOffset(dx, dy, lineWidth2, offset0);

        final double mx = offset0[0];

        final double my = offset0[1];

        drawJoin(cdx, cdy, cx0, cy0, dx, dy, cmx, cmy, mx, my);

        emitLineTo(cx0 + mx, cy0 + my);

        emitLineTo( x1 + mx,  y1 + my);

        emitLineToRev(cx0 - mx, cy0 - my);

        emitLineToRev( x1 - mx,  y1 - my);

        this.cmx = mx;

        this.cmy = my;

        this.cdx = dx;

        this.cdy = dy;

        this.cx0 = x1;

        this.cy0 = y1;

        this.prev = DRAWING_OP_TO;

    }

    @Override

    public void closePath() {

        if (prev != DRAWING_OP_TO) {

            if (prev == CLOSE) {

                return;

            }

            emitMoveTo(cx0, cy0 - lineWidth2);

            this.cmx = this.smx = 0.0d;

            this.cmy = this.smy = -lineWidth2;

            this.cdx = this.sdx = 1.0d;

            this.cdy = this.sdy = 0.0d;

            finish();

            return;

        }

        if (cx0 != sx0 || cy0 != sy0) {

            lineTo(sx0, sy0);

        }

        drawJoin(cdx, cdy, cx0, cy0, sdx, sdy, cmx, cmy, smx, smy);

        emitLineTo(sx0 + smx, sy0 + smy);

        emitMoveTo(sx0 - smx, sy0 - smy);

        emitReverse();

        this.prev = CLOSE;

        emitClose();

    }

    private void emitReverse() {

        reverse.popAll(out);

    }

    @Override

    public void pathDone() {

        if (prev == DRAWING_OP_TO) {

            finish();

        }

        out.pathDone();

        // this shouldn't matter since this object won't be used

        // after the call to this method.