public static class ExactPredicatesThe two geometric predicates a Delaunay tetrahedralisation is made of — which side of a plane a point is on, and whether a point is inside a circumsphere — answered exactly.
No guide page documents this yet — the page shows what the code says about itself.
Remarks
These return a sign, not a magnitude, and the sign is the exact one. That is the whole point. A predicate evaluated in floating point returns a number that is nearly right, and "nearly right" has no meaning for a question whose answer is one of three values: an in-sphere test that says -1e-19 where the truth is 0 has not made a small error, it has given the wrong answer. Incremental construction then builds a cavity that is not star-shaped, and the mesh that comes out is not a mesh.
Filtered, not slow. Every predicate first evaluates in alongside a bound on its own rounding error — the permanent of the same expression, which is what you get by replacing every term with its absolute value. If the result is further from zero than the bound, the sign is certain and the answer is already in hand; that is the case for essentially every call. Only when the two overlap does the exact path run, and it runs in BigInteger over the inputs rescaled to integers, where there is no rounding at all.
The error bounds below are deliberately several times larger than the tightest derivable ones. A bound that is too large costs a rare exact evaluation; a bound that is too small is a wrong answer that nothing reports. Only one of those is worth economising on.
Inputs must be finite. A NaN or an infinity makes both the filter and the rescaling meaningless, and callers that read positions from content are expected to reject them before they get here — DelaunayTetrahedralization does.
Methods (3)
public static int Orient3D(Vector3 a, Vector3 b, Vector3 c, Vector3 d)Which side of the plane through , and the point lies on.
public static int InSphere(Vector3 a, Vector3 b, Vector3 c, Vector3 d, Vector3 e)Whether is inside the sphere through , , and .
public static int InSphere(Vector3 a, Vector3 b, Vector3 c, Vector3 d, Vector3 e, int indexA, int indexB, int indexC, int indexD, int indexE)InSphere, with cospherical ties broken by the points' indices rather than left at zero.
Used by (5)
- DelaunayTetrahedralizationVixen.Core.Mathematics
- DelaunayTetrahedralizationTestsVixen.Core.Mathematics.Tests
- ExactPredicateTestsVixen.Core.Mathematics.Tests
- IncrementalVixen.Core.Mathematics
- PlaneTableVixen.Geometry