Remove MeshVertex, use indices for edges and primitives

3 files changed, 283 insertions, 212 deletions

diff --git a/source/blender/blenkernel/intern/pbvh_pixels.cc b/source/blender/blenkernel/intern/pbvh_pixels.cc
index 5cb1b9374c0..538a3b5618e 100644
--- a/source/blender/blenkernel/intern/pbvh_pixels.cc
+++ b/source/blender/blenkernel/intern/pbvh_pixels.cc
@@ -1,6 +1,7 @@
 /* SPDX-License-Identifier: GPL-2.0-or-later
  * Copyright 2022 Blender Foundation. All rights reserved. */
 
+#include "BKE_attribute.hh"
 #include "BKE_customdata.h"
 #include "BKE_mesh.h"
 #include "BKE_mesh_mapping.h"
@@ -106,9 +107,9 @@ static void update_geom_primitives(PBVH &pbvh, const uv_islands::MeshData &mesh_
   PBVHData &pbvh_data = BKE_pbvh_pixels_data_get(pbvh);
   pbvh_data.clear_data();
   for (const uv_islands::MeshPrimitive &mesh_primitive : mesh_data.primitives) {
-    pbvh_data.geom_primitives.append(int3(mesh_primitive.vertices[0].vertex->v,
-                                          mesh_primitive.vertices[1].vertex->v,
-                                          mesh_primitive.vertices[2].vertex->v));
+    pbvh_data.geom_primitives.append(int3(mesh_primitive.vertices[0].vertex,
+                                          mesh_primitive.vertices[1].vertex,
+                                          mesh_primitive.vertices[2].vertex));
   }
 }
 
