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;
}
static bool IsTriangleCCW( Vector2 vertex1, Vector2 vertex2, Vector2 vertex3 )
{
float signedArea = (vertex2.x - vertex1.x) * (vertex3.y - vertex1.y) - (vertex3.x - vertex1.x) * (vertex2.y - vertex1.y);
return signedArea > 0;
}
// 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 ) );
}
//for ( int k = 0; k < indices.Count; k += 3)
//{
// if ( !IsTriangleCCW( poly.vertices[k], poly.vertices[k+1], poly.vertices[k+2] ))
// {
// var t = poly.vertices[k];
// poly.vertices[k] = poly.vertices[k+2];
// poly.vertices[k+2] = t;
// }
//}
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()
{
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( (l, f, t2) );
}
node.children[i] = n2;
stack.Add( n2 );
}
node.triangles = null;
}
UnityEngine.Debug.Log( "Optimize for raytracing took " + sw.ElapsedMilliseconds );
}
// 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;
}
// 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.
// Also out puts a remap of layer indices. For instance for a specific tile, only layerIdx 1, 6 and 3 are used.
// Then this 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];
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 ;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;
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)
{
// TODO caching the TriIdx doees not work, I have no clue why, it should only function
// as a hint, as where to start. But using this hint results in massive number of triangles going wrong...
// cachedTriIdx = ti;
var layerIdx = (byte)layers[l].VectorTileFeatures[f].SelectedLayerIdx;
texture[(resolution - y -1)*resolution+x] = layerIdx;
break;
}
}
}
if (hit) break;
} // end while
stack.Clear();
if (!hit)
{
texture[(resolution - y -1)*resolution+x] = 255;
failedPixels.Add( new Vector3Int( x, y, 255 ) );
}
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 = 255;
int remappedIndexCounter = -1;
byte remappedPixel = 255;
int addr = 0;
for (int y = 0;y < resolution && !cancelToken;y++)
{
for (int x = 0;x < resolution;x++)
{
byte pixel = texture[addr];
if (pixel < 254)
{
if (pixel != cachedPixel)
{
if (!remappedLayerIndices.TryGetValue( pixel, out remappedPixel ))
{
if (remappedIndexCounter < 253) // 254 is reserved for no layer match, 255 is ray hit with triangle.
{
remappedIndexCounter++;
remappedPixel = (byte)remappedIndexCounter;
remappedLayerIndices.Add( pixel, remappedPixel );
}
else remappedPixel = 0;
}
cachedPixel = pixel;
}
texture[addr] = remappedPixel;
} // leave unfound or unhit pixels on their original value.
addr++;
}
}
UnityEngine.Debug.Assert(remappedIndexCounter <= 254, "Exceeded layer count." );
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;
}
}
}