These days I’m learing the source code of Blender, and I suppose I have found a bug of BMesh Operator “connect_vert_pairs” in dealing with concave polygons. It will not cause any crash, but do produce unsatisfying results. I’ll first describe the bug in a bug report format, explain the code that cause the problem, and give my proposed fix to it. Before committing my code, I think I should ask reviewers whether it is a bug to be fixed (I didn’t find existing issues talking about this).
Please read the detailed descriptions in my replies below. It may be a bit long…
Undo the connection, just move the concave point in x axis by 0.0001m (the CONNECT_EPS defined in bmo_connect_pair.cc), another awkward result (case2) will be produced by performing connection again. The path is not even continuous:
in another similar example below, I move another point on the direction of connection line, this time, Blender gives the error message “Could not connect vertices”. This is case3.
In my opinion, the implementation should be more robust to cases above, that the connection path should contain the concave vertex that is extremely close to it. I will explain the cause base on the latest Blender 4.0.0 alpha source code. In these cases, Vertex/Connect Vertex Path and Vertex/Connect Vertex Pairs both calls BMO “connect_vert_pair”(see bmesh_opdefines.cc and bmo_connect_pair.cc).
The function causes all these cases is state_step(), which starts from a BMElem in a path and tries to find the next intersection point. Let’s call the starting BMElem ele. In state_step(), BMEdges and BMVerts are separately treated by state_step__face_edges() and state_step__face_verts(). Both these functions traverse one adjacent face loop of ele, trying to find the nearest intersection point in both directions. The found point will update the state linked list and the state is inserted into the heap for sorting. This implementation causes two problems:
it cannot really find the exact next intersection point in a face.
In the sketch above, the connection path will have two intersections in one concave BMFace, but the concave vertex and the intersection on the edge are treated as different states. If the edge intersection state is chosen, the connection path will simply jump over the concave vertex.
When ele is a BMVert, loop in state_step() do not allow it to find intersections in the BMFace where ele comes from (ele_from in the code). However, when ele is the concave vertex above, it may find another intersection point in its ele_from. This is the root cause of these bugs.
Let’s make it more clear by using case 2 as an example.
Starting from START, it check its only adjacent face, face1, finding edge1 as the next intersection edge.
Now start from edge1, it only checks face2, since face1 is its ele_from. This is proper for edges though. In face2, it finds an intersection edge first (althought it’s farther away, state_step__face_edges() is called first), adds it to the path, creates state1. Then it finds CONCAVE as a intersection vertex, creates state2.
state2 gets processed first since it’s path length is lower. In state2, we start from CONCAVE, but no faces can be checked, because face2 is just its ele_from, and it does not have any other adjacent faces. As a result, the searching is interrupted, we turn to state1.
In state1, we start from edge2, and finds END in face3, the searching ends.
Now see what we get as a connection path: START–edge1–edge2–END, while CONCAVE is neglected. In current case (case2), connection line between edge1 and edge2 cuts existing edges of the concave face, so it cannot pass BM_face_splits_check_legal() in the nested BMO “connect_verts” (see bmo_connect.cc) call, so the resulted path misses the middle fragment.
If you move CONCAVE -0.0001m on x axis, case2 turns into case1, you will find a direct cut between edge1 and edge2, bypassing CONCAVE.
I have already written the fixed code, and tested on the cases above. Because of space reasons, I do not show my implementation here. If the fix is really needed, Please inform me and I’ll make a pull request. Here I try to explain the fix:
Split state_step__face_edges() and state_step__face_verts() into three functions:
A. function to find the nearest intersection edge in a BMFace, called state_step__face_edges_find(). it mainly copies the do-while loop in state_step__face_edges().
B. function to find the nearest intersection vertex in a BMFace, called state_step__face_verts_find(). it mainly copies the do-while loop in state_step__face_verts().
C. function to add new states, called state_step__face_add() , mainly copies the for(i = 0:2) loop in the original version. It takes element type sign as input, so it can deal with both BMEdges states and BMVert states.
In state_step(). when ele is BMEdge: in each BM_LOOPS_OF_EDGE loop, call A,B,C in sequence. It makes sure that the nearest BMElem is added to the new state at last, reducing states to search and possible confusion.
In state_step(). when ele is BMVert: in each BM_LOOPS_OF_VERT loop, stop checking (l_start->f != ele_from), then call A,B,C in sequence like in 2. The rest of the source code is not changed.
After doing this, case1 and case2 will generate a connection path containing the concave vertex. case3 will no longer raise an error and generate a connection path containing all relative vertices. I also test some regular cases on convex meshes such as a sphere, it functions well.
Since I do not know how to test the new implementation in a complete way, I’m not sure if it will make some working cases fail, but I’ve tried to reduce the changes in the source code as much as possible.
Thanks a lot for your reply, I can reproduce your results with the blend file you provide.
If you move your models closer to global origin, you’ll find that the connection can be performed . This may be caused by some floating point number round-off error. It seems it’s different from the case I report. If I find the possible cause, I will reply later.
Technically it is a part of a terrain geometry which was built from isolines and which require vertex connecting quite often to fix triangulation and refine the topology. This issue has been known for a long time, so I guess it better be fixed at some point.
I found that increasing CONNECT_EPS from 0.0001m to 0.001m will solve the problem. CONNECT_EPS is defined in bmo_connect_pairs.cc, it’s a threshold used to judge intersection of an edge/vertex with the connection path. It seems that it is too strict in your case, maybe the coordinates is large so that calculation errors are also magnified, exceeding CONNECT_EPS. So connect_vert_pair BMO just cannot detect the endpoint to complete the path.
Maybe Blender should give users freedom to change CONNECT_EPS in the editor. I’m don’t know how to find a value univerally applicable to all cases.
. This may be caused by some floating point number round-off error. It seems it’s different from the case I report. If I find the possible cause, I will reply later.