TriangleTree

Remarks

Every query is branch-and-bound, and that is the whole point. A distance field of 32³ samples over a mesh of ten thousand triangles is 32 768 closest-point queries and about a million rays; done against every triangle each time it is ten billion triangle tests, and done against a hierarchy it is a few hundred million. The tree is not an optimisation of the bake, it is what makes the bake finish.

Built by median split on the longest axis, not by SAH. A surface-area heuristic builds a better tree and takes longer to build, and this tree is queried a million times and thrown away — the build is not the cost. Median splitting is also trivially deterministic, which the byte-identical-rebake test depends on: ties in a centroid comparison break on triangle index, so the tree does not depend on the sort's stability.

⚠ It lived in Vixen.Rendering.DistanceFields, whose own remarks said it belonged here as soon as a second caller existed. That caller is docs/plan/41-automatic-retopology.md § D12: attribute transfer drives closest-point queries against the conditioned source mesh, and the geometry assembly cannot reference the distance-field one. Nothing about the structure changed in the move — especially not the tie-break above, which a rebake's byte-identity rests on. ⚠ § D12 credits MeshCollision with "already has the shape of one"; it does not, and never did — it is shell labelling and one axis-aligned box per shell, with no tree and no query. This is the acceleration structure that claim was reaching for.

Fields and properties (2)

• public BoundingBox Bounds

  The box every triangle fits inside.

• public int TriangleCount

  How many triangles the tree holds.

Methods (7)

• public TriangleTree(ReadOnlySpan<Vector3> vertices, ReadOnlySpan<int> indices)

  Builds a tree over a triangle soup.

• public float DistanceSquared(Vector3 point)

  The squared distance from a point to the nearest triangle.

• public ClosestTriangle Closest(Vector3 point)

  The nearest triangle to a point, where on it the nearest point lies, and how far.

• public bool Raycast(Vector3 origin, Vector3 direction, out bool backface)

  The nearest triangle a ray strikes, and which of its faces.

• public TriangleHit Raycast(Vector3 origin, Vector3 direction)

  The nearest triangle a ray strikes, and everything about the hit.

• public static Vector3 ClosestPointOnTriangle(Vector3 point, Vector3 a, Vector3 b, Vector3 c)

  The point on a triangle nearest another point.

• public static Vector3 ClosestPointOnTriangle(Vector3 point, Vector3 a, Vector3 b, Vector3 c, out Vector3 barycentric)

  The point on a triangle nearest another point, and its barycentric coordinates.

Used by (11)

• AtlasRasterVixen.Geometry.Remeshing
• AttributeTransferVixen.Geometry.Remeshing
• DensityFieldVixen.Geometry.Remeshing
• MapBakerVixen.Geometry.Remeshing
• MeshDistanceFieldBakerVixen.Rendering.DistanceFields
• SeamGraphVixen.Geometry.Uv
• SourceSurfaceVixen.Geometry.Remeshing
• TransferFixturesVixen.Geometry.Remeshing.Tests
• TriangleTreeScaleTestsVixen.Core.Mathematics.Tests
• TriangleTreeTestsVixen.Core.Mathematics.Tests
• PaintProjectionVixen.Editor.Texturing