From e6e9f1ac5a2dae42dc523784b03395a50671afaa Mon Sep 17 00:00:00 2001
From: Chris Blackbourn <chrisbblend@gmail.com>
Date: Thu, 16 Jun 2022 09:51:48 +1200
Subject: Fix T98239: During UV Unwrap, create unique indices for each pinned
 UV

Originally reported in T75007.

Differential Revision: https://developer.blender.org/D15199
---
 source/blender/geometry/GEO_uv_parametrizer.h    |  5 ++
 source/blender/geometry/intern/uv_parametrizer.c | 84 +++++++++++++++++++++++-
 2 files changed, 87 insertions(+), 2 deletions(-)

(limited to 'source/blender/geometry')

diff --git a/source/blender/geometry/GEO_uv_parametrizer.h b/source/blender/geometry/GEO_uv_parametrizer.h
index 7fe60a3a855..2181f95945e 100644
--- a/source/blender/geometry/GEO_uv_parametrizer.h
+++ b/source/blender/geometry/GEO_uv_parametrizer.h
@@ -14,6 +14,7 @@ extern "C" {
 
 typedef struct ParamHandle ParamHandle; /* Handle to an array of charts. */
 typedef intptr_t ParamKey;              /* Key (hash) for identifying verts and faces. */
+#define PARAM_KEY_MAX INTPTR_MAX
 
 /* -------------------------------------------------------------------- */
 /** \name Chart Construction:
@@ -34,6 +35,10 @@ ParamHandle *GEO_uv_parametrizer_construct_begin(void);
 
 void GEO_uv_parametrizer_aspect_ratio(ParamHandle *handle, float aspx, float aspy);
 
+void GEO_uv_prepare_pin_index(ParamHandle *handle, const int bmvertindex, const float uv[2]);
+
+ParamKey GEO_uv_find_pin_index(ParamHandle *handle, const int bmvertindex, const float uv[2]);
+
 void GEO_uv_parametrizer_face_add(ParamHandle *handle,
                                   const ParamKey key,
                                   const int nverts,
diff --git a/source/blender/geometry/intern/uv_parametrizer.c b/source/blender/geometry/intern/uv_parametrizer.c
index af3bcc3bdec..c0b9907ea81 100644
--- a/source/blender/geometry/intern/uv_parametrizer.c
+++ b/source/blender/geometry/intern/uv_parametrizer.c
@@ -8,6 +8,7 @@
 
 #include "BLI_boxpack_2d.h"
 #include "BLI_convexhull_2d.h"
+#include "BLI_ghash.h"
 #include "BLI_heap.h"
 #include "BLI_math.h"
 #include "BLI_memarena.h"
@@ -190,6 +191,9 @@ typedef struct ParamHandle {
   PHash *hash_edges;
   PHash *hash_faces;
 
+  struct GHash *pin_hash;
+  int unique_pin_count;
+
   PChart **charts;
   int ncharts;
 
@@ -3817,8 +3821,11 @@ void GEO_uv_parametrizer_delete(ParamHandle *phandle)
     p_chart_delete(phandle->charts[i]);
   }
 
-  if (phandle->charts) {
-    MEM_freeN(phandle->charts);
+  MEM_SAFE_FREE(phandle->charts);
+
+  if (phandle->pin_hash) {
+    BLI_ghash_free(phandle->pin_hash, NULL, NULL);
+    phandle->pin_hash = NULL;
   }
 
   if (phandle->construction_chart) {
@@ -3835,6 +3842,79 @@ void GEO_uv_parametrizer_delete(ParamHandle *phandle)
   MEM_freeN(phandle);
 }
 
+typedef struct GeoUVPinIndex {
+  struct GeoUVPinIndex *next;
+  float uv[2];
+  ParamKey reindex;
+} GeoUVPinIndex;
+
+/* Find a (mostly) unique ParamKey given a BMVert index and UV co-ordinates.
+ * For each unique pinned UVs, return a unique ParamKey, starting with
+ *  a very large number, and decreasing steadily from there.
+ * For non-pinned UVs which share a BMVert with a pinned UV,
+ *  return the index corresponding to the closest pinned UV.
+ * For everything else, just return the BMVert index.
+ * Note that ParamKeys will eventually be hashed, so they don't need to be contiguous.
+ */
+ParamKey GEO_uv_find_pin_index(ParamHandle *handle, const int bmvertindex, const float uv[2])
+{
+  if (!handle->pin_hash) {
+    return bmvertindex; /* No verts pinned. */
+  }
+
+  GeoUVPinIndex *pinuvlist = BLI_ghash_lookup(handle->pin_hash, bmvertindex);
+  if (!pinuvlist) {
+    return bmvertindex; /* Vert not pinned. */
+  }
+
+  /* At least one of the UVs associated with bmvertindex is pinned. Find the best one. */
+  float bestdistsquared = len_squared_v2v2(pinuvlist->uv, uv);
+  ParamKey bestkey = pinuvlist->reindex;
+  pinuvlist = pinuvlist->next;
+  while (pinuvlist) {
+    const float distsquared = len_squared_v2v2(pinuvlist->uv, uv);
+    if (bestdistsquared > distsquared) {
+      bestdistsquared = distsquared;
+      bestkey = pinuvlist->reindex;
+    }
+    pinuvlist = pinuvlist->next;
+  }
+  return bestkey;
+}
+
+static GeoUVPinIndex *new_geo_uv_pinindex(ParamHandle *handle, const float uv[2])
+{
+  GeoUVPinIndex *pinuv = BLI_memarena_alloc(handle->arena, sizeof(*pinuv));
+  pinuv->next = NULL;
+  copy_v2_v2(pinuv->uv, uv);
+  pinuv->reindex = PARAM_KEY_MAX - (handle->unique_pin_count++);
+  return pinuv;
+}
+
+void GEO_uv_prepare_pin_index(ParamHandle *handle, const int bmvertindex, const float uv[2])
+{
+  if (!handle->pin_hash) {
+    handle->pin_hash = BLI_ghash_int_new("uv pin reindex");
+  }
+
+  GeoUVPinIndex *pinuvlist = BLI_ghash_lookup(handle->pin_hash, bmvertindex);
+  if (!pinuvlist) {
+    BLI_ghash_insert(handle->pin_hash, bmvertindex, new_geo_uv_pinindex(handle, uv));
+    return;
+  }
+
+  while (true) {
+    if (equals_v2v2(pinuvlist->uv, uv)) {
+      return;
+    }
+    if (!pinuvlist->next) {
+      pinuvlist->next = new_geo_uv_pinindex(handle, uv);
+      return;
+    }
+    pinuvlist = pinuvlist->next;
+  }
+}
+
 static void p_add_ngon(ParamHandle *handle,
                        const ParamKey key,
                        const int nverts,
-- 
cgit v1.2.3