Implement operation for splitting faces
hannobraun opened this issue · 10 comments
I would like to have an operation that splits a face into two, along a line. This wouldn't be very useful in itself, but it would make it possible to then do different things to those two faces. For example, you could sweep one face to add to the solid (which is also not implemented yet) that it is part of, while leaving the other face as-is. This would enable more complex modeling than is currently possible.
I've started working on this.
I've been working on putting the pieces into place that are going to be required for the face splitting operation (see the pull requests listed above this comment). Right now, my focus is the shell validation code. I already have an operation in my local branch that can split an edge (which is a required part of splitting a face), but using it results in a validation failure. The water-tightness check is basically still stuck in the pre-#1937 world and needs to become a bit smarter.
This shouldn't be too much of a hurdle, so I'm hopeful I can merge the edge splitting operation soon. From there, it shouldn't be too big of a step to implement face splitting.
This week, I worked on refactoring the curve approximation code, extracting the parts that deal with multiple curve boundaries into a new, reusable API. I should be able to now use this new API to fix the water-tightness check that I talked about in my previous comment.
I'm still fiddling with the expanded curve boundaries API, so same as last week.
The new water-tightness check will basically consist of some set operations on curve boundaries, and since the curve approximation code was already doing some of that, I figured the best approach would be to extract that code into a reusable API, clean it up, and expand it as necessary. Having that API should then make implementing the new water-tightness check quite trivial.
Given how long that has been taking, this was probably the wrong call. It might have been more practical to build some special-purpose code for the new water-tightness check and be done with that. However, given that I've already done most of the work for that presumably wrong approach, that insight comes a bit too late 😂
I'm fairly confident that I'm over the hump, so the new water-tightness check should be available soon(tm). This will unblock further work on first edge splitting, then face splitting.
So, I finished the work on the expanded curve boundaries API yesterday, and indeed, that made fixing the water-tightness check trivial. Now split edges work perfectly well, within the context of Fornjot.
Why am I emphasizing this last part? Because exporting this model will result in an invalid mesh. We might be able to get away with this with STL, as long as the program reading those generated STLs is sufficiently smart, but 3MF files are just outright invalid. And this is an inherent problem with the whole approach with splitting a (half-)edge, and not it's counterpart. That's a non-starter.
It would be possible to paper over this in the approximation stage, by recognizing where we have such non-matching edges, and inserting vertices as required, but that doesn't seem like the right solution. I wrote all this code to enable more complex geometry, and now I'm going to write even more code to simplify it again afterwards? That just seems wrong.
I think it would be better roll back the changes made to allow more flexible geometry, which would require that splitting a half-edge also splits its sibling half-edge. This puts more burden on the authoring side, but I now believe that this would be manageable by putting the necessary smarts into the respective operation.
All of this means that the months of work I put into #1937, as well as the additional weeks I spent within the context of this issue to "fix" the water-tightness check, were largely wasted. I mean, yeah, I learned a whole lot and I'm certainly wiser and more experienced than I was before, but months of work seem like a steep price to pay for a little insight.
It is what it is though. I'll be thinking some more about this, to make sure I'm not making any rash decisions. I'll also spend what I foresee to be quite a bit of time reflecting on how I can improve my decision-making in general, to prevent fuck-ups like this in the future. But that kind of self-reflection is not within the scope of this issue, and sounds like a topic more suited for my monthly sponsor updates 😄
I've decided to go ahead and remove all that flexible infrastructure I built for #1937. It's a bit painful, but there's really no point in keeping it around.
I'm currently finishing up some clean-up related to that change, and after that, I'll be back to working on this issue. I have some ideas for how to proceed, and will keep you updated here.
I've merged the half-edge splitting documentation, but using it correctly is a bit non-trivial. Unfortunately, it's not that easy to know which other half-edge to split, to keep all of them lined up correctly.
Eventually this should be fully automatic, but for now, I think it's a more practical next step to make sure this is easier to manually. Next, I can finally implement face splitting, and then re-evaluate whether it's time to make that all nice and automatic then and there, or if it makes more sense to continue with the higher-level stuff I'm building this all for.
Time for another end-of-week update!
This week has been a bit quiet (barely any pull requests), as I've been doing design work (which, for me, tends to be a mix of thinking and hands-on experimentation). I've been looking into how to implement the manual solution, which I've talked about in my previous comment here, in a test model. This turned out impractical, due to two missing pieces:
- A query to find the sibling of a half-edge. I've already added this, see the pull request referenced above this comment.
- An operations for replacing a half-edge, without exactly knowing where in the object graph it is.
Work on the second item is well underway, and I've made some good progress figuring out the details of the design. There's more to figure out still, but I'm hoping for some tangible progress next week.
I have progress to report! I've semi-finished the half-edge replacement operation (need to be a bit of clean-up before I can submit a pull request). Here's a local example model I'm currently experimenting with, where I've split an edge in half:
This model exports to a valid 3MF file, which means I seem to have gotten it right this time 😄
One problem though: The model currently produces a validation error (which I've told it to ignore, to produce this screenshot). Not because the model itself is invalid, but because there is an invalid intermediate state, where one half-edge has been split but its sibling hasn't been. Due to the way the validation service currently works, validation errors in intermediate steps will be regarded the same as validation errors in the final model.
This won't do, obviously, so I have to solve this problem before I can continue. I currently see two options, basically:
- Change the way the validation service works, somehow. I will look into this, but as of right now, I'm not sure what exactly to do about this. This might be a bigger thing than I want to take on right here and now.
- Change the edge-splitting operation to not produce invalid intermediate results. I've yet to look into this, but I suspect that this will be rather straight-forward This won't solve the general problem, but it will solve the specific one I'm facing right now.
I think I'll go with solution 2 and open an issue for the more general problem, but there might be some hidden problem or opportunity that could change my approach. I'll keep you updated.
Edge splitting now works! I've also added an example model that tests/demonstrates this capability.
Things ended up going pretty much as I expected, and I went for the more specific solution of not inserting any invalid intermediate results (so just inserting the valid end result). I actually came to the conclusion that "don't insert any invalid objects" is a pretty good rule to live by, at least for now, so I haven't opened an issue about changing the validation in any fundamental way. We'll have to see how this develops, but right now, I'm pretty happy with what we have.
With this, all the building blocks for splitting faces should be in place, and I'm now looking into implementing it.
And we're done! Implementing face splitting was a bit fiddly, but since most of the building blocks were in place as of yesterday, it wasn't a big deal anymore. Some more info and a screenshot in #2097.
Next up, I plan to make use of this capability by making it possible to sweep the face of an existing shell! No issue exists for that yet, but I'm going to open one soon.