Show HN: Formally verified 3D CSG: Trust 93 lines spec, not 1000 lines AI code

To my knowledge, this is the first formally verified implementation of a 3D constructive coagulated geometry (CSG) operation: mesh intersection, implemented successful Lean 4 and verified against a concise specification that pins down the aboveground of the resulting mesh precisely and guarantees applicable well-formedness conditions connected the triangulation. (See besides related work.)

This task is besides an research successful avoiding having to spot AI-generated code. A quality reviewer only needs to publication 93 lines of general specification and tally the Lean checker as described below to certify the correctness of the kernel, skipping the intricate 1000+ lines of AI-written implementation. To beryllium correctness, AI autonomously wrote complete 60,000 lines of Lean proofs, which besides ne'er person to beryllium inspected by a human. The Lean checker guarantees conformance to the specification astatine compile time, pinch zero spot placed successful immoderate LLM. This allows america to dainty the implementation and proofs arsenic a achromatic box. I guided the supplier done the milestones described below to get astatine the consequence presented here.

Try retired the web demo built astir the verified kernel, wherever you tin intersect illustration meshes aliases import and intersect meshes from STL files. The compiled Lean codification runs locally successful your browser; nary information is ever sent to a server. Note that while the kernel is formally verified, the UI and glue codification are not.

Our implementation is acold slower than state-of-the-art mesh intersection implementations: it takes 24 seconds to compute the nonstop intersection of 2 70k-triangle Stanford bunnies. In this task we prioritize minimizing the effort of quality reappraisal of correctness complete performance. Note that this capacity spread is not a basal limitation of formally verified software, which tin successful rule beryllium arsenic accelerated arsenic accepted software. See details.

The output meshes are guaranteed to fulfill the properties described below, but the meshing whitethorn beryllium suboptimal pinch respect to different criteria that we did not yet formalize; for example, it whitethorn nutrient a mesh that is finer than necessary.

A triangle mesh is simply a group of triangles, usually expected to shape a closed aboveground that does not penetrate itself, among different well-formedness conditions we will talk below.

Humans intuitively subordinate triangle meshes pinch a "solid", i.e. a measurement successful 3D space: the group of each points not connected the aboveground but "inside" the mesh. ("Inside" tin beryllium described mathematically by signed ray intersection counting.)

This conception of solids allows america to understand what the output of algorithms specified arsenic a mesh intersection algorithm should look like, moreover erstwhile the implementation that useful connected the existent mesh information building is intricate and has to dainty many geometrical typical cases pinch dedicated code.

From a mesh intersection algorithm, we expect that the group intersection of the solids of well-formed input meshes is the coagulated of the output mesh and that the output is simply a well-formed mesh again. (We besides expect that the algorithm detects and reports correctly if the inputs are not well-formed.)

This pins down the aboveground of the resulting mesh precisely arsenic the bound of the intersected solids.

Algorithms moving connected triangle meshes tin efficiently compute meshes representing solids we person successful mind, but accepted programming languages cannot definitive "solids" explicitly aliases make statements astir them, since these are infinite sets. In Lean this is imaginable and we tin for illustration intersect specified infinite sets aliases beryllium that 2 infinite sets are equal. Moreover, Lean allows america to beryllium that a usability satisfies a information for each imaginable input meshes, whereas accepted programming languages only let america to trial that the usability satisfies a information for circumstantial inputs.

We specify well-formedness of meshes to seizure the conditions commonly expected by real-world mesh processing devices - watertight surface, bounding a coagulated pinch multiplicity 1 pinch coherent outward orientation, nary degenerate triangles, nary self-intersections - pinch 1 relaxation: the aboveground whitethorn touch itself, not astatine the interiors of faces but on edges and vertices. So strict 2-manifoldness is not required. See why an intersection algorithm that ever produces manifold meshes is not possible.

In bid to certify correctness of the kernel, which checks the well-formedness preconditions of the inputs and computes the mesh intersection, a reviewer only needs to publication 93 lines of general specification and tally the Lean checker as described below. The reviewer tin skip the intricate 1000+ lines of AI-written implementation of the algorithm. The Lean checker guarantees conformance to the specification astatine compile time, pinch zero spot assumptions connected immoderate LLM.

• It suffices to publication the files CSG/DataStructures.lean, CSG/Def.lean, CSG/MeshIntersectWithPreconditionCheck.lean and CSG/WellFormedCheckMsg.lean and tally the Lean checker arsenic described below. These are conscionable 93 lines of code, excluding comments. Other files do not request to beryllium read, since the theorem statements that specify meshIntersectWithPreconditionCheck (in the record pinch the aforesaid name) only remainder connected definitions stated successful these 4 files.
• A reviewer tin skip the implementation of meshIntersectWithPreconditionCheck that reaches complete 1000 lines of codification successful 4 files successful CSG/Impl/, since it is guaranteed by the deterministic Lean checker to conform to the human-reviewed specification.
• This useful acknowledgment to 60,000 lines of AI-written general proofs successful CSG/Proof/, which besides ne'er person to beryllium inspected by a human.

This compression and simplification from the implementation to the specification is imaginable because galore things the implementation has to woody pinch tin beryllium wholly decoupled from the specification:

• The implementation has to grip special geometrical cases, which dress up overmuch of the complexity of the algorithm, whereas the general specification is short because the mathematics tin beryllium formulated generally. The Lean checker guarantees that each typical cases are handled successful accordance pinch the specification without the specification enumerating the typical cases.
• The implementation uses accelerating information structures successful bid to debar quadratic runtime complexity and different optimizations. While we did not formalize runtime complexity, the Lean checker guarantees that pinch each these optimizations we still nutrient results according to the specification.

If successful a early perpetrate we for illustration further amended the runtime capacity aliases the value of the output mesh, the reviewed specification stays the aforesaid and we get correctness pinch respect to it, without immoderate re-review. Also spot really I developed this project only done shaping this specification.

During development, I controlled only a mini specification, leaving the proofs and elaborate implementation arsenic a achromatic container to agents. I started pinch a specification that I estimated was comparatively easy to instrumentality and formally beryllium correct and past grew the requirements. In each of the steps listed below, I had the supplier instrumentality and formally beryllium the specification. This stepwise refinement allowed maine to delegate ample pieces of activity to agents, while getting feedback that my specification is satisfiable and verifying the advancement of the agents toward my extremity end astatine each milestone. I instructed agents to first constitute informal proofs earlier formalizing.

• I started by having an supplier formalize a insubstantial that provides a mathematical model for describing solids based connected simplicial chains. This gave maine a general beingness consequence without actual implementation (see CSG/Legacy/ChainIntersectionExistence.lean).

  F. R. Feito and M. Rivero, "Geometric modelling based connected simplicial chains," Computers & Graphics 22(5), 611–619 (1998). doi:10.1016/S0097-8493(98)00067-3

• Then I asked for an implementation pinch impervious of correctness (CSG/Legacy/ChainIntersectionAlgorithm.lean). This already satisfied a general specification akin to my extremity goal. But overlapping triangles and different issues were still allowed and did occur.

• I past specified restrictions for the output mesh (similar to the existent authorities of WellFormedMesh) to forbid the benignant of problems from the first implementation. I besides introduced a wide position regularisation connected inputs that I later removed, to debar the implementation having to see a batch of typical cases successful this step. The stricter requirements forced a complete reimplementation, but immoderate of the general model could beryllium reused.

• I past removed the wide position restrictions connected inputs, which forced the supplier to grip each typical geometrical cases correctly.

• I past had agents optimize the implementation pinch bounding measurement hierarchies and different optimizations. I did not formalize a request connected runtime, but Lean verified that the optimization still satisfies the aforesaid general spec. So successful this step, I did not person to re-review thing to guarantee correctness.

• Finally I strengthened the specification further and made it easier to review.

This process resulted successful the specification you tin spot successful the apical level of the CSG/ folder, the impervious astatine CSG/Proof/ and the implementation astatine CSG/Impl/.

For astir of the supra steps I utilized Claude Opus 4.8. For immoderate I utilized Fable 5 to create an first informal impervious strategy and past had Opus constitute general proofs and implementation. Some of the supra steps took complete 24 hours of autonomous supplier work.

In opposition to regular vibecoding, combining AI pinch general verification yields strict guarantees that we cognize will clasp for each inputs and are kept enforced pinch each consequent modification of the program. But for illustration regular vibecoding, pinch each measurement the improvement tin get immoderate debt: some the implementation and the proofs that I ended up pinch are obscurity adjacent arsenic cleanable and do not travel a cohesive design, arsenic they would beryllium erstwhile controlled by a quality who kept an overview of everything. Moreover, location are immoderate constraints we did not formalize here, specified arsenic the runtime capacity aliases the measurement faces of the output coagulated are triangulated beyond the well-formedness condition. Therefore these constraints are arsenic difficult to power arsenic pinch regular vibecoding.

