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

namespace Sunless.Architecture;

public static class ArchDamage
{
	public enum MasonryCourse
	{
		None,
		Header,
		Double
	}

	const int SelectionSalt = 311;
	public const int StateSalt = 617;
	const int TiltSalt = 947;

	public static ArchCutAffects Targets( ArchDamageKind kind )
	{
		return kind switch
		{
			ArchDamageKind.Masonry => ArchCutAffects.Walls | ArchCutAffects.Pillars | ArchCutAffects.Trims,
			ArchDamageKind.SurfaceSpall => ArchCutAffects.Ceilings,
			ArchDamageKind.MissingPanels or ArchDamageKind.DisplacedPanels or ArchDamageKind.MixedPanels => ArchCutAffects.Ceilings,
			_ => ArchCutAffects.None
		};
	}

	public static IEnumerable<ArchCarveVolume> Resolve( ArchCutPart cut, ArchKit kit )
	{
		foreach ( var leg in cut.Legs() )
		{
			if ( Panels( cut.ResolvedDamage ) )
			{
				foreach ( var panel in PanelVolumes( cut, leg ) )
				{
					yield return panel;
				}

				continue;
			}

			var volume = ArchCut.Bite( cut, leg );

			if ( cut.ResolvedDamage == ArchDamageKind.Masonry )
			{
				var jitter = MathF.Max( kit?.BreakJitter ?? 0f, MathF.Max( 4f, cut.DamageCellWidth * 0.5f ) );
				volume = volume.Breaking( new ArchCarveBreak { Seed = Seed( cut ), Jitter = jitter } );
			}

			yield return volume;
		}
	}

	public static bool Panels( ArchDamageKind kind )
	{
		return kind is ArchDamageKind.MissingPanels or ArchDamageKind.DisplacedPanels or ArchDamageKind.MixedPanels;
	}

	public static bool Displaced( ArchCutPart cut, ArchCarveVolume volume )
	{
		if ( cut.ResolvedDamage == ArchDamageKind.DisplacedPanels )
		{
			return true;
		}

		if ( cut.ResolvedDamage != ArchDamageKind.MixedPanels )
		{
			return false;
		}

		return Noise( cut, volume, StateSalt ) >= 0.5f;
	}

	public static bool BakeToTarget( ArchPlan plan, ArchKit kit, ArchCutPart cut )
	{
		if ( plan?.OwnerOf( cut ) is not { } building || cut.ResolvedDamage != ArchDamageKind.Masonry )
		{
			return false;
		}

		var edge = MathF.Max( 2f, cut.DamageCellWidth );
		var half = edge * 0.5f;
		var targets = new List<(Vector2 Point, List<Vector2> Loop, float Bottom, float Top)>();

		foreach ( var room in building.Rooms.Where( room => room.Floor == cut.Level ) )
		{
			foreach ( var wall in room.Walls )
			{
				var top = room.BaseHeight + ArchWallSection.Height( wall, room, kit );

				foreach ( var point in new[] { wall.Start, wall.End } )
				{
					targets.Add( (point,
						ArchFootprint.Rect( point - new Vector2( half, half ), point + new Vector2( half, half ) ),
						room.BaseHeight, top) );
				}
			}

			foreach ( var pillar in room.Pillars.Where( pillar => pillar.Placement != PillarPlacement.Pilaster ) )
			{
				foreach ( var position in ArchAsks.PillarPositions( pillar ) )
				{
					var point = new Vector2( position.x, position.y );
					targets.Add( (point,
						ArchFootprint.Rect( point - pillar.Half, point + pillar.Half ),
						position.z, position.z + ArchAsks.PillarHeight( pillar, room, kit, plan )) );
				}
			}
		}

		var baked = false;

		foreach ( var segment in cut.Legs().ToList() )
		{
			var outline = segment.Outline();
			var centre = outline.Aggregate( Vector2.Zero, ( total, point ) => total + point ) / outline.Count;
			var target = targets
				.Where( entry => ArchFootprint.Overlaps( outline, entry.Loop ) )
				.OrderBy( entry => (entry.Point - centre).LengthSquared )
				.FirstOrDefault();

			if ( target.Loop is null )
			{
				continue;
			}

			segment.Start = target.Loop[0];
			segment.End = target.Loop[2];
			segment.Width = MathF.Max( target.Loop.Max( point => point.x ) - target.Loop.Min( point => point.x ),
				target.Loop.Max( point => point.y ) - target.Loop.Min( point => point.y ) );
			segment.BaseHeight = target.Bottom;
			segment.TopHeight = target.Top;
			segment.Loop = target.Loop;
			baked = true;
		}

		if ( baked )
		{
			cut.Profile = CutProfile.Poly;
		}

		return baked;
	}

