using System;
using System.Collections.Generic;
using Sandbox;

namespace RedSnail.WaterTool2;

/// <summary>
/// The water at a point of a piece, at rest: the surface's height and the water's state there.
/// </summary>
internal struct SurfacePoint
{
	public float Height;
	public Vector2 Velocity;
	public float Waves;
	public float Foam;

	/// <summary>
	/// How far the surface has handed over to the sea: 0 is the piece's own water, 1 is the sea's surface exactly.
	/// </summary>
	public float SeaBlend;
}



/// <summary>
/// A patch of the sea's surface a piece of water covers wherever it lies near sea level: the sea is cut away inside
/// it, so the two are never drawn over each other. A polygon in plan, or a disk.
/// </summary>
internal sealed class SeaHole
{
	/// <summary>
	/// The polygon, or null for a disk.
	/// </summary>
	public Vector2[] Points;

	public Vector2 Centre;
	public float Radius;

	/// <summary>
	/// The lowest water surface the hole covers: only holes near sea level cut the sea.
	/// </summary>
	public float Lowest;

	public Vector2 Min;
	public Vector2 Max;



	public static SeaHole Polygon(Vector2[] _Points, float _Lowest)
	{
		var hole = new SeaHole { Points = _Points, Lowest = _Lowest };
		hole.UpdateBounds();

		return hole;
	}



	public static SeaHole Disk(Vector2 _Centre, float _Radius, float _Lowest)
	{
		var hole = new SeaHole { Centre = _Centre, Radius = _Radius, Lowest = _Lowest };
		hole.UpdateBounds();

		return hole;
	}



	public void UpdateBounds()
	{
		if (Points is null)
		{
			Min = Centre - new Vector2(Radius, Radius);
			Max = Centre + new Vector2(Radius, Radius);
			return;
		}

		Min = new Vector2(float.MaxValue, float.MaxValue);
		Max = new Vector2(float.MinValue, float.MinValue);

		foreach (var point in Points)
		{
			Min = new Vector2(MathF.Min(Min.x, point.x), MathF.Min(Min.y, point.y));
			Max = new Vector2(MathF.Max(Max.x, point.x), MathF.Max(Max.y, point.y));
		}
	}



	/// <summary>
	/// Moves the hole from network space into the world (its height too).
	/// </summary>
	public void Transform(in Transform _Transform)
	{
		if (Points is null)
		{
			Vector3 centre = _Transform.PointToWorld(new Vector3(Centre.x, Centre.y, Lowest));

			Centre = new Vector2(centre.x, centre.y);
			Lowest = centre.z;
		}
		else
		{
			for (int i = 0; i < Points.Length; i++)
			{
				Vector3 point = _Transform.PointToWorld(new Vector3(Points[i].x, Points[i].y, 0.0f));
				Points[i] = new Vector2(point.x, point.y);
			}

			Lowest = _Transform.PointToWorld(new Vector3(0.0f, 0.0f, Lowest)).z;
		}

		UpdateBounds();
	}
}



/// <summary>
/// One built piece of water surface on the CPU, in world space and at rest: where every vertex is, and the state of
/// the water there (its flow, wave strength, foam and how far it has handed over to the sea). The GPU draws it;
/// gameplay asks it where the surface is under a point, with the same interpolation the GPU does between the same
/// vertices.
/// </summary>
internal sealed class WaterMeshData
{
	public Vector3[] Positions;
	public Vector2[] Velocities;
	public float[] Waves;
	public float[] Foams;
	public float[] SeaBlend;
	public int[] Indices;

	/// <summary>
	/// Where the sea is cut away under this piece, when it lies near sea level.
	/// </summary>
	public readonly List<SeaHole> SeaHoles = new();

	/// <summary>
	/// The surface's world bounds, at rest.
	/// </summary>
	public BBox Bounds;

	public int VertexCount => Positions?.Length ?? 0;

	public int TriangleCount => (Indices?.Length ?? 0) / 3;

	private float m_BucketSize;
	private float m_MinX;
	private float m_MinY;
	private int m_Columns;
	private int m_Rows;
	private int[] m_BucketStarts;
	private int[] m_BucketTriangles;



