[Bf-blender-cvs] [bdcb11abb71] temp-T97352-3d-texturing-seam-bleeding-b2: Clean apply on master.
Jeroen Bakker
noreply at git.blender.org
Wed May 25 15:16:22 CEST 2022
Commit: bdcb11abb715f213f21ba924c499ed3b91851626
Author: Jeroen Bakker
Date: Wed May 25 15:15:03 2022 +0200
Branches: temp-T97352-3d-texturing-seam-bleeding-b2
https://developer.blender.org/rBbdcb11abb715f213f21ba924c499ed3b91851626
Clean apply on master.
===================================================================
A source/blender/blenkernel/BKE_uv_islands.hh
M source/blender/blenkernel/CMakeLists.txt
M source/blender/blenkernel/intern/pbvh_pixels.cc
A source/blender/blenkernel/intern/uv_islands.cc
===================================================================
diff --git a/source/blender/blenkernel/BKE_uv_islands.hh b/source/blender/blenkernel/BKE_uv_islands.hh
new file mode 100644
index 00000000000..cdb42d84883
--- /dev/null
+++ b/source/blender/blenkernel/BKE_uv_islands.hh
@@ -0,0 +1,445 @@
+
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#pragma once
+
+#include <fstream>
+
+#include "BLI_array.hh"
+#include "BLI_math.h"
+#include "BLI_math_vec_types.hh"
+#include "BLI_vector.hh"
+
+#include "DNA_meshdata_types.h"
+
+namespace blender::bke::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.
+
+/*
+ * When enabled various parts of the code would generate an SVG file to visual see how the
+ * algorithm makes decisions.
+ */
+#define DEBUG_SVG
+
+struct UVIslands;
+struct UVIslandsMask;
+struct UVBorder;
+
+struct UVVertex {
+ /* Loop index of the vertex in the original mesh. */
+ uint64_t loop;
+ /* Position in uv space. */
+ float2 uv;
+};
+
+struct UVEdge {
+ UVVertex vertices[2];
+ int64_t adjacent_uv_primitive = -1;
+
+ bool has_shared_edge(const UVEdge &other) const
+ {
+ 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);
+ }
+
+ bool is_border_edge() const
+ {
+ return adjacent_uv_primitive == -1;
+ }
+};
+
+struct UVPrimitive {
+ /**
+ * Index of the primitive in the original mesh.
+ */
+ uint64_t index;
+ UVEdge edges[3];
+
+ explicit UVPrimitive(uint64_t prim_index, const MLoopTri &tri, const MLoopUV *mloopuv)
+ : index(prim_index)
+ {
+ for (int i = 0; i < 3; i++) {
+ 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];
+ }
+ }
+
+ Vector<std::pair<UVEdge &, UVEdge &>> shared_edges(UVPrimitive &other)
+ {
+ Vector<std::pair<UVEdge &, UVEdge &>> result;
+ for (int i = 0; i < 3; i++) {
+ for (int j = 0; j < 3; j++) {
+ if (edges[i].has_shared_edge(other.edges[j])) {
+ result.append(std::pair<UVEdge &, UVEdge &>(edges[i], other.edges[j]));
+ }
+ }
+ }
+ return result;
+ }
+
+ bool has_shared_edge(const UVPrimitive &other) const
+ {
+ 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;
+ }
+};
+
+struct UVBorderVert {
+ float2 uv;
+
+ /* Index of this vert in the vertices of the original mesh. */
+ int64_t vert;
+
+ struct {
+ /** Should this vertex still be checked when performing extension. */
+ bool extendable : 1;
+ } flags;
+
+ explicit UVBorderVert(float2 &uv, int64_t vert) : uv(uv), vert(vert)
+ {
+ flags.extendable = true;
+ }
+};
+
+struct UVBorderEdge {
+ UVEdge *edge;
+ bool tag = false;
+
+ explicit UVBorderEdge(UVEdge *edge) : edge(edge)
+ {
+ }
+};
+
+struct UVBorder {
+ /** Ordered list of UV Verts of the border of this island. */
+ // TODO: support multiple rings + order (CW, CCW)
+ Vector<UVBorderVert> verts;
+
+ /**
+ * Flip the order of the verts, changing the order between CW and CCW.
+ */
+ void flip_order();
+
+ /**
+ * Calculate the outside angle of the given vert.
+ */
+ float outside_angle(const UVBorderVert &vert) const;
+};
+
+struct UVIsland {
+ Vector<UVPrimitive> primitives;
+ /**
+ * List of borders of this island. There can be multiple borders per island as a border could be
+ * completely encapsulated by another one.
+ */
+ Vector<UVBorder> borders;
+
+ UVIsland(const UVPrimitive &primitive)
+ {
+ append(primitive);
+ }
+
+ /** Initialize the border attribute. */
+ void extract_border(const MLoop *mloop);
+ /** Iterative extend border to fit the mask. */
+ void extend_border(const UVIslandsMask &mask,
+ const short island_index,
+ const MLoopTri *looptris,
+ const int64_t looptri_len,
+ const MLoop *mloop);
+
+ private:
+ void append(const UVPrimitive &primitive)
+ {
+ primitives.append(primitive);
+ }
+
+ public:
+ bool has_shared_edge(const UVPrimitive &primitive) const
+ {
+ for (const UVPrimitive &prim : primitives) {
+ if (prim.has_shared_edge(primitive)) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ const void extend_border(const UVPrimitive &primitive)
+ {
+ UVPrimitive new_prim = primitive;
+ uint64_t shared_edges_len = 0;
+ for (UVPrimitive &prim : primitives) {
+ for (std::pair<UVEdge &, UVEdge &> &shared_edge : prim.shared_edges(new_prim)) {
+ // TODO: eventually this should be supported. Skipped for now as it isn't the most
+ // important this to add. */
+ BLI_assert(shared_edge.first.adjacent_uv_primitive == -1);
+ BLI_assert(shared_edge.second.adjacent_uv_primitive == -1);
+ shared_edge.first.adjacent_uv_primitive = new_prim.index;
+ shared_edge.second.adjacent_uv_primitive = prim.index;
+ shared_edges_len++;
+ }
+ }
+ BLI_assert_msg(shared_edges_len != 0,
+ "Cannot extend as primitive has no shared edges with UV island.");
+ BLI_assert_msg(shared_edges_len < 4,
+ "Cannot extend as primitive has to many shared edges with UV island. "
+ "Inconsistent UVIsland?");
+
+ append(new_prim);
+ }
+
+ /**
+ * 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)
+ {
+ Vector<const UVPrimitive *> prims_to_extend;
+ Vector<const UVPrimitive *> prims_to_append;
+ for (const UVPrimitive &other_prim : other.primitives) {
+ if (primitive.has_shared_edge(other_prim)) {
+ prims_to_extend.append(&other_prim);
+ }
+ else {
+ prims_to_append.append(&other_prim);
+ }
+ }
+
+ for (const UVPrimitive *other_prim : prims_to_extend) {
+ extend_border(*other_prim);
+ }
+ for (const UVPrimitive *other_prim : prims_to_append) {
+ append(*other_prim);
+ }
+ }
+};
+
+/* Debug functions to export to a SVG file. */
+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(std::ostream &ss, const UVIslandsMask &mask, int step);
+void svg(std::ostream &ss, const UVBorder &border);
+void svg_footer(std::ostream &ss);
+
+struct UVIslands {
+ Vector<UVIsland> islands;
+
+ explicit UVIslands(const MLoopTri *primitives, uint64_t primitives_len, const MLoopUV *mloopuv)
+ {
+ for (int prim = 0; prim < primitives_len; prim++) {
+ UVPrimitive primitive(prim, primitives[prim], mloopuv);
+ add(primitive);
+ }
+
+#ifdef DEBUG_SVG
+ std::ofstream of;
+ of.open("/tmp/islands.svg");
+ svg_header(of);
+ svg(of, *this, 0);
+ svg_footer(of);
+ of.close();
+#endif
+ }
+
+ void extract_borders(const MLoop *mloop)
+ {
+ for (UVIsland &island : islands) {
+ island.extract_border(mloop);
+ }
+ }
+
+ void extend_borders(const UVIslandsMask &islands_mask,
+ const MLoopTri *looptris,
+ const int64_t looptri_len,
+ const MLoop *mloop)
+ {
+ ushort index = 0;
+ for (UVIsland &island : islands) {
+ island.extend_border(islands_mask, index++, looptris, looptri_len, mloop);
+ }
+
+#ifdef DEBUG_SVG
+ std::ofstream of;
+ of.open("/tmp/borders.svg");
+ svg_header(of);
+ for (const UVIsland &island : islands) {
+ for (const UVBorder &border : island.borders) {
+ svg(of, border);
+ }
+ }
+ svg_footer(of);
+ of.close();
+#endif
+ }
+
+ 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.has_shared_edge(primitive)) {
+ extended_islands.append(index);
+ }
+ }
+
+ if (extended_islands.size() > 0) {
+ UVIsland &island = islands[extended_islands[0]];
+ island.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++) {
+ island.join(islands[extended_islands[index]], primitive);
+ }
+
+ /* remove the islands that have been joined, starting at the end. */
+ for (uint64_t index = extended_islands.size() - 1; index > 0; index--) {
+ islands.remove(extended_islands[index]);
+ }
+
+ return;
+ }
+
+ /* if the tri has not been added we can create a new island. */
+ 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;
+ }
+};
+
+/* Bitmask containing the num of the nearest Island. */
+// TODO: this is a really quick implementation.
+struct UVIslandsMask {
+ float2 udim_offset;
+ ushort2 resolution;
+ Array<uint16_t> mask;
+
+ UVIslandsMask(float2 udim_offset, ushort2 resolution)
+ : udim_offset(udim_offset), resolution(resolution), mask(resolution.x * resolution.y)
+ {
+ clear();
+ }
+
+ void clear()
+ {
+
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list