Why a tie policy matters
A tetrahedral interpolant specifies a scalar value everywhere in each cell. To display its level set we still need an algorithm that produces polygons and agrees at cell boundaries. The previous section established the regular section shapes; here we turn that result into a finite construction, including a reproducible decision when a vertex is exactly at the requested level. A decision about equality changes the mathematical object, so it must be recorded along with the mesh, rather than hidden in a floating-point comparison.
Setting and the global level rule
Definition 13.1.1
(Conforming tetrahedral complex with vertex data)
Let be a finite conforming geometric tetrahedral complex in : every tetrahedron is nondegenerate, and the intersection of two simplices is empty or a common face. Each vertex has a globally shared position and scalar value . On each tetrahedron is the affine interpolant of its four values. Adjacent affine pieces agree on their common face because they agree at its three vertices. The domain is the union of its tetrahedra.
No manifold or closed-boundary assumption is made yet. Treat input numbers and the constructions below as exact real quantities; rounding and robust computational predicates need separate treatment.
Definition 13.1.2
(Global level shift)
Given a requested level , choose one positive for the entire mesh. If at least one vertex has , let
If all vertex values equal , choose any . Set . For reproducibility, one possible rule is when exists, and otherwise, in the units of . This fixed rule is illustrative: a recorded positive value satisfying the inequalities is sufficient. Every vertex with now lies strictly below ; all vertices originally strictly above or below retain their original side. No vertex has value . This is a global level shift, not a separate per-cell tie break and not a perturbation of the nodal values.
The output represents , not necessarily . A flat tetrahedron with all four values gives containing that entire tetrahedron but empty there. Even as , the one-sided surface need not recover an isolated point, a flat cell, or every part of . A different shift or a downward shift can produce another surface. Applications requiring the exact degenerate level must represent its lower- and higher-dimensional strata, or choose and document a different policy; this algorithm does not claim to do so.
Construction
Definition 13.1.3
(Crossed edge and edge key)
An edge is crossed when and have opposite signs. Its edge key is the pair of unique vertex IDs, stored sorted, so that both orders of the endpoints name the same edge.
Assign each vertex the sign of . For each edge with opposite signs, compute exactly once, using a canonical global edge key ,
The denominator is nonzero and . Store the resulting point under the edge key; reversing the endpoint order gives the same point. Process each tetrahedron as follows.
- If all four signs agree, emit nothing.
- Otherwise gather the three or four crossed-edge points. Each tetrahedral face has either zero or two crossed edges; connect its two points when present. These face segments form the cyclic boundary of the section polygon. Emit its triangle if there are three vertices. If there are four, split it along either diagonal, for example the diagonal whose sorted pair of global edge keys is lexicographically smaller. Orient emitted triangles to agree with when a consistent normal toward increasing field is wanted. A crossed cell cannot have zero gradient.
- Reuse the same intersection indices on common edges. The quadrilateral diagonal is internal to its own tetrahedron, so its choice does not alter a shared-face segment. Distinct cells need not choose a common diagonal.
Here a global edge key uses unique vertex IDs and the sorted pair of those IDs; compare diagonal endpoint keys lexicographically after sorting each pair. This makes the triangulation deterministic once the IDs and are fixed. Exact arithmetic defines the mathematical output. In a floating-point implementation, merely evaluating the same formula twice is not a proof of equality; shared storage prevents independently rounded copies, while the side predicates and input representation still need a stated robust policy.
Concept lensCombinatorial
The cell as a sign pattern
For a cell, only the vector of four signs of matters. Of the sixteen patterns, two are constant and emit nothing, eight have one vertex on one side (one against three) and give a triangle, and six split two against two and give a quadrilateral. Since , the algorithm is a sixteen-entry table plus one interpolation formula per crossed edge.
Theorem 13.1.4
(Exact section and shared-face agreement)
Under the assumptions above, the union of emitted closed triangles is exactly . On every shared triangular face, both incident tetrahedra induce the same section, including its endpoints and segment.
Proof
(Section vertices lie on crossed edges, and shared faces agree)
For a tetrahedron, an affine value is a convex combination of its four vertex values. If every value is strictly on one side of , so is every point of the cell. Otherwise cuts the tetrahedron by a plane: cannot be constant in a cell with both signs. The intersection is a convex polygon. Each vertex of this polygon lies on a tetrahedral edge: an intersection point in the interior of the tetrahedron has a small planar disk around it inside the section, and a point in a face interior has a small line segment through it within that face, so neither can be extreme. Conversely, a crossed-edge point is extreme in the section. Indeed, if it is a proper convex combination of two tetrahedron points, their barycentric coordinates at the other two vertices must vanish because those coordinates are nonnegative. Both points are therefore on that edge; the level plane meets the edge only once, so both equal the crossing. Along an edge, affine interpolation has exactly the displayed crossing when endpoint signs differ and no crossing otherwise. One-versus-three signs give three crossed edges; two-versus-two give four. Every crossed face supplies exactly one boundary segment, so joining them in cyclic order produces the entire polygon. A diagonal partitions a convex quadrilateral into two closed triangles without changing its union.
On a common face, both affine restrictions agree at all three vertices, hence agree everywhere. Their common level is either empty or the same segment with the same two global crossed-edge keys. Reuse makes the endpoint indices identical, and each cell emits that segment as polygon boundary. Taking the union over finitely many cells therefore gives exactly without an intercell geometric crack.
Proof X-ray
Which assumption each step of the proof uses
Read the proof as a list of assumptions and the places where each is spent. First, no vertex value equals . This is why every sign is strict, every crossed edge has a nonzero denominator with , and the section of a cell never contains a vertex of the cell; if a vertex had value exactly , the section could be a point, an edge or a whole face, and the description by crossed edges would fail. Second, the one non-obvious move is the extreme-point argument: it turns the geometric set inside a cell into a finite list, the crossed-edge points, so that the whole construction becomes a sign table plus one formula per edge. Third, conformity of the complex and the global edge keys are used only in the second paragraph: two cells agree on a common face because both affine restrictions agree at its three vertices, and the shared keys make them name the same endpoints. No statement about gradients or about manifolds enters anywhere. Fourth, the argument closes by finiteness: a finite union of closed polygons, adjacent ones meeting along identical segments. It proves that the pieces fit together; it does not prove that the result is a closed surface.
Theorem 13.1.5
(Running time and memory)
Under the same assumptions, the algorithm terminates in expected time when global edge lookup takes constant expected time; memory is linear in those counts plus the output. Sorting edge keys instead yields a deterministic time bound, where count tetrahedra, edges and vertices.
Proof
(Counting the work per cell)
Each cell visits a fixed number of vertices, edges and faces and emits at most two triangles. A global pass finds , and the stated hash-table or sorting bounds follow. Expected hash performance assumes an appropriate hash implementation; sorting provides the stated worst-case comparison bound.
These results do not require the complex itself to be a three-dimensional manifold, and they do not assert that the extracted surface is closed. A section can reach the domain boundary, and a nonmanifold complex can also produce a nonmanifold section. Face agreement alone therefore cannot establish a closed 2-manifold. A manifold or closedness claim requires additional hypotheses and a separate local analysis.
Worked examples
Worked example 13.1.6
(One tetrahedron and the effect of a tied vertex)
Let , , and have values , with . Here , so take . The positive vertices relative to are ; the negative vertices are . The four crossings in cyclic order, following faces, are
For instance, on the interpolation parameter from is . Triangulating with either diagonal gives the same quadrilateral in the plane . At the original level the section instead includes and has a different shape: it is not the quadrilateral just computed. The shift is therefore a modeling choice visible even in exact arithmetic.
Worked example 13.1.7
(Two tetrahedra share one face)
Let , , , and . The tetrahedra and share face . Set values , , , , , and request . The rule gives . Both cells use and , and both attach their polygon to the same segment between them. In , the third crossing is , forming a triangle. In , the other crossings are and ; these four points form a quadrilateral. Its internal diagonal does not change the common segment. The shared geometry follows from a common face and field, not from assuming that the cells have matching gradients.
Worked example 13.1.8
(A flat face beside a crossed cell (edge case))
Take , , , , with values , , , and request . Then and the rule gives . In only is above , so the crossed edges are , , , each with , and the emitted triangle has corners , , . This is correct, since on and the triangle lies in . In all four values are below , so nothing is emitted. The common face has , so it lies entirely in the original level set , but it contains no point of : the two cells agree trivially, with no crack, and the emitted triangle stays at height above the flat face.
Counterexample mode
Equality can hide a nonmanifold level
The claim: if the domain is a manifold and adjacent cells agree exactly on shared faces, then every exact level set is a piecewise-linear 2-manifold. Consider on a cube around the origin, with a conforming tetrahedral subdivision respecting the planes and . The function is affine on each cell, and its zero set consists of the planes and within the cube. Along their common -axis four half-sheets meet. A small sphere centered on the axis intersects these half-sheets in four arcs joining its north and south poles; each pole has degree four in this link graph. The link of an interior point of a piecewise-linear 2-manifold must be a circle, but this graph is not a circle. Thus this original level is not a piecewise-linear 2-manifold along that axis, even though the underlying cube is a manifold and adjacent cells agree exactly. A positive regular shift changes this crossing; it is not a repair of the original set's topology. Consistent face triangulation and numerical equality do not establish manifoldness at a vertex level.
A separate ambiguity appears if neighboring cubes split their shared square face along different diagonals: they do not form a conforming tetrahedral complex. With alternating high and low corner values, the two piecewise-affine face reconstructions can connect crossings differently. Identical corner samples alone do not choose a diagonal or an interpolant. Decide a globally conforming subdivision before extraction; changing it can change the reconstructed field.
Common mistakes
Common mistake
(Measuring the crossing parameter from the wrong endpoint)
For the edge of the first example, is measured from , giving . Using the parameter measured from , namely , in the same formula gives , where . Always check that the interpolated point satisfies .
Common mistake
(Reading the output as the level set at )
If a tetrahedron has all four values equal to , the exact level set contains the whole cell, while the algorithm with emits nothing there. The output describes for the recorded ; it is not the level when vertices tie with .
Common mistake
(Expecting a closed surface)
A single tetrahedron with values at yields a quadrilateral whose four sides lie on the four faces of the cell. The extracted surface has a boundary wherever the section meets the boundary of , and face agreement says nothing about closedness.
Exercises
Quick check
(A tetrahedron has values and requested level zero. Apply the deterministic rule. How many crossed edges are there and what are their interpolation parameters from the value-two vertex?)
First find and .
Solution · Answer
Here and . Only the value-two vertex is above , so the three edges at that vertex are crossed. The parameters from that vertex are toward each zero-valued endpoint and toward the value-minus-two endpoint. The section is a triangle. The two tied vertices were assigned the same side by shifting the level globally.
Quick check
(In the adjacent-cell example, verify and explain whether the two cells' gradients must agree on .)
Apply the crossing formula to the edge .
Solution · Answer
From toward , , hence . The corresponding point is . The two restrictions to agree, but normal derivatives can differ across the face, so the full gradients need not agree.
Quick check
(All vertices have value five and the requested level is five. What do the original and shifted level sets contain? Why does the algorithm terminate?)
Use the rule for when no vertex differs from .
Solution · Answer
The original level set is the whole domain, since every cell interpolant is constant five. The rule uses , , and emits nothing, so the shifted level set is empty. There are finitely many cells and each needs a bounded number of comparisons, so the procedure terminates even though the exact original level is three-dimensional.
Quick check
(A finite tetrahedral complex has cells and its vertices all avoid . Give an upper bound on emitted triangles. Is a closed surface guaranteed?)
Count the triangles one cell can contribute.
Solution · Answer
At most , since each cell produces at most one quadrilateral, split into two triangles. A level may meet the domain boundary, and the domain itself need not be a manifold. Neither closedness nor manifoldness follows from this count.