using System;
using System.Collections.Generic;

namespace Sandbox;

internal static class MeshSliceRuntime
{
	private const float Epsilon = 0.0001f;
	private const float PositionMergeEpsilon = 0.001f;
	private const float DegenerateAreaEpsilon = 0.00001f;

	public static MeshSliceResult Slice(
		ModelRenderer renderer,
		Vector3 worldPosition,
		Vector3 worldNormal,
		MeshSliceRegion region,
		Material crossSectionMaterial )
	{
		if ( renderer is null || renderer.Model is null )
			return null;

		if ( worldNormal.Length <= Epsilon )
			return null;

		var model = renderer.Model;
		var sourceVertices = model.GetVertices();
		var sourceIndices = model.GetIndices();

		if ( sourceVertices is null || sourceVertices.Length < 3 )
			return null;

		if ( sourceIndices is null || sourceIndices.Length < 3 )
			return null;

		var localNormal = renderer.WorldTransform.NormalToLocal( worldNormal );
		if ( localNormal.Length <= Epsilon )
			return null;

		localNormal = localNormal.Normal;
		var localPosition = renderer.WorldTransform.PointToLocal( worldPosition );
		var slicePlane = new Plane( localPosition, localNormal );

		var materials = BuildEffectiveMaterials( renderer );
		if ( materials.Count == 0 )
		{
			materials.Add( null );
		}

		var upperBySlot = CreateTriangleSlots( materials.Count );
		var lowerBySlot = CreateTriangleSlots( materials.Count );
		var intersectionPoints = new List<Vector3>();
		var warnedMaterialRemap = false;

		var didSlice = false;
		var sectionCount = model.MeshCount;
		for ( var section = 0; section < sectionCount; section++ )
		{
			var indexStart = model.GetIndexStart( section );
			var indexCount = model.GetIndexCount( section );
			var baseVertex = model.GetBaseVertex( section );
			if ( indexCount < 3 )
				continue;

			var slotIndex = section;
			if ( slotIndex >= materials.Count )
			{
				slotIndex = materials.Count - 1;

				if ( !warnedMaterialRemap )
				{
					Log.Warning(
						"SliceMesh: mesh sections exceed available material slots. " +
						"Extra sections will be remapped to the last material slot." );
					warnedMaterialRemap = true;
				}
			}

			var upperSlot = upperBySlot[slotIndex];
			var lowerSlot = lowerBySlot[slotIndex];

			for ( var i = 0; i + 2 < indexCount; i += 3 )
			{
				var i0 = indexStart + i;
				var i1 = indexStart + i + 1;
				var i2 = indexStart + i + 2;
				if ( i2 >= sourceIndices.Length )
					break;

				var v0 = (int)sourceIndices[i0] + baseVertex;
				var v1 = (int)sourceIndices[i1] + baseVertex;
				var v2 = (int)sourceIndices[i2] + baseVertex;
				if ( !IsVertexIndexValid( sourceVertices, v0 ) ||
					 !IsVertexIndexValid( sourceVertices, v1 ) ||
					 !IsVertexIndexValid( sourceVertices, v2 ) )
				{
					continue;
				}

				var triangle = new SliceTriangle(
					SliceVertex.From( sourceVertices[v0] ),
					SliceVertex.From( sourceVertices[v1] ),
					SliceVertex.From( sourceVertices[v2] ) );

				if ( SplitTriangle( slicePlane, triangle, upperSlot, lowerSlot, intersectionPoints ) )
				{
					didSlice = true;
				}
			}
		}

		if ( !didSlice )
			return null;

		var capTriangles = BuildCapTriangles( intersectionPoints, localNormal, region );
		var crossMaterial = crossSectionMaterial ?? ResolveMaterialForSlot( materials, 0 );
		var crossSlotIndex = materials.Count;
		materials.Add( crossMaterial );

		EnsureSlotCount( upperBySlot, crossSlotIndex + 1 );
		EnsureSlotCount( lowerBySlot, crossSlotIndex + 1 );

		foreach ( var cap in capTriangles )
		{
			upperBySlot[crossSlotIndex].Add( ToUpperCapTriangle( cap ) );
			lowerBySlot[crossSlotIndex].Add( ToLowerCapTriangle( cap ) );
		}

		var upperModel = BuildModel( upperBySlot, materials );
		var lowerModel = BuildModel( lowerBySlot, materials );
		if ( upperModel is null && lowerModel is null )
			return null;

		return new MeshSliceResult( upperModel, lowerModel );
	}

