VectorTile.cs

using Mapbox.Vector.Tile;
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Threading.Tasks;
using UnityEditor;
using UnityEngine;
using UnityEngine.Networking;
using static Wander.Easing;

namespace Wander
{
    // Always multiple of 3. Each 3 form a triangle.
    public class TriangulatedPolygon
    {
        public List<Vector2> vertices;  
        public List<Vector2> mins;
        public List<Vector2> maxs;
        public List<float>   denoms;

        public void OptimizeForIsPointInTriangle()
        {
            if ( vertices == null ) return; // Non poly layers have this.

            mins   = new List<Vector2>( vertices.Count / 3 );
            maxs   = new List<Vector2>( vertices.Count / 3 );
            denoms = new List<float>( vertices.Count / 3 );

            for ( int i = 0; i < vertices.Count; i += 3 )
            {
                float minx = float.MaxValue;
                float miny = float.MaxValue;    
                if (vertices[i+0].x < minx) minx = vertices[i].x;
                if (vertices[i+0].y < miny) miny = vertices[i].y;
                if (vertices[i+1].x < minx) minx = vertices[i+1].x;
                if (vertices[i+1].y < miny) miny = vertices[i+1].y;
                if (vertices[i+2].x < minx) minx = vertices[i+2].x;
                if (vertices[i+2].y < miny) miny = vertices[i+2].y;
                mins.Add( new Vector2( minx, miny ) );

                float maxx = float.MinValue;
                float maxy = float.MinValue;
                if (vertices[i+0].x > maxx) maxx = vertices[i].x;
                if (vertices[i+0].y > maxy) maxy = vertices[i].y;
                if (vertices[i+1].x > maxx) maxx = vertices[i+1].x;
                if (vertices[i+1].y > maxy) maxy = vertices[i+1].y;
                if (vertices[i+2].x > maxx) maxx = vertices[i+2].x;
                if (vertices[i+2].y > maxy) maxy = vertices[i+2].y;
                maxs.Add( new Vector2( maxx, maxy ) );

                // float denominator = ((vertex2.y - vertex3.y) * (vertex1.x - vertex3.x) + (vertex3.x - vertex2.x) * (vertex1.y - vertex3.y));
                float denominator = ((vertices[i+1].y - vertices[i+2].y) * (vertices[i].x - vertices[i+2].x) + (vertices[i+2].x - vertices[i+1].x) * (vertices[i].y - vertices[i+2].y));
                denoms.Add( 1.0f / denominator );
            }
        }
    }

    public class VectorTile
    {
        public bool DownloadStarted => started;
        public bool Valid => valid;
        public bool Finished => finished;
        public bool Triangulated => triangulated;

        private bool started;
        private bool valid;
        private bool finished;
        private bool triangulated;
        private Task parseTileTask;
        private List<VectorTileLayer> layers;
        private List<List<TriangulatedPolygon>> polygonLayers;

        internal UnityWebRequest request;

        public void StartDownload()
        {
            Debug.Assert(!started);
            request.SendWebRequest();
            started = true;
        }

        public bool IsFinished()
        {
            if (finished)
                return true;

            if (!request.isDone)
                return false;

            if (request.result == UnityWebRequest.Result.Success)
            {
                if (parseTileTask == null)
                {
                    var data = request.downloadHandler.data; // call on mainthread.
                    parseTileTask = Task.Run( () =>
                    {
                        var stream = new MemoryStream( data );
                        layers = VectorTileParser.Parse( stream );
                    } );
                }
                else if (parseTileTask.IsCompleted)
                {
                    valid = parseTileTask.IsCompletedSuccessfully;
                    finished = true;
                    parseTileTask = null;
                }
            }

            return finished;
        }