	public WaterMeshData(int _VertexCount)
	{
		Positions = new Vector3[_VertexCount];
		Velocities = new Vector2[_VertexCount];
		Waves = new float[_VertexCount];
		Foams = new float[_VertexCount];
		SeaBlend = new float[_VertexCount];
	}



	/// <summary>
	/// Moves the piece from network space into the world: positions through the whole transform, the flow turned with
	/// it, the sea holes with them. Then works out its bounds and its lookup grid; with <paramref name="_OutlineHoles"/>,
	/// the piece's own outline becomes its sea hole.
	/// </summary>
	public void Finish(in Transform _Transform, IList<int> _Indices, bool _OutlineHoles = false)
	{
		Indices = new int[_Indices.Count];
		_Indices.CopyTo(Indices, 0);

		Rotation rotation = _Transform.Rotation;

		for (int i = 0; i < Positions.Length; i++)
		{
			Positions[i] = _Transform.PointToWorld(Positions[i]);

			Vector3 flow = rotation * new Vector3(Velocities[i].x, Velocities[i].y, 0.0f);
			Velocities[i] = new Vector2(flow.x, flow.y);
		}

		foreach (var hole in SeaHoles)
			hole.Transform(_Transform);

		if (Positions.Length > 0)
		{
			var bounds = new BBox(Positions[0], Positions[0]);

			foreach (var position in Positions)
				bounds = bounds.AddPoint(position);

			Bounds = bounds;
		}

		if (_OutlineHoles)
			AddOutlineHoles();

		BuildLookup();
	}



	/// <summary>
	/// Every loop of edges only one triangle uses (the piece's outline) as a sea hole.
	/// </summary>
	private void AddOutlineHoles()
	{
		var used = new Dictionary<long, int>();

		for (int t = 0; t + 2 < Indices.Length; t += 3)
		{
			for (int k = 0; k < 3; k++)
			{
				int a = Indices[t + k];
				int b = Indices[t + (k + 1) % 3];
				long key = a < b ? ((long)a << 32) | (uint)b : ((long)b << 32) | (uint)a;

				used[key] = used.GetValueOrDefault(key) + 1;
			}
		}

		// The outline's edges, each from the vertex it leaves to the one it reaches.
		var next = new Dictionary<int, int>();

		for (int t = 0; t + 2 < Indices.Length; t += 3)
		{
			for (int k = 0; k < 3; k++)
			{
				int a = Indices[t + k];
				int b = Indices[t + (k + 1) % 3];
				long key = a < b ? ((long)a << 32) | (uint)b : ((long)b << 32) | (uint)a;

				if (used[key] == 1)
					next[a] = b;
			}
		}

		var visited = new HashSet<int>();

		foreach (int start in next.Keys)
		{
			if (visited.Contains(start))
				continue;

			var loop = new List<Vector2>();
			float lowest = float.MaxValue;
			int current = start;

			while (visited.Add(current) && next.TryGetValue(current, out int following))
			{
				loop.Add(new Vector2(Positions[current].x, Positions[current].y));
				lowest = MathF.Min(lowest, Positions[current].z);
				current = following;
			}

			if (loop.Count >= 3)
				SeaHoles.Add(SeaHole.Polygon(loop.ToArray(), lowest));
		}
	}



	/// <summary>
	/// Buckets the triangles on a grid over the piece, so a point is found among a handful of them.
	/// </summary>
	private void BuildLookup()
	{
		int triangles = TriangleCount;

		if (triangles == 0)
			return;

		float width = MathF.Max(1.0f, Bounds.Size.x);
		float height = MathF.Max(1.0f, Bounds.Size.y);

		// Roughly a couple of triangles per bucket.
		m_BucketSize = MathF.Max(8.0f, MathF.Sqrt(width * height / MathF.Max(1, triangles)) * 1.5f);
		m_MinX = Bounds.Mins.x;
		m_MinY = Bounds.Mins.y;
		m_Columns = Math.Clamp((int)MathF.Ceiling(width / m_BucketSize), 1, 4096);
		m_Rows = Math.Clamp((int)MathF.Ceiling(height / m_BucketSize), 1, 4096);

		var counts = new int[m_Columns * m_Rows + 1];

		for (int pass = 0; pass < 2; pass++)
		{
			for (int t = 0; t < triangles; t++)
			{
				TriangleBuckets(t, out int x0, out int y0, out int x1, out int y1);

				for (int y = y0; y <= y1; y++)
				{
					for (int x = x0; x <= x1; x++)
					{
						int bucket = y * m_Columns + x;

						if (pass == 0)
							counts[bucket + 1]++;
						else
							m_BucketTriangles[m_BucketStarts[bucket] + counts[bucket]++] = t;
					}
				}
			}

			if (pass == 0)
			{
				for (int i = 1; i < counts.Length; i++)
					counts[i] += counts[i - 1];

				m_BucketStarts = counts;
				m_BucketTriangles = new int[counts[^1]];
				counts = new int[m_Columns * m_Rows + 1];
			}
		}
	}