	private static bool SplitTriangle(
		Plane plane,
		SliceTriangle triangle,
		List<SliceTriangle> upperHull,
		List<SliceTriangle> lowerHull,
		List<Vector3> intersectionPoints )
	{
		var d0 = plane.GetDistance( triangle.A.Position );
		var d1 = plane.GetDistance( triangle.B.Position );
		var d2 = plane.GetDistance( triangle.C.Position );

		var hasUp = d0 > Epsilon || d1 > Epsilon || d2 > Epsilon;
		var hasDown = d0 < -Epsilon || d1 < -Epsilon || d2 < -Epsilon;

		// Triangle is fully on one side (or fully on-plane) so no slicing happened.
		if ( !hasUp || !hasDown )
		{
			if ( hasDown && !hasUp )
			{
				lowerHull.Add( triangle );
			}
			else
			{
				upperHull.Add( triangle );
			}

			return false;
		}

		var vertices = new[] { triangle.A, triangle.B, triangle.C };
		var distances = new[] { d0, d1, d2 };

		var upperPolygon = ClipTriangleToHalfSpace( vertices, distances, keepUpper: true );
		var lowerPolygon = ClipTriangleToHalfSpace( vertices, distances, keepUpper: false );

		AddPolygonAsTriangles( upperPolygon, upperHull );
		AddPolygonAsTriangles( lowerPolygon, lowerHull );
		CollectIntersectionPoints( vertices, distances, intersectionPoints );

		return true;
	}

	private static List<SliceVertex> ClipTriangleToHalfSpace( SliceVertex[] vertices, float[] distances, bool keepUpper )
	{
		var output = new List<SliceVertex>( 4 );

		for ( var i = 0; i < 3; i++ )
		{
			var next = (i + 1) % 3;
			var a = vertices[i];
			var b = vertices[next];
			var da = distances[i];
			var db = distances[next];

			var aInside = keepUpper ? da >= -Epsilon : da <= Epsilon;
			var bInside = keepUpper ? db >= -Epsilon : db <= Epsilon;

			if ( aInside && bInside )
			{
				AddUniqueVertex( output, b );
			}
			else if ( aInside && !bInside )
			{
				AddUniqueVertex( output, InterpolateAtPlane( a, b, da, db ) );
			}
			else if ( !aInside && bInside )
			{
				AddUniqueVertex( output, InterpolateAtPlane( a, b, da, db ) );
				AddUniqueVertex( output, b );
			}
		}

		if ( output.Count > 1 && NearlyEqual( output[0].Position, output[output.Count - 1].Position, PositionMergeEpsilon ) )
		{
			output.RemoveAt( output.Count - 1 );
		}

		return output;
	}

	private static void AddPolygonAsTriangles( List<SliceVertex> polygon, List<SliceTriangle> output )
	{
		if ( polygon.Count < 3 )
			return;

		var anchor = polygon[0];
		for ( var i = 1; i + 1 < polygon.Count; i++ )
		{
			var triangle = new SliceTriangle( anchor, polygon[i], polygon[i + 1] );
			if ( IsDegenerate( triangle ) )
				continue;

			output.Add( triangle );
		}
	}

