DCGO/Assets/AddOn/Shapes2D/Scripts/PolyMap.cs

namespace Shapes2D {

    using UnityEngine;

    class PolyMap {
        struct DistanceResult {
            public int index, index2;
        }

        // http://stackoverflow.com/questions/849211/shortest-distance-between-a-point-and-a-line-segment
        static float DistanceToLineSegment(Vector2 pos, Vector2 p1, Vector2 p2) {
            // vector operations are pretty slow!  do it all manually...
            float dx = p2.x - p1.x;
            float dy = p2.y - p1.y;
            float dist = Mathf.Sqrt(dx * dx + dy * dy);
            float l2 = dist * dist;
            float c1x = pos.x - p1.x;
            float c1y = pos.y - p1.y;
            float c2x = p2.x - p1.x;
            float c2y = p2.y - p1.y;
            float dot = c1x * c2x + c1y * c2y;
            dot /= l2;
            float t = dot < 0 ? 0 : dot;
            t = t > 1 ? 1 : t;
            float projx = p1.x + t * dx;
            float projy = p1.y + t * dy;
            dx = projx - pos.x;
            dy = projy - pos.y;
            return Mathf.Sqrt(dx * dx + dy * dy);
        }

        static DistanceResult GetClosestLineSegments(Vector2 pos, Vector2[] vertices) {
            DistanceResult dr;
            dr.index = -1;
            dr.index2 = -1;
            float closestDistance = -1;
            float closestDistance2 = -1;
            int j = vertices.Length - 1;
            for (int i = 0; i < vertices.Length; i++) {
                float dist = DistanceToLineSegment(pos, vertices[i], vertices[j]);
                if (dr.index == -1 || dist < closestDistance) {
                    dr.index2 = dr.index;
                    closestDistance2 = closestDistance;
                    dr.index = i;
                    closestDistance = dist;
                } else if (dr.index2 == -1 || dist < closestDistance2) {
                    dr.index2 = i;
                    closestDistance2 = dist;
                }
                j = i;
            }
            return dr;
        }

        // thanks to http://alienryderflex.com/polygon/.  if the number of nodes (points
        // where a polygon line crosses the horizontal axis of the test position) to the
        // left of the test position is odd, then the point is inside the poly!
        static bool PointIsInsidePoly(Vector2 pos, Vector2[] vertices) {
            bool oddNodes = false;
            int j = vertices.Length - 1;
            for (int i = 0; i < vertices.Length; i++) {
                Vector2 vi = vertices[i];
                Vector2 vj = vertices[j];
                if ((vi.y < pos.y && vj.y >= pos.y || vj.y < pos.y && vi.y >= pos.y)
                        && (vi.x <= pos.x || vj.x <= pos.x)) {
                    if (vi.x + (pos.y - vi.y) / (vj.y - vi.y) * (vj.x - vi.x) < pos.x)
                        oddNodes = !oddNodes; 
                }
                j = i;
            }
            return oddNodes;
        }

        static bool IntersectsVerticalLineSegment(Vector2 v1, Vector2 v2, Vector2 p1, Vector2 p2) {
            float pminx = p1.x < p2.x ? p1.x : p2.x;
            float pminy = p1.y < p2.y ? p1.y : p2.y;
            // float vminx = v1.x < v2.x ? v1.x : v2.x;
            float vminy = v1.y < v2.y ? v1.y : v2.y;
            float pmaxx = p1.x > p2.x ? p1.x : p2.x;
            float pmaxy = p1.y > p2.y ? p1.y : p2.y;
            // float vmaxx = v1.x > v2.x ? v1.x : v2.x;
            float vmaxy = v1.y > v2.y ? v1.y : v2.y;
            if (pminx > v1.x || pmaxx < v1.x || pmaxy < vminy || pminy > vmaxy)
                return false;
            if (p2.x == p1.x)
                return p1.x == v1.x && ((pminy >= vminy && pminy <= vmaxy) || (pmaxy >= vminy && pmaxy <= vmaxy));
            float m = (p2.y - p1.y) / (p2.x - p1.x);
            float b = p2.y - m * p2.x;
            float y = m * v1.x + b;
            return y >= vminy && y <= vmaxy;
        }

