pbvh_uv_islands.hh

Go to the documentation of this file.

/* SPDX-FileCopyrightText: 2023 Blender Authors
 *
 * SPDX-License-Identifier: GPL-2.0-or-later */

 
#pragma once
 
#include <optional>
 
#include "BLI_array.hh"
#include "BLI_map.hh"
#include "BLI_math_vector_types.hh"
#include "BLI_offset_indices.hh"
#include "BLI_vector.hh"
#include "BLI_vector_list.hh"
 
namespace blender::bke::pbvh::uv_islands {
 
struct UVBorder;
struct UVEdge;
struct UVIslands;
struct UVIslandsMask;
struct UVPrimitive;
struct MeshData;
struct UVVertex;
 
class VertToEdgeMap {
  Array<Vector<int>> edges_of_vert_;
 
 public:
  VertToEdgeMap() = delete;
  VertToEdgeMap(const int verts_num)
  {
    edges_of_vert_.reinitialize(verts_num);
  }
 
  void add(const int edge_i, const int v1, const int v2)
  {
    edges_of_vert_[v1].append(edge_i);
    edges_of_vert_[v2].append(edge_i);
  }
  Span<int> operator[](const int vert_i) const
  {
    return edges_of_vert_[vert_i];
  }
};
 
class EdgeToPrimitiveMap {
  Array<Vector<int>> primitives_of_edge_;
 
 public:
  EdgeToPrimitiveMap() = delete;
  EdgeToPrimitiveMap(const int edges_num)
  {
    primitives_of_edge_.reinitialize(edges_num);
  }
 
  void add(const int primitive_i, const int edge_i)
  {
    primitives_of_edge_[edge_i].append(primitive_i);
  }
  Span<int> operator[](const int edge_i) const
  {
    return primitives_of_edge_[edge_i];
  }
};
 
class TriangleToEdgeMap {
  Array<std::array<int, 3>> edges_of_triangle_;
 
 public:
  TriangleToEdgeMap() = delete;
  TriangleToEdgeMap(const int edges_num)
  {
    edges_of_triangle_.reinitialize(edges_num);
  }
 
  void add(const Span<int> edges, const int tri_i)
  {
    std::copy(edges.begin(), edges.end(), edges_of_triangle_[tri_i].begin());
  }
  Span<int> operator[](const int tri_i) const
  {
    return edges_of_triangle_[tri_i];
  }
};

struct MeshData {
 public:
  OffsetIndices<int> faces;
  Span<int3> corner_tris;
  Span<int> corner_verts;
  Span<float2> uv_map;
  Span<float3> vert_positions;
 
  VertToEdgeMap vert_to_edge_map;
 
  Vector<int2> edges;
  EdgeToPrimitiveMap edge_to_primitive_map;
 
  TriangleToEdgeMap primitive_to_edge_map;

  Array<int> uv_island_ids;
  int64_t uv_island_len;
 
  explicit MeshData(OffsetIndices<int> faces,
                    Span<int3> corner_tris,
                    Span<int> corner_verts,
                    Span<float2> uv_map,
                    Span<float3> vert_positions);
};
 
struct UVVertex {
  int vertex;
  /* Position in uv space. */
  float2 uv;
 
  /* uv edges that share this UVVertex. */
  Vector<UVEdge *> uv_edges;
 
  struct {
    bool is_border : 1;
    bool is_extended : 1;
  } flags;
 
  explicit UVVertex();
  explicit UVVertex(const MeshData &mesh_data, const int loop);
};
 
struct UVEdge {
  std::array<UVVertex *, 2> vertices;
  Vector<int, 2> uv_primitive_indices;
 
  UVVertex *get_other_uv_vertex(const int vertex_index);
  bool has_shared_edge(Span<float2> uv_map, const int loop_1, const int loop_2) const;
  bool has_shared_edge(const UVEdge &other) const;
  bool has_same_vertices(const int2 &edge) const;
  bool is_border_edge() const;
 
 private:
  bool has_shared_edge(const UVVertex &v1, const UVVertex &v2) const;
  bool has_same_vertices(const int vert1, const int vert2) const;
  bool has_same_uv_vertices(const UVEdge &other) const;
};
 
struct UVPrimitive {
  const int primitive_i;
  Vector<UVEdge *, 3> edges;
 
  explicit UVPrimitive(const int primitive_i);
 
  Vector<std::pair<UVEdge *, UVEdge *>> shared_edges(UVPrimitive &other);
  bool has_shared_edge(const UVPrimitive &other) const;
  bool has_shared_edge(const MeshData &mesh_data, int other_triangle_index) const;

  const UVVertex *get_uv_vertex(const MeshData &mesh_data, const uint8_t mesh_vert_index) const;

  UVEdge *get_uv_edge(const float2 uv1, const float2 uv2) const;
  UVEdge *get_uv_edge(const int v1, const int v2) const;
 
  bool contains_uv_vertex(const UVVertex *uv_vertex) const;
  const UVVertex *get_other_uv_vertex(const UVVertex *v1, const UVVertex *v2) const;
 
  UVBorder extract_border() const;
};
 
struct UVBorderEdge {
  UVEdge *edge;
  bool tag = false;
  UVPrimitive *uv_primitive;
  /* Should the vertices of the edge be evaluated in reverse order. */
  bool reverse_order = false;
 
  int64_t index = -1;
  int64_t prev_index = -1;
  int64_t next_index = -1;
  int64_t border_index = -1;
 
  explicit UVBorderEdge(UVEdge *edge, UVPrimitive *uv_primitive);
 
  UVVertex *get_uv_vertex(int index);
  const UVVertex *get_uv_vertex(int index) const;

  const UVVertex *get_other_uv_vertex() const;
 
  float length() const;
};
 
struct UVBorderCorner {
  UVBorderEdge *first;
  UVBorderEdge *second;
  float angle;
 
  explicit UVBorderCorner(UVBorderEdge *first, UVBorderEdge *second, float angle);

  float2 uv(float factor, float min_uv_distance);

  bool connected_in_mesh() const;
  void print_debug() const;
};
 
struct UVBorder {
  Vector<UVBorderEdge> edges;

  bool is_ccw() const;

  void flip_order();

  float outside_angle(const UVBorderEdge &edge) const;
 
  void update_indexes(uint64_t border_index);
 
  static std::optional<UVBorder> extract_from_edges(Vector<UVBorderEdge> &edges);

  void remove(int64_t index);
};
 
struct UVIsland {
  int id;
  VectorList<UVVertex> uv_vertices;
  VectorList<UVEdge> uv_edges;
  VectorList<UVPrimitive> uv_primitives;
  Vector<UVBorder> borders;

  Map<int64_t, Vector<UVVertex *>> uv_vertex_lookup;
 
  UVVertex *lookup(const UVVertex &vertex);
  UVVertex *lookup_or_create(const UVVertex &vertex);
  UVEdge *lookup(const UVEdge &edge);
  UVEdge *lookup_or_create(const UVEdge &edge);

  void extract_borders();
  void extend_border(const MeshData &mesh_data,
                     const UVIslandsMask &mask,
                     const short island_index);
 
 private:
  void append(const UVPrimitive &primitive);
 
 public:
  bool has_shared_edge(const UVPrimitive &primitive) const;
  bool has_shared_edge(const MeshData &mesh_data, const int primitive_i) const;
  void extend_border(const UVPrimitive &primitive);

  void print_debug(const MeshData &mesh_data) const;
};
 
struct UVIslands {
  Vector<UVIsland> islands;
 
  explicit UVIslands(const MeshData &mesh_data);
 
  void extract_borders();
  void extend_borders(const MeshData &mesh_data, const UVIslandsMask &islands_mask);
  void print_debug(const MeshData &mesh_data) const;
};

struct UVIslandsMask {

  struct Tile {
    float2 udim_offset;
    ushort2 tile_resolution;
    ushort2 mask_resolution;
    Array<uint16_t> mask;
 
    Tile(float2 udim_offset, ushort2 tile_resolution);
 
    bool is_masked(const uint16_t island_index, const float2 uv) const;
    bool contains(const float2 uv) const;
    float get_pixel_size_in_uv_space() const;
  };
 
  Vector<Tile> tiles;
 
  void add_tile(float2 udim_offset, ushort2 resolution);

  const Tile *find_tile(const float2 uv) const;

  bool is_masked(const uint16_t island_index, const float2 uv) const;

  void add(const MeshData &mesh_data, const UVIslands &islands);
 
  void dilate(int max_iterations);
};
 
}  // namespace blender::bke::pbvh::uv_islands