	private static void CollectIntersectionPoints( SliceVertex[] vertices, float[] distances, List<Vector3> output )
	{
		for ( var i = 0; i < 3; i++ )
		{
			var next = (i + 1) % 3;
			var da = distances[i];
			var db = distances[next];

			if ( MathF.Abs( da ) <= Epsilon )
			{
				AddUniquePoint( output, vertices[i].Position );
			}

			if ( (da > Epsilon && db < -Epsilon) || (da < -Epsilon && db > Epsilon) )
			{
				var edgePoint = InterpolateAtPlane( vertices[i], vertices[next], da, db ).Position;
				AddUniquePoint( output, edgePoint );
			}
		}
	}

	private static List<SliceTriangle> BuildCapTriangles( List<Vector3> points, Vector3 planeNormal, MeshSliceRegion region )
	{
		var uniquePoints = new List<Vector3>( points.Count );
		for ( var i = 0; i < points.Count; i++ )
		{
			AddUniquePoint( uniquePoints, points[i] );
		}

		if ( uniquePoints.Count < 3 )
			return new List<SliceTriangle>();

		var basisU = Vector3.Cross( planeNormal, Vector3.Up );
		if ( basisU.Length <= Epsilon )
		{
			basisU = Vector3.Cross( planeNormal, Vector3.Forward );
		}

		if ( basisU.Length <= Epsilon )
		{
			basisU = Vector3.Right;
		}

		basisU = basisU.Normal;
		var basisV = Vector3.Cross( basisU, planeNormal ).Normal;

		var mapped = new MappedPoint[uniquePoints.Count];
		for ( var i = 0; i < uniquePoints.Count; i++ )
		{
			var point = uniquePoints[i];
			mapped[i] = new MappedPoint
			{
				Original = point,
				Mapped = new Vector2( Vector3.Dot( point, basisU ), Vector3.Dot( point, basisV ) )
			};
		}

		Array.Sort( mapped, static ( a, b ) =>
		{
			if ( a.Mapped.x < b.Mapped.x ) return -1;
			if ( a.Mapped.x > b.Mapped.x ) return 1;
			if ( a.Mapped.y < b.Mapped.y ) return -1;
			if ( a.Mapped.y > b.Mapped.y ) return 1;
			return 0;
		} );

		var hull = BuildConvexHull( mapped );
		if ( hull.Count < 3 )
			return new List<SliceTriangle>();

		var minX = float.MaxValue;
		var minY = float.MaxValue;
		var maxX = float.MinValue;
		var maxY = float.MinValue;
		for ( var i = 0; i < hull.Count; i++ )
		{
			var mappedValue = hull[i].Mapped;
			minX = MathF.Min( minX, mappedValue.x );
			minY = MathF.Min( minY, mappedValue.y );
			maxX = MathF.Max( maxX, mappedValue.x );
			maxY = MathF.Max( maxY, mappedValue.y );
		}

		var width = maxX - minX;
		var height = maxY - minY;
		if ( width <= Epsilon ) width = 1.0f;
		if ( height <= Epsilon ) height = 1.0f;

		var tangent = new Vector4( basisU.x, basisU.y, basisU.z, 1.0f );
		var result = new List<SliceTriangle>( hull.Count - 2 );
		var capNormal = planeNormal.Normal;

		for ( var i = 1; i + 1 < hull.Count; i++ )
		{
			var a = CreateCapVertex( hull[0], capNormal, tangent, region, minX, minY, width, height );
			var b = CreateCapVertex( hull[i], capNormal, tangent, region, minX, minY, width, height );
			var c = CreateCapVertex( hull[i + 1], capNormal, tangent, region, minX, minY, width, height );

			var tri = new SliceTriangle( a, b, c );
			if ( IsDegenerate( tri ) )
				continue;

			result.Add( tri );
		}

		return result;
	}

	private static SliceVertex CreateCapVertex(
		MappedPoint point,
		Vector3 normal,
		Vector4 tangent,
		MeshSliceRegion region,
		float minX,
		float minY,
		float width,
		float height )
	{
		var u = (point.Mapped.x - minX) / width;
		var v = (point.Mapped.y - minY) / height;
		var mappedUv = region.Map( u, v );

		return new SliceVertex
		{
			Position = point.Original,
			Normal = normal,
			Tangent = tangent,
			TexCoord0 = new Vector4( mappedUv.x, mappedUv.y, 0.0f, 1.0f ),
			Color = Color32.White
		};
	}

