Commit: abd7b1c20e06ac6077d9fc0caf0369afac24c499
Author: Howard Trickey
Date: Sat Aug 15 08:24:19 2020 -0400
Branches: newboolean
https://developer.blender.org/rBabd7b1c20e06ac6077d9fc0caf0369afac24c499
Merge branch 'master' into newboolean
===================================================================
===================================================================
diff --cc source/blender/blenlib/CMakeLists.txt
index e4a90b74b87,819c74b6946..2ddc15fb894
--- a/source/blender/blenlib/CMakeLists.txt
+++ b/source/blender/blenlib/CMakeLists.txt
@@@ -370,16 -347,38 +370,40 @@@ blender_add_lib(bf_blenlib "${SRC}" "${
if(WITH_GTESTS)
set(TEST_SRC
+ tests/BLI_array_store_test.cc
tests/BLI_array_test.cc
+ tests/BLI_array_utils_test.cc
++ tests/BLI_boolean_test.cc
+ tests/BLI_delaunay_2d_test.cc
tests/BLI_disjoint_set_test.cc
tests/BLI_edgehash_test.cc
+ tests/BLI_expr_pylike_eval_test.cc
+ tests/BLI_ghash_test.cc
+ tests/BLI_hash_mm2a_test.cc
+ tests/BLI_heap_simple_test.cc
+ tests/BLI_heap_test.cc
tests/BLI_index_mask_test.cc
tests/BLI_index_range_test.cc
+ tests/BLI_kdopbvh_test.cc
tests/BLI_linear_allocator_test.cc
+ tests/BLI_linklist_lockfree_test.cc
+ tests/BLI_listbase_test.cc
tests/BLI_map_test.cc
tests/BLI_math_base_safe_test.cc
+ tests/BLI_math_base_test.cc
+ tests/BLI_math_bits_test.cc
+ tests/BLI_math_color_test.cc
+ tests/BLI_math_geom_test.cc
+ tests/BLI_math_matrix_test.cc
+ tests/BLI_math_vector_test.cc
+ tests/BLI_memiter_test.cc
tests/BLI_memory_utils_test.cc
++ tests/BLI_mesh_intersect_test.cc
tests/BLI_multi_value_map_test.cc
+ tests/BLI_path_util_test.cc
+ tests/BLI_polyfill_2d_test.cc
+ tests/BLI_ressource_strings.h
+ tests/BLI_session_uuid_test.cc
tests/BLI_set_test.cc
tests/BLI_span_test.cc
tests/BLI_stack_cxx_test.cc
diff --cc source/blender/blenlib/tests/BLI_boolean_test.cc
index 474e963deeb,00000000000..474e963deeb
mode 100644,000000..100644
--- a/source/blender/blenlib/tests/BLI_boolean_test.cc
+++ b/source/blender/blenlib/tests/BLI_boolean_test.cc
diff --cc source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
index 00ebd4b0d35,752f833461d..2287389f7aa
--- a/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
+++ b/source/blender/blenlib/tests/BLI_delaunay_2d_test.cc
@@@ -76,81 -102,87 +76,81 @@@ template<typename T> CDT_input<T> fill_
}
i++;
}
- fill_input_verts(r_input, p, nverts);
- if (nedges > 0) {
- add_input_edges(r_input, e, nedges);
+ CDT_input<T> ans;
+ ans.vert = verts;
+ ans.edge = edges;
+ ans.face = faces;
+#ifdef WITH_GMP
+ if (std::is_same<mpq_class, T>::value) {
+ ans.epsilon = T(0);
}
- if (nfaces > 0) {
- for (i = 0; i < nfaces; i++) {
- flen[i] = (int)faces[i].size();
- if (i == 0) {
- fstart[i] = 0;
- }
- else {
- fstart[i] = fstart[i - 1] + flen[i - 1];
- }
- }
- farr = (int *)MEM_malloc_arrayN(fstart[nfaces - 1] + flen[nfaces - 1],
sizeof(int), __func__);
- for (i = 0; i < nfaces; i++) {
- for (j = 0; j < (int)faces[i].size(); j++) {
- farr[fstart[i] + j] = faces[i][j];
+ else {
+ ans.epsilon = T(0.00001);
+ }
+#else
+ ans.epsilon = T(0.00001);
+#endif
+ return ans;
+}
+
+/* Find an original index in a table mapping new to original.
+ * Return -1 if not found.
+ */
- int get_orig_index(const Array<Vector<int>> &out_to_orig, int orig_index)
++static int get_orig_index(const Array<Vector<int>> &out_to_orig, int
orig_index)
+{
+ int n = static_cast<int>(out_to_orig.size());
+ for (int i = 0; i < n; ++i) {
+ for (int orig : out_to_orig[i]) {
+ if (orig == orig_index) {
+ return i;
}
}
- add_input_faces(r_input, farr, fstart, flen, nfaces);
}
+ return -1;
}
- template<typename T> static double math_to_double(const T v)
-#if DO_FILE_TESTS
-static void fill_input_from_file(CDT_input *in, const char *filename)
++template<typename T> static double math_to_double(const T UNUSED(v))
{
- std::FILE *fp = std::fopen(filename, "rb");
- if (fp) {
- std::string contents;
- std::fseek(fp, 0, SEEK_END);
- contents.resize(std::ftell(fp));
- std::rewind(fp);
- std::fread(&contents[0], 1, contents.size(), fp);
- std::fclose(fp);
- fill_input_from_string(in, contents.c_str());
- }
- else {
- printf("couldn't open file %s\n", filename);
- }
+ BLI_assert(false); /* Need implementation for other type. */
+ return 0.0;
}
-#endif
-static void free_spec_arrays(CDT_input *in)
+template<> double math_to_double<double>(const double v)
{
- if (in->vert_coords) {
- MEM_freeN(in->vert_coords);
- }
- if (in->edges) {
- MEM_freeN(in->edges);
- }
- if (in->faces_len_table) {
- MEM_freeN(in->faces_len_table);
- MEM_freeN(in->faces_start_table);
- MEM_freeN(in->faces);
- }
+ return v;
}
-/* which output vert index goes with given input vertex? -1 if not found */
-static int get_output_vert_index(const CDT_result *r, int in_index)
+#ifdef WITH_GMP
+template<> double math_to_double<mpq_class>(const mpq_class v)
{
- int i, j;
+ return v.get_d();
+}
+#endif
- for (i = 0; i < r->verts_len; i++) {
- for (j = 0; j < r->verts_orig_len_table[i]; j++) {
- if (r->verts_orig[r->verts_orig_start_table[i] + j] == in_index) {
- return i;
- }
- }
- }
- return -1;
+template<typename T> static T math_abs(const T v);
+
+#ifdef WITH_GMP
+template<> mpq_class math_abs(const mpq_class v)
+{
+ return abs(v);
}
+#endif
-/* which output edge index is for given output vert indices? */
-static int get_edge(const CDT_result *r, int out_index_1, int out_index_2)
+template<> double math_abs(const double v)
{
- int i;
+ return fabs(v);
+}
- for (i = 0; i < r->edges_len; i++) {
- if ((r->edges[i][0] == out_index_1 && r->edges[i][1] == out_index_2) ||
- (r->edges[i][0] == out_index_2 && r->edges[i][1] == out_index_1)) {
+/* Find an output index corresponding to a given coordinate (appproximately).
+ * Return -1 if not found.
+ */
+template<typename T> int get_vertex_by_coord(const CDT_result<T> &out, double
x, double y)
+{
+ int nv = static_cast<int>(out.vert.size());
+ for (int i = 0; i < nv; ++i) {
+ double vx = math_to_double(out.vert[i][0]);
+ double vy = math_to_double(out.vert[i][1]);
+ if (fabs(vx - x) <= 1e-5 && fabs(vy - y) <= 1e-5) {
return i;
}
}
@@@ -204,185 -235,89 +204,185 @@@ template<typename T> int get_output_fac
return -1;
}
-static int get_face_tri(const CDT_result *r, int out_index_1, int
out_index_2, int out_index_3)
+template<typename T>
+int get_output_tri_index(const CDT_result<T> &out,
+ int out_index_1,
+ int out_index_2,
+ int out_index_3)
{
- int tri[3];
+ Array<int> tri{out_index_1, out_index_2, out_index_3};
+ return get_output_face_index(out, tri);
+}
- tri[0] = out_index_1;
- tri[1] = out_index_2;
- tri[2] = out_index_3;
- return get_face(r, tri, 3);
+template<typename T>
+bool output_face_has_input_id(const CDT_result<T> &out, int out_face_index,
int in_face_index)
+{
+ return out_face_index < static_cast<int>(out.face_orig.size()) &&
+ out.face_orig[out_face_index].contains(in_face_index);
}
-/* return true if given otuput face has given input face id in its originals
list */
-static bool out_face_has_input_id(const CDT_result *r, int out_face_index,
int in_face_index)
+/* For debugging. */
+template<typename T> std::ostream &operator<<(std::ostream &os, const
CDT_result<T> &r)
{
- if (r->faces_orig == NULL) {
- return false;
+ os << "\nRESULT\n";
+ os << r.vert.size() << " verts, " << r.edge.size() << " edges, " <<
r.face.size() << " faces\n";
+ os << "\nVERTS\n";
+ for (int i : r.vert.index_range()) {
+ os << "v" << i << " = " << r.vert[i] << "\n";
+ os << " orig: ";
+ for (int j : r.vert_orig[i].index_range()) {
+ os << r.vert_orig[i][j] << " ";
+ }
+ os << "\n";
}
- if (out_face_index < 0 || out_face_index >= r->faces_len) {
- return false;
+ os << "\nEDGES\n";
+ for (int i : r.edge.index_range()) {
+ os << "e" << i << " = (" << r.edge[i].first << ", " << r.edge[i].second
<< ")\n";
+ os << " orig: ";
+ for (int j : r.edge_orig[i].size()) {
+ os << r.edge_orig[i][j] << " ";
+ }
+ os << "\n";
}
- for (int i = 0; i < r->faces_orig_len_table[out_face_index]; i++) {
- if (r->faces_orig[r->faces_orig_start_table[out_face_index] + i] ==
in_face_index) {
- return true;
+ os << "\nFACES\n";
+ for (int i : r.face.index_range()) {
+ os << "f" << i << " = ";
+ for (int j : r.face[i].index_range()) {
+ os << r.face[i][j] << " ";
}
+ os << "\n";
+ os << " orig: ";
+ for (int j : r.face_orig[i].index_range()) {
+ os << r.face_orig[i][j] << " ";
+ }
+ os << "\n";
}
- return false;
+ return os;
}
-#if DO_FILE_TESTS
-/* for debugging */
-static void dump_result(CDT_result *r)
-{
- int i, j;
+static bool draw_append = false; /* Will be set to true after first call. */
- fprintf(stderr, "\nRESULT\n");
- fprintf(stderr,
- "verts_len=%d edges_len=%d faces_len=%d\n",
- r->verts_len,
- r->edges_len,
- r->faces_len);
- fprintf(stderr, "\nvert coords:\n");
- for (i = 0; i < r->verts_len; i++) {
- fprintf(stderr, "%d: (%f,%f)\n", i, r->vert_coords[i][0],
r->vert_coords[i][1]);
+template<typename T>
+void graph_draw(const std::string &label,
+ const Array<vec2<T>> &verts,
+ const Array<std::pair<int, int>> &edges,
- const Array<Vector<int>> &faces)
++ const Array<Vector<int>> &UNUSED(faces))
+{
+ /* Would like to use BKE_tempdir_base() here, but that brings in dependence
on kernel library.
+ * This is just for developer debugging anyway, and should never be called
in production Blender.
+ */
- #if WIN32
++#ifdef WIN32
+ constexpr const char *drawfile = "./cdt_test_draw.html";
+#else
+ constexpr const char *drawfile = "/tmp/cdt_test_draw.html";
+#endif
+ constexpr int max_draw_width = 1400;
+ constexpr int max_draw_height = 1000;
+ constexpr int thin_line = 1;
+ constexpr int vert_radius = 3;
+ const
@@ Diff output truncated at 10240 characters. @@
_______________________________________________
Bf-blender-cvs mailing list
[email protected]
https://lists.blender.org/mailman/listinfo/bf-blender-cvs