@@ -134,7 +135,7 @@ struct UVPrimitiveLookup {
       for (VectorList<uv_islands::UVPrimitive>::UsedVector &uv_primitives :
            uv_island.uv_primitives) {
         for (uv_islands::UVPrimitive &uv_primitive : uv_primitives) {
-          lookup[uv_primitive.primitive->index].append_as(Entry(&uv_primitive, uv_island_index));
+          lookup[uv_primitive.primitive_i].append_as(Entry(&uv_primitive, uv_island_index));
         }
       }
       uv_island_index++;
@@ -143,6 +144,7 @@ struct UVPrimitiveLookup {
 };
 
 struct EncodePixelsUserData {
+  const uv_islands::MeshData *mesh_data;
   Image *image;
   ImageUser *image_user;
   PBVH *pbvh;
@@ -158,6 +160,7 @@ static void do_encode_pixels(void *__restrict userdata,
                              const TaskParallelTLS *__restrict UNUSED(tls))
 {
   EncodePixelsUserData *data = static_cast<EncodePixelsUserData *>(userdata);
+  const uv_islands::MeshData &mesh_data = *data->mesh_data;
   Image *image = data->image;
   ImageUser image_user = *data->image_user;
   PBVHNode *node = (*data->nodes)[n];
@@ -183,9 +186,9 @@ static void do_encode_pixels(void *__restrict userdata,
            data->uv_primitive_lookup->lookup[geom_prim_index]) {
         uv_islands::UVBorder uv_border = entry.uv_primitive->extract_border();
         float2 uvs[3] = {
-            entry.uv_primitive->get_uv_vertex(0)->uv - tile_offset,
-            entry.uv_primitive->get_uv_vertex(1)->uv - tile_offset,
-            entry.uv_primitive->get_uv_vertex(2)->uv - tile_offset,
+            entry.uv_primitive->get_uv_vertex(mesh_data, 0)->uv - tile_offset,
+            entry.uv_primitive->get_uv_vertex(mesh_data, 1)->uv - tile_offset,
+            entry.uv_primitive->get_uv_vertex(mesh_data, 2)->uv - tile_offset,
         };
         const float minv = clamp_f(min_fff(uvs[0].y, uvs[1].y, uvs[2].y), 0.0f, 1.0f);
         const int miny = floor(minv * image_buffer->y);
@@ -362,9 +365,9 @@ static void update_pixels(PBVH *pbvh, Mesh *mesh, Image *image, ImageUser *image
   }
 
   uv_islands::MeshData mesh_data({pbvh->looptri, pbvh->totprim},
-                                 {pbvh->mloop, pbvh->totprim},
+                                 {pbvh->mloop, mesh->totloop},
                                  pbvh->totvert,
-                                 {ldata_uv, pbvh->totprim});
+                                 {ldata_uv, mesh->totloop});
   uv_islands::UVIslands islands(mesh_data);
 
   uv_islands::UVIslandsMask uv_masks;
@@ -380,16 +383,17 @@ static void update_pixels(PBVH *pbvh, Mesh *mesh, Image *image, ImageUser *image
                       ushort2(tile_buffer->x, tile_buffer->y));
     BKE_image_release_ibuf(image, tile_buffer, nullptr);
   }
-  uv_masks.add(islands);
+  uv_masks.add(mesh_data, islands);
   uv_masks.dilate(image->seamfix_iter);
 
   islands.extract_borders();
-  islands.extend_borders(uv_masks);
+  islands.extend_borders(mesh_data, uv_masks);
   update_geom_primitives(*pbvh, mesh_data);
 
   UVPrimitiveLookup uv_primitive_lookup(mesh_data.looptris.size(), islands);
 
   EncodePixelsUserData user_data;
+  user_data.mesh_data = &mesh_data;
   user_data.pbvh = pbvh;
   user_data.image = image;
   user_data.image_user = image_user;
diff --git a/source/blender/blenkernel/intern/pbvh_uv_islands.cc b/source/blender/blenkernel/intern/pbvh_uv_islands.cc
index 3303a3623fb..cb7ce9e9ad0 100644
--- a/source/blender/blenkernel/intern/pbvh_uv_islands.cc
+++ b/source/blender/blenkernel/intern/pbvh_uv_islands.cc
@@ -31,23 +31,23 @@ static void uv_primitive_append_to_uv_vertices(UVPrimitive &uv_primitive)
 /** \name MeshPrimitive
  * \{ */
 
-MeshUVVert *MeshPrimitive::get_other_uv_vertex(const MeshVertex *v1, const MeshVertex *v2)
+int MeshPrimitive::get_other_uv_vertex(const int v1, const int v2) const
 {
   BLI_assert(vertices[0].vertex == v1 || vertices[1].vertex == v1 || vertices[2].vertex == v1);
   BLI_assert(vertices[0].vertex == v2 || vertices[1].vertex == v2 || vertices[2].vertex == v2);
-  for (MeshUVVert &uv_vertex : vertices) {
+  for (const MeshUVVert &uv_vertex : vertices) {
     if (uv_vertex.vertex != v1 && uv_vertex.vertex != v2) {
-      return &uv_vertex;
+      return uv_vertex.vertex;
     }
   }
-  return nullptr;
+  return -1;
 }
 
-bool MeshPrimitive::has_shared_uv_edge(const MeshPrimitive *other) const
+bool MeshPrimitive::has_shared_uv_edge(const MeshPrimitive &other) const
 {
   int shared_uv_verts = 0;
   for (const MeshUVVert &vert : vertices) {
-    for (const MeshUVVert &other_vert : other->vertices) {
+    for (const MeshUVVert &other_vert : other.vertices) {
       if (vert.uv == other_vert.uv) {
         shared_uv_verts += 1;
       }
@@ -56,7 +56,7 @@ bool MeshPrimitive::has_shared_uv_edge(const MeshPrimitive *other) const
   return shared_uv_verts >= 2;
 }
 
-static const MeshUVVert &get_uv_vert(const MeshPrimitive &mesh_primitive, const MeshVertex *vert)
+static const MeshUVVert &get_uv_vert(const MeshPrimitive &mesh_primitive, const int vert)
 {
   for (const MeshUVVert &uv_vert : mesh_primitive.vertices) {
     if (uv_vert.vertex == vert) {
@@ -67,10 +67,10 @@ static const MeshUVVert &get_uv_vert(const MeshPrimitive &mesh_primitive, const
   return mesh_primitive.vertices[0];
 }
 
-const bool has_vertex(const MeshPrimitive &mesh_primitive, const MeshVertex &mesh_vertex)
+static bool has_vertex(const MeshPrimitive &mesh_primitive, const int vert)
 {
   for (int i = 0; i < 3; i++) {
-    if (mesh_primitive.vertices[i].vertex == &mesh_vertex) {
+    if (mesh_primitive.vertices[i].vertex == vert) {
       return true;
     }
   }
@@ -93,16 +93,6 @@ rctf MeshPrimitive::uv_bounds() const
 /** \name MeshData
  * \{ */
 
-static void mesh_data_init_vertices(MeshData &mesh_data)
-{
-  mesh_data.vertices.reserve(mesh_data.verts_num);
-  for (int64_t i = 0; i < mesh_data.verts_num; i++) {
-    MeshVertex vert;
-    vert.v = i;
-    mesh_data.vertices.append(vert);
-  }
-}
-
 static void mesh_data_init_primitives(MeshData &mesh_data)
 {
   mesh_data.primitives.reserve(mesh_data.looptris.size());
@@ -115,7 +105,7 @@ static void mesh_data_init_primitives(MeshData &mesh_data)
     for (int j = 0; j < 3; j++) {
       MeshUVVert uv_vert;
       uv_vert.loop = tri.tri[j];
-      uv_vert.vertex = &mesh_data.vertices[mesh_data.loops[uv_vert.loop].v];
+      uv_vert.vertex = mesh_data.loops[uv_vert.loop].v;
       uv_vert.uv = mesh_data.mloopuv[uv_vert.loop].uv;
       primitive.vertices.append(uv_vert);
     }
@@ -123,7 +113,7 @@ static void mesh_data_init_primitives(MeshData &mesh_data)
   }
 }
 
-void mesh_data_init_edges(MeshData &mesh_data)
+static void mesh_data_init_edges(MeshData &mesh_data)
 {
   mesh_data.edges.reserve(mesh_data.looptris.size() * 2);
   EdgeHash *eh = BLI_edgehash_new_ex(__func__, mesh_data.looptris.size() * 3);
@@ -144,82 +134,96 @@ void mesh_data_init_edges(MeshData &mesh_data)
         edge_index = mesh_data.edges.size();
         *edge_index_ptr = POINTER_FROM_INT(edge_index + 1);
         MeshEdge edge;
-        edge.vert1 = &mesh_data.vertices[v1];
-        edge.vert2 = &mesh_data.vertices[v2];
+        edge.vert1 = v1;
+        edge.vert2 = v2;
         mesh_data.edges.append(edge);
-        MeshEdge *edge_ptr = &mesh_data.edges.last();
-        mesh_data.vertices[v1].edges.append(edge_ptr);
-        mesh_data.vertices[v2].edges.append(edge_ptr);
+        mesh_data.vert_to_edge_map.add(edge_index, v1, v2);
       }
 
-      MeshEdge *edge = &mesh_data.edges[edge_index];
-      edge->primitives.append(&primitive);
-      primitive.edges.append(edge);
+      primitive.edges.append(edge_index);
+    }
+  }
+  /* Build edge to neighboring triangle map. */
+  mesh_data.edge_to_primitive_map = EdgeToPrimitiveMap(mesh_data.edges.size());
+  for (const int prim_i : mesh_data.primitives.index_range()) {
+    const MeshPrimitive &primitive = mesh_data.primitives[prim_i];
+    for (const int edge_i : primitive.edges) {
+      mesh_data.edge_to_primitive_map.add(prim_i, edge_i);
     }
   }
+
   BLI_edgehash_free(eh, nullptr);
 }
-static const int64_t INVALID_UV_ISLAND_ID = -1;
+static constexpr int INVALID_UV_ISLAND_ID = -1;
 /**
  * NOTE: doesn't support weird topology where unconnected mesh primitives share the same uv
  * island. For a accurate implementation we should use implement an uv_prim_lookup.
  */
-static void extract_uv_neighbors(Vector<MeshPrimitive *> &prims_to_add, MeshPrimitive *primitive)
-{
-  for (MeshEdge *edge : primitive->edges) {
-    for (MeshPrimitive *other_primitive : edge->primitives) {
-      if (primitive == other_primitive) {
+static void extract_uv_neighbors(const MeshData &mesh_data,
+                                 const Span<int> uv_island_ids,
+                                 const int primitive_i,
+                                 Vector<int> &prims_to_add)
+{
+  const MeshPrimitive &primitive = mesh_data.primitives[primitive_i];
+  for (const int edge : primitive.edges) {
+    for (const int other_primitive_i : mesh_data.edge_to_primitive_map[edge]) {
+      if (primitive_i == other_primitive_i) {
         continue;
       }
-      if (other_primitive->uv_island_id != INVALID_UV_ISLAND_ID) {
+      if (uv_island_ids[other_primitive_i] != INVALID_UV_ISLAND_ID) {
         continue;
       }
 
-      if (primitive->has_shared_uv_edge(other_primitive)) {
-        prims_to_add.append(other_primitive);
+      const MeshPrimitive &other_primitive = mesh_data.primitives[other_primitive_i];
+      if (primitive.has_shared_uv_edge(other_primitive)) {
+        prims_to_add.append(other_primitive_i);
       }
     }
   }
 }
 
-void mesh_data_init_primitive_uv_island_ids(MeshData &mesh_data)
+static int mesh_data_init_primitive_uv_island_ids(MeshData &mesh_data)
 {
-  for (MeshPrimitive &primitive : mesh_data.primitives) {
-    primitive.uv_island_id = INVALID_UV_ISLAND_ID;
-  }
+  mesh_data.uv_island_ids.reinitialize(mesh_data.primitives.size());
+  mesh_data.uv_island_ids.fill(INVALID_UV_ISLAND_ID);
 
-  int64_t uv_island_id = 0;
-  Vector<MeshPrimitive *> prims_to_add;
-  for (MeshPrimitive &primitive : mesh_data.primitives) {
+  int uv_island_id = 0;
+  Vector<int> prims_to_add;
+  for (const int primitive_i : mesh_data.primitives.index_range()) {
     /* Early exit when uv island id is already extracted during uv neighbor extractions. */
-    if (primitive.uv_island_id != INVALID_UV_ISLAND_ID) {
+    if (mesh_data.uv_island_ids[primitive_i] != INVALID_UV_ISLAND_ID) {
       continue;
     }
 
-    prims_to_add.append(&primitive);
+    prims_to_add.append(primitive_i);
     while (!prims_to_add.is_empty()) {
-      MeshPrimitive *primitive = prims_to_add.pop_last();
-      primitive->uv_island_id = uv_island_id;
-      extract_uv_neighbors(prims_to_add, primitive);
+      const int other_primitive_i = prims_to_add.pop_last();
+      mesh_data.uv_island_ids[other_primitive_i] = uv_island_id;
+      extract_uv_neighbors(mesh_data, mesh_data.uv_island_ids, other_primitive_i, prims_to_add);
     }
     uv_island_id++;
   }
-  mesh_data.uv_island_len = uv_island_id;
+
+  return uv_island_id;
 }
 
 static void mesh_data_init(MeshData &mesh_data)
 {
-  mesh_data_init_vertices(mesh_data);
   mesh_data_init_primitives(mesh_data);
   mesh_data_init_edges(mesh_data);
-  mesh_data_init_primitive_uv_island_ids(mesh_data);
+  mesh_data.uv_island_len = mesh_data_init_primitive_uv_island_ids(mesh_data);
 }
 
 MeshData::MeshData(const Span<MLoopTri> looptris,
                    const Span<MLoop> loops,
                    const int verts_num,
                    const Span<MLoopUV> mloopuv)
-    : looptris(looptris), verts_num(verts_num), loops(loops), mloopuv(mloopuv)
+    : looptris(looptris),
+      verts_num(verts_num),
+      loops(loops),
+      mloopuv(mloopuv),
+      vert_to_edge_map(verts_num),
+      edge_to_primitive_map(0)
 {
   mesh_data_init(*this);
 }
@@ -269,22 +273,21 @@ bool UVEdge::has_shared_edge(const UVEdge &other) const
   return has_shared_edge(*other.vertices[0], *other.vertices[1]);
 }
 
-bool UVEdge::has_same_vertices(const MeshVertex &vert1, const MeshVertex &vert2) const
+bool UVEdge::has_same_vertices(const int vert1, const int vert2) const
 {
-  return (vertices[0]->vertex == &vert1 && vertices[1]->vertex == &vert2) ||
-         (vertices[0]->vertex == &vert2 && vertices[1]->vertex == &vert1);
+  return (vertices[0]->vertex == vert1 && vertices[1]->vertex == vert2) ||
+         (vertices[0]->vertex == vert2 && vertices[1]->vertex == vert1);
 }
 
 bool UVEdge::has_same_uv_vertices(const UVEdge &other) const
 {
   return has_shared_edge(other) &&
-         has_same_vertices(*other.vertices[0]->vertex, *other.vertices[1]->vertex);
-  ;
+         has_same_vertices(other.vertices[0]->vertex, other.vertices[1]->vertex);
 }
 
 bool UVEdge::has_same_vertices(const MeshEdge &edge) const
 {
-  return has_same_vertices(*edge.vert1, *edge.vert2);
+  return has_same_vertices(edge.vert1, edge.vert2);
 }
 
 bool UVEdge::is_border_edge() const
@@ -292,7 +295,7 @@ bool UVEdge::is_border_edge() const
   return uv_primitives.size() == 1;
 }
 
-UVVertex *UVEdge::get_other_uv_vertex(const MeshVertex *vertex)
+UVVertex *UVEdge::get_other_uv_vertex(const int vertex)
 {
   if (vertices[0]->vertex == vertex) {
     return vertices[1];
@@ -307,7 +310,7 @@ UVVertex *UVEdge::get_other_uv_vertex(const MeshVertex *vertex)
  * \{ */
 UVVertex *UVIsland::lookup(const UVVertex &vertex)
 {
-  int64_t vert_index = vertex.vertex->v;
+  const int vert_index = vertex.vertex;
   Vector<UVVertex *> &vertices = uv_vertex_lookup.lookup_or_add_default(vert_index);
   for (UVVertex *v : vertices) {
     if (v->uv == vertex.uv) {
@@ -328,7 +331,7 @@ UVVertex *UVIsland::lookup_or_create(const UVVertex &vertex)
   UVVertex *result = &uv_vertices.last();
   result->uv_edges.clear();
   /* v is already a key. Ensured by UVIsland::lookup in this method. */
-  uv_vertex_lookup.lookup(vertex.vertex->v).append(result);
+  uv_vertex_lookup.lookup(vertex.vertex).append(result);
   return result;
 }
 
@@ -411,14 +414,18 @@ void UVIsland::extend_border(const UVPrimitive &primitive)
   }
 }
 
-static UVPrimitive *add_primitive(UVIsland &uv_island, MeshPrimitive &primitive)
+static UVPrimitive *add_primitive(const MeshData &mesh_data,
+                                  UVIsland &uv_island,
+                                  const int primitive_i)
 {
-  UVPrimitive uv_primitive(&primitive);
+  UVPrimitive uv_primitive(primitive_i);
+  const MeshPrimitive &primitive = mesh_data.primitives[primitive_i];
   uv_island.uv_primitives.append(uv_primitive);
   UVPrimitive *uv_primitive_ptr = &uv_island.uv_primitives.last();
-  for (MeshEdge *edge : primitive.edges) {
-    const MeshUVVert &v1 = get_uv_vert(primitive, edge->vert1);
-    const MeshUVVert &v2 = get_uv_vert(primitive, edge->vert2);
+  for (const int edge_i : primitive.edges) {
+    const MeshEdge &edge = mesh_data.edges[edge_i];
+    const MeshUVVert &v1 = get_uv_vert(primitive, edge.vert1);
+    const MeshUVVert &v2 = get_uv_vert(primitive, edge.vert2);
     UVEdge uv_edge_template;
     uv_edge_template.vertices[0] = uv_island.lookup_or_create(UVVertex(v1));
     uv_edge_template.vertices[1] = uv_island.lookup_or_create(UVVertex(v2));
@@ -493,7 +500,7 @@ static std::optional<UVBorderCorner> sharpest_border_corner(UVIsland &island)
 
 /** The inner edge of a fan. */
 struct InnerEdge {
-  MeshPrimitive *primitive;
+  const MeshPrimitive *primitive;
   /* UVs order are already applied. So uvs[0] mathes primitive->vertices[vert_order[0]]/ */
   float2 uvs[3];
   int vert_order[3];
@@ -502,7 +509,7 @@ struct InnerEdge {
     bool found : 1;
   } flags;
 
-  InnerEdge(MeshPrimitive *primitive, MeshVertex *vertex) : primitive(primitive)
+  InnerEdge(const MeshPrimitive *primitive, int vertex) : primitive(primitive)
   {
     flags.found = false;
 
@@ -540,29 +547,32 @@ struct Fan {
 
   } flags;
 
-  Fan(MeshVertex &vertex)
+  Fan(const MeshData &mesh_data, const int vertex)
   {
     flags.full = true;
-    MeshEdge *current_edge = vertex.edges[0];
-    MeshPrimitive *stop_primitive = current_edge->primitives[0];
-    MeshPrimitive *previous_primitive = stop_primitive;
+    int current_edge = mesh_data.vert_to_edge_map[vertex].first();
+    const int stop_primitive = mesh_data.edge_to_primitive_map[current_edge].first();
+    int previous_primitive = stop_primitive;
     while (true) {
       bool stop = false;
-      for (MeshPrimitive *other : current_edge->primitives) {
+      for (const int other_primitive_i : mesh_data.edge_to_primitive_map[current_edge]) {
         if (stop) {
           break;
         }
-        if (other == previous_primitive) {
+        if (other_primitive_i == previous_primitive) {
           continue;
         }
 
-        for (MeshEdge *edge : other->edges) {
-          if (edge == current_edge || (edge->vert1 != &vertex && edge->vert2 != &vertex)) {
+        const MeshPrimitive &other_primitive = mesh_data.primitives[other_primitive_i];
+
+        for (const int edge_i : other_primitive.edges) {
+          const MeshEdge &edge = mesh_data.edges[edge_i];
+          if (edge_i == current_edge || (edge.vert1 != vertex && edge.vert2 != vertex)) {
             continue;
           }
-          inner_edges.append(InnerEdge(other, &vertex));
-          current_edge = edge;
-          previous_primitive = other;
+          inner_edges.append(InnerEdge(&other_primitive, vertex));
+          current_edge = edge_i;
+          previous_primitive = other_primitive_i;
           stop = true;
           break;
         }
@@ -592,11 +602,11 @@ struct Fan {
   {
     for (InnerEdge &fan_edge : inner_edges) {
       fan_edge.flags.found = false;
-      const MeshVertex *v0 = fan_edge.primitive->vertices[fan_edge.vert_order[0]].vertex;
-      const MeshVertex *v1 = fan_edge.primitive->vertices[fan_edge.vert_order[1]].vertex;
+      const int v0 = fan_edge.primitive->vertices[fan_edge.vert_order[0]].vertex;
+      const int v1 = fan_edge.primitive->vertices[fan_edge.vert_order[1]].vertex;
       for (const UVEdge *edge : uv_vertex.uv_edges) {
-        const MeshVertex *e0 = edge->vertices[0]->vertex;
-        const MeshVertex *e1 = edge->vertices[1]->vertex;
+        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;
@@ -608,14 +618,14 @@ struct Fan {
   void init_uv_coordinates(UVVertex &uv_vertex)
   {
     for (InnerEdge &fan_edge : inner_edges) {
-      int64_t other_v = fan_edge.primitive->vertices[fan_edge.vert_order[0]].vertex->v;
-      if (other_v == uv_vertex.vertex->v) {
-        other_v = fan_edge.primitive->vertices[fan_edge.vert_order[1]].vertex->v;
+      int other_v = fan_edge.primitive->vertices[fan_edge.vert_order[0]].vertex;
+      if (other_v == uv_vertex.vertex) {
+        other_v = fan_edge.primitive->vertices[fan_edge.vert_order[1]].vertex;
       }
 
       for (UVEdge *edge : uv_vertex.uv_edges) {
         const UVVertex *other_uv_vertex = edge->get_other_uv_vertex(uv_vertex.vertex);
-        int64_t other_edge_v = other_uv_vertex->vertex->v;
+        int64_t other_edge_v = other_uv_vertex->vertex;
         if (other_v == other_edge_v) {
           fan_edge.uvs[0] = uv_vertex.uv;
           fan_edge.uvs[1] = other_uv_vertex->uv;
@@ -631,27 +641,29 @@ struct Fan {
   }
 };
 
-static void add_uv_primitive_shared_uv_edge(UVIsland &island,
+static void add_uv_primitive_shared_uv_edge(const MeshData &mesh_data,
+                                            UVIsland &island,
                                             UVVertex *connected_vert_1,
                                             UVVertex *connected_vert_2,
                                             float2 uv_unconnected,
-                                            MeshPrimitive *mesh_primitive)
+                                            const int mesh_primitive_i)
 {
-  UVPrimitive prim1(mesh_primitive);
+  UVPrimitive prim1(mesh_primitive_i);
+  const MeshPrimitive &mesh_primitive = mesh_data.primitives[mesh_primitive_i];
 
-  MeshUVVert *other_vert = mesh_primitive->get_other_uv_vertex(connected_vert_1->vertex,
-                                                               connected_vert_2->vertex);
+  const int other_vert_i = mesh_primitive.get_other_uv_vertex(connected_vert_1->vertex,
+                                                              connected_vert_2->vertex);
   UVVertex vert_template;
   vert_template.uv = uv_unconnected;
-  vert_template.vertex = other_vert->vertex;
+  vert_template.vertex = other_vert_i;
   UVVertex *vert_ptr = island.lookup_or_create(vert_template);
 
-  const MeshUVVert *mesh_vert_1 = &get_uv_vert(*mesh_primitive, connected_vert_1->vertex);
+  const MeshUVVert *mesh_vert_1 = &get_uv_vert(mesh_primitive, connected_vert_1->vertex);
   vert_template.uv = connected_vert_1->uv;
   vert_template.vertex = mesh_vert_1->vertex;
   UVVertex *vert_1_ptr = island.lookup_or_create(vert_template);
 
-  const MeshUVVert *mesh_vert_2 = &get_uv_vert(*mesh_primitive, connected_vert_2->vertex);
+  const MeshUVVert *mesh_vert_2 = &get_uv_vert(mesh_primitive, connected_vert_2->vertex);
   vert_template.uv = connected_vert_2->uv;
   vert_template.vertex = mesh_vert_2->vertex;
   UVVertex *vert_2_ptr = island.lookup_or_create(vert_template);
@@ -671,52 +683,53 @@ static void add_uv_primitive_shared_uv_edge(UVIsland &island,
   island.uv_primitives.append(prim1);
 }
 
-static MeshPrimitive *find_fill_border(const MeshVertex &v1,
-                                       const MeshVertex &v2,
-                                       const MeshVertex &v3)
+static int find_fill_border(const MeshData &mesh_data, const int v1, const int v2, const int v3)
 {
-  for (MeshEdge *edge : v1.edges) {
-    for (MeshPrimitive *primitive : edge->primitives) {
-      if (has_vertex(*primitive, v1) && has_vertex(*primitive, v2) && has_vertex(*primitive, v3)) {
-        return primitive;
+  for (const int edge_i : mesh_data.vert_to_edge_map[v1]) {
+    for (const int primitive_i : mesh_data.edge_to_primitive_map[edge_i]) {
+      const MeshPrimitive &primitive = mesh_data.primitives[primitive_i];
+      if (has_vertex(primitive, v1) && has_vertex(primitive, v2) && has_vertex(primitive, v3)) {
+        return primitive_i;
       }
     }
   }
-  return nullptr;
+  return -1;
 }
 /**
  * Find a primitive that can be used to fill give corner.
- * Will return nullptr when no primitive can be found.
+ * Will return -1 when no primitive can be found.
  */
-static MeshPrimitive *find_fill_border(UVBorderCorner &corner)
+static int find_fill_border(const MeshData &mesh_data, UVBorderCorner &corner)
 {
   if (corner.first->get_uv_vertex(1) != corner.second->get_uv_vertex(0)) {
-    return nullptr;
+    return -1;
   }
   if (corner.first->get_uv_vertex(0) == corner.second->get_uv_vertex(1)) {
-    return nullptr;
+    return -1;
   }
   UVVertex *shared_vert = corner.second->get_uv_vertex(0);
-  for (MeshEdge *edge : shared_vert->vertex->edges) {
-    if (corner.first->edge->has_same_vertices(*edge)) {
-      for (MeshPrimitive *primitive : edge->primitives) {
-        MeshVertex *other_vert = primitive->get_other_uv_vertex(edge->vert1, edge->vert2)->vertex;
+  for (const int edge_i : mesh_data.vert_to_edge_map[shared_vert->vertex]) {
+    const MeshEdge &edge = mesh_data.edges[edge_i];
+    if (corner.first->edge->has_same_vertices(edge)) {
+      for (const int primitive_i : mesh_data.edge_to_primitive_map[edge_i]) {
+        const MeshPrimitive &primitive = mesh_data.primitives[primitive_i];
+        const int other_vert = primitive.get_other_uv_vertex(edge.vert1, edge.vert2);
         if (other_vert == corner.second->get_uv_vertex(1)->vertex) {
-          return primitive;
+          return primitive_i;
         }
       }
     }
   }
-  return nullptr;
+  return -1;
 }
 
 static void add_uv_primitive_fill(UVIsland &island,
                                   UVVertex &uv_vertex1,
                                   UVVertex &uv_vertex2,
                                   UVVertex &uv_vertex3,
-                                  MeshPrimitive &fill_primitive)
+                                  const int fill_primitive_i)
 {
-  UVPrimitive uv_primitive(&fill_primitive);
+  UVPrimitive uv_primitive(fill_primitive_i);
   UVEdge edge_template;
   edge_template.vertices[0] = &uv_vertex1;
   edge_template.vertices[1] = &uv_vertex2;
@@ -732,13 +745,16 @@ static void add_uv_primitive_fill(UVIsland &island,
   island.uv_primitives.append(uv_primitive);
 }
 
-static void extend_at_vert(UVIsland &island, UVBorderCorner &corner, float min_uv_distance)
+static void extend_at_vert(const MeshData &mesh_data,
+                           UVIsland &island,
+                           UVBorderCorner &corner,
+                           float min_uv_distance)
 {
   int border_index = corner.first->border_index;
   UVBorder &border = island.borders[border_index];
 
   UVVertex *uv_vertex = corner.second->get_uv_vertex(0);
-  Fan fan(*(uv_vertex->vertex));
+  Fan fan(mesh_data, uv_vertex->vertex);
   if (!fan.flags.full) {
     return;
   }
@@ -751,30 +767,32 @@ static void extend_at_vert(UVIsland &island, UVBorderCorner &corner, float min_u
   int num_to_add = fan.count_num_to_add();
 
   if (num_to_add == 0) {
-    MeshPrimitive *fill_primitive_1 = corner.second->uv_primitive->primitive;
-    MeshPrimitive *fill_primitive_2 = corner.first->uv_primitive->primitive;
+    int fill_primitive_1_i = corner.second->uv_primitive->primitive_i;
+    int fill_primitive_2_i = corner.first->uv_primitive->primitive_i;
 
-    MeshPrimitive *fill_primitive = find_fill_border(corner);
+    const int fill_primitive_i = find_fill_border(mesh_data, corner);
     // Although the fill_primitive can fill the missing segment it could lead to a squashed
     // triangle when the corner angle is near 180 degrees. In order to fix this we will
     // always add two segments both using the found fill primitive.
-    if (fill_primitive) {
-      fill_primitive_1 = fill_primitive;
-      fill_primitive_2 = fill_primitive;
+    if (fill_primitive_i != -1) {
+      fill_primitive_1_i = fill_primitive_i;
+      fill_primitive_2_i = fill_primitive_i;
     }
 
     float2 center_uv = corner.uv(0.5f, min_uv_distance);
-    add_uv_primitive_shared_uv_edge(island,
+    add_uv_primitive_shared_uv_edge(mesh_data,
+                                    island,
                                     corner.first->get_uv_vertex(1),
                                     corner.first->get_uv_vertex(0),
                                     center_uv,
-                                    fill_primitive_1);
+                                    fill_primitive_1_i);
     UVPrimitive &new_prim_1 = island.uv_primitives.last();
-    add_uv_primitive_shared_uv_edge(island,
+    add_uv_primitive_shared_uv_edge(mesh_data,
+                                    island,
                                     corner.second->get_uv_vertex(0),
                                     corner.second->get_uv_vertex(1),
                                     center_uv,
-                                    fill_primitive_2);
+                                    fill_primitive_2_i);
     UVPrimitive &new_prim_2 = island.uv_primitives.last();
 
     /* Update border after adding the new geometry. */
@@ -800,8 +818,7 @@ static void extend_at_vert(UVIsland &island, UVBorderCorner &corner, float min_u
 
     for (int i = 0; i < num_to_add; i++) {
       float2 old_uv = current_edge->get_other_uv_vertex(uv_vertex->vertex)->uv;
-      MeshVertex *shared_edge_vertex =
-          current_edge->get_other_uv_vertex(uv_vertex->vertex)->vertex;
+      int shared_edge_vertex = current_edge->get_other_uv_vertex(uv_vertex->vertex)->vertex;
 
       float factor = (i + 1.0f) / (num_to_add + 1.0f);
       float2 new_uv = corner.uv(factor, min_uv_distance);
@@ -813,15 +830,17 @@ static void extend_at_vert(UVIsland &island, UVBorderCorner &corner, float min_u
         }
 
         // Find primitive that shares the current edge and the segment edge.
-        MeshPrimitive *fill_primitive = find_fill_border(
-            *uv_vertex->vertex,
-            *shared_edge_vertex,
-            *segment.primitive->vertices[segment.vert_order[1]].vertex);
-        if (fill_primitive == nullptr) {
+        const int fill_primitive_i = find_fill_border(
+            mesh_data,
+            uv_vertex->vertex,
+            shared_edge_vertex,
+            segment.primitive->vertices[segment.vert_order[1]].vertex);
+        if (fill_primitive_i == -1) {
           continue;
         }
-        MeshVertex *other_prim_vertex =
-            fill_primitive->get_other_uv_vertex(uv_vertex->vertex, shared_edge_vertex)->vertex;
+        const MeshPrimitive &fill_primitive = mesh_data.primitives[fill_primitive_i];
+        const int other_prim_vertex = fill_primitive.get_other_uv_vertex(uv_vertex->vertex,
+                                                                         shared_edge_vertex);
 
         UVVertex uv_vertex_template;
         uv_vertex_template.vertex = uv_vertex->vertex;
@@ -835,7 +854,7 @@ static void extend_at_vert(UVIsland &island, UVBorderCorner &corner, float min_u
         UVVertex *vertex_3_ptr = island.lookup_or_create(uv_vertex_template);
 
         add_uv_primitive_fill(
-            island, *vertex_1_ptr, *vertex_2_ptr, *vertex_3_ptr, *fill_primitive);
+            island, *vertex_1_ptr, *vertex_2_ptr, *vertex_3_ptr, fill_primitive_i);
 
         segment.flags.found = true;
 
@@ -851,13 +870,15 @@ static void extend_at_vert(UVIsland &island, UVBorderCorner &corner, float min_u
     {
       /* Add final segment. */
       float2 old_uv = current_edge->get_other_uv_vertex(uv_vertex->vertex)->uv;
-      MeshVertex *shared_edge_vertex =
-          current_edge->get_other_uv_vertex(uv_vertex->vertex)->vertex;
-      MeshPrimitive *fill_primitive = find_fill_border(
-          *uv_vertex->vertex, *shared_edge_vertex, *corner.second->get_uv_vertex(1)->vertex);
-      if (fill_primitive) {
-        MeshVertex *other_prim_vertex =
-            fill_primitive->get_other_uv_vertex(uv_vertex->vertex, shared_edge_vertex)->vertex;
+      int shared_edge_vertex = current_edge->get_other_uv_vertex(uv_vertex->vertex)->vertex;
+      const int fill_primitive_i = find_fill_border(mesh_data,
+                                                    uv_vertex->vertex,
+                                                    shared_edge_vertex,
+                                                    corner.second->get_uv_vertex(1)->vertex);
+      if (fill_primitive_i != -1) {
+        const MeshPrimitive &fill_primitive = mesh_data.primitives[fill_primitive_i];
+        const int other_prim_vertex = fill_primitive.get_other_uv_vertex(uv_vertex->vertex,
+                                                                         shared_edge_vertex);
 
         UVVertex uv_vertex_template;
         uv_vertex_template.vertex = uv_vertex->vertex;
@@ -870,7 +891,7 @@ static void extend_at_vert(UVIsland &island, UVBorderCorner &corner, float min_u
         uv_vertex_template.uv = corner.second->get_uv_vertex(1)->uv;
         UVVertex *vertex_3_ptr = island.lookup_or_create(uv_vertex_template);
         add_uv_primitive_fill(
-            island, *vertex_1_ptr, *vertex_2_ptr, *vertex_3_ptr, *fill_primitive);
+            island, *vertex_1_ptr, *vertex_2_ptr, *vertex_3_ptr, fill_primitive_i);
 
         UVPrimitive &new_prim = island.uv_primitives.last();
         UVBorderEdge new_border(new_prim.get_uv_edge(shared_edge_vertex, other_prim_vertex),
@@ -914,7 +935,9 @@ static void reset_extendability_flags(UVIsland &island)
   }
 }
 
-void UVIsland::extend_border(const UVIslandsMask &mask, const short island_index)
+void UVIsland::extend_border(const MeshData &mesh_data,
+                             const UVIslandsMask &mask,
+                             const short island_index)
 {
   // Find sharpest corner that still inside the island mask and can be extended.
   // exit when no corner could be found.
@@ -936,7 +959,8 @@ void UVIsland::extend_border(const UVIslandsMask &mask, const short island_index
     /* When outside the mask, the uv should not be considered for extension. */
     const UVIslandsMask::Tile *tile = mask.find_tile(uv_vertex->uv);
     if (tile && tile->is_masked(island_index, uv_vertex->uv)) {
-      extend_at_vert(*this, *extension_corner, tile->get_pixel_size_in_uv_space() * 2.0f);
+      extend_at_vert(
+          mesh_data, *this, *extension_corner, tile->get_pixel_size_in_uv_space() * 2.0f);
     }
     /* Mark that the vert is extended. Unable to extend twice. */
     uv_vertex->flags.is_extended = true;
@@ -1075,7 +1099,7 @@ float2 UVBorderCorner::uv(float factor, float min_uv_distance)
 /** \name UVPrimitive
  * \{ */
 
-UVPrimitive::UVPrimitive(MeshPrimitive *primitive) : primitive(primitive)
+UVPrimitive::UVPrimitive(const int primitive_i) : primitive_i(primitive_i)
 {
 }
 
@@ -1122,9 +1146,11 @@ bool UVPrimitive::has_shared_edge(const MeshPrimitive &primitive) const
 /**
  * Get the UVVertex in the order that the verts are ordered in the MeshPrimitive.
  */
-const UVVertex *UVPrimitive::get_uv_vertex(const uint8_t mesh_vert_index) const
+const UVVertex *UVPrimitive::get_uv_vertex(const MeshData &mesh_data,
+                                           const uint8_t mesh_vert_index) const
 {
-  const MeshVertex *mesh_vertex = primitive->vertices[mesh_vert_index].vertex;
+  const MeshPrimitive &primitive = mesh_data.primitives[this->primitive_i];
+  const int mesh_vertex = primitive.vertices[mesh_vert_index].vertex;
   for (const UVEdge *uv_edge : edges) {
     for (const UVVertex *uv_vert : uv_edge->vertices) {
       if (uv_vert->vertex == mesh_vertex) {
@@ -1153,11 +1179,11 @@ UVEdge *UVPrimitive::get_uv_edge(const float2 uv1, const float2 uv2) const
   return nullptr;
 }
 
-UVEdge *UVPrimitive::get_uv_edge(const MeshVertex *v1, const MeshVertex *v2) const
+UVEdge *UVPrimitive::get_uv_edge(const int v1, const int v2) const
 {
   for (UVEdge *uv_edge : edges) {
-    const MeshVertex *e1 = uv_edge->vertices[0]->vertex;
-    const MeshVertex *e2 = uv_edge->vertices[1]->vertex;
+    const int e1 = uv_edge->vertices[0]->vertex;
+    const int e2 = uv_edge->vertices[1]->vertex;
     if ((e1 == v1 && e2 == v2) || (e1 == v2 && e2 == v1)) {
       return uv_edge;
     }
@@ -1245,16 +1271,16 @@ float UVBorderEdge::length() const
 /** \name UVIslands
  * \{ */
 
-UVIslands::UVIslands(MeshData &mesh_data)
+UVIslands::UVIslands(const MeshData &mesh_data)
 {
   islands.reserve(mesh_data.uv_island_len);
 
   for (int64_t uv_island_id = 0; uv_island_id < mesh_data.uv_island_len; uv_island_id++) {
     islands.append_as(UVIsland());
     UVIsland *uv_island = &islands.last();
-    for (MeshPrimitive &primitive : mesh_data.primitives) {
-      if (primitive.uv_island_id == uv_island_id) {
-        add_primitive(*uv_island, primitive);
+    for (const int primitive_i : mesh_data.primitives.index_range()) {
+      if (mesh_data.uv_island_ids[primitive_i] == uv_island_id) {
+        add_primitive(mesh_data, *uv_island, primitive_i);
       }
     }
   }
@@ -1267,11 +1293,11 @@ void UVIslands::extract_borders()
   }
 }
 
-void UVIslands::extend_borders(const UVIslandsMask &islands_mask)
+void UVIslands::extend_borders(const MeshData &mesh_data, const UVIslandsMask &islands_mask)
 {
   ushort index = 0;
   for (UVIsland &island : islands) {
-    island.extend_border(islands_mask, index++);
+    island.extend_border(mesh_data, islands_mask, index++);
   }
 }
 
@@ -1306,15 +1332,16 @@ float UVIslandsMask::Tile::get_pixel_size_in_uv_space() const
   return min_ff(1.0f / tile_resolution.x, 1.0f / tile_resolution.y);
 }
 
-static void add_uv_island(UVIslandsMask::Tile &tile,
+static void add_uv_island(const MeshData &mesh_data,
+                          UVIslandsMask::Tile &tile,
                           const UVIsland &uv_island,
                           int16_t island_index)
 {
   for (const VectorList<UVPrimitive>::UsedVector &uv_primitives : uv_island.uv_primitives)
     for (const UVPrimitive &uv_primitive : uv_primitives) {
-      const MeshPrimitive *mesh_primitive = uv_primitive.primitive;
+      const MeshPrimitive &mesh_primitive = mesh_data.primitives[uv_primitive.primitive_i];
 
-      rctf uv_bounds = mesh_primitive->uv_bounds();
+      rctf uv_bounds = mesh_primitive.uv_bounds();
       rcti buffer_bounds;
       buffer_bounds.xmin = max_ii(
           floor((uv_bounds.xmin - tile.udim_offset.x) * tile.mask_resolution.x), 0);
@@ -1331,9 +1358,9 @@ static void add_uv_island(UVIslandsMask::Tile &tile,
         for (int x = buffer_bounds.xmin; x < buffer_bounds.xmax + 1; x++) {
           float2 uv(float(x) / tile.mask_resolution.x, float(y) / tile.mask_resolution.y);
           float3 weights;
-          barycentric_weights_v2(mesh_primitive->vertices[0].uv,
-                                 mesh_primitive->vertices[1].uv,
-                                 mesh_primitive->vertices[2].uv,
+          barycentric_weights_v2(mesh_primitive.vertices[0].uv,
+                                 mesh_primitive.vertices[1].uv,
+                                 mesh_primitive.vertices[2].uv,
                                  uv + tile.udim_offset,
                                  weights);
           if (!barycentric_inside_triangle_v2(weights)) {
@@ -1347,11 +1374,11 @@ static void add_uv_island(UVIslandsMask::Tile &tile,
     }
 }
 
-void UVIslandsMask::add(const UVIslands &uv_islands)
+void UVIslandsMask::add(const MeshData &mesh_data, const UVIslands &uv_islands)
 {
   for (Tile &tile : tiles) {
-    for (int index = 0; index < uv_islands.islands.size(); index++) {
-      add_uv_island(tile, uv_islands.islands[index], index);
+    for (const int i : uv_islands.islands.index_range()) {
+      add_uv_island(mesh_data, tile, uv_islands.islands[i], i);
     }
   }
 }
diff --git a/source/blender/blenkernel/intern/pbvh_uv_islands.hh b/source/blender/blenkernel/intern/pbvh_uv_islands.hh
index 65f640d1c02..39a303b97f2 100644
--- a/source/blender/blenkernel/intern/pbvh_uv_islands.hh
+++ b/source/blender/blenkernel/intern/pbvh_uv_islands.hh
@@ -31,6 +31,7 @@
 #include "BLI_rect.h"
 #include "BLI_vector.hh"
 #include "BLI_vector_list.hh"
+#include "BLI_virtual_array.hh"
 
 #include "DNA_meshdata_types.h"
 
@@ -46,44 +47,73 @@ struct UVPrimitive;
 struct UVPrimitiveEdge;
 struct UVVertex;
 
-struct MeshVertex {
-  int64_t v;
-  Vector<MeshEdge *> edges;
-};
-
 struct MeshUVVert {
-  MeshVertex *vertex;
+  int vertex;
   float2 uv;
   int64_t loop;
 };
 
 struct MeshEdge {
-  MeshVertex *vert1;
-  MeshVertex *vert2;
-  Vector<MeshPrimitive *> primitives;
+  int vert1;
+  int vert2;
+};
+
+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];
+  }
 };
 
 /** Represents a triangle in 3d space (MLoopTri). */
 struct MeshPrimitive {
   int64_t index;
   int64_t poly;
-  Vector<MeshEdge *, 3> edges;
+  Vector<int, 3> edges;
   Vector<MeshUVVert, 3> vertices;
 
-  /**
-   * UV island this primitive belongs to. This is used to speed up the initial uv island
-   * extraction and should not be used afterwards.
-   */
-  int64_t uv_island_id;
-
   /** Get the vertex that is not given. Both given vertices must be part of the MeshPrimitive. */
-  MeshUVVert *get_other_uv_vertex(const MeshVertex *v1, const MeshVertex *v2);
+  int get_other_uv_vertex(const int v1, const int v2) const;
 
   /** Get the UV bounds for this MeshPrimitive. */
   rctf uv_bounds() const;
 
   /** Is the given MeshPrimitive sharing an edge. */
-  bool has_shared_uv_edge(const MeshPrimitive *other) const;
+  bool has_shared_uv_edge(const MeshPrimitive &other) const;
 };
 
 /**
@@ -97,9 +127,17 @@ struct MeshData {
   const Span<MLoop> loops;
   const Span<MLoopUV> mloopuv;
 
-  Vector<MeshPrimitive> primitives;
+  VertToEdgeMap vert_to_edge_map;
+
   Vector<MeshEdge> edges;
-  Vector<MeshVertex> vertices;
+  EdgeToPrimitiveMap edge_to_primitive_map;
+
+  Vector<MeshPrimitive> primitives;
+  /**
+   * UV island each primitive belongs to. This is used to speed up the initial uv island
+   * extraction and should not be used afterwards.
+   */
+  Array<int> uv_island_ids;
   /** Total number of found uv islands. */
   int64_t uv_island_len;
 
@@ -111,7 +149,7 @@ struct MeshData {
 };
 
 struct UVVertex {
-  MeshVertex *vertex;
+  int vertex;
   /* Position in uv space. */
   float2 uv;
 
@@ -131,7 +169,7 @@ struct UVEdge {
   std::array<UVVertex *, 2> vertices;
   Vector<UVPrimitive *, 2> uv_primitives;
 
-  UVVertex *get_other_uv_vertex(const MeshVertex *vertex);
+  UVVertex *get_other_uv_vertex(const int vertex_index);
   bool has_shared_edge(const MeshUVVert &v1, const MeshUVVert &v2) const;
   bool has_shared_edge(const UVEdge &other) const;
   bool has_same_vertices(const MeshEdge &edge) const;
@@ -139,7 +177,7 @@ struct UVEdge {
 
  private:
   bool has_shared_edge(const UVVertex &v1, const UVVertex &v2) const;
-  bool has_same_vertices(const MeshVertex &vert1, const MeshVertex &vert2) const;
+  bool has_same_vertices(const int v1, const int v2) const;
   bool has_same_uv_vertices(const UVEdge &other) const;
 };
 
@@ -147,10 +185,10 @@ struct UVPrimitive {
   /**
    * Index of the primitive in the original mesh.
    */
-  MeshPrimitive *primitive;
+  const int primitive_i;
   Vector<UVEdge *, 3> edges;
 
-  explicit UVPrimitive(MeshPrimitive *primitive);
+  explicit UVPrimitive(const int primitive_i);
 
   Vector<std::pair<UVEdge *, UVEdge *>> shared_edges(UVPrimitive &other);
   bool has_shared_edge(const UVPrimitive &other) const;
@@ -159,14 +197,14 @@ struct UVPrimitive {
   /**
    * Get the UVVertex in the order that the verts are ordered in the MeshPrimitive.
    */
-  const UVVertex *get_uv_vertex(const uint8_t mesh_vert_index) const;
+  const UVVertex *get_uv_vertex(const MeshData &mesh_data, const uint8_t mesh_vert_index) const;
 
   /**
    * Get the UVEdge that share the given uv coordinates.
    * Will assert when no UVEdge found.
    */
   UVEdge *get_uv_edge(const float2 uv1, const float2 uv2) const;
-  UVEdge *get_uv_edge(const MeshVertex *v1, const MeshVertex *v2) const;
+  UVEdge *get_uv_edge(const int v1, const int v2) const;
 
   const bool contains_uv_vertex(const UVVertex *uv_vertex) const;
   const UVVertex *get_other_uv_vertex(const UVVertex *v1, const UVVertex *v2) const;
@@ -266,7 +304,9 @@ struct UVIsland {
   /** Initialize the border attribute. */
   void extract_borders();
   /** Iterative extend border to fit the mask. */
-  void extend_border(const UVIslandsMask &mask, const short island_index);
+  void extend_border(const MeshData &mesh_data,
+                     const UVIslandsMask &mask,
+                     const short island_index);
 
  private:
   void append(const UVPrimitive &primitive);
@@ -280,10 +320,10 @@ struct UVIsland {
 struct UVIslands {
   Vector<UVIsland> islands;
 
-  explicit UVIslands(MeshData &mesh_data);
+  explicit UVIslands(const MeshData &mesh_data);
 
   void extract_borders();
-  void extend_borders(const UVIslandsMask &islands_mask);
+  void extend_borders(const MeshData &mesh_data, const UVIslandsMask &islands_mask);
 };
 
 /** Mask to find the index of the UVIsland for a given UV coordinate. */
@@ -324,7 +364,7 @@ struct UVIslandsMask {
    * Add the given UVIslands to the mask. Tiles should be added beforehand using the 'add_tile'
    * method.
    */
-  void add(const UVIslands &islands);
+  void add(const MeshData &mesh_data, const UVIslands &islands);
 
   void dilate(int max_iterations);
 };