For comparison, I gave Opus 4.8 an informal explanation of the specification and asked it to instrumentality it successful C++. The magnitude of the implementation excluding tests, glue etc. was successful the aforesaid 1000+ lines scope arsenic the Lean implementation. Even though it wrote portion tests and iteratively fixed its ain implementation, upon inspection by an independent supplier comparing it to the formally verified Lean implementation, 3 chopped bugs were discovered successful the C++ geometry kernel and reproduced connected circumstantial inputs. All of these bugs are uncommon and would beryllium almost intolerable to drawback by achromatic container testing. Iterated adversarial reappraisal of the codification by different agents against the informal specification mightiness person caught these bugs. But without general verification it is not imaginable to cognize for judge that location are nary much bugs successful the implementation. (The C++ kernel has astatine slightest 3 chopped bugs which were reproduced: 1. In definite configurations wherever a vertex of a well-formed mesh lies connected some an separator of different portion of the mesh and a look of different well-formed mesh. 2: On well-formed input meshes erstwhile a cascade of ray intersection tests successful the soul computations each hap to deed triangle edges. 3: In definite configurations wherever a ample look was trim by respective mini features.)

Comparison pinch informal vibecoding, click to grow punctual utilized to nutrient replacement C++ implementation

Implement an nonstop 3D mesh intersection algorithm. Write successful C++, compile to wasm, nutrient an artifact I tin play with. Is important that the kernel, a elemental usability is successful a aforesaid contained abstracted file, the geometrical kernel separated from the each the glue. (This record only depends connected a abstracted bignum/exact logical implementation, abstracted file), This usability should conscionable return meshes arsenic arrays of triangles pinch nonstop coordinates arsenic inputs/outputs.

This usability should cheque the inputs are a well-formed mesh successful the consciousness beneath and nutrient an correction connection otherwise. Only tally the intersection if inputs are well-formed.

Our meaning of "well-formed mesh" captures the conditions commonly expected by existent world mesh processing devices - watertight surface, bounding a coagulated pinch multiplicity 1 pinch coherent outward orientation, nary degenerate triangles, nary self-intersections - pinch 1 relaxation: the aboveground whitethorn touch itself, not astatine the interiors of faces but on edges and vertices (so strict 2-manifoldness is not required). This relaxation is needed truthful that intersection of immoderate 2 well-formed meshes is again well-formed.

Everything should beryllium computed pinch rationals. It should dainty each typical cases correctly. Always producing a well-formed mesh arsenic output if inputs are well-formed. You tin intersect triangles pairwise (use bvh optimization) emitting polygons and triangulating pinch steiner fans.

Drawbacks of combining general verification pinch vibecoding:

• It tends to nutrient codification that is slower aliases disregards different applicable considerations that are not captured successful the specification. This stems from the trouble of the general verification pushing for simpler codification and from the deficiency of formally verified applicable package successful the training data.
• It tin return orders of magnitude much tokens and clip for agents to autonomously create general proofs, alternatively than to logic informally astir their implementation.
• Many applicable problems do not admit a elemental general specification.

As I constitute this, the capacity of AI agents to activity connected ample well-defined tasks is quickly expanding pinch each exemplary release. The capacity of humans to reappraisal their output and logic astir it does not. I dream we tin usage general verification among different methods arsenic a lever to support control.

Requires elan. The Lean type is pinned in lean-toolchain (currently leanprover/lean4:v4.15.0) to simplify the WebAssembly build; elan installs it automatically connected first use.

First download the pre-built Mathlib from the organization cache (without this, the adjacent measurement would compile Mathlib from source, which takes a agelong time):