	public static void WallCorners(
		ArchMesh canvas,
		ArchPlan plan,
		ArchKit kit,
		ArchBuilding building,
		ArchRoom room,
		ArchWall wall,
		float edgeFrom,
		float edgeTo,
		float height,
		float thickness,
		ArchStyle style,
		ArchConnectionService connections = null )
	{
		connections ??= new ArchConnectionService( building, kit );

		foreach ( var (cut, volume) in ArchCut.Damage( plan, room.Floor, kit, room.BaseHeight, room.BaseHeight + height, building.Id, ArchCutAffects.Walls, wall.Id ) )
		{
			if ( cut.ResolvedDamage != ArchDamageKind.Masonry )
			{
				continue;
			}

			var brush = style.Brush( ArchSurface.WallBase,
				new[] { cut.Palette, wall.Palette, room.Palette, building.Palette } );

			foreach ( var (point, along, direction) in new[]
			{
				(wall.Start, edgeFrom, -1f),
				(wall.End, edgeTo, 1f)
			} )
			{
				var adjacent = room.Walls
					.Where( candidate => candidate.Id != wall.Id && candidate.Length > 1f )
					.Where( candidate => (candidate.Start - point).Length < 0.1f || (candidate.End - point).Length < 0.1f )
					.Where( candidate => MathF.Abs( Vector2.Dot( candidate.Direction, wall.Direction ) ) < 0.99f )
					.OrderBy( candidate => candidate.Id )
					.FirstOrDefault();

				if ( adjacent is not null && wall.Id > adjacent.Id )
				{
					continue;
				}

				var reach = MathF.Max( 2f, cut.DamageCellWidth );
				var corner = ArchFootprint.Rect( point - new Vector2( reach, reach ), point + new Vector2( reach, reach ) );

				if ( !ArchFootprint.Overlaps( volume.Footprint, corner ) )
				{
					continue;
				}

				var bottom = Math.Clamp( volume.Floor.At( point ) - room.BaseHeight, 0f, height );
				var top = Math.Clamp( volume.Ceiling.At( point ) - room.BaseHeight, 0f, height );

				if ( adjacent is null )
				{
					BrickCorner( canvas, cut, wall.Id, along, direction, bottom, top, thickness, brush );
					continue;
				}

				var adjacentThickness = ArchWallSection.Thickness( adjacent, kit );
				var adjacentJoin = connections.Wall( adjacent, room ).WithThickness( adjacentThickness ).Create();
				var adjacentAtStart = (adjacent.Start - point).Length < 0.1f;
				var adjacentAlong = adjacentAtStart ? adjacentJoin.StartExtend : adjacentJoin.EndExtend;
				var adjacentDirection = adjacentAtStart ? -1f : 1f;

				JoinedBrickCorner( canvas, cut, wall, along, direction, thickness,
					adjacent, adjacentAlong, adjacentDirection, adjacentThickness, bottom, top, brush );
			}
		}
	}

	public static void PillarCorners(
		ArchMesh canvas,
		ArchPlan plan,
		ArchKit kit,
		ArchBuilding building,
		ArchRoom room,
		ArchPillarPart part,
		Vector3 origin,
		float height,
		ArchStyle style )
	{
		if ( part.Sides > 4 )
		{
			return;
		}

		var half = part.Half;
		var footprint = ArchFootprint.Rect( new Vector2( origin.x, origin.y ) - half, new Vector2( origin.x, origin.y ) + half );

		foreach ( var (cut, volume) in ArchCut.Damage( plan, room.Floor, kit, origin.z, origin.z + height, building.Id, ArchCutAffects.Pillars, part.Id ) )
		{
			if ( cut.ResolvedDamage != ArchDamageKind.Masonry || !ArchFootprint.Overlaps( volume.Footprint, footprint ) )
			{
				continue;
			}

			var brush = style.Brush( ArchSurface.WallBase,
				new[] { cut.Palette, part.Palette, room.Palette, building.Palette } );

			var bottom = Math.Clamp( volume.Floor.At( new Vector2( origin.x, origin.y ) ), origin.z, origin.z + height );
			var top = Math.Clamp( volume.Ceiling.At( new Vector2( origin.x, origin.y ) ), origin.z, origin.z + height );
			var width = MathF.Max( 2f, cut.DamageCellWidth );
			var course = MathF.Max( 2f, cut.DamageCellLength );
			var proud = MathF.Max( 0.5f, cut.DamageDepth );
			var socket = MathF.Min( width * 0.25f, MathF.Min( half.x, half.y ) * 0.5f );
			var joint = MathF.Min( 0.375f, course * 0.1f );
			var first = (int)MathF.Floor( bottom / course );
			var last = (int)MathF.Ceiling( top / course );

			for ( var z = first; z < last; z++ )
			{
				var state = CourseAt( cut, z, 1f );

				if ( state == MasonryCourse.None || !KeepsCourse( cut, part.Id, z ) )
				{
					continue;
				}

				var low = MathF.Max( bottom, z * course ) + joint;
				var high = MathF.Min( top, (z + 1) * course ) - joint;
				var reachNoise = BrickVariation( cut, part.Id, z );
				var stateScale = state == MasonryCourse.Double ? 1f : 0.45f;
				var reachX = MathF.Min( half.x, width * stateScale * (0.75f + reachNoise * 0.25f) );
				var reachY = MathF.Min( half.y, width * stateScale * (0.75f + reachNoise * 0.25f) );
				var runsAlongX = (z & 1) == 0;

				foreach ( var (corner, signX, signY) in new[]
				{
					(new Vector2( origin.x - half.x, origin.y - half.y ), -1f, -1f),
					(new Vector2( origin.x + half.x, origin.y - half.y ), 1f, -1f),
					(new Vector2( origin.x + half.x, origin.y + half.y ), 1f, 1f),
					(new Vector2( origin.x - half.x, origin.y + half.y ), -1f, 1f)
				} )
				{
					if ( !volume.Covers( corner ) )
					{
						continue;
					}

					if ( runsAlongX )
					{
						canvas.Box(
							new Vector3( corner.x - signX * reachX, corner.y - signY * socket, low ),
							new Vector3( corner.x + signX * socket, corner.y + signY * proud, high ),
							brush,
							tangent: Vector3.Forward );

						continue;
					}

					canvas.Box(
						new Vector3( corner.x - signX * socket, corner.y - signY * reachY, low ),
						new Vector3( corner.x + signX * proud, corner.y + signY * socket, high ),
						brush,
						tangent: Vector3.Forward );
				}
			}
		}
	}

