| | | 1 | | //======================================================================= |
| | | 2 | | // MeshJoinedSurfaceRegions.cs |
| | | 3 | | //======================================================================= |
| | | 4 | | // MIT License, Copyright (c) 2026-present David Oravsky (mrdav30) |
| | | 5 | | // See LICENSE file in the project root for full license information. |
| | | 6 | | //======================================================================= |
| | | 7 | | |
| | | 8 | | using System; |
| | | 9 | | using System.Collections.Generic; |
| | | 10 | | using FixedMathSharp; |
| | | 11 | | using FixedMathSharp.Geometry; |
| | | 12 | | using Gravitas.Colliders; |
| | | 13 | | using SwiftCollections; |
| | | 14 | | |
| | | 15 | | namespace Gravitas.CollisionHandling; |
| | | 16 | | |
| | | 17 | | /// <summary>Shared source ownership and graph of exactly admitted joined surface regions.</summary> |
| | | 18 | | internal partial class MeshJoinedSurfaceRegions<TFrame> where TFrame : struct |
| | | 19 | | { |
| | 463 | 20 | | internal readonly SwiftList<(LSMeshCollider Collider, int Triangle)> Inputs = new(); |
| | 463 | 21 | | internal readonly SwiftList<PhysicsMesh> Meshes = new(); |
| | 463 | 22 | | internal readonly SwiftList<int> Candidates = new(); |
| | 463 | 23 | | internal readonly SwiftList<MeshSurfaceBoundaryDomain> PreparedBoundaries = new(); |
| | 463 | 24 | | internal readonly MeshSurfaceBoundaryFan Fan = new(); |
| | 463 | 25 | | internal readonly SwiftDictionary<(PhysicsMesh Mesh, int Owner), int> MemberBySurface = new(); |
| | 463 | 26 | | internal readonly SwiftList<Member<TFrame>> Members = new(); |
| | 1852 | 27 | | internal readonly SwiftList<int> Parents = new(), Roots = new(), RegionByRoot = new(), NodeMembers = new(); |
| | 926 | 28 | | private int[] _responseComponents = Array.Empty<int>(), _responseMembers = Array.Empty<int>(); |
| | 463 | 29 | | private readonly IComparer<(LSMeshCollider Collider, int Triangle)> _memberComparer = |
| | 463 | 30 | | Comparer<(LSMeshCollider Collider, int Triangle)>.Create(static (a, b) => |
| | 463 | 31 | | { |
| | 463 | 32 | | int order = ((IPhysicsColliderRegistryItem)a.Collider).ReplayOrder.CompareTo(((IPhysicsColliderRegistryItem) |
| | 463 | 33 | | return order != 0 ? order : a.Triangle.CompareTo(b.Triangle); |
| | 463 | 34 | | }); |
| | 463 | 35 | | internal int PreparedCount = -1; |
| | | 36 | | internal bool Active; |
| | | 37 | | |
| | | 38 | | internal void Prepare(ReadOnlySpan<(LSMeshCollider Collider, int Triangle)> surfaces, |
| | | 39 | | ReadOnlySpan<PhysicsMesh> preparedMeshes, |
| | | 40 | | SwiftDictionary<(PhysicsMesh, int), MeshSurfaceBoundaryDomain>? prepared) |
| | | 41 | | { |
| | 21505 | 42 | | Active = true; |
| | 43010 | 43 | | Inputs.FastClear(); MemberBySurface.Clear(); |
| | 125264 | 44 | | foreach (var input in surfaces) |
| | | 45 | | { |
| | 41127 | 46 | | int owner = input.Collider.Mesh.GetManifoldSurfaceOwner(input.Triangle); |
| | 82253 | 47 | | if (MemberBySurface.TryAdd((input.Collider.Mesh, owner), 0)) Inputs.Add((input.Collider, owner)); |
| | | 48 | | } |
| | 21505 | 49 | | Inputs.SortInPlace(_memberComparer); |
| | 21505 | 50 | | bool reuse = PreparedCount == Inputs.Count; |
| | 119916 | 51 | | for (int index = 0; reuse && index < Inputs.Count; index++) |
| | | 52 | | { |
| | 76906 | 53 | | Member<TFrame> member = Members[index]; var input = Inputs[index]; |
| | 38453 | 54 | | reuse = member.Collider == input.Collider && member.Owner == input.Triangle |
| | 38453 | 55 | | && member.PreparedLifetime == input.Collider.LifetimeVersion |
| | 38453 | 56 | | && member.PreparedVersion == input.Collider.RuntimeShapeVersion; |
| | | 57 | | } |
| | | 58 | | // Only a fully completed build publishes the reusable set. |
| | 21505 | 59 | | PreparedCount = -1; |
| | 107525 | 60 | | Meshes.FastClear(); Parents.FastClear(); Roots.FastClear(); RegionByRoot.FastClear(); NodeMembers.FastClear(); |
| | 21505 | 61 | | if (prepared != null) |
| | 333239 | 62 | | foreach (PhysicsMesh mesh in preparedMeshes) Meshes.Add(mesh); |
| | | 63 | | else |
| | 1342 | 64 | | foreach (var input in Inputs.AsReadOnlySpan()) |
| | 849 | 65 | | if (Meshes.Count == 0 || Meshes[Meshes.Count - 1] != input.Collider.Mesh) Meshes.Add(input.Collider.Mesh |
| | 21505 | 66 | | PreparedBoundaries.FastClear(); |
| | 21505 | 67 | | int meshIndex = -1; |
| | 125262 | 68 | | for (int index = 0; index < Inputs.Count; index++) |
| | | 69 | | { |
| | 42069 | 70 | | if (index == Members.Count) Members.Add(new Member<TFrame>()); |
| | 41126 | 71 | | Member<TFrame> member = Members[index]; |
| | 82252 | 72 | | member.Collider = Inputs[index].Collider; member.Triangle = member.Owner = Inputs[index].Triangle; |
| | 41126 | 73 | | PhysicsMesh mesh = member.Collider.Mesh; |
| | 41126 | 74 | | MemberBySurface[(mesh, member.Owner)] = index; |
| | 82221 | 75 | | if (index == 0 || Inputs[index - 1].Collider != member.Collider) meshIndex++; |
| | 41126 | 76 | | bool changed = !reuse; |
| | 41126 | 77 | | if (prepared != null) |
| | | 78 | | { |
| | 40701 | 79 | | MeshSurfaceBoundaryDomain boundary = prepared[(mesh, member.Owner)]; |
| | 40701 | 80 | | changed |= !ReferenceEquals(member.Boundary, boundary); |
| | 40701 | 81 | | member.Boundary = boundary; |
| | | 82 | | } |
| | 599 | 83 | | else if (!reuse) member.Boundary.Build(Meshes.AsReadOnlySpan(), meshIndex, member.Triangle); |
| | 41126 | 84 | | if (changed) |
| | | 85 | | { |
| | 2699 | 86 | | member.BoundaryTrusted = true; |
| | 27814 | 87 | | foreach (var span in member.Boundary.Spans) |
| | 11406 | 88 | | if (span.Kind == SpanKind.Ambiguous) member.BoundaryTrusted = false; |
| | | 89 | | } |
| | 41126 | 90 | | PreparedBoundaries.Add(member.Boundary); |
| | 41126 | 91 | | if (member.JoinedSpans.Length < member.Boundary.Spans.Length) |
| | 945 | 92 | | Array.Resize(ref member.JoinedSpans, member.Boundary.Spans.Length); |
| | 41126 | 93 | | Array.Clear(member.JoinedSpans, 0, member.Boundary.Spans.Length); |
| | | 94 | | } |
| | 21505 | 95 | | } |
| | | 96 | | |
| | | 97 | | internal void AddRegions(int index) |
| | 19132 | 98 | | => AddRegions(index, Members[index].Connectivity.RegionCount); |
| | | 99 | | |
| | | 100 | | internal void PrepareResponseComponents() |
| | | 101 | | { |
| | 23591 | 102 | | if (_responseComponents.Length < Inputs.Count) |
| | | 103 | | { |
| | 365 | 104 | | Array.Resize(ref _responseComponents, Inputs.Count); |
| | 365 | 105 | | Array.Resize(ref _responseMembers, Inputs.Count); |
| | | 106 | | } |
| | 134258 | 107 | | for (int index = 0; index < Inputs.Count; index++) |
| | 87076 | 108 | | { _responseComponents[index] = index; _responseMembers[index] = -1; } |
| | | 109 | | // Geometry certifies coverage independently of finite support admission. |
| | | 110 | | // A covered rim stays covered even when its owner supplies no sample. |
| | 134258 | 111 | | for (int index = 0; index < Inputs.Count; index++) |
| | | 112 | | { |
| | 43538 | 113 | | Member<TFrame> member = Members[index]; |
| | 450220 | 114 | | for (int span = 0; span < member.Boundary.Spans.Length; span++) |
| | | 115 | | { |
| | 181572 | 116 | | var edge = member.Boundary.Spans[span]; |
| | | 117 | | // Coverage certifies this span independently. An ambiguous or |
| | | 118 | | // folded edge elsewhere still keeps its own native perimeter. |
| | 181572 | 119 | | member.JoinedSpans[span] = edge.Kind == SpanKind.Joined |
| | 181572 | 120 | | && MemberBySurface.TryGetValue((Meshes[edge.OtherMember], edge.OtherSurface), out int other); |
| | 181572 | 121 | | if (!member.JoinedSpans[span]) continue; |
| | 79668 | 122 | | int a = FindResponseComponent(index), b = FindResponseComponent(MemberBySurface[(Meshes[edge.OtherMember |
| | 39834 | 123 | | _responseComponents[Math.Max(a, b)] = Math.Min(a, b); |
| | | 124 | | } |
| | | 125 | | } |
| | 23591 | 126 | | } |
| | | 127 | | |
| | | 128 | | internal void AddAdmittedMember(int index) |
| | | 129 | | { |
| | 26481 | 130 | | int component = FindResponseComponent(index); |
| | | 131 | | // Inputs are sorted, so the first genuine overlap is the stable carrier. |
| | 46666 | 132 | | if (_responseMembers[component] < 0) _responseMembers[component] = index; |
| | 26481 | 133 | | } |
| | | 134 | | |
| | | 135 | | internal int FindResponseComponent(int index) |
| | | 136 | | { |
| | 456365 | 137 | | while (_responseComponents[index] != index) |
| | 237244 | 138 | | { _responseComponents[index] = _responseComponents[_responseComponents[index]]; index = _responseComponents[inde |
| | 337743 | 139 | | return index; |
| | | 140 | | } |
| | | 141 | | |
| | 65157 | 142 | | internal int GetResponseMember(int index) => _responseMembers[FindResponseComponent(index)]; |
| | | 143 | | |
| | | 144 | | internal void AddRegions(int index, int count) |
| | | 145 | | { |
| | 100524 | 146 | | Member<TFrame> member = Members[index]; member.Offset = Parents.Count; |
| | 168610 | 147 | | for (int region = 0; region < count; region++) |
| | 102129 | 148 | | { Parents.Add(Parents.Count); RegionByRoot.Add(-1); NodeMembers.Add(index); } |
| | 50262 | 149 | | } |
| | | 150 | | |
| | | 151 | | internal void Union(int first, int second) |
| | | 152 | | { |
| | 52132 | 153 | | int a = Find(first), b = Find(second); |
| | 26066 | 154 | | Parents[Math.Max(a, b)] = Math.Min(a, b); |
| | 26066 | 155 | | } |
| | | 156 | | |
| | | 157 | | internal int Find(int node) |
| | | 158 | | { |
| | 415245 | 159 | | while (Parents[node] != node) { Parents[node] = Parents[Parents[node]]; node = Parents[node]; } |
| | 225312 | 160 | | return node; |
| | | 161 | | } |
| | | 162 | | |
| | | 163 | | internal void CompleteRegions() |
| | | 164 | | { |
| | 121166 | 165 | | for (int node = 0; node < Parents.Count; node++) |
| | | 166 | | { |
| | 34043 | 167 | | int root = Find(node); |
| | 34043 | 168 | | if (RegionByRoot[root] >= 0) continue; |
| | 53292 | 169 | | RegionByRoot[root] = Roots.Count; Roots.Add(root); |
| | | 170 | | } |
| | 26540 | 171 | | } |
| | | 172 | | |
| | | 173 | | internal void Commit() |
| | | 174 | | { |
| | 125262 | 175 | | foreach (Member<TFrame> member in Members.AsReadOnlySpan()[..Inputs.Count]) |
| | 82252 | 176 | | { member.PreparedVersion = member.Collider.RuntimeShapeVersion; member.PreparedLifetime = member.Collider.Lifeti |
| | 21505 | 177 | | PreparedCount = Inputs.Count; |
| | 21505 | 178 | | } |
| | | 179 | | |
| | | 180 | | internal ReadOnlySpan<WideAxis3> GetEndpointFan(LSMeshCollider collider, int triangle, int span, bool upper, out boo |
| | | 181 | | { |
| | 76 | 182 | | Member<TFrame> member = Members[MemberBySurface[(collider.Mesh, collider.Mesh.GetManifoldSurfaceOwner(triangle)) |
| | 76 | 183 | | bool trusted = Fan.BuildEndpoint(Meshes.AsReadOnlySpan(), member.Boundary, span, upper, PreparedBoundaries.AsRea |
| | 76 | 184 | | suppress = trusted && !Fan.HasExposedBoundary; |
| | | 185 | | // A genuine shared corner supplies one physical row in stable collider/surface order. |
| | 76 | 186 | | if (trusted) |
| | 468 | 187 | | foreach (var owner in Fan.Owners) |
| | 161 | 188 | | if (MemberBySurface.TryGetValue((Meshes[owner.Member], owner.Surface), out int other) |
| | 161 | 189 | | && (((IPhysicsColliderRegistryItem)Members[other].Collider).ReplayOrder < ((IPhysicsColliderRegistry |
| | 161 | 190 | | && collider.Mesh.GetCanonicalSurfaceOrdinal(owner.Surface) < collider.Mesh.GetCanonicalSurfaceOr |
| | 40 | 191 | | suppress = true; |
| | 76 | 192 | | return trusted ? Fan.Rays : default; |
| | | 193 | | } |
| | | 194 | | |
| | | 195 | | internal ReadOnlySpan<WideAxis3> GetCornerFan(LSMeshCollider collider, int triangle, int vertex, out bool suppress) |
| | | 196 | | { |
| | 227 | 197 | | Member<TFrame> member = Members[MemberBySurface[(collider.Mesh, collider.Mesh.GetManifoldSurfaceOwner(triangle)) |
| | 227 | 198 | | Vector3d point = collider.Mesh.GeometryVertices[vertex]; |
| | 227 | 199 | | bool trusted = Fan.BuildAtPoint(Meshes.AsReadOnlySpan(), member.Boundary.SourceMember, member.Owner, |
| | 227 | 200 | | point, PreparedBoundaries.AsReadOnlySpan()); |
| | 227 | 201 | | suppress = trusted && !Fan.HasExposedBoundary; |
| | | 202 | | // A finite canonical-owner corner can borrow a fan only when every |
| | | 203 | | // incident owner's complete perimeter retains its classification. |
| | 227 | 204 | | if (trusted) |
| | 1259 | 205 | | foreach (var owner in Fan.Owners) |
| | 408 | 206 | | if (MemberBySurface.TryGetValue((Meshes[owner.Member], owner.Surface), out int incident) && !Members[inc |
| | 2 | 207 | | { suppress = false; return default; } |
| | 226 | 208 | | if (trusted) |
| | 1254 | 209 | | foreach (var owner in Fan.Owners) |
| | | 210 | | { |
| | 406 | 211 | | if (!MemberBySurface.TryGetValue((Meshes[owner.Member], owner.Surface), out int other) |
| | 406 | 212 | | || ((IPhysicsColliderRegistryItem)Members[other].Collider).ReplayOrder > ((IPhysicsColliderRegistryI |
| | 406 | 213 | | && collider.Mesh.GetCanonicalSurfaceOrdinal(owner.Surface) >= collider.Mesh.GetCanonicalSurfaceOrdin |
| | 109 | 214 | | PhysicsMesh mesh = Members[other].Collider.Mesh; |
| | 109 | 215 | | ReadOnlySpan<int> edges = mesh.GetCanonicalSurfaceBoundaryVertexPairs(owner.Surface); |
| | 720 | 216 | | for (int edge = 0; edge < edges.Length; edge += 2) |
| | | 217 | | { |
| | 318 | 218 | | int location = WideTriangleRelations.LocateEdgePoint(new FixedSegment(point, point), |
| | 318 | 219 | | collider.Mesh.GeometryFrame, default(Signed832), Signed832.ExtendValue(Signed192.Signed(1)), |
| | 318 | 220 | | new FixedSegment(mesh.GeometryVertices[edges[edge]], mesh.GeometryVertices[edges[edge + 1]]), me |
| | | 221 | | // Certified exposed/joined transitions are authored corners |
| | | 222 | | // of some member. An interior-edge owner cannot supply one. |
| | 452 | 223 | | if (location == 0 || location == 2) { suppress = true; break; } |
| | | 224 | | } |
| | | 225 | | } |
| | 226 | 226 | | return trusted ? Fan.Rays : default; |
| | | 227 | | } |
| | | 228 | | |
| | | 229 | | |
| | | 230 | | } |