recently I do some investigation in nurbs code in blender : https://devtalk.blender.org/t/better-curve-surface-support https://devtalk.blender.org/t/branch-soc-2014-nurbs-update-to-master-code-base-d6807
I found that blender does not seem to have a unified 2D Boolean library for general purposes
In fact, if blender comes with a 2D Boolean library, the possible benefits are:
- Multiple box selection methods can be added in blender boudbox selection mode
- NURBS UV domain can dig holes and let blender support NURBS file format in the sense of modern system
- Unified curves spline trim algorithm
I’d like to consult the developers
What are the open source best practices 2D Boolean libraries now?
What are the binding requirements of blender for the library of such functions to enter the code?
2 Likes
I remember seeing a thread where @Howard_Trickey had mentioned a long term goal for 2d booleans but it sounded pretty far out based on his workload. Maybe you can coordinate with Howard and help out on that front?
I’m very glad to hear that the fundation has its own plan.
If there really need help, I’d love to participate
Were you thinking of a library that does booleans on 2d polygons, or something more general (say, with boundaries that are piecewise curves)? My vague plans were only for the former, and were along the lines of taking the 2D delaunay triangulation library function I have added to Blender, and either modify it or put a layer on top of it so that the resulting triangles, which are labeled according to which original polygons they came from, can be used to construct the boolean result.
I have other stuff higher priority than this to work on but if you are a coder and would like to work on this, with my advice and help, contact me in, say, blender.chat and we can talk.
Another possibility would be to find an open source library with an appropriate license and include it as a new dependency in Blender. We don’t do that lightly, however, and would probably need a compelling case of actual useful code in an acceptable patch that relies on that library before adding it, not just a “it would open these possibilities” kind of statement.
Thank you very much for your reply
My main purpose of requiring 2D Boolean library is to promote the NURBS branch to meet the official requirements and be incorporated into the trunk, because I found that this branch has implemented a set of code of Ploygon clip.
I found that after seven years, none of Blender’s developers have really seen the code content of this 2014 branch. Maybe NURBS is a very simple topic, but after all these years, no one has written a reliable basic layer of NURBS. I tried to merge the branch code into the trunk two years ago and submitted an application for code review, but two years later, no developers have asked about it.
Therefore, I want to be more proactive in promoting this matter (code review). I have carefully read the code implementation at that time. A large part of the content of UV domain is the implementation of a set of Ploygon clips. However, it is not known whether these codes are robust. From my education, it is right not to build wheels repeatedly at the right times. Although I have 20 years of blender experience in my life, I don’t have much time to participate in blender development. Therefore, it is often necessary to consult the opinions of relevant development before making a decision.
I also found a library of similar algorithms: Clipper - an open source freeware polygon clipping library It is based on C + +. I don’t know whether these functions are satisfied, so I also want to deeply understand the views of relevant parties.
I live in China, so my schedule may be different from yours,I very much hope to consult you at the blender.chat during your working hours. I don’t know when it’s convenient for you. Thank you again.
1 Like
The Clipper library might be ok – its license seems compatible with GPL. But a big concern is that it seems not to be actively maintained (last update in 2014). Maybe the library is bug-free and doesn’t need any future updates, but that is not too likely.
I am in the New York area, so typically available on blender chat during waking hours NY time.
Thank Howard very much for providing very detailed information. Because my English is not very good, I have read it for a long time.
I am considering how to combine the high level API design of 2D Boolean with some features of constrained Delaunay triangulation.
The following are some of my immature thoughts. If someone is familiar with this aspect, I hope they could provide more detailed suggestions.
I copied the code of gsoc2014 NURBS branch as follows:
/******************** Booleans ********************/
// High level
void bool_AND(int poly2); // gridmesh -> gridmesh (intersection) poly2
void bool_SUB(int poly2); // gridmesh -> gridmesh (intersection) ~poly2
// Low level boolean support algorithms
// Step 1: insert verts at intersections
void insert_vert_poly_gridmesh(int poly,
int *verts_added=NULL,
int *edges_intersected=NULL);
// Step 2: find mutual entry/exit points
void label_interior_AND(int poly2, bool invert_poly2=false, int *bb=NULL);
void label_interior_SUB(int poly2, int *bb=NULL);
void label_exterior_cells(int poly, bool interior_lbl, int* bb=NULL);
known_corner_t label_interior_cell(int cell, int poly2, bool bool_SUB, known_corner_t kin);
void label_interior_freepoly(int poly);
// Step 3: perform the actual trim
void trim_to_odd(int *bb=NULL);
void trim_to_odd(int poly); // Trim one grid poly, leaving behind parts w/odd winding# in .next_poly linked list
The simplest case may be like this. Input a domain surrounded by a quadrilateral and the lines of two trims. The final output may be in two cases.
The input trim line segment can be marked as interior and exterior, so we can get a variety of combinations.
In the code of gsoc2014 NURBS branch, a gridmesh is defined for the domain construction of NURBS. Each small box is defined as a cell, and each cell is surrounded by a poly of quadrilateral points.
We need a method to find the intersection of the edges in low level routine. I think the implementation of gsoc2014 NURBS branch seems to use Bresenham algorithm. Without careful annotation, I can only guess that it is this kind of algorithm.
In the output after intersection, this part of the code gives the code of the combination of quadrilateral and triangle.
Through CDT we get all triangle output. Of course , the quadrilateral combination equipment can be re equipped according to the index, but I haven’t thought about this part clearly.
I am not sure I understand what you are saying and asking for suggestions about.
In your first post: the idea of having several input curves, each with an annotation saying which side is “inside” and which is “outside” makes sense to me. One could either give explicit annotations as you seem to be suggesting, or it could be implicit by the direction that the curve has in the plane: usually, as you go around a curve counterclockwise, the inside is on the left of the curve.
In your second post, you seem to be talking about how the implementation in gsoc2014 NURBS did trimming by overlaying a fine grid and finding the intersection of the various curves with that grid; then deciding for each grid square whether that square is “inside” or “outside” the final result. That is certainly a possible way of approaching the problem. If you follow that way, I don’t see the need for code that knows how to intersect and do booleans on polygons, however: I don’t really see the value that my earlier suggestion of using CDT would add here. An alternative to that grid approach would be to convert each NURBS curve into a connected series of line segments, and then use something like the CDT algorithm to intersect all of the line segments with each other. In that method, I don’t see the need for bringing a grid into things. Whether you use the first method (grid) or second (polyline intersection) is up to you and probably tests you might do to see which works better and works faster.
Just to comment on the Clipper library, the current version is pretty robust - I’ve been using it in the C# version for years for precision engineering tools. It forces an upscale to ints (32-bit or 64-bit) to run, and then you would have to downscale again. He does this to avoid precision issues with floating point values.
There is a version 2 that the developer is working on, which is a rework of the code (primarily in Pascal, with a C++ variant that was contributed and may not yet be fully maintained). The approach taken in version 2 seems to be much more efficient, but is hung up on some micro tessellation issues that he is still trying to resolve.
1 Like
Sorry for late reply.
Recently, I was in China negotiating a six-month Code development related to Blender contract with a client, which took a lot of time.
That’s what I’m thinking now, seeing as blender is starting to move into c++.Would like to use a unified class to include all things 2d boolean. Possibly use c++ function overloading to implement all the various 2d boolean methods in a single class.
When the contract is fulfilled, I may start some simple testing work.
ClipperLib 2 is making progress now with maturing ports to C#/C++
Looking at the docs, I’ve noticed it also has an offset function for polygons. Slightly diverging from the topic, but that would be a very welcome addition to Blender, as the current inset tool makes a mess when there are vertices close to each other, and then overlapping them
2 Likes
