DelaunayTetrahedralization

Remarks

Bowyer–Watson is fifteen lines of idea: to insert a point, delete every cell whose circumsphere contains it, and fill the cavity that leaves by joining the point to each of the cavity's boundary faces. All of the difficulty is in "contains", which is a question about a sign, and which floating point cannot answer. Every predicate here is exact, and every tie a degenerate input produces is broken by InSphere the same way every time — which is what a grid of points needs, since its cells are cospherical eight at a time and no amount of tolerance decides anything about them.

The Delaunay property is what makes this worth building rather than any old tetrahedralisation. A cell's circumsphere is empty of other points, so the four points a position interpolates between are its natural neighbours rather than whichever four a mesh generator happened to group. For light probes that is the difference between indirect light that changes smoothly as an object walks across a room and light that jumps when it crosses an arbitrary seam.

Construction is enclosed rather than incremental at the hull. The points are inserted into a tetrahedron large enough to hold them all, and the cells touching its four corners are dropped at the end. That is the textbook arrangement and it has a textbook hazard: an enclosure that is not large enough silently loses cells near the hull. So the result is checked — FillsConvexHull is true only when what came out uses every point and its boundary is closed and convex, which for a complex whose cells are all Delaunay is exactly the statement that it is the Delaunay tetrahedralisation of the input. A failed check grows the enclosure and rebuilds.

Duplicate positions are merged, and Vertices is the merged set — indices into it, not into what the caller passed. Input that has no volume at all (fewer than four points, or all of them on one plane) has no tetrahedralisation, which is reported by IsDegenerate rather than by an exception: a floor's worth of probes at one height is a thing an author can legitimately make, and the caller has a fallback for it.

Fields and properties (6)

• public ReadOnlySpan<Vector3> Vertices

  The distinct input positions, in first-seen order. Cell indices refer to these.

• public ReadOnlySpan<int> CellVertices

  Four vertex indices per cell, positively oriented.

• public ReadOnlySpan<int> CellNeighbours

  Four neighbour cell indices per cell — the cell across the face opposite each vertex, or -1 where that face is on the boundary.

• public int CellCount

  How many cells there are.

• public bool IsDegenerate

  Whether the input has no volume, and so no tetrahedralisation.

• public bool FillsConvexHull

  Whether the cells fill the convex hull of the input — the check that says this is the Delaunay tetrahedralisation and not merely a Delaunay-looking piece of one.

Methods (3)

• public static DelaunayTetrahedralization Build(ReadOnlySpan<Vector3> positions)

  Builds the tetrahedralisation of .

• public bool TryFind(Vector3 position, out int cell, out Vector4 weights)

  Finds the cell containing and the barycentric weights of the position within it.

• public bool TryFind(Vector3 position, int hint, out int cell, out Vector4 weights)

  TryFind, starting the walk from a hint.

Used by (3)

• DelaunayTetrahedralizationTestsVixen.Core.Mathematics.Tests
• IncrementalVixen.Core.Mathematics
• LightProbeVolumeVixen.Rendering