verified-3d-mesh-intersection
Formally verified 3D mesh intersection - trust 93 lines of spec, not 1000+ lines of AI-written code
What is it?
What it is
A formally verified implementation of 3D constructive solid geometry (CSG) mesh intersection in Lean 4, comprising a small human-reviewed specification (93 lines), AI-generated proofs (~60k lines), and AI-generated implementation (>1000 lines), with a WebAssembly demo that runs the verified kernel in the browser.
Why it exists
To provide trustworthy mesh intersection correctness without requiring humans to inspect complex AI-generated code or proofs, by relying on Lean's type checker to guarantee conformance to a concise specification, thus minimizing review effort while delivering machine-checked guarantees for all inputs.
Who should use it
Researchers in formal verification and computational geometryDevelopers needing provably correct mesh intersection (e.g., safety-critical applications)Academics studying verified constructive solid geometryEngineers who want to trust AI-generated code via formal specification
Who should avoid it
Practitioners requiring high-performance mesh intersectionThose unfamiliar with Lean or formal methodsProjects needing rapid prototyping without proof overheadUsers seeking simple drop-in libraries without verification
How it works
A quick walkthrough in plain English
How verified-3d-mesh-intersection works
Step 1 of 3
You interact with it
Open verified-3d-mesh-intersection, send a request, or connect it to your stack.
Features
Advantages
- Zero trust required in AI-written implementation or proofs
- Eliminates the need for extensive manual unit testing for edge cases
- Mathematical certainty of correctness for all valid inputs
- Decouples complex implementation details from a simple, human-readable specification
- Prevents common geometric bugs found in unverified C++ implementations
Disadvantages
- Significantly slower than state-of-the-art implementations (e.g., 24s for 70k triangles)
- Output mesh may be suboptimal (e.g., finer triangulation than necessary)
- High computational cost for generating formal proofs via AI
- Does not guarantee manifold output meshes in all valid intersection scenarios
Installation
FAQ
What does the formally verified specification guarantee about the mesh intersection result?
The specification guarantees that the solid of the output mesh equals the set intersection of the solids of the two input meshes (solid (meshIntersect M₁ M₂) = solid M₁ ∩ solid M₂) and that the output mesh is well-formed according to the project's definition (watertight surface, bounds a solid with multiplicity one, coherent outward orientation, no degenerate triangles, no self‑intersections, allowing only edge/vertex self‑touching).
How can a human reviewer certify correctness without trusting the AI‑generated implementation?
A reviewer needs only to read the 93 lines of specification in the files CSG/DataStructures.lean, CSG/Def.lean, CSG/MeshIntersectWithPreconditionCheck.lean and CSG/WellFormedCheckMsg.lean, then run `lake build` to check the proofs. The Lean checker ensures the 1000+ line AI implementation conforms to this specification, so the reviewer does not need to inspect the implementation or the 60,000 lines of AI‑generated proofs.
What are the steps to build and run the verification locally?
First install elan to get Lean 4, then run `lake exe cache get` to download Mathlib. Build and check all proofs with `lake build`. Optionally inspect axioms with the provided `printf … | lake env lean --stdin` command. To build the web demo, ensure emscripten, zstd, node/npm are installed and run `./build_web_demo.sh`.
Why does the algorithm not require manifold output meshes, and what happens in non‑manifold cases?
The specification only requires the output to bound a solid with multiplicity one; it does not forbid the surface from touching itself along edges or vertices. Consequently, when two solids touch at a point or edge (e.g., rotating a cube‑with‑holes to create a non‑manifold contact), the verified algorithm correctly produces an output whose surface may be non‑manifold, which is unavoidable if we want the intersection of arbitrary well‑formed inputs to again be well‑formed.
What performance characteristics should users expect from the verified kernel?
The verified kernel is intentionally slower than state‑of‑the‑art mesh intersection tools; intersecting two 70 k‑triangle Stanford bunnies takes about 24 seconds on an M4 Pro. The slowness stems from using exact rational arithmetic, runtime well‑formedness checks, and the lack of hardware‑accelerated floats, but the developers note that performance is not a fundamental limitation of formally verified software and can be improved without affecting the verified specification.
What special geometrical cases does the implementation have to handle to satisfy the specification?
The implementation must correctly handle cases such as vertices of one mesh lying on the other mesh, coplanar face overlaps (same or opposite normals), edges of overlapped faces being collinear, rays hitting edges or vertices exactly during inside/outside tests, faces lying on bounding‑box borders in acceleration structures, and internally generated T‑junctions that must be resolved to maintain a well‑formed output. Formal verification guarantees these cases are processed correctly without the reviewer needing to examine them.
Featured in Videos
YouTube tutorials and walkthroughs for verified-3d-mesh-intersection