	public static IEnumerable<(List<Vector3> Points, bool Closed)> Surviving(
		ArchPlan plan,
		ArchKit kit,
		int level,
		int hostId,
		IReadOnlyList<Vector3> path )
	{
		var runs = new List<List<Vector3>>();

		for ( var index = 0; index + 1 < (path?.Count ?? 0); index++ )
		{
			var from = path[index];
			var to = path[index + 1];
			var flatFrom = new Vector2( from.x, from.y );
			var flatTo = new Vector2( to.x, to.y );
			var blocked = ArchCut.Damage( plan, level, kit, MathF.Min( from.z, to.z ), MathF.Max( from.z, to.z ), hostId, ArchCutAffects.Trims )
				.Where( found => found.Cut.ResolvedDamage == ArchDamageKind.Masonry )
				.SelectMany( found => ArchFootprint.Inside( found.Volume.Footprint, flatFrom, flatTo ) )
				.ToList();
			var marks = blocked.SelectMany( range => new[] { Math.Clamp( range.From, 0f, 1f ), Math.Clamp( range.To, 0f, 1f ) } )
				.Append( 0f )
				.Append( 1f )
				.Distinct()
				.OrderBy( value => value )
				.ToList();

			for ( var mark = 0; mark + 1 < marks.Count; mark++ )
			{
				var start = marks[mark];
				var finish = marks[mark + 1];
				var middle = (start + finish) * 0.5f;

				if ( finish - start < 0.001f || blocked.Any( range => middle > range.From && middle < range.To ) )
				{
					continue;
				}

				var first = Vector3.Lerp( from, to, start );
				var last = Vector3.Lerp( from, to, finish );
				var run = runs.LastOrDefault();

				if ( run is null || (run[^1] - first).Length > 0.05f )
				{
					run = new List<Vector3> { first };
					runs.Add( run );
				}

				run.Add( last );
			}
		}

		foreach ( var run in runs.Where( run => run is { Count: >= 2 } ) )
		{
			var closed = ArchRunPath.IsClosed( run );

			yield return (closed ? run.Take( run.Count - 1 ).ToList() : run, closed);
		}
	}

	public static void DisplacedPanel( ArchMesh canvas, ArchCutPart cut, ArchCarveVolume volume, float soffit, ArchBrush brush )
	{
		var loop = volume.Footprint.ToList();

		if ( loop.Count < 3 )
		{
			return;
		}

		var centre = loop.Aggregate( Vector2.Zero, ( total, point ) => total + point ) / loop.Count;
		var pitch = (Noise( cut, volume, TiltSalt ) * 2f - 1f) * MathF.Max( 0f, cut.DamageTilt );
		var roll = (Noise( cut, volume, TiltSalt + 1 ) * 2f - 1f) * MathF.Max( 0f, cut.DamageTilt );
		var rotation = Rotation.From( pitch, 0f, roll );
		var top = soffit - MathF.Max( 0.5f, cut.DamageDrop );
		var thickness = MathF.Max( 0.35f, MathF.Min( 1f, cut.DamageDrop * 0.2f ) );
		var lower = new List<Vector3>();
		var upper = new List<Vector3>();

		foreach ( var point in loop )
		{
			var local = new Vector3( point.x - centre.x, point.y - centre.y, 0f );
			var turned = rotation * local;

			lower.Add( new Vector3( centre.x + turned.x, centre.y + turned.y, top + turned.z - thickness ) );
			upper.Add( new Vector3( centre.x + turned.x, centre.y + turned.y, top + turned.z ) );
		}

		canvas.Prism( lower, upper, brush );
	}

	static void BrickCorner( ArchMesh canvas, ArchCutPart cut, int wallId, float along, float direction, float bottom, float top, float thickness, ArchBrush brush )
	{
		var width = MathF.Max( 2f, cut.DamageCellWidth );
		var course = MathF.Max( 2f, cut.DamageCellLength );
		var half = thickness * 0.5f;
		var recess = MathF.Min( MathF.Max( 0.25f, cut.DamageDepth ), MathF.Max( 0.25f, thickness - 0.5f ) );
		var socket = MathF.Min( 1f, course * 0.2f );
		var joint = MathF.Min( 0.375f, course * 0.1f );
		var extrusion = MathF.Min( 1.5f, MathF.Max( 0.5f, recess * 0.25f ) );
		var back = MathF.Min( 0f, -half + recess );
		var first = (int)MathF.Floor( bottom / course );
		var last = (int)MathF.Ceiling( top / course );

		for ( var z = first; z < last; z++ )
		{
			var state = CourseAt( cut, z, direction );

			if ( state == MasonryCourse.None || !KeepsCourse( cut, wallId, z ) )
			{
				continue;
			}

			var low = MathF.Max( bottom, z * course ) + joint;
			var high = MathF.Min( top, (z + 1) * course ) - joint;
			var into = direction < 0f ? 1f : -1f;
			var variation = BrickVariation( cut, wallId, z );
			var lengthScale = 0.88f + variation * 0.16f;
			var courseSocket = socket * (0.8f + variation * 0.4f);
			var front = -half - extrusion * (0.8f + variation * 0.35f);

			if ( state == MasonryCourse.Header )
			{
				var header = MathF.Max( course * 1.25f, width * 0.35f ) * lengthScale;

				Brick( canvas, along, into, -courseSocket, header, front, back, low, high, brush );

				continue;
			}

			var primaryLength = width * lengthScale;

			Brick( canvas, along, into, -courseSocket, primaryLength, front, back, low, high, brush );
		}
	}