        // Number of failed polys to triangulate are returned.
        public int Triangulate()
        {
            if (triangulated )
                return 0;
            int numFailedPolys = 0;
            polygonLayers = new List<List<TriangulatedPolygon>>();
            List<double> vertices = new List<double>();
            List<int> holeIndices = new List<int>();
            for ( int i =0; i < layers.Count; i++ )
            {
                var features = layers[i].VectorTileFeatures;
                var polygons = new List<TriangulatedPolygon>();
                for (int j = 0; j< features.Count; j++)
                {
                    polygons.Add( new TriangulatedPolygon() ); // Add empty to ensure list(layer) of lists(features) match.
                    if (features[j].GeometryType != Tile.GeomType.Polygon)
                    {
                        continue;
                    }
                    vertices.Clear();
                    holeIndices.Clear();
                    var rings = features[j].Geometry;
                    for (int k = 0;k < rings.Count;k++)
                    {
                        if (k != 0) // if is not first ring, this is a hole
                        {
                            holeIndices.Add( vertices.Count / 2 );
                        }
                        var ring = rings[k];
                        for (int q = 0;q < ring.Count;q++)
                        {
                            vertices.Add( ring[q].X );
                            vertices.Add( ring[q].Y );
                        }
                    }
                    try
                    {
                        var indices = EarcutNet.Earcut.Tessellate( vertices, holeIndices );
                        TriangulatedPolygon poly = new TriangulatedPolygon();
                        poly.vertices = new List<Vector2>( indices.Count );
                        for (int k = 0;k < indices.Count; k++)
                        {
                            double x = vertices[indices[k]*2];
                            double y = vertices[indices[k]*2+1];
                            poly.vertices.Add( new Vector2( (float)x, (float)y ) );
                        }
                        polygons[polygons.Count-1] = poly;
                        Debug.Assert( poly.vertices.Count % 3 == 0 );
                    }
                    catch (Exception)
                    {
                        numFailedPolys++;
                    }
                }
                polygonLayers.Add( polygons );
            }
            triangulated = true;
            return numFailedPolys;
        }

        public void OptimizeForPointIsInsideTriangle()
        {
            for (int i = 0;i < polygonLayers.Count;i++)
                for (int j = 0;j < polygonLayers[i].Count;j++)
                    polygonLayers[i][j].OptimizeForIsPointInTriangle();
        }

