// WEdgeBevel 2.0 alpha5
// (based on WEdgeSlide)

// Author: alexione/mindnever (alexione@mindnever.org)
// Created on 23-11.10.2005.

// USAGE:
//   1. select points of edges
//   2. call plugin in point selection mode

// NOTES:
//   - plugin supports any distant, not only that in slider
//   - when undo-ing WEdgeBevel, you need to undo two times
//   - plugin works only for polygons with at least 3 points

// GREETING:
//   to greent/mindnever (greent@mindnever.org) for an idea and testing

// HISTORY:
//   2.0 - new internal architecture (faster and more correct calculations)
//       - added Distance parameter

@version 2.1
@script modeler
@name WEdgeBevel

npoints;
pointpos; // original positions

// polygons which point belongs to
point_polygonscount; // [pt] = n
point_polygons; // [pt][i] = poly
point_polygonsindex; // [pt][i] = k
point_polygons_newpoint_index; // [pt][i] = i

// points which point is connected to
point_pointscount; // [pt] = n
point_points; // [pt][i] = pt
point_newpoint_index; // [pt][i] = i

// new points
newpointscount;
newpoints; // [k] = pt
newpoints_basepos; // [k] = <x, y, z>
newpoints_deltascount; // [k] = n
newpoints_deltas; // [k][i] = <x, y, z>

edgescount;
edgespoint1, edgespoint2; // edgespoint1[i] < edgespoint2[i]

opt_percent;
opt_uniformness;
opt_maxdist;

need_undo;
firstundo;
lastpercent;

