This node is useful for making 2D animations with curves. Like this one I made for an earlier feature request patch :
For example, the AND operation is useful to mask the pupils to the shape of the eye. Such a thing is currently not possible in blender, at least not non-destructively.
I plan to support AND, OR, and DIFFERENCE operations. All curves must be bezier curves, because splines cannot keep their shape AND have sharp corners without an unreasonable amount of additional control points, and blender’s spline to bezier operation does not result in perfectly identical results.
This general idea sounds great! I would like to have that sort of operation where the result is still a curve. It’s probably worth thinking about how this overlaps with the Curve Fill node though, at least a list of when this is useful but the other isn’t would go a long way towards making the case for such a node in master.
I would recommend using the same terms as the rest of Blender though, i.e. “Boolean” instead of “Bool”, “Intersection” instead of “And”, “Union” instead of “Or”.
For the implementation I would imagine you might be able to use the constrained Delaunay triangulation algorithm used for the Curve Fill node? What did you have in mind?
My first thought is how does the actual boolean actually look at intersection/coincidence for the operation. If there was a specific “Projection” I would imagine the usefulness would increase significantly.
In other words, if the curves aren’t perfectly on the same plane, if you could do the same sort of boolean operation that you show from the Top View, despite their z coordinates, that would be extremely useful for motion graphics, and the use case you presented I imagine.
Note: If this is already how it functions then disregard this comment.
Worth? Worth?!! It’s a must!! … First of all thank you for working on it, if you have a branch or patch I’d love to test it.
You mentioned 2d animations, but there’s definitely more areas where 2D booleans would improve workflow.
One thing I wonder is how does it work internally, are the boolean operations done directly on curve data or there’s some conversion curve → mesh → curve? Also are boolean operations faster on curve data than mesh data in general?
I tried the new Curve Fill node, and I don’t think there are any overlaps between the 2 nodes’ functionalities. The Curve Boolean node just creates the curve/path, it does not return any mesh geometry like the Curve Fill one does. It can be connected directly to a Curve Fill node to display the result :
So Delaunay triangulation should not be necessary.
Currently, z - coordinates are dropped during intersections. I thought about an input normal to project along, but users can just as easily rotate their curves before and after using this node themselves, and I want to keep the logic as simple as possible.
The node is not quite ready yet. I’ll post a link to my repository when all edge cases have been implemented.
The idea is super simple : Go along one of the curve and copy all control points, until you hit an intersection, where you switch to the other curve. Do that until you reach the end of the curve or completed a full loop. That is significantly simpler in 1D/curves than it is in 2D/hulls. A good implementation should therefore be way faster. Currently brute force is used to calculate the intersection points, and even so, performance so far has been a non issue. (But I DO plan to implement proper intersection in as few steps as feasable (It’ll still be O(n^2), because when you think about it, worst case all lines really intersect with all others, meaning O((n - 1)^2) intersection points get created, but in the average case the algorithm should be roughly proportional to the amount of intersection points, not the amount of segments, which I will attempt to get to.) ) .
The node uses the curve’s evaluated points for 2 reasons :
Intersecting 2 curves can have a lot of points of intersections. Even just a bezier x line intersection can have up to 3 intersections, and it just gets more complicated with each and every additional curve type we have to consider.
That’s a lot of hard code nobody wants.
The boolean operation should conform as closely as possible to the existing shape. If the user reduces the resolution of one of their curves, but the algorithm used an infinitely high resolution, intersection points would no longer lie on the visible curve.
I don’t know if you could call this curve → mesh → curve, but it’s definitely curve → evaluated curve points → curve, if that makes sense.
If you do end up implementing an efficient 2D segments/segments intersection algorithm I would suggest to:
Write it as a library implementation so it can be added to BLI. There are multiple areas in Blender that would benefit from such a library.
Consider using integer arithmetic. I’ve implemented something like this in the past and I know that dealing with floating points is a big issue. Especially since with these algorithms there is no “soft error”. Either you don’t find an intersection or you do. If you don’t, the whole result gets messed up
Reach out if you have any questions or issues! Again, I’ve dealt with this problem before and I’m glad to help out if I can. @filedescriptor on blender.chat
Thanks, I’ll take you up on that!
But polishing the Node is going to take at least a week still, if not two. Lots of issues to iron out. I’ll only look into optimization after everything works reliably.
Also, I’m not sure how useful my line segment intersection functions are going to be to the rest of blender. With curves we can use their topology to very quickly create meaningful bounds, and binary search from there, but with a more generic set of segments in 3D space some elaborate binning would be required to get similar performance.
No no, I am also talking about 2D space. Like you are currently doing with a very simple projection onto the xy plane for example. We already have some code for 3D intersections by Howard with the new boolean code.
Unaware of your work on this I tried implementing 2D curve booleans yesterday with the Clipper library
If you’re interested in my code to try it out let me know in blender.chat (erik85)
Well, that’s inconvenient, but at least the functionality is there.
Who would have thought after all these years we’d have the same obscure idea at the same time .
Unless the performance of your library is particularly bad, I’m obviously calling this project off. I’ve so far ignored self intersection outright, so just based on your screenshot your solution appears superior.
This was just a quick test because I found that library yesterday and couldn’t not test it. I’m not planning to continue developing it (atleast not in the near future) so I think you should definitely continue, but maybe look at using Clipper. It also has a feature to offset curves that could be useful in other genometry nodes.
Ok.
I didn’t use any external dependencies because I didn’t feel I had the clout to get them into master. I was under the impression that they were frowned upon, but I’m not so sure anymore.
Yeah I’m not sure either, some core developer will have to answer that. But there are many small libs used in Blender and for something like this it should be fine I hope. It feels a bit unnecessary to reinvent the wheel.
After thinking about this for a while, here’s how I’m going to proceed forwards :
There are both pros and cons to using a library like Erik used.
Pros :
Easier
Cleaner
Inherently works well with all current and future curve types, since they are all turned into Poly Lines
Cons :
Result Curve is always a poly line, which makes the geometry node modifier “apply” operation less useful to users.
Intersections cannot be calculated at lower resolutions, then scaled back up again for rendering.
Attributes like radius get lost unless we massively modify the library.
An external library needs to be approved. It’s small (only ~250kb), but a lot of the code inside is redundant. And getting a patch approved is historically easier without external code.
My node currently has to convert splines to bezier curves, but it always returns easily-editable bezier curves. It doesn’t even support Poly-Lines at the moment, and therefore never even returns them. Useful for users, superfluous if raw evaluated curve data is what you’re after, which 99% of the time you would be.
But taking a step back from the Node itself, all these bezier boolean operations have uses outside of Geometry Nodes. They are in fact a basis on which vector graphic programs like Inkscape work. So even if the final Node uses a simpler Poly Line approach, the code could likely find its way into a set of edit mode operations. Which means my work thus far is likely not going to waste either way. Phew.
So for the time being I’m going to continue the node like before, implementing full bezier boolean operations. After that’s done, I’ll implement Poly Line support, which should use the same internal functions, and therefore be trivial to implement, by hand. A library would be overkill, and would always need to be modified to carry over curve attributes, but the fundamental idea of returning a poly line when that’s all that the following modifiers would use anyways has merit.
You can find an up-to-date blender 3.0 with my changes here :
Make sure to only use curves without fill geometries (disable fill mode), as filled curves currently don’t work with most curve nodes, due to a bug.
Also keep in mind that currently, self intersection is not supported. If there’s an actual reason to have it, I’ll try to implement it at the very end, but for now, I can’t think of a good reason.
Performance has not been a priority thus far. But if you encounter performance issues, make sure to check whether Curve Fill or Curve To Mesh are at fault. In all my tests, those algorithms always performed worse than the actual boolean operation. Which is good. Because all of them should scale similarly well with the better line intersection algorithm I’ll be working on after all else is done.
EDIT : PolySpline support implemented. That went smooth as butter
Next up I’ll implement a “Spline to Bezier” function. Then it’s on to optimization and cleanup.
… First of all thank you for working on it, if you have a branch or patch I’d love to test it.
