Merge branch 'master' into temp_bmesh_multires

13 files changed, 145 insertions, 48 deletions

diff --git a/source/blender/blenlib/BLI_rand.h b/source/blender/blenlib/BLI_rand.h
index ec74cef9311..f8627952628 100644
--- a/source/blender/blenlib/BLI_rand.h
+++ b/source/blender/blenlib/BLI_rand.h
@@ -71,6 +71,9 @@ void BLI_rng_shuffle_array(struct RNG *rng,
                            unsigned int elem_size_i,
                            unsigned int elem_tot) ATTR_NONNULL(1, 2);
 
+void BLI_rng_shuffle_bitmap(struct RNG *rng, unsigned int *bitmap, unsigned int bits_tot)
+    ATTR_NONNULL(1, 2);
+
 /** Note that skipping is as slow as generating n numbers! */
 void BLI_rng_skip(struct RNG *rng, int n) ATTR_NONNULL(1);
 
@@ -89,6 +92,9 @@ void BLI_array_randomize(void *data,
                          unsigned int elem_tot,
                          unsigned int seed);
 
+void BLI_bitmap_randomize(unsigned int *bitmap, unsigned int bits_tot, unsigned int seed)
+    ATTR_NONNULL(1);
+
 /** Better seed for the random number generator, using noise.c hash[] */
 /** Allows up to BLENDER_MAX_THREADS threads to address */
 void BLI_thread_srandom(int thread, unsigned int seed);
diff --git a/source/blender/blenlib/BLI_utildefines.h b/source/blender/blenlib/BLI_utildefines.h
index 0ddabcaa2fb..5b84e050f82 100644
--- a/source/blender/blenlib/BLI_utildefines.h
+++ b/source/blender/blenlib/BLI_utildefines.h
@@ -788,23 +788,24 @@ extern bool BLI_memory_is_zero(const void *arr, const size_t arr_size);
     extern "C++" { \
     inline constexpr _enum_type operator|(_enum_type a, _enum_type b) \
     { \
-      return static_cast<_enum_type>(static_cast<int>(a) | b); \
+      return static_cast<_enum_type>(static_cast<uint64_t>(a) | static_cast<uint64_t>(b)); \
     } \
     inline constexpr _enum_type operator&(_enum_type a, _enum_type b) \
     { \
-      return static_cast<_enum_type>(static_cast<int>(a) & b); \
+      return static_cast<_enum_type>(static_cast<uint64_t>(a) & static_cast<uint64_t>(b)); \
     } \
     inline constexpr _enum_type operator~(_enum_type a) \
     { \
-      return static_cast<_enum_type>(~static_cast<int>(a) & (2 * _max_enum_value - 1)); \
+      return static_cast<_enum_type>(~static_cast<uint64_t>(a) & \
+                                     (2 * static_cast<uint64_t>(_max_enum_value) - 1)); \
     } \
     inline _enum_type &operator|=(_enum_type &a, _enum_type b) \
     { \
-      return a = static_cast<_enum_type>(static_cast<int>(a) | b); \
+      return a = static_cast<_enum_type>(static_cast<uint64_t>(a) | static_cast<uint64_t>(b)); \
     } \
     inline _enum_type &operator&=(_enum_type &a, _enum_type b) \
     { \
-      return a = static_cast<_enum_type>(static_cast<int>(a) & b); \
+      return a = static_cast<_enum_type>(static_cast<uint64_t>(a) & static_cast<uint64_t>(b)); \
     } \
     } /* extern "C++" */
 