main
{
    selmode(DIRECT);
    editbegin();

    // ----------------------------------------------------
    // check number of selected points
    // ----------------------------------------------------

    npoints = editbegin();
    if(npoints < 2)
    {
        error("You need at least 2 points selected.");
        return;
    }

    editend();
    selmode(USER);
    editbegin();

    // ----------------------------------------------------
    // initialize structures
    // ----------------------------------------------------

    for (i = 1; i <= npoints; ++i)
    {
        pt = points[i];
        pointpos[pt] = pointinfo(pt);

        point_polygonscount[pt] = 0;
        point_polygons[pt] = @0@;
        point_polygonsindex[pt] = @0@;

        point_pointscount[pt] = 0;

        npolygons = pt.polygon;
        if (npolygons)
        {
            ptpolygons = pt.polygon();
            for (j = 1; j <= npolygons; ++j)
            {
                poly = ptpolygons[j];
                npolypoints = poly.pointCount;

                if (npolypoints >= 3)
                {
                    nn = ++point_polygonscount[pt];
                    point_polygons[pt][nn] = poly;

                    ipoint = 1;
                    while ((ipoint <= npolypoints) && (poly.points[ipoint] != pt))
                        ++ipoint;
                    point_polygonsindex[pt][nn] = ipoint;
                    point_polygons_newpoint_index[pt][nn] = 0;

                    n = point_pointscount[pt];

                    pt2 = poly.points[round_n(ipoint - 1, npolypoints)];
                    k = 1;
                    while ((k <= n) && (point_points[pt][k] != pt2))
                        ++k;
                    if (k > n)
                    {
                        point_pointscount[pt] = ++n;
                        point_points[pt][n] = pt2;
                        point_newpoint_index[pt][n] = 0;
                    }

                    pt2 = poly.points[round_n(ipoint + 1, npolypoints)];
                    k = 1;
                    while ((k <= n) && (point_points[pt][k] != pt2))
                        ++k;
                    if (k > n)
                    {
                        point_pointscount[pt] = ++n;
                        point_points[pt][n] = pt2;
                        point_newpoint_index[pt][n] = 0;
                    }
                }
            }
        }
    }

    // ----------------------------------------------------
    // check edges, update model structure
    // ----------------------------------------------------

    newpointscount = 0;
    newpolygonscount = 0;
    edgescount = 0;
    need_undo = false;

    // create beveling rectangles
    for (i = 1; i <= npoints; ++i)
    {
        pt = points[i];
        npolygons = point_polygonscount[pt];
        for (j = 1; j <= npolygons; ++j)
        {
            poly = point_polygons[pt][j];
            npolypoints = poly.pointCount;

            ipoint = point_polygonsindex[pt][j];
            check_polygonedge(poly, round_n(ipoint - 1, npolypoints));
            check_polygonedge(poly, ipoint);
        }
    }

    // create newpoints for edges around points
    for (i = 1; i <= npoints; ++i)
    {
        pt = points[i];
        nptpoints = point_pointscount[pt];
        for (j = 1; j <= nptpoints; ++j)
        {
            pt2 = point_points[pt][j];
            if (pt2 > npoints)
                newpt = ensure_newpoint(pt, pt2, 0);
        }
    }

    // fill holes around points
    for (i = 1; i <= npoints; ++i)
    {
        pt = points[i];
        update_point(pt);
    }

    // update polygons around points
    for (i = 1; i <= npoints; ++i)
    {
        pt = points[i];
        npolygons = point_polygonscount[pt];
        for (j = 1; j <= npolygons; ++j)
        {
            poly = point_polygons[pt][j];
            if (poly)
                update_polygon(poly);
        }
    }

    // remove points
    for (i = npoints; i > 0; --i)
    {
        pt = points[i];
        rempoint(pt);
    }

    // calculate maxdist
    maxdist = 0;
    for (i = 1; i <= newpointscount; i++)
    {
        n = newpoints_deltascount[i];
        for (j = 1; j <= n; ++j)
        {
            delta = newpoints_deltas[i][j];
            d = vmag(delta);
            if (!maxdist || (d < maxdist))
                maxdist = d;
        }
    }

    editend();

    for (i = 1; i <= newpointscount; i++)
        selpoint(SET, POINTID, newpoints[i]);

    // ----------------------------------------------------
    // create interface
    // ----------------------------------------------------

    firstundo = true;
    lastpercent = 0;

    reqbegin("WEdgeBevel");
    reqsize(200, 110);

    opt_percent = 0.01;
    opt_uniformness = 0;
    opt_maxdist = maxdist;
    slide_points(opt_percent, opt_uniformness, opt_maxdist);

    cPercent = ctlminislider("Percent", opt_percent, 0, 100);
    ctlposition(cPercent, 26, 5, 149);
    ctlrefresh(cPercent, "update_percent");

    cUniformness = ctlminislider("Uniformness", opt_uniformness, 0, 100);
    ctlposition(cUniformness, 5, 30, 170);
    ctlrefresh(cUniformness, "update_uniformness");

    cMaxDist = ctlminislider("Distance", opt_maxdist * 100, 0, opt_maxdist * 1000);
    ctlposition(cMaxDist, 21, 55, 154);
    ctlrefresh(cMaxDist, "update_distance");

    if (!reqpost())
    {
        slide_points(0, 0, 0);
        if (need_undo)
            undo();
        return;
    }
}


