VectorTile.cs

using Mapbox.Vector.Tile;
using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.IO;
using System.Threading.Tasks;
using UnityEngine;
using UnityEngine.Networking;

namespace Wander
{
    internal class QuadTreeNode
    {
        internal Vector2 min, max;
        internal QuadTreeNode[] children;
        internal List<(int, int, int)> triangles; // Layer, Feature, Triangle index.
        internal int depth;
    }

    // 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));
                denominator = 1.0f / denominator;
                denoms.Add( 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 bool layersIdentified;
        private Task parseTileTask;
        private List<VectorTileLayer> layers;
        private List<List<TriangulatedPolygon>> polygonLayers;
        private QuadTreeNode root;

        internal UnityWebRequest request;

        public void StartDownload()
        {
            UnityEngine.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;
                        UnityEngine.Debug.Assert( poly.vertices.Count % 3 == 0 );
                    }
                    catch (Exception)
                    {
                        numFailedPolys++;
                    }
                }
                polygonLayers.Add( polygons );
            }
            triangulated = true;
            return numFailedPolys;
        }

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

                // Generate quadtree
                List<QuadTreeNode> stack = new List<QuadTreeNode>();
                root = new QuadTreeNode();
                root.triangles = new List<(int, int, int)>();
                root.min = new Vector2( 0, 0 );
                root.max = new Vector2( 4096, 4096 ); // TODO 4096 should be max of all layer extents.
                for (int l = 0;l < polygonLayers.Count;l++)
                {
                    var layer = layers[l];
                    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;

                        if (feature.SelectedLayerIdx == 254)
                            continue;

                        if (feature.RelativeHeight != 0)
                            continue;

                        var poly = polygonLayers[l][f];
                        for (int t = 0;t < poly.vertices.Count/3;t++)
                        {
                            root.triangles.Add( (l, f, t) );
                        }
                    }
                }
                stack.Add( root );
                while (stack.Count > 0)
                {
                    var node = stack[0];
                    stack.RemoveAt( 0 );
                    if (node.triangles.Count < 4)
                        continue;
                    if (node.depth > 7)
                        continue;
                    node.children = new QuadTreeNode[4];
                    var hs = (node.max - node.min) / 2;
                    Vector2 [] mins = new [] {
                    node.min,
                    new Vector2(node.min.x+hs.x, node.min.y),
                    new Vector2(node.min.x,      node.min.y+hs.y),
                    new Vector2(node.min.x+hs.x, node.min.y+hs.y)
                };
                    for (int i = 0;i < 4;i++)
                    {
                        var n2   = new QuadTreeNode();
                        n2.depth = node.depth+1;
                        n2.min   = mins[i];
                        n2.max   = n2.min + hs;
                        n2.triangles = new List<(int, int, int)>();
                        for (int t = 0;t < node.triangles.Count;t++)
                        {
                            int l  = node.triangles[t].Item1;
                            int f  = node.triangles[t].Item2;
                            int t2 = node.triangles[t].Item3;
                            var min2 = polygonLayers[l][f].mins[t2];
                            var max2 = polygonLayers[l][f].maxs[t2];
                            if ((min2.x > n2.max.x) || (min2.y > n2.max.y) || (max2.x < n2.min.x) || (max2.y < n2.min.y))
                            {
                                continue;
                            }
                            n2.triangles.Add( node.triangles[t] );
                            UnityEngine.Debug.Assert( layers[l].VectorTileFeatures[f].SelectedLayerIdx != 254 &&
                                                      layers[l].VectorTileFeatures[f].RelativeHeight == 0 );
                        }
                        node.children[i] = n2;
                        stack.Add( n2 );
                    }
                    node.triangles = null;
                }
                UnityEngine.Debug.Log( "Optimize for raytracing took " + sw.ElapsedMilliseconds );
            }
            catch (Exception e)
            {
                UnityEngine.Debug.LogException( e );
            }
        }

        // Identify feature by specifying a (unique) index based on some criteria. This can very per
        // vector tile provider. 
        public void IdentifyLayers( Func<VectorTileLayer, List<KeyValuePair<string, object>>, int> selectionCallback,
                                    Func<VectorTileLayer, List<KeyValuePair<string, object>>, int> relativeHeightCallback )
        {
            for (int l = 0;l < layers.Count;l++)
            {
                var layer  = layers[l];
                for (int f = 0;f < layer.VectorTileFeatures.Count;f++)
                {
                    var feature = layer.VectorTileFeatures[f];
                    feature.SelectedLayerIdx = 254;

                    int uniqueId = selectionCallback( layer, feature.Attributes );
                    if (uniqueId > -1)
                    {
                        feature.SelectedLayerIdx = uniqueId;
                    }
                    uniqueId = relativeHeightCallback( layer, feature.Attributes );
                    feature.RelativeHeight = uniqueId;
                }
            }
            layersIdentified = true;
        }

        // Generates a raster for each position (pixel). 2 pixels are pushed in 1 (each 16 bit).
        // If no polygon was hit, 15 is encoded (reserved).
        // If polygon was hit, but no feature was matched, also 15 is encoded.
        // Returns a list of failed to match pixels. This can be due to geometry not exactly matching or a layer not being found.
        // Also outputs a remap of layer indices. For instance for a specific tile, only layerIdx 1, 6 and 3 are used.
        // Then it applies a remapping of 1->0, 6->1, 3->2. So that in the shader only 3 textures are needed starting from 0, 1.. etc.
        public byte[] RenderToTextureSingle(
            int resolution,
            out Dictionary<byte, byte> remappedLayerIndices,
            out List<Vector3Int> failedPixels,
            ref bool cancelToken )
        {
            Stopwatch sw = new Stopwatch();
            sw.Restart();

            UnityEngine.Debug.Assert( triangulated, "First call Triangulate." );
            UnityEngine.Debug.Assert( layersIdentified, "Identify layers first." );
            UnityEngine.Debug.Assert( resolution > 1, "Must be at least 2." );

            byte [] texture = new byte[resolution*resolution/2];
            failedPixels = new List<Vector3Int>();
            remappedLayerIndices = new Dictionary<byte, byte>();
            float oneOverRes = 1.0f / resolution;
            int cachedTriIdx = 0;
            float fx = 4096 * oneOverRes; // TODO 4096 may be different in other implementations.

            QuadTreeNode node = null;
            List<QuadTreeNode> stack = new List<QuadTreeNode>();

            // For each pixel.
            for (int y = 0;y < resolution && !cancelToken;y++)
            {
                for (int x = 0;x < resolution && !cancelToken;x++)
                {
                    bool hit  = false;
                    Vector2 p = new Vector2(fx*x+0.5f, fx*y+0.5f);

                    stack.Add( root );
                    while (stack.Count > 0)
                    {
                        node = stack[0];
                        stack.RemoveAt( 0 );
                        if (p.x < node.min.x || p.y < node.min.y || p.x > node.max.x || p.y > node.max.y)
                        {
                            continue;
                        }

                        if (node.children != null)
                        {
                            for (int c = 0;c < node.children.Length;c++)
                            {
                                stack.Add( node.children[c] );
                            }
                        }
                        else if (node.triangles != null) // Is leaf
                        {
                            for (int t = 0;t < node.triangles.Count;t++)
                            {
                                int ti = (cachedTriIdx + t)  % node.triangles.Count; // Continue searching where we left off 
                                int l  = node.triangles[ti].Item1;
                                int f  = node.triangles[ti].Item2;
                                int t2 = node.triangles[ti].Item3;
                                var min2 = polygonLayers[l][f].mins[t2];
                                var max2 = polygonLayers[l][f].maxs[t2];
                                if (p.x < min2.x || p.x > max2.x) continue;
                                if (p.y < min2.y || p.y > max2.y) continue;
                                var vertices = polygonLayers[l][f].vertices;
                                var denoms   = polygonLayers[l][f].denoms;
                                hit = GeomUtil.PointIsInsideTriangle2( p, vertices[t2*3], vertices[t2*3+1], vertices[t2*3+2], denoms[t2] );
                                if (hit)
                                {
                                    cachedTriIdx = ti;
                                    var layerIdx = (byte)layers[l].VectorTileFeatures[f].SelectedLayerIdx;
                                    //var addr2    = y*resolution+x;
                                    var addr2    = (resolution - y -1)*resolution+x;
                                    if (layerIdx > 15) layerIdx = 15; // max layers 15 (15 is reserved, nothing was hit). 
                                    var shift = (addr2&1) << 2;
                                    texture[addr2>>1] |= (byte)(layerIdx << shift);
                                    break;
                                }
                            }
                        }

                        if (hit) break;

                    } // end while

                    stack.Clear();
                    if (!hit)
                    {
                        var addr2 = (resolution - y -1)*resolution+x;
                        var shift = (addr2&1) << 2;
                        texture[addr2>>1] |= (byte)(15 << shift);
                        failedPixels.Add( new Vector3Int( x, y, 15 ) );
                    }
                    else
                    {
                        stack.Add( node ); // Add the node that was hit as the next pixel may likely hit this poly again.
                    }
                }
            }

            // Determine number of different layers. For instance, if only layer 3, 8, 14 and 15 are used, we select
            // a material that only uses 4 textures and put 3 -> Albedo_0 -> 8 to Albedo_1, etc. in the shader.
            byte cachedPixel = 15;
            int  remappedIndexCounter = -1;
            byte remappedPixel = 15;
            uint addr  = 0;
            byte pixel = 0;
            for (int y = 0;y < resolution && !cancelToken;y++)
            {
                for (int x = 0;x < resolution && !cancelToken;x++)
                {
                    if ((x&1) == 0)
                        pixel = texture[addr>>1];
                    byte shift  = (byte)((addr&1));
                    byte pixel2 = (byte)((pixel >> (shift<<2)) & 15);
                    if (pixel2 != 15)
                    {
                        if (pixel2 != cachedPixel)
                        {
                            if (!remappedLayerIndices.TryGetValue( pixel2, out remappedPixel ))
                            {
                                if (remappedIndexCounter < 13) // 15 is reserved for not found, so 0-14 are valid.
                                {
                                    remappedIndexCounter++;
                                    remappedPixel = (byte)remappedIndexCounter;
                                    remappedLayerIndices.Add( pixel2, remappedPixel );
                                }
                                else remappedPixel = 15; // Reserved for invalid.
                            }
                            cachedPixel = pixel2;
                        }
                        UnityEngine.Debug.Assert( remappedPixel < 15 );
                    }
                    else
                    {
                        remappedPixel = 15;
                        cachedPixel = 15;
                    }
                    // Data in texture is not zero anymore, so must check if is even, then just set, otherwise OR-add it.
                    if (shift==0)
                        texture[addr>>1] = remappedPixel;
                    else
                        texture[addr>>1] |= (byte)(remappedPixel << 4);
                    addr++;
                }
            }

            UnityEngine.Debug.Assert( remappedIndexCounter <= 15, "Exceeded layer count." ); // Invalid pixel is not added to map, so max must be 15, not 16.

            UnityEngine.Debug.Log( "Render to texture took " + sw.ElapsedMilliseconds );
            return texture;
        }
    }

    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;
        }
    }
}