	private void TriangleBuckets(int _Triangle, out int _X0, out int _Y0, out int _X1, out int _Y1)
	{
		Vector3 a = Positions[Indices[_Triangle * 3]];
		Vector3 b = Positions[Indices[_Triangle * 3 + 1]];
		Vector3 c = Positions[Indices[_Triangle * 3 + 2]];

		_X0 = Bucket(MathF.Min(a.x, MathF.Min(b.x, c.x)) - m_MinX, m_Columns);
		_X1 = Bucket(MathF.Max(a.x, MathF.Max(b.x, c.x)) - m_MinX, m_Columns);
		_Y0 = Bucket(MathF.Min(a.y, MathF.Min(b.y, c.y)) - m_MinY, m_Rows);
		_Y1 = Bucket(MathF.Max(a.y, MathF.Max(b.y, c.y)) - m_MinY, m_Rows);
	}



	private int Bucket(float _Offset, int _Count)
	{
		return Math.Clamp((int)MathF.Floor(_Offset / m_BucketSize), 0, _Count - 1);
	}



	/// <summary>
	/// The surface at rest over a world point, and the water's state there, interpolated across the triangle the point
	/// falls in exactly as the GPU interpolates it. False when the point is not over this piece.
	/// </summary>
	public bool TrySample(Vector2 _Point, out SurfacePoint _Surface)
	{
		_Surface = default;

		if (m_BucketStarts is null)
			return false;

		if (_Point.x < Bounds.Mins.x || _Point.x > Bounds.Maxs.x || _Point.y < Bounds.Mins.y || _Point.y > Bounds.Maxs.y)
			return false;

		int bucket = Bucket(_Point.y - m_MinY, m_Rows) * m_Columns + Bucket(_Point.x - m_MinX, m_Columns);

		for (int i = m_BucketStarts[bucket]; i < m_BucketStarts[bucket + 1]; i++)
		{
			int t = m_BucketTriangles[i];
			int ia = Indices[t * 3];
			int ib = Indices[t * 3 + 1];
			int ic = Indices[t * 3 + 2];

			Vector3 a = Positions[ia];
			Vector3 b = Positions[ib];
			Vector3 c = Positions[ic];

			float area = Cross(b.x - a.x, b.y - a.y, c.x - a.x, c.y - a.y);

			if (MathF.Abs(area) < 1e-6f)
				continue;

			float wa = Cross(b.x - _Point.x, b.y - _Point.y, c.x - _Point.x, c.y - _Point.y) / area;
			float wb = Cross(c.x - _Point.x, c.y - _Point.y, a.x - _Point.x, a.y - _Point.y) / area;
			float wc = 1.0f - wa - wb;

			const float tolerance = -1e-4f;

			if (wa < tolerance || wb < tolerance || wc < tolerance)
				continue;

			_Surface = new SurfacePoint
			{
				Height = a.z * wa + b.z * wb + c.z * wc,
				Velocity = Velocities[ia] * wa + Velocities[ib] * wb + Velocities[ic] * wc,
				Waves = Waves[ia] * wa + Waves[ib] * wb + Waves[ic] * wc,
				Foam = Foams[ia] * wa + Foams[ib] * wb + Foams[ic] * wc,
				SeaBlend = SeaBlend[ia] * wa + SeaBlend[ib] * wb + SeaBlend[ic] * wc
			};

			return true;
		}

		return false;
	}



	private static float Cross(float _Ax, float _Ay, float _Bx, float _By)
	{
		return _Ax * _By - _Ay * _Bx;
	}
}