// ------------------------------------------------------------
// checks polygon edge [i, i+1] in polygon poly
// ------------------------------------------------------------
check_polygonedge: poly, i
{
    npolypoints = poly.pointCount;
    i1 = round_n(i + 1, npolypoints);

    a1 = poly.points[i];
    a2 = poly.points[round_n(i - 1, npolypoints)];

    b1 = poly.points[i1];
    b2 = poly.points[round_n(i1 + 1, npolypoints)];

    if ((a1 <= npoints) && (b1 <= npoints) && !edgechecked(a1, b1))
    {
        //info("poly " + poly + " [" + a1 + " " + b1 + "]");

        ipoly2 = find_other_polygon_index(a1, b1);
        if (ipoly2)
        {
            poly2 = point_polygons[a1][ipoly2];
            npolypoints2 = poly2.pointCount;

            j1 = point_polygonsindex[a1][ipoly2];
            j = round_n(j1 - 1, npolypoints2);

//            msg = "poly2 " + poly2 + " (" + npolypoints2 + ") :";
//            for (k = 1; k <= npolypoints; k++)
//            {
//                msg = msg + " " + poly2.points[k];
//                if ((k == j) || (k == j1))
//                    msg = msg + "*";
//            }
//            info(msg);

            a3 = poly2.points[round_n(j1 + 1, npolypoints2)];
            b3 = poly2.points[round_n(j - 1, npolypoints2)];

//            info("edge " + a1 + "[" + a2 + ":" + a3 + "] " + b1 + "[" + b2 + ":" + b3 + "]");

            newpoly_points[1] = ensure_newpoint(a1, a2, poly);
            newpoly_points[2] = ensure_newpoint(a1, a3, poly2);
            newpoly_points[3] = ensure_newpoint(b1, b3, poly2);
            newpoly_points[4] = ensure_newpoint(b1, b2, poly);
            addpolygon(newpoly_points);

            need_undo = true;

            if (a1 > b1)
            {
                ab = a1;
                a1 = b1;
                b1 = ab;
            }

            ++edgescount;
            edgespoint1[edgescount] = a1;
            edgespoint2[edgescount] = b1;
        }
    }
}


// ------------------------------------------------------------
// ensure valid point for pt1-pt2 in polygon poly
// ------------------------------------------------------------
ensure_newpoint: pt1, pt2, poly
{
    if (pt2 > npoints)
    {
        ipoint = find_point_pointsindex(pt1, pt2);
        inewpoint = point_newpoint_index[pt1][ipoint];
        if (!inewpoint)
        {
            newpos = pointinfo(pt1);
            newpt = addpoint(newpos);
            need_undo = true;

            inewpoint = ++newpointscount;
            point_newpoint_index[pt1][ipoint] = inewpoint;

            newpoints[inewpoint] = newpt;
            newpoints_basepos[inewpoint] = newpos;
            newpoints_deltascount[inewpoint] = 1;
            newpoints_deltas[inewpoint][1] = pointinfo(pt2) - pointinfo(pt1);
        }
        return newpoints[inewpoint];
    }
    else
    {
        ipoly = find_point_polygonsindex(pt1, poly);
        inewpoint = point_polygons_newpoint_index[pt1][ipoly];
        if (!inewpoint)
        {
            newpos = pointinfo(pt1);
            newpt = addpoint(newpos);
            need_undo = true;

            inewpoint = ++newpointscount;
            point_polygons_newpoint_index[pt1][ipoly] = inewpoint;

            newpoints[inewpoint] = newpt;
            newpoints_basepos[inewpoint] = newpos;
            newpoints_deltascount[inewpoint] = 1;
            newpoints_deltas[inewpoint][1] = pointinfo(pt2) - pointinfo(pt1);
        }
        else
            newpoints_deltas[inewpoint][++newpoints_deltascount[inewpoint]] = pointinfo(pt2) - pointinfo(pt1);

        return newpoints[inewpoint];
    }
}


