using Unity.Collections;
using Unity.Mathematics;
using Unity.Collections.LowLevel.Unsafe;
namespace UnityEngine.U2D.Common.UTess
{
// Ensures that there are no duplicate Points, Overlapping Edges.
struct PlanarGraph
{
private static readonly double kEpsilon = 0.00001;
private static readonly int kMaxIntersectionTolerance = 4; // Maximum Intersection Tolerance per Intersection Loop Check.
internal static void RemoveDuplicateEdges(ref Array<int2> edges, ref int edgeCount, Array<int> duplicates, int duplicateCount)
{
if (duplicateCount == 0)
{
for (var i = 0; i < edgeCount; ++i)
{
var e = edges[i];
e.x = math.min(edges[i].x, edges[i].y);
e.y = math.max(edges[i].x, edges[i].y);
edges[i] = e;
}
}
else
{
for (var i = 0; i < edgeCount; ++i)
{
var e = edges[i];
var a = duplicates[e.x];
var b = duplicates[e.y];
e.x = math.min(a, b);
e.y = math.max(a, b);
edges[i] = e;
}
}
unsafe
{
ModuleHandle.InsertionSort<int2, TessEdgeCompare>(edges.UnsafePtr, 0, edgeCount - 1,new TessEdgeCompare());
}
var n = 1;
for (var i = 1; i < edgeCount; ++i)
{
var prev = edges[i - 1];
var next = edges[i];
if (next.x == prev.x && next.y == prev.y)
continue;
if (next.x == next.y)
continue;
edges[n++] = next;
}
edgeCount = n;
}
internal static bool CheckCollinear(double2 a0, double2 a1, double2 b0, double2 b1)
{
double2 a = a0;
double2 b = a1;
double2 c = b0;
double2 d = b1;
double x = (b.y - a.y) / (b.x - a.x);
double y = (c.y - a.y) / (c.x - a.x);
double z = (d.y - a.y) / (d.x - a.x);
return ((!math.isinf(x) || !math.isinf(y) || !math.isinf(z)) && math.abs(x - y) > kEpsilon && math.abs(x - z) > kEpsilon);
}
internal static bool LineLineIntersection(double2 a0, double2 a1, double2 b0, double2 b1)
{
var x0 = ModuleHandle.OrientFastDouble(a0, b0, b1);
var y0 = ModuleHandle.OrientFastDouble(a1, b0, b1);
if ((x0 > kEpsilon && y0 > kEpsilon) || (x0 < -kEpsilon && y0 < -kEpsilon))
{
return false;
}
var x1 = ModuleHandle.OrientFastDouble(b0, a0, a1);
var y1 = ModuleHandle.OrientFastDouble(b1, a0, a1);
if ((x1 > kEpsilon && y1 > kEpsilon) || (x1 < -kEpsilon && y1 < -kEpsilon))
{
return false;
}
// Check for degenerate collinear case
if (math.abs(x0) < kEpsilon && math.abs(y0) < kEpsilon && math.abs(x1) < kEpsilon && math.abs(y1) < kEpsilon)
{
return CheckCollinear(a0, a1, b0, b1);
}
return true;
}
internal static bool LineLineIntersection(double2 p1, double2 p2, double2 p3, double2 p4, ref double2 result)
{
double bx = p2.x - p1.x;
double by = p2.y - p1.y;
double dx = p4.x - p3.x;
double dy = p4.y - p3.y;
double bDotDPerp = bx * dy - by * dx;
if (math.abs(bDotDPerp) < kEpsilon)
{
return false;
}
double cx = p3.x - p1.x;
double cy = p3.y - p1.y;
double t = (cx * dy - cy * dx) / bDotDPerp;
if ((t >= -kEpsilon) && (t <= 1.0f + kEpsilon))
{
result.x = p1.x + t * bx;
result.y = p1.y + t * by;
return true;
}
return false;
}
internal static bool CalculateEdgeIntersections(Array<int2> edges, int edgeCount, Array<double2> points, int pointCount, ref Array<int2> results, ref Array<double2> intersects, ref int resultCount)
{
resultCount = 0;
for (int i = 0; i < edgeCount; ++i)
{
for (int j = i + 1; j < edgeCount; ++j)
{
var e = edges[i];
var f = edges[j];
if (e.x == f.x || e.x == f.y || e.y == f.x || e.y == f.y)
continue;
var a = points[e.x];
var b = points[e.y];
var c = points[f.x];
var d = points[f.y];
var g = double2.zero;
if (LineLineIntersection(a, b, c, d))
{
if (LineLineIntersection(a, b, c, d, ref g))
{
// Until we ensure Outline is generated properly, we need this useless Check every correction.
if (resultCount >= intersects.Length)
return false;
intersects[resultCount] = g;
results[resultCount++] = new int2(i, j);
}
}
}
}
// Basically we have self intersections all over (eg. gobo_tree_04). Better don't generate any Mesh as even though this will eventually succeed, error correction will take long time.
if (resultCount > (edgeCount * kMaxIntersectionTolerance))
{
return false;
}
var tjc = new IntersectionCompare();
tjc.edges = edges;
tjc.points = points;
unsafe
{
ModuleHandle.InsertionSort<int2, IntersectionCompare>(results.UnsafePtr, 0, resultCount - 1, tjc);
}
return true;
}
internal static bool CalculateTJunctions(Array<int2> edges, int edgeCount, Array<double2> points, int pointCount, Array<int2> results, ref int resultCount)
{
resultCount = 0;
for (int i = 0; i < edgeCount; ++i)
{
for (int j = 0; j < pointCount; ++j)
{
var e = edges[i];
if (e.x == j || e.y == j)
continue;
var a = points[e.x];
var b = points[e.y];
var c = points[j];
var d = points[j];
if (LineLineIntersection(a, b, c, d))
{
// Until we ensure Outline is generated properly, we need this useless Check every correction.
if (resultCount >= results.Length)
return false;
results[resultCount++] = new int2(i, j);
}
}
}
return true;
}
internal static bool CutEdges(ref Array<double2> points, ref int pointCount, ref Array<int2> edges, ref int edgeCount, ref Array<int2> tJunctions, ref int tJunctionCount, Array<int2> intersections, Array<double2> intersects, int intersectionCount)
{
for (int i = 0; i < intersectionCount; ++i)
{
var intr = intersections[i];
var e = intr.x;
var f = intr.y;
int2 j1 = int2.zero;
j1.x = e;
j1.y = pointCount;
tJunctions[tJunctionCount++] = j1;
int2 j2 = int2.zero;
j2.x = f;
j2.y = pointCount;
tJunctions[tJunctionCount++] = j2;
// Until we ensure Outline is generated properly, we need this useless Check every correction.
if (pointCount >= points.Length)
return false;
points[pointCount++] = intersects[i];
}
unsafe
{
ModuleHandle.InsertionSort<int2, TessJunctionCompare>( tJunctions.UnsafePtr, 0, tJunctionCount - 1, new TessJunctionCompare());
}
// Split edges along junctions
for (int i = tJunctionCount - 1; i >= 0; --i)
{
var tJunction = tJunctions[i];
var e = tJunction.x;
var edge = edges[e];
var s = edge.x;
var t = edge.y;
// Check if edge is not lexicographically sorted
var a = points[s];
var b = points[t];
if (((a.x - b.x) < 0) || (a.x == b.x && (a.y - b.y) < 0))
{
var tmp = s;
s = t;
t = tmp;
}
// Split leading edge
edge.x = s;
var last = edge.y = tJunction.y;
edges[e] = edge;
// If we are grouping edges by color, remember to track data
// Split other edges
while (i > 0 && tJunctions[i - 1].x == e)
{
var next = tJunctions[--i].y;
int2 te = new int2();
te.x = last;
te.y = next;
edges[edgeCount++] = te;
last = next;
}
int2 le = new int2();
le.x = last;
le.y = t;
edges[edgeCount++] = le;
}
return true;
}
internal static void RemoveDuplicatePoints(ref Array<double2> points, ref int pointCount, ref Array<int> duplicates, ref int duplicateCount, Allocator allocator)
{
TessLink link = TessLink.CreateLink(pointCount, allocator);
for (int i = 0; i < pointCount; ++i)
{
for (int j = i + 1; j < pointCount; ++j)
{
if (math.distance(points[i], points[j]) < kEpsilon)
{
link.Link(i, j);
}
}
}
duplicateCount = 0;
for (var i = 0; i < pointCount; ++i)
{
var j = link.Find(i);
if (j != i)
{
duplicateCount++;
points[j] = math.min(points[i], points[j]);
}
}
// Find Duplicates.
if (duplicateCount != 0)
{
var prevPointCount = pointCount;
pointCount = 0;
for (var i = 0; i < prevPointCount; ++i)
{
var j = link.Find(i);
if (j == i)
{
duplicates[i] = pointCount;
points[pointCount++] = points[i];
}
else
{
duplicates[i] = -1;
}
}
// Update Duplicates.
for (int i = 0; i < prevPointCount; ++i)
{
if (duplicates[i] < 0)
{
duplicates[i] = duplicates[link.Find(i)];
}
}
}
TessLink.DestroyLink(link);
}
// Validate the Input Points ane Edges.
internal static bool Validate(Allocator allocator, in NativeArray<float2> inputPoints, int pointCount, in NativeArray<int2> inputEdges, int edgeCount, ref NativeArray<float2> outputPoints, out int outputPointCount, ref NativeArray<int2> outputEdges, out int outputEdgeCount)
{
outputPointCount = 0;
outputEdgeCount = 0;
// Outline generated inputs can have differences in the range of 0.00001f.. See TwoLayers.psb sample.
// Since PlanarGraph operates on double, scaling up and down does not result in loss of data.
var precisionFudge = 10000.0f;
var protectLoop = edgeCount;
var requiresFix = true;
var validGraph = false;
// Processing Arrays.
int startEdgeCount = edgeCount;
Array<int> duplicates = new Array<int>(startEdgeCount, ModuleHandle.kMaxEdgeCount, allocator, NativeArrayOptions.UninitializedMemory);
Array<int2> edges = new Array<int2>(startEdgeCount, ModuleHandle.kMaxEdgeCount, allocator, NativeArrayOptions.UninitializedMemory);
Array<int2> tJunctions = new Array<int2>(startEdgeCount, ModuleHandle.kMaxEdgeCount, allocator, NativeArrayOptions.UninitializedMemory);
Array<int2> edgeIntersections = new Array<int2>(startEdgeCount, ModuleHandle.kMaxEdgeCount, allocator, NativeArrayOptions.UninitializedMemory);
Array<double2> points = new Array<double2>(pointCount * 2, pointCount * 8, allocator, NativeArrayOptions.UninitializedMemory);
Array<double2> intersects = new Array<double2>(pointCount * 2, pointCount * 8, allocator, NativeArrayOptions.UninitializedMemory);
// Initialize.
for (int i = 0; i < pointCount; ++i)
points[i] = inputPoints[i] * precisionFudge;
unsafe
{
UnsafeUtility.MemCpy(edges.UnsafeReadOnlyPtr, inputEdges.GetUnsafePtr(), edgeCount * sizeof(int2));
}
// Pre-clear duplicates, otherwise the following will simply fail.
RemoveDuplicateEdges(ref edges, ref edgeCount, duplicates, 0);
// While PSG is clean.
while (requiresFix && --protectLoop > 0)
{
// Edge Edge Intersection.
int intersectionCount = 0;
validGraph = CalculateEdgeIntersections(edges, edgeCount, points, pointCount, ref edgeIntersections, ref intersects, ref intersectionCount);
if (!validGraph)
break;
// Edge Point Intersection. T-Junction.
int tJunctionCount = 0;
validGraph = CalculateTJunctions(edges, edgeCount, points, pointCount, tJunctions, ref tJunctionCount);
if (!validGraph)
break;
// Cut Overlapping Edges.
validGraph = CutEdges(ref points, ref pointCount, ref edges, ref edgeCount, ref tJunctions, ref tJunctionCount, edgeIntersections, intersects, intersectionCount);
if (!validGraph)
break;
// Remove Duplicate Points.
int duplicateCount = 0;
RemoveDuplicatePoints(ref points, ref pointCount, ref duplicates, ref duplicateCount, allocator);
RemoveDuplicateEdges(ref edges, ref edgeCount, duplicates, duplicateCount);
requiresFix = intersectionCount != 0 || tJunctionCount != 0;
}
if (validGraph)
{
// Finalize Output.
outputEdgeCount = edgeCount;
outputPointCount = pointCount;
unsafe
{
UnsafeUtility.MemCpy(outputEdges.GetUnsafePtr(), edges.UnsafeReadOnlyPtr, edgeCount * sizeof(int2));
}
for (int i = 0; i < pointCount; ++i)
outputPoints[i] = new float2((float)(points[i].x / precisionFudge), (float)(points[i].y / precisionFudge));
}
edges.Dispose();
points.Dispose();
intersects.Dispose();
duplicates.Dispose();
tJunctions.Dispose();
edgeIntersections.Dispose();
return (validGraph && protectLoop > 0);
}
}
}