s&box Package Code Search
Search C# source code, UI razor templates, shaders, and configs across s&box packages.
link Raw Facepunch API Link: https://public.facepunch.com/sbox/code/search/1/?ident=facepunch.libpolygon&take=20
Showing code results for query:
*
(9 total matches found)
Game
library
using System;
using System.Collections.Generic;
namespace Sandbox.Polygons;
public class PolygonModelRenderer : ModelRenderer
{
private Mesh _mesh;
private string _svg;
private bool _meshDirty;
/// <summary>
/// Scalable Vector Graphics source string for this model.
/// </summary>
[Property]
public string Svg
{
get => _svg;
set
{
_svg = value;
_meshDirty = true;
}
}
private int _lastHash = 0;
protected override void OnEnabled()
{
base.OnEnabled();
UpdateModel();
}
protected override void OnValidate()
{
base.OnValidate();
_meshDirty = true;
}
private void UpdateModel()
{
if ( !_meshDirty )
{
return;
}
var hash = Svg?.FastHash() ?? 0;
if ( _lastHash == hash )
{
return;
}
if ( Model?.IsProcedural is not true )
{
Model = null;
}
_lastHash = hash;
if ( !string.IsNullOrEmpty( Svg ) )
{
using var builder = PolygonMeshBuilder.Rent();
builder.MaxSmoothAngle = 33f.DegreeToRadian();
builder.AddSvg( _svg, new AddSvgOptions
{
ThrowIfNotSupported = true
}, new Rect( -128f, -128f, 256f, 256f ) );
builder.Extrude( 8f );
builder.Arc( 2f, 2 );
builder.Fill();
builder.Mirror();
_mesh ??= new Mesh( Material.Load( "materials/default/white.vmat" ) );
_mesh.UpdateMesh( PolygonMeshBuilder.Vertex.Layout, builder.Vertices, builder.Indices );
Model ??= new ModelBuilder()
.AddMesh( _mesh )
.Create();
}
else
{
_mesh?.SetIndexRange( 0, 0 );
}
}
protected override void OnUpdate()
{
UpdateModel();
base.OnUpdate();
}
}
Game
library
namespace Sandbox.Polygons;
partial class PolygonMeshBuilder
{
private struct Edge
{
public int Index { get; }
public Vector2 Origin { get; }
public Vector2 Tangent { get; }
public Vector2 Normal { get; }
public Vector2 Velocity { get; set; }
public int PrevEdge { get; set; }
public int NextEdge { get; set; }
public float Distance { get; set; }
public float MaxDistance { get; set; }
public (int Prev, int Next) Vertices { get; set; }
public int Twin { get; }
public Edge( int index, Vector2 origin, Vector2 tangent, float distance, int twin = -1 )
{
Index = index;
Origin = origin;
Tangent = tangent;
Normal = Helpers.Rotate90( tangent );
Velocity = Vector2.Zero;
PrevEdge = -1;
NextEdge = -1;
Vertices = (-1, -1);
Distance = distance;
MaxDistance = float.PositiveInfinity;
Twin = twin;
}
public readonly Vector2 Project( float distance )
{
return Origin + Velocity * (distance - Distance);
}
public override string ToString()
{
return $"{(char) ('A' + Index)}";
}
public bool Equals( Edge other )
{
return Index == other.Index;
}
public override bool Equals( object obj )
{
return obj is Edge other && Equals( other );
}
public override int GetHashCode()
{
return Index;
}
}
}
Game
library
using System;
using System.Collections.Generic;
namespace Sandbox.Polygons;
internal static class Helpers
{
public static Vector2 NormalizeSafe( in Vector2 vec )
{
var length = vec.Length;
if ( length > 9.9999997473787516E-06 )
{
return vec / length;
}
else
{
return 0f;
}
}
public static Vector2 Rotate90( Vector2 v )
{
return new Vector2( v.y, -v.x );
}
public static float Cross( Vector2 a, Vector2 b )
{
return a.x * b.y - a.y * b.x;
}
public static bool LineSegmentsIntersect( Vector2 a0, Vector2 a1, Vector2 b0, Vector2 b1 )
{
return Math.Sign( Cross( a0 - b0, b1 - b0 ) ) != Math.Sign( Cross( a1 - b0, b1 - b0 ) )
&& Math.Sign( Cross( b0 - a0, a1 - a0 ) ) != Math.Sign( Cross( b1 - a0, a1 - a0 ) );
}
public static Vector3 RotateNormal( Vector3 oldNormal, float sin, float cos )
{
var normal2d = new Vector2( oldNormal.x, oldNormal.y );
if ( normal2d.LengthSquared <= 0.000001f )
{
return oldNormal;
}
normal2d = NormalizeSafe( normal2d );
return new Vector3( normal2d.x * cos, normal2d.y * cos, sin ).Normal;
}
public static float GetEpsilon( Vector2 vec, float frac = 0.0001f )
{
return Math.Max( Math.Abs( vec.x ), Math.Abs( vec.y ) ) * frac;
}
public static float GetEpsilon( Vector2 a, Vector2 b, float frac = 0.0001f )
{
return Math.Max( GetEpsilon( a, frac ), GetEpsilon( b, frac ) );
}
public static void UpdateMesh<T>( this Mesh mesh, VertexAttribute[] layout, List<T> vertices, List<int> indices )
where T : unmanaged
{
if ( !mesh.HasIndexBuffer )
{
mesh.CreateVertexBuffer( vertices.Count, layout, vertices );
mesh.CreateIndexBuffer( indices.Count, indices );
}
else if ( indices.Count > 0 && vertices.Count > 0 )
{
mesh.SetIndexBufferSize( indices.Count );
mesh.SetVertexBufferSize( vertices.Count );
mesh.SetVertexBufferData( vertices );
mesh.SetIndexBufferData( indices );
}
mesh.SetIndexRange( 0, indices.Count );
}
}
Game
library
using System;
using System.Collections.Generic;
using System.Linq;
namespace Sandbox.Polygons;
partial class PolygonMeshBuilder
{
/// <summary>
/// Triangulate any remaining active edges so that the generated mesh is closed.
/// </summary>
public PolygonMeshBuilder Fill()
{
Validate();
Fill_UpdateExistingVertices();
Fill_SplitIntoMonotonicPolygons();
Fill_Triangulate();
PostBevel();
return this;
}
private enum SweepEvent
{
Start,
End,
Split,
Merge,
Upper,
Lower
}
private static SweepEvent CategorizeEvent( in Edge prev, in Edge curr, in Edge next )
{
var prevLeft = Compare( prev.Origin, curr.Origin ) < 0;
var nextLeft = Compare( next.Origin, curr.Origin ) < 0;
var nextBelow = curr.Tangent.y < -prev.Tangent.y;
switch (prevLeft, nextLeft, nextBelow)
{
case (false, false, false ):
return SweepEvent.Start;
case (true, true, true ):
return SweepEvent.End;
case (false, false, true ):
return SweepEvent.Split;
case (true, true, false ):
return SweepEvent.Merge;
case (true, false, _ ):
return SweepEvent.Upper;
case (false, true, _ ):
return SweepEvent.Lower;
}
}
[ThreadStatic]
private static List<int> Fill_SortedEdges;
[ThreadStatic]
private static Dictionary<int, (int Index, bool WasMerge)> Fill_Helpers;
[ThreadStatic]
private static List<SweepEdge> Fill_SweepEdges;
private readonly struct SweepEdge
{
public int Index { get; }
public Vector2 Origin { get; }
public float DeltaY { get; }
public SweepEdge( in Edge edge )
{
Index = edge.Index;
Origin = edge.Origin;
DeltaY = Math.Abs( edge.Tangent.x ) <= 0.0001f
? 0f : edge.Tangent.y / edge.Tangent.x;
}
public float GetEdgeY( float x )
{
return Origin.y + DeltaY * (x - Origin.x);
}
}
private int ConnectTwoWay( ref Edge a, ref Edge b )
{
ref var prevA = ref _allEdges[a.PrevEdge];
ref var prevB = ref _allEdges[b.PrevEdge];
ref var aNew = ref _allEdges[AddEdge( a.Origin, (b.Origin - a.Origin).Normal, a.Distance )];
ref var bNew = ref _allEdges[AddEdge( b.Origin, (a.Origin - b.Origin).Normal, b.Distance )];
aNew.Vertices = AddVertices( ref a );
bNew.Vertices = AddVertices( ref b );
SimpleConnectEdges( ref prevA, ref aNew );
SimpleConnectEdges( ref aNew, ref b );
SimpleConnectEdges( ref prevB, ref bNew );
SimpleConnectEdges( ref bNew, ref a );
_activeEdges.Add( aNew.Index );
_activeEdges.Add( bNew.Index );
return aNew.Index;
}
private int FixUp( ref Edge v, in Edge e )
{
var helperInfo = Fill_Helpers[e.Index];
if ( helperInfo.WasMerge )
{
return ConnectTwoWay( ref v, ref _allEdges[helperInfo.Index] );
}
return v.Index;
}
private void SetHelper( in Edge edge, in Edge helper, bool wasMerge )
{
Fill_Helpers[edge.Index] = (helper.Index, wasMerge);
}
private void AddSweepEdge( in Edge edge )
{
// TODO: could binary search for insertion point
var origin = edge.Origin;
Fill_SweepEdges.Add( new SweepEdge( edge ) );
Fill_SweepEdges.Sort( ( a, b ) =>
a.GetEdgeY( origin.x ).CompareTo( b.GetEdgeY( origin.x ) ) );
}
private void ReplaceSweepEdge( in Edge old, in Edge replacement )
{
// TODO: could binary search
for ( var i = 0; i < Fill_SweepEdges.Count; ++i )
{
if ( Fill_SweepEdges[i].Index == old.Index )
{
Fill_SweepEdges[i] = new SweepEdge( in replacement );
break;
}
}
}
private void RemoveSweepEdge( in Edge edge )
{
// TODO: could binary search
for ( var i = 0; i < Fill_SweepEdges.Count; ++i )
{
if ( Fill_SweepEdges[i].Index == edge.Index )
{
Fill_SweepEdges.RemoveAt( i );
break;
}
}
}
private int FindAboveSweepEdge( in Edge edge )
{
// TODO: could binary search
foreach ( var other in Fill_SweepEdges )
{
if ( edge.PrevEdge == other.Index || edge.Index == other.Index )
{
continue;
}
if ( other.GetEdgeY( edge.Origin.x ) - edge.Origin.y >= 0f )
{
return other.Index;
}
}
throw new Exception();
}
private void Fill_UpdateExistingVertices()
{
_nextAngle = MathF.PI * 0.5f;
_nextDistance = float.PositiveInfinity;
if ( !SkipNormals && Math.Abs( _prevAngle - _nextAngle ) >= 0.001f )
{
foreach ( var index in _activeEdges )
{
ref var edge = ref _allEdges[index];
edge.Vertices = (-1, -1);
AddVertices( ref edge, true );
}
}
_prevAngle = _nextAngle;
}
private void Fill_SplitIntoMonotonicPolygons()
{
Fill_SortedEdges ??= new List<int>();
Fill_SortedEdges.Clear();
Fill_SortedEdges.AddRange( _activeEdges );
Fill_SortedEdges.Sort( ( a, b ) => Compare( _allEdges[a].Origin, _allEdges[b].Origin ) );
Fill_Helpers ??= new Dictionary<int, (int Index, bool WasMerge)>();
Fill_Helpers.Clear();
Fill_SweepEdges ??= new List<SweepEdge>();
Fill_SweepEdges.Clear();
// Based on https://www.cs.umd.edu/class/spring2020/cmsc754/Lects/lect05-triangulate.pdf
// Add pairs of edges to split into x-monotonic polygons
foreach ( var index in Fill_SortedEdges )
{
EnsureCapacity( 4 );
ref var edge = ref _allEdges[index];
ref var next = ref _allEdges[edge.NextEdge];
ref var prev = ref _allEdges[edge.PrevEdge];
switch ( CategorizeEvent( in prev, in edge, in next ) )
{
case SweepEvent.Start:
AddSweepEdge( in edge );
SetHelper( in edge, in edge, false );
break;
case SweepEvent.End:
FixUp( ref edge, in prev );
RemoveSweepEdge( in prev );
break;
case SweepEvent.Split:
{
ref var above = ref _allEdges[FindAboveSweepEdge( in edge )];
ref var helper = ref _allEdges[Fill_Helpers[above.Index].Index];
ref var fixedUp = ref _allEdges[ConnectTwoWay( ref edge, ref helper )];
AddSweepEdge( in edge );
SetHelper( in above, in fixedUp, false );
SetHelper( in edge, in edge, false );
break;
}
case SweepEvent.Merge:
{
ref var above = ref _allEdges[FindAboveSweepEdge( in edge )];
RemoveSweepEdge( in prev );
ref var new1 = ref _allEdges[FixUp( ref edge, in above )];
FixUp( ref new1, in prev );
SetHelper( in above, in new1, true );
break;
}
case SweepEvent.Upper:
FixUp( ref edge, in prev );
ReplaceSweepEdge( in prev, in edge );
SetHelper( in edge, in edge, false );
break;
case SweepEvent.Lower:
{
ref var above = ref _allEdges[FindAboveSweepEdge( in edge )];
ref var helper = ref _allEdges[FixUp( ref edge, in above )];
SetHelper( in above, in helper, false );
break;
}
}
}
}
private readonly struct CloseVertex
{
public Vector2 Position { get; }
/// <summary>
/// Difference to this vertex from the previous one.
/// </summary>
public Vector2 Delta { get; }
public int Vertex { get; }
public bool IsUpper { get; }
public CloseVertex( Vector2 position, Vector2 delta, int vertex, bool isUpper )
{
Position = position;
Delta = delta;
Vertex = vertex;
IsUpper = isUpper;
}
}
[ThreadStatic]
private static List<CloseVertex> Fill_Vertices;
[ThreadStatic]
private static Stack<CloseVertex> Fill_Stack;
private static bool IsReflex( Vector2 prevDelta, Vector2 nextDelta )
{
return Vector2.Dot( Helpers.Rotate90( nextDelta ), prevDelta ) >= 0f;
}
private static int Compare( Vector2 a, Vector2 b )
{
var xCompare = a.x.CompareTo( b.x );
if ( xCompare != 0 ) return xCompare;
return a.y.CompareTo( b.y );
}
private void Fill_Triangulate()
{
Fill_Vertices ??= new List<CloseVertex>();
Fill_Stack ??= new Stack<CloseVertex>();
while ( _activeEdges.Count > 0 )
{
var firstIndex = _activeEdges.First();
_activeEdges.Remove( firstIndex );
var first = _allEdges[firstIndex];
var minPos = first.Origin;
var maxPos = first.Origin;
var minEdgeIndex = firstIndex;
var maxEdgeIndex = firstIndex;
var edge = first;
while ( edge.NextEdge != first.Index )
{
edge = _allEdges[edge.NextEdge];
_activeEdges.Remove( edge.Index );
if ( Compare( edge.Origin, minPos ) < 0 )
{
minPos = edge.Origin;
minEdgeIndex = edge.Index;
}
if ( Compare( edge.Origin, maxPos ) > 0 )
{
maxPos = edge.Origin;
maxEdgeIndex = edge.Index;
}
}
Fill_Vertices.Clear();
edge = _allEdges[minEdgeIndex];
Fill_Vertices.Add( new CloseVertex( edge.Origin, default, edge.Vertices.Prev, true ) );
while ( edge.NextEdge != maxEdgeIndex )
{
var next = _allEdges[edge.NextEdge];
Fill_Vertices.Add( new CloseVertex( next.Origin, next.Origin - edge.Origin, next.Vertices.Prev, true ) );
edge = next;
}
edge = _allEdges[maxEdgeIndex];
while ( edge.Index != minEdgeIndex )
{
var next = _allEdges[edge.NextEdge];
Fill_Vertices.Add( new CloseVertex( edge.Origin, edge.Origin - next.Origin, edge.Vertices.Prev, false ) );
edge = next;
}
Fill_Vertices.Sort( ( a, b ) => Compare( a.Position, b.Position ) );
Fill_Stack.Clear();
Fill_Stack.Push( Fill_Vertices[0] );
Fill_Stack.Push( Fill_Vertices[1] );
for ( var i = 2; i < Fill_Vertices.Count; ++i )
{
var next = Fill_Vertices[i];
var top = Fill_Stack.Peek();
if ( top.IsUpper != next.IsUpper )
{
// Case 1
while ( Fill_Stack.Count > 1 )
{
var curr = Fill_Stack.Pop();
var prev = Fill_Stack.Peek();
if ( next.IsUpper )
{
AddTriangle( next.Vertex, prev.Vertex, curr.Vertex );
}
else
{
AddTriangle( next.Vertex, curr.Vertex, prev.Vertex );
}
}
Fill_Stack.Clear();
Fill_Stack.Push( top );
Fill_Stack.Push( new CloseVertex( next.Position,
next.Position - top.Position,
next.Vertex, next.IsUpper ) );
continue;
}
while ( Fill_Stack.Count > 1 && IsReflex( top.Delta, next.Position - top.Position ) != top.IsUpper )
{
var curr = Fill_Stack.Pop();
top = Fill_Stack.Peek();
if ( next.IsUpper )
{
AddTriangle( next.Vertex, curr.Vertex, top.Vertex );
}
else
{
AddTriangle( next.Vertex, top.Vertex, curr.Vertex );
}
}
Fill_Stack.Push( new CloseVertex( next.Position,
next.Position - top.Position,
next.Vertex, next.IsUpper ) );
}
}
}
}
Game
library
using System;
using System.Collections.Generic;
namespace Sandbox.Polygons;
partial class PolygonMeshBuilder
{
[ThreadStatic]
private static List<int> Validate_EdgeList;
private void Validate()
{
if ( _validated )
{
return;
}
// Check active edge loops:
// * Referenced edges must also be active
// * Make sure references are correct in both directions
// * Edges can't reference themselves
foreach ( var edgeIndex in _activeEdges )
{
ref var edge = ref _allEdges[edgeIndex];
if ( !_activeEdges.Contains( edge.NextEdge ) )
{
throw InvalidPolygonException();
}
if ( !_activeEdges.Contains( edge.PrevEdge ) )
{
throw InvalidPolygonException();
}
if ( edge.NextEdge == edge.Index )
{
throw InvalidPolygonException();
}
ref var next = ref _allEdges[edge.NextEdge];
if ( next.PrevEdge != edge.Index )
{
throw InvalidPolygonException();
}
}
// Check for intersecting edges
// TODO: Bentley–Ottmann?
Validate_EdgeList ??= new List<int>();
Validate_EdgeList.Clear();
Validate_EdgeList.AddRange( _activeEdges );
for ( var i = 0; i < Validate_EdgeList.Count; ++i )
{
ref var edgeA0 = ref _allEdges[Validate_EdgeList[i]];
ref var edgeA1 = ref _allEdges[edgeA0.NextEdge];
var a0 = edgeA0.Origin;
var a1 = edgeA1.Origin;
var minA = Vector2.Min( a0 ,a1 );
var maxA = Vector2.Max( a0, a1 );
for ( var j = i + 1; j < Validate_EdgeList.Count; ++j )
{
ref var edgeB0 = ref _allEdges[Validate_EdgeList[j]];
if ( edgeA0.NextEdge == edgeB0.Index || edgeA0.PrevEdge == edgeB0.Index )
{
continue;
}
ref var edgeB1 = ref _allEdges[edgeB0.NextEdge];
var b0 = edgeA0.Origin;
var b1 = edgeA1.Origin;
var minB = Vector2.Min( b0, b1 );
var maxB = Vector2.Max( b0, b1 );
if ( minA.x >= maxB.x || minA.y >= maxB.y || minB.x >= maxA.x || minB.y >= maxA.y )
{
continue;
}
if ( Helpers.LineSegmentsIntersect( a0, a1, b0, b1 ) )
{
throw InvalidPolygonException();
}
}
}
_validated = true;
}
private static Exception InvalidPolygonException()
{
return new Exception( "Invalid polygon" );
}
}
Game
library
using System;
using System.Collections.Generic;
using System.Linq;
using System.Runtime.CompilerServices;
using System.Runtime.InteropServices;
namespace Sandbox.Polygons;
/// <summary>
/// Helper class for building 3D meshes based on a 2D polygon. Supports
/// concave polygons with holes, although edges must not intersect.
/// </summary>
public partial class PolygonMeshBuilder : Pooled<PolygonMeshBuilder>
{
public record struct Vertex( Vector3 Position, Vector3 Normal, Vector4 Tangent )
{
public static VertexAttribute[] Layout { get; } = new[]
{
new VertexAttribute( VertexAttributeType.Position, VertexAttributeFormat.Float32 ),
new VertexAttribute( VertexAttributeType.Normal, VertexAttributeFormat.Float32 ),
new VertexAttribute( VertexAttributeType.Tangent, VertexAttributeFormat.Float32, 4 )
};
}
private int _nextEdgeIndex;
private Edge[] _allEdges = new Edge[64];
private readonly HashSet<int> _activeEdges = new ();
private readonly List<Vertex> _vertices = new ();
private readonly List<int> _indices = new ();
private float _prevDistance;
private float _nextDistance;
private float _invDistance;
private float _prevHeight;
private float _nextHeight;
private float _prevAngle;
private float _nextAngle;
private float _minSmoothNormalDot;
private bool _validated;
/// <summary>
/// Number of edges that will be affected by calls to methods like <see cref="Bevel"/>, <see cref="Round"/>, and <see cref="Close"/>.
/// </summary>
public int ActiveEdgeCount => _activeEdges.Count;
/// <summary>
/// If true, no active edges remain because the mesh is fully closed.
/// </summary>
public bool IsClosed => _activeEdges.Count == 0;
/// <summary>
/// Corners of the original polygon with an interior or exterior
/// angle less than this (in radians) will have smooth normals.
/// </summary>
public float MaxSmoothAngle { get; set; } = 0f;
/// <summary>
/// If true, don't bother generating normals / tangents.
/// </summary>
public bool SkipNormals { get; set; }
/// <summary>
/// Positions of each vertex in the generated mesh.
/// </summary>
public IEnumerable<Vector3> Positions => _vertices.Select( x => x.Position );
/// <summary>
/// Normals of each vertex in the generated mesh.
/// </summary>
public IEnumerable<Vector3> Normals => _vertices.Select( x => x.Normal );
/// <summary>
/// U-tangents, and the signs of the V-tangents, of each vertex in the generated mesh.
/// </summary>
public IEnumerable<Vector4> Tangents => _vertices.Select( x => x.Tangent );
/// <summary>
/// Positions, normals, and tangents of each vertex.
/// </summary>
public List<Vertex> Vertices => _vertices;
/// <summary>
/// Indices of vertices describing the triangulation of the generated mesh.
/// </summary>
public List<int> Indices => _indices;
/// <summary>
/// Clear all geometry from this builder.
/// </summary>
public PolygonMeshBuilder Clear()
{
_nextEdgeIndex = 0;
_activeEdges.Clear();
_vertices.Clear();
_indices.Clear();
_prevDistance = 0f;
_nextDistance = 0f;
_invDistance = 0f;
_prevHeight = 0f;
_nextHeight = 0f;
_prevAngle = 0f;
_nextAngle = 0f;
_minSmoothNormalDot = 0f;
_validated = true;
return this;
}
/// <summary>
/// Reset this builder to be like a new instance.
/// </summary>
public override void Reset()
{
Clear();
MaxSmoothAngle = 0f;
SkipNormals = false;
}
private static int NextPowerOfTwo( int value )
{
var po2 = 1;
while ( po2 < value )
{
po2 <<= 1;
}
return po2;
}
private void EnsureCapacity( int toAdd )
{
if ( _nextEdgeIndex + toAdd > _allEdges.Length )
{
Array.Resize( ref _allEdges, NextPowerOfTwo( _nextEdgeIndex + toAdd ) );
}
}
private int AddEdge( Vector2 origin, Vector2 tangent, float distance, int? twinOffset = null )
{
var edge = new Edge( _nextEdgeIndex, origin, tangent, distance, twinOffset != null ? _nextEdgeIndex + twinOffset.Value : -1 );
_allEdges[edge.Index] = edge;
++_nextEdgeIndex;
return edge.Index;
}
private void Invalidate()
{
_validated = false;
}
/// <summary>
/// Add a set of active edges forming a loop. Clockwise loops will be a solid polygon, and count-clockwise
/// will form a hole. Holes must be inside of solid polygons, otherwise the mesh can't be closed correctly.
/// </summary>
/// <param name="vertices">List of vertices to read a range from.</param>
/// <param name="offset">Index of the first vertex in the loop.</param>
/// <param name="count">Number of vertices in the loop.</param>
/// <param name="reverse">If true, reverse the order of the vertices in the loop.</param>
public PolygonMeshBuilder AddEdgeLoop( IReadOnlyList<Vector2> vertices, int offset, int count, bool reverse = false )
{
return AddEdgeLoop( vertices, offset, count, Vector2.Zero, Vector2.One, reverse );
}
public PolygonMeshBuilder AddEdgeLoop( IReadOnlyList<Vector2> vertices, int offset, int count, Vector2 position, Vector2 scale, bool reverse = false )
{
var firstIndex = _nextEdgeIndex;
EnsureCapacity( count );
Invalidate();
var prevVertex = position + vertices[offset + count - 1] * scale;
for ( var i = 0; i < count; ++i )
{
var nextVertex = position + vertices[offset + i] * scale;
_activeEdges.Add( AddEdge( prevVertex, Helpers.NormalizeSafe( nextVertex - prevVertex ), _prevDistance ) );
prevVertex = nextVertex;
}
var prevIndex = count - 1;
for ( var i = 0; i < count; ++i )
{
ref var prevEdge = ref _allEdges[firstIndex + prevIndex];
ref var nextEdge = ref _allEdges[firstIndex + i];
if ( reverse )
{
ConnectEdges( ref nextEdge, ref prevEdge );
}
else
{
ConnectEdges( ref prevEdge, ref nextEdge );
}
prevIndex = i;
}
return this;
}
[ThreadStatic]
private static Dictionary<int, int> AddEdges_VertexMap;
/// <summary>
/// Add a raw set of edges. Be careful to ensure that each loop of edges is fully closed.
/// </summary>
/// <param name="vertices">Positions of vertices to connect with edges.</param>
/// <param name="edges">Indices of the start and end vertices of each edge.</param>
public void AddEdges( IReadOnlyList<Vector2> vertices, IReadOnlyList<(int Prev, int Next)> edges )
{
AddEdges_VertexMap ??= new Dictionary<int, int>();
AddEdges_VertexMap.Clear();
EnsureCapacity( edges.Count );
Invalidate();
foreach ( var (i, j) in edges )
{
var prev = vertices[i];
var next = vertices[j];
var index = AddEdge( prev, Helpers.NormalizeSafe( next - prev ), _prevDistance );
_activeEdges.Add( index );
AddEdges_VertexMap.Add( i, index );
}
for ( var i = 0; i < edges.Count; ++i )
{
var edge = edges[i];
ref var prev = ref _allEdges[AddEdges_VertexMap[edge.Prev]];
ref var next = ref _allEdges[AddEdges_VertexMap[edge.Next]];
ConnectEdges( ref prev, ref next );
}
}
private static float LerpRadians( float a, float b, float t )
{
var delta = b - a;
delta -= MathF.Floor( delta * (0.5f / MathF.PI) ) * MathF.PI * 2f;
if ( delta > MathF.PI )
{
delta -= MathF.PI * 2f;
}
return a + delta * Math.Clamp( t, 0f, 1f );
}
private Vector4 GetTangent( Vector3 normal )
{
var tangent = Vector3.Cross( normal, new Vector3( 0f, 0f, 1f ) ).Normal;
return new Vector4( tangent, 1f );
}
private (int Prev, int Next) AddVertices( ref Edge edge, bool forceMaxDistance = false )
{
if ( edge.Vertices.Prev > -1 )
{
return edge.Vertices;
}
var prevEdge = _allEdges[edge.PrevEdge];
var index = _vertices.Count;
var prevNormal = -prevEdge.Normal;
var nextNormal = -edge.Normal;
var t = forceMaxDistance ? 1f : (edge.Distance - _prevDistance) * _invDistance;
var height = _prevHeight + t * (_nextHeight - _prevHeight);
var pos = new Vector3( edge.Origin.x, edge.Origin.y, height );
if ( SkipNormals || MathF.Abs( _nextHeight - _prevHeight ) <= 0.001f )
{
_vertices.Add( new(
pos,
new Vector3( 0f, 0f, 1f ),
new Vector4( 1f, 0f, 0f, 1f ) ) );
edge.Vertices = (index, index);
}
else
{
var angle = LerpRadians( _prevAngle, _nextAngle, t );
var cos = MathF.Cos( angle );
var sin = MathF.Sin( angle );
if ( Vector2.Dot( prevNormal, nextNormal ) >= _minSmoothNormalDot )
{
var normal = new Vector3( (prevNormal.x + nextNormal.x) * cos, (prevNormal.y + nextNormal.y) * cos, sin * 2f ).Normal;
_vertices.Add( new( pos, normal, GetTangent( normal ) ) );
edge.Vertices = (index, index);
}
else
{
var normal0 = new Vector3( prevNormal.x * cos, prevNormal.y * cos, sin ).Normal;
var normal1 = new Vector3( nextNormal.x * cos, nextNormal.y * cos, sin ).Normal;
_vertices.Add( new( pos, normal0, GetTangent( normal0 ) ) );
_vertices.Add( new( pos, normal1, GetTangent( normal1 ) ) );
edge.Vertices = (index, index + 1);
}
}
return edge.Vertices;
}
private void AddTriangle( int a, int b, int c )
{
_indices.Add( a );
_indices.Add( b );
_indices.Add( c );
}
/// <summary>
/// Add faces on each active edge extending upwards by the given height.
/// </summary>
/// <param name="height">Total distance upwards, away from the plane of the polygon.</param>
public PolygonMeshBuilder Extrude( float height )
{
return Bevel( 0f, height );
}
/// <summary>
/// Add faces on each active edge extending inwards by the given width. This will close the mesh if <paramref name="width"/> is large enough.
/// </summary>
/// <param name="width">Total distance inwards.</param>
public PolygonMeshBuilder Inset( float width )
{
return Bevel( width, 0f );
}
[ThreadStatic]
private static Dictionary<int, int> Mirror_IndexMap;
/// <summary>
/// Mirrors all previously created faces. The mirror plane is normal to the Z axis, with a given distance from the origin.
/// </summary>
/// <param name="z">Distance of the mirror plane from the origin.</param>
public PolygonMeshBuilder Mirror( float z = 0f )
{
Mirror_IndexMap ??= new Dictionary<int, int>();
Mirror_IndexMap.Clear();
_vertices.EnsureCapacity( _vertices.Count * 2 );
_indices.EnsureCapacity( _indices.Count * 2 );
var indexCount = _indices.Count;
var vertexCount = _vertices.Count;
for ( var i = 0; i < vertexCount; i++ )
{
var vertex = _vertices[i];
var position = vertex.Position;
var normal = vertex.Normal;
var tangent = vertex.Tangent;
if ( Math.Abs( position.z - z ) <= 0.001f && (SkipNormals || Math.Abs( normal.z ) <= 0.0001f && Math.Abs( tangent.z ) <= 0.0001f) )
{
Mirror_IndexMap.Add( i, i );
}
else
{
Mirror_IndexMap.Add( i, _vertices.Count );
_vertices.Add( new(
new Vector3( position.x, position.y, z * 2f - position.z ),
new Vector3( normal.x, normal.y, -normal.z ),
new Vector4( tangent.x, tangent.y, -tangent.z, tangent.w ) ) );
}
}
for ( var i = 0; i < indexCount; i += 3 )
{
var a = Mirror_IndexMap[_indices[i + 0]];
var b = Mirror_IndexMap[_indices[i + 1]];
var c = Mirror_IndexMap[_indices[i + 2]];
_indices.Add( a );
_indices.Add( c );
_indices.Add( b );
}
return this;
}
/// <summary>
/// Perform successive <see cref="Bevel"/>s so that the edge of the polygon curves inwards in a quarter circle arc.
/// </summary>
/// <param name="radius">Radius of the arc.</param>
/// <param name="faces">How many bevels to split the rounded edge into.</param>
/// <param name="smooth">If true, use smooth normals rather than flat shading.</param>
/// <param name="convex">If true, the faces will be pointing outwards from the center of the arc.</param>
public PolygonMeshBuilder Arc( float radius, int faces, bool smooth = true, bool convex = true )
{
return Arc( radius, radius, faces, smooth, convex );
}
/// <summary>
/// Perform successive <see cref="Bevel"/>s so that the edge of the polygon curves inwards in a quarter circle arc.
/// </summary>
/// <param name="width">Total distance inwards.</param>
/// <param name="height">Total distance upwards, away from the plane of the polygon.</param>
/// <param name="faces">How many bevels to split the rounded edge into.</param>
/// <param name="smooth">If true, use smooth normals rather than flat shading.</param>
/// <param name="convex">If true, the faces will be pointing outwards from the center of the arc.</param>
public PolygonMeshBuilder Arc( float width, float height, int faces, bool smooth = true, bool convex = true )
{
var prevWidth = 0f;
var prevHeight = 0f;
var prevTheta = 0f;
static float MapAngle( float theta, bool convex, bool positive )
{
var min = positive ? 0f : MathF.PI * 0.5f;
return convex ? min + theta : min + MathF.PI * 0.5f - theta;
}
for ( var i = 0; i < faces; ++i )
{
var theta = MathF.PI * 0.5f * (i + 1f) / faces;
var cos = MathF.Cos( theta );
var sin = MathF.Sin( theta );
var nextWidth = 1f - cos;
var nextHeight = sin;
if ( smooth )
{
if ( height >= 0f == convex )
{
Bevel( (nextWidth - prevWidth) * width,
(nextHeight - prevHeight) * height,
MapAngle( prevTheta, convex, height >= 0f ),
MapAngle( theta, convex, height >= 0f ) );
}
else
{
Bevel( (nextHeight - prevHeight) * width,
(nextWidth - prevWidth) * height,
MapAngle( prevTheta, convex, height >= 0f ),
MapAngle( theta, convex, height >= 0f ) );
}
}
else
{
if ( height >= 0f == convex )
{
Bevel( (nextWidth - prevWidth) * width,
(nextHeight - prevHeight) * height );
}
else
{
Bevel( (nextHeight - prevHeight) * width,
(nextWidth - prevWidth) * height );
}
}
prevWidth = nextWidth;
prevHeight = nextHeight;
prevTheta = theta;
}
return this;
}
}
Game
library
using System;
using System.Collections.Generic;
using System.Linq;
namespace Sandbox.Polygons;
partial class PolygonMeshBuilder
{
private HashSet<(int A, int B)> PossibleCuts { get; } = new();
[ThreadStatic] private static List<(int A, int B)> Bevel_PossibleCutList;
[ThreadStatic] private static List<int> Bevel_ActiveEdgeList;
/// <summary>
/// Add faces starting at each active edge, traveling inwards and upwards to produce a bevel.
/// If the bevel distance is large enough the mesh will become closed. Otherwise, you can use
/// <see cref="Close"/> to add a flat face after the bevel.
/// </summary>
/// <param name="width">Total distance inwards.</param>
/// <param name="height">Total distance upwards, away from the plane of the polygon.</param>
public PolygonMeshBuilder Bevel( float width, float height )
{
var angle = MathF.Atan2( width, height );
return Bevel( width, height, angle, angle );
}
/// <summary>
/// Add faces starting at each active edge, traveling inwards and upwards to produce a bevel.
/// Use <paramref name="prevAngle"/> and <paramref name="nextAngle"/> to control the normal directions
/// at the start and end of the bevel faces. Angles are in radians, with 0 pointing outwards along
/// the plane of the polygon, and PI/2 pointing upwards away from the plane.
/// If the bevel distance is large enough the mesh will become closed. Otherwise, you can use
/// <see cref="Close"/> to add a flat face after the bevel.
/// </summary>
/// <param name="width">Total distance inwards.</param>
/// <param name="height">Total distance upwards, away from the plane of the polygon.</param>
/// <param name="prevAngle">Angle, in radians, to use for normals at the outside of the bevel.</param>
/// <param name="nextAngle"></param>
public PolygonMeshBuilder Bevel( float width, float height, float prevAngle, float nextAngle )
{
if ( width < 0f )
{
throw new ArgumentOutOfRangeException( nameof( width ) );
}
Validate();
Bevel_UpdateExistingVertices( width, height, prevAngle, nextAngle );
var cutList = Bevel_PossibleCutList ??= new List<(int A, int B)>();
var edgeList = Bevel_ActiveEdgeList ??= new List<int>();
var finished = false;
var endDist = _nextDistance;
if ( MathF.Abs( _nextDistance ) > 0.001f )
{
var maxIterations = _activeEdges.Count * _activeEdges.Count;
int iterations;
for ( iterations = 0; iterations < maxIterations && _activeEdges.Count > 0; ++iterations )
{
int? closedEdge = null;
int? splitEdge = null;
int? splittingEdge = null;
Vector2 bestPos = default;
var bestDist = _nextDistance;
var bestMerge = false;
foreach ( var index in _activeEdges )
{
ref var edge = ref _allEdges[index];
if ( edge.MaxDistance >= bestDist ) continue;
var next = _allEdges[edge.NextEdge];
bestDist = edge.MaxDistance;
closedEdge = edge.Index;
bestPos = (edge.Project( edge.MaxDistance ) + next.Project( edge.MaxDistance )) * 0.5f;
}
cutList.Clear();
cutList.AddRange( PossibleCuts );
foreach ( var (index, otherIndex) in cutList )
{
if ( !_activeEdges.Contains( index ) || !_activeEdges.Contains( otherIndex ) )
{
PossibleCuts.Remove( (index, otherIndex) );
continue;
}
var edge = _allEdges[index];
var other = _allEdges[otherIndex];
var splitDist = CalculateSplitDistance( edge, other, _allEdges[other.NextEdge],
out var splitPos, out var merge );
if ( splitDist - _nextDistance > 0.001f )
{
PossibleCuts.Remove( (index, otherIndex) );
continue;
}
if ( splitDist >= bestDist ) continue;
bestDist = splitDist;
bestPos = splitPos;
bestMerge = merge;
closedEdge = null;
splitEdge = other.Index;
splittingEdge = edge.Index;
}
if ( splittingEdge != null && bestMerge )
{
Bevel_Merge( splittingEdge.Value, splitEdge.Value, bestPos, bestDist );
continue;
}
if ( splittingEdge != null )
{
Bevel_Split( splittingEdge.Value, splitEdge.Value, bestPos, bestDist );
continue;
}
if ( closedEdge != null )
{
Bevel_Close( closedEdge.Value, bestPos, bestDist );
continue;
}
finished = true;
break;
}
if ( _activeEdges.Count > 0 && iterations == maxIterations )
{
throw new Exception( $"Exploded after {iterations} with {_activeEdges.Count} active edges!" );
}
}
else
{
finished = true;
}
if ( !finished && _activeEdges.Count > 0 )
{
endDist = _activeEdges.Max( i => _allEdges[i].Distance );
}
EnsureCapacity( _activeEdges.Count );
edgeList.Clear();
edgeList.AddRange( _activeEdges );
_activeEdges.Clear();
foreach ( var index in edgeList )
{
ref var b = ref _allEdges[index];
ref var a = ref _allEdges[b.PrevEdge];
ref var c = ref _allEdges[b.NextEdge];
ref var d = ref _allEdges[AddEdge( b.Project( endDist ), b.Tangent, endDist )];
var ai = AddVertices( ref a );
var bi = AddVertices( ref b );
var ci = AddVertices( ref c );
ConnectEdges( ref a, ref d );
ConnectEdges( ref d, ref c );
var di = AddVertices( ref d, true );
AddTriangle( ai.Next, di.Prev, bi.Prev );
AddTriangle( bi.Next, di.Next, ci.Prev );
_activeEdges.Add( d.Index );
}
PostBevel();
return this;
}
private void Bevel_UpdateExistingVertices( float width, float height, float prevAngle, float nextAngle )
{
_nextDistance = _prevDistance + width;
_nextHeight = _prevHeight + height;
_nextAngle = nextAngle;
_minSmoothNormalDot = MathF.Cos( Math.Clamp( MaxSmoothAngle, 0f, MathF.PI * (511f / 512f) ) );
_invDistance = width <= 0.0001f ? 0f : 1f / (_nextDistance - _prevDistance);
if ( !SkipNormals && Math.Abs( _prevAngle - prevAngle ) >= 0.001f )
{
foreach ( var index in _activeEdges )
{
ref var edge = ref _allEdges[index];
edge.Vertices = (-1, -1);
}
}
_prevAngle = prevAngle;
PossibleCuts.Clear();
foreach ( var index in _activeEdges )
{
ref var edge = ref _allEdges[index];
UpdateMaxDistance( ref edge, _allEdges[edge.NextEdge] );
foreach ( var otherIndex in _activeEdges )
{
if ( otherIndex != index )
{
PossibleCuts.Add( (index, otherIndex) );
}
}
}
}
private void Bevel_Merge( int edgeA, int edgeB, Vector2 mergePos, float bestDist )
{
EnsureCapacity( 2 );
ref var a = ref _allEdges[edgeA];
ref var b = ref _allEdges[edgeB];
_activeEdges.Remove( a.Index );
_activeEdges.Remove( b.Index );
if ( a.NextEdge == b.Index && b.NextEdge == a.Index )
{
return;
}
ref var aPrev = ref _allEdges[a.PrevEdge];
ref var bPrev = ref _allEdges[b.PrevEdge];
ref var aNext = ref _allEdges[a.NextEdge];
ref var bNext = ref _allEdges[b.NextEdge];
ref var aNew = ref _allEdges[AddEdge( mergePos, a.Tangent, bestDist, 1 )];
ref var bNew = ref _allEdges[AddEdge( mergePos, b.Tangent, bestDist, -1 )];
var aPrevi = AddVertices( ref aPrev ).Next;
var ai = AddVertices( ref a );
var aNexti = AddVertices( ref aNext ).Prev;
var bPrevi = AddVertices( ref bPrev ).Next;
var bi = AddVertices( ref b );
var bNexti = AddVertices( ref bNext ).Prev;
_activeEdges.Add( aNew.Index );
_activeEdges.Add( bNew.Index );
ConnectEdges( ref bPrev, ref aNew );
ConnectEdges( ref aNew, ref aNext );
ConnectEdges( ref aPrev, ref bNew );
ConnectEdges( ref bNew, ref bNext );
UpdateMaxDistance( ref bPrev, aNew );
UpdateMaxDistance( ref aNew, aNext );
UpdateMaxDistance( ref aNext, _allEdges[aNext.NextEdge] );
UpdateMaxDistance( ref aPrev, bNew );
UpdateMaxDistance( ref bNew, bNext );
UpdateMaxDistance( ref bNext, _allEdges[bNext.NextEdge] );
var aNewi = AddVertices( ref aNew );
var bNewi = AddVertices( ref bNew );
AddTriangle( aPrevi, bNewi.Prev, ai.Prev );
AddTriangle( ai.Next, aNewi.Next, aNexti );
AddTriangle( bPrevi, aNewi.Prev, bi.Prev );
AddTriangle( bi.Next, bNewi.Next, bNexti );
AddAllPossibleCuts( aNew.Index );
AddAllPossibleCuts( aNext.Index );
AddAllPossibleCuts( bNew.Index );
AddAllPossibleCuts( bNext.Index );
}
private void Bevel_Split( int splittingEdge, int splitEdge, Vector2 splitPos, float bestDist )
{
EnsureCapacity( 2 );
ref var a = ref _allEdges[splitEdge];
ref var d = ref _allEdges[splittingEdge];
ref var b = ref _allEdges[AddEdge( splitPos, a.Tangent, bestDist, 1 )];
ref var c = ref _allEdges[d.PrevEdge];
ref var e = ref _allEdges[AddEdge( splitPos, d.Tangent, bestDist, -1 )];
ref var aNext = ref _allEdges[a.NextEdge];
ref var dNext = ref _allEdges[d.NextEdge];
var ai = AddVertices( ref a ).Next;
var fi = AddVertices( ref aNext ).Prev;
var ci = AddVertices( ref c ).Next;
var di = AddVertices( ref d );
var gi = AddVertices( ref dNext ).Prev;
_activeEdges.Remove( d.Index );
_activeEdges.Add( b.Index );
_activeEdges.Add( e.Index );
ConnectEdges( ref a, ref e );
ConnectEdges( ref e, ref dNext );
ConnectEdges( ref c, ref b );
ConnectEdges( ref b, ref aNext );
UpdateMaxDistance( ref a, e );
UpdateMaxDistance( ref e, dNext );
UpdateMaxDistance( ref dNext, _allEdges[dNext.NextEdge] );
UpdateMaxDistance( ref c, b );
UpdateMaxDistance( ref b, aNext );
UpdateMaxDistance( ref aNext, _allEdges[aNext.NextEdge] );
var bi = AddVertices( ref b );
var ei = AddVertices( ref e );
AddTriangle( ai, bi.Next, fi );
AddTriangle( ci, bi.Prev, di.Prev );
AddTriangle( di.Next, ei.Next, gi );
AddAllPossibleCuts( b.Index );
AddAllPossibleCuts( dNext.Index );
AddAllPossibleCuts( e.Index );
AddAllPossibleCuts( aNext.Index );
}
private void Bevel_Close( int closedEdge, Vector2 closePos, float bestDist )
{
EnsureCapacity( 1 );
ref var b = ref _allEdges[closedEdge];
ref var a = ref _allEdges[b.PrevEdge];
ref var c = ref _allEdges[b.NextEdge];
ref var cNext = ref _allEdges[c.NextEdge];
ref var d = ref _allEdges[AddEdge( closePos, c.Tangent, bestDist )];
_activeEdges.Remove( b.Index );
_activeEdges.Remove( c.Index );
if ( b.PrevEdge == b.NextEdge )
{
return;
}
_activeEdges.Add( d.Index );
ConnectEdges( ref a, ref d );
ConnectEdges( ref d, ref cNext );
UpdateMaxDistance( ref a, d );
UpdateMaxDistance( ref d, cNext );
UpdateMaxDistance( ref cNext, _allEdges[cNext.NextEdge] );
var ai = AddVertices( ref a );
var bi = AddVertices( ref b );
var ci = AddVertices( ref c );
var ei = AddVertices( ref cNext );
var di = AddVertices( ref d );
var fi = _vertices.Count;
_vertices.Add( new(
_vertices[di.Prev].Position,
_vertices[bi.Next].Normal,
_vertices[bi.Next].Tangent ) );
AddTriangle( ai.Next, di.Prev, bi.Prev );
AddTriangle( bi.Next, fi, ci.Prev );
AddTriangle( ci.Next, di.Next, ei.Prev );
AddAllPossibleCuts( d.Index );
AddAllPossibleCuts( cNext.Index );
}
private void PostBevel()
{
_prevDistance = _nextDistance;
_prevHeight = _nextHeight;
_prevAngle = _nextAngle;
}
private void AddAllPossibleCuts( int index )
{
foreach ( var otherIndex in _activeEdges )
{
if ( otherIndex != index )
{
PossibleCuts.Add( (index, otherIndex) );
PossibleCuts.Add( (otherIndex, index) );
}
}
}
private static Vector3 RotateNormal( Vector3 oldNormal, float sin, float cos )
{
var normal2d = new Vector2( oldNormal.x, oldNormal.y );
if ( normal2d.LengthSquared <= 0.000001f )
{
return oldNormal;
}
normal2d = normal2d.Normal;
return new Vector3( normal2d.x * cos, normal2d.y * cos, sin ).Normal;
}
private static float GetEpsilon( Vector2 vec, float frac = 0.0001f )
{
return Math.Max( Math.Abs( vec.x ), Math.Abs( vec.y ) ) * frac;
}
private static float GetEpsilon( Vector2 a, Vector2 b, float frac = 0.0001f )
{
return Math.Max( GetEpsilon( a ), GetEpsilon( b ) );
}
private static void UpdateMaxDistance( ref Edge edge, in Edge nextEdge )
{
if ( edge.NextEdge == edge.PrevEdge )
{
edge.MaxDistance = edge.Distance;
return;
}
var baseDistance = Math.Max( edge.Distance, nextEdge.Distance );
var thisOrigin = edge.Project( baseDistance );
var nextOrigin = nextEdge.Project( baseDistance );
var posDist = Vector2.Dot( nextOrigin - thisOrigin, edge.Tangent );
var dPrev = Vector2.Dot( edge.Velocity, edge.Tangent );
var dNext = Vector2.Dot( nextEdge.Velocity, edge.Tangent );
if ( dPrev - dNext <= 0.001f )
{
var epsilon = GetEpsilon( thisOrigin, nextOrigin, 0.001f );
edge.MaxDistance = posDist <= epsilon ? baseDistance : float.PositiveInfinity;
}
else
{
edge.MaxDistance = baseDistance + MathF.Max( 0f, posDist / (dPrev - dNext) );
}
}
private static void SimpleConnectEdges( ref Edge prev, ref Edge next )
{
prev.NextEdge = next.Index;
next.PrevEdge = prev.Index;
}
private static void ConnectEdges( ref Edge prev, ref Edge next )
{
SimpleConnectEdges( ref prev, ref next );
var sum = prev.Normal + next.Normal;
var sqrMag = sum.LengthSquared;
if ( sqrMag < 0.001f )
{
next.Velocity = Vector2.Zero;
}
else
{
next.Velocity = 2f * sum / sum.LengthSquared;
}
}
private static float CalculateSplitDistance( in Edge edge, in Edge other, in Edge otherNext,
out Vector2 splitPos, out bool merge )
{
splitPos = default;
merge = false;
if ( other.Index == edge.Index || edge.Twin == other.Index || edge.Velocity.LengthSquared <= 0f )
{
return float.PositiveInfinity;
}
var dv = Vector2.Dot( other.Velocity - edge.Velocity, other.Normal );
if ( dv <= GetEpsilon( edge.Velocity, other.Velocity ) )
{
return float.PositiveInfinity;
}
var baseDistance = Math.Max( edge.Distance, Math.Max( other.Distance, otherNext.Distance ) );
var thisOrigin = edge.Project( baseDistance );
var edgeOrigin = other.Project( baseDistance );
var dx = Vector2.Dot( thisOrigin - edgeOrigin, other.Normal );
if ( dx <= -GetEpsilon( thisOrigin, edgeOrigin ) )
{
return float.PositiveInfinity;
}
var t = dx / dv;
if ( t <= -0.0001f )
{
return float.PositiveInfinity;
}
if ( baseDistance + t >= edge.MaxDistance || baseDistance + t >= other.MaxDistance )
{
return float.PositiveInfinity;
}
splitPos = thisOrigin + edge.Velocity * t;
var prevPos = edgeOrigin + other.Velocity * t;
var nextPos = otherNext.Project( baseDistance + t );
var dPrev = Vector2.Dot( splitPos - prevPos, other.Tangent );
var dNext = Vector2.Dot( splitPos - nextPos, other.Tangent );
var epsilon = GetEpsilon( prevPos, nextPos );
if ( dPrev <= -epsilon || dNext >= -epsilon )
{
return float.PositiveInfinity;
}
if ( dPrev <= epsilon )
{
if ( edge.NextEdge == other.Index || edge.PrevEdge == other.Index )
{
return float.PositiveInfinity;
}
merge = true;
}
return baseDistance + Math.Max( 0f, t );
}
}
Game
library
using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using Sandbox.Utility.Svg;
namespace Sandbox.Polygons;
/// <summary>
/// Options for <see cref="PolygonMeshBuilder.AddSvg"/>.
/// </summary>
public class AddSvgOptions
{
public static AddSvgOptions Default { get; } = new();
/// <summary>
/// If true, any unsupported path types will throw an exception. Defaults to false.
/// </summary>
public bool ThrowIfNotSupported { get; set; }
/// <summary>
/// Maximum distance between vertices on curved paths. Defaults to 1.
/// </summary>
public float CurveResolution { get; set; } = 1f;
public bool KeepAspectRatio { get; set; } = true;
}
partial class PolygonMeshBuilder
{
/// <summary>
/// Add all supported paths from the given SVG document.
/// </summary>
/// <param name="contents">SVG document contents.</param>
/// <param name="options">Options for generating vertices from paths.</param>
/// <param name="targetBounds">Rescale and translate the imported SVG to fill the given bounds</param>
public PolygonMeshBuilder AddSvg( string contents, AddSvgOptions options = null, Rect? targetBounds = null )
{
options ??= AddSvgOptions.Default;
var svg = SvgDocument.FromString( contents );
if ( svg.Paths.Count == 0 )
{
return this;
}
if ( targetBounds == null )
{
foreach ( var path in svg.Paths )
{
AddPath( path, options );
}
return this;
}
var bounds = svg.Paths[0].Bounds;
foreach ( var path in svg.Paths )
{
bounds.Add( path.Bounds );
}
var scale = targetBounds.Value.Size / bounds.Size;
var aspectOffset = Vector2.Zero;
if ( options.KeepAspectRatio )
{
var oldScale = scale;
scale = Math.Min( scale.x, scale.y );
aspectOffset = (oldScale - scale) * targetBounds.Value.Size * 0.25f;
}
var offset = targetBounds.Value.Position - bounds.Position * scale + aspectOffset;
foreach ( var path in svg.Paths )
{
AddPath( path, options, offset, scale );
}
return this;
}
private static void ThrowNotSupported( AddSvgOptions options, string message )
{
if ( !options.ThrowIfNotSupported )
{
return;
}
throw new NotImplementedException( $"SVG path element not supported: {message}" );
}
/// <summary>
/// Add an individual path from an SVG document, if supported.
/// </summary>
/// <param name="path">SVG path element.</param>
/// <param name="options">Options for generating vertices from paths.</param>
/// <param name="targetBounds">Rescale and translate the imported SVG to fill the given bounds</param>
public PolygonMeshBuilder AddPath( SvgPath path, AddSvgOptions options = null )
{
options ??= AddSvgOptions.Default;
return AddPath( path, options, Vector2.Zero, Vector2.One );
}
private PolygonMeshBuilder AddPath( SvgPath path, AddSvgOptions options, Vector2 offset, Vector2 scale )
{
if ( path.IsEmpty )
{
return this;
}
if ( path.FillColor == null )
{
return this;
}
if ( path.FillType != PathFillType.Winding )
{
if ( options.ThrowIfNotSupported )
{
//throw new NotImplementedException( "Only fill-type: winding is supported." );
}
//return this;
}
var openPath = new List<Vector2>();
var last = Vector2.Zero;
foreach ( var cmd in path.Commands )
{
switch ( cmd )
{
case AddPolyPathCommand addPolyPathCommand:
AddPolyPath( addPolyPathCommand, options, offset, scale );
break;
case AddCirclePathCommand addCirclePathCommand:
AddCirclePath( addCirclePathCommand, options, openPath, offset, scale );
break;
case MoveToPathCommand moveToPathCommand:
openPath.Clear();
openPath.Add( new Vector2( moveToPathCommand.X, moveToPathCommand.Y ) );
break;
case LineToPathCommand lineToPathCommand:
openPath.Add( new Vector2( lineToPathCommand.X, lineToPathCommand.Y ) );
break;
case CubicToPathCommand cubicToPathCommand:
CubicToPath( cubicToPathCommand, options, openPath, last );
break;
case ClosePathCommand:
if ( openPath.Count >= 3 )
{
AddEdgeLoop( openPath, 0, openPath.Count, offset, scale );
}
openPath.Clear();
break;
default:
ThrowNotSupported( options, $"{cmd.GetType()}" );
break;
}
if ( openPath.Count > 0 )
{
last = openPath[^1];
}
}
return this;
}
private void AddPolyPath( AddPolyPathCommand cmd, AddSvgOptions options, Vector2 offset, Vector2 scale )
{
if ( !cmd.Close )
{
return;
}
AddEdgeLoop( cmd.Points, 0, cmd.Points.Count, offset, scale );
}
private void AddCirclePath( AddCirclePathCommand cmd, AddSvgOptions options, List<Vector2> openPath, Vector2 offset, Vector2 scale )
{
openPath.Clear();
var center = new Vector2( cmd.X, cmd.Y );
for ( var i = 23; i >= 0; i-- )
{
var r = i * (MathF.PI * 2f / 24f);
var cos = MathF.Cos( r );
var sin = MathF.Sin( r );
openPath.Add( new Vector2( cos, sin ) * cmd.Radius + center );
}
AddEdgeLoop( openPath, 0, openPath.Count, offset, scale );
}
private void CubicToPath( CubicToPathCommand cmd, AddSvgOptions options, List<Vector2> openPath, Vector2 last )
{
var pointCount = 6;
var tScale = 1f / pointCount;
for ( var i = 0; i < pointCount; i++ )
{
var t = (i + 1) * tScale;
var s = 1f - t;
var a = s * s * s;
var b = 3f * s * s * t;
var c = 3f * s * t * t;
var d = t * t * t;
var p0 = last;
var p1 = new Vector2( cmd.X0, cmd.Y0 );
var p2 = new Vector2( cmd.X1, cmd.Y1 );
var p3 = new Vector2( cmd.X2, cmd.Y2 );
openPath.Add( p0 * a + p1 * b + p2 * c + p3 * d );
}
}
public string ToSvg()
{
var openEdges = new HashSet<int>( _activeEdges );
var writer = new StringWriter();
writer.WriteLine( "<svg xmlns=\"http://www.w3.org/2000/svg\">" );
while ( openEdges.Count > 0 )
{
var firstIndex = openEdges.First();
var edge = _allEdges[firstIndex];
writer.Write( " <polygon points=\"" );
while ( true )
{
writer.Write( $"{edge.Origin.x:R},{edge.Origin.y:R} " );
openEdges.Remove( edge.Index );
if ( edge.NextEdge == firstIndex )
{
break;
}
edge = _allEdges[edge.NextEdge];
}
writer.WriteLine("\" fill=\"black\" stroke=\"red\" />");
}
writer.WriteLine( @"</svg>" );
return writer.ToString();
}
}
Game
library
using System;
using System.Collections.Generic;
namespace Sandbox.Polygons;
public abstract class Pooled<T> : IDisposable
where T : Pooled<T>, new()
{
#pragma warning disable SB3000
private const int MaxPoolCount = 64;
private static List<T> Pool { get; } = new();
#pragma warning restore SB3000
public static T Rent()
{
lock ( Pool )
{
if ( Pool.Count <= 0 ) return new T();
var writer = Pool[^1];
Pool.RemoveAt( Pool.Count - 1 );
writer._isInPool = false;
writer.Reset();
return writer;
}
}
public void Return()
{
lock ( Pool )
{
if ( _isInPool ) throw new InvalidOperationException( "Already returned." );
Reset();
_isInPool = true;
if ( Pool.Count < MaxPoolCount ) Pool.Add( (T) this );
}
}
private bool _isInPool;
public abstract void Reset();
public void Dispose()
{
Return();
}
}
Debug: View Raw JSON Response
{
"TotalCount": 9,
"Files": [
{
"Ident": "facepunch.libpolygon",
"Path": "Code/PolygonModelRenderer.cs",
"FileName": "PolygonModelRenderer.cs",
"PackageType": "library",
"CodeKind": "Game",
"AssetVersionId": 55832,
"IsPrivate": false,
"Code": "\r\nusing System;\r\nusing System.Collections.Generic;\r\n\r\nnamespace Sandbox.Polygons;\r\n\r\npublic class PolygonModelRenderer : ModelRenderer\r\n{\r\n\tprivate Mesh _mesh;\r\n\r\n\tprivate string _svg;\r\n\tprivate bool _meshDirty;\r\n\r\n\t/// <summary>\r\n\t/// Scalable Vector Graphics source string for this model.\r\n\t/// </summary>\r\n\t[Property]\r\n\tpublic string Svg\r\n\t{\r\n\t\tget => _svg;\r\n\t\tset\r\n\t\t{\r\n\t\t\t_svg = value;\r\n\t\t\t_meshDirty = true;\r\n\t\t}\r\n\t}\r\n\r\n\tprivate int _lastHash = 0;\r\n\r\n\tprotected override void OnEnabled()\r\n\t{\r\n\t\tbase.OnEnabled();\r\n\r\n\t\tUpdateModel();\r\n\t}\r\n\r\n\tprotected override void OnValidate()\r\n\t{\r\n\t\tbase.OnValidate();\r\n\r\n\t\t_meshDirty = true;\r\n\t}\r\n\r\n\tprivate void UpdateModel()\r\n\t{\r\n\t\tif ( !_meshDirty )\r\n\t\t{\r\n\t\t\treturn;\r\n\t\t}\r\n\r\n\t\tvar hash = Svg?.FastHash() ?? 0;\r\n\t\tif ( _lastHash == hash )\r\n\t\t{\r\n\t\t\treturn;\r\n\t\t}\r\n\r\n\t\tif ( Model?.IsProcedural is not true )\r\n\t\t{\r\n\t\t\tModel = null;\r\n\t\t}\r\n\r\n\t\t_lastHash = hash;\r\n\r\n\t\tif ( !string.IsNullOrEmpty( Svg ) )\r\n\t\t{\r\n\t\t\tusing var builder = PolygonMeshBuilder.Rent();\r\n\r\n\t\t\tbuilder.MaxSmoothAngle = 33f.DegreeToRadian();\r\n\r\n\t\t\tbuilder.AddSvg( _svg, new AddSvgOptions\r\n\t\t\t{\r\n\t\t\t\tThrowIfNotSupported = true\r\n\t\t\t}, new Rect( -128f, -128f, 256f, 256f ) );\r\n\t\t\tbuilder.Extrude( 8f );\r\n\t\t\tbuilder.Arc( 2f, 2 );\r\n\t\t\tbuilder.Fill();\r\n\t\t\tbuilder.Mirror();\r\n\r\n\t\t\t_mesh ??= new Mesh( Material.Load( \"materials/default/white.vmat\" ) );\r\n\t\t\t_mesh.UpdateMesh( PolygonMeshBuilder.Vertex.Layout, builder.Vertices, builder.Indices );\r\n\t\t\t\r\n\t\t\tModel ??= new ModelBuilder()\r\n\t\t\t\t.AddMesh( _mesh )\r\n\t\t\t\t.Create();\r\n\t\t}\r\n\t\telse\r\n\t\t{\r\n\t\t\t_mesh?.SetIndexRange( 0, 0 );\r\n\t\t}\r\n\t}\r\n\r\n\tprotected override void OnUpdate()\r\n\t{\r\n\t\tUpdateModel();\r\n\r\n\t\tbase.OnUpdate();\r\n\t}\r\n}\r\n"
},
{
"Ident": "facepunch.libpolygon",
"Path": "Code/PolygonMeshBuilder.Edge.cs",
"FileName": "PolygonMeshBuilder.Edge.cs",
"PackageType": "library",
"CodeKind": "Game",
"AssetVersionId": 55832,
"IsPrivate": false,
"Code": "\r\nnamespace Sandbox.Polygons;\r\n\r\npartial class PolygonMeshBuilder\r\n{\r\n\tprivate struct Edge\r\n\t{\r\n\t\tpublic int Index { get; }\r\n\r\n\t\tpublic Vector2 Origin { get; }\r\n\t\tpublic Vector2 Tangent { get; }\r\n\t\tpublic Vector2 Normal { get; }\r\n\r\n\t\tpublic Vector2 Velocity { get; set; }\r\n\r\n\t\tpublic int PrevEdge { get; set; }\r\n\t\tpublic int NextEdge { get; set; }\r\n\r\n\t\tpublic float Distance { get; set; }\r\n\t\tpublic float MaxDistance { get; set; }\r\n\r\n\t\tpublic (int Prev, int Next) Vertices { get; set; }\r\n\r\n\t\tpublic int Twin { get; }\r\n\r\n\t\tpublic Edge( int index, Vector2 origin, Vector2 tangent, float distance, int twin = -1 )\r\n\t\t{\r\n\t\t\tIndex = index;\r\n\r\n\t\t\tOrigin = origin;\r\n\t\t\tTangent = tangent;\r\n\t\t\tNormal = Helpers.Rotate90( tangent );\r\n\r\n\t\t\tVelocity = Vector2.Zero;\r\n\r\n\t\t\tPrevEdge = -1;\r\n\t\t\tNextEdge = -1;\r\n\r\n\t\t\tVertices = (-1, -1);\r\n\r\n\t\t\tDistance = distance;\r\n\t\t\tMaxDistance = float.PositiveInfinity;\r\n\r\n\t\t\tTwin = twin;\r\n\t\t}\r\n\r\n\t\tpublic readonly Vector2 Project( float distance )\r\n\t\t{\r\n\t\t\treturn Origin + Velocity * (distance - Distance);\r\n\t\t}\r\n\r\n\t\tpublic override string ToString()\r\n\t\t{\r\n\t\t\treturn $\"{(char) ('A' + Index)}\";\r\n\t\t}\r\n\r\n\t\tpublic bool Equals( Edge other )\r\n\t\t{\r\n\t\t\treturn Index == other.Index;\r\n\t\t}\r\n\r\n\t\tpublic override bool Equals( object obj )\r\n\t\t{\r\n\t\t\treturn obj is Edge other && Equals( other );\r\n\t\t}\r\n\r\n\t\tpublic override int GetHashCode()\r\n\t\t{\r\n\t\t\treturn Index;\r\n\t\t}\r\n\t}\r\n}"
},
{
"Ident": "facepunch.libpolygon",
"Path": "Code/Helpers.cs",
"FileName": "Helpers.cs",
"PackageType": "library",
"CodeKind": "Game",
"AssetVersionId": 55832,
"IsPrivate": false,
"Code": "using System;\r\nusing System.Collections.Generic;\r\n\r\nnamespace Sandbox.Polygons;\r\n\r\ninternal static class Helpers\r\n{\r\n\tpublic static Vector2 NormalizeSafe( in Vector2 vec )\r\n\t{\r\n\t\tvar length = vec.Length;\r\n\r\n\t\tif ( length > 9.9999997473787516E-06 )\r\n\t\t{\r\n\t\t\treturn vec / length;\r\n\t\t}\r\n\t\telse\r\n\t\t{\r\n\t\t\treturn 0f;\r\n\t\t}\r\n\t}\r\n\r\n\tpublic static Vector2 Rotate90( Vector2 v )\r\n\t{\r\n\t\treturn new Vector2( v.y, -v.x );\r\n\t}\r\n\r\n\tpublic static float Cross( Vector2 a, Vector2 b )\r\n\t{\r\n\t\treturn a.x * b.y - a.y * b.x;\r\n\t}\r\n\r\n\tpublic static bool LineSegmentsIntersect( Vector2 a0, Vector2 a1, Vector2 b0, Vector2 b1 )\r\n\t{\r\n\t\treturn Math.Sign( Cross( a0 - b0, b1 - b0 ) ) != Math.Sign( Cross( a1 - b0, b1 - b0 ) )\r\n\t\t\t&& Math.Sign( Cross( b0 - a0, a1 - a0 ) ) != Math.Sign( Cross( b1 - a0, a1 - a0 ) );\r\n\t}\r\n\r\n\tpublic static Vector3 RotateNormal( Vector3 oldNormal, float sin, float cos )\r\n\t{\r\n\t\tvar normal2d = new Vector2( oldNormal.x, oldNormal.y );\r\n\r\n\t\tif ( normal2d.LengthSquared <= 0.000001f )\r\n\t\t{\r\n\t\t\treturn oldNormal;\r\n\t\t}\r\n\r\n\t\tnormal2d = NormalizeSafe( normal2d );\r\n\r\n\t\treturn new Vector3( normal2d.x * cos, normal2d.y * cos, sin ).Normal;\r\n\t}\r\n\r\n\tpublic static float GetEpsilon( Vector2 vec, float frac = 0.0001f )\r\n\t{\r\n\t\treturn Math.Max( Math.Abs( vec.x ), Math.Abs( vec.y ) ) * frac;\r\n\t}\r\n\r\n\tpublic static float GetEpsilon( Vector2 a, Vector2 b, float frac = 0.0001f )\r\n\t{\r\n\t\treturn Math.Max( GetEpsilon( a, frac ), GetEpsilon( b, frac ) );\r\n\t}\r\n\r\n\tpublic static void UpdateMesh<T>( this Mesh mesh, VertexAttribute[] layout, List<T> vertices, List<int> indices )\r\n\t\twhere T : unmanaged\r\n\t{\r\n\t\tif ( !mesh.HasIndexBuffer )\r\n\t\t{\r\n\t\t\tmesh.CreateVertexBuffer( vertices.Count, layout, vertices );\r\n\t\t\tmesh.CreateIndexBuffer( indices.Count, indices );\r\n\t\t}\r\n\t\telse if ( indices.Count > 0 && vertices.Count > 0 )\r\n\t\t{\r\n\t\t\tmesh.SetIndexBufferSize( indices.Count );\r\n\t\t\tmesh.SetVertexBufferSize( vertices.Count );\r\n\r\n\t\t\tmesh.SetVertexBufferData( vertices );\r\n\t\t\tmesh.SetIndexBufferData( indices );\r\n\t\t}\r\n\r\n\t\tmesh.SetIndexRange( 0, indices.Count );\r\n\t}\r\n}\r\n"
},
{
"Ident": "facepunch.libpolygon",
"Path": "Code/PolygonMeshBuilder.Fill.cs",
"FileName": "PolygonMeshBuilder.Fill.cs",
"PackageType": "library",
"CodeKind": "Game",
"AssetVersionId": 55832,
"IsPrivate": false,
"Code": "using System;\r\nusing System.Collections.Generic;\r\nusing System.Linq;\r\n\r\nnamespace Sandbox.Polygons;\r\n\r\npartial class PolygonMeshBuilder\r\n{\r\n\t/// <summary>\r\n\t/// Triangulate any remaining active edges so that the generated mesh is closed.\r\n\t/// </summary>\r\n\tpublic PolygonMeshBuilder Fill()\r\n\t{\r\n\t\tValidate();\r\n\r\n\t\tFill_UpdateExistingVertices();\r\n\t\tFill_SplitIntoMonotonicPolygons();\r\n\t\tFill_Triangulate();\r\n\r\n\t\tPostBevel();\r\n\r\n\t\treturn this;\r\n\t}\r\n\r\n\tprivate enum SweepEvent\r\n\t{\r\n\t\tStart,\r\n\t\tEnd,\r\n\t\tSplit,\r\n\t\tMerge,\r\n\t\tUpper,\r\n\t\tLower\r\n\t}\r\n\r\n\tprivate static SweepEvent CategorizeEvent( in Edge prev, in Edge curr, in Edge next )\r\n\t{\r\n\t\tvar prevLeft = Compare( prev.Origin, curr.Origin ) < 0;\r\n\t\tvar nextLeft = Compare( next.Origin, curr.Origin ) < 0;\r\n\r\n\t\tvar nextBelow = curr.Tangent.y < -prev.Tangent.y;\r\n\r\n\t\tswitch (prevLeft, nextLeft, nextBelow)\r\n\t\t{\r\n\t\t\tcase (false, false, false ):\r\n\t\t\t\treturn SweepEvent.Start;\r\n\r\n\t\t\tcase (true, true, true ):\r\n\t\t\t\treturn SweepEvent.End;\r\n\r\n\t\t\tcase (false, false, true ):\r\n\t\t\t\treturn SweepEvent.Split;\r\n\r\n\t\t\tcase (true, true, false ):\r\n\t\t\t\treturn SweepEvent.Merge;\r\n\r\n\t\t\tcase (true, false, _ ):\r\n\t\t\t\treturn SweepEvent.Upper;\r\n\r\n\t\t\tcase (false, true, _ ):\r\n\t\t\t\treturn SweepEvent.Lower;\r\n\t\t}\r\n\t}\r\n\r\n\t[ThreadStatic]\r\n\tprivate static List<int> Fill_SortedEdges;\r\n\r\n\t[ThreadStatic]\r\n\tprivate static Dictionary<int, (int Index, bool WasMerge)> Fill_Helpers;\r\n\r\n\t[ThreadStatic]\r\n\tprivate static List<SweepEdge> Fill_SweepEdges;\r\n\r\n\tprivate readonly struct SweepEdge\r\n\t{\r\n\t\tpublic int Index { get; }\r\n\r\n\t\tpublic Vector2 Origin { get; }\r\n\t\tpublic float DeltaY { get; }\r\n\r\n\t\tpublic SweepEdge( in Edge edge )\r\n\t\t{\r\n\t\t\tIndex = edge.Index;\r\n\r\n\t\t\tOrigin = edge.Origin;\r\n\t\t\tDeltaY = Math.Abs( edge.Tangent.x ) <= 0.0001f\r\n\t\t\t\t? 0f : edge.Tangent.y / edge.Tangent.x;\r\n\t\t}\r\n\r\n\t\tpublic float GetEdgeY( float x )\r\n\t\t{\r\n\t\t\treturn Origin.y + DeltaY * (x - Origin.x);\r\n\t\t}\r\n\t}\r\n\r\n\tprivate int ConnectTwoWay( ref Edge a, ref Edge b )\r\n\t{\r\n\t\tref var prevA = ref _allEdges[a.PrevEdge];\r\n\t\tref var prevB = ref _allEdges[b.PrevEdge];\r\n\r\n\t\tref var aNew = ref _allEdges[AddEdge( a.Origin, (b.Origin - a.Origin).Normal, a.Distance )];\r\n\t\tref var bNew = ref _allEdges[AddEdge( b.Origin, (a.Origin - b.Origin).Normal, b.Distance )];\r\n\r\n\t\taNew.Vertices = AddVertices( ref a );\r\n\t\tbNew.Vertices = AddVertices( ref b );\r\n\r\n\t\tSimpleConnectEdges( ref prevA, ref aNew );\r\n\t\tSimpleConnectEdges( ref aNew, ref b );\r\n\r\n\t\tSimpleConnectEdges( ref prevB, ref bNew );\r\n\t\tSimpleConnectEdges( ref bNew, ref a );\r\n\r\n\t\t_activeEdges.Add( aNew.Index );\r\n\t\t_activeEdges.Add( bNew.Index );\r\n\r\n\t\treturn aNew.Index;\r\n\t}\r\n\r\n\tprivate int FixUp( ref Edge v, in Edge e )\r\n\t{\r\n\t\tvar helperInfo = Fill_Helpers[e.Index];\r\n\r\n\t\tif ( helperInfo.WasMerge )\r\n\t\t{\r\n\t\t\treturn ConnectTwoWay( ref v, ref _allEdges[helperInfo.Index] );\r\n\t\t}\r\n\r\n\t\treturn v.Index;\r\n\t}\r\n\r\n\tprivate void SetHelper( in Edge edge, in Edge helper, bool wasMerge )\r\n\t{\r\n\t\tFill_Helpers[edge.Index] = (helper.Index, wasMerge);\r\n\t}\r\n\r\n\tprivate void AddSweepEdge( in Edge edge )\r\n\t{\r\n\t\t// TODO: could binary search for insertion point\r\n\r\n\t\tvar origin = edge.Origin;\r\n\t\tFill_SweepEdges.Add( new SweepEdge( edge ) );\r\n\t\tFill_SweepEdges.Sort( ( a, b ) =>\r\n\t\t\ta.GetEdgeY( origin.x ).CompareTo( b.GetEdgeY( origin.x ) ) );\r\n\t}\r\n\r\n\tprivate void ReplaceSweepEdge( in Edge old, in Edge replacement )\r\n\t{\r\n\t\t// TODO: could binary search\r\n\r\n\t\tfor ( var i = 0; i < Fill_SweepEdges.Count; ++i )\r\n\t\t{\r\n\t\t\tif ( Fill_SweepEdges[i].Index == old.Index )\r\n\t\t\t{\r\n\t\t\t\tFill_SweepEdges[i] = new SweepEdge( in replacement );\r\n\t\t\t\tbreak;\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\r\n\tprivate void RemoveSweepEdge( in Edge edge )\r\n\t{\r\n\t\t// TODO: could binary search\r\n\r\n\t\tfor ( var i = 0; i < Fill_SweepEdges.Count; ++i )\r\n\t\t{\r\n\t\t\tif ( Fill_SweepEdges[i].Index == edge.Index )\r\n\t\t\t{\r\n\t\t\t\tFill_SweepEdges.RemoveAt( i );\r\n\t\t\t\tbreak;\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\r\n\tprivate int FindAboveSweepEdge( in Edge edge )\r\n\t{\r\n\t\t// TODO: could binary search\r\n\r\n\t\tforeach ( var other in Fill_SweepEdges )\r\n\t\t{\r\n\t\t\tif ( edge.PrevEdge == other.Index || edge.Index == other.Index )\r\n\t\t\t{\r\n\t\t\t\tcontinue;\r\n\t\t\t}\r\n\r\n\t\t\tif ( other.GetEdgeY( edge.Origin.x ) - edge.Origin.y >= 0f )\r\n\t\t\t{\r\n\t\t\t\treturn other.Index;\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\tthrow new Exception();\r\n\t}\r\n\r\n\tprivate void Fill_UpdateExistingVertices()\r\n\t{\r\n\t\t_nextAngle = MathF.PI * 0.5f;\r\n\t\t_nextDistance = float.PositiveInfinity;\r\n\r\n\t\tif ( !SkipNormals && Math.Abs( _prevAngle - _nextAngle ) >= 0.001f )\r\n\t\t{\r\n\t\t\tforeach ( var index in _activeEdges )\r\n\t\t\t{\r\n\t\t\t\tref var edge = ref _allEdges[index];\r\n\t\t\t\tedge.Vertices = (-1, -1);\r\n\r\n\t\t\t\tAddVertices( ref edge, true );\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\t_prevAngle = _nextAngle;\r\n\t}\r\n\r\n\tprivate void Fill_SplitIntoMonotonicPolygons()\r\n\t{\r\n\t\tFill_SortedEdges ??= new List<int>();\r\n\t\tFill_SortedEdges.Clear();\r\n\r\n\t\tFill_SortedEdges.AddRange( _activeEdges );\r\n\r\n\t\tFill_SortedEdges.Sort( ( a, b ) => Compare( _allEdges[a].Origin, _allEdges[b].Origin ) );\r\n\r\n\t\tFill_Helpers ??= new Dictionary<int, (int Index, bool WasMerge)>();\r\n\t\tFill_Helpers.Clear();\r\n\r\n\t\tFill_SweepEdges ??= new List<SweepEdge>();\r\n\t\tFill_SweepEdges.Clear();\r\n\r\n\t\t// Based on https://www.cs.umd.edu/class/spring2020/cmsc754/Lects/lect05-triangulate.pdf\r\n\r\n\t\t// Add pairs of edges to split into x-monotonic polygons\r\n\r\n\t\tforeach ( var index in Fill_SortedEdges )\r\n\t\t{\r\n\t\t\tEnsureCapacity( 4 );\r\n\r\n\t\t\tref var edge = ref _allEdges[index];\r\n\t\t\tref var next = ref _allEdges[edge.NextEdge];\r\n\t\t\tref var prev = ref _allEdges[edge.PrevEdge];\r\n\r\n\t\t\tswitch ( CategorizeEvent( in prev, in edge, in next ) )\r\n\t\t\t{\r\n\t\t\t\tcase SweepEvent.Start:\r\n\t\t\t\t\tAddSweepEdge( in edge );\r\n\t\t\t\t\tSetHelper( in edge, in edge, false );\r\n\t\t\t\t\tbreak;\r\n\r\n\t\t\t\tcase SweepEvent.End:\r\n\t\t\t\t\tFixUp( ref edge, in prev );\r\n\t\t\t\t\tRemoveSweepEdge( in prev );\r\n\t\t\t\t\tbreak;\r\n\r\n\t\t\t\tcase SweepEvent.Split:\r\n\t\t\t\t\t{\r\n\t\t\t\t\t\tref var above = ref _allEdges[FindAboveSweepEdge( in edge )];\r\n\t\t\t\t\t\tref var helper = ref _allEdges[Fill_Helpers[above.Index].Index];\r\n\t\t\t\t\t\tref var fixedUp = ref _allEdges[ConnectTwoWay( ref edge, ref helper )];\r\n\t\t\t\t\t\tAddSweepEdge( in edge );\r\n\t\t\t\t\t\tSetHelper( in above, in fixedUp, false );\r\n\t\t\t\t\t\tSetHelper( in edge, in edge, false );\r\n\t\t\t\t\t\tbreak;\r\n\t\t\t\t\t}\r\n\r\n\t\t\t\tcase SweepEvent.Merge:\r\n\t\t\t\t\t{\r\n\t\t\t\t\t\tref var above = ref _allEdges[FindAboveSweepEdge( in edge )];\r\n\t\t\t\t\t\tRemoveSweepEdge( in prev );\r\n\t\t\t\t\t\tref var new1 = ref _allEdges[FixUp( ref edge, in above )];\r\n\t\t\t\t\t\tFixUp( ref new1, in prev );\r\n\t\t\t\t\t\tSetHelper( in above, in new1, true );\r\n\t\t\t\t\t\tbreak;\r\n\t\t\t\t\t}\r\n\r\n\t\t\t\tcase SweepEvent.Upper:\r\n\t\t\t\t\tFixUp( ref edge, in prev );\r\n\t\t\t\t\tReplaceSweepEdge( in prev, in edge );\r\n\t\t\t\t\tSetHelper( in edge, in edge, false );\r\n\t\t\t\t\tbreak;\r\n\r\n\t\t\t\tcase SweepEvent.Lower:\r\n\t\t\t\t\t{\r\n\t\t\t\t\t\tref var above = ref _allEdges[FindAboveSweepEdge( in edge )];\r\n\t\t\t\t\t\tref var helper = ref _allEdges[FixUp( ref edge, in above )];\r\n\t\t\t\t\t\tSetHelper( in above, in helper, false );\r\n\t\t\t\t\t\tbreak;\r\n\t\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\r\n\tprivate readonly struct CloseVertex\r\n\t{\r\n\t\tpublic Vector2 Position { get; }\r\n\r\n\t\t/// <summary>\r\n\t\t/// Difference to this vertex from the previous one.\r\n\t\t/// </summary>\r\n\t\tpublic Vector2 Delta { get; }\r\n\r\n\t\tpublic int Vertex { get; }\r\n\t\tpublic bool IsUpper { get; }\r\n\r\n\t\tpublic CloseVertex( Vector2 position, Vector2 delta, int vertex, bool isUpper )\r\n\t\t{\r\n\t\t\tPosition = position;\r\n\t\t\tDelta = delta;\r\n\t\t\tVertex = vertex;\r\n\t\t\tIsUpper = isUpper;\r\n\t\t}\r\n\t}\r\n\r\n\t[ThreadStatic]\r\n\tprivate static List<CloseVertex> Fill_Vertices;\r\n\r\n\t[ThreadStatic]\r\n\tprivate static Stack<CloseVertex> Fill_Stack;\r\n\r\n\tprivate static bool IsReflex( Vector2 prevDelta, Vector2 nextDelta )\r\n\t{\r\n\t\treturn Vector2.Dot( Helpers.Rotate90( nextDelta ), prevDelta ) >= 0f;\r\n\t}\r\n\r\n\tprivate static int Compare( Vector2 a, Vector2 b )\r\n\t{\r\n\t\tvar xCompare = a.x.CompareTo( b.x );\r\n\t\tif ( xCompare != 0 ) return xCompare;\r\n\t\treturn a.y.CompareTo( b.y );\r\n\t}\r\n\r\n\tprivate void Fill_Triangulate()\r\n\t{\r\n\t\tFill_Vertices ??= new List<CloseVertex>();\r\n\t\tFill_Stack ??= new Stack<CloseVertex>();\r\n\r\n\t\twhile ( _activeEdges.Count > 0 )\r\n\t\t{\r\n\t\t\tvar firstIndex = _activeEdges.First();\r\n\t\t\t_activeEdges.Remove( firstIndex );\r\n\r\n\t\t\tvar first = _allEdges[firstIndex];\r\n\r\n\t\t\tvar minPos = first.Origin;\r\n\t\t\tvar maxPos = first.Origin;\r\n\t\t\tvar minEdgeIndex = firstIndex;\r\n\t\t\tvar maxEdgeIndex = firstIndex;\r\n\r\n\t\t\tvar edge = first;\r\n\r\n\t\t\twhile ( edge.NextEdge != first.Index )\r\n\t\t\t{\r\n\t\t\t\tedge = _allEdges[edge.NextEdge];\r\n\t\t\t\t_activeEdges.Remove( edge.Index );\r\n\r\n\t\t\t\tif ( Compare( edge.Origin, minPos ) < 0 )\r\n\t\t\t\t{\r\n\t\t\t\t\tminPos = edge.Origin;\r\n\t\t\t\t\tminEdgeIndex = edge.Index;\r\n\t\t\t\t}\r\n\r\n\t\t\t\tif ( Compare( edge.Origin, maxPos ) > 0 )\r\n\t\t\t\t{\r\n\t\t\t\t\tmaxPos = edge.Origin;\r\n\t\t\t\t\tmaxEdgeIndex = edge.Index;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\r\n\t\t\tFill_Vertices.Clear();\r\n\r\n\t\t\tedge = _allEdges[minEdgeIndex];\r\n\t\t\tFill_Vertices.Add( new CloseVertex( edge.Origin, default, edge.Vertices.Prev, true ) );\r\n\r\n\t\t\twhile ( edge.NextEdge != maxEdgeIndex )\r\n\t\t\t{\r\n\t\t\t\tvar next = _allEdges[edge.NextEdge];\r\n\t\t\t\tFill_Vertices.Add( new CloseVertex( next.Origin, next.Origin - edge.Origin, next.Vertices.Prev, true ) );\r\n\t\t\t\tedge = next;\r\n\t\t\t}\r\n\r\n\t\t\tedge = _allEdges[maxEdgeIndex];\r\n\r\n\t\t\twhile ( edge.Index != minEdgeIndex )\r\n\t\t\t{\r\n\t\t\t\tvar next = _allEdges[edge.NextEdge];\r\n\t\t\t\tFill_Vertices.Add( new CloseVertex( edge.Origin, edge.Origin - next.Origin, edge.Vertices.Prev, false ) );\r\n\t\t\t\tedge = next;\r\n\t\t\t}\r\n\r\n\t\t\tFill_Vertices.Sort( ( a, b ) => Compare( a.Position, b.Position ) );\r\n\r\n\t\t\tFill_Stack.Clear();\r\n\t\t\tFill_Stack.Push( Fill_Vertices[0] );\r\n\t\t\tFill_Stack.Push( Fill_Vertices[1] );\r\n\r\n\t\t\tfor ( var i = 2; i < Fill_Vertices.Count; ++i )\r\n\t\t\t{\r\n\t\t\t\tvar next = Fill_Vertices[i];\r\n\t\t\t\tvar top = Fill_Stack.Peek();\r\n\r\n\t\t\t\tif ( top.IsUpper != next.IsUpper )\r\n\t\t\t\t{\r\n\t\t\t\t\t// Case 1\r\n\r\n\t\t\t\t\twhile ( Fill_Stack.Count > 1 )\r\n\t\t\t\t\t{\r\n\t\t\t\t\t\tvar curr = Fill_Stack.Pop();\r\n\t\t\t\t\t\tvar prev = Fill_Stack.Peek();\r\n\r\n\t\t\t\t\t\tif ( next.IsUpper )\r\n\t\t\t\t\t\t{\r\n\t\t\t\t\t\t\tAddTriangle( next.Vertex, prev.Vertex, curr.Vertex );\r\n\t\t\t\t\t\t}\r\n\t\t\t\t\t\telse\r\n\t\t\t\t\t\t{\r\n\t\t\t\t\t\t\tAddTriangle( next.Vertex, curr.Vertex, prev.Vertex );\r\n\t\t\t\t\t\t}\r\n\t\t\t\t\t}\r\n\r\n\t\t\t\t\tFill_Stack.Clear();\r\n\t\t\t\t\tFill_Stack.Push( top );\r\n\t\t\t\t\tFill_Stack.Push( new CloseVertex( next.Position,\r\n\t\t\t\t\t\tnext.Position - top.Position,\r\n\t\t\t\t\t\tnext.Vertex, next.IsUpper ) );\r\n\t\t\t\t\tcontinue;\r\n\t\t\t\t}\r\n\r\n\t\t\t\twhile ( Fill_Stack.Count > 1 && IsReflex( top.Delta, next.Position - top.Position ) != top.IsUpper )\r\n\t\t\t\t{\r\n\t\t\t\t\tvar curr = Fill_Stack.Pop();\r\n\t\t\t\t\ttop = Fill_Stack.Peek();\r\n\r\n\t\t\t\t\tif ( next.IsUpper )\r\n\t\t\t\t\t{\r\n\t\t\t\t\t\tAddTriangle( next.Vertex, curr.Vertex, top.Vertex );\r\n\t\t\t\t\t}\r\n\t\t\t\t\telse\r\n\t\t\t\t\t{\r\n\t\t\t\t\t\tAddTriangle( next.Vertex, top.Vertex, curr.Vertex );\r\n\t\t\t\t\t}\r\n\t\t\t\t}\r\n\r\n\t\t\t\tFill_Stack.Push( new CloseVertex( next.Position,\r\n\t\t\t\t\tnext.Position - top.Position,\r\n\t\t\t\t\tnext.Vertex, next.IsUpper ) );\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n}"
},
{
"Ident": "facepunch.libpolygon",
"Path": "Code/PolygonMeshBuilder.Validate.cs",
"FileName": "PolygonMeshBuilder.Validate.cs",
"PackageType": "library",
"CodeKind": "Game",
"AssetVersionId": 55832,
"IsPrivate": false,
"Code": "using System;\r\nusing System.Collections.Generic;\r\n\r\nnamespace Sandbox.Polygons;\r\n\r\npartial class PolygonMeshBuilder\r\n{\r\n\t[ThreadStatic]\r\n\tprivate static List<int> Validate_EdgeList;\r\n\r\n\tprivate void Validate()\r\n\t{\r\n\t\tif ( _validated )\r\n\t\t{\r\n\t\t\treturn;\r\n\t\t}\r\n\r\n\t\t// Check active edge loops:\r\n\t\t// * Referenced edges must also be active\r\n\t\t// * Make sure references are correct in both directions\r\n\t\t// * Edges can't reference themselves\r\n\r\n\t\tforeach ( var edgeIndex in _activeEdges )\r\n\t\t{\r\n\t\t\tref var edge = ref _allEdges[edgeIndex];\r\n\r\n\t\t\tif ( !_activeEdges.Contains( edge.NextEdge ) )\r\n\t\t\t{\r\n\t\t\t\tthrow InvalidPolygonException();\r\n\t\t\t}\r\n\r\n\t\t\tif ( !_activeEdges.Contains( edge.PrevEdge ) )\r\n\t\t\t{\r\n\t\t\t\tthrow InvalidPolygonException();\r\n\t\t\t}\r\n\r\n\t\t\tif ( edge.NextEdge == edge.Index )\r\n\t\t\t{\r\n\t\t\t\tthrow InvalidPolygonException();\r\n\t\t\t}\r\n\r\n\t\t\tref var next = ref _allEdges[edge.NextEdge];\r\n\r\n\t\t\tif ( next.PrevEdge != edge.Index )\r\n\t\t\t{\r\n\t\t\t\tthrow InvalidPolygonException();\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\t// Check for intersecting edges\r\n\t\t// TODO: Bentley\u2013Ottmann?\r\n\r\n\t\tValidate_EdgeList ??= new List<int>();\r\n\t\tValidate_EdgeList.Clear();\r\n\t\tValidate_EdgeList.AddRange( _activeEdges );\r\n\r\n\t\tfor ( var i = 0; i < Validate_EdgeList.Count; ++i )\r\n\t\t{\r\n\t\t\tref var edgeA0 = ref _allEdges[Validate_EdgeList[i]];\r\n\t\t\tref var edgeA1 = ref _allEdges[edgeA0.NextEdge];\r\n\r\n\t\t\tvar a0 = edgeA0.Origin;\r\n\t\t\tvar a1 = edgeA1.Origin;\r\n\r\n\t\t\tvar minA = Vector2.Min( a0 ,a1 );\r\n\t\t\tvar maxA = Vector2.Max( a0, a1 );\r\n\r\n\t\t\tfor ( var j = i + 1; j < Validate_EdgeList.Count; ++j )\r\n\t\t\t{\r\n\t\t\t\tref var edgeB0 = ref _allEdges[Validate_EdgeList[j]];\r\n\r\n\t\t\t\tif ( edgeA0.NextEdge == edgeB0.Index || edgeA0.PrevEdge == edgeB0.Index )\r\n\t\t\t\t{\r\n\t\t\t\t\tcontinue;\r\n\t\t\t\t}\r\n\r\n\t\t\t\tref var edgeB1 = ref _allEdges[edgeB0.NextEdge];\r\n\r\n\t\t\t\tvar b0 = edgeA0.Origin;\r\n\t\t\t\tvar b1 = edgeA1.Origin;\r\n\r\n\t\t\t\tvar minB = Vector2.Min( b0, b1 );\r\n\t\t\t\tvar maxB = Vector2.Max( b0, b1 );\r\n\r\n\t\t\t\tif ( minA.x >= maxB.x || minA.y >= maxB.y || minB.x >= maxA.x || minB.y >= maxA.y )\r\n\t\t\t\t{\r\n\t\t\t\t\tcontinue;\r\n\t\t\t\t}\r\n\r\n\t\t\t\tif ( Helpers.LineSegmentsIntersect( a0, a1, b0, b1 ) )\r\n\t\t\t\t{\r\n\t\t\t\t\tthrow InvalidPolygonException();\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\t_validated = true;\r\n\t}\r\n\r\n\tprivate static Exception InvalidPolygonException()\r\n\t{\r\n\t\treturn new Exception( \"Invalid polygon\" );\r\n\t}\r\n}\r\n"
},
{
"Ident": "facepunch.libpolygon",
"Path": "Code/PolygonMeshBuilder.cs",
"FileName": "PolygonMeshBuilder.cs",
"PackageType": "library",
"CodeKind": "Game",
"AssetVersionId": 55832,
"IsPrivate": false,
"Code": "using System;\r\nusing System.Collections.Generic;\r\nusing System.Linq;\r\nusing System.Runtime.CompilerServices;\r\nusing System.Runtime.InteropServices;\r\n\r\nnamespace Sandbox.Polygons;\r\n\r\n/// <summary>\r\n/// Helper class for building 3D meshes based on a 2D polygon. Supports\r\n/// concave polygons with holes, although edges must not intersect.\r\n/// </summary>\r\npublic partial class PolygonMeshBuilder : Pooled<PolygonMeshBuilder>\r\n{\r\n\tpublic record struct Vertex( Vector3 Position, Vector3 Normal, Vector4 Tangent )\r\n\t{\r\n\t\tpublic static VertexAttribute[] Layout { get; } = new[]\r\n\t\t{\r\n\t\t\tnew VertexAttribute( VertexAttributeType.Position, VertexAttributeFormat.Float32 ),\r\n\t\t\tnew VertexAttribute( VertexAttributeType.Normal, VertexAttributeFormat.Float32 ),\r\n\t\t\tnew VertexAttribute( VertexAttributeType.Tangent, VertexAttributeFormat.Float32, 4 )\r\n\t\t};\r\n\t}\r\n\r\n\tprivate int _nextEdgeIndex;\r\n\tprivate Edge[] _allEdges = new Edge[64];\r\n\tprivate readonly HashSet<int> _activeEdges = new ();\r\n\r\n\tprivate readonly List<Vertex> _vertices = new ();\r\n\tprivate readonly List<int> _indices = new ();\r\n\r\n\tprivate float _prevDistance;\r\n\tprivate float _nextDistance;\r\n\r\n\tprivate float _invDistance;\r\n\r\n\tprivate float _prevHeight;\r\n\tprivate float _nextHeight;\r\n\r\n\tprivate float _prevAngle;\r\n\tprivate float _nextAngle;\r\n\r\n\tprivate float _minSmoothNormalDot;\r\n\r\n\tprivate bool _validated;\r\n\r\n\t/// <summary>\r\n\t/// Number of edges that will be affected by calls to methods like <see cref=\"Bevel\"/>, <see cref=\"Round\"/>, and <see cref=\"Close\"/>.\r\n\t/// </summary>\r\n\tpublic int ActiveEdgeCount => _activeEdges.Count;\r\n\r\n\t/// <summary>\r\n\t/// If true, no active edges remain because the mesh is fully closed.\r\n\t/// </summary>\r\n\tpublic bool IsClosed => _activeEdges.Count == 0;\r\n\r\n\t/// <summary>\r\n\t/// Corners of the original polygon with an interior or exterior\r\n\t/// angle less than this (in radians) will have smooth normals.\r\n\t/// </summary>\r\n\tpublic float MaxSmoothAngle { get; set; } = 0f;\r\n\r\n\t/// <summary>\r\n\t/// If true, don't bother generating normals / tangents.\r\n\t/// </summary>\r\n\tpublic bool SkipNormals { get; set; }\r\n\r\n\t/// <summary>\r\n\t/// Positions of each vertex in the generated mesh.\r\n\t/// </summary>\r\n\tpublic IEnumerable<Vector3> Positions => _vertices.Select( x => x.Position );\r\n\r\n\t/// <summary>\r\n\t/// Normals of each vertex in the generated mesh.\r\n\t/// </summary>\r\n\tpublic IEnumerable<Vector3> Normals => _vertices.Select( x => x.Normal );\r\n\r\n\t/// <summary>\r\n\t/// U-tangents, and the signs of the V-tangents, of each vertex in the generated mesh.\r\n\t/// </summary>\r\n\tpublic IEnumerable<Vector4> Tangents => _vertices.Select( x => x.Tangent );\r\n\r\n\t/// <summary>\r\n\t/// Positions, normals, and tangents of each vertex.\r\n\t/// </summary>\r\n\tpublic List<Vertex> Vertices => _vertices;\r\n\r\n\t/// <summary>\r\n\t/// Indices of vertices describing the triangulation of the generated mesh.\r\n\t/// </summary>\r\n\tpublic List<int> Indices => _indices;\r\n\r\n\t/// <summary>\r\n\t/// Clear all geometry from this builder.\r\n\t/// </summary>\r\n\tpublic PolygonMeshBuilder Clear()\r\n\t{\r\n\t\t_nextEdgeIndex = 0;\r\n\t\t_activeEdges.Clear();\r\n\r\n\t\t_vertices.Clear();\r\n\t\t_indices.Clear();\r\n\r\n\t\t_prevDistance = 0f;\r\n\t\t_nextDistance = 0f;\r\n\r\n\t\t_invDistance = 0f;\r\n\r\n\t\t_prevHeight = 0f;\r\n\t\t_nextHeight = 0f;\r\n\r\n\t\t_prevAngle = 0f;\r\n\t\t_nextAngle = 0f;\r\n\r\n\t\t_minSmoothNormalDot = 0f;\r\n\r\n\t\t_validated = true;\r\n\r\n\t\treturn this;\r\n\t}\r\n\r\n\t/// <summary>\r\n\t/// Reset this builder to be like a new instance.\r\n\t/// </summary>\r\n\tpublic override void Reset()\r\n\t{\r\n\t\tClear();\r\n\r\n\t\tMaxSmoothAngle = 0f;\r\n\t\tSkipNormals = false;\r\n\t}\r\n\r\n\tprivate static int NextPowerOfTwo( int value )\r\n\t{\r\n\t\tvar po2 = 1;\r\n\t\twhile ( po2 < value )\r\n\t\t{\r\n\t\t\tpo2 <<= 1;\r\n\t\t}\r\n\r\n\t\treturn po2;\r\n\t}\r\n\r\n\tprivate void EnsureCapacity( int toAdd )\r\n\t{\r\n\t\tif ( _nextEdgeIndex + toAdd > _allEdges.Length )\r\n\t\t{\r\n\t\t\tArray.Resize( ref _allEdges, NextPowerOfTwo( _nextEdgeIndex + toAdd ) );\r\n\t\t}\r\n\t}\r\n\r\n\tprivate int AddEdge( Vector2 origin, Vector2 tangent, float distance, int? twinOffset = null )\r\n\t{\r\n\t\tvar edge = new Edge( _nextEdgeIndex, origin, tangent, distance, twinOffset != null ? _nextEdgeIndex + twinOffset.Value : -1 );\r\n\t\t_allEdges[edge.Index] = edge;\r\n\t\t++_nextEdgeIndex;\r\n\t\treturn edge.Index;\r\n\t}\r\n\r\n\tprivate void Invalidate()\r\n\t{\r\n\t\t_validated = false;\r\n\t}\r\n\r\n\t/// <summary>\r\n\t/// Add a set of active edges forming a loop. Clockwise loops will be a solid polygon, and count-clockwise\r\n\t/// will form a hole. Holes must be inside of solid polygons, otherwise the mesh can't be closed correctly.\r\n\t/// </summary>\r\n\t/// <param name=\"vertices\">List of vertices to read a range from.</param>\r\n\t/// <param name=\"offset\">Index of the first vertex in the loop.</param>\r\n\t/// <param name=\"count\">Number of vertices in the loop.</param>\r\n\t/// <param name=\"reverse\">If true, reverse the order of the vertices in the loop.</param>\r\n\tpublic PolygonMeshBuilder AddEdgeLoop( IReadOnlyList<Vector2> vertices, int offset, int count, bool reverse = false )\r\n\t{\r\n\t\treturn AddEdgeLoop( vertices, offset, count, Vector2.Zero, Vector2.One, reverse );\r\n\t}\r\n\r\n\tpublic PolygonMeshBuilder AddEdgeLoop( IReadOnlyList<Vector2> vertices, int offset, int count, Vector2 position, Vector2 scale, bool reverse = false )\r\n\t{\r\n\t\tvar firstIndex = _nextEdgeIndex;\r\n\r\n\t\tEnsureCapacity( count );\r\n\t\tInvalidate();\r\n\r\n var prevVertex = position + vertices[offset + count - 1] * scale;\r\n\t\tfor ( var i = 0; i < count; ++i )\r\n\t\t{\r\n\t\t\tvar nextVertex = position + vertices[offset + i] * scale;\r\n\r\n\t\t\t_activeEdges.Add( AddEdge( prevVertex, Helpers.NormalizeSafe( nextVertex - prevVertex ), _prevDistance ) );\r\n\r\n\t\t\tprevVertex = nextVertex;\r\n\t\t}\r\n\r\n\t\tvar prevIndex = count - 1;\r\n\t\tfor ( var i = 0; i < count; ++i )\r\n\t\t{\r\n\t\t\tref var prevEdge = ref _allEdges[firstIndex + prevIndex];\r\n\t\t\tref var nextEdge = ref _allEdges[firstIndex + i];\r\n\r\n\t\t\tif ( reverse )\r\n\t\t\t{\r\n\t\t\t\tConnectEdges( ref nextEdge, ref prevEdge );\r\n\t\t\t}\r\n\t\t\telse\r\n\t\t\t{\r\n\t\t\t\tConnectEdges( ref prevEdge, ref nextEdge );\r\n\t\t\t}\r\n\r\n\t\t\tprevIndex = i;\r\n\t\t}\r\n\r\n\t\treturn this;\r\n\t}\r\n\r\n\t[ThreadStatic]\r\n\tprivate static Dictionary<int, int> AddEdges_VertexMap;\r\n\r\n\t/// <summary>\r\n\t/// Add a raw set of edges. Be careful to ensure that each loop of edges is fully closed.\r\n\t/// </summary>\r\n\t/// <param name=\"vertices\">Positions of vertices to connect with edges.</param>\r\n\t/// <param name=\"edges\">Indices of the start and end vertices of each edge.</param>\r\n\tpublic void AddEdges( IReadOnlyList<Vector2> vertices, IReadOnlyList<(int Prev, int Next)> edges )\r\n\t{\r\n\t\tAddEdges_VertexMap ??= new Dictionary<int, int>();\r\n\t\tAddEdges_VertexMap.Clear();\r\n\r\n\t\tEnsureCapacity( edges.Count );\r\n\t\tInvalidate();\r\n\r\n foreach ( var (i, j) in edges )\r\n\t\t{\r\n\t\t\tvar prev = vertices[i];\r\n\t\t\tvar next = vertices[j];\r\n\r\n\t\t\tvar index = AddEdge( prev, Helpers.NormalizeSafe( next - prev ), _prevDistance );\r\n\r\n\t\t\t_activeEdges.Add( index );\r\n\t\t\tAddEdges_VertexMap.Add( i, index );\r\n\t\t}\r\n\r\n\t\tfor ( var i = 0; i < edges.Count; ++i )\r\n\t\t{\r\n\t\t\tvar edge = edges[i];\r\n\r\n\t\t\tref var prev = ref _allEdges[AddEdges_VertexMap[edge.Prev]];\r\n\t\t\tref var next = ref _allEdges[AddEdges_VertexMap[edge.Next]];\r\n\r\n\t\t\tConnectEdges( ref prev, ref next );\r\n\t\t}\r\n\t}\r\n\r\n\tprivate static float LerpRadians( float a, float b, float t )\r\n\t{\r\n\t\tvar delta = b - a;\r\n\t\tdelta -= MathF.Floor( delta * (0.5f / MathF.PI) ) * MathF.PI * 2f;\r\n\r\n\t\tif ( delta > MathF.PI )\r\n\t\t{\r\n\t\t\tdelta -= MathF.PI * 2f;\r\n\t\t}\r\n\r\n\t\treturn a + delta * Math.Clamp( t, 0f, 1f );\r\n\t}\r\n\r\n\tprivate Vector4 GetTangent( Vector3 normal )\r\n\t{\r\n\t\tvar tangent = Vector3.Cross( normal, new Vector3( 0f, 0f, 1f ) ).Normal;\r\n\r\n\t\treturn new Vector4( tangent, 1f );\r\n\t}\r\n\r\n\tprivate (int Prev, int Next) AddVertices( ref Edge edge, bool forceMaxDistance = false )\r\n\t{\r\n\t\tif ( edge.Vertices.Prev > -1 )\r\n\t\t{\r\n\t\t\treturn edge.Vertices;\r\n\t\t}\r\n\r\n\t\tvar prevEdge = _allEdges[edge.PrevEdge];\r\n\r\n\t\tvar index = _vertices.Count;\r\n\t\tvar prevNormal = -prevEdge.Normal;\r\n\t\tvar nextNormal = -edge.Normal;\r\n\r\n\t\tvar t = forceMaxDistance ? 1f : (edge.Distance - _prevDistance) * _invDistance;\r\n\t\tvar height = _prevHeight + t * (_nextHeight - _prevHeight);\r\n\r\n\t\tvar pos = new Vector3( edge.Origin.x, edge.Origin.y, height );\r\n\r\n\t\tif ( SkipNormals || MathF.Abs( _nextHeight - _prevHeight ) <= 0.001f )\r\n\t\t{\r\n\t\t\t_vertices.Add( new(\r\n\t\t\t\tpos,\r\n\t\t\t\tnew Vector3( 0f, 0f, 1f ),\r\n\t\t\t\tnew Vector4( 1f, 0f, 0f, 1f ) ) );\r\n\r\n\t\t\tedge.Vertices = (index, index);\r\n\t\t}\r\n\t\telse\r\n\t\t{\r\n\t\t\tvar angle = LerpRadians( _prevAngle, _nextAngle, t );\r\n\t\t\tvar cos = MathF.Cos( angle );\r\n\t\t\tvar sin = MathF.Sin( angle );\r\n\r\n\t\t\tif ( Vector2.Dot( prevNormal, nextNormal ) >= _minSmoothNormalDot )\r\n\t\t\t{\r\n\t\t\t\tvar normal = new Vector3( (prevNormal.x + nextNormal.x) * cos, (prevNormal.y + nextNormal.y) * cos, sin * 2f ).Normal;\r\n\r\n\t\t\t\t_vertices.Add( new( pos, normal, GetTangent( normal ) ) );\r\n\r\n\t\t\t\tedge.Vertices = (index, index);\r\n\t\t\t}\r\n\t\t\telse\r\n\t\t\t{\r\n\t\t\t\tvar normal0 = new Vector3( prevNormal.x * cos, prevNormal.y * cos, sin ).Normal;\r\n\t\t\t\tvar normal1 = new Vector3( nextNormal.x * cos, nextNormal.y * cos, sin ).Normal;\r\n\r\n\t\t\t\t_vertices.Add( new( pos, normal0, GetTangent( normal0 ) ) );\r\n\t\t\t\t_vertices.Add( new( pos, normal1, GetTangent( normal1 ) ) );\r\n\r\n\t\t\t\tedge.Vertices = (index, index + 1);\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\treturn edge.Vertices;\r\n\t}\r\n\r\n\tprivate void AddTriangle( int a, int b, int c )\r\n\t{\r\n\t\t_indices.Add( a );\r\n\t\t_indices.Add( b );\r\n\t\t_indices.Add( c );\r\n\t}\r\n\r\n\t/// <summary>\r\n\t/// Add faces on each active edge extending upwards by the given height.\r\n\t/// </summary>\r\n\t/// <param name=\"height\">Total distance upwards, away from the plane of the polygon.</param>\r\n\tpublic PolygonMeshBuilder Extrude( float height )\r\n\t{\r\n\t\treturn Bevel( 0f, height );\r\n\t}\r\n\r\n\t/// <summary>\r\n\t/// Add faces on each active edge extending inwards by the given width. This will close the mesh if <paramref name=\"width\"/> is large enough.\r\n\t/// </summary>\r\n\t/// <param name=\"width\">Total distance inwards.</param>\r\n\tpublic PolygonMeshBuilder Inset( float width )\r\n\t{\r\n\t\treturn Bevel( width, 0f );\r\n\t}\r\n\r\n\t[ThreadStatic]\r\n\tprivate static Dictionary<int, int> Mirror_IndexMap;\r\n\r\n\t/// <summary>\r\n\t/// Mirrors all previously created faces. The mirror plane is normal to the Z axis, with a given distance from the origin.\r\n\t/// </summary>\r\n\t/// <param name=\"z\">Distance of the mirror plane from the origin.</param>\r\n\tpublic PolygonMeshBuilder Mirror( float z = 0f )\r\n\t{\r\n\t\tMirror_IndexMap ??= new Dictionary<int, int>();\r\n\t\tMirror_IndexMap.Clear();\r\n\r\n\t\t_vertices.EnsureCapacity( _vertices.Count * 2 );\r\n\t\t_indices.EnsureCapacity( _indices.Count * 2 );\r\n\r\n\t\tvar indexCount = _indices.Count;\r\n\t\tvar vertexCount = _vertices.Count;\r\n\r\n\t\tfor ( var i = 0; i < vertexCount; i++ )\r\n\t\t{\r\n\t\t\tvar vertex = _vertices[i];\r\n\t\t\tvar position = vertex.Position;\r\n\t\t\tvar normal = vertex.Normal;\r\n\t\t\tvar tangent = vertex.Tangent;\r\n\r\n\t\t\tif ( Math.Abs( position.z - z ) <= 0.001f && (SkipNormals || Math.Abs( normal.z ) <= 0.0001f && Math.Abs( tangent.z ) <= 0.0001f) )\r\n\t\t\t{\r\n\t\t\t\tMirror_IndexMap.Add( i, i );\r\n\t\t\t}\r\n\t\t\telse\r\n\t\t\t{\r\n\t\t\t\tMirror_IndexMap.Add( i, _vertices.Count );\r\n\r\n\t\t\t\t_vertices.Add( new(\r\n\t\t\t\t\tnew Vector3( position.x, position.y, z * 2f - position.z ),\r\n\t\t\t\t\tnew Vector3( normal.x, normal.y, -normal.z ),\r\n\t\t\t\t\tnew Vector4( tangent.x, tangent.y, -tangent.z, tangent.w ) ) );\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\tfor ( var i = 0; i < indexCount; i += 3 )\r\n\t\t{\r\n\t\t\tvar a = Mirror_IndexMap[_indices[i + 0]];\r\n\t\t\tvar b = Mirror_IndexMap[_indices[i + 1]];\r\n\t\t\tvar c = Mirror_IndexMap[_indices[i + 2]];\r\n\r\n\t\t\t_indices.Add( a );\r\n\t\t\t_indices.Add( c );\r\n\t\t\t_indices.Add( b );\r\n\t\t}\r\n\r\n\t\treturn this;\r\n\t}\r\n\r\n\t/// <summary>\r\n\t/// Perform successive <see cref=\"Bevel\"/>s so that the edge of the polygon curves inwards in a quarter circle arc.\r\n\t/// </summary>\r\n\t/// <param name=\"radius\">Radius of the arc.</param>\r\n\t/// <param name=\"faces\">How many bevels to split the rounded edge into.</param>\r\n\t/// <param name=\"smooth\">If true, use smooth normals rather than flat shading.</param>\r\n\t/// <param name=\"convex\">If true, the faces will be pointing outwards from the center of the arc.</param>\r\n\tpublic PolygonMeshBuilder Arc( float radius, int faces, bool smooth = true, bool convex = true )\r\n\t{\r\n\t\treturn Arc( radius, radius, faces, smooth, convex );\r\n\t}\r\n\r\n\t/// <summary>\r\n\t/// Perform successive <see cref=\"Bevel\"/>s so that the edge of the polygon curves inwards in a quarter circle arc.\r\n\t/// </summary>\r\n\t/// <param name=\"width\">Total distance inwards.</param>\r\n\t/// <param name=\"height\">Total distance upwards, away from the plane of the polygon.</param>\r\n\t/// <param name=\"faces\">How many bevels to split the rounded edge into.</param>\r\n\t/// <param name=\"smooth\">If true, use smooth normals rather than flat shading.</param>\r\n\t/// <param name=\"convex\">If true, the faces will be pointing outwards from the center of the arc.</param>\r\n\tpublic PolygonMeshBuilder Arc( float width, float height, int faces, bool smooth = true, bool convex = true )\r\n\t{\r\n\t\tvar prevWidth = 0f;\r\n\t\tvar prevHeight = 0f;\r\n\t\tvar prevTheta = 0f;\r\n\r\n\t\tstatic float MapAngle( float theta, bool convex, bool positive )\r\n\t\t{\r\n\t\t\tvar min = positive ? 0f : MathF.PI * 0.5f;\r\n\t\t\treturn convex ? min + theta : min + MathF.PI * 0.5f - theta;\r\n\t\t}\r\n\r\n\t\tfor ( var i = 0; i < faces; ++i )\r\n\t\t{\r\n\t\t\tvar theta = MathF.PI * 0.5f * (i + 1f) / faces;\r\n\r\n\t\t\tvar cos = MathF.Cos( theta );\r\n\t\t\tvar sin = MathF.Sin( theta );\r\n\r\n\t\t\tvar nextWidth = 1f - cos;\r\n\t\t\tvar nextHeight = sin;\r\n\r\n\t\t\tif ( smooth )\r\n\t\t\t{\r\n\t\t\t\tif ( height >= 0f == convex )\r\n\t\t\t\t{\r\n\t\t\t\t\tBevel( (nextWidth - prevWidth) * width,\r\n\t\t\t\t\t\t(nextHeight - prevHeight) * height,\r\n\t\t\t\t\t\tMapAngle( prevTheta, convex, height >= 0f ),\r\n\t\t\t\t\t\tMapAngle( theta, convex, height >= 0f ) );\r\n\t\t\t\t}\r\n\t\t\t\telse\r\n\t\t\t\t{\r\n\t\t\t\t\tBevel( (nextHeight - prevHeight) * width,\r\n\t\t\t\t\t\t(nextWidth - prevWidth) * height,\r\n\t\t\t\t\t\tMapAngle( prevTheta, convex, height >= 0f ),\r\n\t\t\t\t\t\tMapAngle( theta, convex, height >= 0f ) );\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t\telse\r\n\t\t\t{\r\n\t\t\t\tif ( height >= 0f == convex )\r\n\t\t\t\t{\r\n\t\t\t\t\tBevel( (nextWidth - prevWidth) * width,\r\n\t\t\t\t\t\t(nextHeight - prevHeight) * height );\r\n\t\t\t\t}\r\n\t\t\t\telse\r\n\t\t\t\t{\r\n\t\t\t\t\tBevel( (nextHeight - prevHeight) * width,\r\n\t\t\t\t\t\t(nextWidth - prevWidth) * height );\r\n\t\t\t\t}\r\n\t\t\t}\r\n\r\n\t\t\tprevWidth = nextWidth;\r\n\t\t\tprevHeight = nextHeight;\r\n\t\t\tprevTheta = theta;\r\n\t\t}\r\n\r\n\t\treturn this;\r\n\t}\r\n}\r\n"
},
{
"Ident": "facepunch.libpolygon",
"Path": "Code/PolygonMeshBuilder.Bevel.cs",
"FileName": "PolygonMeshBuilder.Bevel.cs",
"PackageType": "library",
"CodeKind": "Game",
"AssetVersionId": 55832,
"IsPrivate": false,
"Code": "using System;\r\nusing System.Collections.Generic;\r\nusing System.Linq;\r\n\r\nnamespace Sandbox.Polygons;\r\n\r\npartial class PolygonMeshBuilder\r\n{\r\n\tprivate HashSet<(int A, int B)> PossibleCuts { get; } = new();\r\n\r\n\t[ThreadStatic] private static List<(int A, int B)> Bevel_PossibleCutList;\r\n\r\n\t[ThreadStatic] private static List<int> Bevel_ActiveEdgeList;\r\n\r\n\r\n\t/// <summary>\r\n\t/// Add faces starting at each active edge, traveling inwards and upwards to produce a bevel.\r\n\t/// If the bevel distance is large enough the mesh will become closed. Otherwise, you can use\r\n\t/// <see cref=\"Close\"/> to add a flat face after the bevel.\r\n\t/// </summary>\r\n\t/// <param name=\"width\">Total distance inwards.</param>\r\n\t/// <param name=\"height\">Total distance upwards, away from the plane of the polygon.</param>\r\n\tpublic PolygonMeshBuilder Bevel( float width, float height )\r\n\t{\r\n\t\tvar angle = MathF.Atan2( width, height );\r\n\r\n\t\treturn Bevel( width, height, angle, angle );\r\n\t}\r\n\r\n\t/// <summary>\r\n\t/// Add faces starting at each active edge, traveling inwards and upwards to produce a bevel.\r\n\t/// Use <paramref name=\"prevAngle\"/> and <paramref name=\"nextAngle\"/> to control the normal directions\r\n\t/// at the start and end of the bevel faces. Angles are in radians, with 0 pointing outwards along\r\n\t/// the plane of the polygon, and PI/2 pointing upwards away from the plane.\r\n\t/// If the bevel distance is large enough the mesh will become closed. Otherwise, you can use\r\n\t/// <see cref=\"Close\"/> to add a flat face after the bevel.\r\n\t/// </summary>\r\n\t/// <param name=\"width\">Total distance inwards.</param>\r\n\t/// <param name=\"height\">Total distance upwards, away from the plane of the polygon.</param>\r\n\t/// <param name=\"prevAngle\">Angle, in radians, to use for normals at the outside of the bevel.</param>\r\n\t/// <param name=\"nextAngle\"></param>\r\n\tpublic PolygonMeshBuilder Bevel( float width, float height, float prevAngle, float nextAngle )\r\n\t{\r\n\t\tif ( width < 0f )\r\n\t\t{\r\n\t\t\tthrow new ArgumentOutOfRangeException( nameof( width ) );\r\n\t\t}\r\n\r\n\t\tValidate();\r\n\t\tBevel_UpdateExistingVertices( width, height, prevAngle, nextAngle );\r\n\r\n\t\tvar cutList = Bevel_PossibleCutList ??= new List<(int A, int B)>();\r\n\t\tvar edgeList = Bevel_ActiveEdgeList ??= new List<int>();\r\n\r\n\t\tvar finished = false;\r\n\t\tvar endDist = _nextDistance;\r\n\r\n\t\tif ( MathF.Abs( _nextDistance ) > 0.001f )\r\n\t\t{\r\n\t\t\tvar maxIterations = _activeEdges.Count * _activeEdges.Count;\r\n\r\n\t\t\tint iterations;\r\n\t\t\tfor ( iterations = 0; iterations < maxIterations && _activeEdges.Count > 0; ++iterations )\r\n\t\t\t{\r\n\t\t\t\tint? closedEdge = null;\r\n\t\t\t\tint? splitEdge = null;\r\n\t\t\t\tint? splittingEdge = null;\r\n\r\n\t\t\t\tVector2 bestPos = default;\r\n\r\n\t\t\t\tvar bestDist = _nextDistance;\r\n\t\t\t\tvar bestMerge = false;\r\n\r\n\t\t\t\tforeach ( var index in _activeEdges )\r\n\t\t\t\t{\r\n\t\t\t\t\tref var edge = ref _allEdges[index];\r\n\r\n\t\t\t\t\tif ( edge.MaxDistance >= bestDist ) continue;\r\n\r\n\t\t\t\t\tvar next = _allEdges[edge.NextEdge];\r\n\r\n\t\t\t\t\tbestDist = edge.MaxDistance;\r\n\t\t\t\t\tclosedEdge = edge.Index;\r\n\t\t\t\t\tbestPos = (edge.Project( edge.MaxDistance ) + next.Project( edge.MaxDistance )) * 0.5f;\r\n\t\t\t\t}\r\n\r\n\t\t\t\tcutList.Clear();\r\n\t\t\t\tcutList.AddRange( PossibleCuts );\r\n\r\n\t\t\t\tforeach ( var (index, otherIndex) in cutList )\r\n\t\t\t\t{\r\n\t\t\t\t\tif ( !_activeEdges.Contains( index ) || !_activeEdges.Contains( otherIndex ) )\r\n\t\t\t\t\t{\r\n\t\t\t\t\t\tPossibleCuts.Remove( (index, otherIndex) );\r\n\t\t\t\t\t\tcontinue;\r\n\t\t\t\t\t}\r\n\r\n\t\t\t\t\tvar edge = _allEdges[index];\r\n\t\t\t\t\tvar other = _allEdges[otherIndex];\r\n\r\n\t\t\t\t\tvar splitDist = CalculateSplitDistance( edge, other, _allEdges[other.NextEdge],\r\n\t\t\t\t\t\tout var splitPos, out var merge );\r\n\r\n\t\t\t\t\tif ( splitDist - _nextDistance > 0.001f )\r\n\t\t\t\t\t{\r\n\t\t\t\t\t\tPossibleCuts.Remove( (index, otherIndex) );\r\n\t\t\t\t\t\tcontinue;\r\n\t\t\t\t\t}\r\n\r\n\t\t\t\t\tif ( splitDist >= bestDist ) continue;\r\n\r\n\t\t\t\t\tbestDist = splitDist;\r\n\t\t\t\t\tbestPos = splitPos;\r\n\t\t\t\t\tbestMerge = merge;\r\n\r\n\t\t\t\t\tclosedEdge = null;\r\n\t\t\t\t\tsplitEdge = other.Index;\r\n\t\t\t\t\tsplittingEdge = edge.Index;\r\n\t\t\t\t}\r\n\r\n\t\t\t\tif ( splittingEdge != null && bestMerge )\r\n\t\t\t\t{\r\n\t\t\t\t\tBevel_Merge( splittingEdge.Value, splitEdge.Value, bestPos, bestDist );\r\n\t\t\t\t\tcontinue;\r\n\t\t\t\t}\r\n\r\n\t\t\t\tif ( splittingEdge != null )\r\n\t\t\t\t{\r\n\t\t\t\t\tBevel_Split( splittingEdge.Value, splitEdge.Value, bestPos, bestDist );\r\n\t\t\t\t\tcontinue;\r\n\t\t\t\t}\r\n\r\n\t\t\t\tif ( closedEdge != null )\r\n\t\t\t\t{\r\n\t\t\t\t\tBevel_Close( closedEdge.Value, bestPos, bestDist );\r\n\t\t\t\t\tcontinue;\r\n\t\t\t\t}\r\n\r\n\t\t\t\tfinished = true;\r\n\t\t\t\tbreak;\r\n\t\t\t}\r\n\r\n\t\t\tif ( _activeEdges.Count > 0 && iterations == maxIterations )\r\n\t\t\t{\r\n\t\t\t\tthrow new Exception( $\"Exploded after {iterations} with {_activeEdges.Count} active edges!\" );\r\n\t\t\t}\r\n\t\t}\r\n\t\telse\r\n\t\t{\r\n\t\t\tfinished = true;\r\n\t\t}\r\n\r\n\t\tif ( !finished && _activeEdges.Count > 0 )\r\n\t\t{\r\n\t\t\tendDist = _activeEdges.Max( i => _allEdges[i].Distance );\r\n\t\t}\r\n\r\n\t\tEnsureCapacity( _activeEdges.Count );\r\n\r\n\t\tedgeList.Clear();\r\n\t\tedgeList.AddRange( _activeEdges );\r\n\r\n\t\t_activeEdges.Clear();\r\n\r\n\t\tforeach ( var index in edgeList )\r\n\t\t{\r\n\t\t\tref var b = ref _allEdges[index];\r\n\t\t\tref var a = ref _allEdges[b.PrevEdge];\r\n\t\t\tref var c = ref _allEdges[b.NextEdge];\r\n\t\t\tref var d = ref _allEdges[AddEdge( b.Project( endDist ), b.Tangent, endDist )];\r\n\r\n\t\t\tvar ai = AddVertices( ref a );\r\n\t\t\tvar bi = AddVertices( ref b );\r\n\t\t\tvar ci = AddVertices( ref c );\r\n\r\n\t\t\tConnectEdges( ref a, ref d );\r\n\t\t\tConnectEdges( ref d, ref c );\r\n\r\n\t\t\tvar di = AddVertices( ref d, true );\r\n\r\n\t\t\tAddTriangle( ai.Next, di.Prev, bi.Prev );\r\n\t\t\tAddTriangle( bi.Next, di.Next, ci.Prev );\r\n\r\n\t\t\t_activeEdges.Add( d.Index );\r\n\t\t}\r\n\r\n\t\tPostBevel();\r\n\r\n\t\treturn this;\r\n\t}\r\n\r\n\tprivate void Bevel_UpdateExistingVertices( float width, float height, float prevAngle, float nextAngle )\r\n\t{\r\n\t\t_nextDistance = _prevDistance + width;\r\n\t\t_nextHeight = _prevHeight + height;\r\n\t\t_nextAngle = nextAngle;\r\n\t\t_minSmoothNormalDot = MathF.Cos( Math.Clamp( MaxSmoothAngle, 0f, MathF.PI * (511f / 512f) ) );\r\n\r\n\t\t_invDistance = width <= 0.0001f ? 0f : 1f / (_nextDistance - _prevDistance);\r\n\r\n\t\tif ( !SkipNormals && Math.Abs( _prevAngle - prevAngle ) >= 0.001f )\r\n\t\t{\r\n\t\t\tforeach ( var index in _activeEdges )\r\n\t\t\t{\r\n\t\t\t\tref var edge = ref _allEdges[index];\r\n\t\t\t\tedge.Vertices = (-1, -1);\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\t_prevAngle = prevAngle;\r\n\r\n\t\tPossibleCuts.Clear();\r\n\r\n\t\tforeach ( var index in _activeEdges )\r\n\t\t{\r\n\t\t\tref var edge = ref _allEdges[index];\r\n\t\t\tUpdateMaxDistance( ref edge, _allEdges[edge.NextEdge] );\r\n\r\n\t\t\tforeach ( var otherIndex in _activeEdges )\r\n\t\t\t{\r\n\t\t\t\tif ( otherIndex != index )\r\n\t\t\t\t{\r\n\t\t\t\t\tPossibleCuts.Add( (index, otherIndex) );\r\n\t\t\t\t}\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\r\n\tprivate void Bevel_Merge( int edgeA, int edgeB, Vector2 mergePos, float bestDist )\r\n\t{\r\n\t\tEnsureCapacity( 2 );\r\n\r\n\t\tref var a = ref _allEdges[edgeA];\r\n\t\tref var b = ref _allEdges[edgeB];\r\n\r\n\t\t_activeEdges.Remove( a.Index );\r\n\t\t_activeEdges.Remove( b.Index );\r\n\r\n\t\tif ( a.NextEdge == b.Index && b.NextEdge == a.Index )\r\n\t\t{\r\n\t\t\treturn;\r\n\t\t}\r\n\r\n\t\tref var aPrev = ref _allEdges[a.PrevEdge];\r\n\t\tref var bPrev = ref _allEdges[b.PrevEdge];\r\n\r\n\t\tref var aNext = ref _allEdges[a.NextEdge];\r\n\t\tref var bNext = ref _allEdges[b.NextEdge];\r\n\r\n\t\tref var aNew = ref _allEdges[AddEdge( mergePos, a.Tangent, bestDist, 1 )];\r\n\t\tref var bNew = ref _allEdges[AddEdge( mergePos, b.Tangent, bestDist, -1 )];\r\n\r\n\t\tvar aPrevi = AddVertices( ref aPrev ).Next;\r\n\t\tvar ai = AddVertices( ref a );\r\n\t\tvar aNexti = AddVertices( ref aNext ).Prev;\r\n\t\tvar bPrevi = AddVertices( ref bPrev ).Next;\r\n\t\tvar bi = AddVertices( ref b );\r\n\t\tvar bNexti = AddVertices( ref bNext ).Prev;\r\n\r\n\t\t_activeEdges.Add( aNew.Index );\r\n\t\t_activeEdges.Add( bNew.Index );\r\n\r\n\t\tConnectEdges( ref bPrev, ref aNew );\r\n\t\tConnectEdges( ref aNew, ref aNext );\r\n\r\n\t\tConnectEdges( ref aPrev, ref bNew );\r\n\t\tConnectEdges( ref bNew, ref bNext );\r\n\r\n\t\tUpdateMaxDistance( ref bPrev, aNew );\r\n\t\tUpdateMaxDistance( ref aNew, aNext );\r\n\t\tUpdateMaxDistance( ref aNext, _allEdges[aNext.NextEdge] );\r\n\r\n\t\tUpdateMaxDistance( ref aPrev, bNew );\r\n\t\tUpdateMaxDistance( ref bNew, bNext );\r\n\t\tUpdateMaxDistance( ref bNext, _allEdges[bNext.NextEdge] );\r\n\r\n\t\tvar aNewi = AddVertices( ref aNew );\r\n\t\tvar bNewi = AddVertices( ref bNew );\r\n\r\n\t\tAddTriangle( aPrevi, bNewi.Prev, ai.Prev );\r\n\t\tAddTriangle( ai.Next, aNewi.Next, aNexti );\r\n\t\tAddTriangle( bPrevi, aNewi.Prev, bi.Prev );\r\n\t\tAddTriangle( bi.Next, bNewi.Next, bNexti );\r\n\r\n\t\tAddAllPossibleCuts( aNew.Index );\r\n\t\tAddAllPossibleCuts( aNext.Index );\r\n\t\tAddAllPossibleCuts( bNew.Index );\r\n\t\tAddAllPossibleCuts( bNext.Index );\r\n\t}\r\n\r\n\tprivate void Bevel_Split( int splittingEdge, int splitEdge, Vector2 splitPos, float bestDist )\r\n\t{\r\n\t\tEnsureCapacity( 2 );\r\n\r\n\t\tref var a = ref _allEdges[splitEdge];\r\n\t\tref var d = ref _allEdges[splittingEdge];\r\n\t\tref var b = ref _allEdges[AddEdge( splitPos, a.Tangent, bestDist, 1 )];\r\n\t\tref var c = ref _allEdges[d.PrevEdge];\r\n\t\tref var e = ref _allEdges[AddEdge( splitPos, d.Tangent, bestDist, -1 )];\r\n\t\tref var aNext = ref _allEdges[a.NextEdge];\r\n\t\tref var dNext = ref _allEdges[d.NextEdge];\r\n\r\n\t\tvar ai = AddVertices( ref a ).Next;\r\n\t\tvar fi = AddVertices( ref aNext ).Prev;\r\n\t\tvar ci = AddVertices( ref c ).Next;\r\n\t\tvar di = AddVertices( ref d );\r\n\t\tvar gi = AddVertices( ref dNext ).Prev;\r\n\r\n\t\t_activeEdges.Remove( d.Index );\r\n\t\t_activeEdges.Add( b.Index );\r\n\t\t_activeEdges.Add( e.Index );\r\n\r\n\t\tConnectEdges( ref a, ref e );\r\n\t\tConnectEdges( ref e, ref dNext );\r\n\r\n\t\tConnectEdges( ref c, ref b );\r\n\t\tConnectEdges( ref b, ref aNext );\r\n\r\n\t\tUpdateMaxDistance( ref a, e );\r\n\t\tUpdateMaxDistance( ref e, dNext );\r\n\t\tUpdateMaxDistance( ref dNext, _allEdges[dNext.NextEdge] );\r\n\r\n\t\tUpdateMaxDistance( ref c, b );\r\n\t\tUpdateMaxDistance( ref b, aNext );\r\n\t\tUpdateMaxDistance( ref aNext, _allEdges[aNext.NextEdge] );\r\n\r\n\t\tvar bi = AddVertices( ref b );\r\n\t\tvar ei = AddVertices( ref e );\r\n\r\n\t\tAddTriangle( ai, bi.Next, fi );\r\n\t\tAddTriangle( ci, bi.Prev, di.Prev );\r\n\t\tAddTriangle( di.Next, ei.Next, gi );\r\n\r\n\t\tAddAllPossibleCuts( b.Index );\r\n\t\tAddAllPossibleCuts( dNext.Index );\r\n\t\tAddAllPossibleCuts( e.Index );\r\n\t\tAddAllPossibleCuts( aNext.Index );\r\n\t}\r\n\r\n\tprivate void Bevel_Close( int closedEdge, Vector2 closePos, float bestDist )\r\n\t{\r\n\t\tEnsureCapacity( 1 );\r\n\r\n\t\tref var b = ref _allEdges[closedEdge];\r\n\t\tref var a = ref _allEdges[b.PrevEdge];\r\n\t\tref var c = ref _allEdges[b.NextEdge];\r\n\t\tref var cNext = ref _allEdges[c.NextEdge];\r\n\t\tref var d = ref _allEdges[AddEdge( closePos, c.Tangent, bestDist )];\r\n\r\n\t\t_activeEdges.Remove( b.Index );\r\n\t\t_activeEdges.Remove( c.Index );\r\n\r\n\t\tif ( b.PrevEdge == b.NextEdge )\r\n\t\t{\r\n\t\t\treturn;\r\n\t\t}\r\n\r\n\t\t_activeEdges.Add( d.Index );\r\n\r\n\t\tConnectEdges( ref a, ref d );\r\n\t\tConnectEdges( ref d, ref cNext );\r\n\r\n\t\tUpdateMaxDistance( ref a, d );\r\n\t\tUpdateMaxDistance( ref d, cNext );\r\n\t\tUpdateMaxDistance( ref cNext, _allEdges[cNext.NextEdge] );\r\n\r\n\t\tvar ai = AddVertices( ref a );\r\n\t\tvar bi = AddVertices( ref b );\r\n\t\tvar ci = AddVertices( ref c );\r\n\t\tvar ei = AddVertices( ref cNext );\r\n\t\tvar di = AddVertices( ref d );\r\n\r\n\t\tvar fi = _vertices.Count;\r\n\r\n\t\t_vertices.Add( new(\r\n\t\t\t_vertices[di.Prev].Position,\r\n\t\t\t_vertices[bi.Next].Normal,\r\n\t\t\t_vertices[bi.Next].Tangent ) );\r\n\r\n\t\tAddTriangle( ai.Next, di.Prev, bi.Prev );\r\n\t\tAddTriangle( bi.Next, fi, ci.Prev );\r\n\t\tAddTriangle( ci.Next, di.Next, ei.Prev );\r\n\r\n\t\tAddAllPossibleCuts( d.Index );\r\n\t\tAddAllPossibleCuts( cNext.Index );\r\n\t}\r\n\r\n\tprivate void PostBevel()\r\n\t{\r\n\t\t_prevDistance = _nextDistance;\r\n\t\t_prevHeight = _nextHeight;\r\n\t\t_prevAngle = _nextAngle;\r\n\t}\r\n\r\n\tprivate void AddAllPossibleCuts( int index )\r\n\t{\r\n\t\tforeach ( var otherIndex in _activeEdges )\r\n\t\t{\r\n\t\t\tif ( otherIndex != index )\r\n\t\t\t{\r\n\t\t\t\tPossibleCuts.Add( (index, otherIndex) );\r\n\t\t\t\tPossibleCuts.Add( (otherIndex, index) );\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\r\n\tprivate static Vector3 RotateNormal( Vector3 oldNormal, float sin, float cos )\r\n\t{\r\n\t\tvar normal2d = new Vector2( oldNormal.x, oldNormal.y );\r\n\r\n\t\tif ( normal2d.LengthSquared <= 0.000001f )\r\n\t\t{\r\n\t\t\treturn oldNormal;\r\n\t\t}\r\n\r\n\t\tnormal2d = normal2d.Normal;\r\n\r\n\t\treturn new Vector3( normal2d.x * cos, normal2d.y * cos, sin ).Normal;\r\n\t}\r\n\r\n\tprivate static float GetEpsilon( Vector2 vec, float frac = 0.0001f )\r\n\t{\r\n\t\treturn Math.Max( Math.Abs( vec.x ), Math.Abs( vec.y ) ) * frac;\r\n\t}\r\n\r\n\tprivate static float GetEpsilon( Vector2 a, Vector2 b, float frac = 0.0001f )\r\n\t{\r\n\t\treturn Math.Max( GetEpsilon( a ), GetEpsilon( b ) );\r\n\t}\r\n\r\n\tprivate static void UpdateMaxDistance( ref Edge edge, in Edge nextEdge )\r\n\t{\r\n\t\tif ( edge.NextEdge == edge.PrevEdge )\r\n\t\t{\r\n\t\t\tedge.MaxDistance = edge.Distance;\r\n\t\t\treturn;\r\n\t\t}\r\n\r\n\t\tvar baseDistance = Math.Max( edge.Distance, nextEdge.Distance );\r\n\t\tvar thisOrigin = edge.Project( baseDistance );\r\n\t\tvar nextOrigin = nextEdge.Project( baseDistance );\r\n\r\n\t\tvar posDist = Vector2.Dot( nextOrigin - thisOrigin, edge.Tangent );\r\n\r\n\t\tvar dPrev = Vector2.Dot( edge.Velocity, edge.Tangent );\r\n\t\tvar dNext = Vector2.Dot( nextEdge.Velocity, edge.Tangent );\r\n\r\n\t\tif ( dPrev - dNext <= 0.001f )\r\n\t\t{\r\n\t\t\tvar epsilon = GetEpsilon( thisOrigin, nextOrigin, 0.001f );\r\n\t\t\tedge.MaxDistance = posDist <= epsilon ? baseDistance : float.PositiveInfinity;\r\n\t\t}\r\n\t\telse\r\n\t\t{\r\n\t\t\tedge.MaxDistance = baseDistance + MathF.Max( 0f, posDist / (dPrev - dNext) );\r\n\t\t}\r\n\t}\r\n\r\n\tprivate static void SimpleConnectEdges( ref Edge prev, ref Edge next )\r\n\t{\r\n\t\tprev.NextEdge = next.Index;\r\n\t\tnext.PrevEdge = prev.Index;\r\n\t}\r\n\r\n\tprivate static void ConnectEdges( ref Edge prev, ref Edge next )\r\n\t{\r\n\t\tSimpleConnectEdges( ref prev, ref next );\r\n\r\n\t\tvar sum = prev.Normal + next.Normal;\r\n\t\tvar sqrMag = sum.LengthSquared;\r\n\r\n\t\tif ( sqrMag < 0.001f )\r\n\t\t{\r\n\t\t\tnext.Velocity = Vector2.Zero;\r\n\t\t}\r\n\t\telse\r\n\t\t{\r\n\t\t\tnext.Velocity = 2f * sum / sum.LengthSquared;\r\n\t\t}\r\n\t}\r\n\r\n\tprivate static float CalculateSplitDistance( in Edge edge, in Edge other, in Edge otherNext,\r\n\t\tout Vector2 splitPos, out bool merge )\r\n\t{\r\n\t\tsplitPos = default;\r\n\t\tmerge = false;\r\n\r\n\t\tif ( other.Index == edge.Index || edge.Twin == other.Index || edge.Velocity.LengthSquared <= 0f )\r\n\t\t{\r\n\t\t\treturn float.PositiveInfinity;\r\n\t\t}\r\n\r\n\t\tvar dv = Vector2.Dot( other.Velocity - edge.Velocity, other.Normal );\r\n\r\n\t\tif ( dv <= GetEpsilon( edge.Velocity, other.Velocity ) )\r\n\t\t{\r\n\t\t\treturn float.PositiveInfinity;\r\n\t\t}\r\n\r\n\t\tvar baseDistance = Math.Max( edge.Distance, Math.Max( other.Distance, otherNext.Distance ) );\r\n\t\tvar thisOrigin = edge.Project( baseDistance );\r\n\t\tvar edgeOrigin = other.Project( baseDistance );\r\n\r\n\t\tvar dx = Vector2.Dot( thisOrigin - edgeOrigin, other.Normal );\r\n\r\n\t\tif ( dx <= -GetEpsilon( thisOrigin, edgeOrigin ) )\r\n\t\t{\r\n\t\t\treturn float.PositiveInfinity;\r\n\t\t}\r\n\r\n\t\tvar t = dx / dv;\r\n\r\n\t\tif ( t <= -0.0001f )\r\n\t\t{\r\n\t\t\treturn float.PositiveInfinity;\r\n\t\t}\r\n\r\n\t\tif ( baseDistance + t >= edge.MaxDistance || baseDistance + t >= other.MaxDistance )\r\n\t\t{\r\n\t\t\treturn float.PositiveInfinity;\r\n\t\t}\r\n\r\n\t\tsplitPos = thisOrigin + edge.Velocity * t;\r\n\r\n\t\tvar prevPos = edgeOrigin + other.Velocity * t;\r\n\t\tvar nextPos = otherNext.Project( baseDistance + t );\r\n\r\n\t\tvar dPrev = Vector2.Dot( splitPos - prevPos, other.Tangent );\r\n\t\tvar dNext = Vector2.Dot( splitPos - nextPos, other.Tangent );\r\n\r\n\t\tvar epsilon = GetEpsilon( prevPos, nextPos );\r\n\r\n\t\tif ( dPrev <= -epsilon || dNext >= -epsilon )\r\n\t\t{\r\n\t\t\treturn float.PositiveInfinity;\r\n\t\t}\r\n\r\n\t\tif ( dPrev <= epsilon )\r\n\t\t{\r\n\t\t\tif ( edge.NextEdge == other.Index || edge.PrevEdge == other.Index )\r\n\t\t\t{\r\n\t\t\t\treturn float.PositiveInfinity;\r\n\t\t\t}\r\n\r\n\t\t\tmerge = true;\r\n\t\t}\r\n\r\n\t\treturn baseDistance + Math.Max( 0f, t );\r\n\t}\r\n}\r\n"
},
{
"Ident": "facepunch.libpolygon",
"Path": "Code/PolygonMeshBuilder.SVG.cs",
"FileName": "PolygonMeshBuilder.SVG.cs",
"PackageType": "library",
"CodeKind": "Game",
"AssetVersionId": 55832,
"IsPrivate": false,
"Code": "using System;\r\nusing System.Collections.Generic;\r\nusing System.IO;\r\nusing System.Linq;\r\nusing Sandbox.Utility.Svg;\r\n\r\nnamespace Sandbox.Polygons;\r\n\r\n/// <summary>\r\n/// Options for <see cref=\"PolygonMeshBuilder.AddSvg\"/>.\r\n/// </summary>\r\npublic class AddSvgOptions\r\n{\r\n\tpublic static AddSvgOptions Default { get; } = new();\r\n\r\n\t/// <summary>\r\n\t/// If true, any unsupported path types will throw an exception. Defaults to false.\r\n\t/// </summary>\r\n\tpublic bool ThrowIfNotSupported { get; set; }\r\n\r\n\t/// <summary>\r\n\t/// Maximum distance between vertices on curved paths. Defaults to 1.\r\n\t/// </summary>\r\n\tpublic float CurveResolution { get; set; } = 1f;\r\n\r\n public bool KeepAspectRatio { get; set; } = true;\r\n}\r\n\r\npartial class PolygonMeshBuilder\r\n{\r\n\t/// <summary>\r\n\t/// Add all supported paths from the given SVG document.\r\n\t/// </summary>\r\n\t/// <param name=\"contents\">SVG document contents.</param>\r\n\t/// <param name=\"options\">Options for generating vertices from paths.</param>\r\n\t/// <param name=\"targetBounds\">Rescale and translate the imported SVG to fill the given bounds</param>\r\n\tpublic PolygonMeshBuilder AddSvg( string contents, AddSvgOptions options = null, Rect? targetBounds = null )\r\n {\r\n options ??= AddSvgOptions.Default;\r\n\r\n var svg = SvgDocument.FromString( contents );\r\n\r\n\t\tif ( svg.Paths.Count == 0 )\r\n\t\t{\r\n\t\t\treturn this;\r\n\t\t}\r\n\r\n\t\tif ( targetBounds == null )\r\n\t\t{\r\n\t\t\tforeach ( var path in svg.Paths )\r\n\t\t\t{\r\n\t\t\t\tAddPath( path, options );\r\n\t\t\t}\r\n\r\n\t\t\treturn this;\r\n\t\t}\r\n\r\n\t\tvar bounds = svg.Paths[0].Bounds;\r\n\r\n\t\tforeach ( var path in svg.Paths )\r\n\t\t{\r\n\t\t\tbounds.Add( path.Bounds );\r\n\t\t}\r\n\r\n\t\tvar scale = targetBounds.Value.Size / bounds.Size;\r\n var aspectOffset = Vector2.Zero;\r\n\r\n if ( options.KeepAspectRatio )\r\n {\r\n var oldScale = scale;\r\n\r\n scale = Math.Min( scale.x, scale.y );\r\n aspectOffset = (oldScale - scale) * targetBounds.Value.Size * 0.25f;\r\n }\r\n\r\n\t\tvar offset = targetBounds.Value.Position - bounds.Position * scale + aspectOffset;\r\n\r\n\t\tforeach ( var path in svg.Paths )\r\n\t\t{\r\n\t\t\tAddPath( path, options, offset, scale );\r\n\t\t}\r\n\r\n\t\treturn this;\r\n\t}\r\n\r\n\tprivate static void ThrowNotSupported( AddSvgOptions options, string message )\r\n\t{\r\n\t\tif ( !options.ThrowIfNotSupported )\r\n\t\t{\r\n\t\t\treturn;\r\n\t\t}\r\n\r\n\t\tthrow new NotImplementedException( $\"SVG path element not supported: {message}\" );\r\n\t}\r\n\r\n\t/// <summary>\r\n\t/// Add an individual path from an SVG document, if supported.\r\n\t/// </summary>\r\n\t/// <param name=\"path\">SVG path element.</param>\r\n\t/// <param name=\"options\">Options for generating vertices from paths.</param>\r\n\t/// <param name=\"targetBounds\">Rescale and translate the imported SVG to fill the given bounds</param>\r\n\tpublic PolygonMeshBuilder AddPath( SvgPath path, AddSvgOptions options = null )\r\n\t{\r\n\t\toptions ??= AddSvgOptions.Default;\r\n\t\treturn AddPath( path, options, Vector2.Zero, Vector2.One );\r\n\t}\r\n\r\n\tprivate PolygonMeshBuilder AddPath( SvgPath path, AddSvgOptions options, Vector2 offset, Vector2 scale )\r\n\t{\r\n\t\tif ( path.IsEmpty )\r\n\t\t{\r\n\t\t\treturn this;\r\n\t\t}\r\n\r\n\t\tif ( path.FillColor == null )\r\n\t\t{\r\n\t\t\treturn this;\r\n\t\t}\r\n\r\n\t\tif ( path.FillType != PathFillType.Winding )\r\n\t\t{\r\n\t\t\tif ( options.ThrowIfNotSupported )\r\n\t\t\t{\r\n\t\t\t\t//throw new NotImplementedException( \"Only fill-type: winding is supported.\" );\r\n\t\t\t}\r\n\r\n\t\t\t//return this;\r\n\t\t}\r\n\r\n\t\tvar openPath = new List<Vector2>();\r\n\t\tvar last = Vector2.Zero;\r\n\r\n\t\tforeach ( var cmd in path.Commands )\r\n\t\t{\r\n\t\t\tswitch ( cmd )\r\n\t\t\t{\r\n\t\t\t\tcase AddPolyPathCommand addPolyPathCommand:\r\n\t\t\t\t\tAddPolyPath( addPolyPathCommand, options, offset, scale );\r\n\t\t\t\t\tbreak;\r\n\r\n\t\t\t\tcase AddCirclePathCommand addCirclePathCommand:\r\n\t\t\t\t\tAddCirclePath( addCirclePathCommand, options, openPath, offset, scale );\r\n\t\t\t\t\tbreak;\r\n\r\n\t\t\t\tcase MoveToPathCommand moveToPathCommand:\r\n\t\t\t\t\topenPath.Clear();\r\n\t\t\t\t\topenPath.Add( new Vector2( moveToPathCommand.X, moveToPathCommand.Y ) );\r\n\t\t\t\t\tbreak;\r\n\r\n\t\t\t\tcase LineToPathCommand lineToPathCommand:\r\n\t\t\t\t\topenPath.Add( new Vector2( lineToPathCommand.X, lineToPathCommand.Y ) );\r\n\t\t\t\t\tbreak;\r\n\r\n\t\t\t\tcase CubicToPathCommand cubicToPathCommand:\r\n\t\t\t\t\tCubicToPath( cubicToPathCommand, options, openPath, last );\r\n\t\t\t\t\tbreak;\r\n\r\n\t\t\t\tcase ClosePathCommand:\r\n\t\t\t\t\tif ( openPath.Count >= 3 )\r\n\t\t\t\t\t{\r\n\t\t\t\t\t\tAddEdgeLoop( openPath, 0, openPath.Count, offset, scale );\r\n\t\t\t\t\t}\r\n\r\n\t\t\t\t\topenPath.Clear();\r\n\t\t\t\t\tbreak;\r\n\r\n\t\t\t\tdefault:\r\n\t\t\t\t\tThrowNotSupported( options, $\"{cmd.GetType()}\" );\r\n\t\t\t\t\tbreak;\r\n\t\t\t}\r\n\r\n\t\t\tif ( openPath.Count > 0 )\r\n\t\t\t{\r\n\t\t\t\tlast = openPath[^1];\r\n\t\t\t}\r\n\t\t}\r\n\r\n\t\treturn this;\r\n\t}\r\n\r\n\tprivate void AddPolyPath( AddPolyPathCommand cmd, AddSvgOptions options, Vector2 offset, Vector2 scale )\r\n\t{\r\n\t\tif ( !cmd.Close )\r\n\t\t{\r\n\t\t\treturn;\r\n\t\t}\r\n\r\n\t\tAddEdgeLoop( cmd.Points, 0, cmd.Points.Count, offset, scale );\r\n\t}\r\n\r\n\tprivate void AddCirclePath( AddCirclePathCommand cmd, AddSvgOptions options, List<Vector2> openPath, Vector2 offset, Vector2 scale )\r\n\t{\r\n\t\topenPath.Clear();\r\n\r\n\t\tvar center = new Vector2( cmd.X, cmd.Y );\r\n\r\n\t\tfor ( var i = 23; i >= 0; i-- )\r\n\t\t{\r\n\t\t\tvar r = i * (MathF.PI * 2f / 24f);\r\n\r\n\t\t\tvar cos = MathF.Cos( r );\r\n\t\t\tvar sin = MathF.Sin( r );\r\n\r\n\t\t\topenPath.Add( new Vector2( cos, sin ) * cmd.Radius + center );\r\n\t\t}\r\n\r\n\t\tAddEdgeLoop( openPath, 0, openPath.Count, offset, scale );\r\n\t}\r\n\r\n\tprivate void CubicToPath( CubicToPathCommand cmd, AddSvgOptions options, List<Vector2> openPath, Vector2 last )\r\n\t{\r\n\t\tvar pointCount = 6;\r\n\t\tvar tScale = 1f / pointCount;\r\n\r\n\t\tfor ( var i = 0; i < pointCount; i++ )\r\n\t\t{\r\n\t\t\tvar t = (i + 1) * tScale;\r\n\t\t\tvar s = 1f - t;\r\n\r\n\t\t\tvar a = s * s * s;\r\n\t\t\tvar b = 3f * s * s * t;\r\n\t\t\tvar c = 3f * s * t * t;\r\n\t\t\tvar d = t * t * t;\r\n\r\n\t\t\tvar p0 = last;\r\n\t\t\tvar p1 = new Vector2( cmd.X0, cmd.Y0 );\r\n\t\t\tvar p2 = new Vector2( cmd.X1, cmd.Y1 );\r\n\t\t\tvar p3 = new Vector2( cmd.X2, cmd.Y2 );\r\n\r\n\t\t\topenPath.Add( p0 * a + p1 * b + p2 * c + p3 * d );\r\n\t\t}\r\n\t}\r\n\r\n\tpublic string ToSvg()\r\n\t{\r\n\t\tvar openEdges = new HashSet<int>( _activeEdges );\r\n\t\tvar writer = new StringWriter();\r\n\r\n\t\twriter.WriteLine( \"<svg xmlns=\\\"http://www.w3.org/2000/svg\\\">\" );\r\n\r\n\t\twhile ( openEdges.Count > 0 )\r\n\t\t{\r\n\t\t\tvar firstIndex = openEdges.First();\r\n\r\n\t\t\tvar edge = _allEdges[firstIndex];\r\n\r\n\t\t\twriter.Write( \" <polygon points=\\\"\" );\r\n\r\n\t\t\twhile ( true )\r\n\t\t\t{\r\n\t\t\t\twriter.Write( $\"{edge.Origin.x:R},{edge.Origin.y:R} \" );\r\n\t\t\t\topenEdges.Remove( edge.Index );\r\n\r\n\t\t\t\tif ( edge.NextEdge == firstIndex )\r\n\t\t\t\t{\r\n\t\t\t\t\tbreak;\r\n\t\t\t\t}\r\n\r\n\t\t\t\tedge = _allEdges[edge.NextEdge];\r\n\t\t\t}\r\n\r\n\t\t\twriter.WriteLine(\"\\\" fill=\\\"black\\\" stroke=\\\"red\\\" />\");\r\n\t\t}\r\n\r\n\t\twriter.WriteLine( @\"</svg>\" );\r\n\r\n\t\treturn writer.ToString();\r\n\t}\r\n}\r\n"
},
{
"Ident": "facepunch.libpolygon",
"Path": "Code/Pooled.cs",
"FileName": "Pooled.cs",
"PackageType": "library",
"CodeKind": "Game",
"AssetVersionId": 55832,
"IsPrivate": false,
"Code": "using System;\r\nusing System.Collections.Generic;\r\n\r\nnamespace Sandbox.Polygons;\r\n\r\npublic abstract class Pooled<T> : IDisposable\r\n where T : Pooled<T>, new()\r\n{\r\n#pragma warning disable SB3000\r\n private const int MaxPoolCount = 64;\r\n private static List<T> Pool { get; } = new();\r\n#pragma warning restore SB3000\r\n\r\n public static T Rent()\r\n {\r\n lock ( Pool )\r\n {\r\n if ( Pool.Count <= 0 ) return new T();\r\n\r\n var writer = Pool[^1];\r\n Pool.RemoveAt( Pool.Count - 1 );\r\n\r\n writer._isInPool = false;\r\n writer.Reset();\r\n\r\n return writer;\r\n }\r\n }\r\n\r\n public void Return()\r\n {\r\n lock ( Pool )\r\n {\r\n if ( _isInPool ) throw new InvalidOperationException( \"Already returned.\" );\r\n\r\n Reset();\r\n\r\n _isInPool = true;\r\n\r\n if ( Pool.Count < MaxPoolCount ) Pool.Add( (T) this );\r\n }\r\n }\r\n\r\n private bool _isInPool;\r\n\r\n public abstract void Reset();\r\n\r\n public void Dispose()\r\n {\r\n Return();\r\n }\r\n}\r\n"
}
]
}