// ------------------------------------------------------------
// fills hole near point
// ------------------------------------------------------------
update_point: pt
{
    npointpolygons = point_polygonscount[pt];
    ntotal = npointpolygons + point_pointscount[pt];
    holepointscount = 0;

    D1 = <0, 0, 0>;
    D2 = <0, 0, 0>;
    D3 = <0, 0, 0>;
    D12 = 0;
    D123 = 0;
    nD = 0;

    for (i = 1; i <= ntotal; ++i)
    {
        if (i <= npointpolygons)
            inewpoint = point_polygons_newpoint_index[pt][i];
        else
            inewpoint = point_newpoint_index[pt][i - npointpolygons];

        if (inewpoint)
        {
            pt2 = newpoints[inewpoint];
            delta = interpolate_newpoint_delta(inewpoint);

            ++nD;
            if (nD == 1)
                D1 = delta;
            else if (nD == 2)
            {
                D2 = delta;
                D12 = normalize(cross3d(D1, D2));
            }
            else
            {
                aD123 = abs(dot3d(D12, normalize(delta)));
                if (aD123 >= D123)
                {
                    D123 = aD123;
                    D3 = delta;
                }
            }
        }
    }

    //info("D1 = " + D1 + "   D2 = " + D2 + "   D3 = " + D3 + "   D12 = " + D12 + "   D123 = " + D123);

    maxM = 0.0;

    if (D123 < 0.001)
    {
        for (j = 1; j <= point_polygonscount[pt]; ++j)
        {
            polyN = polynormal(point_polygons[pt][j]);
            if (vmag(polyN) > 0.001)
            {
                m = abs(dot3d(D12, polyN));
                if ((m > 0.999) && (m > max))
                {
                    maxM = m;
                    N = polyN;
                }
            }
        }
    }

    if (maxM < 0.001)
    {
        N = normalize(cross3d(D3 - D1, D2 - D1));
        if (dot3d(D1, N) > 0.001)
            N = -N;
    }

    if (vmag(N) < 0.001)
        N = <1, 0, 0>;

    dTx = abs(N.x);
    dTy = abs(N.y);
    dTz = abs(N.z);

    //info("" + pt + " -> <" + N + ">   dT = <" + dTx + "," + dTy + "," + dTz + ">");

    if ((dTx <= dTy) && (dTx <= dTz))
        T = <1, 0, 0>;
    else if (dTy <= dTz)
        T = <0, 1, 0>;
    else
        T = <0, 0, 1>;

    A = normalize(cross3d(T, N));
    B = cross3d(A, N);

    //info("" + pt + " -> <" + N + ">  T = <" + T + ">   A = <" + A + ">   B = <" + B + ">");

    for (i = 1; i <= ntotal; ++i)
    {
        if (i <= npointpolygons)
            inewpoint = point_polygons_newpoint_index[pt][i];
        else
            inewpoint = point_newpoint_index[pt][i - npointpolygons];

        if (inewpoint)
        {
            pt2 = newpoints[inewpoint];
            delta = interpolate_newpoint_delta(inewpoint);
            pt2pos = newpoints_basepos[inewpoint] + delta;

            if (holepointscount < 2)
            {
                ++holepointscount;
                holepoints[holepointscount] = pt2;
                holepoints_pos[holepointscount] = pt2pos;
                if (holepointscount == 1)
                    D1 = delta;
                else
                    D2 = delta;
            }
            else
            {
/*
                D12 = normalize(cross3d(D1, D2));
                D123 = abs(dot3d(D12, D3));

                if ((holepointscount == 2) || (D123 > 0.001))
                {
                    max = 0;

                    if (D123 < 0.001)
                    {
                        for (j = 1; j <= point_polygonscount[pt]; ++j)
                        {
                            polyN = polynormal(point_polygons[pt][j]);
                            if (vmag(polyN) > 0.001)
                            {
                                m = abs(dot3d(D12, polyN));
                                if ((m > 0.999) && (m > max))
                                {
                                    max = m;
                                    N = polyN;
                                }
                            }
                        }
                    }

                    if (max < 0.001)
                    {
                        D3 = delta;
                        N = normalize(cross3d(D3 - D1, D2 - D1));
                        if (dot3d(D1, N) > 0.001)
                            N = -N;
                    }

                    if (vmag(N) < 0.001)
                        N = <1, 0, 0>;

                    dTx = abs(N.x);
                    dTy = abs(N.y);
                    dTz = abs(N.z);

                    //info("" + pt + " -> <" + N + ">   dT = <" + dTx + "," + dTy + "," + dTz + ">");

                    if ((dTx <= dTy) && (dTx <= dTz))
                        T = <1, 0, 0>;
                    else if (dTy <= dTz)
                        T = <0, 1, 0>;
                    else
                        T = <0, 0, 1>;

                    A = normalize(cross3d(T, N));
                    B = cross3d(A, N);

                    //info("" + pt + " -> <" + N + ">  T = <" + T + ">   A = <" + A + ">   B = <" + B + ">");
                }
*/

                T = proj(pt2pos, N, A, B);

                j = 1;
                ok = true;

                while (ok && (j <= holepointscount - 1)) {
                    P = proj(holepoints_pos[j], N, A, B);
                    Q = proj(holepoints_pos[j + 1], N, A, B);

                    t = (Q.y - P.y) * T.x - (Q.x - P.x) * T.y + P.y * Q.x - P.x * Q.y;
                    if (abs(t) < 0.001)
                    {
                        d = Q.x - P.x;
                        t = T.x - P.x;
                        if (!d)
                        {
                            d = Q.y - P.y;
                            t = T.y - P.y;
                        }
                        if (d)
                        {
                            t = t / d;
                            if ((t >= 0) && (t <= 1))
                                ok = false;
                        }
                    }
                    if (t < 0)
                        ok = false;

                    if (ok)
                        ++j;
                }

                ++j;
                ++holepointscount;

                for (j1 = holepointscount; j1 > j; --j1)
                {
                    holepoints[j1] = holepoints[j1 - 1];
                    holepoints_pos[j1] = holepoints_pos[j1 - 1];
                }

                holepoints[j] = pt2;
                holepoints_pos[j] = pt2pos;
            }
        }
    }

    if (holepointscount >= 3)
        addpolygon(holepoints);
}