        static bool IntersectsHorizontalLineSegment(Vector2 v1, Vector2 v2, Vector2 p1, Vector2 p2) {
            float pminx = p1.x < p2.x ? p1.x : p2.x;
            float pminy = p1.y < p2.y ? p1.y : p2.y;
            float vminx = v1.x < v2.x ? v1.x : v2.x;
            // float vminy = v1.y < v2.y ? v1.y : v2.y;
            float pmaxx = p1.x > p2.x ? p1.x : p2.x;
            float pmaxy = p1.y > p2.y ? p1.y : p2.y;
            float vmaxx = v1.x > v2.x ? v1.x : v2.x;
            // float vmaxy = v1.y > v2.y ? v1.y : v2.y;
            if (pminx > vmaxx || pmaxx < vminx || pmaxy < v1.y || pminy > v1.y)
                return false;
            if (p2.x == p1.x)
                return p1.x >= vminx && p2.x <= vmaxx;   
            float m = (p2.y - p1.y) / (p2.x - p1.x);
            float b = p2.y - m * p2.x;
            float x = (v1.y - b) / m;
            return x >= vminx && x <= vmaxx;
        }

        static int RectIntersectsPolyEdge(Vector2 tl, Vector2 tr, Vector2 bl, Vector2 br,
                Vector2[] vertices, bool[] results) {
            int edgeCount = 0;
            int j = vertices.Length - 1;
            for (int i = 0; i < vertices.Length; i++) {
                Vector2 p1 = vertices[i];
                Vector2 p2 = vertices[j];
                bool top = IntersectsHorizontalLineSegment(tl, tr, p1, p2);
                bool bottom = IntersectsHorizontalLineSegment(bl, br, p1, p2);
                bool left = IntersectsVerticalLineSegment(tl, bl, p1, p2);
                bool right = IntersectsVerticalLineSegment(tr, br, p1, p2);
                results[i] = top || bottom || left || right;
                if (top || bottom || left || right)
                    edgeCount ++;
                j = i;
            }
            return edgeCount;
        }

        static int RectContainsVertex(Vector2 tl, Vector2 tr, Vector2 bl, Vector2 br,
                Vector2[] vertices, bool[] results) {
            int vertCount = 0;
            int i = 0;
            foreach (Vector2 v in vertices) {
                results[i] = v.x >= tl.x && v.x <= tr.x && v.y >= bl.y && v.y <= tl.y;
                if (results[i])
                    vertCount ++;
                i ++;
            }
            return vertCount;
        }

        // which side of the line is the point on?  consistent winding means this tells us 
        // if a point is on the inside of a convex polygon or not (or a convex section of a
        // concave poly which is what we care about), assuming it isn't excluded by any of 
        // the other lines.
        static bool PointLineTest(Vector2 pos, Vector2 p1, Vector2 p2) {
            return (pos.x - p1.x) * (p2.y - p1.y) - (pos.y - p1.y) * (p2.x - p1.x) > 0;
        }

        // maybe could use Vector2.Angle() instead?
        static float GetAngleBetween(Vector2 v1, Vector2 v2) {
            float a1 = Mathf.Atan2(v1.y, v1.x) * Mathf.Rad2Deg;
            float a2 = Mathf.Atan2(v2.y, v2.x) * Mathf.Rad2Deg;
            if (a1 < 0)
                a1 += 360;
            if (a2 < 0)
                a2 += 360;
            float result = a1 - a2;
            if (result < 0)
                result += 360;
            return result;
        }

        public static void GeneratePolyMap(Vector2[] vertices, Texture2D polyMap) {
            if (polyMap.width != polyMap.height)
                throw new System.InvalidOperationException("Poly map texture must be square!");
            int resolution = polyMap.width;
            Vector2 tex = new Vector2(1f / resolution, 1f / resolution);
            bool[] edgeIntersections = new bool[vertices.Length];
            bool[] vertIntersections = new bool[vertices.Length];
            // for each texel
            for (int x = 0; x < resolution; x++) {
                for (int y = 0; y < resolution; y++) {
                    Vector2 center = new Vector2(x, y) * tex.x + tex / 2 - new Vector2(0.5f, 0.5f);
                    Vector2 tl = center + new Vector2(-tex.x / 2, tex.y / 2);
                    Vector2 tr = center + tex / 2;
                    Vector2 bl = center - tex / 2;
                    Vector2 br = center + new Vector2(tex.x / 2, -tex.y / 2);
                    int edgeCount = RectIntersectsPolyEdge(tl, tr, bl, br, vertices, edgeIntersections);
                    bool inside = PointIsInsidePoly(center, vertices);
                    // get the closest line segments to the texel center.  it's much faster
                    // for the shader to just look at a few line segments than all of them, but 
                    // when the closest lines to the center of the texel aren't the closest for all 
                    // pixels in the texel there will be rendering flaws (though hopefully one of them 
                    // will be the closest one to each pixel in reasonably spaced polygons).
                    // note that in most cases we could do a simpler algorithm that just checks the
                    // closest of the two nearest lines in the fragment shader and colors pixels
                    // inside of the winner, but it gets fuzzy in many cases where fragments are
                    // exactly as far (or almost exactly as far) from each line.
                    DistanceResult dr = GetClosestLineSegments(center, vertices);
                    // we'll send a 'mode' to the shader indicating what it should do.
                    // 0 = all pixels in the texel are outside the poly
                    // 1 = all pixels in the texel are inside the poly
                    // 2 = must be inside the closest line
                    // 3 = must be inside both lines
                    // 4 = must be inside either line
                    int mode = 0;
                    if (edgeCount == 0) {
                        // no intersection, so all points are on the same side of the poly
                        mode = inside ? 1 : 0;
                    } else if (edgeCount == 1) {
                        // intersects with 1 edge, just be inside that edge.
                        // make sure dr.index is the intersecting edge - it's possible it isn't.
                        mode = 2;
                        if (!edgeIntersections[dr.index]) {
                            int temp = dr.index;
                            dr.index = dr.index2;
                            dr.index2 = temp;
                        }
                        // mode = 5;
                    } else if (RectContainsVertex(tl, tr, bl, br, vertices, vertIntersections) > 0) {
                        // the texel contains >= 1 vertex, so we need to get the angle between
                        // the vert's lines to figure out what to do.  multiple verts in a single texel 
                        // are not supported.
                        // find the relevant vertex
                        Vector2 v = Vector2.zero;
                        int i;
                        for (i = 0; i < vertices.Length; i++) {
                            if (vertIntersections[i]) {
                                v = vertices[i];
                                break;
                            }
                        }
                        // find the neighboring verts.  make sure their lines are the closest segments too.
                        // v1 -- v -- v2
                        dr.index = i;
                        int j = i == 0 ? vertices.Length - 1 : i - 1;
                        Vector2 v1 = vertices[j];
                        j = i == vertices.Length - 1 ? 0 : i + 1;
                        dr.index2 = j;
                        Vector2 v2 = vertices[j];
                        // find the angle between the two lines
                        float angle = GetAngleBetween(v1 - v, v2 - v);
                        // each pixel needs to be inside the joint
                        if (angle <= 180) {
                            mode = 3;
                        } else {
                            mode = 4;
                        }
                        // mode = 5;
                    } else {
                        // edge count is > 1 and no vertex intersection.
                        // we can tell if the lines are facing in the same direction by using the
                        // center as a reference and checking if it is on the same or different
                        // side of each line, and whether or not it's inside the poly.
                        int found = 0;
                        bool test1 = false, test2 = false;
                        for (int i = 0; i < vertices.Length; i++) { 
                            if (!edgeIntersections[i])
                                continue;
                            int j = i == 0 ? vertices.Length - 1 : i - 1;
                            if (found == 0)
                                test1 = PointLineTest(center, vertices[i], vertices[j]);
                            else
                                test2 = PointLineTest(center, vertices[i], vertices[j]);
                            found ++;
                            if (found == 2)
                                break;
                        }
                        if ((test1 == test2) && inside)
                            mode = 3;
                        else if ((test1 == test2) && !inside)
                            mode = 4;
                        else if ((test1 != test2) && inside)
                            mode = 4;
                        else if ((test1 != test2) && !inside)
                            mode = 3;
                        // mode = 5;
                    }
                    polyMap.SetPixel(x, y, new Color(dr.index / 256f, dr.index2 / 256f, 0, mode / 256f));
                }
            }
            polyMap.Apply();
        }
    }

}