Exact planes from snapped vertices, so faces that meet at a corner meet exactly #252

Problem

The exact CSG rounds every plane of a brush on its own (ExactBrushes.AddPlanes -> ExactPlane.Quantize: unit normal to 2^-20, offset to 1/16384 m). Planes that meet in one point in the brush's float mesh generally no longer meet in one point after rounding. Where more than three planes meet at a corner, the exact polytope gets small extra edges near that corner.

When two of those planes are nearly parallel, the extra edge is long: about 0.03 mm / sin(angle between them). A spiral stairs rail piece is one convex brush whose twisted top is two triangles. At both ends of the fold between them, four planes meet: the end, the side and both triangles, which are only a degree or two apart. The fold then ends 1.65 mm from the corner instead of at it. That leaves a vertex in the middle of the rail's top edge.

The output weld collapses edges shorter than 1 mm (OutputModelWeld.kCollapseLength) to hide these slivers after the fact. It can't reach this one.

Failing tests that show it: ChiselGeneratorSizeTests.SpiralStairsFilledDown_HaveWallsDownToTheFloor (Up and Down).

What the literature does

Plane-based exact Booleans import a mesh by rounding its vertices to an integer grid, and derive each face's plane exactly from three of them (normal = e12 x e13, d = -v.n). Every face plane then passes exactly through its vertices, so faces meeting at a corner meet there exactly, however many there are.

• Bernstein & Fussell 2009, Fast, Exact, Linear Booleans
• Campen & Kobbelt 2010, Exact and Robust (Self-)Intersections for Polygonal Meshes
• Nehring-Wirxel, Trettner & Kobbelt 2021, Fast Exact Booleans for Iterated CSG using Octree-Embedded BSPs (arXiv 2103.02486). Section 1 describes this failure for planes made separately, and section 3.2 gives the bit bounds (27 bit positions, 55 bit normals, 256 bit arithmetic).
• Trettner, Nehring-Wirxel & Kobbelt 2022, EMBER

What it would take in Chisel

• Snap each brush's vertices to a grid in tree space, and make each face's exact plane from three of its snapped vertices. Brushes that share a face must pick the same three, by position, so their planes come out exactly opposite.
• Bit widths: a cross-product normal needs about twice the bits of the coordinates. ExactPlane allows normals below 2^32 and offsets below 2^56 (Int128/Int192 maths). That leaves about 15-16 bits of coordinates across a brush, about 2.8 m on the current 1/16384 m grid. So the exact maths needs wider integers, or the vertex grid needs to be coarser.
• Snapping nearly-coplanar faces of different brushes onto one plane would then come from the vertex grid, not from rounding the planes.
• The ExactJudge input check, which rebuilds the expected planes with Quantize, has to follow.
• Once corners are exact, OutputModelWeld's short-edge collapse may no longer be needed.