	private static List<MappedPoint> BuildConvexHull( MappedPoint[] mapped )
	{
		var hull = new List<MappedPoint>( mapped.Length + 1 );

		for ( var i = 0; i < mapped.Length; i++ )
		{
			while ( hull.Count >= 2 )
			{
				var cross = SignedArea2D( hull[hull.Count - 2].Mapped, hull[hull.Count - 1].Mapped, mapped[i].Mapped );
				if ( cross > 0.0f )
					break;

				hull.RemoveAt( hull.Count - 1 );
			}

			hull.Add( mapped[i] );
		}

		for ( int i = mapped.Length - 2, start = hull.Count + 1; i >= 0; i-- )
		{
			while ( hull.Count >= start )
			{
				var cross = SignedArea2D( hull[hull.Count - 2].Mapped, hull[hull.Count - 1].Mapped, mapped[i].Mapped );
				if ( cross > 0.0f )
					break;

				hull.RemoveAt( hull.Count - 1 );
			}

			hull.Add( mapped[i] );
		}

		if ( hull.Count > 1 )
		{
			hull.RemoveAt( hull.Count - 1 );
		}

		return hull;
	}

	private static Model BuildModel( List<List<SliceTriangle>> trianglesBySlot, List<Material> materials )
	{
		var builder = Model.Builder;
		var hasMesh = false;
		var collisionVertices = new List<Vector3>();

		for ( var i = 0; i < trianglesBySlot.Count; i++ )
		{
			var triangles = trianglesBySlot[i];
			if ( triangles.Count == 0 )
				continue;

			var material = ResolveMaterialForSlot( materials, i );
			var mesh = BuildMesh( triangles, material );
			if ( mesh is null )
				continue;

			builder.AddMesh( mesh );
			CollectCollisionVertices( triangles, collisionVertices );
			hasMesh = true;
		}

		if ( !hasMesh )
			return null;

		// Build a convex collision hull from sliced points so spawned hull colliders
		// match the sliced result instead of inheriting source collider geometry.
		if ( collisionVertices.Count >= 4 )
		{
			builder.AddCollisionHull( collisionVertices );
		}

		return builder.Create();
	}

	private static void CollectCollisionVertices( List<SliceTriangle> triangles, List<Vector3> output )
	{
		for ( var i = 0; i < triangles.Count; i++ )
		{
			AddUniquePoint( output, triangles[i].A.Position );
			AddUniquePoint( output, triangles[i].B.Position );
			AddUniquePoint( output, triangles[i].C.Position );
		}
	}

	private static Mesh BuildMesh( List<SliceTriangle> triangles, Material material )
	{
		var vertexCount = triangles.Count * 3;
		if ( vertexCount < 3 )
			return null;

		var vertices = new Vertex[vertexCount];
		var indices = new int[vertexCount];

		var mins = Vector3.Zero;
		var maxs = Vector3.Zero;
		var hasBounds = false;
		var index = 0;

		for ( var i = 0; i < triangles.Count; i++ )
		{
			var tri = triangles[i];
			var a = ToVertex( tri.A );
			var b = ToVertex( tri.B );
			var c = ToVertex( tri.C );

			vertices[index] = a;
			indices[index] = index;
			ExpandBounds( a.Position, ref mins, ref maxs, ref hasBounds );
			index++;

			vertices[index] = b;
			indices[index] = index;
			ExpandBounds( b.Position, ref mins, ref maxs, ref hasBounds );
			index++;

			vertices[index] = c;
			indices[index] = index;
			ExpandBounds( c.Position, ref mins, ref maxs, ref hasBounds );
			index++;
		}

		var mesh = new Mesh( material );
		mesh.CreateVertexBuffer( vertices.Length, vertices );
		mesh.CreateIndexBuffer( indices.Length, indices );
		if ( hasBounds )
		{
			mesh.Bounds = new BBox( mins, maxs );
		}

		return mesh;
	}

