fornjot
fornjot copied to clipboard
hannobraun
Don't use triangle meshes as intermediate representation of shapes
Some time ago, instead of using classical boundary representation, Fornjot generated triangle meshes for each primitive shape directly, then extended/modified these triangle meshes when transforming/combining these shapes. It was clear to me from the beginning that this was an intermediate step. It was just simple to do, as long as Fornjot didn't haves features that made that approach complicated.
As expected, that approach outlived its usefulness pretty fast, and I've been working on moving the CAD kernel to the boundary representation approach for a while now. As of this writing, the kernel supports both approaches in parallel.
Most of that work has already been done, so I'm actually a bit late in opening this issue. The only remaining operation (as of this writing) that still produces the triangle representation is fj::Sweep, and only for the side walls.
I'm working on that (work-in-progress is available in the enclosure branch). Unfortunately that last bit requires some more refactoring of the internal representation. I'll possibly tackle #78 first, before finishing this issue. I think that might be easier, overall.
Now that #78 has been addressed, I've looked into this issue again. I started by checking out my work-in-progress in #88, to figure out what a sensible next step would be.
The last operation that still uses triangles as intermediate representation is sweep, for the side faces it generates. Addressing this will require support for sweeping vertices into edges, and edges into faces, and on the geometry side, sweeping points into lines, and curves into surfaces. This will require support for more complex surfaces (ones swept from circles), make the current line/plane representations redundant, and will need to be supported by the approximation code.
I don't want to make the required changes to the approximation code without a reliable test suite in place, hence I'm taking another detour: Addressing #138.
I've made some more progress here, then I let myself get distracted by #193. Back on track now.
I've taken a strong step forward in my WIP branch (#178). The sweep operation has been made fully triangle-less, and the triangle representation has been removed.
The new and improved sweep doesn't work for circles though:
I saw this coming. The problem is that the side wall is continuous, connecting to itself. The approximation/triangulation code can't handle this. I have a plan for addressing this. If things go like I expect, this shouldn't be much of an issue.
My WIP branch in #178 now contains a commit that includes the improvements I mentioned in my previous comment here, with a triangle representation fallback for the cases that the new code can't handle. Unfortunately the new code is not correct. It creates duplicate vertices (multiple Vertex instances that refer to the same vertex), which is a bug.
Even though I know exactly what the problem is, I don't see an easy way to address this within the current structure. And I don't want to implement some ugly hack that will come back to bite us later.
Instead, I've come up with the following plan for my next steps:
- Address #176. This is a cleanup that will be important in the long run anyway, but also makes the next step easier.
- Simplify the sweep code and add a test suite, making it easier to extend.
- Address #242. This isn't strictly necessary at this point, but since the sweep code has turned out to be difficult and bug-prone, I can use the additional protection.
- Adapt and merge the functionality in #178.
With all this done, triangle representation will be relegated to a single edge case. Addressing that requires yet more changes, as I've discovered. There are a lot of details which I'll explain in a separate issue (hoping to find the time do that soon), but the bottom-line is that the approximation code will need to be extended to handle continuous faces, which it currently can't. I have a plan for doing this, but it will likely require non-trivial infrastructure changes.
I don't think I will do that any time soon though. At that point, I will probably call this issue blocked on the yet to be opened issue, and do something else. Stopping when so little triangle representation is left in the kernel feels a bit wrong, but I need to make progress on the milestone I'm currently focused on, and that last edge case won't affect that.
Vertex validation is now enabled (#242)! I'm back to working on this issue.
With #355, this issue is mostly done. The last edge case are continuous side faces of a sweep. Continuous faces are faces that connect to each other; an example of that is the side wall of a cylinder. Since approximation doesn't support continuous faces yet (#250), this issue is now blocked on #250.
As I alluded to in a previous comment, this is good enough for now. The current development priority is an MVP with straight edges and flat faces that includes CSG, and triangle representation prevents CSG support (which is why I'm working on this issue in the first place). And since continuous faces are always be curved (because they couldn't connect back to themselves, if they're not), not having full CSG support for them in the initial MVP is fine.
As a result, this issue is no longer an immediate priority. I might finish this up, if motivation strikes me some evening or weekend, but otherwise, I'll do something else for now. Don't worry, there's more than enough to do. I'll be fine :smile: