From 2b5fe4ce17116d2ff66c1b6a5c824dd376517647 Mon Sep 17 00:00:00 2001 From: Jeroen Bakker Date: Tue, 17 May 2022 15:42:42 +0200 Subject: 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. --- source/blender/blenkernel/intern/pbvh_pixels.cc | 319 +++++++++++++++++++++++- 1 file changed, 318 insertions(+), 1 deletion(-) (limited to 'source/blender/blenkernel') 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 borders; + Vector 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 islands; + + public: + void add(const uint64_t prim_index, const MLoopTri &tri, const MLoopUV *mloopuv) + { + Vector 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; -- cgit v1.2.3