[Bf-blender-cvs] [1e2f4fac009] temp-T97352-3d-texturing-seam-bleeding-b2: Use KDTree for uvvertex lookup (currently slowing down due to rebalancing overhead.

[Jeroen Bakker]

Commit: 1e2f4fac00982ba967b0a542a3389f8f4c63c478
Author: Jeroen Bakker
Date:   Tue Jul 5 12:10:35 2022 +0200
Branches: temp-T97352-3d-texturing-seam-bleeding-b2
https://developer.blender.org/rB1e2f4fac00982ba967b0a542a3389f8f4c63c478

Use KDTree for uvvertex lookup (currently slowing down due to rebalancing overhead.

===================================================================

M	source/blender/blenkernel/BKE_uv_islands.hh

===================================================================

diff --git a/source/blender/blenkernel/BKE_uv_islands.hh b/source/blender/blenkernel/BKE_uv_islands.hh
index c7cbcff8d8e..27172e7ed40 100644
--- a/source/blender/blenkernel/BKE_uv_islands.hh
+++ b/source/blender/blenkernel/BKE_uv_islands.hh
@@ -644,12 +644,30 @@ struct UVIsland {
    * be completely encapsulated by another one.
    */
   Vector<UVBorder> borders;
+  KDTree_2d *uv_vertex_lookup;
 
   UVIsland()
   {
     uv_vertices.reserve(100000);
     uv_edges.reserve(100000);
     uv_primitives.reserve(100000);
+    uv_vertex_lookup = BLI_kdtree_2d_new(uv_vertices.capacity());
+    BLI_kdtree_2d_balance(uv_vertex_lookup);
+  }
+
+  UVIsland(UVIsland &&other)
+  {
+    uv_vertices = std::move(other.uv_vertices);
+    uv_edges = std::move(other.uv_edges);
+    uv_primitives = std::move(other.uv_primitives);
+    borders = std::move(other.borders);
+    uv_vertex_lookup = other.uv_vertex_lookup;
+    other.uv_vertex_lookup = nullptr;
+  }
+
+  ~UVIsland()
+  {
+    BLI_kdtree_2d_free(uv_vertex_lookup);
   }
 
   UVPrimitive *add_primitive(MeshPrimitive &primitive)
@@ -673,12 +691,34 @@ struct UVIsland {
 
   UVVertex *lookup_or_create(const UVVertex &vertex)
   {
-    for (UVVertex &uv_vertex : uv_vertices) {
-      if (uv_vertex.uv == vertex.uv && uv_vertex.vertex == vertex.vertex) {
-        return &uv_vertex;
-      }
+    struct CallbackData {
+      UVVertex *found_vertex;
+      const UVVertex &vertex;
+      Vector<UVVertex> &uv_vertices;
+    } callback_data = {nullptr, vertex, uv_vertices};
+    BLI_kdtree_2d_range_search_cb(
+        uv_vertex_lookup,
+        vertex.uv,
+        0.0001f,
+        [](void *user_data, int index, const float *UNUSED(co), float UNUSED(dist_sq)) {
+          CallbackData *data = static_cast<CallbackData *>(user_data);
+          UVVertex &vertex = data->uv_vertices[index];
+          if (vertex.uv == data->vertex.uv && vertex.vertex == data->vertex.vertex) {
+            data->found_vertex = &vertex;
+            return false;
+          }
+
+          return true;
+        },
+        static_cast<void *>(&callback_data));
+
+    if (callback_data.found_vertex != nullptr) {
+      return callback_data.found_vertex;
     }
 
+    int64_t vert_index = uv_vertices.size();
+    BLI_kdtree_2d_insert(uv_vertex_lookup, vert_index, vertex.uv);
+    BLI_kdtree_2d_balance(uv_vertex_lookup);
     uv_vertices.append(vertex);
     UVVertex *result = &uv_vertices.last();
     result->uv_edges.clear();
@@ -819,7 +859,7 @@ struct UVIslands {
     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(UVIsland());
+      islands.append_as(UVIsland());
       UVIsland *uv_island = &islands.last();
       for (MeshPrimitive &primitive : mesh_data.primitives) {
         if (primitive.uv_island_id == uv_island_id) {