[Bf-blender-cvs] [de2c4ee5878] master: Another slight increase in speed for Delaunay CDT.
Howard Trickey
noreply at git.blender.org
Fri Jul 23 14:33:03 CEST 2021
Commit: de2c4ee58782a26f0e2dcac47d54bceb67a137e2
Author: Howard Trickey
Date: Fri Jul 23 08:31:40 2021 -0400
Branches: master
https://developer.blender.org/rBde2c4ee58782a26f0e2dcac47d54bceb67a137e2
Another slight increase in speed for Delaunay CDT.
When the new "need_ids" flag is false and the output type is not
one of the valid BMesh kinds, there is no need to propagate even
a dummy id to all of the faces.
===================================================================
M source/blender/blenlib/intern/delaunay_2d.cc
M source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
===================================================================
diff --git a/source/blender/blenlib/intern/delaunay_2d.cc b/source/blender/blenlib/intern/delaunay_2d.cc
index 47e4617d094..4582ea69d9b 100644
--- a/source/blender/blenlib/intern/delaunay_2d.cc
+++ b/source/blender/blenlib/intern/delaunay_2d.cc
@@ -2208,7 +2208,10 @@ static int power_of_10_greater_equal_to(int x)
* order around each face in turn. And then the next face starts at
* cdt->face_edge_offset beyond the start for the previous face.
*/
-template<typename T> void add_face_constraints(CDT_state<T> *cdt_state, const CDT_input<T> &input)
+template<typename T>
+void 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();
@@ -2265,8 +2268,16 @@ template<typename T> void add_face_constraints(CDT_state<T> *cdt_state, const CD
}
int fedge_end = fedge_start + flen - 1;
if (face_symedge0 != nullptr) {
+ /* We need to propagate face ids to all faces that represent #f, if #need_ids.
+ * Even if `need_ids == false`, we need to propagate at least the fact that
+ * the face ids set would be non-empty if the output type is one of the ones
+ * making valid BMesh faces. */
int id = cdt_state->need_ids ? f : 0;
add_face_ids(cdt_state, face_symedge0, id, fedge_start, fedge_end);
+ if (cdt_state->need_ids || (output_type == CDT_CONSTRAINTS_VALID_BMESH ||
+ output_type == CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES)) {
+ add_face_ids(cdt_state, face_symedge0, f, fedge_start, fedge_end);
+ }
}
fstart += flen;
}
@@ -2779,7 +2790,7 @@ 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);
+ add_face_constraints(&cdt_state, input, output_type);
return get_cdt_output(&cdt_state, input, output_type);
}
diff --git a/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc b/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
index f158a5bbae9..f221036419e 100644
--- a/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
+++ b/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
@@ -1948,6 +1948,12 @@ void text_test(
if (num_lines > 1) {
label += " lines=" + std::to_string(num_lines);
}
+ if (!need_ids) {
+ label += " no_ids";
+ }
+ if (otype != CDT_INSIDE_WITH_HOLES) {
+ label += " otype=" + std::to_string(otype);
+ }
graph_draw<T>(label, out.vert, out.edge, out.face);
}
}
@@ -1957,6 +1963,51 @@ TEST(delaunay_d, TextB10)
text_test<double>(10, 1, 1, CDT_INSIDE_WITH_HOLES, true);
}
+TEST(delaunay_d, TextB10_noids)
+{
+ text_test<double>(10, 1, 1, CDT_INSIDE_WITH_HOLES, false);
+}
+
+TEST(delaunay_d, TextB10_inside)
+{
+ text_test<double>(10, 1, 1, CDT_INSIDE, true);
+}
+
+TEST(delaunay_d, TextB10_inside_noids)
+{
+ text_test<double>(10, 1, 1, CDT_INSIDE, false);
+}
+
+TEST(delaunay_d, TextB10_constraints)
+{
+ text_test<double>(10, 1, 1, CDT_CONSTRAINTS, true);
+}
+
+TEST(delaunay_d, TextB10_constraints_noids)
+{
+ text_test<double>(10, 1, 1, CDT_CONSTRAINTS, false);
+}
+
+TEST(delaunay_d, TextB10_constraints_valid_bmesh)
+{
+ text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH, true);
+}
+
+TEST(delaunay_d, TextB10_constraints_valid_bmesh_noids)
+{
+ text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH, false);
+}
+
+TEST(delaunay_d, TextB10_constraints_valid_bmesh_with_holes)
+{
+ text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, true);
+}
+
+TEST(delaunay_d, TextB10_constraints_valid_bmesh_with_holes_noids)
+{
+ text_test<double>(10, 1, 1, CDT_CONSTRAINTS_VALID_BMESH_WITH_HOLES, false);
+}
+
TEST(delaunay_d, TextB200)
{
text_test<double>(200, 1, 1, CDT_INSIDE_WITH_HOLES, true);
More information about the Bf-blender-cvs
mailing list