New method. building via faces.

2 files changed, 238 insertions, 320 deletions

diff --git a/source/blender/blenkernel/BKE_uv_islands.hh b/source/blender/blenkernel/BKE_uv_islands.hh
index 6af47d029c7..0b7cad8160f 100644
--- a/source/blender/blenkernel/BKE_uv_islands.hh
+++ b/source/blender/blenkernel/BKE_uv_islands.hh
@@ -3,6 +3,8 @@
 
 #pragma once
 
+#include <fstream>
+
 #include "BLI_math_vec_types.hh"
 #include "BLI_vector.hh"
 
@@ -13,368 +15,186 @@ namespace blender::bke::uv_islands {
 // TODO: Joining uv island should check where the borders could be merged.
 // TODO: this isn't optimized for performance.
 
-struct UVIslandEdge {
-  float2 uv1;
-  float2 uv2;
-
-  UVIslandEdge() : uv1(float2(0.0f, 0.0f)), uv2(float2(0.0f, 0.0f))
-  {
-  }
-
-  UVIslandEdge(const float2 &uv1, const float2 &uv2) : uv1(uv1), uv2(uv2)
-  {
-  }
+struct UVVertex {
+  /* Loop index of the vertex in the original mesh. */
+  uint64_t loop;
+  /* Position in uv space. */
+  float2 uv;
+};
 
-  bool operator==(const UVIslandEdge &other) const
-  {
-    return (uv1 == other.uv1 && uv2 == other.uv2) || (uv1 == other.uv2 && uv2 == other.uv1);
-  }
+struct UVEdge {
+  UVVertex vertices[2];
+  int64_t adjacent_uv_primitive = -1;
 
-  void print() const
+  bool has_shared_edge(const UVEdge &other) const
   {
-    printf("UVIslandEdge(float2(%f, %f), float2(%f, %f))\n", uv1.x, uv1.y, uv2.x, uv2.y);
+    return (vertices[0].uv == other.vertices[0].uv && vertices[1].uv == other.vertices[1].uv) ||
+           (vertices[0].uv == other.vertices[1].uv && vertices[1].uv == other.vertices[0].uv);
   }
 };
 
-struct Primitive {
+struct UVPrimitive {
+  /**
+   * Index of the primitive in the original mesh.
+   */
   uint64_t index;
-  UVIslandEdge edge[3];
-
-  Primitive()
-  {
-  }
+  UVEdge edges[3];
 
-  Primitive(uint64_t index,
-            const UVIslandEdge &edge1,
-            const UVIslandEdge &edge2,
-            const UVIslandEdge &edge3)
-      : index(index), edge({edge1, edge2, edge3})
+  explicit UVPrimitive(uint64_t prim_index, const MLoopTri &tri, const MLoopUV *mloopuv)
+      : index(prim_index)
   {
-  }
-
-  Primitive(uint64_t index, const MLoopTri &tri, const MLoopUV *mloopuv) : index(index)
-  {
-    const float2 uv1(mloopuv[tri.tri[0]].uv);
-    const float2 uv2(mloopuv[tri.tri[1]].uv);
-    const float2 uv3(mloopuv[tri.tri[2]].uv);
-    edge[0] = UVIslandEdge(uv1, uv2);
-    edge[1] = UVIslandEdge(uv2, uv3);
-    edge[2] = UVIslandEdge(uv3, uv1);
-  }
-
-  void print() const
-  {
-    printf(">>>> Primitive(start)\n");
     for (int i = 0; i < 3; i++) {
-      edge[i].print();
+      edges[i].vertices[0].uv = mloopuv[tri.tri[i]].uv;
+      edges[i].vertices[1].uv = mloopuv[tri.tri[(i + 1) % 3]].uv;
+      edges[i].vertices[0].loop = tri.tri[i];
+      edges[i].vertices[1].loop = tri.tri[(i + 1) % 3];
     }
-    printf("<<<< Primitive(end)\n");
   }
-};
-
-/* Mapping between generated primitives and original primitives. */
-struct UVIslandPrimitive {
-  uint64_t orig_prim;
 
-  UVIslandPrimitive(uint64_t orig_prim) : orig_prim(orig_prim)
-  {
-  }
-};
-
-class UVIsland {
-  // We might want to use a linked list as there are more edits then reads.
-  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("island.add(");
-      border.print();
-      printf("); // %d\n", i);
-    }
-    printf("<<<< UVIsland(end)\n");
-  }
-  /* Join a given UVIsland into self by using the given tri as the edges that needs to be merged.
-   */
-  void join(const UVIsland &other, const Primitive &primitive)
+  std::optional<std::pair<UVEdge &, UVEdge &>> shared_edge(UVPrimitive &other)
   {
-    printf("Before joining");
-    print();
-    other.print();
-    primitive.print();
-
-    int64_t a_edge_index[3];
-    int64_t b_edge_index[3];
-    for (int i = 0; i < 3; i++) {
-      a_edge_index[i] = borders.first_index_of_try(primitive.edge[i]);
-      b_edge_index[i] = other.borders.first_index_of_try(primitive.edge[i]);
-    }
-
-    // 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) {
-      printf("1-1 join\n");
-      BLI_assert_unreachable();
-    }
-    if (a_border_len == 1 && b_border_len == 2) {
-      printf("1-2 join\n");
-      BLI_assert_unreachable();
-    }
-    if (a_border_len == 2 && b_border_len == 1) {
-      printf("2-1 join\n");
-      BLI_assert_unreachable();
-    }
-    if (a_border_len == 2 && b_border_len == 2) {
-      printf("2-2 join\n");
-      int common_edge_len = 0;
-      for (int i = 0; i < 3; i++) {
-        if (a_edge_index[i] != -1 && b_edge_index[i] != -1) {
-          common_edge_len++;
-        }
-      }
-
-      Vector<uint64_t> edges_to_remove_from_dst;
-      uint64_t insert;
-      uint64_t start;
-      uint64_t end;
-
-      switch (common_edge_len) {
-        case 0:
-          BLI_assert_unreachable();
-          break;
-
-        case 1: {
-          /* 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.
-          end = b_edge_index[common_edge];
-          start = b_edge_index[other_b_edge];
-
-          int other_a_edge = a_edge_index[next_edge] != -1 ? next_edge : prev_edge;
-          insert = a_edge_index[common_edge];
-          if (other_a_edge == common_edge - 1) {
-            edges_to_remove_from_dst.append(insert);
-            insert--;
-          }
-          break;
-        }
-
-        case 2: {
-          // find edge that isn't common.
-          int unshared_edge = -1;
-          for (int i = 0; i < 3; i++) {
-            if (a_edge_index[i] == -1 || b_edge_index[i] == -1) {
-              unshared_edge = i;
-            }
-          }
-          int next_edge = (unshared_edge + 1) % 3;
-          int prev_edge = 3 - unshared_edge - next_edge;
-          edges_to_remove_from_dst.append(a_edge_index[next_edge]);
-          edges_to_remove_from_dst.append(a_edge_index[prev_edge]);
-          insert = prev_edge;
-
-          break;
-        }
-      }
-
-      // TODO: It could be that different edge should be removed and copies start at other
-      // locations depending on next_edge/prev_edge selection.
-      // TODO: sort_reversed?
-      for (uint64_t index_to_remove : edges_to_remove_from_dst) {
-        borders.remove(index_to_remove);
-        printf("removed %d: ", index_to_remove);
-        print();
-      }
-
-      printf("i:%d s:%d e:%d\n", insert, start, end);
-
-      if (end < start) {
-        // TODO: these loops can be done with a single call and an iterator. For debugging and need
-        // to look how to use the iterators this hasn't been done.
-        for (int i = end - 1; i >= 0; i--) {
-          borders.insert(insert, other.borders[i]);
-          printf("insert: %d->%d", i, insert);
-          print();
-          BLI_assert(borders[insert].uv2 == borders[insert + 1].uv1);
-        }
-        for (int i = other.borders.size() - 1; i > start; i--) {
-          borders.insert(insert, other.borders[i]);
-          printf("insert: %d->%d", i, insert);
-          print();
-          BLI_assert(borders[insert].uv2 == borders[insert + 1].uv1);
-        }
-      }
-      else {
-        for (int i = end; i >= start; i--) {
-          borders.insert(insert, other.borders[i]);
-          printf("insert: %d->%d", i, insert);
-          print();
-          BLI_assert(borders[insert].uv2 == borders[insert + 1].uv1);
+      for (int j = 0; j < 3; j++) {
+        if (edges[i].has_shared_edge(other.edges[j])) {
+          return std::pair<UVEdge &, UVEdge &>(edges[i], other.edges[j]);
         }
       }
     }
-
-    printf("After joining");
-    print();
-
-    BLI_assert(validate());
+    return std::nullopt;
   }
 
-  void add(const UVIslandEdge &border)
+  bool has_shared_edge(const UVPrimitive &other) const
   {
-    borders.append(border);
+    for (int i = 0; i < 3; i++) {
+      for (int j = 0; j < 3; j++) {
+        if (edges[i].has_shared_edge(other.edges[j])) {
+          return true;
+        }
+      }
+    }
+    return false;
   }
+};
 
-  void extend_border(const int64_t edge_to_remove,
-                     const UVIslandEdge &border1,
-                     const 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());
-  }
+struct UVIsland {
+  Vector<UVPrimitive> primitives;
 
-  void extend_border(const int64_t edge1_to_remove,
-                     const int64_t edge2_to_remove,
-                     const UVIslandEdge &border)
+  UVIsland(const UVPrimitive &primitive)
   {
-    borders[edge1_to_remove] = border;
-    borders.remove(edge2_to_remove);
-    BLI_assert(validate());
+    primitives.append(primitive);
   }
 
-  /** 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 Primitive &primitive)
+  bool has_shared_edge(const UVPrimitive &primitive) const
   {
-    const int64_t edge1_index = borders.first_index_of_try(primitive.edge[0]);
-    const int64_t edge2_index = borders.first_index_of_try(primitive.edge[1]);
-    const int64_t edge3_index = borders.first_index_of_try(primitive.edge[2]);
-    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, primitive.edge[0], primitive.edge[1]);
-      return true;
-    }
-    if (has_edge1 == false && has_edge2 == true && has_edge3 == false) {
-      extend_border(edge2_index, primitive.edge[2], primitive.edge[0]);
-      return true;
-    }
-    if (has_edge1 == false && has_edge2 == true && has_edge3 == true) {
-      extend_border(edge2_index, edge3_index, primitive.edge[0]);
-      return true;
-    }
-    if (has_edge1 == true && has_edge2 == false && has_edge3 == false) {
-      extend_border(edge1_index, primitive.edge[1], primitive.edge[2]);
-      return true;
-    }
-    if (has_edge1 == true && has_edge2 == false && has_edge3 == true) {
-      extend_border(edge3_index, edge1_index, primitive.edge[1]);
-      return true;
-    }
-    if (has_edge1 == true && has_edge2 == true && has_edge3 == false) {
-      extend_border(edge1_index, edge2_index, primitive.edge[2]);
-      return true;
-    }
-    if (has_edge1 == true && has_edge2 == true && has_edge3 == true) {
-      /* Nothing to do as it overlaps completely. */
-      return true;
+    for (const UVPrimitive &prim : primitives) {
+      if (prim.has_shared_edge(primitive)) {
+        return true;
+      }
     }
     return false;
   }
 
-  void add_prim(const uint64_t prim_index)
-  {
-    primitives.append(UVIslandPrimitive(prim_index));
-  }
-
-  void add(const Primitive &primitive)
+  const void extend_border(const UVPrimitive &primitive)
   {
-    for (int i = 0; i < 3; i++) {
-      borders.append(primitive.edge[i]);
+    UVPrimitive new_prim = primitive;
+    uint64_t shared_edges_len = 0;
+    for (UVPrimitive &prim : primitives) {
+      std::optional<std::pair<UVEdge &, UVEdge &>> shared_edge = prim.shared_edge(new_prim);
+      if (!shared_edge.has_value()) {
+        continue;
+      }
+      // TODO: eventually this should be supported. Skipped for now as it isn't the most important
+      // this to add. */
+      std::pair<UVEdge &, UVEdge &> &edges = *shared_edge;
+      BLI_assert(edges.first.adjacent_uv_primitive == -1);
+      BLI_assert(edges.second.adjacent_uv_primitive == -1);
+      edges.first.adjacent_uv_primitive = new_prim.index;
+      edges.second.adjacent_uv_primitive = prim.index;
+      shared_edges_len++;
     }
-    BLI_assert(validate());
+    BLI_assert_msg(shared_edges_len != 0,
+                   "Cannot extend as primitive has no shared edges with UV island.");
+    BLI_assert_msg(shared_edges_len < 3,
+                   "Cannot extend as primitive has to many shared edges with UV island. "
+                   "Inconsistent UVIsland?");
+
+    primitives.append(new_prim);
   }
 
-  const bool validate() const
+  /**
+   * Join 2 uv islands together where the primitive gives the location that joins the two islands
+   * together.
+   *
+   * NOTE: this cannot be used to join two islands that have multiple shared primitives, or
+   * connecting via multiple primitives.
+   * */
+  void join(const UVIsland &other, const UVPrimitive &primitive)
   {
-    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.");
+    for (const UVPrimitive &other_prim : other.primitives) {
+      if (primitive.has_shared_edge(other_prim)) {
+        extend_border(other_prim);
+        continue;
+      }
+      primitives.append(other_prim);
     }
-    BLI_assert_msg(borders.last().uv2 == borders[0].uv1, "Start and end are not connected.");
-
-    return true;
   }
 };
 
-class UVIslands {
+struct UVIslands;
+void svg_header(std::ostream &ss);
+void svg(std::ostream &ss, const UVIslands &islands, int step);
+void svg(std::ostream &ss, const UVPrimitive &primitive, int step);
+void svg_footer(std::ostream &ss);
+
+struct UVIslands {
   Vector<UVIsland> islands;
 
- public:
-  void add(const Primitive &primitive)
+  explicit UVIslands(const MLoopTri *primitives, uint64_t primitives_len, const MLoopUV *mloopuv)
+  {
+    std::ofstream of;
+    of.open("/tmp/islands.svg");
+    svg_header(of);
+    int step = 0;
+    for (int prim = 0; prim < primitives_len; prim++) {
+      UVPrimitive primitive(prim, primitives[prim], mloopuv);
+      if (prim == 12) {
+        printf("BREAK");
+      }
+      if (prim < 14) {
+        svg(of, primitive, step);
+        svg(of, *this, step);
+        of.flush();
+        step++;
+      }
+      BLI_assert(validate());
+      add(primitive);
+      if (!validate()) {
+        svg(of, *this, step);
+        svg_footer(of);
+        of.close();
+        BLI_assert(false);
+        return;
+      }
+    }
+    svg(of, *this, step);
+    svg_footer(of);
+    of.close();
+    // TODO: extract border.
+  }
+
+ private:
+  void add(const UVPrimitive &primitive)
   {
     Vector<uint64_t> extended_islands;
     for (uint64_t index = 0; index < islands.size(); index++) {
       UVIsland &island = islands[index];
-      if (island.extend_border(primitive)) {
+      if (island.has_shared_edge(primitive)) {
         extended_islands.append(index);
       }
     }
 
     if (extended_islands.size() > 0) {
+      islands[extended_islands[0]].extend_border(primitive);
       /* `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++) {
@@ -385,17 +205,120 @@ class UVIslands {
       for (uint64_t index = extended_islands.size() - 1; index > 0; index--) {
         islands.remove_and_reorder(index);
       }
-      islands[extended_islands[0]].add_prim(primitive.index);
 
       return;
     }
 
     /* if the tri has not been added we can create a new island. */
-    UVIsland island;
-    island.add(primitive);
-    island.add_prim(primitive.index);
+    UVIsland island(primitive);
     islands.append(island);
   }
+
+  bool validate() const
+  {
+    /* After operations it is not allowed that islands share any edges. In that case it should
+     * already be merged. */
+    for (int i = 0; i < islands.size() - 1; i++) {
+      for (int j = i + 1; j < islands.size(); j++) {
+        for (const UVPrimitive &prim : islands[j].primitives) {
+          if (islands[i].has_shared_edge(prim)) {
+            return false;
+          }
+        }
+      }
+    }
+    return true;
+  }
 };
 
+void svg_header(std::ostream &ss)
+{
+  ss << "<svg viewBox=\"0 0 1024 1024\" width=\"1024\" height=\"1024\" "
+        "xmlns=\"http://www.w3.org/2000/svg\">\n";
+}
+void svg_footer(std::ostream &ss)
+{
+  ss << "</svg>\n";
+}
+void svg(std::ostream &ss, const UVEdge &edge)
+{
+  ss << "       <line x1=\"" << edge.vertices[0].uv.x * 1024 << "\" y1=\""
+     << edge.vertices[0].uv.y * 1024 << "\" x2=\"" << edge.vertices[1].uv.x * 1024 << "\" y2=\""
+     << edge.vertices[1].uv.y * 1024 << "\"/>\n";
+}
+
+void svg(std::ostream &ss, const UVIslands &islands, int step)
+{
+  ss << "<g transform=\"translate(" << step * 1024 << " 0)\">\n";
+  int island_index = 0;
+  for (const UVIsland &island : islands.islands) {
+    ss << "  <g fill=\"yellow\">\n";
+
+    /* Inner edges */
+    ss << "    <g stroke=\"grey\" stroke-dasharray=\"5 5\">\n";
+    for (const UVPrimitive &primitive : island.primitives) {
+      for (int i = 0; i < 3; i++) {
+        const UVEdge &edge = primitive.edges[i];
+        if (edge.adjacent_uv_primitive == -1) {
+          continue;
+        }
+        svg(ss, edge);
+      }
+    }
+    ss << "     </g>\n";
+
+    /* Border */
+    ss << "    <g stroke=\"black\" stroke-width=\"2\">\n";
+    for (const UVPrimitive &primitive : island.primitives) {
+      for (int i = 0; i < 3; i++) {
+        const UVEdge &edge = primitive.edges[i];
+        if (edge.adjacent_uv_primitive != -1) {
+          continue;
+        }
+        svg(ss, edge);
+      }
+    }
+    ss << "     </g>\n";
+
+    ss << "   </g>\n";
+    island_index++;
+  }
+
+  ss << "</g>\n";
+}
+
+void svg_coords(std::ostream &ss, const float2 &coords)
+{
+  ss << coords.x * 1024 << "," << coords.y * 1024;
+}
+
+void svg(std::ostream &ss, const UVPrimitive &primitive)
+{
+  ss << "       <polygon points=\"";
+  for (int i = 0; i < 3; i++) {
+    svg_coords(ss, primitive.edges[i].vertices[0].uv);
+    ss << " ";
+  }
+  ss << "\"/>\n";
+}
+
+void svg(std::ostream &ss, const UVPrimitive &primitive, int step)
+{
+  ss << "<g transform=\"translate(" << step * 1024 << " 0)\">\n";
+  ss << "  <g fill=\"lightred\">\n";
+  svg(ss, primitive);
+  ss << "  </g>";
+  ss << "</g>\n";
+}
+
+/*std::string as_svg(const UVIslands &islands)
+{
+  std::stringstream ss;
+  svg_header(ss);
+  svg(ss, islands);
+  svg_footer(ss);
+
+  return ss.str();
+}*/
+
 }  // namespace blender::bke::uv_islands
\ No newline at end of file
diff --git a/source/blender/blenkernel/intern/pbvh_pixels.cc b/source/blender/blenkernel/intern/pbvh_pixels.cc
index 6e4f8dff4ae..57667aa4518 100644
--- a/source/blender/blenkernel/intern/pbvh_pixels.cc
+++ b/source/blender/blenkernel/intern/pbvh_pixels.cc
@@ -37,12 +37,7 @@ constexpr bool USE_WATERTIGHT_CHECK = true;
 /** Build UV islands from PBVH primitives. */
 static uv_islands::UVIslands build_uv_islands(const PBVH &pbvh, const MLoopUV *mloopuv)
 {
-  uv_islands::UVIslands islands;
-  for (int prim = 0; prim < pbvh.totprim; prim++) {
-    uv_islands::Primitive primitive(prim, pbvh.looptri[prim], mloopuv);
-    islands.add(primitive);
-  }
-
+  uv_islands::UVIslands islands(pbvh.looptri, pbvh.totprim, mloopuv);
   return islands;
 }