diff --git a/source/blender/blenlib/BLI_vector.hh b/source/blender/blenlib/BLI_vector.hh
index 0e878d549c1..da02c4f4ae1 100644
--- a/source/blender/blenlib/BLI_vector.hh
+++ b/source/blender/blenlib/BLI_vector.hh
@@ -213,7 +213,8 @@ class Vector {
    * Example Usage:
    *  Vector<ModifierData *> modifiers(ob->modifiers);
    */
-  Vector(ListBase &values, Allocator allocator = {}) : Vector(NoExceptConstructor(), allocator)
+  Vector(const ListBase &values, Allocator allocator = {})
+      : Vector(NoExceptConstructor(), allocator)
   {
     LISTBASE_FOREACH (T, value, &values) {
       this->append(value);
@@ -507,10 +508,10 @@ class Vector {
   }
 
   /**
-   * Enlarges the size of the internal buffer that is considered to be initialized. This invokes
-   * undefined behavior when when the new size is larger than the capacity. The method can be
-   * useful when you want to call constructors in the vector yourself. This should only be done in
-   * very rare cases and has to be justified every time.
+   * Enlarges the size of the internal buffer that is considered to be initialized.
+   * This invokes undefined behavior when the new size is larger than the capacity.
+   * The method can be useful when you want to call constructors in the vector yourself.
+   * This should only be done in very rare cases and has to be justified every time.
    */
   void increase_size_by_unchecked(const int64_t n) noexcept
   {
diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index a0e94e00634..8f556e0ddb6 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -1212,7 +1212,7 @@ static void tree_overlap_traverse_cb(BVHOverlapData_Thread *data_thread,
 }
 
 /**
- * a version of #tree_overlap_traverse_cb that that break on first true return.
+ * a version of #tree_overlap_traverse_cb that break on first true return.
  */
 static bool tree_overlap_traverse_num(BVHOverlapData_Thread *data_thread,
                                       const BVHNode *node1,
diff --git a/source/blender/blenlib/intern/kdtree_impl.h b/source/blender/blenlib/intern/kdtree_impl.h
index 2a0e8b3ec68..2aec3ce082a 100644
--- a/source/blender/blenlib/intern/kdtree_impl.h
+++ b/source/blender/blenlib/intern/kdtree_impl.h
@@ -967,7 +967,7 @@ static int kdtree_node_cmp_deduplicate(const void *n0_p, const void *n1_p)
 }
 
 /**
- * Remove exact duplicates (run before before balancing).
+ * Remove exact duplicates (run before balancing).
  *
  * Keep the first element added when duplicates are found.
  */
diff --git a/source/blender/blenlib/intern/math_color.c b/source/blender/blenlib/intern/math_color.c
index 67c4ad95d79..263c508c07c 100644
--- a/source/blender/blenlib/intern/math_color.c
+++ b/source/blender/blenlib/intern/math_color.c
@@ -717,13 +717,17 @@ void blackbody_temperature_to_rgb_table(float *r_table, int width, float min, fl
 /* ****************************** wavelength ******************************** */
 /* Wavelength to RGB. */
 
-/* CIE colour matching functions xBar, yBar, and zBar for
- *   wavelengths from 380 through 780 nanometers, every 5
- *   nanometers.
+/**
+ * CIE color matching functions `xBar`, `yBar`, and `zBar` for
+ * wavelengths from 380 through 780 nanometers, every 5 nanometers.
+ *
  * For a wavelength lambda in this range:
- *   cie_colour_match[(lambda - 380) / 5][0] = xBar
- *   cie_colour_match[(lambda - 380) / 5][1] = yBar
- *   cie_colour_match[(lambda - 380) / 5][2] = zBar */
+ * \code{.txt}
+ * cie_color_match[(lambda - 380) / 5][0] = xBar
+ * cie_color_match[(lambda - 380) / 5][1] = yBar
+ * cie_color_match[(lambda - 380) / 5][2] = zBar
+ * \endcode
+ */
 
 static float cie_colour_match[81][3] = {
     {0.0014f, 0.0000f, 0.0065f}, {0.0022f, 0.0001f, 0.0105f}, {0.0042f, 0.0001f, 0.0201f},
diff --git a/source/blender/blenlib/intern/mesh_intersect.cc b/source/blender/blenlib/intern/mesh_intersect.cc
index 32f0216951a..988988179fd 100644
--- a/source/blender/blenlib/intern/mesh_intersect.cc
+++ b/source/blender/blenlib/intern/mesh_intersect.cc
@@ -1386,7 +1386,7 @@ static ITT_value intersect_tri_tri(const IMesh &tm, int t1, int t2)
   int sr1 = filter_plane_side(d_r1, d_r2, d_n2, abs_d_r1, abs_d_r2, abs_d_n2);
   if ((sp1 > 0 && sq1 > 0 && sr1 > 0) || (sp1 < 0 && sq1 < 0 && sr1 < 0)) {
 #  ifdef PERFDEBUG
-    incperfcount(2); /* Tri tri intersects decided by filter plane tests. */
+    incperfcount(2); /* Triangle-triangle intersects decided by filter plane tests. */
 #  endif
     if (dbg_level > 0) {
       std::cout << "no intersection, all t1's verts above or below t2\n";
@@ -1404,7 +1404,7 @@ static ITT_value intersect_tri_tri(const IMesh &tm, int t1, int t2)
   int sr2 = filter_plane_side(d_r2, d_r1, d_n1, abs_d_r2, abs_d_r1, abs_d_n1);
   if ((sp2 > 0 && sq2 > 0 && sr2 > 0) || (sp2 < 0 && sq2 < 0 && sr2 < 0)) {
 #  ifdef PERFDEBUG
-    incperfcount(2); /* Tri tri intersects decided by filter plane tests. */
+    incperfcount(2); /* Triangle-triangle intersects decided by filter plane tests. */
 #  endif
     if (dbg_level > 0) {
       std::cout << "no intersection, all t2's verts above or below t1\n";
@@ -1446,7 +1446,7 @@ static ITT_value intersect_tri_tri(const IMesh &tm, int t1, int t2)
       std::cout << "no intersection, all t1's verts above or below t2 (exact)\n";
     }
 #  ifdef PERFDEBUG
-    incperfcount(3); /* Tri tri intersects decided by exact plane tests. */
+    incperfcount(3); /* Triangle-triangle intersects decided by exact plane tests. */
 #  endif
     return ITT_value(INONE);
   }
@@ -1478,7 +1478,7 @@ static ITT_value intersect_tri_tri(const IMesh &tm, int t1, int t2)
       std::cout << "no intersection, all t2's verts above or below t1 (exact)\n";
     }
 #  ifdef PERFDEBUG
-    incperfcount(3); /* Tri tri intersects decided by exact plane tests. */
+    incperfcount(3); /* Triangle-triangle intersects decided by exact plane tests. */
 #  endif
     return ITT_value(INONE);
   }
@@ -1998,6 +1998,10 @@ static Array<Face *> polyfill_triangulate_poly(Face *f, IMeshArena *arena)
  * If this happens, we use the polyfill triangulator instead. We don't
  * use the polyfill triangulator by default because it can create degenerate
  * triangles (which we can handle but they'll create non-manifold meshes).
+ *
+ * While it is tempting to handle quadrilaterals specially, since that
+ * is by far the usual case, we need to know if the quad is convex when
+ * projected before doing so, and that takes a fair amount of computation by itself.
  */
 static Array<Face *> triangulate_poly(Face *f, IMeshArena *arena)
 {
@@ -2099,20 +2103,6 @@ IMesh triangulate_polymesh(IMesh &imesh, IMeshArena *arena)
     if (flen == 3) {
       face_tris.append(f);
     }
-    else if (flen == 4) {
-      const Vert *v0 = (*f)[0];
-      const Vert *v1 = (*f)[1];
-      const Vert *v2 = (*f)[2];
-      const Vert *v3 = (*f)[3];
-      int eo_01 = f->edge_orig[0];
-      int eo_12 = f->edge_orig[1];
-      int eo_23 = f->edge_orig[2];
-      int eo_30 = f->edge_orig[3];
-      Face *f0 = arena->add_face({v0, v1, v2}, f->orig, {eo_01, eo_12, -1}, {false, false, false});
-      Face *f1 = arena->add_face({v0, v2, v3}, f->orig, {-1, eo_23, eo_30}, {false, false, false});
-      face_tris.append(f0);
-      face_tris.append(f1);
-    }
     else {
       Array<Face *> tris = triangulate_poly(f, arena);
       for (Face *tri : tris) {
diff --git a/source/blender/blenlib/intern/rand.cc b/source/blender/blenlib/intern/rand.cc
index 8dbfffbad20..db5e08d37ce 100644
--- a/source/blender/blenlib/intern/rand.cc
+++ b/source/blender/blenlib/intern/rand.cc
@@ -28,6 +28,7 @@
 
 #include "MEM_guardedalloc.h"
 
+#include "BLI_bitmap.h"
 #include "BLI_math.h"
 #include "BLI_rand.h"
 #include "BLI_rand.hh"
@@ -149,18 +150,16 @@ void BLI_rng_get_tri_sample_float_v3(
 
 void BLI_rng_shuffle_array(RNG *rng, void *data, unsigned int elem_size_i, unsigned int elem_tot)
 {
-  const uint elem_size = elem_size_i;
-  unsigned int i = elem_tot;
-  void *temp;
-
   if (elem_tot <= 1) {
     return;
   }
 
-  temp = malloc(elem_size);
+  const uint elem_size = elem_size_i;
+  unsigned int i = elem_tot;
+  void *temp = malloc(elem_size);
 
   while (i--) {
-    unsigned int j = BLI_rng_get_uint(rng) % elem_tot;
+    const unsigned int j = BLI_rng_get_uint(rng) % elem_tot;
     if (i != j) {
       void *iElem = (unsigned char *)data + i * elem_size_i;
       void *jElem = (unsigned char *)data + j * elem_size_i;
@@ -173,6 +172,24 @@ void BLI_rng_shuffle_array(RNG *rng, void *data, unsigned int elem_size_i, unsig
   free(temp);
 }
 
+void BLI_rng_shuffle_bitmap(struct RNG *rng, BLI_bitmap *bitmap, unsigned int bits_tot)
+{
+  if (bits_tot <= 1) {
+    return;
+  }
+
+  unsigned int i = bits_tot;
+  while (i--) {
+    const unsigned int j = BLI_rng_get_uint(rng) % bits_tot;
+    if (i != j) {
+      const bool i_bit = BLI_BITMAP_TEST(bitmap, i);
+      const bool j_bit = BLI_BITMAP_TEST(bitmap, j);
+      BLI_BITMAP_SET(bitmap, i, j_bit);
+      BLI_BITMAP_SET(bitmap, j, i_bit);
+    }
+  }
+}
+
 /**
  * Simulate getting \a n random values.
  *
@@ -216,6 +233,14 @@ void BLI_array_randomize(void *data,
   BLI_rng_shuffle_array(&rng, data, elem_size, elem_tot);
 }
 
+void BLI_bitmap_randomize(BLI_bitmap *bitmap, unsigned int bits_tot, unsigned int seed)
+{
+  RNG rng;
+
+  BLI_rng_seed(&rng, seed);
+  BLI_rng_shuffle_bitmap(&rng, bitmap, bits_tot);
+}
+
 /* ********* for threaded random ************** */
 
 static RNG rng_tab[BLENDER_MAX_THREADS];
diff --git a/source/blender/blenlib/intern/stack.c b/source/blender/blenlib/intern/stack.c
index f2e8b352aab..4a9bdd48a0a 100644
--- a/source/blender/blenlib/intern/stack.c
+++ b/source/blender/blenlib/intern/stack.c
@@ -182,7 +182,7 @@ void BLI_stack_pop(BLI_Stack *stack, void *dst)
 }
 
 /**
- * A version of #BLI_stack_pop which which fills in an array.
+ * A version of #BLI_stack_pop which fills in an array.
  *
  * \param dst: The destination array,
  * must be at least (#BLI_Stack.elem_size * \a n) bytes long.
@@ -201,7 +201,7 @@ void BLI_stack_pop_n(BLI_Stack *stack, void *dst, unsigned int n)
 }
 
 /**
- * A version of #BLI_stack_pop_n which which fills in an array (in the reverse order).
+ * A version of #BLI_stack_pop_n which fills in an array (in the reverse order).
  *
  * \note The first item in the array will be first item added to the stack.
  */
diff --git a/source/blender/blenlib/intern/string.c b/source/blender/blenlib/intern/string.c
index b2b8d6a0f24..61d095658a3 100644
--- a/source/blender/blenlib/intern/string.c
+++ b/source/blender/blenlib/intern/string.c
@@ -370,7 +370,7 @@ size_t BLI_str_escape(char *__restrict dst, const char *__restrict src, const si
  * \param src: The escaped source string.
  * \param dst_maxncpy: The maximum number of bytes allowable to copy.
  *
- * \note This is used for for parsing animation paths in blend files.
+ * \note This is used for parsing animation paths in blend files.
  */
 size_t BLI_str_unescape(char *__restrict dst, const char *__restrict src, const size_t src_maxncpy)
 {
diff --git a/source/blender/blenlib/tests/BLI_listbase_test.cc b/source/blender/blenlib/tests/BLI_listbase_test.cc
index ff85cf79e87..0ba08a0cd48 100644
--- a/source/blender/blenlib/tests/BLI_listbase_test.cc
+++ b/source/blender/blenlib/tests/BLI_listbase_test.cc
@@ -192,7 +192,7 @@ TEST(listbase, Sort)
     EXPECT_TRUE(listbase_is_valid(&words_lb));
   }
 
-  /* sort single single */
+  /* Sort single list. */
   {
     LinkData link;
     link.data = words;
diff --git a/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc b/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
index ec57cf29cad..1a9ffbd3403 100644
--- a/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
+++ b/source/blender/blenlib/tests/BLI_mesh_intersect_test.cc
@@ -174,6 +174,76 @@ TEST(mesh_intersect, Mesh)
   EXPECT_TRUE(f->is_tri());
 }
 
+TEST(mesh_intersect, TriangulateTri)
+{
+  const char *spec = R"(3 1
+  0 0 0
+  1 0 0
+  1/2 1 0
+  0 1 2
+  )";
+
+  IMeshBuilder mb(spec);
+  IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
+  EXPECT_EQ(im_tri.faces().size(), 1);
+}
+
+TEST(mesh_intersect, TriangulateQuad)
+{
+  const char *spec = R"(4 1
+  0 0 0
+  1 0 0
+  1 1 0
+  0 1 0
+  0 1 2 3
+  )";
+
+  IMeshBuilder mb(spec);
+  IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
+  EXPECT_EQ(im_tri.faces().size(), 2);
+}
+
+TEST(mesh_intersect, TriangulatePentagon)
+{
+  const char *spec = R"(5 1
+  0 0 0
+  1 0 0
+  1 1 0
+  1/2 2 0
+  0 1 0
+  0 1 2 3 4
+  )";
+
+  IMeshBuilder mb(spec);
+  IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
+  EXPECT_EQ(im_tri.faces().size(), 3);
+  if (DO_OBJ) {
+    write_obj_mesh(im_tri, "pentagon");
+  }
+}
+
+TEST(mesh_intersect, TriangulateTwoFaces)
+{
+  const char *spec = R"(7 2
+  461/250 -343/125 103/1000
+  -3/40 -453/200 -97/500
+  237/100 -321/200 -727/500
+  451/1000 -563/500 -1751/1000
+  12/125 -2297/1000 -181/1000
+  12/125 -411/200 -493/1000
+  1959/1000 -2297/1000 -493/1000
+  1 3 2 0 6 5 4
+  6 0 1 4
+  )";
+
+  IMeshBuilder mb(spec);
+  IMesh im_tri = triangulate_polymesh(mb.imesh, &mb.arena);
+  EXPECT_EQ(im_tri.faces().size(), 7);
+  if (DO_OBJ) {
+    write_obj_mesh(im_tri, "twofaces");
+  }
+}
+
 TEST(mesh_intersect, OneTri)
 {
   const char *spec = R"(3 1
diff --git a/source/blender/blenlib/tests/BLI_string_utf8_test.cc b/source/blender/blenlib/tests/BLI_string_utf8_test.cc
index 2796cbbfbda..9ddc372e6d1 100644
--- a/source/blender/blenlib/tests/BLI_string_utf8_test.cc
+++ b/source/blender/blenlib/tests/BLI_string_utf8_test.cc
@@ -92,12 +92,12 @@ static const char *utf8_invalid_tests[][3] = {
                   "\x90\x91\x92\x93\x94\x95\x96\x97\x98\x99\x9a\x9b\x9c\x9d\x9e\x9f"
                   "\xa0\xa1\xa2\xa3\xa4\xa5\xa6\xa7\xa8\xa9\xaa\xab\xac\xad\xae\xaf"
                   "\xb0\xb1\xb2\xb3\xb4\xb5\xb6\xb7\xb8\xb9\xba\xbb\xbc\xbd\xbe\xbf\" |",
-     "3.1.9      \"\" |", "\x40"},
+     "3.1.9      \"\" |", "\x40"}, /* NOLINT: modernize-raw-string-literal. */
 /*    3.2  Lonely start characters
  *    3.2.1  All 32 first bytes of 2-byte sequences (0xc0-0xdf), each followed by a space character: */
     {"3.2.1      \"\xc0 \xc1 \xc2 \xc3 \xc4 \xc5 \xc6 \xc7 \xc8 \xc9 \xca \xcb \xcc \xcd \xce \xcf "
                   "\xd0 \xd1 \xd2 \xd3 \xd4 \xd5 \xd6 \xd7 \xd8 \xd9 \xda \xdb \xdc \xdd \xde \xdf \" |",
-     "3.2.1      \"                                \" |", "\x20"},
+     "3.2.1      \"                                \" |", "\x20"}, /* NOLINT: modernize-raw-string-literal. */
 /*    3.2.2  All 16 first bytes of 3-byte sequences (0xe0-0xef), each followed by a space character: */
     {"3.2.2      \"\xe0 \xe1 \xe2 \xe3 \xe4 \xe5 \xe6 \xe7 \xe8 \xe9 \xea \xeb \xec \xed \xee \xef \"                                 |",
      "3.2.2      \"                \"                                 |", "\x10"},