We could use floats internally and gain a lot of performance as I described in my response here: https://news.ycombinator.com/item?id=49085136.
With this we would still be able to handle special cases correctly.
If you mean, you want float in the interface, I think the picture would be the similar as I described there: You still need to fallback to higher precision for certain computations. But you would also not be able to return the outputs correctly, so we would need to think about how we want to describe this in the specification...
One complication: For union the spec would look a little bit different than for intersection. I defined the solid associated to a mesh in a way that does not include the surface of the mesh itself. That works for the intersection. For union we would have:
I think it would not be hard to reduce the implementation and the proof of correctness to the intersection: There are some tricks which you can do like flipping the orientation of a mesh and putting a large cube that contains both meshes around it and then intersect these. (And then at the end doing the reverse trick.) Hopefully the implementation would not actually do this, but this construction could be used in the proof.
The implementations uses exact rationals numbers. So there are no issues with numerical errors. We can do all geometrical operations exactly.
Many performant implementations have a separate layer that tries to use floats to decide inequalities and fall back to higher precision when floats are not sufficient. As I understand, this layer can be separated from the geometrical predicates we need (what I mean by predicate is for example deciding which side of a plane a point is), so we could formalize that arithmetic layer separately using axioms on floating point numbers and then plug it in the existing code. I think we could do that and still provide exact outputs and prove the same spec we have right now and the performance should increase a lot, since most of the computations right now is computing all these predicates exactly.
Also note that many implementations don’t even try to treat special geometrical cases correctly (for example they „cheat“ by using something called simulation of simplicity which provides some guarantees against some bugs, but at the expense of not treating the cases exactly correctly which can lead to artifacts).
I learned working with the Isabelle proof assistant in a university course. There were weekly exercises and a group project at the end. (Actually proving things by hand, no LLM.) That really helped. Before that course it was also hard for me to get into this.
Other than that you can also read introductory material for set theory. There the meaning of all of the unicode symbols you can see in the spec should be explained.
Both the implementation and the proof are written in Lean.
In the files I reference here https://github.com/schildep/verified-3d-mesh-intersection#mi...
there are theorems about the function that does the mesh intersection computation.
The implementation is in the CSG/Impl folder. The proof is in the CSG/Proof folder. They are imported and tied together in the human reviewed file. Lean checks that these theorems in the human reviewed file are proven via the proofs.
I think this would need to be reimplemented for performance. But maybe the spec can be reused. As agents get better we might reimplement the same spec for performance with minimal human effort. (See notes regarding performance and floats in readme.)
Maybe what you mean is that kernels of proof assistants must be small. Here I am referring to a geometry processing kernel (that is formally verified by a proof assistant). The implementation of the algorithm can be very long, the proof that it conforms to the spec can be very long. But lean checks the proof. And so you only have to trust the spec and that the lean proof assistant is correct.
In the 93 lines I assumed a reviewer already trusts that the kernel of the Lean proof assistants is correct. We have to trust somethings.
The implementation of a function is in the CSG/Impl folder. A proof is in the CSG/Proof folder. They are both imported and tied together in the human reviewed file in a theorem that makes a mathematical statement about the function. Lean checks mechanically that the theorems are proven via the supplied proofs. Here you have to trust the Lean checker, but neither the proof nor the implementation.
Then you know that the statement in the file you reviewed holds about that function.
The runtime performance is most probably worse than yours. The goal of this project is a minimal specification that a reviewer can trust. See section in readme on performance and how it could be improved while still keeping formal guarantees, but would mean a reviewer having to trust axioms on floating point numbers:
https://github.com/schildep/verified-3d-mesh-intersection#pe...
If you mean, you want float in the interface, I think the picture would be the similar as I described there: You still need to fallback to higher precision for certain computations. But you would also not be able to return the outputs correctly, so we would need to think about how we want to describe this in the specification...