Next Gen STEP AP242 Native-ish BREP Geometric Modeling Kernel
using System.Security.Cryptography;
using System.Text;
using System.Text.Json;
using System.Text.Json.Serialization;
using Aetheris.Kernel.Core.Geometry;
using Aetheris.Kernel.Core.Geometry.Curves;
using Aetheris.Kernel.Core.Geometry.Surfaces;
using Aetheris.Kernel.Core.Math;
using Aetheris.Kernel.Core.Topology;
namespace Aetheris.Kernel.Core.Brep.Tessellation;
/// <summary>
/// Derived, surface-aware mesh document. This is deliberately not a topology or
/// mass-property authority: the B-rep remains the exact source of both.
/// </summary>
public sealed record SurfaceMeshDocument(
IReadOnlyList<SurfaceMeshVertex> Vertices,
IReadOnlyList<SurfacePatch> Patches,
IReadOnlyList<SharedEdgeSamplePlan> SharedBoundaries,
SurfaceMeshMetrics Metrics,
IReadOnlyList<ForeignTrimResolution>? ForeignTrimResolutions = null);
public sealed record SurfaceMeshVertex(int Id, Point3D Position, double? U = null, double? V = null);
/// <summary>One trim loop expressed both as shared B-rep samples and in the support plane's local coordinates.</summary>
public sealed record SurfaceMeshTrimLoop(
LoopId LoopId,
IReadOnlyList<int> VertexIds,
IReadOnlyList<(double U, double V)> LocalCoordinates,
bool IsInner,
double SignedArea,
IReadOnlyList<SurfaceMeshBoundarySpan>? BoundarySpans = null);
/// <summary>Source-B-rep provenance for an ordered planar boundary span.</summary>
public sealed record SurfaceMeshBoundarySpan(
EdgeId SourceEdgeId,
int StartVertexId,
int EndVertexId,
CurveGeometryKind SourceCurveKind,
int SampleCount);
public sealed record FaceBoundaryUse(FaceId FaceId, LoopId LoopId, CoedgeId CoedgeId, bool IsReversed);
/// <summary>One exact curve sampled once in edge parameter order, then reused by every face use.</summary>
public sealed record SharedEdgeSamplePlan(
EdgeId EdgeId,
CurveGeometryKind CurveKind,
ParameterInterval Interval,
IReadOnlyList<SurfaceMeshVertex> Samples,
IReadOnlyList<FaceBoundaryUse> Uses,
bool IsClosed,
double MaxChordalDeviation,
double MaxTangentDeviationRadians = 0d);
public enum ForeignTrimResolutionKind { ExistingAnalytic, RecoveredAnalytic, SampledBSpline }
/// <summary>
/// Meshing-only interpretation of a foreign trim. It never replaces the source
/// B-rep curve and therefore does not make spline geometry kernel-authoritative.
/// </summary>
public sealed record ForeignTrimResolution(
EdgeId SourceEdgeId,
CurveGeometryKind SourceCurveKind,
ForeignTrimResolutionKind ResolutionKind,
SharedEdgeSamplePlan SharedSamplePlan,
IReadOnlyList<string> AdjacentSupportFamilies,
string? RecognitionCandidate,
double? MaxRecognitionDeviation,
double RecognitionTolerance,
string Provenance);
public enum SurfaceMeshSupportKind { Plane, Cylinder, Cone, Sphere, Torus, BoundedParametricPatch, Ellipsoid }
public enum SurfaceMeshCellKind { Quad, Triangle, BoundaryPolygon, Singular }
public enum SurfaceMeshCellProvenance { Unclassified, FeatureBand, Bridge, CoarseRemainder, ResidualTransition }
/// <summary>
/// Domain-neutral evaluator for a bounded parametric support. Implementations adapt the
/// authored geometry owned by a higher layer; SurfaceMeshIR only consumes the first jet
/// needed for sampling and normal generation.
/// </summary>
public interface ISurfaceMeshBoundedPatch
{
string StableId { get; }
double MinimumU { get; }
double MaximumU { get; }
double MinimumV { get; }
double MaximumV { get; }
SurfaceMeshParametricJet Evaluate(double u, double v);
bool TryProject(Point3D point, out double u, out double v);
}
public sealed record SurfaceMeshParametricJet(Point3D Point, Vector3D Du, Vector3D Dv)
{
public bool TryNormal(out Vector3D normal) => Du.Cross(Dv).TryNormalize(out normal);
}
public sealed record SurfaceMeshSupport(
SurfaceMeshSupportKind Kind,
PlaneSurface? Plane = null,
CylinderSurface? Cylinder = null,
ConeSurface? Cone = null,
SphereSurface? Sphere = null,
TorusSurface? Torus = null,
[property: JsonIgnore] ISurfaceMeshBoundedPatch? BoundedPatch = null,
string? BoundedPatchStableId = null,
EllipsoidSurface? Ellipsoid = null);
public abstract record SurfaceMeshCell(SurfaceMeshCellKind Kind, IReadOnlyList<int> VertexIds, int RefinementLevel = 0, int? ParentCellId = null)
{
public SurfaceMeshCellProvenance Provenance { get; init; } = SurfaceMeshCellProvenance.Unclassified;
public string? ExceptionalReason { get; init; }
}
public sealed record QuadCell(IReadOnlyList<int> VertexIds, int RefinementLevel = 0, int? ParentCellId = null)
: SurfaceMeshCell(SurfaceMeshCellKind.Quad, VertexIds, RefinementLevel, ParentCellId);
public sealed record TriangleCell(IReadOnlyList<int> VertexIds, int RefinementLevel = 0, int? ParentCellId = null)
: SurfaceMeshCell(SurfaceMeshCellKind.Triangle, VertexIds, RefinementLevel, ParentCellId);
public sealed record BoundaryPolygonCell(IReadOnlyList<int> VertexIds, int RefinementLevel = 0, int? ParentCellId = null)
: SurfaceMeshCell(SurfaceMeshCellKind.BoundaryPolygon, VertexIds, RefinementLevel, ParentCellId);
public sealed record SingularCell(IReadOnlyList<int> VertexIds, int RefinementLevel = 0, int? ParentCellId = null)
: SurfaceMeshCell(SurfaceMeshCellKind.Singular, VertexIds, RefinementLevel, ParentCellId);
public sealed record SurfacePatch(
FaceId FaceId,
SurfaceMeshSupport Support,
IReadOnlyList<LoopId> TrimLoops,
IReadOnlyList<SurfaceMeshCell> Cells,
bool IsAlignedWithSupport,
string? SemanticOwner = null,
bool HasPeriodicUSeam = false,
bool HasPeriodicVSeam = false,
int MaxRefinementLevel = 0,
IReadOnlyList<SurfaceMeshTrimLoop>? TrimLoopData = null,
string? ChartId = null,
string? PlanarPlannerPath = null,
PlanarFeatureDecompositionPlan? PlanarFeaturePlan = null,
string? ResidualFieldId = null);
public enum SurfaceMeshDownstreamIntent { Presentation, Manufacturing, Fea }
/// <summary>Small policy seam for task-aware meshing; no language surface is exposed yet.</summary>
public sealed record SurfaceMeshPolicy(
double TargetChordalError,
double TargetNormalErrorRadians,
int MaxRefinementDepth,
int MaxBoundarySamples,
SurfaceMeshDownstreamIntent DownstreamIntent = SurfaceMeshDownstreamIntent.Presentation)
{
public static SurfaceMeshPolicy FromDisplayOptions(DisplayTessellationOptions options) => new(
options.ChordTolerance, options.AngularToleranceRadians, 8, options.MaximumSegments, SurfaceMeshDownstreamIntent.Presentation);
}
/// <summary>
/// A deliberately bounded correspondence for a four-sided analytic patch. It is
/// not an arbitrary trim remesher: the two transverse boundaries retain their
/// authoritative B-rep samples and each pair of opposing boundaries has the same
/// deterministic segment count. Interior points are evaluated on the support.
/// </summary>
public sealed record TrimBandPlan(
EdgeId StructuredGuideEdge,
EdgeId ExactTrimEdge,
EdgeId StartSideEdge,
EdgeId EndSideEdge,
int AngularSegments,
int GeneratorSegments,
string CorrespondenceRule = "matched edge parameter order; interpolate in analytic support coordinates");
public sealed record SurfaceMeshMetrics(
int PatchCount, int SharedBoundaryCount, int CellCount, int QuadCount, int ExceptionalCellCount,
int TriangleCount, int MaxRefinementLevel, double MaxChordalDeviation, int BoundaryCrackCount,
double MinEdgeLength, double MaxEdgeLength, string DeterministicHash,
int BoundaryPolygonCount = 0,
int NonManifoldEdgeCount = 0,
int FinalTriangleCount = 0,
double WorstAspectRatio = 0d,
double MaxNormalDeviation = 0d,
long ApproximateBufferBytes = 0);
/// <summary>Read-only coverage accounting for an imported B-rep before a structured build.</summary>
public sealed record SurfaceMeshIrCoverageAudit(
int FaceCount,
int AnalyticSupportFaceCount,
int UnsupportedSupportFaceCount,
IReadOnlyDictionary<string, int> EdgeCurveFamilies,
IReadOnlyList<SurfaceMeshIrCoverageBlocker> BoundaryBlockers,
IReadOnlyList<SurfaceMeshIrCoverageBlocker>? ForeignSplineTrims = null);
public sealed record SurfaceMeshIrCoverageBlocker(
int EdgeId,
string CurveFamily,
IReadOnlyList<int> FaceIds,
IReadOnlyList<string>? FaceSupportFamilies = null,
int? Degree = null,
IReadOnlyList<int>? KnotMultiplicities = null,
IReadOnlyList<double>? KnotValues = null,
IReadOnlyList<Point3D>? ControlPoints = null,
ParameterInterval? ParameterInterval = null,
bool? Closed = null,
string? KnotSpecification = null,
Point3D? StartPoint = null,
Point3D? EndPoint = null,
Vector3D? StartTangent = null,
Vector3D? EndTangent = null);
public static class SurfaceMeshIrDebug
{
public static string ToJson(SurfaceMeshDocument document)
=> JsonSerializer.Serialize(document, new JsonSerializerOptions { WriteIndented = true, IncludeFields = true });
}
/// <summary>
/// Planner/lowerer for the analytic surface subset with explicit support topology.
/// General trim remeshing remains a visible legacy fallback; supported patches retain
/// quads until the final deterministic triangle lowering step.
/// </summary>
public static class SurfaceMeshIrTessellator
{
private const double Epsilon = 1e-9d;
public static bool TryTessellate(BrepBody body, DisplayTessellationOptions options, out DisplayTessellationResult result)
{
result = default!;
var policy = SurfaceMeshPolicy.FromDisplayOptions(options);
if (!TryBuild(body, policy, out var document)) return false;
if (!SurfaceMeshIrValidator.TryValidate(document, out _)) return false;
if (!TryLowerToTriangleMesh(document, out _, out _)) return false;
var patches = document.Patches.OrderBy(p => p.FaceId.Value).Select(p => LowerPatch(document, p)).ToArray();
var edges = document.SharedBoundaries.OrderBy(p => p.EdgeId.Value)
.Select(p => new DisplayEdgePolyline(p.EdgeId, p.Samples.Select(s => s.Position).ToArray(), p.IsClosed)).ToArray();
result = new DisplayTessellationResult(patches, edges, MeshPipeline: DisplayMeshPipeline.SurfaceMeshIr, SurfaceMeshMetrics: document.Metrics);
return true;
}
/// <summary>
/// Reports generic support coverage without invoking a fallback or modifying
/// topology. It is intentionally conservative: an analytic support face is
/// counted separately from whether its bounded trim is currently plannable.
/// </summary>
public static SurfaceMeshIrCoverageAudit Audit(BrepBody body)
{
var families = new SortedDictionary<string, int>(StringComparer.Ordinal);
var blockers = new List<SurfaceMeshIrCoverageBlocker>();
var foreignSplineTrims = new List<SurfaceMeshIrCoverageBlocker>();
var analytic = 0;
var unsupportedSupports = 0;
foreach (var face in body.Topology.Faces)
{
if (body.TryGetFaceSurfaceGeometry(face.Id, out var surface) && surface?.Kind is SurfaceGeometryKind.Plane or SurfaceGeometryKind.Cylinder or SurfaceGeometryKind.Cone or SurfaceGeometryKind.Sphere or SurfaceGeometryKind.Torus or SurfaceGeometryKind.Ellipsoid) analytic++;
else unsupportedSupports++;
}
foreach (var edge in body.Topology.Edges.OrderBy(edge => edge.Id.Value))
{
var family = body.TryGetEdgeCurveGeometry(edge.Id, out var curve) && curve is not null ? curve.Kind.ToString() : "Unbound";
families[family] = families.GetValueOrDefault(family) + 1;
if (family is "Line3" or "Circle3" or "Ellipse3" or "Hyperbola3") continue;
var usedFaces = body.Topology.Faces
.Where(face => body.GetLoopIds(face.Id).SelectMany(body.GetCoedgeIds).Any(coedgeId => body.Topology.GetCoedge(coedgeId).EdgeId == edge.Id))
.OrderBy(face => face.Id.Value).ToArray();
var faceIds = usedFaces.Select(face => face.Id.Value).ToArray();
var supports = usedFaces.Select(face => body.TryGetFaceSurfaceGeometry(face.Id, out var support) && support is not null ? support.Kind.ToString() : "Unbound").ToArray();
var spline = curve?.BSpline3;
var interval = body.Bindings.TryGetEdgeBinding(edge.Id, out var binding) ? binding.TrimInterval : null;
var audit = new SurfaceMeshIrCoverageBlocker(
edge.Id.Value, family, faceIds, supports,
spline?.Degree, spline?.KnotMultiplicities, spline?.KnotValues, spline?.ControlPoints,
interval, spline?.ClosedCurve, spline?.KnotSpec,
spline is { } value ? value.Evaluate(interval?.Start ?? value.DomainStart) : null,
spline is { } value2 ? value2.Evaluate(interval?.End ?? value2.DomainEnd) : null,
spline is { } value3 ? value3.EvaluateTangent(interval?.Start ?? value3.DomainStart) : null,
spline is { } value4 ? value4.EvaluateTangent(interval?.End ?? value4.DomainEnd) : null);
if (curve?.Kind == CurveGeometryKind.BSpline3 && spline is not null) foreignSplineTrims.Add(audit);
else blockers.Add(audit);
}
return new SurfaceMeshIrCoverageAudit(body.Topology.Faces.Count(), analytic, unsupportedSupports, families, blockers, foreignSplineTrims);
}
/// <summary>Final deterministic lowering seam used by export. Consumers only see triangles.</summary>
public static bool TryLowerToTriangleMesh(SurfaceMeshDocument document, out TriangleMesh mesh, out TriangleMeshTopologyReport report)
{
var positions = document.Vertices.OrderBy(v => v.Id).Select(v => v.Position).ToList();
var normals = document.Vertices.OrderBy(v => v.Id).Select(_ => new Vector3D(0d, 0d, 0d)).ToList();
var indexById = document.Vertices.OrderBy(v => v.Id).Select((vertex, index) => (vertex.Id, index)).ToDictionary(item => item.Id, item => item.index);
var indices = new List<int>();
foreach (var patch in document.Patches.OrderBy(p => p.FaceId.Value))
{
var vertexById = document.Vertices.ToDictionary(v => v.Id);
var exactNormal = ResolvePatchNormal(document, patch, vertexById);
foreach (var cell in patch.Cells)
{
var ids = cell.VertexIds;
if (cell.Kind == SurfaceMeshCellKind.Quad)
{
var a = indexById[ids[0]]; var b = indexById[ids[1]]; var c = indexById[ids[2]]; var d = indexById[ids[3]];
var ac = (positions[a] - positions[c]).Length; var bd = (positions[b] - positions[d]).Length;
var acValid = TriangleAreaMagnitude(positions[a], positions[b], positions[c]) > Epsilon && TriangleAreaMagnitude(positions[a], positions[c], positions[d]) > Epsilon;
var bdValid = TriangleAreaMagnitude(positions[a], positions[b], positions[d]) > Epsilon && TriangleAreaMagnitude(positions[b], positions[c], positions[d]) > Epsilon;
if (acValid && (!bdValid || ac <= bd)) indices.AddRange([a, b, c, a, c, d]); else indices.AddRange([a, b, d, b, c, d]);
normals[a] = exactNormal(positions[a]); normals[b] = exactNormal(positions[b]); normals[c] = exactNormal(positions[c]); normals[d] = exactNormal(positions[d]);
}
else if (cell.Kind == SurfaceMeshCellKind.Triangle)
{
var a = indexById[ids[0]]; var b = indexById[ids[1]]; var c = indexById[ids[2]];
indices.AddRange([a, b, c]); normals[a] = exactNormal(positions[a]); normals[b] = exactNormal(positions[b]); normals[c] = exactNormal(positions[c]);
}
else
{
if (TryTriangulateBoundaryCell(patch, ids, vertexById, out var localIndices))
{
for (var i = 0; i < localIndices.Count; i += 3)
{
var a = indexById[ids[localIndices[i]]]; var b = indexById[ids[localIndices[i + 1]]]; var c = indexById[ids[localIndices[i + 2]]];
indices.AddRange([a, b, c]); normals[a] = exactNormal(positions[a]); normals[b] = exactNormal(positions[b]); normals[c] = exactNormal(positions[c]);
}
}
else
{
// No general centre fan: an untriangulable cell rejects this
// optional IR route, allowing the caller's diagnostic fallback.
mesh = new TriangleMesh(positions, normals, [], new HashSet<(int, int)>(), "");
report = new(false, false, false, 0, 0, 0, 0, 0, positions.Count, 0);
return false;
}
}
}
}
var hard = BuildHardEdges(document, indexById);
var hash = Convert.ToHexString(SHA256.HashData(Encoding.UTF8.GetBytes(string.Join("|", positions.Select(p => $"{p.X:R},{p.Y:R},{p.Z:R}") ) + ";" + string.Join(',', indices)))).ToLowerInvariant();
mesh = new TriangleMesh(positions, normals, indices, hard, hash);
return TriangleMeshValidator.TryValidateClosed(mesh, out report, out _);
}
private static Point3D ResolvePlanarPolygonCentroid(
IReadOnlyList<int> ids,
IReadOnlyDictionary<int, SurfaceMeshVertex> vertices,
PlaneSurface plane)
{
var local = ids.Select(id => ToPlaneLocal(plane, vertices[id].Position)).ToArray();
var twiceArea = 0d;
var weightedU = 0d;
var weightedV = 0d;
for (var index = 0; index < local.Length; index++)
{
var next = local[(index + 1) % local.Length];
var cross = (local[index].U * next.V) - (next.U * local[index].V);
twiceArea += cross;
weightedU += (local[index].U + next.U) * cross;
weightedV += (local[index].V + next.V) * cross;
}
if (double.Abs(twiceArea) <= Epsilon)
return new Point3D(ids.Average(id => vertices[id].Position.X), ids.Average(id => vertices[id].Position.Y), ids.Average(id => vertices[id].Position.Z));
return plane.Evaluate(weightedU / (3d * twiceArea), weightedV / (3d * twiceArea));
}
private static IReadOnlySet<(int A, int B)> BuildHardEdges(SurfaceMeshDocument document, IReadOnlyDictionary<int, int> indexById)
{
// Multi-chart supports such as a sphere legitimately contribute several
// patches for one B-rep face; all charts share the same smooth support.
var supportByFace = document.Patches
.GroupBy(patch => patch.FaceId)
.ToDictionary(group => group.Key, group => group.First().Support.Kind);
var hard = new HashSet<(int A, int B)>();
foreach (var boundary in document.SharedBoundaries)
{
var kinds = boundary.Uses.Select(use => supportByFace[use.FaceId]).Distinct().ToArray();
if (kinds.Length < 2 || kinds.All(kind => kind == kinds[0])) continue;
for (var i = 0; i + 1 < boundary.Samples.Count; i++)
{
var a = indexById[boundary.Samples[i].Id]; var b = indexById[boundary.Samples[i + 1].Id];
hard.Add(a < b ? (a, b) : (b, a));
}
}
return hard;
}
public static bool TryBuild(BrepBody body, SurfaceMeshPolicy policy, out SurfaceMeshDocument document)
=> TryBuild(body, policy, out document, out _);
/// <summary>Builds the structured document and exposes the first generic unsupported contract.</summary>
public static bool TryBuild(BrepBody body, SurfaceMeshPolicy policy, out SurfaceMeshDocument document, out string? failure)
{
document = default!; failure = null;
var vertices = new List<SurfaceMeshVertex>();
var plans = new List<SharedEdgeSamplePlan>();
var endpointVertices = new Dictionary<VertexId, SurfaceMeshVertex>();
var nextVertexId = 0;
// A bounded conic/torus band can only use shared edge IDs when every
// opposing boundary has a common cell lattice. Establish those counts
// before sampling anything; this is what makes the Hyperbola authoritative
// rather than a face-local approximation.
var structuredSegments = BuildStructuredSegmentConstraints(body, policy);
foreach (var edge in body.Topology.Edges.OrderBy(e => e.Id.Value))
{
if (!TryPlanEdge(body, edge.Id, policy, endpointVertices, ref nextVertexId, structuredSegments.TryGetValue(edge.Id, out var forcedSegments) ? forcedSegments : null, out var plan))
{
failure = body.TryGetEdgeCurveGeometry(edge.Id, out var curve) && curve is not null
? $"SurfaceMeshIR does not support edge {edge.Id.Value} with curve family {curve.Kind}."
: $"SurfaceMeshIR could not resolve exact geometry for edge {edge.Id.Value}.";
return false;
}
vertices.AddRange(plan.Samples);
plans.Add(plan);
}
vertices = vertices.GroupBy(v => v.Id).Select(g => g.First()).OrderBy(v => v.Id).ToList();
var byEdge = plans.ToDictionary(p => p.EdgeId);
var patches = new List<SurfacePatch>();
foreach (var face in body.Topology.Faces.OrderBy(f => f.Id.Value))
{
if (!body.TryGetFaceSurfaceGeometry(face.Id, out var surface) || surface is null ||
surface.Kind is not (SurfaceGeometryKind.Plane or SurfaceGeometryKind.Cylinder or SurfaceGeometryKind.Cone or SurfaceGeometryKind.Sphere or SurfaceGeometryKind.Torus or SurfaceGeometryKind.Ellipsoid) ||
!body.Bindings.TryGetFaceBinding(face.Id, out var faceBinding))
{
failure = $"SurfaceMeshIR does not support face {face.Id.Value}: the face has no bound Plane/Cylinder/Cone/Sphere/Torus/Ellipsoid support.";
return false;
}
switch (surface.Kind)
{
case SurfaceGeometryKind.Plane:
var planePatch = TryBuildPlanePatch(body, face.Id, faceBinding.Orientation.IsAlignedWithSurface, surface.Plane!.Value, byEdge, vertices, ref nextVertexId);
if (planePatch is null) { failure = $"SurfaceMeshIR does not support trim topology on planar face {face.Id.Value}."; return false; }
patches.Add(planePatch);
break;
case SurfaceGeometryKind.Cylinder:
var cylinderPatch = TryBuildCylinderPatch(body, face.Id, faceBinding.Orientation.IsAlignedWithSurface, surface.Cylinder!.Value, byEdge, policy, vertices, ref nextVertexId);
if (cylinderPatch is null) { failure = $"SurfaceMeshIR does not support trim topology on cylindrical face {face.Id.Value}."; return false; }
patches.Add(cylinderPatch);
break;
case SurfaceGeometryKind.Cone:
var conePatch = TryBuildConePatch(body, face.Id, faceBinding.Orientation.IsAlignedWithSurface, surface.Cone!.Value, byEdge, policy, vertices, ref nextVertexId);
if (conePatch is null) { failure = $"SurfaceMeshIR does not support trim topology on conical face {face.Id.Value}."; return false; }
patches.Add(conePatch);
break;
case SurfaceGeometryKind.Ellipsoid:
var ellipsoidPatch = TryBuildConvexQuadricPatch(body, face.Id, faceBinding.Orientation.IsAlignedWithSurface,
new SurfaceMeshSupport(SurfaceMeshSupportKind.Ellipsoid, Ellipsoid: surface.Ellipsoid), byEdge, policy, vertices, ref nextVertexId);
if (ellipsoidPatch is null) { failure = $"SurfaceMeshIR does not support chart/trim topology on ellipsoid face {face.Id.Value}."; return false; }
patches.Add(ellipsoidPatch);
break;
case SurfaceGeometryKind.Sphere:
if (body.GetLoopIds(face.Id).Count > 0)
{
var cornerPatch = TryBuildConvexQuadricPatch(body, face.Id, faceBinding.Orientation.IsAlignedWithSurface,
new SurfaceMeshSupport(SurfaceMeshSupportKind.Sphere, Sphere: surface.Sphere), byEdge, policy, vertices, ref nextVertexId);
if (cornerPatch is null) { failure = $"SurfaceMeshIR does not support convex spherical trim on face {face.Id.Value}."; return false; }
patches.Add(cornerPatch); break;
}
if (!TryBuildSphereCharts(body, face.Id, faceBinding.Orientation.IsAlignedWithSurface, surface.Sphere!.Value, vertices, ref nextVertexId, out var spherePatches)) { failure = $"SurfaceMeshIR does not support chart/trim topology on spherical face {face.Id.Value}."; return false; }
patches.AddRange(spherePatches);
break;
case SurfaceGeometryKind.Torus:
var torusPatch = TryBuildTorusPatch(body, face.Id, faceBinding.Orientation.IsAlignedWithSurface, surface.Torus!.Value, byEdge, policy, vertices, ref nextVertexId);
if (torusPatch is null) { failure = $"SurfaceMeshIR does not support trim topology on toroidal face {face.Id.Value}."; return false; }
patches.Add(torusPatch);
break;
}
}
vertices = vertices.GroupBy(v => v.Id).Select(g => g.First()).OrderBy(v => v.Id).ToList();
// Some construction recipes retain source-only topological edges after a
// replacement trim has been emitted. They have no face use and are not a
// mesh boundary contract, so keep them out of the SurfaceMeshIR document.
var sharedPlans = plans.Where(plan => plan.Uses.Count > 0).ToArray();
var preMetrics = ComputeMetrics(vertices, patches, sharedPlans, triangleCount: 0);
var foreignTrimResolutions = BuildForeignTrimResolutions(body, sharedPlans, policy);
var builtDocument = new SurfaceMeshDocument(vertices, patches, sharedPlans, preMetrics, foreignTrimResolutions);
// Chart traversal is not material orientation. Strip/bridge planners may
// walk their local chart either way; publish every cell in the resolved
// BRep support orientation once, before OBJ, display or STL consumes it.
var vertexById = vertices.ToDictionary(v => v.Id);
patches = patches.Select(patch =>
{
var normal = ResolvePatchNormal(builtDocument, patch, vertexById);
return patch with { Cells = patch.Cells.Select(cell =>
{
if (cell.VertexIds.Count < 3) return cell;
var ids = cell.VertexIds;
// Use the analytic chart's Jacobian orientation, not a chord's
// approximate 3D normal. Thin trimmed ears may span appreciable
// curvature; independently flipping those chords folds a patch.
var chart = ids.Select(id => patch.Support.Kind switch
{
SurfaceMeshSupportKind.Cylinder when patch.Support.Cylinder is { } c => TryProjectPointToCylinderUv(c, vertexById[id].Position),
SurfaceMeshSupportKind.Cone when patch.Support.Cone is { } c => TryProjectPointToConeUv(c, vertexById[id].Position),
SurfaceMeshSupportKind.Torus when patch.Support.Torus is { } t => TryProjectPointToTorusUv(t, vertexById[id].Position),
_ => null
}).ToArray();
if (chart.All(p => p is not null))
{
var uv = UnwrapPeriodicU(chart.Select(p => p!.Value).ToArray());
if (patch.Support.Kind == SurfaceMeshSupportKind.Torus)
uv = UnwrapPeriodicU(uv.Select(p => (p.V, p.U)).ToArray()).Select(p => (U: p.V, V: p.U)).ToArray();
var positive = SignedArea(uv) > 0;
return positive != patch.IsAlignedWithSupport
? cell with { VertexIds = ids.Take(1).Concat(ids.Skip(1).Reverse()).ToArray() } : cell;
}
var origin = vertexById[ids[0]].Position;
var area = new Vector3D(0, 0, 0); var outward = new Vector3D(0, 0, 0);
for (var i = 0; i < ids.Count; i++)
{
var point = vertexById[ids[i]].Position;
area += (point - origin).Cross(vertexById[ids[(i + 1) % ids.Count]].Position - origin);
outward += normal(point);
}
return area.Dot(outward) < 0
? cell with { VertexIds = ids.Take(1).Concat(ids.Skip(1).Reverse()).ToArray() } : cell;
}).ToArray() };
}).ToList();
builtDocument = builtDocument with { Patches = patches };
var triangleCount = builtDocument.Patches.Sum(p => CountLoweredTriangles(builtDocument, p));
document = builtDocument with { Metrics = ComputeMetrics(vertices, patches, sharedPlans, triangleCount) };
return true;
}
private static IReadOnlyList<ForeignTrimResolution> BuildForeignTrimResolutions(
BrepBody body,
IReadOnlyList<SharedEdgeSamplePlan> plans,
SurfaceMeshPolicy policy)
{
var resolutions = new List<ForeignTrimResolution>();
foreach (var plan in plans.Where(plan => plan.CurveKind == CurveGeometryKind.BSpline3).OrderBy(plan => plan.EdgeId.Value))
{
if (!body.TryGetEdgeCurveGeometry(plan.EdgeId, out var geometry) || geometry?.BSpline3 is not { } spline) continue;
var start = spline.Evaluate(plan.Interval.Start);
var end = spline.Evaluate(plan.Interval.End);
var chord = end - start;
var maxLineDeviation = Enumerable.Range(0, 33).Max(index =>
{
var parameter = plan.Interval.Start + ((plan.Interval.End - plan.Interval.Start) * index / 32d);
var point = spline.Evaluate(parameter);
if (chord.LengthSquared <= 1e-24d) return (point - start).Length;
var fraction = double.Clamp((point - start).Dot(chord) / chord.LengthSquared, 0d, 1d);
return (point - (start + (chord * fraction))).Length;
});
var supportFamilies = plan.Uses.Select(use =>
{
if (!body.TryGetFaceSurfaceGeometry(use.FaceId, out var surface) || surface is null) return "Unbound";
return surface.Kind.ToString();
}).Order(StringComparer.Ordinal).ToArray();
resolutions.Add(new ForeignTrimResolution(
plan.EdgeId,
CurveGeometryKind.BSpline3,
ForeignTrimResolutionKind.SampledBSpline,
plan,
supportFamilies,
"Line3",
maxLineDeviation,
policy.TargetChordalError,
maxLineDeviation <= policy.TargetChordalError
? "Line proximity passed position tolerance but exact tangent/span equivalence was not proven; retained as sampled source spline."
: "Adjacent analytic supports did not imply a bounded supported curve family; strict direct line recognition failed, so the imported non-rational spline was sampled without mutating the B-rep."));
}
return resolutions;
}
private static bool TryPlanEdge(BrepBody body, EdgeId edgeId, SurfaceMeshPolicy policy, Dictionary<VertexId, SurfaceMeshVertex> endpointVertices, ref int nextVertexId, int? forcedSegments, out SharedEdgeSamplePlan plan)
{
plan = default!;
if (!body.Bindings.TryGetEdgeBinding(edgeId, out var binding) || !body.TryGetEdgeCurveGeometry(edgeId, out var curve) || curve is null) return false;
var interval = binding.TrimInterval ?? new ParameterInterval(0d, 1d);
List<(double Parameter, Point3D Point)> sampled;
bool closed;
double chordError;
var tangentError = 0d;
switch (curve.Kind)
{
case CurveGeometryKind.Line3 when curve.Line3 is { } line:
// A bounded through-hole ring needs matching side-face boundary
// vertices. Split only line edges on bodies that actually carry
// circular trims; ordinary flat boxes remain one coarse quad/face.
var lineSegments = forcedSegments ?? (body.Geometry.Curves.Any(c => c.Value.Kind == CurveGeometryKind.Circle3) ? 9 : 1);
sampled = Enumerable.Range(0, lineSegments + 1)
.Select(i => (interval.Start + ((interval.End - interval.Start) * i / lineSegments), line.Evaluate(interval.Start + ((interval.End - interval.Start) * i / lineSegments))))
.ToList();
closed = false; chordError = 0d; break;
case CurveGeometryKind.Circle3 when curve.Circle3 is { } circle:
var span = interval.End - interval.Start;
var segments = int.Max(ResolveCircleSegments(circle.Radius, span, policy), forcedSegments ?? 1);
sampled = Enumerable.Range(0, segments + 1).Select(i =>
{
var parameter = interval.Start + (span * i / segments);
return (parameter, circle.Evaluate(parameter));
}).ToList();
closed = double.Abs(double.Abs(span) - (2d * double.Pi)) <= Epsilon;
chordError = circle.Radius * (1d - double.Cos(double.Abs(span) / (2d * segments)));
break;
case CurveGeometryKind.Hyperbola3 when curve.Hyperbola3 is { } hyperbola:
sampled = SampleHyperbola(hyperbola, interval, policy);
if (forcedSegments is { } count && count > 0)
sampled = Enumerable.Range(0, count + 1)
.Select(i => (interval.Start + ((interval.End - interval.Start) * i / count), hyperbola.Evaluate(interval.Start + ((interval.End - interval.Start) * i / count))))
.ToList();
closed = false;
chordError = ComputePolylineChordDeviation(hyperbola.Evaluate, sampled);
break;
case CurveGeometryKind.Ellipse3 when curve.Ellipse3 is { } ellipse:
var ellipseSpan = interval.End - interval.Start;
// An ellipse is a linear image of a unit circle: its major
// radius bounds chord deviation, and a/b bounds tangent turn.
var ellipseSegments = int.Max(ResolveCircleSegments(ellipse.MajorRadius, ellipseSpan, policy), forcedSegments ?? 1);
var tangentSegments = double.Ceiling(double.Abs(ellipseSpan) * ellipse.MajorRadius / ellipse.MinorRadius / policy.TargetNormalErrorRadians);
if (!double.IsFinite(tangentSegments) || tangentSegments >= policy.MaxBoundarySamples) return false;
ellipseSegments = int.Max(ellipseSegments, (int)tangentSegments);
if (ellipseSegments + 1 > policy.MaxBoundarySamples) return false;
sampled = Enumerable.Range(0, ellipseSegments + 1).Select(i =>
{
var parameter = interval.Start + ellipseSpan * i / ellipseSegments;
return (parameter, ellipse.Evaluate(parameter));
}).ToList();
closed = double.Abs(double.Abs(ellipseSpan) - 2 * double.Pi) <= Epsilon;
chordError = ellipse.MajorRadius * (1 - double.Cos(double.Abs(ellipseSpan) / (2 * ellipseSegments)));
tangentError = double.Abs(ellipseSpan) * ellipse.MajorRadius / ellipse.MinorRadius / ellipseSegments;
break;
case CurveGeometryKind.BSpline3 when curve.BSpline3 is { } spline:
var splineSampling = BSplineTrimSampler.Sample(spline, interval, policy);
if (!splineSampling.IsSuccess) return false;
sampled = splineSampling.Samples.Select(sample => (sample.Parameter, sample.Point)).ToList();
closed = spline.ClosedCurve || (sampled[0].Point - sampled[^1].Point).Length <= policy.TargetChordalError;
chordError = splineSampling.MaxChordalDeviation;
tangentError = splineSampling.MaxTangentDeviationRadians;
break;
default: return false;
}
if (!body.TryGetEdgeVertices(edgeId, out var startVertex, out var endVertex)) return false;
var samples = new SurfaceMeshVertex[sampled.Count];
for (var i = 0; i < sampled.Count; i++)
{
var endpoint = i == 0 ? startVertex : i == sampled.Count - 1 ? endVertex : default;
if (endpoint.IsValid && endpointVertices.TryGetValue(endpoint, out var existing))
{
samples[i] = existing;
}
else
{
samples[i] = new SurfaceMeshVertex(nextVertexId++, sampled[i].Point);
if (endpoint.IsValid) endpointVertices.Add(endpoint, samples[i]);
}
}
var uses = body.Topology.Faces.OrderBy(f => f.Id.Value).SelectMany(face => body.GetLoopIds(face.Id).SelectMany(loop => body.GetCoedgeIds(loop)
.Select(coedgeId => body.Topology.GetCoedge(coedgeId)).Where(c => c.EdgeId == edgeId)
.Select(c => new FaceBoundaryUse(face.Id, loop, c.Id, c.IsReversed)))).ToArray();
plan = new SharedEdgeSamplePlan(edgeId, curve.Kind, interval, samples, uses, closed, chordError, tangentError);
return true;
}
private static IReadOnlyDictionary<EdgeId, int> BuildStructuredSegmentConstraints(BrepBody body, SurfaceMeshPolicy policy)
{
var result = new Dictionary<EdgeId, int>();
foreach (var face in body.Topology.Faces.OrderBy(face => face.Id.Value))
{
if (!body.TryGetFaceSurfaceGeometry(face.Id, out var surface) || surface is null ||
surface.Kind is not (SurfaceGeometryKind.Cone or SurfaceGeometryKind.Cylinder or SurfaceGeometryKind.Torus)) continue;
var loops = body.GetLoopIds(face.Id);
if (loops.Count != 1) continue;
var coedges = body.GetCoedgeIds(loops[0]).Select(body.Topology.GetCoedge).ToArray();
if (coedges.Length != 4) continue;
var candidates = new List<(EdgeId Edge, int Segments)>();
foreach (var coedge in coedges)
{
if (!body.TryGetEdgeCurveGeometry(coedge.EdgeId, out var curve) || curve is null ||
!body.Bindings.TryGetEdgeBinding(coedge.EdgeId, out var binding)) { candidates.Clear(); break; }
var interval = binding.TrimInterval ?? new ParameterInterval(0d, 1d);
var count = curve.Kind switch
{
CurveGeometryKind.Circle3 when curve.Circle3 is { } circle => ResolveCircleSegments(circle.Radius, interval.End - interval.Start, policy),
CurveGeometryKind.Hyperbola3 when curve.Hyperbola3 is { } hyperbola => SampleHyperbola(hyperbola, interval, policy).Count - 1,
CurveGeometryKind.Line3 => body.Geometry.Curves.Any(item => item.Value.Kind == CurveGeometryKind.Circle3) ? 9 : 1,
_ => 0
};
if (count <= 0) { candidates.Clear(); break; }
candidates.Add((coedge.EdgeId, count));
}
if (candidates.Count != 4) continue;
// Opposing boundaries share a lattice direction. Do not force the
// transverse direction to the same density: a root torus needs many
// samples around its major span but only a few across its minor arc.
var transverse = int.Max(candidates[0].Segments, candidates[2].Segments);
var longitudinal = int.Max(candidates[1].Segments, candidates[3].Segments);
foreach (var candidate in new[] { candidates[0], candidates[2] })
result[candidate.Edge] = int.Max(result.GetValueOrDefault(candidate.Edge), transverse);
foreach (var candidate in new[] { candidates[1], candidates[3] })
result[candidate.Edge] = int.Max(result.GetValueOrDefault(candidate.Edge), longitudinal);
}
return result;
}
private static int ResolveCircleSegments(double radius, double span, SurfaceMeshPolicy policy)
{
var chord = policy.TargetChordalError >= radius ? 1 : (int)double.Ceiling(double.Abs(span) / (2d * double.Acos(double.Clamp(1d - (policy.TargetChordalError / radius), -1d, 1d))));
var normal = (int)double.Ceiling(double.Abs(span) / policy.TargetNormalErrorRadians);
// Keep the established display-circle baseline stable while the policy grows a
// dedicated edge-density knob; legacy display callers historically receive 36.
var baseline = double.Abs(double.Abs(span) - (2d * double.Pi)) <= Epsilon ? 36 : 1;
return int.Max(baseline, int.Max(1, int.Max(chord, normal)));
}
private static List<(double Parameter, Point3D Point)> SampleHyperbola(Hyperbola3Curve hyperbola, ParameterInterval interval, SurfaceMeshPolicy policy)
{
var samples = new List<(double Parameter, Point3D Point)> { (interval.Start, hyperbola.Evaluate(interval.Start)) };
AppendHyperbolaSegment(hyperbola, interval.Start, interval.End, samples[0].Point, hyperbola.Evaluate(interval.End), policy, samples, 0);
return samples;
}
private static void AppendHyperbolaSegment(
Hyperbola3Curve hyperbola,
double start,
double end,
Point3D startPoint,
Point3D endPoint,
SurfaceMeshPolicy policy,
List<(double Parameter, Point3D Point)> samples,
int depth)
{
var middle = (start + end) * 0.5d;
var middlePoint = hyperbola.Evaluate(middle);
var chordMidpoint = new Point3D((startPoint.X + endPoint.X) * 0.5d, (startPoint.Y + endPoint.Y) * 0.5d, (startPoint.Z + endPoint.Z) * 0.5d);
var deviation = (middlePoint - chordMidpoint).Length;
if (depth >= policy.MaxRefinementDepth || samples.Count + 1 >= policy.MaxBoundarySamples || deviation <= policy.TargetChordalError)
{
samples.Add((end, endPoint));
return;
}
AppendHyperbolaSegment(hyperbola, start, middle, startPoint, middlePoint, policy, samples, depth + 1);
AppendHyperbolaSegment(hyperbola, middle, end, middlePoint, endPoint, policy, samples, depth + 1);
}
private static double ComputePolylineChordDeviation(Func<double, Point3D> evaluate, IReadOnlyList<(double Parameter, Point3D Point)> samples)
{
var worst = 0d;
for (var index = 0; index + 1 < samples.Count; index++)
{
var middle = (samples[index].Parameter + samples[index + 1].Parameter) * 0.5d;
var midpoint = evaluate(middle);
var chordMidpoint = new Point3D(
(samples[index].Point.X + samples[index + 1].Point.X) * 0.5d,
(samples[index].Point.Y + samples[index + 1].Point.Y) * 0.5d,
(samples[index].Point.Z + samples[index + 1].Point.Z) * 0.5d);
worst = double.Max(worst, (midpoint - chordMidpoint).Length);
}
return worst;
}
/// <summary>
/// Reverses a trim loop when its measured winding contradicts the outer-CCW / inner-CW convention.
/// Reversal is purely a traversal change: the same vertices bound the same region.
/// </summary>
private static SurfaceMeshTrimLoop NormalizeTraversal(SurfaceMeshTrimLoop loop)
{
var wanted = loop.IsInner ? -1d : 1d;
if (loop.SignedArea == 0d || double.Sign(loop.SignedArea) == wanted) return loop;
// Reverse the cycle about its own base point: [a,b,c,d] becomes [a,d,c,b], not [d,c,b,a].
// Loop index 0 seeds guide construction and bridge candidate ordering, so moving it would make
// two mirror-image faces decompose differently for no geometric reason.
static T[] ReverseCycle<T>(IReadOnlyList<T> items) =>
items.Take(1).Concat(items.Skip(1).Reverse()).ToArray();
var ids = ReverseCycle(loop.VertexIds);
var local = ReverseCycle(loop.LocalCoordinates);
var spans = loop.BoundarySpans?
.Reverse()
.Select(span => span with { StartVertexId = span.EndVertexId, EndVertexId = span.StartVertexId })
.ToArray();
return loop with { VertexIds = ids, LocalCoordinates = local, SignedArea = -loop.SignedArea, BoundarySpans = spans };
}
private static SurfacePatch? TryBuildPlanePatch(BrepBody body, FaceId faceId, bool sameSense, PlaneSurface plane, IReadOnlyDictionary<EdgeId, SharedEdgeSamplePlan> plans, List<SurfaceMeshVertex> vertices, ref int nextVertexId)
{
var loops = body.GetLoopIds(faceId);
if (loops.Count == 0) return null;
var loopData = new List<SurfaceMeshTrimLoop>(loops.Count);
foreach (var loop in loops)
{
var coedges = body.GetCoedgeIds(loop).Select(body.Topology.GetCoedge).ToArray();
if (coedges.Length == 0) return null;
var ids = FlattenLoop(coedges, plans);
if (ids.Count < 3) return null;
var local = ids.Select(id => ToPlaneLocal(plane, vertices.First(v => v.Id == id).Position)).ToArray();
var spans = BuildBoundarySpans(coedges, plans);
loopData.Add(new SurfaceMeshTrimLoop(loop, ids, local, false, SignedArea(local), spans));
}
var outer = loopData.OrderByDescending(loop => double.Abs(loop.SignedArea)).First();
var inners = loopData.Where(loop => loop.LoopId != outer.LoopId).ToArray();
// A trimmed planar face has exactly one valid traversal convention: the outer loop runs
// counter-clockwise in the plane-local frame and every inner loop runs clockwise. The source
// topology does not guarantee it - a box's two caps carry their outer loops in the same 3D
// direction even though their normals oppose, so one cap arrives mirrored and, on a face with
// a hole, outer and inner can even agree in sign, which is geometrically impossible. Cell
// winding does not depend on this (every emitted cell is re-oriented by its own signed area),
// so the decomposition planners below were the first consumers to actually trust the traversal
// direction, and they silently produced a different, poorer decomposition when it was wrong.
// Normalize once, here, rather than teaching each planner to accept both handednesses.
var annotatedLoops = loopData
.Select(loop => NormalizeTraversal(loop with { IsInner = loop.LoopId != outer.LoopId }))
.ToArray();
outer = annotatedLoops.Single(loop => loop.LoopId == outer.LoopId);
inners = annotatedLoops.Where(loop => loop.LoopId != outer.LoopId).ToArray();
if (inners.Length == 0)
{
var coedges = body.GetCoedgeIds(outer.LoopId).Select(body.Topology.GetCoedge).ToArray();
if (coedges.Length == 4 && coedges.All(c => plans[c.EdgeId].CurveKind == CurveGeometryKind.Line3) && outer.VertexIds.Count == 4)
return new SurfacePatch(faceId, new SurfaceMeshSupport(SurfaceMeshSupportKind.Plane, Plane: plane), loops,
// Trim loops may already run against the support normal (e.g. an extrusion bottom).
// Keep their order only when its measured sense matches the face sense.
[new QuadCell(Orient(outer.VertexIds, (outer.SignedArea > 0d) == sameSense))], sameSense, TrimLoopData: annotatedLoops, PlanarPlannerPath: "PlanarDomain.RectangleQuad");
}
PlanarFeatureDecompositionPlan? failedFeaturePlan = null;
if (inners.Length > 0)
{
var featureDomain = PlanarDomainPlanner.Create(annotatedLoops);
var originalVertexCount = vertices.Count;
var originalNextVertexId = nextVertexId;
if (PlanarFeatureBandPlanner.TryPlan(featureDomain, plane, vertices, ref nextVertexId, sameSense, out var featureCells, out var featurePlan, out _))
return new SurfacePatch(faceId, new SurfaceMeshSupport(SurfaceMeshSupportKind.Plane, Plane: plane), loops, featureCells, sameSense,
TrimLoopData: annotatedLoops, PlanarPlannerPath: "PlanarDomain.FeatureBandsAndStructuredBridges", PlanarFeaturePlan: featurePlan);
failedFeaturePlan = featurePlan;
if (vertices.Count > originalVertexCount) vertices.RemoveRange(originalVertexCount, vertices.Count - originalVertexCount);
nextVertexId = originalNextVertexId;
}
// The rectangular annulus is retained as the economical all-quad path.
// It is now a bounded fallback when a dedicated local feature plan cannot
// be proved valid, rather than the preferred through-hole topology.
if (inners.Length != 1 || !IsRectangle(outer.LocalCoordinates) || inners[0].VertexIds.Count != outer.VertexIds.Count)
{
var domainVertices = vertices.ToDictionary(vertex => vertex.Id);
var domain = PlanarDomainPlanner.Create(annotatedLoops);
if (inners.Length > 0)
{
if (!PlanarDomainPlanner.TryDecompose(domain, plane, domainVertices, sameSense, out var fallbackCells, out var fallbackPath)) return null;
var fallbackConforming = PreserveBoundaryVerticesInParameterSpace(fallbackCells, annotatedLoops);
var fallbackCompact = PlanarDomainPlanner.MergeConformingCells(fallbackConforming, domain.BoundaryVertices, sameSense);
return new SurfacePatch(faceId, new SurfaceMeshSupport(SurfaceMeshSupportKind.Plane, Plane: plane), loops, fallbackCompact, sameSense,
TrimLoopData: annotatedLoops, PlanarPlannerPath: fallbackPath + ".M7Fallback", PlanarFeaturePlan: failedFeaturePlan);
}
if (!PlanarDomainPlanner.TryDecompose(domain, plane, domainVertices, sameSense, out var rawCells, out var plannerPath)) return null;
var conformingCells = PreserveBoundaryVerticesInParameterSpace(rawCells, annotatedLoops);
var compactCells = PlanarDomainPlanner.MergeConformingCells(conformingCells, domain.BoundaryVertices, sameSense);
return new SurfacePatch(faceId, new SurfaceMeshSupport(SurfaceMeshSupportKind.Plane, Plane: plane), loops, compactCells, sameSense,
TrimLoopData: annotatedLoops, PlanarPlannerPath: plannerPath);
}
var inner = inners[0];
var vertexById = vertices.ToDictionary(v => v.Id);
var outerIds = EnsureCounterClockwise(outer.VertexIds, outer.LocalCoordinates);
var innerIds = AlignRingToOuter(
outerIds,
EnsureCounterClockwise(inner.VertexIds, inner.LocalCoordinates),
vertexById);
var cells = new List<SurfaceMeshCell>(outerIds.Count * 2);
var middle = new int[outerIds.Count];
for (var i = 0; i < outerIds.Count; i++)
{
var outerPoint = vertexById[outerIds[i]].Position;
var innerPoint = vertexById[innerIds[i]].Position;
// One grading band prevents a giant cell from landing directly on
// the curved trim while keeping the zero-curvature plane cheap.
var point = new Point3D(
outerPoint.X * 0.40d + innerPoint.X * 0.60d,
outerPoint.Y * 0.40d + innerPoint.Y * 0.60d,
outerPoint.Z * 0.40d + innerPoint.Z * 0.60d);
middle[i] = nextVertexId++;
var uv = ToPlaneLocal(plane, point);
vertices.Add(new SurfaceMeshVertex(middle[i], point, uv.U, uv.V));
}
for (var i = 0; i < outerIds.Count; i++)
{
var next = (i + 1) % outerIds.Count;
cells.Add(new QuadCell(Orient([outerIds[i], outerIds[next], middle[next], middle[i]], sameSense), 0));
cells.Add(new QuadCell(Orient([middle[i], middle[next], innerIds[next], innerIds[i]], sameSense), 1));
}
return new SurfacePatch(faceId, new SurfaceMeshSupport(SurfaceMeshSupportKind.Plane, Plane: plane), loops, cells, sameSense, MaxRefinementLevel: 1,
TrimLoopData: annotatedLoops, PlanarPlannerPath: "PlanarDomain.EqualCountAnnularBand.M7Fallback", PlanarFeaturePlan: failedFeaturePlan);
}
internal static IReadOnlyList<SurfaceMeshCell> PreserveBoundaryVerticesInParameterSpace(
IReadOnlyList<SurfaceMeshCell> source,
IReadOnlyList<SurfaceMeshTrimLoop> loops)
{
var pending = new Queue<SurfaceMeshCell>(source);
var result = new List<SurfaceMeshCell>(source.Count);
while (pending.Count > 0)
{
var cell = pending.Dequeue();
if (cell is not TriangleCell triangle)
{
result.Add(cell);
continue;
}
var ids = triangle.VertexIds;
IReadOnlyList<int>? splitPath = null;
var splitEdge = -1;
for (var edge = 0; edge < 3 && splitPath is null; edge++)
{
splitPath = FindCollinearLoopPath(ids[edge], ids[(edge + 1) % 3], loops);
if (splitPath is not null) splitEdge = edge;
}
if (splitPath is null)
{
result.Add(cell);
continue;
}
var opposite = ids[(splitEdge + 2) % 3];
for (var index = 0; index + 1 < splitPath.Count; index++)
pending.Enqueue(new TriangleCell([splitPath[index], splitPath[index + 1], opposite], triangle.RefinementLevel, triangle.ParentCellId));
}
return result;
}
private static IReadOnlyList<int>? FindCollinearLoopPath(
int start,
int end,
IReadOnlyList<SurfaceMeshTrimLoop> loops)
{
foreach (var loop in loops)
{
var ids = loop.VertexIds;
var startIndex = Enumerable.Range(0, ids.Count).FirstOrDefault(index => ids[index] == start, -1);
var endIndex = Enumerable.Range(0, ids.Count).FirstOrDefault(index => ids[index] == end, -1);
if (startIndex < 0 || endIndex < 0) continue;
foreach (var direction in new[] { 1, -1 })
{
var path = new List<int> { start };
var index = startIndex;
while (path.Count <= ids.Count)
{
index = (index + direction + ids.Count) % ids.Count;
path.Add(ids[index]);
if (index == endIndex) break;
}
if (path.Count <= 2 || path[^1] != end) continue;
var a = loop.LocalCoordinates[startIndex];
var b = loop.LocalCoordinates[endIndex];
var chordU = b.U - a.U;
var chordV = b.V - a.V;
var chordLengthSquared = (chordU * chordU) + (chordV * chordV);
if (chordLengthSquared <= Epsilon) continue;
var isOnSegment = path.Skip(1).SkipLast(1).All(id =>
{
var localIndex = Enumerable.Range(0, ids.Count).First(index => ids[index] == id);
var point = loop.LocalCoordinates[localIndex];
var offsetU = point.U - a.U;
var offsetV = point.V - a.V;
var t = ((offsetU * chordU) + (offsetV * chordV)) / chordLengthSquared;
var residualU = point.U - (a.U + (chordU * t));
var residualV = point.V - (a.V + (chordV * t));
return t > 0d && t < 1d && double.Sqrt((residualU * residualU) + (residualV * residualV)) <= 1e-8d;
});
if (isOnSegment) return path;
}
}
return null;
}
private static SurfacePatch? TryBuildCylinderPatch(BrepBody body, FaceId faceId, bool sameSense, CylinderSurface cylinder, IReadOnlyDictionary<EdgeId, SharedEdgeSamplePlan> plans, SurfaceMeshPolicy policy, List<SurfaceMeshVertex> vertices, ref int nextVertexId)
{
var bounded = TryBuildFourSidedCylinderPatch(body, faceId, sameSense, cylinder, plans, vertices, ref nextVertexId);
if (bounded is not null) return bounded;
var loops = body.GetLoopIds(faceId);
if (loops.Count != 1) return null;
var coedges = body.GetCoedgeIds(loops[0]).Select(body.Topology.GetCoedge).ToArray();
var circles = coedges.Where(c => plans[c.EdgeId].CurveKind == CurveGeometryKind.Circle3).Select(c => plans[c.EdgeId]).ToArray();
if (circles.Length != 2 || circles[0].Samples.Count != circles[1].Samples.Count || !circles.All(p => p.IsClosed))
return TryBuildSampledBoundaryBand(body, faceId, sameSense,
new SurfaceMeshSupport(SurfaceMeshSupportKind.Cylinder, Cylinder: cylinder), plans, policy,
point => TryProjectPointToCylinderUv(cylinder, point), vertices, ref nextVertexId);
var rings = circles.Select(p => p.Samples.Take(p.Samples.Count - 1).ToArray()).ToArray();
if (rings[0].Length < 3) return null;
var v0 = (rings[0][0].Position - cylinder.Origin).Dot(cylinder.Axis.ToVector());
var v1 = (rings[1][0].Position - cylinder.Origin).Dot(cylinder.Axis.ToVector());
var bottom = v0 <= v1 ? rings[0] : rings[1];
var top = v0 <= v1 ? rings[1] : rings[0];
var cells = new List<SurfaceMeshCell>(bottom.Length);
for (var i = 0; i < bottom.Length; i++)
{
var next = (i + 1) % bottom.Length;
cells.Add(new QuadCell(Orient([bottom[i].Id, bottom[next].Id, top[next].Id, top[i].Id], sameSense)));
}
return new SurfacePatch(faceId, new SurfaceMeshSupport(SurfaceMeshSupportKind.Cylinder, Cylinder: cylinder), loops, cells, sameSense, HasPeriodicUSeam: true);
}
private static SurfacePatch? TryBuildConePatch(BrepBody body, FaceId faceId, bool sameSense, ConeSurface cone, IReadOnlyDictionary<EdgeId, SharedEdgeSamplePlan> plans, SurfaceMeshPolicy policy, List<SurfaceMeshVertex> vertices, ref int nextVertexId)
{
var bounded = TryBuildFourSidedConePatch(body, faceId, sameSense, cone, plans, vertices, ref nextVertexId);
if (bounded is not null) return bounded;
var apexPatch = TryBuildConeApexPatch(body, faceId, sameSense, cone, plans, vertices, ref nextVertexId);
if (apexPatch is not null) return apexPatch;
var loops = body.GetLoopIds(faceId);
var circles = loops
.SelectMany(loop => body.GetCoedgeIds(loop).Select(body.Topology.GetCoedge))
.Select(coedge => plans[coedge.EdgeId])
.Where(plan => plan.CurveKind == CurveGeometryKind.Circle3 && plan.IsClosed)
.DistinctBy(plan => plan.EdgeId)
.ToArray();
if (circles.Length != 2 || circles[0].Samples.Count != circles[1].Samples.Count)
{
return TryBuildSampledBoundaryBand(body, faceId, sameSense,
new SurfaceMeshSupport(SurfaceMeshSupportKind.Cone, Cone: cone), plans, policy,
point => TryProjectPointToConeUv(cone, point), vertices, ref nextVertexId);
}
var rings = circles.Select(plan => plan.Samples.Take(plan.Samples.Count - 1).ToArray()).ToArray();
if (rings[0].Length < 3)
{
return null;
}
var v0 = cone.AxialParameterFromPoint(rings[0][0].Position);
var v1 = cone.AxialParameterFromPoint(rings[1][0].Position);
if (!double.IsFinite(v0) || !double.IsFinite(v1) || double.Abs(v1 - v0) <= Epsilon)
{
return null;
}
var lower = v0 <= v1 ? rings[0] : rings[1];
var upper = v0 <= v1 ? rings[1] : rings[0];
var cells = new List<SurfaceMeshCell>(lower.Length);
for (var i = 0; i < lower.Length; i++)
{
var next = (i + 1) % lower.Length;
cells.Add(new QuadCell(Orient([lower[i].Id, lower[next].Id, upper[next].Id, upper[i].Id], sameSense)));
}
return new SurfacePatch(
faceId,
new SurfaceMeshSupport(SurfaceMeshSupportKind.Cone, Cone: cone),
loops,
cells,
sameSense,
HasPeriodicUSeam: true);
}
/// <summary>A sector of a cone closed at its apex: two generators from the apex and the rim between them, as
/// one ring of quads round a central fan.</summary>
private static SurfacePatch? TryBuildConeSectorPatch(
BrepBody body,
FaceId faceId,
bool sameSense,
ConeSurface cone,
IReadOnlyDictionary<EdgeId, SharedEdgeSamplePlan> plans,
List<SurfaceMeshVertex> vertices,
ref int nextVertexId)
{
var loops = body.GetLoopIds(faceId);
if (loops.Count != 1) return null;
var coedges = body.GetCoedgeIds(loops[0]).Select(body.Topology.GetCoedge).ToArray();
if (coedges.Length != 3) return null;
var edgePlans = coedges.Select(coedge => plans[coedge.EdgeId]).ToArray();
if (edgePlans.Count(plan => plan.CurveKind == CurveGeometryKind.Circle3) != 1
|| edgePlans.Count(plan => plan.CurveKind == CurveGeometryKind.Line3) != 2)
return null;
var boundary = FlattenLoop(coedges, plans).ToArray();
var vertexById = vertices.ToDictionary(vertex => vertex.Id);
var apexIndex = Array.FindIndex(boundary,
id => (vertexById[id].Position - cone.Apex).Length <= Epsilon);
if (apexIndex < 0) return null;
var ordered = Enumerable.Range(0, boundary.Length)
.Select(offset => boundary[(apexIndex + offset) % boundary.Length])
.ToArray();
var projected = ordered.Skip(1)
.Select(id => TryProjectPointToConeUv(cone, vertexById[id].Position))
.ToArray();
if (projected.Any(value => value is null)) return null;
var chainUv = UnwrapPeriodicU(projected.Select(value => value!.Value).ToArray());
var apexV = cone.AxialParameterFromPoint(cone.Apex);
var uv = new (double U, double V)[ordered.Length];
uv[0] = ((chainUv[0].U + chainUv[^1].U) * 0.5d, apexV);
for (var index = 1; index < uv.Length; index++) uv[index] = chainUv[index - 1];
if (double.Abs(SignedArea(uv)) <= Epsilon) return null;
var center = (U: uv.Average(value => value.U), V: uv.Average(value => value.V));
const double boundaryBandFraction = 0.18d;
var innerIds = new int[ordered.Length];
for (var index = 0; index < ordered.Length; index++)
{
var innerUv = (
U: uv[index].U + ((center.U - uv[index].U) * boundaryBandFraction),
V: uv[index].V + ((center.V - uv[index].V) * boundaryBandFraction));
innerIds[index] = nextVertexId++;
vertices.Add(new SurfaceMeshVertex(innerIds[index], cone.Evaluate(innerUv.U, innerUv.V), innerUv.U, innerUv.V));
}
var cells = new List<SurfaceMeshCell>((ordered.Length * 2) + 1);
for (var index = 0; index < ordered.Length; index++)
{
var next = (index + 1) % ordered.Length;
cells.Add(new QuadCell(Orient([ordered[index], ordered[next], innerIds[next], innerIds[index]], sameSense), 1));
}
var centerId = nextVertexId++;
vertices.Add(new SurfaceMeshVertex(centerId, cone.Evaluate(center.U, center.V), center.U, center.V));
for (var index = 0; index < innerIds.Length; index++)
cells.Add(new TriangleCell(Orient([centerId, innerIds[index], innerIds[(index + 1) % innerIds.Length]], sameSense), 1));
return new SurfacePatch(
faceId,
new SurfaceMeshSupport(SurfaceMeshSupportKind.Cone, Cone: cone),
loops,
cells,
sameSense,
MaxRefinementLevel: 1,
HasPeriodicUSeam: false,
TrimLoopData: [new SurfaceMeshTrimLoop(loops[0], ordered, uv, false, SignedArea(uv))]);
}
private static SurfacePatch? TryBuildConeApexPatch(
BrepBody body,
FaceId faceId,
bool sameSense,
ConeSurface cone,
IReadOnlyDictionary<EdgeId, SharedEdgeSamplePlan> plans,
List<SurfaceMeshVertex> vertices,
ref int nextVertexId)
{
// A cone closed at its apex: one loop of the seam (a generator) walked down from the apex and back up, and
// the rim between, in one or more arcs. Meshed as rings in (u, v): the apex, then one ring per seam sample
// down to the rim. Each ring starts and ends on the seam's own vertex, so the seam stays manifold.
var loops = body.GetLoopIds(faceId);
if (loops.Count != 1) return null;
var coedges = body.GetCoedgeIds(loops[0]).Select(body.Topology.GetCoedge).ToArray();
if (coedges.Length < 3) return null;
var seamEdges = coedges.GroupBy(c => c.EdgeId).Where(g => g.Count() == 2).Select(g => g.Key).ToArray();
// Without a seam the face is a sector between two generators.
if (seamEdges.Length == 0) return TryBuildConeSectorPatch(body, faceId, sameSense, cone, plans, vertices, ref nextVertexId);
if (seamEdges.Length != 1 || plans[seamEdges[0]].CurveKind != CurveGeometryKind.Line3) return null;
if (coedges.Any(c => c.EdgeId != seamEdges[0] && plans[c.EdgeId].CurveKind != CurveGeometryKind.Circle3)) return null;
var vertexById = vertices.ToDictionary(vertex => vertex.Id);
int[] Ids(Coedge c) { var ids = plans[c.EdgeId].Samples.Select(x => x.Id).ToArray(); if (c.IsReversed) Array.Reverse(ids); return ids; }
bool AtApex(int id) => (vertexById[id].Position - cone.Apex).Length <= Epsilon;
// Start the loop at the seam walked down from the apex.
var down = Array.FindIndex(coedges, c => c.EdgeId == seamEdges[0] && AtApex(Ids(c)[0]));
if (down < 0) return null;
var ordered = Enumerable.Range(0, coedges.Length).Select(k => coedges[(down + k) % coedges.Length]).ToArray();
if (ordered[^1].EdgeId != seamEdges[0]) return null;
var seam = Ids(ordered[0]);
var rim = new List<int> { seam[^1] };
foreach (var arc in ordered[1..^1])
{
var ids = Ids(arc);
if (ids[0] != rim[^1]) return null;
rim.AddRange(ids[1..]);
}
if (rim[^1] != seam[^1] || rim.Count < 4) return null;
var rimUv = rim.Select(id => TryProjectPointToConeUv(cone, vertexById[id].Position)).ToArray();
if (rimUv.Any(value => value is null)) return null;
var unwrapped = UnwrapPeriodicU(rimUv.Select(value => value!.Value).ToArray());
if (double.Abs(double.Abs(unwrapped[^1].U - unwrapped[0].U) - 2d * double.Pi) > 1e-6) return null;
var apexV = cone.AxialParameterFromPoint(cone.Apex);
var seamV = seam.Select((id, k) => k == 0 ? apexV : TryProjectPointToConeUv(cone, vertexById[id].Position)?.V).ToArray();
if (seamV.Any(v => v is null)) return null;
// Rows from just below the apex to the rim: row k sits at the seam's k-th sample.
var rows = new List<int[]>();
for (var k = 1; k < seam.Length; k++)
{
if (k == seam.Length - 1) { rows.Add(rim.ToArray()); break; }
var row = new int[rim.Count];
row[0] = row[^1] = seam[k];
for (var index = 1; index < rim.Count - 1; index++)
{
var (u, v) = (unwrapped[index].U, seamV[k]!.Value);
row[index] = nextVertexId++;
vertices.Add(new SurfaceMeshVertex(row[index], cone.Evaluate(u, v), u, v));
}
rows.Add(row);
}
// The trim loop as walked: down the seam at the rim's first u, round the rim, up the seam at its last.
var loopIds = new List<int>(); var loopUv = new List<(double U, double V)>();
for (var k = 0; k < seam.Length - 1; k++) { loopIds.Add(seam[k]); loopUv.Add((unwrapped[0].U, seamV[k]!.Value)); }
for (var index = 0; index < rim.Count - 1; index++) { loopIds.Add(rim[index]); loopUv.Add(unwrapped[index]); }
for (var k = seam.Length - 1; k >= 1; k--) { loopIds.Add(seam[k]); loopUv.Add((unwrapped[^1].U, seamV[k]!.Value)); }
var uv = loopUv.ToArray();
if (double.Abs(SignedArea(uv)) <= Epsilon) return null;
// Cells are wound counter-clockwise in (u, v), then turned to the face's sense, as in the other patches: the
// loop's own walking direction is not trusted for it (a source file's face sense may disagree with it).
var ccw = SignedArea(uv) > 0;
int[] Wind(int[] ids) => ccw ? ids : ids.Reverse().ToArray();
var cells = new List<SurfaceMeshCell>();
var apex = seam[0];
for (var index = 0; index < rim.Count - 1; index++)
cells.Add(new TriangleCell(Orient(Wind([rows[0][index], rows[0][index + 1], apex]), sameSense), 1));
for (var k = 0; k + 1 < rows.Count; k++)
for (var index = 0; index < rim.Count - 1; index++)
cells.Add(new QuadCell(Orient(Wind([rows[k + 1][index], rows[k + 1][index + 1], rows[k][index + 1], rows[k][index]]), sameSense), 1));
return new SurfacePatch(
faceId,
new SurfaceMeshSupport(SurfaceMeshSupportKind.Cone, Cone: cone),
loops,
cells,
sameSense,
MaxRefinementLevel: 1,
HasPeriodicUSeam: false,
TrimLoopData: [new SurfaceMeshTrimLoop(loops[0], loopIds, uv, false, SignedArea(uv))]);
}
private static SurfacePatch? TryBuildSampledBoundaryBand(
BrepBody body,
FaceId faceId,
bool sameSense,
SurfaceMeshSupport support,
IReadOnlyDictionary<EdgeId, SharedEdgeSamplePlan> plans,
SurfaceMeshPolicy policy,
Func<Point3D, (double U, double V)?> project,
List<SurfaceMeshVertex> vertices,
ref int nextVertexId)
{
var loops = body.GetLoopIds(faceId);
if (loops.Count != 1) return null;
var coedges = body.GetCoedgeIds(loops[0]).Select(body.Topology.GetCoedge).ToArray();
if (coedges.Length < 3) return null;
var outerIds = FlattenLoop(coedges, plans).ToArray();
if (outerIds.Length < 3) return null;
var vertexById = plans.SelectMany(plan => plan.Value.Samples).DistinctBy(vertex => vertex.Id).ToDictionary(vertex => vertex.Id);
var rawUv = outerIds.Select(id => project(vertexById[id].Position)).ToArray();
if (rawUv.Any(uv => uv is null)) return null;
var uv = UnwrapPeriodicU(rawUv.Select(value => value!.Value).ToArray());
for (var index = 0; index < outerIds.Length; index++)
{
var reconstructed = support.Kind switch
{
SurfaceMeshSupportKind.Cylinder when support.Cylinder is { } supportCylinder => supportCylinder.Evaluate(uv[index].U, uv[index].V),
SurfaceMeshSupportKind.Cone when support.Cone is { } cone => cone.Evaluate(uv[index].U, uv[index].V),
SurfaceMeshSupportKind.Torus when support.Torus is { } torus => torus.Evaluate(uv[index].U, uv[index].V),
_ => throw new InvalidOperationException("Sampled boundary triangulation requires an evaluable analytic support.")
};
if ((reconstructed - vertexById[outerIds[index]].Position).Length > policy.TargetChordalError) return null;
}
if (double.Abs(SignedArea(uv)) <= Epsilon) return null;
var trimLoop = new SurfaceMeshTrimLoop(loops[0], outerIds, uv, false, SignedArea(uv));
if (support.Cylinder is { } cylinder
&& TryBuildMonotoneCylinderStrip(faceId, sameSense, support, loops, trimLoop, cylinder, vertices, ref nextVertexId, out var structured))
return structured;
var flatBoundary = uv.Select(value => new Point3D(value.U, value.V, 0d)).ToArray();
var idByFlatPoint = flatBoundary.Select((point, index) => (point, index))
.GroupBy(item => item.point)
.ToDictionary(group => group.Key, group => outerIds[group.First().index]);
if (!PlanarPolygonTriangulator.TryTriangulateWithHoles(flatBoundary, [], new Vector3D(0d, 0d, 1d), out var flatPoints, out var triangleIndices, out _)
|| !flatPoints.All(idByFlatPoint.ContainsKey)) return null;
var triangulated = new List<SurfaceMeshCell>(triangleIndices.Count / 3);
for (var index = 0; index < triangleIndices.Count; index += 3)
triangulated.Add(new TriangleCell(Orient([
idByFlatPoint[flatPoints[triangleIndices[index]]],
idByFlatPoint[flatPoints[triangleIndices[index + 1]]],
idByFlatPoint[flatPoints[triangleIndices[index + 2]]]], sameSense), 1));
var cells = PreserveBoundaryVerticesInParameterSpace(triangulated, [trimLoop]);
return new SurfacePatch(faceId, support, loops, cells, sameSense, MaxRefinementLevel: 1, TrimLoopData: [trimLoop]);
}
private static bool TryBuildMonotoneCylinderStrip(
FaceId faceId,
bool sameSense,
SurfaceMeshSupport support,
IReadOnlyList<LoopId> loops,
SurfaceMeshTrimLoop trimLoop,
CylinderSurface cylinder,
List<SurfaceMeshVertex> vertices,
ref int nextVertexId,
out SurfacePatch patch)
{
patch = default!;
var ids = trimLoop.VertexIds;
var uv = trimLoop.LocalCoordinates;
var minU = uv.Min(point => point.U);
var maxU = uv.Max(point => point.U);
var spanU = maxU - minU;
if (spanU <= Epsilon) return false;
var uTolerance = double.Max(Epsilon, spanU * 1e-8d);
var leftIndices = Enumerable.Range(0, uv.Count).Where(index => double.Abs(uv[index].U - minU) <= uTolerance).ToArray();
var rightIndices = Enumerable.Range(0, uv.Count).Where(index => double.Abs(uv[index].U - maxU) <= uTolerance).ToArray();
if (leftIndices.Length < 2 || rightIndices.Length < 2) return false;
var lowerLeft = leftIndices.MinBy(index => uv[index].V);
var upperLeft = leftIndices.MaxBy(index => uv[index].V);
var lowerRight = rightIndices.MinBy(index => uv[index].V);
var upperRight = rightIndices.MaxBy(index => uv[index].V);
var lower = SelectLowerPath(ids, uv, lowerLeft, lowerRight);
var upper = SelectUpperPath(ids, uv, upperLeft, upperRight);
if (lower is null || upper is null) return false;
var leftSide = leftIndices.OrderBy(index => uv[index].V).Select(index => (Id: ids[index], Uv: uv[index])).ToArray();
var rightSide = rightIndices.OrderBy(index => uv[index].V).Select(index => (Id: ids[index], Uv: uv[index])).ToArray();
if (leftSide.Length != rightSide.Length || leftSide.Length < 2) return false;
for (var row = 0; row < leftSide.Length; row++)
{
var leftFraction = (leftSide[row].Uv.V - leftSide[0].Uv.V) / (leftSide[^1].Uv.V - leftSide[0].Uv.V);
var rightFraction = (rightSide[row].Uv.V - rightSide[0].Uv.V) / (rightSide[^1].Uv.V - rightSide[0].Uv.V);
if (double.Abs(leftFraction - rightFraction) > 1e-7d) return false;
}
var progress = lower.Select(item => NormalizeProgress(item.Uv.U, minU, spanU))
.Concat(upper.Select(item => NormalizeProgress(item.Uv.U, minU, spanU)))
.Append(0d).Append(1d)
.Order().Aggregate(new List<double>(), (result, value) =>
{
if (result.Count == 0 || double.Abs(result[^1] - value) > 1e-10d) result.Add(value);
return result;
});
var rows = new List<StripRow>(leftSide.Length) { new(lower.Select(item => item.Id).ToArray(), lower.Select(item => NormalizeProgress(item.Uv.U, minU, spanU)).ToArray()) };
for (var row = 1; row + 1 < leftSide.Length; row++)
{
var fraction = (leftSide[row].Uv.V - leftSide[0].Uv.V) / (leftSide[^1].Uv.V - leftSide[0].Uv.V);
var rowIds = new int[progress.Count];
for (var column = 0; column < progress.Count; column++)
{
if (column == 0) rowIds[column] = leftSide[row].Id;
else if (column == progress.Count - 1) rowIds[column] = rightSide[row].Id;
else
{
var u = minU + (spanU * progress[column]);
var lowerV = InterpolateStripV(lower, u);
var upperV = InterpolateStripV(upper, u);
var v = lowerV + ((upperV - lowerV) * fraction);
rowIds[column] = nextVertexId++;
vertices.Add(new SurfaceMeshVertex(rowIds[column], cylinder.Evaluate(u, v), u, v));
}
}
rows.Add(new StripRow(rowIds, progress));
}
rows.Add(new StripRow(upper.Select(item => item.Id).ToArray(), upper.Select(item => NormalizeProgress(item.Uv.U, minU, spanU)).ToArray()));
var cells = new List<SurfaceMeshCell>();
for (var row = 0; row + 1 < rows.Count; row++)
ConnectStripRows(rows[row], rows[row + 1], sameSense, cells);
patch = new SurfacePatch(faceId, support, loops, cells, sameSense, MaxRefinementLevel: 1, TrimLoopData: [trimLoop]);
return true;
}
private sealed record StripRow(IReadOnlyList<int> Ids, IReadOnlyList<double> Progress);
private static IReadOnlyList<(int Id, (double U, double V) Uv)>? SelectLowerPath(
IReadOnlyList<int> ids, IReadOnlyList<(double U, double V)> uv, int start, int end)
=> SelectMonotonePath(ids, uv, start, end, chooseLower: true);
private static IReadOnlyList<(int Id, (double U, double V) Uv)>? SelectUpperPath(
IReadOnlyList<int> ids, IReadOnlyList<(double U, double V)> uv, int start, int end)
=> SelectMonotonePath(ids, uv, start, end, chooseLower: false);
private static IReadOnlyList<(int Id, (double U, double V) Uv)>? SelectMonotonePath(
IReadOnlyList<int> ids, IReadOnlyList<(double U, double V)> uv, int start, int end, bool chooseLower)
{
var candidates = new List<IReadOnlyList<(int Id, (double U, double V) Uv)>>();
foreach (var direction in new[] { 1, -1 })
{
var path = new List<(int Id, (double U, double V) Uv)> { (ids[start], uv[start]) };
var index = start;
while (path.Count <= ids.Count)
{
index = (index + direction + ids.Count) % ids.Count;
path.Add((ids[index], uv[index]));
if (index == end) break;
}
if (path[^1].Id != ids[end]) continue;
if (path[0].Uv.U > path[^1].Uv.U) path.Reverse();
if (path.Zip(path.Skip(1), (a, b) => b.Uv.U + 1e-9d >= a.Uv.U).All(value => value)) candidates.Add(path);
}
if (candidates.Count == 0) return null;
return chooseLower
? candidates.OrderBy(path => path.Average(item => item.Uv.V)).First()
: candidates.OrderByDescending(path => path.Average(item => item.Uv.V)).First();
}
private static double NormalizeProgress(double u, double minU, double spanU)
=> double.Clamp((u - minU) / spanU, 0d, 1d);
private static double InterpolateStripV(IReadOnlyList<(int Id, (double U, double V) Uv)> chain, double u)
{
for (var index = 0; index + 1 < chain.Count; index++)
{
var a = chain[index].Uv;
var b = chain[index + 1].Uv;
if (u < a.U - Epsilon || u > b.U + Epsilon) continue;
if (double.Abs(b.U - a.U) <= Epsilon) return (a.V + b.V) * 0.5d;
var fraction = (u - a.U) / (b.U - a.U);
return a.V + ((b.V - a.V) * fraction);
}
return u <= chain[0].Uv.U ? chain[0].Uv.V : chain[^1].Uv.V;
}
private static void ConnectStripRows(StripRow lower, StripRow upper, bool sameSense, ICollection<SurfaceMeshCell> cells)
{
var lowerIndex = 0;
var upperIndex = 0;
while (lowerIndex + 1 < lower.Ids.Count || upperIndex + 1 < upper.Ids.Count)
{
var nextLower = lowerIndex + 1 < lower.Progress.Count ? lower.Progress[lowerIndex + 1] : double.PositiveInfinity;
var nextUpper = upperIndex + 1 < upper.Progress.Count ? upper.Progress[upperIndex + 1] : double.PositiveInfinity;
if (double.Abs(nextLower - nextUpper) <= 1e-10d)
{
var oldLower = lowerIndex++;
var oldUpper = upperIndex++;
cells.Add(new QuadCell(Orient([lower.Ids[oldLower], lower.Ids[lowerIndex], upper.Ids[upperIndex], upper.Ids[oldUpper]], sameSense), 1));
}
else if (nextLower < nextUpper)
{
var oldLower = lowerIndex++;
cells.Add(new TriangleCell(Orient([lower.Ids[oldLower], lower.Ids[lowerIndex], upper.Ids[upperIndex]], sameSense), 1));
}
else
{
var oldUpper = upperIndex++;
cells.Add(new TriangleCell(Orient([lower.Ids[lowerIndex], upper.Ids[upperIndex], upper.Ids[oldUpper]], sameSense), 1));
}
}
}
private static IReadOnlyList<(double U, double V)> UnwrapPeriodicU(IReadOnlyList<(double U, double V)> values)
{
if (values.Count == 0) return [];
var result = new (double U, double V)[values.Count];
result[0] = values[0];
for (var index = 1; index < values.Count; index++)
{
var u = values[index].U;
while (u - result[index - 1].U > double.Pi) u -= 2d * double.Pi;
while (u - result[index - 1].U < -double.Pi) u += 2d * double.Pi;
result[index] = (u, values[index].V);
}
return result;
}
private static SurfacePatch? TryBuildFourSidedCylinderPatch(BrepBody body, FaceId faceId, bool sameSense, CylinderSurface cylinder, IReadOnlyDictionary<EdgeId, SharedEdgeSamplePlan> plans, List<SurfaceMeshVertex> vertices, ref int nextVertexId)
{
for (var offset = 0; offset < 4; offset++)
{
if (!TryGetFourSidedBoundary(body, faceId, plans, out var boundary, offset)) continue;
if (boundary.TopKind is not (CurveGeometryKind.Circle3 or CurveGeometryKind.BSpline3)
|| boundary.BottomKind is not (CurveGeometryKind.Circle3 or CurveGeometryKind.BSpline3)
|| boundary.LeftKind != CurveGeometryKind.Line3 || boundary.RightKind != CurveGeometryKind.Line3) continue;
var patch = BuildFourSidedPatch(faceId, sameSense, new SurfaceMeshSupport(SurfaceMeshSupportKind.Cylinder, Cylinder: cylinder), body.GetLoopIds(faceId), boundary,
point => TryProjectPointToCylinderUv(cylinder, point),
(u, v) => cylinder.Evaluate(u, v), vertices, ref nextVertexId,
hasPeriodicUSeam: false);
if (patch is not null) return patch;
}
return null;
}
private static SurfacePatch? TryBuildFourSidedConePatch(BrepBody body, FaceId faceId, bool sameSense, ConeSurface cone, IReadOnlyDictionary<EdgeId, SharedEdgeSamplePlan> plans, List<SurfaceMeshVertex> vertices, ref int nextVertexId)
{
for (var offset = 0; offset < 4; offset++)
{
if (!TryGetFourSidedBoundary(body, faceId, plans, out var boundary, offset)) continue;
if (boundary.TopKind is not (CurveGeometryKind.Circle3 or CurveGeometryKind.BSpline3)
|| boundary.BottomKind is not (CurveGeometryKind.Circle3 or CurveGeometryKind.Hyperbola3 or CurveGeometryKind.BSpline3)
|| boundary.LeftKind != CurveGeometryKind.Line3 || boundary.RightKind != CurveGeometryKind.Line3) continue;
var patch = BuildFourSidedPatch(faceId, sameSense, new SurfaceMeshSupport(SurfaceMeshSupportKind.Cone, Cone: cone), body.GetLoopIds(faceId), boundary,
point => TryProjectPointToConeUv(cone, point),
(u, v) => cone.Evaluate(u, v), vertices, ref nextVertexId,
hasPeriodicUSeam: false);
if (patch is not null) return patch;
}
return null;
}
private sealed record FourSidedBoundary(
SharedEdgeSamplePlan TopPlan, SharedEdgeSamplePlan RightPlan, SharedEdgeSamplePlan BottomPlan, SharedEdgeSamplePlan LeftPlan,
IReadOnlyList<SurfaceMeshVertex> Top, IReadOnlyList<SurfaceMeshVertex> Right, IReadOnlyList<SurfaceMeshVertex> Bottom, IReadOnlyList<SurfaceMeshVertex> Left)
{
public CurveGeometryKind TopKind => TopPlan.CurveKind;
public CurveGeometryKind BottomKind => BottomPlan.CurveKind;
public CurveGeometryKind LeftKind => LeftPlan.CurveKind;
public CurveGeometryKind RightKind => RightPlan.CurveKind;
}
private static bool TryGetFourSidedBoundary(BrepBody body, FaceId faceId, IReadOnlyDictionary<EdgeId, SharedEdgeSamplePlan> plans, out FourSidedBoundary boundary, int startOffset = 0, bool allowClosed = false)
{
boundary = default!;
var loops = body.GetLoopIds(faceId);
if (loops.Count != 1) return false;
var sourceCoedges = body.GetCoedgeIds(loops[0]).Select(body.Topology.GetCoedge).ToArray();
var coedges = sourceCoedges.Length == 4
? Enumerable.Range(0, 4).Select(index => sourceCoedges[(index + startOffset) % 4]).ToArray()
: sourceCoedges;
if (coedges.Length != 4 || (!allowClosed && coedges.Any(coedge => plans[coedge.EdgeId].IsClosed))) return false;
IReadOnlyList<SurfaceMeshVertex> Samples(Coedge coedge)
{
var samples = plans[coedge.EdgeId].Samples.ToArray();
if (coedge.IsReversed) Array.Reverse(samples);
return samples;
}
var top = Samples(coedges[0]); var right = Samples(coedges[1]);
var bottom = Samples(coedges[2]).Reverse().ToArray(); var left = Samples(coedges[3]).Reverse().ToArray();
if (top.Count < 2 || top.Count != bottom.Length || right.Count != left.Length ||
top[0].Id != left[0].Id || top[^1].Id != right[0].Id || bottom[0].Id != left[^1].Id || bottom[^1].Id != right[^1].Id) return false;
boundary = new(plans[coedges[0].EdgeId], plans[coedges[1].EdgeId], plans[coedges[2].EdgeId], plans[coedges[3].EdgeId], top, right, bottom, left);
return true;
}
private static SurfacePatch? BuildFourSidedPatch(
FaceId faceId, bool sameSense, SurfaceMeshSupport support, IReadOnlyList<LoopId> loops, FourSidedBoundary boundary,
Func<Point3D, (double U, double V)?> project, Func<double, double, Point3D> evaluate, List<SurfaceMeshVertex> vertices, ref int nextVertexId, bool hasPeriodicUSeam,
bool periodicV = false)
{
var columns = boundary.Top.Count;
var rows = boundary.Left.Count;
var topUv = boundary.Top.Select(sample => project(sample.Position)).ToArray();
var bottomUv = boundary.Bottom.Select(sample => project(sample.Position)).ToArray();
if (topUv.Any(uv => uv is null) || bottomUv.Any(uv => uv is null)) return null;
var grid = new SurfaceMeshVertex[rows, columns];
for (var column = 0; column < columns; column++) { grid[0, column] = boundary.Top[column]; grid[rows - 1, column] = boundary.Bottom[column]; }
for (var row = 0; row < rows; row++) { grid[row, 0] = boundary.Left[row]; grid[row, columns - 1] = boundary.Right[row]; }
for (var row = 1; row < rows - 1; row++)
{
var t = row / (double)(rows - 1);
for (var column = 1; column < columns - 1; column++)
{
var top = topUv[column]!.Value; var bottom = bottomUv[column]!.Value;
var u = InterpolateAngle(top.U, bottom.U, t);
// A torus's V is its minor angle: across a tube that crosses V = 0 the short way round is the patch.
var v = periodicV ? InterpolateAngle(top.V, bottom.V, t) : top.V + ((bottom.V - top.V) * t);
var point = evaluate(u, v);
grid[row, column] = new SurfaceMeshVertex(nextVertexId++, point, u, v);
vertices.Add(grid[row, column]);
}
}
var cells = new List<SurfaceMeshCell>((rows - 1) * (columns - 1));
for (var row = 0; row < rows - 1; row++)
for (var column = 0; column < columns - 1; column++)
cells.Add(new QuadCell(Orient([grid[row, column].Id, grid[row, column + 1].Id, grid[row + 1, column + 1].Id, grid[row + 1, column].Id], sameSense)));
return new SurfacePatch(faceId, support, loops, cells, sameSense, HasPeriodicUSeam: hasPeriodicUSeam);
}
// One bounded convex spherical chart, optionally transformed by the exact
// ellipsoid frame. Shared trim samples stay immutable; concentric inner rings
// refine only the face interior, so neighboring edge/face identities agree.
private static SurfacePatch? TryBuildConvexQuadricPatch(BrepBody body, FaceId face, bool sameSense,
SurfaceMeshSupport support, IReadOnlyDictionary<EdgeId, SharedEdgeSamplePlan> plans, SurfaceMeshPolicy policy,
List<SurfaceMeshVertex> vertices, ref int nextId)
{
var loops = body.GetLoopIds(face);
if (loops.Count != 1) return null;
var boundary = new List<SurfaceMeshVertex>();
foreach (var coedge in body.GetCoedgeIds(loops[0]).Select(body.Topology.GetCoedge))
{
var plan = plans[coedge.EdgeId];
if (plan.CurveKind is not (CurveGeometryKind.Circle3 or CurveGeometryKind.Ellipse3)) return null;
var reversed = coedge.IsReversed ^ !body.Bindings.GetEdgeBinding(coedge.EdgeId).OrientedEdgeSense;
var samples = reversed ? plan.Samples.Reverse().ToArray() : plan.Samples;
boundary.AddRange(samples.Take(samples.Count - 1));
}
if (boundary.Count < 3) return null;
var ellipsoid = support.Ellipsoid;
var sphere = support.Sphere;
Vector3D Unit(Point3D point) => ellipsoid is not null ? ellipsoid.UnitCoordinates(point)
: (point - sphere!.Value.Center) * (1 / sphere.Value.Radius);
Point3D World(Vector3D unit) => ellipsoid is not null ? ellipsoid.FromUnit(Point3D.Origin + unit)
: sphere!.Value.Center + unit * sphere.Value.Radius;
var directions = boundary.Select(p => Unit(p.Position)).ToArray();
if (directions.Any(v => double.Abs(v.Length - 1) > 1e-8)) return null;
var sum = directions.Aggregate(Vector3D.Zero, (a, b) => a + b);
if (!Direction3D.TryCreate(sum, out var direction)) return null;
var center = direction.ToVector();
if (directions.Any(d => center.Dot(d) < .1)) return null;
var area = Vector3D.Zero;
for (var i = 0; i < directions.Length; i++) area += directions[i].Cross(directions[(i + 1) % directions.Length]);
if (area.Dot(center) < 0) { boundary.Reverse(); Array.Reverse(directions); }
// A small convex normal polygon is the admitted domain. Concave or
// self-crossing loops cannot be replaced by this radial chart.
for (var i = 0; i < directions.Length; i++)
{
var normal = directions[i].Cross(directions[(i + 1) % directions.Length]);
if (normal.Length < 1e-12) continue;
if (directions.Any(d => normal.Dot(d) < -1e-9)) return null;
}
var maxRadius = ellipsoid is null ? sphere!.Value.Radius : double.Max(ellipsoid.RadiusX, double.Max(ellipsoid.RadiusY, ellipsoid.RadiusZ));
var minRadius = ellipsoid is null ? maxRadius : double.Min(ellipsoid.RadiusX, double.Min(ellipsoid.RadiusY, ellipsoid.RadiusZ));
var angle = double.Min(policy.TargetNormalErrorRadians * minRadius / maxRadius, double.Sqrt(8 * policy.TargetChordalError / maxRadius)) / 2;
if (!double.IsFinite(angle) || angle <= 0) return null;
var count = double.Ceiling(2 * directions.Max(d => double.Acos(double.Clamp(center.Dot(d), -1, 1))) / angle);
if (!double.IsFinite(count) || count > policy.MaxBoundarySamples) return null;
var rings = System.Math.Max(1, (int)count);
var centerId = nextId++; vertices.Add(new(centerId, World(center)));
var previous = Array.Empty<int>(); var cells = new List<SurfaceMeshCell>();
for (var ring = 1; ring <= rings; ring++)
{
var current = new int[boundary.Count]; var t = (double)ring / rings;
for (var i = 0; i < current.Length; i++)
{
if (ring == rings) { current[i] = boundary[i].Id; continue; }
var q = Direction3D.Create(center * (1 - t) + directions[i] * t).ToVector();
current[i] = nextId++; vertices.Add(new(current[i], World(q)));
}
for (var i = 0; i < current.Length; i++)
{
var j = (i + 1) % current.Length;
if (ring == 1) cells.Add(new TriangleCell(Orient([centerId, current[i], current[j]], sameSense)));
else cells.Add(new QuadCell(Orient([previous[i], current[i], current[j], previous[j]], sameSense)));
}
previous = current;
}
return new(face, support, loops, cells, sameSense, ChartId: "ConvexQuadricTrim");
}
private static bool TryBuildSphereCharts(
BrepBody body,
FaceId faceId,
bool sameSense,
SphereSurface sphere,
List<SurfaceMeshVertex> vertices,
ref int nextVertexId,
out IReadOnlyList<SurfacePatch> patches)
{
// A six-chart cube sphere has no pole fan. Integer cube-grid coordinates
// are the seam identity: neighboring charts literally reuse vertex IDs.
if (body.GetLoopIds(faceId).Count != 0)
{
patches = [];
return false;
}
const int subdivisions = 6;
var seamVertices = new Dictionary<(int X, int Y, int Z), int>();
var byId = vertices.ToDictionary(vertex => vertex.Id);
var chartDefinitions = new[]
{
new CubeChart("+X", (1, 0, 0), (0, 1, 0), (0, 0, 1)),
new CubeChart("-X", (-1, 0, 0), (0, 0, 1), (0, 1, 0)),
new CubeChart("+Y", (0, 1, 0), (0, 0, 1), (1, 0, 0)),
new CubeChart("-Y", (0, -1, 0), (1, 0, 0), (0, 0, 1)),
new CubeChart("+Z", (0, 0, 1), (1, 0, 0), (0, 1, 0)),
new CubeChart("-Z", (0, 0, -1), (0, 1, 0), (1, 0, 0)),
};
var result = new List<SurfacePatch>(chartDefinitions.Length);
foreach (var chart in chartDefinitions)
{
var grid = new int[subdivisions + 1, subdivisions + 1];
for (var row = 0; row <= subdivisions; row++)
{
for (var column = 0; column <= subdivisions; column++)
{
var numeratorX = (chart.Normal.X * subdivisions) + (chart.U.X * ((2 * column) - subdivisions)) + (chart.V.X * ((2 * row) - subdivisions));
var numeratorY = (chart.Normal.Y * subdivisions) + (chart.U.Y * ((2 * column) - subdivisions)) + (chart.V.Y * ((2 * row) - subdivisions));
var numeratorZ = (chart.Normal.Z * subdivisions) + (chart.U.Z * ((2 * column) - subdivisions)) + (chart.V.Z * ((2 * row) - subdivisions));
var key = (numeratorX, numeratorY, numeratorZ);
if (!seamVertices.TryGetValue(key, out var id))
{
var cube = new Vector3D(numeratorX, numeratorY, numeratorZ);
var unit = cube / cube.Length;
var position = sphere.Center
+ (sphere.XAxis.ToVector() * (sphere.Radius * unit.X))
+ (sphere.YAxis.ToVector() * (sphere.Radius * unit.Y))
+ (sphere.Axis.ToVector() * (sphere.Radius * unit.Z));
id = nextVertexId++;
var vertex = new SurfaceMeshVertex(id, position, column / (double)subdivisions, row / (double)subdivisions);
vertices.Add(vertex);
byId.Add(id, vertex);
seamVertices.Add(key, id);
}
grid[row, column] = id;
}
}
var cells = new List<SurfaceMeshCell>(subdivisions * subdivisions);
for (var row = 0; row < subdivisions; row++)
{
for (var column = 0; column < subdivisions; column++)
{
cells.Add(new QuadCell(Orient([grid[row, column], grid[row, column + 1], grid[row + 1, column + 1], grid[row + 1, column]], sameSense)));
}
}
result.Add(new SurfacePatch(faceId, new SurfaceMeshSupport(SurfaceMeshSupportKind.Sphere, Sphere: sphere), [], cells, sameSense, ChartId: chart.Name));
}
patches = result;
return true;
}
private static SurfacePatch? TryBuildTorusPatch(
BrepBody body,
FaceId faceId,
bool sameSense,
TorusSurface torus,
IReadOnlyDictionary<EdgeId, SharedEdgeSamplePlan> plans,
SurfaceMeshPolicy policy,
List<SurfaceMeshVertex> vertices,
ref int nextVertexId)
{
// Two closed rings and one bounded arc used twice as a seam: a swept
// bend (minor rings, major seam) or a rounded rim (major rings, minor
// seam). Those rings do not imply a complete torus.
for (var offset = 0; offset < 4; offset++)
{
if (!TryGetFourSidedBoundary(body, faceId, plans, out var band, offset, allowClosed: true)
|| !band.TopPlan.IsClosed || !band.BottomPlan.IsClosed
|| band.LeftPlan.IsClosed || band.RightPlan.IsClosed
|| band.LeftPlan.EdgeId != band.RightPlan.EdgeId
|| band.TopKind != CurveGeometryKind.Circle3 || band.BottomKind != CurveGeometryKind.Circle3
|| band.LeftKind != CurveGeometryKind.Circle3) continue;
var ring = band.Top.Select(sample => TryProjectPointToTorusUv(torus, sample.Position)).ToArray();
var seam = band.Left.Select(sample => TryProjectPointToTorusUv(torus, sample.Position)).ToArray();
if (ring.Any(uv => uv is null) || seam.Any(uv => uv is null)) return null;
// The rings are minor circles and the seam a major arc (a swept bend), or the rings are major circles
// around the axis and the seam a minor arc (a rim rounded all the way round). Each grid point is the
// ring's parameter along it and the seam's across.
(double U, double V) At(int row, int column, bool majorRings) =>
majorRings ? (ring[column]!.Value.U, seam[row]!.Value.V) : (seam[row]!.Value.U, ring[column]!.Value.V);
bool? layout = null;
foreach (var majorRings in new[] { false, true })
{
var matches = true;
for (var column = 0; column < ring.Length && matches; column++)
{
var (u, v) = At(seam.Length - 1, column, majorRings);
matches = (torus.Evaluate(u, v) - band.Bottom[column].Position).Length <= 1e-7d;
}
if (matches) { layout = majorRings; break; }
}
if (layout is not { } majorRingLayout) return null;
var bandGrid = new int[seam.Length, ring.Length];
for (var row = 0; row < seam.Length; row++)
for (var column = 0; column < ring.Length; column++)
{
if (row == 0) bandGrid[row, column] = band.Top[column].Id;
else if (row == seam.Length - 1) bandGrid[row, column] = band.Bottom[column].Id;
else if (column == 0) bandGrid[row, column] = band.Left[row].Id;
else if (column == ring.Length - 1) bandGrid[row, column] = band.Right[row].Id;
else
{
var (u, v) = At(row, column, majorRingLayout);
bandGrid[row, column] = nextVertexId++;
vertices.Add(new SurfaceMeshVertex(bandGrid[row, column], torus.Evaluate(u, v), u, v));
}
}
var bandCells = new List<SurfaceMeshCell>();
for (var row = 0; row < seam.Length - 1; row++)
for (var column = 0; column < ring.Length - 1; column++)
{
int[] ids = [bandGrid[row,column],bandGrid[row,column+1],bandGrid[row+1,column+1],bandGrid[row+1,column]];
// The traversal can oppose the analytic support orientation; resolve the chart winding before
// applying the authoritative face sign.
var (u, v) = At(row, column, majorRingLayout);
var p = torus.Evaluate(u, v);
var along = At(row, column + 1, majorRingLayout); var across = At(row + 1, column, majorRingLayout);
var cross = (torus.Evaluate(along.U, along.V) - p).Cross(torus.Evaluate(across.U, across.V) - p);
if (cross.Dot(torus.Normal(u, v).ToVector()) < 0) Array.Reverse(ids);
bandCells.Add(new QuadCell(Orient(ids, sameSense)));
}
return new SurfacePatch(faceId, new SurfaceMeshSupport(SurfaceMeshSupportKind.Torus,Torus:torus), body.GetLoopIds(faceId), bandCells, sameSense, HasPeriodicVSeam:true);
}
// Root/concave fillet: four directed circle uses delimit a genuine
// bounded torus domain (major-angle across each split face, minor-angle
// across the fillet). Preserve that coedge ordering; reversing both
// contact rings would visually turn the trim inside-out.
if (TryGetFourSidedBoundary(body, faceId, plans, out var bounded)
&& bounded.TopKind == CurveGeometryKind.Circle3 && bounded.RightKind == CurveGeometryKind.Circle3
&& bounded.BottomKind == CurveGeometryKind.Circle3 && bounded.LeftKind == CurveGeometryKind.Circle3)
{
return BuildFourSidedPatch(faceId, sameSense, new SurfaceMeshSupport(SurfaceMeshSupportKind.Torus, Torus: torus), body.GetLoopIds(faceId), bounded,
point => TryProjectPointToTorusUv(torus, point), (u, v) => torus.Evaluate(u, v), vertices, ref nextVertexId,
hasPeriodicUSeam: false, periodicV: true);
}
if (body.GetLoopIds(faceId).Count != 1)
{
return null;
}
var seamPlans = body.GetCoedgeIds(body.GetLoopIds(faceId)[0])
.Select(body.Topology.GetCoedge)
.Select(coedge => plans[coedge.EdgeId])
.Where(plan => plan.CurveKind == CurveGeometryKind.Circle3 && plan.IsClosed)
.DistinctBy(plan => plan.EdgeId)
.ToArray();
if (seamPlans.Length != 2)
{
// Bounded CAD miter: two contact circles and two shared spline
// intersections. Reuse the parameter-space trim owner and its
// boundary IDs; never turn this into a complete-torus fallback.
var boundary = body.GetCoedgeIds(body.GetLoopIds(faceId)[0])
.Select(body.Topology.GetCoedge).Select(c => plans[c.EdgeId]).ToArray();
if (boundary.Length != 4 ||
boundary.Count(p => p.CurveKind == CurveGeometryKind.Circle3) != 2 ||
boundary.Count(p => p.CurveKind == CurveGeometryKind.BSpline3) != 2) return null;
(double U, double V)? Project(Point3D point)
{
var uv = TryProjectPointToTorusUv(torus, point);
if (uv is not { } value) return null;
return (value.U, value.V > double.Pi ? value.V - 2 * double.Pi : value.V);
}
var projected = boundary.SelectMany(p => p.Samples).Select(s => Project(s.Position)).ToArray();
if (projected.Any(p => p is null || double.Abs(p.Value.V) > double.Pi / 2 + 1e-8))
return null; // Only the regular outer half-tube; no pole or periodic V crossing.
return TryBuildSampledBoundaryBand(body, faceId, sameSense,
new SurfaceMeshSupport(SurfaceMeshSupportKind.Torus, Torus: torus), plans, policy,
Project, vertices, ref nextVertexId);
}
var parameters = seamPlans
.Select(plan => (Plan: plan, Samples: plan.Samples.Take(plan.Samples.Count - 1).Select(sample => (Sample: sample, Uv: TryProjectPointToTorusUv(torus, sample.Position))).ToArray()))
.ToArray();
if (parameters.Any(entry => entry.Samples.Any(sample => sample.Uv is null)))
{
return null;
}
var major = parameters.OrderByDescending(entry => CircularSpan(entry.Samples.Select(sample => sample.Uv!.Value.U))).First();
var minor = parameters.Single(entry => entry.Plan.EdgeId != major.Plan.EdgeId);
var uSegments = System.Math.Max(major.Samples.Length, ResolveCircleSegments(torus.MajorRadius + torus.MinorRadius, 2d * double.Pi, policy));
var vSegments = System.Math.Max(minor.Samples.Length, ResolveCircleSegments(torus.MinorRadius, 2d * double.Pi, policy));
var seamIds = new Dictionary<(int U, int V), SurfaceMeshVertex>();
AddTorusSeamSamples(major.Samples, uSegments, vSegments, seamIds);
AddTorusSeamSamples(minor.Samples, uSegments, vSegments, seamIds);
var grid = new int[uSegments, vSegments];
for (var uIndex = 0; uIndex < uSegments; uIndex++)
{
for (var vIndex = 0; vIndex < vSegments; vIndex++)
{
if (seamIds.TryGetValue((uIndex, vIndex), out var sampled))
{
grid[uIndex, vIndex] = sampled.Id;
continue;
}
var u = (2d * double.Pi * uIndex) / uSegments;
var v = (2d * double.Pi * vIndex) / vSegments;
var vertex = new SurfaceMeshVertex(nextVertexId++, torus.Evaluate(u, v), u, v);
vertices.Add(vertex);
grid[uIndex, vIndex] = vertex.Id;
}
}
var cells = new List<SurfaceMeshCell>(uSegments * vSegments);
for (var uIndex = 0; uIndex < uSegments; uIndex++)
{
for (var vIndex = 0; vIndex < vSegments; vIndex++)
{
var nextU = (uIndex + 1) % uSegments;
var nextV = (vIndex + 1) % vSegments;
cells.Add(new QuadCell(Orient([grid[uIndex, vIndex], grid[nextU, vIndex], grid[nextU, nextV], grid[uIndex, nextV]], sameSense)));
}
}
return new SurfacePatch(faceId, new SurfaceMeshSupport(SurfaceMeshSupportKind.Torus, Torus: torus), body.GetLoopIds(faceId), cells, sameSense, HasPeriodicUSeam: true, HasPeriodicVSeam: true);
}
private static void AddTorusSeamSamples(
IReadOnlyList<(SurfaceMeshVertex Sample, (double U, double V)? Uv)> samples,
int uSegments,
int vSegments,
IDictionary<(int U, int V), SurfaceMeshVertex> seamIds)
{
foreach (var (sample, uv) in samples)
{
if (uv is not { } value)
{
continue;
}
var u = ((int)System.Math.Round(value.U / (2d * double.Pi) * uSegments)) % uSegments;
var v = ((int)System.Math.Round(value.V / (2d * double.Pi) * vSegments)) % vSegments;
seamIds.TryAdd((U: u, V: v), sample);
}
}
private static (double U, double V)? TryProjectPointToTorusUv(TorusSurface torus, Point3D point)
{
var axis = torus.Axis.ToVector();
var offset = point - torus.Center;
var axial = offset.Dot(axis);
var planar = offset - (axis * axial);
var planarLength = planar.Length;
if (planarLength <= Epsilon)
{
return null;
}
var u = NormalizeAngle(double.Atan2(planar.Dot(torus.YAxis.ToVector()), planar.Dot(torus.XAxis.ToVector())));
var v = NormalizeAngle(double.Atan2(axial, planarLength - torus.MajorRadius));
return (u, v);
}
private static (double U, double V)? TryProjectPointToCylinderUv(CylinderSurface cylinder, Point3D point)
{
var offset = point - cylinder.Origin;
var v = offset.Dot(cylinder.Axis.ToVector());
var radial = offset - (cylinder.Axis.ToVector() * v);
if (radial.Length <= Epsilon) return null;
return (NormalizeAngle(double.Atan2(radial.Dot(cylinder.YAxis.ToVector()), radial.Dot(cylinder.XAxis.ToVector()))), v);
}
private static (double U, double V)? TryProjectPointToConeUv(ConeSurface cone, Point3D point)
{
var offset = point - cone.Apex;
var v = offset.Dot(cone.Axis.ToVector());
var radial = offset - (cone.Axis.ToVector() * v);
if (radial.Length <= Epsilon) return null;
var x = cone.ReferenceAxis.ToVector() - (cone.Axis.ToVector() * cone.ReferenceAxis.ToVector().Dot(cone.Axis.ToVector()));
if (!x.TryNormalize(out x)) return null;
var y = cone.Axis.ToVector().Cross(x);
return (NormalizeAngle(double.Atan2(radial.Dot(y), radial.Dot(x))), v);
}
private static double CircularSpan(IEnumerable<double> angles)
{
var values = angles.OrderBy(value => value).ToArray();
if (values.Length < 2)
{
return 0d;
}
return values.Zip(values.Skip(1), (a, b) => b - a).DefaultIfEmpty().Max();
}
private static double NormalizeAngle(double angle)
{
var normalized = angle % (2d * double.Pi);
return normalized < 0d ? normalized + (2d * double.Pi) : normalized;
}
private static double InterpolateAngle(double start, double end, double t)
{
var delta = end - start;
if (delta > double.Pi) delta -= 2d * double.Pi;
else if (delta < -double.Pi) delta += 2d * double.Pi;
return NormalizeAngle(start + (delta * t));
}
private readonly record struct CubeChart(string Name, (int X, int Y, int Z) Normal, (int X, int Y, int Z) U, (int X, int Y, int Z) V);
private static IReadOnlyList<int> FlattenLoop(IReadOnlyList<Coedge> coedges, IReadOnlyDictionary<EdgeId, SharedEdgeSamplePlan> plans)
{
var output = new List<int>();
foreach (var coedge in coedges)
{
var ids = plans[coedge.EdgeId].Samples.Select(s => s.Id).ToArray();
if (coedge.IsReversed) Array.Reverse(ids);
if (plans[coedge.EdgeId].IsClosed) ids = ids[..^1];
if (output.Count > 0 && ids.Length > 0 && output[^1] == ids[0]) ids = ids[1..];
output.AddRange(ids);
}
if (output.Count > 1 && output[0] == output[^1]) output.RemoveAt(output.Count - 1);
return output;
}
private static IReadOnlyList<SurfaceMeshBoundarySpan> BuildBoundarySpans(IReadOnlyList<Coedge> coedges, IReadOnlyDictionary<EdgeId, SharedEdgeSamplePlan> plans)
{
var spans = new List<SurfaceMeshBoundarySpan>(coedges.Count);
foreach (var coedge in coedges)
{
var samples = plans[coedge.EdgeId].Samples.Select(sample => sample.Id).ToArray();
if (coedge.IsReversed) Array.Reverse(samples);
if (plans[coedge.EdgeId].IsClosed) samples = samples[..^1];
if (samples.Length >= 2)
spans.Add(new SurfaceMeshBoundarySpan(coedge.EdgeId, samples[0], samples[^1], plans[coedge.EdgeId].CurveKind, samples.Length));
}
return spans;
}
private static (double U, double V) ToPlaneLocal(PlaneSurface plane, Point3D point)
{
var offset = point - plane.Origin;
return (offset.Dot(plane.UAxis.ToVector()), offset.Dot(plane.VAxis.ToVector()));
}
private static double SignedArea(IReadOnlyList<(double U, double V)> points)
=> Enumerable.Range(0, points.Count).Sum(i =>
{
var next = points[(i + 1) % points.Count];
return (points[i].U * next.V) - (next.U * points[i].V);
}) * 0.5d;
private static IReadOnlyList<int> EnsureCounterClockwise(IReadOnlyList<int> ids, IReadOnlyList<(double U, double V)> local)
=> SignedArea(local) >= 0d ? ids : ids.Reverse().ToArray();
private static IReadOnlyList<int> AlignRingToOuter(
IReadOnlyList<int> outerIds,
IReadOnlyList<int> innerIds,
IReadOnlyDictionary<int, SurfaceMeshVertex> vertexById)
{
// Loop orientation alone does not establish the cyclic phase. Pairing
// a rectangular loop that begins at a corner with a circle that begins
// on its +X axis can otherwise create a twisted annular strip whose
// quads overlap the hole. Select the deterministic cyclic shift with
// the shortest total spokes while preserving both loop orderings.
var bestShift = 0;
var bestCost = double.PositiveInfinity;
for (var shift = 0; shift < innerIds.Count; shift++)
{
var cost = 0d;
for (var i = 0; i < outerIds.Count; i++)
{
var delta = vertexById[outerIds[i]].Position - vertexById[innerIds[(i + shift) % innerIds.Count]].Position;
cost += delta.LengthSquared;
}
if (cost < bestCost - Epsilon)
{
bestCost = cost;
bestShift = shift;
}
}
return Enumerable.Range(0, innerIds.Count).Select(i => innerIds[(i + bestShift) % innerIds.Count]).ToArray();
}
private static IReadOnlyList<SurfaceMeshCell>? TryBuildConvexAnnularStitch(SurfaceMeshTrimLoop outer, SurfaceMeshTrimLoop inner, bool sameSense)
{
// Localized planar boundary adaptation for an unequal-count convex ring.
// It advances each authoritative boundary by normalized arc progress and
// emits a quad whenever both advance together; the unavoidable count
// mismatch is restricted to boundary triangles.
if (!IsConvex(outer.LocalCoordinates) || !IsConvex(inner.LocalCoordinates)) return null;
var outerIds = EnsureCounterClockwise(outer.VertexIds, outer.LocalCoordinates).ToArray();
var innerIds = EnsureCounterClockwise(inner.VertexIds, inner.LocalCoordinates).ToArray();
if (outerIds.Length < 3 || innerIds.Length < 3) return null;
innerIds = AlignUnequalRingInParameterSpace(outer, inner, outerIds, innerIds);
var cells = new List<SurfaceMeshCell>(outerIds.Length + innerIds.Length);
var outerIndex = 0; var innerIndex = 0;
while (outerIndex < outerIds.Length || innerIndex < innerIds.Length)
{
var nextOuter = (outerIndex + 1d) / outerIds.Length;
var nextInner = (innerIndex + 1d) / innerIds.Length;
var outerCurrent = outerIds[outerIndex % outerIds.Length];
var innerCurrent = innerIds[innerIndex % innerIds.Length];
if (double.Abs(nextOuter - nextInner) <= Epsilon)
{
cells.Add(new QuadCell(Orient([outerCurrent, outerIds[(outerIndex + 1) % outerIds.Length], innerIds[(innerIndex + 1) % innerIds.Length], innerCurrent], sameSense)));
outerIndex++; innerIndex++;
}
else if (nextOuter < nextInner)
{
cells.Add(new TriangleCell(Orient([outerCurrent, outerIds[(outerIndex + 1) % outerIds.Length], innerCurrent], sameSense)));
outerIndex++;
}
else
{
cells.Add(new TriangleCell(Orient([outerCurrent, innerIds[(innerIndex + 1) % innerIds.Length], innerCurrent], sameSense)));
innerIndex++;
}
}
return cells;
}
private static int[] AlignUnequalRingInParameterSpace(
SurfaceMeshTrimLoop outer,
SurfaceMeshTrimLoop inner,
IReadOnlyList<int> outerIds,
IReadOnlyList<int> innerIds)
{
var outerLocal = outer.VertexIds.Select((id, index) => (id, local: outer.LocalCoordinates[index]))
.ToDictionary(item => item.id, item => item.local);
var innerLocal = inner.VertexIds.Select((id, index) => (id, local: inner.LocalCoordinates[index]))
.ToDictionary(item => item.id, item => item.local);
var bestShift = 0;
var bestCost = double.PositiveInfinity;
for (var shift = 0; shift < innerIds.Count; shift++)
{
var cost = 0d;
for (var outerIndex = 0; outerIndex < outerIds.Count; outerIndex++)
{
var innerIndex = (int)double.Floor((double)outerIndex * innerIds.Count / outerIds.Count);
var a = outerLocal[outerIds[outerIndex]];
var b = innerLocal[innerIds[(innerIndex + shift) % innerIds.Count]];
var du = a.U - b.U;
var dv = a.V - b.V;
cost += (du * du) + (dv * dv);
}
if (cost < bestCost - Epsilon)
{
bestCost = cost;
bestShift = shift;
}
}
return Enumerable.Range(0, innerIds.Count).Select(index => innerIds[(index + bestShift) % innerIds.Count]).ToArray();
}
private static bool IsConvex(IReadOnlyList<(double U, double V)> points)
{
if (points.Count < 3) return false;
var sign = 0;
for (var index = 0; index < points.Count; index++)
{
var a = points[index]; var b = points[(index + 1) % points.Count]; var c = points[(index + 2) % points.Count];
var cross = ((b.U - a.U) * (c.V - b.V)) - ((b.V - a.V) * (c.U - b.U));
if (double.Abs(cross) <= Epsilon) continue;
var current = cross > 0d ? 1 : -1;
if (sign != 0 && sign != current) return false;
sign = current;
}
return sign != 0;
}
private static bool IsRectangle(IReadOnlyList<(double U, double V)> points)
{
var minU = points.Min(p => p.U); var maxU = points.Max(p => p.U);
var minV = points.Min(p => p.V); var maxV = points.Max(p => p.V);
return points.All(p => double.Abs(p.U - minU) < 1e-7d || double.Abs(p.U - maxU) < 1e-7d || double.Abs(p.V - minV) < 1e-7d || double.Abs(p.V - maxV) < 1e-7d);
}
private static IReadOnlyList<int> Orient(IReadOnlyList<int> ids, bool sameSense) => sameSense ? ids : ids.Reverse().ToArray();
private static DisplayFaceMeshPatch LowerPatch(SurfaceMeshDocument document, SurfacePatch patch)
{
var vertexById = document.Vertices.ToDictionary(v => v.Id);
var positions = new List<Point3D>(); var normals = new List<Vector3D>(); var indices = new List<int>(); var local = new Dictionary<int, int>();
var normal = ResolvePatchNormal(document, patch, vertexById);
int Add(int id) { if (local.TryGetValue(id, out var existing)) return existing; var index = positions.Count; positions.Add(vertexById[id].Position); normals.Add(normal(vertexById[id].Position)); local[id] = index; return index; }
foreach (var cell in patch.Cells)
{
var ids = cell.VertexIds;
if (cell.Kind == SurfaceMeshCellKind.Quad)
{
var a = Add(ids[0]); var b = Add(ids[1]); var c = Add(ids[2]); var d = Add(ids[3]);
AppendQuadTriangles(positions, [a, b, c, d], indices);
}
else if (cell.Kind == SurfaceMeshCellKind.Triangle) indices.AddRange([Add(ids[0]), Add(ids[1]), Add(ids[2])]);
else if (ids.Count >= 3)
{
if (TryTriangulateBoundaryCell(patch, ids, vertexById, out var localIndices))
{
for (var i = 0; i < localIndices.Count; i += 3)
indices.AddRange([Add(ids[localIndices[i]]), Add(ids[localIndices[i + 1]]), Add(ids[localIndices[i + 2]])]);
}
else
{
throw new InvalidOperationException($"Face {patch.FaceId.Value} has an untriangulable boundary cell; no centre fan is permitted.");
}
}
}
return new DisplayFaceMeshPatch(patch.FaceId, positions, normals, indices, DisplayFaceMeshSource.SurfaceMeshIr);
}
private static bool TryTriangulateBoundaryCell(SurfacePatch patch, IReadOnlyList<int> ids,
IReadOnlyDictionary<int, SurfaceMeshVertex> vertices, out IReadOnlyList<int> indices)
{
indices = [];
var points = ids.Select(id => vertices[id]).ToArray();
if (patch.Support.Plane is { } plane)
return PlanarPolygonTriangulator.TryTriangulate(points.Select(p => p.Position).ToArray(),
patch.IsAlignedWithSupport ? plane.Normal.ToVector() : -plane.Normal.ToVector(), out indices, out _);
if (points.Any(p => p.U is null || p.V is null)) return false;
var uv = points.Select(p => new Point3D(p.U!.Value, p.V!.Value, 0)).ToArray();
var area = Enumerable.Range(0, uv.Length).Sum(i => uv[i].X * uv[(i + 1) % uv.Length].Y - uv[(i + 1) % uv.Length].X * uv[i].Y);
// Cell order already carries resolved face orientation. Preserve it in the
// local chart rather than reinterpreting STEP source SAME_SENSE.
return PlanarPolygonTriangulator.TryTriangulate(uv, new Vector3D(0, 0, area >= 0 ? 1 : -1), out indices, out _);
}
// Shared final lowering for retained quad cells. Prefer the shorter valid diagonal;
// ties are deterministic and no vertex is introduced away from the support.
internal static void AppendQuadTriangles(IReadOnlyList<Point3D> positions, IReadOnlyList<int> ids, List<int> indices)
{
var a = ids[0]; var b = ids[1]; var c = ids[2]; var d = ids[3];
var ac = (positions[a] - positions[c]).Length; var bd = (positions[b] - positions[d]).Length;
var acValid = TriangleAreaMagnitude(positions[a], positions[b], positions[c]) > Epsilon && TriangleAreaMagnitude(positions[a], positions[c], positions[d]) > Epsilon;
var bdValid = TriangleAreaMagnitude(positions[a], positions[b], positions[d]) > Epsilon && TriangleAreaMagnitude(positions[b], positions[c], positions[d]) > Epsilon;
// Symmetric ruled quads have equal diagonals. Ignore only rounding-scale
// length differences so platform libm does not select a different split.
var tieTolerance = 1e-12d * double.Max(1d, double.Max(ac, bd));
if (acValid && (!bdValid || ac <= bd + tieTolerance)) indices.AddRange([a, b, c, a, c, d]);
else indices.AddRange([a, b, d, b, c, d]);
}
private static Func<Point3D, Vector3D> ResolvePatchNormal(SurfaceMeshDocument document, SurfacePatch patch, IReadOnlyDictionary<int, SurfaceMeshVertex> vertices)
{
return patch.Support.Kind switch
{
SurfaceMeshSupportKind.Plane when patch.Support.Plane is { } plane => _ => patch.IsAlignedWithSupport ? plane.Normal.ToVector() : -plane.Normal.ToVector(),
SurfaceMeshSupportKind.Cylinder when patch.Support.Cylinder is { } cylinder => p =>
{
var offset = p - cylinder.Origin;
var angle = double.Atan2(offset.Dot(cylinder.YAxis.ToVector()), offset.Dot(cylinder.XAxis.ToVector()));
var exact = cylinder.Normal(angle).ToVector();
return patch.IsAlignedWithSupport ? exact : -exact;
},
SurfaceMeshSupportKind.Cone when patch.Support.Cone is { } cone => p =>
{
var offset = p - cone.Apex;
var axis = cone.Axis.ToVector();
var radial = offset - (axis * offset.Dot(axis));
var reference = cone.ReferenceAxis.ToVector();
var xAxis = reference - (axis * reference.Dot(axis));
var yAxis = axis.Cross(xAxis);
var angle = radial.Length <= Epsilon ? 0d : double.Atan2(radial.Dot(yAxis), radial.Dot(xAxis));
var exact = cone.Normal(angle).ToVector();
return patch.IsAlignedWithSupport ? exact : -exact;
},
SurfaceMeshSupportKind.Ellipsoid when patch.Support.Ellipsoid is { } ellipsoid => p =>
patch.IsAlignedWithSupport ? ellipsoid.Normal(p) : -ellipsoid.Normal(p),
SurfaceMeshSupportKind.Sphere when patch.Support.Sphere is { } sphere => p =>
{
var exact = Direction3D.Create(p - sphere.Center).ToVector();
return patch.IsAlignedWithSupport ? exact : -exact;
},
SurfaceMeshSupportKind.Torus when patch.Support.Torus is { } torus => p =>
{
var uv = TryProjectPointToTorusUv(torus, p) ?? throw new InvalidOperationException("Torus mesh vertex is not on its exact support.");
var exact = torus.Normal(uv.U, uv.V).ToVector();
return patch.IsAlignedWithSupport ? exact : -exact;
},
_ => throw new InvalidOperationException($"Patch {patch.FaceId.Value} has no exact support evaluator."),
};
}
private static int CountLoweredTriangles(SurfaceMeshDocument document, SurfacePatch patch) => patch.Cells.Sum(c => c.Kind switch { SurfaceMeshCellKind.Quad => 2, SurfaceMeshCellKind.Triangle => 1, _ => c.VertexIds.Count >= 3 ? c.VertexIds.Count - 2 : 0 });
private static double TriangleAreaMagnitude(Point3D a, Point3D b, Point3D c) => (b - a).Cross(c - a).Length * 0.5d;
private static SurfaceMeshMetrics ComputeMetrics(IReadOnlyList<SurfaceMeshVertex> vertices, IReadOnlyList<SurfacePatch> patches, IReadOnlyList<SharedEdgeSamplePlan> plans, int triangleCount)
{
var lengths = plans.SelectMany(p => p.Samples.Zip(p.Samples.Skip(1), (a, b) => (a.Position - b.Position).Length)).ToArray();
var cells = patches.SelectMany(p => p.Cells).ToArray();
var payload = string.Join("|", vertices.OrderBy(v => v.Id).Select(v => $"{v.Id}:{v.Position.X:R},{v.Position.Y:R},{v.Position.Z:R}")) + string.Join("|", cells.Select(c => $"{c.Kind}:{string.Join(',', c.VertexIds)}"));
var hash = Convert.ToHexString(SHA256.HashData(Encoding.UTF8.GetBytes(payload))).ToLowerInvariant();
var boundaryPolygons = cells.Count(c => c.Kind == SurfaceMeshCellKind.BoundaryPolygon);
var approximateBytes = (vertices.Count * (sizeof(int) + (3 * sizeof(double)))) + (cells.Sum(c => c.VertexIds.Count) * sizeof(int));
return new SurfaceMeshMetrics(patches.Count, plans.Count, cells.Length, cells.Count(c => c.Kind == SurfaceMeshCellKind.Quad), cells.Count(c => c.Kind != SurfaceMeshCellKind.Quad), triangleCount, cells.Select(c => c.RefinementLevel).DefaultIfEmpty().Max(), plans.Select(p => p.MaxChordalDeviation).DefaultIfEmpty().Max(), 0, lengths.DefaultIfEmpty().Min(), lengths.DefaultIfEmpty().Max(), hash, boundaryPolygons, 0, triangleCount, 0d, 0d, approximateBytes);
}
}
public static class SurfaceMeshIrValidator
{
public static bool TryValidate(SurfaceMeshDocument document, out string? failure)
{
var vertexById = document.Vertices.ToDictionary(v => v.Id);
var vertices = vertexById.Keys.ToHashSet();
if (vertices.Count != document.Vertices.Count) { failure = "SurfaceMeshIR vertex IDs are not unique."; return false; }
foreach (var boundary in document.SharedBoundaries)
{
if (boundary.Samples.Count < 2 || boundary.Uses.Count == 0) { failure = $"Shared edge {boundary.EdgeId.Value} has no complete sample/use contract (samples={boundary.Samples.Count}, uses={boundary.Uses.Count})."; return false; }
if (boundary.Samples.Any(sample => !vertices.Contains(sample.Id))) { failure = $"Shared edge {boundary.EdgeId.Value} references a missing vertex."; return false; }
if (boundary.IsClosed && boundary.Samples[0].Id != boundary.Samples[^1].Id) { failure = $"Closed shared edge {boundary.EdgeId.Value} does not reuse its endpoint vertex."; return false; }
}
foreach (var cell in document.Patches.SelectMany(p => p.Cells))
{
if (cell.VertexIds.Count < 3 || cell.VertexIds.Any(id => !vertices.Contains(id))) { failure = "A cell references an invalid or insufficient vertex set."; return false; }
if (cell.VertexIds.Distinct().Count() != cell.VertexIds.Count) { failure = "A cell repeats a vertex."; return false; }
var points = cell.VertexIds.Select(id => vertexById[id].Position).ToArray();
if (PolygonAreaMagnitude(points) <= 1e-14d) { failure = "A cell has zero area."; return false; }
}
if (document.Patches.Any(patch => patch.TrimLoopData is { Count: > 1 } && patch.Cells.Count == 0)) { failure = "A trimmed patch has no covering cells."; return false; }
failure = null; return true;
}
private static double PolygonAreaMagnitude(IReadOnlyList<Point3D> points)
{
var normal = new Vector3D(0d, 0d, 0d);
for (var i = 0; i < points.Count; i++) normal += new Vector3D(points[i].X, points[i].Y, points[i].Z).Cross(new Vector3D(points[(i + 1) % points.Count].X, points[(i + 1) % points.Count].Y, points[(i + 1) % points.Count].Z));
return normal.Length * 0.5d;
}
}