	static void JoinedBrickCorner(
		ArchMesh canvas,
		ArchCutPart cut,
		ArchWall owner,
		float ownerAlong,
		float ownerDirection,
		float ownerThickness,
		ArchWall adjacent,
		float adjacentAlong,
		float adjacentDirection,
		float adjacentThickness,
		float bottom,
		float top,
		ArchBrush brush )
	{
		var course = MathF.Max( 2f, cut.DamageCellLength );
		var joint = MathF.Min( 0.375f, course * 0.1f );
		var first = (int)MathF.Floor( bottom / course );
		var last = (int)MathF.Ceiling( top / course );
		var hostId = Math.Min( owner.Id, adjacent.Id );

		for ( var z = first; z < last; z++ )
		{
			if ( !KeepsCourse( cut, hostId, z ) )
			{
				continue;
			}

			var low = MathF.Max( bottom, z * course ) + joint;
			var high = MathF.Min( top, (z + 1) * course ) - joint;
			var loops = new List<IReadOnlyList<Vector2>>();

			AddJoinedBrickLoop( loops, cut, owner, owner, ownerAlong, ownerDirection, ownerThickness, z );
			AddJoinedBrickLoop( loops, cut, owner, adjacent, adjacentAlong, adjacentDirection, adjacentThickness, z );

			var loop = ConvexHull( ArchFootprint.Union( loops ).SelectMany( region => region ) );

			if ( loop.Count >= 3 )
			{
				CornerPrism( canvas, loop, low, high, brush );
			}
		}
	}

	static void CornerPrism( ArchMesh canvas, IReadOnlyList<Vector2> loop, float low, float high, ArchBrush brush )
	{
		var bottom = loop.Select( point => new Vector3( point.x, point.y, low ) ).ToList();
		var top = loop.Select( point => new Vector3( point.x, point.y, high ) ).ToList();

		if ( loop.Count != 6 )
		{
			canvas.Prism( bottom, top, brush, tangent: Vector3.Forward );
			return;
		}

		using var solid = canvas.Solid( ArchSolid.Hull( bottom.Concat( top ).ToList() ) );

		for ( var index = 0; index < loop.Count; index++ )
		{
			var next = (index + 1) % loop.Count;
			canvas.Ribbon( bottom[index], bottom[next], top[next], top[index], Vector3.Forward, brush );
		}

		canvas.Ribbon( bottom[3], bottom[2], bottom[1], bottom[0], Vector3.Forward, brush );
		canvas.Ribbon( bottom[5], bottom[4], bottom[3], bottom[0], Vector3.Forward, brush );
		canvas.Ribbon( top[0], top[1], top[2], top[3], Vector3.Forward, brush );
		canvas.Ribbon( top[0], top[3], top[4], top[5], Vector3.Forward, brush );
	}

	static List<Vector2> ConvexHull( IEnumerable<Vector2> points )
	{
		var ordered = points.Distinct().OrderBy( point => point.x ).ThenBy( point => point.y ).ToList();

		if ( ordered.Count <= 3 )
		{
			return ordered;
		}

		var lower = new List<Vector2>();

		foreach ( var point in ordered )
		{
			while ( lower.Count >= 2 && Turn( lower[^2], lower[^1], point ) <= 0f )
			{
				lower.RemoveAt( lower.Count - 1 );
			}

			lower.Add( point );
		}

		var upper = new List<Vector2>();

		for ( var index = ordered.Count - 1; index >= 0; index-- )
		{
			var point = ordered[index];

			while ( upper.Count >= 2 && Turn( upper[^2], upper[^1], point ) <= 0f )
			{
				upper.RemoveAt( upper.Count - 1 );
			}

			upper.Add( point );
		}

		lower.RemoveAt( lower.Count - 1 );
		upper.RemoveAt( upper.Count - 1 );
		lower.AddRange( upper );

		return lower;
	}

