[Bf-blender-cvs] [2b5fe4ce171] temp-T97352-3d-texturing-seam-bleeding-b: UV Island determination.
Jeroen Bakker
noreply at git.blender.org
Tue May 17 15:42:45 CEST 2022
Commit: 2b5fe4ce17116d2ff66c1b6a5c824dd376517647
Author: Jeroen Bakker
Date: Tue May 17 15:42:42 2022 +0200
Branches: temp-T97352-3d-texturing-seam-bleeding-b
https://developer.blender.org/rB2b5fe4ce17116d2ff66c1b6a5c824dd376517647
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.
===================================================================
M source/blender/blenkernel/intern/pbvh_pixels.cc
===================================================================
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 targ
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list