Add Fillet #1229
Add Fillet #1229
Conversation
| */ | ||
| ///@{ | ||
| static Manifold Fillet(const MeshGL&, double radius, | ||
| const std::vector<size_t>& selectedEdges = {}); |
There was a problem hiding this comment.
So, the API here is tricky - I can see why you're basing this on MeshGL input, since that allows you to select edges, and that's what I did for one of the Smoothing constructors. However, I think I'd prefer to avoid edge-selection APIs as much as we can. I think I'd prefer a Fillet command that fillets all edges beyond a threshold angle, and then it can be non-static. Do you think that's doable?
There was a problem hiding this comment.
I think the fillet in pure geometric way won't be that robustness, See corner case 1. It heavily rely on the request radius and adjacent relationship. If so, the result might be out of control.
But I think it would be extremely valuable if there is a full robust fillet method, and i'll keep looking for it.
There was a problem hiding this comment.
Yeah, Manifold's core ethos is robustness - we want find an algorithm that doesn't have edges cases, rather than trying to fix edges cases one by one. In computational geometry, edge cases tend to be the norm, rather than the exception.
|
openscad/openscad#5337 Implement roof() without CGAL Specifically, Might be related and able to handle together? |
|
Actually I have a straight skeleton algorithm I implemented in Matlab ages ago that I've been meaning to port if you're interested. It is good for polygon offsets, though I'm not sure how that would relate to polygon fillets or especially to mesh fillets? |
@elalish Besides, I think it might require using Clipper to maintain robustness , as otherwise, construct new point could lead to floating-point precision issues and numerical instability. Do you think my consideration exist? And yes, it's more relevant to offsets. Since this is a sudden thought, I want to keep offset thread clean so put it here . |
|
I don't have time to port it at the moment - it'll probably take me a week just to dredge up the old Matlab script from my archives. If you'd be interested in reading through it and trying to port it to C++, I'll be happy to give pointers. The main thing was using SVD to calculate skeleton verts from sets of three edges, so as to also get a numerical uncertainty. I used this to merge verts, which keeps the numerics stable. A Hilbert curve is a great test case, and shows why degeneracy is so common in the straight skeleton. |
|
Thanks! I'll give it a try. |
|
Notes about today's meeting. Consider the polygon with a hole in the middle. If we define fillet using rolling ball (blue) directly, we will get two rounded squares at the bottom because the middle section can't fit a ball inside. The issue here is that this changes the topology in a potentially weird way, so maybe we can try not to remove stuff when removing it can change the contour. With this interpretation, we get the result at the top. |
|
My current thought is to process vertex one by one. If there is no solution in the neighbor, we will find it via adjacent vertex circles overlapping. It can simply be proven. This gives a better result than rolling sphere method ends up nothing, see the second figure. However, I still need to find a way to search for a solution for adjacent overlapping circles. I'm currently thinking about using an inward offset to find a possible solution area. What do you think about it? CC @elalish @pca006132 |
|
Our You might consider writing it in such a way that it can incrementally create the fillets, so that if it runs into trouble, we can dump out the intermediate result in a form we can visualize. |
|
And what do you mean by adjacent vertex circle overlapping? Can you give a more detailed example? Or explain why the 3 circles in your first figure are different in sizes. |
|
Since we are focusing on 2d convex vertex fillet, I am processing convex vertex one by one, calculating the intersect point and bridge with an arc. See Figure 1, this is when the fillet radius is relatively small. As we rule out e2, we have to find a solution between e1 and e3. The solution might meet the concave vertex and split the shape into two parts, that's what I currently achieved. See Figure 5. But there are also situations where no solution existed between e1 and e3, and need to do a global search for a solution. Last week, I was trying to find it locally but have no idea. Another idea is using offset to get a possible solution region nearly, which is also not so clear. Maybe I should just start coding and get some results at least. |
No, maybe I should explain it a bit better. Here, the blue area is where the fixed-radius circle can reach. The issue is that it has a different topology than the thing we started with. So we fill in the green area to make the topology the same as the original, and the final result is the colored region. Here, it is mostly similar to the example above. However, the two red regions on the right are not significant in terms of topology, so we can simply remove them. The question here is can we figure out a simple way to compute this. Maybe we can split the edges, compute if each segment can touch the circle, from this we can find the edges that are in the same blue component. And for the remaining edges, we can check if they connect different blue components, and if yes we keep them.
I think if you have something like figure 2, this means you can't have a circle that touches both e1 and e2 and fits within the polygon. Similarly for e2 and e3. This means that e2 should go. |
|
Some trivial stuff related to the algorithm that you may consider: For every oriented edge, we check the red region for other edges. If there are no other edges, we must be able to fit circles inside the red region, so the edge must be kept. Otherwise, there are several cases: tangent--tangent, tangent--point, point--point. For all cases, we need to ensure that no other edges can intersect the circle, or it will be invalid. For tangents, we split the edge and do the check recursively. For points, we add an edge to join them (and split the polygon). For the degenerate case where there is another edge that touches the circle, we ignore that because it doesn't matter. |
Figure 1. General idea
Fillet operation means to create rounding corner with selected edges.
Algorithm Input: target mesh, radius of rounding corner and selected edges.
Implement: Main idea is create a properly cylinder and boolean with target mesh to create the rounding corner.
Figure 2. Corner cases
There are some corner cases this implement can't handle.
Siemens NX fillet operation
Blender bevel
As for case 1, most software only deal with adjacent faces, can't handle this case with pure geometric way. But, this can be solve by MinkowskiSum with outward and inward offset.
Siemens NX fillet operation
Blender bevel
As for case 2, Blender create transition surface while NX can't handle it.