	static float Turn( Vector2 from, Vector2 through, Vector2 to )
	{
		return (through.x - from.x) * (to.y - from.y) - (through.y - from.y) * (to.x - from.x);
	}

	static void AddJoinedBrickLoop(
		List<IReadOnlyList<Vector2>> loops,
		ArchCutPart cut,
		ArchWall owner,
		ArchWall leg,
		float along,
		float direction,
		float thickness,
		int course )
	{
		var state = CourseAt( cut, course, direction );

		if ( state == MasonryCourse.None )
		{
			return;
		}

		var width = MathF.Max( 2f, cut.DamageCellWidth );
		var courseHeight = MathF.Max( 2f, cut.DamageCellLength );
		var half = thickness * 0.5f;
		var recess = MathF.Min( MathF.Max( 0.25f, cut.DamageDepth ), MathF.Max( 0.25f, thickness - 0.5f ) );
		var extrusion = MathF.Min( 1.5f, MathF.Max( 0.5f, recess * 0.25f ) );
		var variation = BrickVariation( cut, leg.Id, course );
		var lengthScale = 0.88f + variation * 0.16f;
		var socket = MathF.Min( 1f, courseHeight * 0.2f ) * (0.8f + variation * 0.4f);
		var length = state == MasonryCourse.Header
			? MathF.Max( courseHeight * 1.25f, width * 0.35f ) * lengthScale
			: width * lengthScale;
		var front = -half - extrusion * (0.8f + variation * 0.35f);
		var back = MathF.Min( 0f, -half + recess );
		var anchor = leg.Start + leg.Direction * along;
		var into = leg.Direction * (direction < 0f ? 1f : -1f);
		var world = new[]
		{
			anchor - into * socket + leg.Normal * front,
			anchor + into * length + leg.Normal * front,
			anchor + into * length + leg.Normal * back,
			anchor - into * socket + leg.Normal * back
		};

		loops.Add( world.Select( point =>
		{
			var delta = point - owner.Start;
			return new Vector2( Vector2.Dot( delta, owner.Direction ), Vector2.Dot( delta, owner.Normal ) );
		} ).ToList() );
	}

	static void Brick( ArchMesh canvas, float edge, float into, float from, float to, float front, float back, float low, float high, ArchBrush brush )
	{
		canvas.Box(
			new Vector3( edge + into * from, front, low ),
			new Vector3( edge + into * to, back, high ),
			brush,
			tangent: Vector3.Forward );
	}

	public static MasonryCourse CourseAt( ArchCutPart cut, int course, float direction )
	{
		var oppositeFace = direction > 0f;
		var phase = cut.MasonryPattern switch
		{
			ArchMasonryPattern.BrickPier => ((course % 2) + 2) % 2,
			ArchMasonryPattern.WornCorner => ((course % 4) + 4) % 4,
			_ => ((course % 6) + 6) % 6
		};

		return cut.MasonryPattern switch
		{
			ArchMasonryPattern.BrickPier => Interlocked( phase == 0, oppositeFace ),
			ArchMasonryPattern.WornCorner => phase == 3 ? MasonryCourse.None : Interlocked( phase % 2 == 0, oppositeFace ),
			_ => phase is 2 or 4 ? MasonryCourse.None : Interlocked( phase is 0 or 3, oppositeFace )
		};
	}

	static float BrickVariation( ArchCutPart cut, int hostId, int course )
	{
		return ArchBarrierShape.Noise( Seed( cut ), hostId ^ course * 83492791, StateSalt ) < 0.5f ? 0.25f : 0.75f;
	}

	static MasonryCourse Interlocked( bool stretcherOnFirstFace, bool oppositeFace )
	{
		return stretcherOnFirstFace != oppositeFace ? MasonryCourse.Double : MasonryCourse.Header;
	}

	public static bool KeepsCourse( ArchCutPart cut, int hostId, int course )
	{
		return ArchBarrierShape.Noise( Seed( cut ), hostId ^ course * 19349663, SelectionSalt ) <= Math.Clamp( cut.DamageAmount, 0f, 1f );
	}

	static IEnumerable<ArchCarveVolume> PanelVolumes( ArchCutPart cut, ArchCutSegment leg )
	{
		var footprint = leg.Outline();
		var width = MathF.Max( 4f, cut.DamageCellWidth );
		var length = MathF.Max( 4f, cut.DamageCellLength );
		var amount = Math.Clamp( cut.DamageAmount, 0f, 1f );

		ArchFootprint.Bounds( footprint, out var min, out var max );

		var fromX = (int)MathF.Floor( min.x / width );
		var toX = (int)MathF.Ceiling( max.x / width );
		var fromY = (int)MathF.Floor( min.y / length );
		var toY = (int)MathF.Ceiling( max.y / length );

		for ( var x = fromX; x < toX; x++ )
		{
			for ( var y = fromY; y < toY; y++ )
			{
				var cellMin = new Vector2( MathF.Max( min.x, x * width ), MathF.Max( min.y, y * length ) );
				var cellMax = new Vector2( MathF.Min( max.x, (x + 1) * width ), MathF.Min( max.y, (y + 1) * length ) );
				var cell = Clip( ArchFootprint.Rect( cellMin, cellMax ), footprint );

				if ( cell.Count < 3 || MathF.Abs( ArchFootprint.SignedArea( cell ) ) < 4f )
				{
					continue;
				}

				var index = x * 73856093 ^ y * 19349663;

				if ( ArchBarrierShape.Noise( Seed( cut ), index, SelectionSalt ) > amount )
				{
					continue;
				}

				yield return ArchCarveVolume.Over( cell, leg.BaseHeight, leg.TopHeight );
			}
		}
	}

	static List<Vector2> Clip( IReadOnlyList<Vector2> subject, IReadOnlyList<Vector2> boundary )
	{
		var clipped = subject.ToList();
		var winding = ArchFootprint.SignedArea( boundary ) >= 0f ? 1f : -1f;

		for ( var edge = 0; edge < boundary.Count && clipped.Count > 0; edge++ )
		{
			var from = boundary[edge];
			var to = boundary[(edge + 1) % boundary.Count];
			var input = clipped;
			clipped = new List<Vector2>();
			var previous = input[^1];
			var previousInside = Side( from, to, previous ) * winding >= -0.01f;

			foreach ( var current in input )
			{
				var currentInside = Side( from, to, current ) * winding >= -0.01f;

				if ( currentInside != previousInside )
				{
					clipped.Add( Intersection( previous, current, from, to ) );
				}

				if ( currentInside )
				{
					clipped.Add( current );
				}

				previous = current;
				previousInside = currentInside;
			}
		}

		return ArchFootprint.Wind( clipped );
	}

	static Vector2 Intersection( Vector2 a, Vector2 b, Vector2 c, Vector2 d )
	{
		var ab = b - a;
		var cd = d - c;
		var divisor = ab.x * cd.y - ab.y * cd.x;

		if ( MathF.Abs( divisor ) < 0.0001f )
		{
			return b;
		}

		var offset = c - a;
		var along = (offset.x * cd.y - offset.y * cd.x) / divisor;

		return a + ab * along;
	}

	static float Side( Vector2 a, Vector2 b, Vector2 point )
	{
		return (b.x - a.x) * (point.y - a.y) - (b.y - a.y) * (point.x - a.x);
	}

	static float Noise( ArchCutPart cut, ArchCarveVolume volume, int salt )
	{
		var centre = volume.Footprint.Aggregate( Vector2.Zero, ( total, point ) => total + point ) / volume.Footprint.Count;
		var index = (int)MathF.Round( centre.x * 17f ) ^ (int)MathF.Round( centre.y * 31f );

		return ArchBarrierShape.Noise( Seed( cut ), index, salt );
	}

	public static int Seed( ArchCutPart cut )
	{
		return cut.Id == 0 ? 1 : cut.Id;
	}
}