blender
/
blender
129
398
Fork 572
Code Issues 6.2k Pull Requests 747 Projects 19 Wiki Activity

Fix T95901: Crash in Fill curve (set to N-gon) 

The code that eats away faces until you find input faces in
the Constrained Delaunay Triangulation goes too far and crashes
when there are no input faces. In the test case there were input
faces but they only had two vertices, so were all ignored.
This commit is contained in:
Howard Trickey 2022-03-26 10:47:09 -04:00
parent 4039e94422
commit 9d25418a52
Notes: blender-bot 2023-02-14 00:44:02 +01:00 
Referenced by issue #95901, Crash - Geometry nodes using Mesh to curve > Fill curve (set to N-gon)
1 changed files with 16 additions and 6 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

22
source/blender/blenlib/intern/delaunay_2d.cc
View File

@ -2188,17 +2188,19 @@ static int power_of_10_greater_equal_to(int x)
}
/**
Incrementally each edge of each input face as an edge constraint.
* Incrementally each edge of each input face as an edge constraint.
* The code will ensure that the #CDTEdge's created will have ids that tie them
* back to the original face edge (using a numbering system for those edges
* that starts with cdt->face_edge_offset, and continues with the edges in
* order around each face in turn. And then the next face starts at
* cdt->face_edge_offset beyond the start for the previous face.
* Return the number of faces added, which may be less than input.face.size()
* in the case that some faces have less than 3 sides.
*/
template<typename T>
void add_face_constraints(CDT_state<T> *cdt_state,
const CDT_input<T> &input,
CDT_output_type output_type)
int add_face_constraints(CDT_state<T> *cdt_state,
const CDT_input<T> &input,
CDT_output_type output_type)
{
int nv = input.vert.size();
int nf = input.face.size();
@ -2216,6 +2218,7 @@ void add_face_constraints(CDT_state<T> *cdt_state,
* together the are >= INT_MAX, then the Delaunay calculation will take unreasonably long anyway.
*/
BLI_assert(INT_MAX / cdt_state->face_edge_offset > nf);
int faces_added = 0;
for (int f = 0; f < nf; f++) {
int flen = input.face[f].size();
if (flen <= 2) {
@ -2231,6 +2234,7 @@ void add_face_constraints(CDT_state<T> *cdt_state,
/* Ignore face edges with invalid vertices. */
continue;
}
++faces_added;
CDTVert<T> *v1 = cdt->get_vert_resolve_merge(iv1);
CDTVert<T> *v2 = cdt->get_vert_resolve_merge(iv2);
LinkNode *edge_list;
@ -2265,6 +2269,7 @@ void add_face_constraints(CDT_state<T> *cdt_state,
}
}
}
return faces_added;
}
/* Delete_edge but try not to mess up outer face.
@ -2642,7 +2647,8 @@ CDT_result<T> get_cdt_output(CDT_state<T> *cdt_state,
const CDT_input<T> UNUSED(input),
CDT_output_type output_type)
{
prepare_cdt_for_output(cdt_state, output_type);
CDT_output_type oty = output_type;
prepare_cdt_for_output(cdt_state, oty);
CDT_result<T> result;
CDTArrangement<T> *cdt = &cdt_state->cdt;
result.face_edge_offset = cdt_state->face_edge_offset;
@ -2774,7 +2780,11 @@ CDT_result<T> delaunay_calc(const CDT_input<T> &input, CDT_output_type output_ty
add_input_verts(&cdt_state, input);
initial_triangulation(&cdt_state.cdt);
add_edge_constraints(&cdt_state, input);
add_face_constraints(&cdt_state, input, output_type);
int actual_nf = add_face_constraints(&cdt_state, input, output_type);
if (actual_nf == 0 && !ELEM(output_type, CDT_FULL, CDT_INSIDE, CDT_CONSTRAINTS)) {
/* Can't look for faces or holes if there were no valid input faces. */
output_type = CDT_INSIDE;
}
return get_cdt_output(&cdt_state, input, output_type);
}