// ------------------------------------------------------------
// projection of point P on plane N; returns (u, v, t)
// ------------------------------------------------------------
proj: P, N, A, B
{
    t = dot3d(P, N) / dot3d(N, N);
    S = P - t * N;
    u = dot3d(S, A) / dot3d(A, A);
    v = dot3d(S, B) / dot3d(B, B);
    return <u, v, t>;
}


// ------------------------------------------------------------
// interpolates newpoint
// ------------------------------------------------------------
interpolate_newpoint_delta: inewpoint
{
    delta = <0, 0, 0>;
    ndeltas = newpoints_deltascount[inewpoint];
    for (i = 1; i <= ndeltas; ++i)
        delta = delta + newpoints_deltas[inewpoint][i];
    return delta;
}


// ------------------------------------------------------------
// update points of polygon after beveling
// ------------------------------------------------------------
update_polygon: poly
{
    npolypoints = poly.pointCount;
    npolypoints2 = 0;

    for (i = 1; i <= npolypoints; ++i)
    {
        pt = poly.points[i];
        if (pt <= npoints)
        {
            k = find_point_polygonsindex(pt, poly);
            inewpoint = point_polygons_newpoint_index[pt][k];
            if (inewpoint)
                poly2_points[++npolypoints2] = newpoints[inewpoint];
            else
            {
                // check left newpoint
                pt2 = poly.points[round_n(i - 1, npolypoints)];
                k = find_point_pointsindex(pt, pt2);
                inewpoint = point_newpoint_index[pt][k];
                if (inewpoint)
                    poly2_points[++npolypoints2] = newpoints[inewpoint];

                // check right newpoint
                pt2 = poly.points[round_n(i + 1, npolypoints)];
                k = find_point_pointsindex(pt, pt2);
                inewpoint = point_newpoint_index[pt][k];
                if (inewpoint)
                    poly2_points[++npolypoints2] = newpoints[inewpoint];
            }
        }
        else
            poly2_points[++npolypoints2] = pt;
    }

/*
    msg = "newpoly:";
    for (i = 1; i <= npolypoints2; ++i)
        msg = msg + " " + poly2_points[i];
    info(msg);
*/

    addpolygon(poly2_points);

    for (i = 1; i <= npolypoints; ++i)
    {
        pt = poly.points[i];
        if (pt <= npoints)
            point_polygons[pt][find_point_polygonsindex(pt, poly)] = 0;
    }

    rempoly(poly);
}


