[Bf-blender-cvs] [21eff2c0ac2] master: 3DTexturing: Improve fix seam bleeding for manifold parts of mesh.
Jeroen Bakker
noreply at git.blender.org
Tue Jan 24 15:13:27 CET 2023
Commit: 21eff2c0ac214215c9c404cea6a8ffbfb2608c59
Author: Jeroen Bakker
Date: Tue Jan 24 15:03:21 2023 +0100
Branches: master
https://developer.blender.org/rB21eff2c0ac214215c9c404cea6a8ffbfb2608c59
3DTexturing: Improve fix seam bleeding for manifold parts of mesh.
Current implementation had some faulty assumtions and had some work
arounds for crashes that were actually limitation of the implementation.
The main reason for this was that the implementation didn't add new
primitives in the same direction it was already adding. Some when
incorrect behavior was detected it was assumed that the part wasn't
manifold (anymore) and didn't fix that part of the mesh.
The new implementation will extract a solution and use this solution
also as the order to generate primitives in uv space.
This patch fixes several crashes and improves the overall quality
when fixing seam bleeding. It also adds additional debug tools
(print_debug) implementation in order to find issues faster in the
future.
===================================================================
M source/blender/blenkernel/intern/pbvh_uv_islands.cc
M source/blender/blenkernel/intern/pbvh_uv_islands.hh
===================================================================
diff --git a/source/blender/blenkernel/intern/pbvh_uv_islands.cc b/source/blender/blenkernel/intern/pbvh_uv_islands.cc
index 16091b32917..b94b50c5210 100644
--- a/source/blender/blenkernel/intern/pbvh_uv_islands.cc
+++ b/source/blender/blenkernel/intern/pbvh_uv_islands.cc
@@ -80,17 +80,6 @@ static int get_uv_loop(const MeshData &mesh_data, const MLoopTri &looptri, const
return looptri.tri[0];
}
-static bool has_vertex(const MeshData &mesh_data, const MLoopTri &looptri, const int vert)
-{
- for (int i = 0; i < 3; i++) {
- const int vert_i = mesh_data.loops[looptri.tri[i]].v;
- if (vert_i == vert) {
- return true;
- }
- }
- return false;
-}
-
static rctf primitive_uv_bounds(const MLoopTri &looptri, const Span<float2> uv_map)
{
rctf result;
@@ -247,6 +236,21 @@ UVVertex::UVVertex(const MeshData &mesh_data, const int loop)
uv_vertex_init_flags(*this);
}
+/**
+ * Get a list containing the indices of mesh primitives (primitive of the input mesh), that
+ * surround the given uv_vertex in uv-space.
+ */
+static Vector<int> connecting_mesh_primitive_indices(const UVVertex &uv_vertex)
+{
+ Vector<int> primitives_around_uv_vertex;
+ for (const UVEdge *uv_edge : uv_vertex.uv_edges) {
+ for (const UVPrimitive *uv_primitive : uv_edge->uv_primitives) {
+ primitives_around_uv_vertex.append_non_duplicates(uv_primitive->primitive_i);
+ }
+ }
+ return primitives_around_uv_vertex;
+}
+
/** \} */
/* -------------------------------------------------------------------- */
@@ -496,7 +500,9 @@ static std::optional<UVBorderCorner> sharpest_border_corner(UVIsland &island)
}
/** The inner edge of a fan. */
+/* TODO: InnerEdge name is incorrect as it links to an edge and primitive. */
struct InnerEdge {
+ const int primitive_index;
const MLoopTri *primitive;
/* UVs order are already applied. So `uvs[0]` matches `primitive->vertices[vert_order[0]]`. */
float2 uvs[3];
@@ -506,8 +512,11 @@ struct InnerEdge {
bool found : 1;
} flags;
- InnerEdge(const MeshData &mesh_data, const MLoopTri *primitive, int vertex)
- : primitive(primitive)
+ InnerEdge(const MeshData &mesh_data,
+ const int primitive_index,
+ const MLoopTri *primitive,
+ int vertex)
+ : primitive_index(primitive_index), primitive(primitive)
{
flags.found = false;
@@ -529,6 +538,23 @@ struct InnerEdge {
vert_order[2] = 2;
}
}
+
+ void print_debug(const MeshData &mesh_data) const
+ {
+ std::stringstream ss;
+ ss << "# p:" << primitive->poly;
+ ss << " v1:" << mesh_data.loops[primitive->tri[vert_order[0]]].v;
+ ss << " v2:" << mesh_data.loops[primitive->tri[vert_order[1]]].v;
+ ss << " v3:" << mesh_data.loops[primitive->tri[vert_order[2]]].v;
+ ss << " uv1:" << uvs[0];
+ ss << " uv2:" << uvs[1];
+ ss << " uv3:" << uvs[2];
+ if (flags.found) {
+ ss << " *found";
+ }
+ ss << "\n";
+ std::cout << ss.str();
+ }
};
struct Fan {
@@ -567,7 +593,7 @@ struct Fan {
if (edge_i == current_edge || (edge.vert1 != vertex && edge.vert2 != vertex)) {
continue;
}
- inner_edges.append(InnerEdge(mesh_data, &other_looptri, vertex));
+ inner_edges.append(InnerEdge(mesh_data, other_primitive_i, &other_looptri, vertex));
current_edge = edge_i;
previous_primitive = other_primitive_i;
stop = true;
@@ -584,7 +610,7 @@ struct Fan {
}
}
- int count_num_to_add() const
+ int count_edges_not_added() const
{
int result = 0;
for (const InnerEdge &fan_edge : inner_edges) {
@@ -597,18 +623,11 @@ struct Fan {
void mark_already_added_segments(const MeshData &mesh_data, const UVVertex &uv_vertex)
{
+ Vector<int> mesh_primitive_indices = connecting_mesh_primitive_indices(uv_vertex);
+
+ /* Go over all fan edges to find if they can be found as primitive around the uv vertex. */
for (InnerEdge &fan_edge : inner_edges) {
- fan_edge.flags.found = false;
- const int v0 = mesh_data.loops[fan_edge.primitive->tri[fan_edge.vert_order[0]]].v;
- const int v1 = mesh_data.loops[fan_edge.primitive->tri[fan_edge.vert_order[1]]].v;
- for (const UVEdge *edge : uv_vertex.uv_edges) {
- const int e0 = edge->vertices[0]->vertex;
- const int e1 = edge->vertices[1]->vertex;
- if ((e0 == v0 && e1 == v1) || (e0 == v1 && e1 == v0)) {
- fan_edge.flags.found = true;
- break;
- }
- }
+ fan_edge.flags.found = mesh_primitive_indices.contains(fan_edge.primitive_index);
}
}
@@ -636,6 +655,150 @@ struct Fan {
inner_edges[i].uvs[2] = inner_edges[i + 1].uvs[1];
}
}
+
+#ifndef NDEBUG
+ /**
+ * Check if the given vertex is part of the outside of the fan.
+ * Return true if the given vertex is found on the outside of the fan, otherwise returns false.
+ */
+ bool contains_vertex_on_outside(const MeshData &mesh_data, const int vertex_index) const
+ {
+ for (const InnerEdge &inner_edge : inner_edges) {
+ int v2 = mesh_data.loops[inner_edge.primitive->tri[inner_edge.vert_order[1]]].v;
+ if (vertex_index == v2) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+#endif
+
+ static bool is_path_valid(const Span<InnerEdge *> &path,
+ const MeshData &mesh_data,
+ const int from_vertex,
+ const int to_vertex)
+ {
+ int current_vert = from_vertex;
+ for (InnerEdge *inner_edge : path) {
+ int v1 = mesh_data.loops[inner_edge->primitive->tri[inner_edge->vert_order[1]]].v;
+ int v2 = mesh_data.loops[inner_edge->primitive->tri[inner_edge->vert_order[2]]].v;
+ if (!ELEM(current_vert, v1, v2)) {
+ return false;
+ }
+ current_vert = v1 == current_vert ? v2 : v1;
+ }
+ return current_vert == to_vertex;
+ }
+
+ /**
+ * Find the closest path over the fan between `from_vertex` and `to_vertex`. The result contains
+ * exclude the starting and final edge.
+ *
+ * Algorithm only uses the winding order of the given fan segments.
+ */
+ static Vector<InnerEdge *> path_between(const Span<InnerEdge *> edge_order,
+ const MeshData &mesh_data,
+ const int from_vertex,
+ const int to_vertex,
+ const bool reversed)
+ {
+ const int from_vert_order = 1;
+ const int to_vert_order = 2;
+ const int index_increment = reversed ? -1 : 1;
+
+ Vector<InnerEdge *> result;
+ result.reserve(edge_order.size());
+ int index = 0;
+ while (true) {
+ InnerEdge *inner_edge = edge_order[index];
+ int v2 =
+ mesh_data.loops[inner_edge->primitive->tri[inner_edge->vert_order[from_vert_order]]].v;
+ if (v2 == from_vertex) {
+ break;
+ }
+ index = (index + index_increment + edge_order.size()) % edge_order.size();
+ }
+
+ while (true) {
+ InnerEdge *inner_edge = edge_order[index];
+ result.append(inner_edge);
+
+ int v3 =
+ mesh_data.loops[inner_edge->primitive->tri[inner_edge->vert_order[to_vert_order]]].v;
+ if (v3 == to_vertex) {
+ break;
+ }
+
+ index = (index + index_increment + edge_order.size()) % edge_order.size();
+ }
+
+ return result;
+ }
+
+ /**
+ * Score the given solution to be the best. Best solution would have the lowest score.
+ *
+ * Score is determined by counting the number of steps and subtracting that with steps that have
+ * not yet been visited.
+ */
+ static int64_t score(const Span<InnerEdge *> solution)
+ {
+ int64_t not_visited_steps = 0;
+ for (InnerEdge *inner_edge : solution) {
+ if (!inner_edge->flags.found) {
+ not_visited_steps++;
+ }
+ }
+ return solution.size() - not_visited_steps;
+ }
+
+ Vector<InnerEdge *> best_path_between(const MeshData &mesh_data,
+ const int from_vertex,
+ const int to_vertex)
+ {
+ BLI_assert_msg(contains_vertex_on_outside(mesh_data, from_vertex),
+ "Inconsistency detected, `from_vertex` isn't part of the outside of the fan.");
+ BLI_assert_msg(contains_vertex_on_outside(mesh_data, to_vertex),
+ "Inconsistency detected, `to_vertex` isn't part of the outside of the fan.");
+ if (to_vertex == from_vertex) {
+ return Vector<InnerEdge *>();
+ }
+
+ Array<InnerEdge *> edges(inner_edges.size());
+ for (int64_t index : inner_edges.index_range()) {
+ edges[index] = &inner_edges[index];
+ }
+
+ Vector<InnerEdge *> winding_1 = path_between(edges, mesh_data, from_vertex, to_vertex, false);
+ Vector<InnerEdge *> winding_2 = path_between(edges, mesh_data, from_vertex, to_vertex, true);
+
+ bool winding_1_valid = is_path_valid(winding_1, mesh_data, from_vertex, to_vertex);
+ bool winding_2_valid = is_path_valid(winding_2, mesh_data, from_vertex, to_vertex);
+
+ if (winding_1_valid && !winding_2_valid) {
+ return winding_1;
+ }
+ if (!winding_1_valid && winding_2_valid) {
+ return winding_2;
+ }
+ if (!winding_1_valid && !winding_2_valid) {
+ BLI_assert_msg(false, "Both solutions aren't valid.");
+ return Vector<InnerEdge *>();
+ }
+ if (score(winding_1) < score(winding_2)) {
+ return winding_1;
+ }
+ return winding_2;
+ }
+
+ void print_debug(const MeshData &mesh_data) const
+ {
+ for (const InnerEdge &inner_edge : inner_edges) {
+ inner_edge.print_debug(mesh_data);
+ }
+ std::cout << "\n";
+ }
};
static void add_uv_primitive_shared_uv_edge(const MeshData &mesh_data,
@@ -679,25 +842,11 @@ static void add_uv_primitive_shared_uv_edge(const MeshData &mesh_data,
uv_primitive_append_to_uv_vertices(prim1);
island.uv_primitives.append(prim1);
}
-
-static int find_fill_border(const MeshData &mesh_data, const int v1, const int v2, const int v3)
-{
- for (const int edge_i : mesh_data.vert_to_edge_map[v1]) {
- for (const int primitive_i : mesh_data.edge_to_primitive
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list