From 63d0916dfd29433efc15093a7db0e837e2dd7215 Mon Sep 17 00:00:00 2001 From: Jeroen Bakker Date: Fri, 20 May 2022 12:23:54 +0200 Subject: New method. building via faces. --- source/blender/blenkernel/BKE_uv_islands.hh | 551 ++++++++++-------------- source/blender/blenkernel/intern/pbvh_pixels.cc | 7 +- 2 files changed, 238 insertions(+), 320 deletions(-) (limited to 'source/blender/blenkernel') 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 + #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 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("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> 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 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(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 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> 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 &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 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 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 << "\n"; +} +void svg_footer(std::ostream &ss) +{ + ss << "\n"; +} +void svg(std::ostream &ss, const UVEdge &edge) +{ + ss << " \n"; +} + +void svg(std::ostream &ss, const UVIslands &islands, int step) +{ + ss << "\n"; + int island_index = 0; + for (const UVIsland &island : islands.islands) { + ss << " \n"; + + /* Inner edges */ + ss << " \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 << " \n"; + + /* Border */ + ss << " \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 << " \n"; + + ss << " \n"; + island_index++; + } + + ss << "\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 << " \n"; +} + +void svg(std::ostream &ss, const UVPrimitive &primitive, int step) +{ + ss << "\n"; + ss << " \n"; + svg(ss, primitive); + ss << " "; + ss << "\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; } -- cgit v1.2.3