How does Fornjot handle numerical stability?

[rockandsalt]

Hi,

Really cool project, one of the reason why making a CAD kernel is so hard is that you have to take into account numerical stability in all your algorithm that relies on equality checks. Additionally, you need to keep it under control or else you won't get what you expect if you do a lot of operation. I was wondering how does fornjot handle it? Are you doing it the CGAL way with a flexible type system that switches between exact and floating point math. Or you are doing it like Open Cascade where most function have a precision input ie : if point is within +-d of the line then the point is on the line.

Regards

[hannobraun]

Hey, @rockandsalt!

Really cool project

Thank you!

one of the reason why making a CAD kernel is so hard is that you have to take into account numerical stability in all your algorithm that relies on equality checks. Additionally, you need to keep it under control or else you won't get what you expect if you do a lot of operation. I was wondering how does fornjot handle it? Are you doing it the CGAL way with a flexible type system that switches between exact and floating point math. Or you are doing it like Open Cascade where most function have a precision input ie : if point is within +-d of the line then the point is on the line.

Neither, actually. Instead, Fornjot tries to avoid any situation that could cause those kinds of problems in the first place. For example, if a vertex is converted into surface coordinates, its canonical (3D) form is stored, so there's no loss when converting it back.

That alone is not enough, of course. I have a concept in mind, that I have started to implement. Basically, once this is fully implemented, the kernel will require geometric relationships to be explicit. For example, you can't have a vertex that just happens to be on a face. That would be an error. The kernel needs to know that the vertex is meant to be on the face. For example because the vertex results from a sketch that was drawn on that face, or because the user set a constraint to place the vertex there.

I don't know how well that will work out. It's an experiment!

The kernel's documentation talks some more about this: https://github.com/hannobraun/Fornjot/blob/d59e7ebdee1dcc4cb8dba896eafa7244cc248619/crates/fj-kernel/src/lib.rs#L15-L84

[rockandsalt]

@hannobraun, FYI I ended doing some research I found this review paper not sure how up to date it is (it is from 2005). According to the author, your approach falls into what they call "the geometric approaches". The authors have contributed to cgal so they are more biased towards the CGAL approach which they call EGC (exact geometric computation). Here's a link for the Prof Yap research group page which contains other papers and books on the subject. I also find the introduction page of their research group interesting, they describe what is their research beyond EGC.

[hannobraun]

Oh, wow, those are some interesting links. I'll have to study those in detail at some point. Thank you, @rockandsalt!

I'm going to add them to #556, so they don't get forgotten.

[XYCaptain]

Thanks for sharing！