// ------------------------------------------------------------
// find index of other polygon for the edge (in respect to pt1)
// ------------------------------------------------------------
find_other_polygon_index: pt1, pt2
{
    ipoly2 = point_polygonscount[pt1];
    ok = false;

    while (ipoly2 && !ok)
    {
        poly2 = point_polygons[pt1][ipoly2];
        npolypoints2 = poly2.pointCount;

        j1 = point_polygonsindex[pt1][ipoly2];
        j = round_n(j1 - 1, npolypoints2);

        if (poly2.points[j] == pt2)
            ok = true;
        else
            --ipoly2;
    }

    return ipoly2;
}


// ------------------------------------------------------------
// find index so that point_points[pt1][index] = pt2
// ------------------------------------------------------------
find_point_pointsindex: pt1, pt2
{
    if (pt1 <= npoints)
    {
        k = point_pointscount[pt1];
        while (k && (point_points[pt1][k] != pt2))
            k--;
        return k;
    }
    else
        return 0;
}


// ------------------------------------------------------------
// find index so that point_polygons[pt][index] = poly
// ------------------------------------------------------------
find_point_polygonsindex: pt, poly
{
    if (pt <= npoints)
    {
        k = point_polygonscount[pt];
        while (k && (point_polygons[pt][k] != poly))
            k--;
        return k;
    }
    else
        return 0;
}


// ------------------------------------------------------------
// checks if edges is already checked
// ------------------------------------------------------------
edgechecked: pt1, pt2
{
    if (pt1 > pt2)
    {
        pt12 = pt1;
        pt1 = pt2;
        pt2 = pt12;
    }

    k = edgescount;
    while (k && ((edgespoint1[k] != pt1) || (edgespoint2[k] != pt2)))
        --k;

    return (k != 0);
}


// ------------------------------------------------------------
// update methods
// ------------------------------------------------------------
update_percent: value
{
    opt_percent = value / 100;
    slide_points(opt_percent, opt_uniformness, opt_maxdist);
}

update_uniformness: value
{
    opt_uniformness = value / 100;
    slide_points(opt_percent, opt_uniformness, opt_maxdist);
}

update_distance: value
{
    opt_maxdist = value / 100;
    slide_points(opt_percent, opt_uniformness, opt_maxdist);
}


// ------------------------------------------------------------
// slides all points
// ------------------------------------------------------------
slide_points: percent, uniformness, maxdist
{
    if (firstundo)
        firstundo = false;
    else if (lastpercent)
        undo();

    if (percent)
    {
        n = 0;
        editbegin();

        percent_maxdist = percent * maxdist;

        for (inewpoint = 1; inewpoint <= newpointscount; ++inewpoint)
        {
            oldpos = pointinfo(newpoints[inewpoint]);
            newpos = newpoints_basepos[inewpoint];

            ndeltas = newpoints_deltascount[inewpoint];
            for (i = 1; i <= ndeltas; ++i)
            {
                delta = newpoints_deltas[inewpoint][i];

                d = vmag(delta);
                if (d)
                    percent2 = percent_maxdist / d;
                else
                    percent2 = 0;

                newpos = newpos + ((1 - uniformness) * percent + uniformness * percent2) * delta;
            }

            if ((oldpos.x != newpos.x) || (oldpos.y != newpos.y) || (oldpos.z != newpos.z))
            {
                pointmove(newpoints[inewpoint], newpos);
                ++n;
            }
        }

        editend();
        if (!n)
            percent = 0;
    }

    lastpercent = percent;
}


// ------------------------------------------------------------
// round i to [1..n]
// ------------------------------------------------------------
round_n: i, n
{
    while (i < 1)
        i = i + n;
    while (i > n)
        i = i - n;
    return i;
}