UV Island determination.

A lot of cases aren't working. A plane and a cube should be working.
More complex objects have a high change that it triggers an assert
as it isn't implemented yet.

1 files changed, 318 insertions, 1 deletions

diff --git a/source/blender/blenkernel/intern/pbvh_pixels.cc b/source/blender/blenkernel/intern/pbvh_pixels.cc
index 49397797c0d..ed5294e8b9a 100644
--- a/source/blender/blenkernel/intern/pbvh_pixels.cc
+++ b/source/blender/blenkernel/intern/pbvh_pixels.cc
@@ -26,7 +26,322 @@ namespace blender::bke::pbvh::pixels {
  * During debugging this check could be enabled.
  * It will write to each image pixel that is covered by the PBVH.
  */
-constexpr bool USE_WATERTIGHT_CHECK = false;
+constexpr bool USE_WATERTIGHT_CHECK = true;
+
+/* -------------------------------------------------------------------- */
+
+/** \name UV Islands
+ * \{ */
+
+// TODO: primitives can be added twice
+// TODO: Joining uv island should check where the borders could be merged.
+// TODO: this isn't optimized for performance.
+// TODO: should consider putting the primitive data into a struct as it is reconstructed in
+// multiple places.
+
+struct UVIslandEdge {
+  float2 uv1;
+  float2 uv2;
+
+  UVIslandEdge(const float2 &uv1, const float2 &uv2) : uv1(uv1), uv2(uv2)
+  {
+  }
+
+  bool operator==(const UVIslandEdge &other) const
+  {
+    return (uv1 == other.uv1 && uv2 == other.uv2) || (uv1 == other.uv2 && uv2 == other.uv1);
+  }
+};
+
+/* Mapping between generated primitives and original primitives. */
+struct UVIslandPrimitive {
+  uint64_t orig_prim;
+
+  UVIslandPrimitive(uint64_t orig_prim) : orig_prim(orig_prim)
+  {
+  }
+};
+
+class UVIsland {
+  Vector<UVIslandEdge> borders;
+  Vector<UVIslandPrimitive> primitives;
+
+ public:
+  void print() const
+  {
+    printf(">>>> UVIsland(start)\n");
+    for (int i = 0; i < borders.size(); i++) {
+      const UVIslandEdge &border = borders[i];
+      printf(
+          " . %d: (%f,%f)-(%f,%f)\n", i, border.uv1.x, border.uv1.y, border.uv2.x, border.uv2.y);
+    }
+    printf("<<<< UVIsland(end)\n");
+  }
+
+  void join(UVIsland &other, const MLoopTri &tri, const MLoopUV *mloopuv)
+  {
+    printf("Before joining");
+    print();
+    other.print();
+    const float2 uv1(mloopuv[tri.tri[0]].uv);
+    const float2 uv2(mloopuv[tri.tri[1]].uv);
+    const float2 uv3(mloopuv[tri.tri[2]].uv);
+    UVIslandEdge edge1(uv1, uv2);
+    UVIslandEdge edge2(uv2, uv3);
+    UVIslandEdge edge3(uv3, uv1);
+    const int64_t a_edge_index[3] = {borders.first_index_of_try(edge1),
+                                     borders.first_index_of_try(edge2),
+                                     borders.first_index_of_try(edge3)};
+    const int64_t b_edge_index[3] = {other.borders.first_index_of_try(edge1),
+                                     other.borders.first_index_of_try(edge2),
+                                     other.borders.first_index_of_try(edge3)};
+
+    // CHeck the number of edges. Based on this a different way should be used for joining.
+    // these are the cases:
+    // * self contains a single edge, other contains a single edge.
+    // * self contains a single edge, other contains a double edge.
+    // * self contains a double edge, other contains a single edge.
+    // * self contains a double edge, other contains a double edge.
+    int a_border_len = 0;
+    int b_border_len = 0;
+    for (int i = 0; i < 3; i++) {
+      if (a_edge_index[i] != -1) {
+        a_border_len += 1;
+      }
+      if (b_edge_index[i] != -1) {
+        b_border_len += 1;
+      }
+    }
+    BLI_assert_msg(a_border_len == 1 || a_border_len == 2, "Incorrect number of borders.");
+    BLI_assert_msg(b_border_len == 1 || b_border_len == 2, "Incorrect number of borders.");
+
+    if (a_border_len == 1 && b_border_len == 1) {
+      BLI_assert_unreachable();
+    }
+    if (a_border_len == 1 && b_border_len == 2) {
+      BLI_assert_unreachable();
+    }
+    if (a_border_len == 2 && b_border_len == 1) {
+      BLI_assert_unreachable();
+    }
+    if (a_border_len == 2 && b_border_len == 2) {
+      printf("2-2 join\n");
+      /* Determine the common edge. */
+      int common_edge = -1;
+      for (int i = 0; i < 3; i++) {
+        if (a_edge_index[i] != -1 && b_edge_index[i] != -1) {
+          BLI_assert(common_edge == -1);
+          common_edge = i;
+        }
+      }
+
+      int next_edge = (common_edge + 1) % 3;
+      int prev_edge = 3 - common_edge - next_edge;
+      BLI_assert(common_edge != -1);
+      int other_b_edge = b_edge_index[next_edge] != -1 ? next_edge : prev_edge;
+
+      // In this case there should be a single common edge. This edge will still be an edge
+      // in the merged island. find the index where to insert the other. find the start and
+      // end to the other to insert.
+      uint64_t end = b_edge_index[common_edge];
+      uint64_t start = b_edge_index[other_b_edge];
+
+      int other_a_edge = a_edge_index[next_edge] != -1 ? next_edge : prev_edge;
+      uint64_t insert = a_edge_index[common_edge];
+      if (other_a_edge == common_edge - 1) {
+        borders.remove(insert - 1);
+        insert -= 1;
+        printf("removed %d: ", insert);
+        print();
+      }
+      if (end < start) {
+        for (int i = end - 1; i >= 0; i--) {
+          borders.insert(insert, other.borders[i]);
+          printf("insert: %d->%d", i, insert);
+          print();
+        }
+        for (int i = other.borders.size() - 1; i > start; i--) {
+          borders.insert(insert, other.borders[i]);
+          printf("insert: %d->%d", i, insert);
+          print();
+        }
+      }
+      else {
+        for (int i = end; i >= start; i--) {
+          borders.insert(insert, other.borders[i]);
+          printf("insert: %d->%d", i, insert);
+          print();
+        }
+      }
+    }
+
+    printf("After joining");
+    print();
+
+    BLI_assert(validate());
+  }
+
+  void extend_border(const int64_t edge_to_remove, UVIslandEdge &border1, UVIslandEdge &border2)
+  {
+    BLI_assert_msg(border1.uv2 == border2.uv1,
+                   "Winding order of replacement borders is not correct.");
+    borders[edge_to_remove] = border2;
+    borders.insert(edge_to_remove, border1);
+    BLI_assert(validate());
+  }
+
+  void extend_border(const int64_t edge1_to_remove,
+                     const int64_t edge2_to_remove,
+                     UVIslandEdge &border)
+  {
+    borders[edge1_to_remove] = border;
+    borders.remove(edge2_to_remove);
+    BLI_assert(validate());
+  }
+
+  /** Try to extend the border of the uv island by adding the given tri. Returns false when the
+   * border couldn't be extended. This happens when there is no common edge in uv space. */
+  bool extend_border(const MLoopTri &tri, const MLoopUV *mloopuv)
+  {
+    const float2 uv1(mloopuv[tri.tri[0]].uv);
+    const float2 uv2(mloopuv[tri.tri[1]].uv);
+    const float2 uv3(mloopuv[tri.tri[2]].uv);
+    UVIslandEdge edge1(uv1, uv2);
+    UVIslandEdge edge2(uv2, uv3);
+    UVIslandEdge edge3(uv3, uv1);
+    const int64_t edge1_index = borders.first_index_of_try(edge1);
+    const int64_t edge2_index = borders.first_index_of_try(edge2);
+    const int64_t edge3_index = borders.first_index_of_try(edge3);
+    const bool has_edge1 = edge1_index != -1;
+    const bool has_edge2 = edge2_index != -1;
+    const bool has_edge3 = edge3_index != -1;
+
+    if (has_edge1 == false && has_edge2 == false && has_edge3 == false) {
+      /* Cannot extend as there is no common edge with a border. */
+      return false;
+    }
+    if (has_edge1 == false && has_edge2 == false && has_edge3 == true) {
+      extend_border(edge3_index, edge1, edge2);
+      return true;
+    }
+    if (has_edge1 == false && has_edge2 == true && has_edge3 == false) {
+      extend_border(edge2_index, edge3, edge1);
+      return true;
+    }
+    if (has_edge1 == false && has_edge2 == true && has_edge3 == true) {
+      extend_border(edge2_index, edge3_index, edge1);
+      return true;
+    }
+    if (has_edge1 == true && has_edge2 == false && has_edge3 == false) {
+      extend_border(edge1_index, edge2, edge3);
+      return true;
+    }
+    if (has_edge1 == true && has_edge2 == false && has_edge3 == true) {
+      extend_border(edge3_index, edge1_index, edge2);
+      return true;
+    }
+    if (has_edge1 == true && has_edge2 == true && has_edge3 == false) {
+      extend_border(edge1_index, edge2_index, edge3);
+      return true;
+    }
+    if (has_edge1 == true && has_edge2 == true && has_edge3 == true) {
+      /* Nothing to do as it overlaps completely. */
+      return true;
+    }
+    return false;
+  }
+
+  void add_prim(const uint64_t prim_index)
+  {
+    primitives.append(UVIslandPrimitive(prim_index));
+  }
+
+  void add(const MLoopTri &tri, const MLoopUV *mloopuv)
+  {
+    const float2 uv1(mloopuv[tri.tri[0]].uv);
+    const float2 uv2(mloopuv[tri.tri[1]].uv);
+    const float2 uv3(mloopuv[tri.tri[2]].uv);
+    UVIslandEdge edge1(uv1, uv2);
+    UVIslandEdge edge2(uv2, uv3);
+    UVIslandEdge edge3(uv3, uv1);
+    borders.append(edge1);
+    borders.append(edge2);
+    borders.append(edge3);
+    BLI_assert(validate());
+  }
+
+  const bool validate() const
+  {
+    if (borders.size() == 0) {
+      return true;
+    }
+    if (borders.size() == 1 || borders.size() == 2) {
+      BLI_assert_msg(false, "Island with 1 or 2 border edges aren't allowed.");
+      return false;
+    }
+
+    for (int index = 1; index < borders.size(); index++) {
+      const UVIslandEdge &prev = borders[index - 1];
+      const UVIslandEdge &curr = borders[index];
+      BLI_assert_msg(prev.uv2 == curr.uv1, "Edges do not form a single border.");
+    }
+    BLI_assert_msg(borders.last().uv2 == borders[0].uv1, "Start and end are not connected.");
+
+    return true;
+  }
+};
+
+class UVIslands {
+  Vector<UVIsland> islands;
+
+ public:
+  void add(const uint64_t prim_index, const MLoopTri &tri, const MLoopUV *mloopuv)
+  {
+    Vector<uint64_t> extended_islands;
+    for (uint64_t index = 0; index < islands.size(); index++) {
+      UVIsland &island = islands[index];
+      if (island.extend_border(tri, mloopuv)) {
+        extended_islands.append(index);
+      }
+    }
+
+    if (extended_islands.size() > 0) {
+      /* `extended_islands` can hold upto 3 islands that are connected with the given tri.
+       * they can be joined to a single island, using the first as its target. */
+      for (uint64_t index = 1; index < extended_islands.size(); index++) {
+        islands[extended_islands[0]].join(islands[extended_islands[index]], tri, mloopuv);
+      }
+
+      /* remove the islands that have been joined, starting at the end. */
+      for (uint64_t index = extended_islands.size() - 1; index > 0; index--) {
+        islands.remove_and_reorder(index);
+      }
+      islands[extended_islands[0]].add_prim(prim_index);
+
+      return;
+    }
+
+    /* if the tri has not been added we can create a new island. */
+    UVIsland island;
+    island.add(tri, mloopuv);
+    island.add_prim(prim_index);
+    islands.append(island);
+  }
+};
+
+/** Build UV islands from PBVH primitives. */
+UVIslands build_uv_islands(const PBVH &pbvh, const MLoopUV *mloopuv)
+{
+  UVIslands islands;
+  for (int prim = 0; prim < pbvh.totprim; prim++) {
+    const MLoopTri &tri = pbvh.looptri[prim];
+    islands.add(prim, tri, mloopuv);
+  }
+
+  return islands;
+}
+
+/** \} */
 
 /**
  * Calculate the delta of two neighbor UV coordinates in the given image buffer.
@@ -294,6 +609,8 @@ static void update_pixels(PBVH *pbvh, Mesh *mesh, Image *image, ImageUser *image
     init_triangles(pbvh, node, node_data, mesh->mloop);
   }
 
+  UVIslands islands = build_uv_islands(*pbvh, ldata_uv);
+
   EncodePixelsUserData user_data;
   user_data.pbvh = pbvh;
   user_data.image = image;