        // Calls callback(x, y, channel) for each raster position (256 channels) where each value represents a single channel.
        // If no polygon was hit, 255 is called.
        // If polygon was hit, but no feature was matched, 254 is called.
        // Returns a list of failed to match pixels. This can be due to geometry not exactly matching or a layer not being found.
        public List<Vector3Int> RenderToTextureSingle(
            int width, int height, 
            List<string> matchingAttribKeys, 
            List<List<string>> layerNamesList, 
            Func<int, int, byte, bool> callback )
        {
            Debug.Assert( triangulated, "First call Triangulate." );
            Debug.Assert( layerNamesList.Count < 254, "254 and 255 are reserved for no hit or no match." );

            // First match layers to layer names.
            bool cancel = false;
            List<Vector3Int> failedPixels = new List<Vector3Int>();
            for (int l = 0;l < layers.Count && !cancel;l++)
            {
                var layer  = layers[l];
                for (int f = 0;f < layer.VectorTileFeatures.Count && !cancel;f++)
                {
                    var feature = layer.VectorTileFeatures[f];
                    feature.SelectedLayerIdx = 254;

                    if (feature.GeometryType != Tile.GeomType.Polygon)
                        continue;

                    if (feature.Attributes == null)
                        continue;

                    // Find matching layer.
                    bool matchingLayerFound = false;
                    for (int a = 0;a < feature.Attributes.Count && !matchingLayerFound;a++)
                    {
                        for (int m = 0;m < matchingAttribKeys.Count && !matchingLayerFound;m++)
                        {
                            if (feature.Attributes[a].Key != matchingAttribKeys[m])
                                continue;

                            string function = feature.Attributes[a].Value as string;
                            for (int layerIdx = 0;layerIdx < layerNamesList.Count && !matchingLayerFound;layerIdx++)
                            {
                                for (int layerNameIdx = 0;layerNameIdx < layerNamesList[layerIdx].Count;layerNameIdx++)
                                {
                                    if (function.Contains( layerNamesList[layerIdx][layerNameIdx] ))
                                    {
                                        feature.SelectedLayerIdx = layerIdx;
                                        matchingLayerFound = true;
                                        break;
                                    }
                                }
                            }
                        }
                    }

                    // try Layer.name
                    if (!matchingLayerFound)
                    {
                        for (int layerIdx = 0;layerIdx < layerNamesList.Count && !matchingLayerFound;layerIdx++)
                        {
                            for (int layerNameIdx = 0;layerNameIdx < layerNamesList[layerIdx].Count;layerNameIdx++)
                            {
                                if (layer.Name.Contains( layerNamesList[layerIdx][layerNameIdx] ))
                                {
                                    feature.SelectedLayerIdx = layerIdx;
                                    matchingLayerFound = true;
                                    break;
                                }
                            }
                        }
                    }
                }
            }

            Debug.Assert( width == height, "Must be square images." );

            // For each layer, for each pixel, now check triangle intersections.
            for (int l = 0;l < layers.Count && !cancel;l++)
            {
                var layer = layers[l];
                float fx  = (float)layer.Extent / width;
                TriangulatedPolygon cachedPoly = default;
                int cachedVtxIdx  = -1;
                int cachedTriIdx  = -1;
                byte cachedPixel  = 0;
                for (int y = 0;y < height && !cancel;y++)
                {
                    for (int x = 0;x < width && !cancel;x++)
                    {
                        Vector2 p = new Vector2(fx*x+0.5f*fx, fx*y+0.5f*fx);
                        bool hit  = false;

                        // First try cache, quite often adjacent pixels will hit the same triangle.
                        if (cachedVtxIdx!=-1)
                        {
                            var vertices = cachedPoly.vertices;
                            var denoms   = cachedPoly.denoms;
                            var mins     = cachedPoly.mins;
                            var maxs     = cachedPoly.maxs;
                            if (!(p.x < mins[cachedTriIdx].x || p.x > maxs[cachedTriIdx].x) &&
                                !(p.y < mins[cachedTriIdx].y || p.y > maxs[cachedTriIdx].y))
                            {
                                hit = GeomUtil.PointIsInsideTriangle2( p, vertices[cachedVtxIdx], vertices[cachedVtxIdx+1], vertices[cachedVtxIdx+2], denoms[cachedTriIdx] );
                                if (hit)
                                {
                                    cancel = callback( x, y, cachedPixel ); // If SelectedLayerIdx did not match, it was set to 254.
                                    continue; // Pass from cache, continue to next pixel.
                                }
                            }
                        }

                        // Must check all triangles, no cache or was no hit with cache.
                        for (int f = 0;f < layer.VectorTileFeatures.Count;f++)
                        {
                            var feature = layer.VectorTileFeatures[f];

                            if (feature.GeometryType != Tile.GeomType.Polygon)
                                continue;

                            var polygons = polygonLayers[l][f];
                            if (polygons.vertices.Count == 0)
                                continue;

                            cachedVtxIdx = -1;
                            cachedPoly   = polygonLayers[l][f];
                            var mins     = cachedPoly.mins;
                            var maxs     = cachedPoly.maxs; 
                            var denoms   = cachedPoly.denoms;
                            var vertices = cachedPoly.vertices;
                            for (int vIdx = 0, triIdx = 0; vIdx < vertices.Count; vIdx += 3, triIdx++)
                            {
                                if ( p.x < mins[triIdx].x || p.x > maxs[triIdx].x ) continue;
                                if ( p.y < mins[triIdx].y || p.y > maxs[triIdx].y ) continue;
                                hit = GeomUtil.PointIsInsideTriangle2( p, vertices[vIdx], vertices[vIdx+1], vertices[vIdx+2], denoms[triIdx] );
                                if (hit)
                                {
                                    cachedTriIdx = triIdx;
                                    cachedVtxIdx = vIdx;
                                    cachedPixel  = (byte)feature.SelectedLayerIdx;
                                    cancel = callback( x, y, cachedPixel );
                                    break;
                                }
                            }

                            if (hit) break;
                        }

                        if ( !hit )
                        {
                            failedPixels.Add( new Vector3Int( x, y, 255 ) );
                        }
                    }
                }
            }

            return failedPixels;
        }
    }

    public static class VectorTileLoader
    {
        public static VectorTile LoadFromUrl( string url, bool autoStart=true )
        {
            VectorTile tile = new VectorTile();
            tile.request = UnityWebRequest.Get( url );
            if (autoStart)
            {
                tile.StartDownload();
            }
            return tile;
        }
    }
}