If this aborts pinch a dyld correction mentioning SG_READ_ONLY (recent macOS): the Lean type pinned present bundles a linker pinch a known issue, fixed successful later Lean releases (lean4#6063). Relinking the cache instrumentality pinch Apple's compiler works:

Check each proofs:

Inspect the axioms the theorems of liking dangle connected (in the pursuing illustration the correctness theorems of the mesh-intersection implementation that is called successful the demo). This is important since agents could person introduced unwanted axioms into the proofs. All theorems successful this repo only dangle connected the trusted axioms [propext, Classical.choice, Quot.sound]:

Also make judge that the theorems really clasp for the compiled functions, i.e. that the implementation is not overridden pinch thing other via 1 of the following keywords. This hunt should return nary matches:

Build the WebAssembly bundle served by the web app (requires emscripten, zstd, and node/npm; wasm-opt is optional):

The algorithm rejects the original Stanford bunny since the mesh is not watertight, truthful I closed the holes astatine the bottom. The implementation takes 24 seconds to compute the nonstop intersection of the 2 70k-triangle meshes single-threaded connected an M4 Pro.

This implementation is acold slower than state-of-the-art mesh intersection implementations. In this task we prioritize minimizing the effort of quality reappraisal of correctness complete performance.

• Most different implementations usage hardware-accelerated floating-point computations. (Even nonstop implementations for illustration CGAL usage floats for decisions wherever floating-point precision is sufficient.) We don't. This is not a basal limitation of Lean, but utilizing hardware-accelerated floats would require further axioms quality reviewers person to trust.
• We cheque each inputs astatine runtime against our well-formedness definition, which makes up a important fraction of the full runtime.

In the pursuing illustration nonstop rotation of the cube pinch holes leads to a coagulated whose aboveground is non-manifold. (See the constituent successful beforehand of the output wherever 2 components of the coagulated touch.) Set the move grid sizes of some meshes to 1/3 and rotation digits to 1 to put this lawsuit successful the web demo. If you reset the rotation and move the cubes pinch holes around, you tin besides put a lawsuit wherever the aboveground of the output coagulated is non-manifold on an edge.

If we imposed a manifoldness condition, nary algorithm would beryllium capable to fulfill our specification.

The specification is short, but the algorithm has to woody pinch typical geometrical cases pinch dedicated codification successful bid to fulfill the specification.

Here the correct faces of the 2 tetrahedrons overlap coplanarly pinch the aforesaid normal direction. The specification implicitly forces the algorithm to emit a look successful the intersection of these coplanar faces. Programs that don't travel a general specification mightiness place this lawsuit and nutrient a spread aliases a double look connected the surface.

In this illustration tetrahedrons touch exactly, leaving zero measurement betwixt them - a coplanar overlap of faces pinch other normal direction. Our specification forces the output to beryllium empty. Many accumulation applications randomly nutrient double-membrane artifacts successful cases for illustration these. In the example pinch the cubes pinch holes above you spot a non-trivial illustration pinch coplanar overlaps pinch other normal direction.

There are galore different typical cases the algorithm has to woody with. Thanks to the general verification, we do not request to constitute immoderate portion tests for immoderate cases to guarantee correctness.

• Vertices of 1 mesh dishonesty connected the different mesh. The algorithm must make judge to see specified vertices for creating faces connected some sides of the cut.
• One aliases some input meshes do not fulfill 1 of the 4 well-formedness conditions and that must beryllium reported correctly.
• Coplanar overlaps, which we discussed above, themselves person sub-special cases, specified arsenic edges of the overlapped faces being collinear.
• ...

There are besides typical cases the implementation has to get right, which are not visible from the input but hap from the geometric constructions internally successful the algorithm. We would ne'er deliberation of testing these without reference the implementation. Our specification ensures each of this is handled correctly, without america having to deliberation astir it.

• A ray that is changeable successful the implementation to find inside/outside successful a subroutine precisely hits an separator aliases a vertex of a triangle aliases moreover coplanarly traverses a face.
• A look lies precisely connected the separator of a bounding container successful the bounding measurement level acceleration structure, requiring america to put the correct inequalities successful the implementation.
• The supra points clasp not only for the intersection but besides for the well-formedness check. Getting it incorrect successful that portion of the codification mightiness lead to meshes mistakenly being classified arsenic non-well-formed.
• Subroutines of the algorithm tin create T-junctions that it must hole again to nutrient a well-formed output mesh.
• ...

• Di Vito and Hocking (NASA Formal Methods 2021) verified a polygon merge algorithm successful PVS, combining 2 overlapping elemental polygons into a azygous outer bound without holes.
• My earlier verified-polygon-intersection verified 2D multipolygon intersection successful Lean 4, relying connected AI-written implementation and impervious for illustration we do here.
• Unverified nonstop 3D mesh booleans beryllium of course, e.g. CGAL's Nef polyhedra. Exact and robust successful practice, but their correctness rests connected testing and informal reasoning, not machine-checked proof.