	private static Vertex ToVertex( SliceVertex source )
	{
		var normal = source.Normal.Length > Epsilon ? source.Normal.Normal : Vector3.Up;
		var tangent = GetSafeTangent( source.Tangent, normal );

		return new Vertex
		{
			Position = source.Position,
			Color = source.Color,
			Normal = normal,
			TexCoord0 = source.TexCoord0,
			Tangent = tangent
		};
	}

	private static Vector4 GetSafeTangent( Vector4 tangent, Vector3 normal )
	{
		var tangentDirection = new Vector3( tangent.x, tangent.y, tangent.z );
		if ( tangentDirection.Length <= Epsilon )
		{
			tangentDirection = Vector3.Cross( normal, Vector3.Up );
			if ( tangentDirection.Length <= Epsilon )
			{
				tangentDirection = Vector3.Cross( normal, Vector3.Right );
			}
		}

		tangentDirection = tangentDirection.Normal;
		var w = MathF.Abs( tangent.w ) <= Epsilon ? 1.0f : MathF.Sign( tangent.w );
		return new Vector4( tangentDirection.x, tangentDirection.y, tangentDirection.z, w );
	}

	private static SliceTriangle ToUpperCapTriangle( SliceTriangle triangle )
	{
		return BuildCapTriangleForSide( triangle, invertNormal: true );
	}

	private static SliceTriangle ToLowerCapTriangle( SliceTriangle triangle )
	{
		return BuildCapTriangleForSide( triangle, invertNormal: false );
	}

	private static SliceTriangle BuildCapTriangleForSide( SliceTriangle triangle, bool invertNormal )
	{
		var desiredNormal = invertNormal ? -triangle.A.Normal : triangle.A.Normal;
		if ( desiredNormal.Length <= Epsilon )
		{
			desiredNormal = invertNormal ? Vector3.Down : Vector3.Up;
		}
		else
		{
			desiredNormal = desiredNormal.Normal;
		}

		var a = triangle.A.WithNormal( desiredNormal );
		var b = triangle.B.WithNormal( desiredNormal );
		var c = triangle.C.WithNormal( desiredNormal );

		// Ensure front-face winding matches the desired cap normal.
		var cross = Vector3.Cross( b.Position - a.Position, c.Position - a.Position );
		if ( Vector3.Dot( cross, desiredNormal ) < 0.0f )
		{
			(b, c) = (c, b);
		}

		return new SliceTriangle( a, b, c );
	}

	private static List<Material> BuildEffectiveMaterials( ModelRenderer renderer )
	{
		var materials = new List<Material>();
		var modelMaterials = renderer.Model.Materials;
		if ( modelMaterials.Length == 0 )
		{
			return materials;
		}

		for ( var i = 0; i < modelMaterials.Length; i++ )
		{
			var overrideMaterial = renderer.Materials.GetOverride( i );
			materials.Add( overrideMaterial ?? modelMaterials[i] );
		}

		return materials;
	}

	private static Material ResolveMaterialForSlot( IReadOnlyList<Material> materials, int slotIndex )
	{
		if ( materials.Count == 0 )
			return null;

		if ( slotIndex < materials.Count )
			return materials[slotIndex];

		return materials[materials.Count - 1];
	}

	private static List<List<SliceTriangle>> CreateTriangleSlots( int count )
	{
		var output = new List<List<SliceTriangle>>( count );
		for ( var i = 0; i < count; i++ )
		{
			output.Add( new List<SliceTriangle>() );
		}

		return output;
	}

	private static void EnsureSlotCount( List<List<SliceTriangle>> slots, int count )
	{
		while ( slots.Count < count )
		{
			slots.Add( new List<SliceTriangle>() );
		}
	}

	private static SliceVertex InterpolateAtPlane( SliceVertex a, SliceVertex b, float da, float db )
	{
		var denominator = da - db;
		var t = MathF.Abs( denominator ) <= Epsilon ? 0.5f : da / denominator;
		t = Math.Clamp( t, 0.0f, 1.0f );
		return SliceVertex.Lerp( a, b, t );
	}

	private static bool IsVertexIndexValid( Vertex[] vertices, int index )
	{
		return index >= 0 && index < vertices.Length;
	}

	private static bool IsDegenerate( SliceTriangle triangle )
	{
		var ab = triangle.B.Position - triangle.A.Position;
		var ac = triangle.C.Position - triangle.A.Position;
		var area = Vector3.Cross( ab, ac ).Length;
		return area <= DegenerateAreaEpsilon;
	}

	private static void AddUniquePoint( List<Vector3> points, Vector3 point )
	{
		for ( var i = 0; i < points.Count; i++ )
		{
			if ( NearlyEqual( points[i], point, PositionMergeEpsilon ) )
				return;
		}

		points.Add( point );
	}

	private static void AddUniqueVertex( List<SliceVertex> vertices, SliceVertex vertex )
	{
		if ( vertices.Count == 0 )
		{
			vertices.Add( vertex );
			return;
		}

		var previous = vertices[vertices.Count - 1];
		if ( NearlyEqual( previous.Position, vertex.Position, PositionMergeEpsilon ) )
			return;

		vertices.Add( vertex );
	}

	private static bool NearlyEqual( Vector3 a, Vector3 b, float epsilon )
	{
		return (a - b).Length <= epsilon;
	}

	private static float SignedArea2D( Vector2 a, Vector2 b, Vector2 c )
	{
		return (a.x - b.x) * (b.y - c.y) - (b.x - c.x) * (a.y - b.y);
	}

	private static void ExpandBounds( Vector3 point, ref Vector3 mins, ref Vector3 maxs, ref bool hasBounds )
	{
		if ( !hasBounds )
		{
			mins = point;
			maxs = point;
			hasBounds = true;
			return;
		}

		mins = Vector3.Min( mins, point );
		maxs = Vector3.Max( maxs, point );
	}

	private struct SliceTriangle
	{
		public SliceVertex A;
		public SliceVertex B;
		public SliceVertex C;

		public SliceTriangle( SliceVertex a, SliceVertex b, SliceVertex c )
		{
			A = a;
			B = b;
			C = c;
		}
	}

	private struct SliceVertex
	{
		public Vector3 Position;
		public Vector3 Normal;
		public Vector4 Tangent;
		public Vector4 TexCoord0;
		public Color32 Color;

		public static SliceVertex From( Vertex source )
		{
			return new SliceVertex
			{
				Position = source.Position,
				Normal = source.Normal,
				Tangent = source.Tangent,
				TexCoord0 = source.TexCoord0,
				Color = source.Color
			};
		}

		public SliceVertex WithNormal( Vector3 normal )
		{
			var copy = this;
			copy.Normal = normal;
			return copy;
		}

		public static SliceVertex Lerp( SliceVertex a, SliceVertex b, float t )
		{
			return new SliceVertex
			{
				Position = Vector3.Lerp( a.Position, b.Position, t ),
				Normal = Vector3.Lerp( a.Normal, b.Normal, t ),
				Tangent = Vector4.Lerp( a.Tangent, b.Tangent, t ),
				TexCoord0 = Vector4.Lerp( a.TexCoord0, b.TexCoord0, t ),
				Color = LerpColor( a.Color, b.Color, t )
			};
		}

		private static Color32 LerpColor( Color32 a, Color32 b, float t )
		{
			return new Color32(
				LerpByte( a.r, b.r, t ),
				LerpByte( a.g, b.g, t ),
				LerpByte( a.b, b.b, t ),
				LerpByte( a.a, b.a, t ) );
		}

		private static byte LerpByte( byte a, byte b, float t )
		{
			var value = a + (b - a) * t;
			return (byte)Math.Clamp( (int)MathF.Round( value ), 0, 255 );
		}
	}

	private struct MappedPoint
	{
		public Vector3 Original;
		public Vector2 Mapped;
	}
}