Curves: use uv coordinates to attach curves to mesh

This implements the new way to attach curves to a mesh surface using
a uv map (based on the recent discussion in T95776).

The curves data block now not only stores a reference to the surface object
but also a name of a uv map on that object. Having a uv map is optional
for most operations, but it will be required later for animation (when the
curves are supposed to be deformed based on deformation of the surface).

The "Empty Hair" operator in the Add menu sets the uv map name automatically
if possible. It's possible to start working without a uv map and to attach the
curves to a uv map later on. It's also possible to reattach the curves to a new
uv map using the "Curves > Snap to Nearest Surface" operator in curves sculpt
mode.

Note, the implementation to do the reverse lookup from uv to a position on the
surface is trivial and inefficient now. A more efficient data structure will be
implemented separately soon.

Differential Revision: https://developer.blender.org/D15125

11 files changed, 203 insertions, 83 deletions

diff --git a/source/blender/blenkernel/BKE_curves.hh b/source/blender/blenkernel/BKE_curves.hh
index 168b17bad30..dc67f1e7403 100644
--- a/source/blender/blenkernel/BKE_curves.hh
+++ b/source/blender/blenkernel/BKE_curves.hh
@@ -264,22 +264,10 @@ class CurvesGeometry : public ::CurvesGeometry {
   MutableSpan<float> nurbs_weights_for_write();
 
   /**
-   * The index of a triangle (#MLoopTri) that a curve is attached to.
-   * The index is -1, if the curve is not attached.
+   * UV coordinate for each curve that encodes where the curve is attached to the surface mesh.
    */
-  VArray<int> surface_triangle_indices() const;
-  MutableSpan<int> surface_triangle_indices_for_write();
-
-  /**
-   * Barycentric coordinates of the attachment point within a triangle.
-   * Only the first two coordinates are stored. The third coordinate can be derived because the sum
-   * of the three coordinates is 1.
-   *
-   * When the triangle index is -1, this coordinate should be ignored.
-   * The span can be empty, when all triangle indices are -1.
-   */
-  Span<float2> surface_triangle_coords() const;
-  MutableSpan<float2> surface_triangle_coords_for_write();
+  Span<float2> surface_uv_coords() const;
+  MutableSpan<float2> surface_uv_coords_for_write();
 
   VArray<float> selection_point_float() const;
   MutableSpan<float> selection_point_float_for_write();
diff --git a/source/blender/blenkernel/intern/curves_geometry.cc b/source/blender/blenkernel/intern/curves_geometry.cc
index c2e67d853c9..2fa31bd4100 100644
--- a/source/blender/blenkernel/intern/curves_geometry.cc
+++ b/source/blender/blenkernel/intern/curves_geometry.cc
@@ -35,10 +35,9 @@ static const std::string ATTR_HANDLE_POSITION_RIGHT = "handle_right";
 static const std::string ATTR_NURBS_ORDER = "nurbs_order";
 static const std::string ATTR_NURBS_WEIGHT = "nurbs_weight";
 static const std::string ATTR_NURBS_KNOTS_MODE = "knots_mode";
-static const std::string ATTR_SURFACE_TRIANGLE_INDEX = "surface_triangle_index";
-static const std::string ATTR_SURFACE_TRIANGLE_COORDINATE = "surface_triangle_coordinate";
 static const std::string ATTR_SELECTION_POINT_FLOAT = ".selection_point_float";
 static const std::string ATTR_SELECTION_CURVE_FLOAT = ".selection_curve_float";
+static const std::string ATTR_SURFACE_UV_COORDINATE = "surface_uv_coordinate";
 
 /* -------------------------------------------------------------------- */
 /** \name Constructors/Destructor
@@ -419,24 +418,14 @@ MutableSpan<int8_t> CurvesGeometry::nurbs_knots_modes_for_write()
   return get_mutable_attribute<int8_t>(*this, ATTR_DOMAIN_CURVE, ATTR_NURBS_KNOTS_MODE, 0);
 }
 
-VArray<int> CurvesGeometry::surface_triangle_indices() const
+Span<float2> CurvesGeometry::surface_uv_coords() const
 {
-  return get_varray_attribute<int>(*this, ATTR_DOMAIN_CURVE, ATTR_SURFACE_TRIANGLE_INDEX, -1);
+  return get_span_attribute<float2>(*this, ATTR_DOMAIN_CURVE, ATTR_SURFACE_UV_COORDINATE);
 }
 
-MutableSpan<int> CurvesGeometry::surface_triangle_indices_for_write()
+MutableSpan<float2> CurvesGeometry::surface_uv_coords_for_write()
 {
-  return get_mutable_attribute<int>(*this, ATTR_DOMAIN_CURVE, ATTR_SURFACE_TRIANGLE_INDEX, -1);
-}
-
-Span<float2> CurvesGeometry::surface_triangle_coords() const
-{
-  return get_span_attribute<float2>(*this, ATTR_DOMAIN_CURVE, ATTR_SURFACE_TRIANGLE_COORDINATE);
-}
-
-MutableSpan<float2> CurvesGeometry::surface_triangle_coords_for_write()
-{
-  return get_mutable_attribute<float2>(*this, ATTR_DOMAIN_CURVE, ATTR_SURFACE_TRIANGLE_COORDINATE);
+  return get_mutable_attribute<float2>(*this, ATTR_DOMAIN_CURVE, ATTR_SURFACE_UV_COORDINATE);
 }
 
 VArray<float> CurvesGeometry::selection_point_float() const
diff --git a/source/blender/blenlib/BLI_virtual_array.hh b/source/blender/blenlib/BLI_virtual_array.hh
index ab4ca185ddb..0705d423f01 100644
--- a/source/blender/blenlib/BLI_virtual_array.hh
+++ b/source/blender/blenlib/BLI_virtual_array.hh
@@ -1138,6 +1138,8 @@ template<typename T> class VArray_Span final : public Span<T> {
   Array<T> owned_data_;
 
  public:
+  VArray_Span() = default;
+
   VArray_Span(VArray<T> varray) : Span<T>(), varray_(std::move(varray))
   {
     this->size_ = varray_.size();
diff --git a/source/blender/editors/curves/CMakeLists.txt b/source/blender/editors/curves/CMakeLists.txt
index a5d8390e7f2..3c31e8014ff 100644
--- a/source/blender/editors/curves/CMakeLists.txt
+++ b/source/blender/editors/curves/CMakeLists.txt
@@ -7,6 +7,7 @@ set(INC
   ../../blentranslation
   ../../depsgraph
   ../../functions
+  ../../geometry
   ../../makesdna
   ../../makesrna
   ../../windowmanager
diff --git a/source/blender/editors/curves/intern/curves_ops.cc b/source/blender/editors/curves/intern/curves_ops.cc
index 85214e1608d..54f0a0208fb 100644
--- a/source/blender/editors/curves/intern/curves_ops.cc
+++ b/source/blender/editors/curves/intern/curves_ops.cc
@@ -17,6 +17,7 @@
 
 #include "WM_api.h"
 
+#include "BKE_attribute_math.hh"
 #include "BKE_bvhutils.h"
 #include "BKE_context.h"
 #include "BKE_curves.hh"
@@ -45,6 +46,8 @@
 #include "RNA_enum_types.h"
 #include "RNA_prototypes.h"
 
+#include "GEO_reverse_uv_sampler.hh"
+
 /**
  * The code below uses a suffix naming convention to indicate the coordinate space:
  * `cu`: Local space of the curves object that is being edited.
@@ -184,25 +187,20 @@ static void try_convert_single_object(Object &curves_ob,
   }
   Mesh &surface_me = *static_cast<Mesh *>(surface_ob.data);
 
+  BVHTreeFromMesh surface_bvh;
+  BKE_bvhtree_from_mesh_get(&surface_bvh, &surface_me, BVHTREE_FROM_LOOPTRI, 2);
+  BLI_SCOPED_DEFER([&]() { free_bvhtree_from_mesh(&surface_bvh); });
+
   const Span<float3> positions_cu = curves.positions();
-  const VArray<int> looptri_indices = curves.surface_triangle_indices();
   const Span<MLoopTri> looptris{BKE_mesh_runtime_looptri_ensure(&surface_me),
                                 BKE_mesh_runtime_looptri_len(&surface_me)};
 
-  /* Find indices of curves that can be transferred to the old hair system. */
-  Vector<int> curves_indices_to_transfer;
-  for (const int curve_i : curves.curves_range()) {
-    const int looptri_i = looptri_indices[curve_i];
-    if (looptri_i >= 0 && looptri_i < looptris.size()) {
-      curves_indices_to_transfer.append(curve_i);
-    }
-    else {
-      *r_could_not_convert_some_curves = true;
-    }
+  if (looptris.is_empty()) {
+    *r_could_not_convert_some_curves = true;
   }
 
-  const int hairs_num = curves_indices_to_transfer.size();
-  if (hairs_num == 0) {
+  const int hair_num = curves.curves_num();
+  if (hair_num == 0) {
     return;
   }
 
@@ -228,8 +226,8 @@ static void try_convert_single_object(Object &curves_ob,
   psys_changed_type(&surface_ob, particle_system);
 
   MutableSpan<ParticleData> particles{
-      static_cast<ParticleData *>(MEM_calloc_arrayN(hairs_num, sizeof(ParticleData), __func__)),
-      hairs_num};
+      static_cast<ParticleData *>(MEM_calloc_arrayN(hair_num, sizeof(ParticleData), __func__)),
+      hair_num};
 
   /* The old hair system still uses #MFace, so make sure those are available on the mesh. */
   BKE_mesh_tessface_calc(&surface_me);
@@ -250,17 +248,23 @@ static void try_convert_single_object(Object &curves_ob,
   const float4x4 world_to_surface_mat = surface_to_world_mat.inverted();
   const float4x4 curves_to_surface_mat = world_to_surface_mat * curves_to_world_mat;
 
-  for (const int new_hair_i : curves_indices_to_transfer.index_range()) {
-    const int curve_i = curves_indices_to_transfer[new_hair_i];
+  for (const int new_hair_i : IndexRange(hair_num)) {
+    const int curve_i = new_hair_i;
     const IndexRange points = curves.points_for_curve(curve_i);
 
-    const int looptri_i = looptri_indices[curve_i];
-    const MLoopTri &looptri = looptris[looptri_i];
-    const int poly_i = looptri.poly;
-
     const float3 &root_pos_cu = positions_cu[points.first()];
     const float3 root_pos_su = curves_to_surface_mat * root_pos_cu;
 
+    BVHTreeNearest nearest;
+    nearest.dist_sq = FLT_MAX;
+    BLI_bvhtree_find_nearest(
+        surface_bvh.tree, root_pos_su, &nearest, surface_bvh.nearest_callback, &surface_bvh);
+    BLI_assert(nearest.index >= 0);
+
+    const int looptri_i = nearest.index;
+    const MLoopTri &looptri = looptris[looptri_i];
+    const int poly_i = looptri.poly;
+
     const int mface_i = find_mface_for_root_position(
         surface_me, poly_to_mface_map[poly_i], root_pos_su);
     const MFace &mface = surface_me.mface[mface_i];
@@ -520,7 +524,7 @@ static int snap_curves_to_surface_exec(bContext *C, wmOperator *op)
 {
   const AttachMode attach_mode = static_cast<AttachMode>(RNA_enum_get(op->ptr, "attach_mode"));
 
-  std::atomic<bool> found_invalid_looptri_index = false;
+  std::atomic<bool> found_invalid_uv = false;
 
   CTX_DATA_BEGIN (C, Object *, curves_ob, selected_objects) {
     if (curves_ob->type != OB_CURVES) {
@@ -537,9 +541,19 @@ static int snap_curves_to_surface_exec(bContext *C, wmOperator *op)
     }
     Mesh &surface_mesh = *static_cast<Mesh *>(surface_ob.data);
 
+    MeshComponent surface_mesh_component;
+    surface_mesh_component.replace(&surface_mesh, GeometryOwnershipType::ReadOnly);
+
+    VArray_Span<float2> surface_uv_map;
+    if (curves_id.surface_uv_map != nullptr) {
+      surface_uv_map = surface_mesh_component
+                           .attribute_try_get_for_read(
+                               curves_id.surface_uv_map, ATTR_DOMAIN_CORNER, CD_PROP_FLOAT2)
+                           .typed<float2>();
+    }
+
     MutableSpan<float3> positions_cu = curves.positions_for_write();
-    MutableSpan<int> surface_triangle_indices = curves.surface_triangle_indices_for_write();
-    MutableSpan<float2> surface_triangle_coords = curves.surface_triangle_coords_for_write();
+    MutableSpan<float2> surface_uv_coords = curves.surface_uv_coords_for_write();
 
     const Span<MLoopTri> surface_looptris = {BKE_mesh_runtime_looptri_ensure(&surface_mesh),
                                              BKE_mesh_runtime_looptri_len(&surface_mesh)};
@@ -585,36 +599,50 @@ static int snap_curves_to_surface_exec(bContext *C, wmOperator *op)
               pos_cu += pos_diff_cu;
             }
 
-            surface_triangle_indices[curve_i] = looptri_index;
-
-            const MLoopTri &looptri = surface_looptris[looptri_index];
-            const float3 &p0_su = surface_mesh.mvert[surface_mesh.mloop[looptri.tri[0]].v].co;
-            const float3 &p1_su = surface_mesh.mvert[surface_mesh.mloop[looptri.tri[1]].v].co;
-            const float3 &p2_su = surface_mesh.mvert[surface_mesh.mloop[looptri.tri[2]].v].co;
-            float3 bary_coords;
-            interp_weights_tri_v3(bary_coords, p0_su, p1_su, p2_su, new_first_point_pos_su);
-            surface_triangle_coords[curve_i] = bke::curves::encode_surface_bary_coord(bary_coords);
+            if (!surface_uv_map.is_empty()) {
+              const MLoopTri &looptri = surface_looptris[looptri_index];
+              const int corner0 = looptri.tri[0];
+              const int corner1 = looptri.tri[1];
+              const int corner2 = looptri.tri[2];
+              const float2 &uv0 = surface_uv_map[corner0];
+              const float2 &uv1 = surface_uv_map[corner1];
+              const float2 &uv2 = surface_uv_map[corner2];
+              const float3 &p0_su = surface_mesh.mvert[surface_mesh.mloop[corner0].v].co;
+              const float3 &p1_su = surface_mesh.mvert[surface_mesh.mloop[corner1].v].co;
+              const float3 &p2_su = surface_mesh.mvert[surface_mesh.mloop[corner2].v].co;
+              float3 bary_coords;
+              interp_weights_tri_v3(bary_coords, p0_su, p1_su, p2_su, new_first_point_pos_su);
+              const float2 uv = attribute_math::mix3(bary_coords, uv0, uv1, uv2);
+              surface_uv_coords[curve_i] = uv;
+            }
           }
         });
         break;
       }
       case AttachMode::Deform: {
+        if (!surface_uv_map.is_empty()) {
+          BKE_report(op->reports,
+                     RPT_ERROR,
+                     "Curves do not have attachment information that can be used for deformation");
+        }
+        using geometry::ReverseUVSampler;
+        ReverseUVSampler reverse_uv_sampler{surface_uv_map, surface_looptris};
+
         threading::parallel_for(curves.curves_range(), 256, [&](const IndexRange curves_range) {
           for (const int curve_i : curves_range) {
             const IndexRange points = curves.points_for_curve(curve_i);
             const int first_point_i = points.first();
             const float3 old_first_point_pos_cu = positions_cu[first_point_i];
 
-            const int looptri_index = surface_triangle_indices[curve_i];
-            if (!surface_looptris.index_range().contains(looptri_index)) {
-              found_invalid_looptri_index = true;
+            const float2 uv = surface_uv_coords[curve_i];
+            ReverseUVSampler::Result lookup_result = reverse_uv_sampler.sample(uv);
+            if (lookup_result.type != ReverseUVSampler::ResultType::Ok) {
+              found_invalid_uv = true;
               continue;
             }
 
-            const MLoopTri &looptri = surface_looptris[looptri_index];
-
-            const float3 bary_coords = bke::curves::decode_surface_bary_coord(
-                surface_triangle_coords[curve_i]);
+            const MLoopTri &looptri = *lookup_result.looptri;
+            const float3 &bary_coords = lookup_result.bary_weights;
 
             const float3 &p0_su = surface_mesh.mvert[surface_mesh.mloop[looptri.tri[0]].v].co;
             const float3 &p1_su = surface_mesh.mvert[surface_mesh.mloop[looptri.tri[1]].v].co;
@@ -638,7 +666,7 @@ static int snap_curves_to_surface_exec(bContext *C, wmOperator *op)
   }
   CTX_DATA_END;
 
-  if (found_invalid_looptri_index) {
+  if (found_invalid_uv) {
     BKE_report(op->reports, RPT_INFO, "Could not snap some curves to the surface");
   }
 
diff --git a/source/blender/editors/object/object_add.cc b/source/blender/editors/object/object_add.cc
index 5e09948e192..041a1383b28 100644
--- a/source/blender/editors/object/object_add.cc
+++ b/source/blender/editors/object/object_add.cc
@@ -2086,6 +2086,12 @@ static int object_curves_empty_hair_add_exec(bContext *C, wmOperator *op)
     Curves *curves_id = static_cast<Curves *>(object->data);
     curves_id->surface = surface_ob;
     id_us_plus(&surface_ob->id);
+
+    Mesh *surface_mesh = static_cast<Mesh *>(surface_ob->data);
+    const char *uv_name = CustomData_get_active_layer_name(&surface_mesh->ldata, CD_MLOOPUV);
+    if (uv_name != nullptr) {
+      curves_id->surface_uv_map = BLI_strdup(uv_name);
+    }
   }
 
   return OPERATOR_FINISHED;
diff --git a/source/blender/editors/sculpt_paint/CMakeLists.txt b/source/blender/editors/sculpt_paint/CMakeLists.txt
index dfd8f8b1bb9..9a9efc9e6cf 100644
--- a/source/blender/editors/sculpt_paint/CMakeLists.txt
+++ b/source/blender/editors/sculpt_paint/CMakeLists.txt
@@ -10,6 +10,7 @@ set(INC
   ../../depsgraph
   ../../draw
   ../../functions
+  ../../geometry
   ../../gpu
   ../../imbuf
   ../../makesdna
diff --git a/source/blender/editors/sculpt_paint/curves_sculpt_add.cc b/source/blender/editors/sculpt_paint/curves_sculpt_add.cc
index 390f142ac0f..5f168bd4e05 100644
--- a/source/blender/editors/sculpt_paint/curves_sculpt_add.cc
+++ b/source/blender/editors/sculpt_paint/curves_sculpt_add.cc
@@ -19,6 +19,7 @@
 #include "BKE_context.h"
 #include "BKE_curves.hh"
 #include "BKE_curves_utils.hh"
+#include "BKE_geometry_set.hh"
 #include "BKE_mesh.h"
 #include "BKE_mesh_runtime.h"
 #include "BKE_paint.h"
@@ -95,6 +96,7 @@ struct AddOperationExecutor {
   Mesh *surface_ = nullptr;
   Span<MLoopTri> surface_looptris_;
   Span<float3> corner_normals_su_;
+  VArray_Span<float2> surface_uv_map_;
 
   const CurvesSculpt *curves_sculpt_ = nullptr;
   const Brush *brush_ = nullptr;
@@ -114,6 +116,7 @@ struct AddOperationExecutor {
 
   /** Various matrices to convert between coordinate spaces. */
   float4x4 curves_to_world_mat_;
+  float4x4 curves_to_surface_mat_;
   float4x4 world_to_curves_mat_;
   float4x4 world_to_surface_mat_;
   float4x4 surface_to_world_mat_;
@@ -165,6 +168,7 @@ struct AddOperationExecutor {
     world_to_surface_mat_ = surface_to_world_mat_.inverted();
     surface_to_curves_mat_ = world_to_curves_mat_ * surface_to_world_mat_;
     surface_to_curves_normal_mat_ = surface_to_curves_mat_.inverted().transposed();
+    curves_to_surface_mat_ = curves_to_world_mat_ * world_to_surface_mat_;
 
     if (!CustomData_has_layer(&surface_->ldata, CD_NORMAL)) {
       BKE_mesh_calc_normals_split(surface_);
@@ -208,6 +212,15 @@ struct AddOperationExecutor {
     surface_looptris_ = {BKE_mesh_runtime_looptri_ensure(surface_),
                          BKE_mesh_runtime_looptri_len(surface_)};
 
+    if (curves_id_->surface_uv_map != nullptr) {
+      MeshComponent surface_component;
+      surface_component.replace(surface_, GeometryOwnershipType::ReadOnly);
+      surface_uv_map_ = surface_component
+                            .attribute_try_get_for_read(curves_id_->surface_uv_map,
+                                                        ATTR_DOMAIN_CORNER)
+                            .typed<float2>();
+    }
+
     /* Sample points on the surface using one of multiple strategies. */
     AddedPoints added_points;
     if (add_amount_ == 1) {
@@ -652,7 +665,9 @@ struct AddOperationExecutor {
     }
 
     Array<float3> new_normals_su = this->compute_normals_for_added_curves_su(added_points);
-    this->initialize_surface_attachment(added_points);
+    if (!surface_uv_map_.is_empty()) {
+      this->initialize_surface_attachment(added_points);
+    }
 
     this->fill_new_selection();
 
@@ -775,14 +790,18 @@ struct AddOperationExecutor {
 
   void initialize_surface_attachment(const AddedPoints &added_points)
   {
-    MutableSpan<int> surface_triangle_indices = curves_->surface_triangle_indices_for_write();
-    MutableSpan<float2> surface_triangle_coords = curves_->surface_triangle_coords_for_write();
+    MutableSpan<float2> surface_uv_coords = curves_->surface_uv_coords_for_write();
     threading::parallel_for(
         added_points.bary_coords.index_range(), 1024, [&](const IndexRange range) {
           for (const int i : range) {
             const int curve_i = tot_old_curves_ + i;
-            surface_triangle_indices[curve_i] = added_points.looptri_indices[i];
-            surface_triangle_coords[curve_i] = float2(added_points.bary_coords[i]);
+            const MLoopTri &looptri = surface_looptris_[added_points.looptri_indices[i]];
+            const float2 &uv0 = surface_uv_map_[looptri.tri[0]];
+            const float2 &uv1 = surface_uv_map_[looptri.tri[1]];
+            const float2 &uv2 = surface_uv_map_[looptri.tri[2]];
+            const float3 &bary_coords = added_points.bary_coords[i];
+            const float2 uv = attribute_math::mix3(bary_coords, uv0, uv1, uv2);
+            surface_uv_coords[curve_i] = uv;
           }
         });
   }
@@ -820,8 +839,6 @@ struct AddOperationExecutor {
                                               const Span<float> new_lengths_cu)
   {
     MutableSpan<float3> positions_cu = curves_->positions_for_write();
-    const VArray_Span<int> surface_triangle_indices{curves_->surface_triangle_indices()};
-    const Span<float2> surface_triangle_coords = curves_->surface_triangle_coords();
 
     threading::parallel_for(
         added_points.bary_coords.index_range(), 256, [&](const IndexRange range) {
@@ -846,10 +863,22 @@ struct AddOperationExecutor {
 
             for (const NeighborInfo &neighbor : neighbors) {
               const int neighbor_curve_i = neighbor.index;
-              const int neighbor_looptri_index = surface_triangle_indices[neighbor_curve_i];
-
-              float3 neighbor_bary_coord{surface_triangle_coords[neighbor_curve_i]};
-              neighbor_bary_coord.z = 1.0f - neighbor_bary_coord.x - neighbor_bary_coord.y;
+              const float3 &neighbor_first_pos_cu =
+                  positions_cu[curves_->offsets()[neighbor_curve_i]];
+              const float3 neighbor_first_pos_su = curves_to_surface_mat_ * neighbor_first_pos_cu;
+
+              BVHTreeNearest nearest;
+              nearest.dist_sq = FLT_MAX;
+              BLI_bvhtree_find_nearest(surface_bvh_.tree,
+                                       neighbor_first_pos_su,
+                                       &nearest,
+                                       surface_bvh_.nearest_callback,
+                                       &surface_bvh_);
+              const int neighbor_looptri_index = nearest.index;
+              const MLoopTri &neighbor_looptri = surface_looptris_[neighbor_looptri_index];
+
+              const float3 neighbor_bary_coord = this->get_bary_coords(
+                  *surface_, neighbor_looptri, nearest.co);
 
               const float3 neighbor_normal_su = this->compute_point_normal_su(
                   neighbor_looptri_index, neighbor_bary_coord);
diff --git a/source/blender/geometry/CMakeLists.txt b/source/blender/geometry/CMakeLists.txt
index 010c327d482..1916c5f91f3 100644
--- a/source/blender/geometry/CMakeLists.txt
+++ b/source/blender/geometry/CMakeLists.txt
@@ -21,6 +21,7 @@ set(SRC
   intern/point_merge_by_distance.cc
   intern/realize_instances.cc
   intern/resample_curves.cc
+  intern/reverse_uv_sampler.cc
   intern/uv_parametrizer.c
 
   GEO_mesh_merge_by_distance.hh
@@ -29,6 +30,7 @@ set(SRC
   GEO_point_merge_by_distance.hh
   GEO_realize_instances.hh
   GEO_resample_curves.hh
+  GEO_reverse_uv_sampler.hh
   GEO_uv_parametrizer.h
 )
 
diff --git a/source/blender/geometry/GEO_reverse_uv_sampler.hh b/source/blender/geometry/GEO_reverse_uv_sampler.hh
new file mode 100644
index 00000000000..d392b65eaf4
--- /dev/null
+++ b/source/blender/geometry/GEO_reverse_uv_sampler.hh
@@ -0,0 +1,42 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#pragma once
+
+#include <optional>
+
+#include "BLI_math_vector.hh"
+#include "BLI_span.hh"
+
+#include "DNA_meshdata_types.h"
+
+namespace blender::geometry {
+
+/**
+ * Can find the polygon/triangle that maps to a specific uv coordinate.
+ *
+ * \note this uses a trivial implementation currently that has to be replaced.
+ */
+class ReverseUVSampler {
+ private:
+  const Span<float2> uv_map_;
+  const Span<MLoopTri> looptris_;
+
+ public:
+  ReverseUVSampler(const Span<float2> uv_map, const Span<MLoopTri> looptris);
+
+  enum class ResultType {
+    None,
+    Ok,
+    Multiple,
+  };
+
+  struct Result {
+    ResultType type = ResultType::None;
+    const MLoopTri *looptri = nullptr;
+    float3 bary_weights;
+  };
+
+  Result sample(const float2 &query_uv) const;
+};
+
+}  // namespace blender::geometry
diff --git a/source/blender/geometry/intern/reverse_uv_sampler.cc b/source/blender/geometry/intern/reverse_uv_sampler.cc
new file mode 100644
index 00000000000..9aa98895a86
--- /dev/null
+++ b/source/blender/geometry/intern/reverse_uv_sampler.cc
@@ -0,0 +1,32 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+#include "GEO_reverse_uv_sampler.hh"
+
+#include "BLI_math_geom.h"
+
+namespace blender::geometry {
+
+ReverseUVSampler::ReverseUVSampler(const Span<float2> uv_map, const Span<MLoopTri> looptris)
+    : uv_map_(uv_map), looptris_(looptris)
+{
+}
+
+ReverseUVSampler::Result ReverseUVSampler::sample(const float2 &query_uv) const
+{
+  for (const MLoopTri &looptri : looptris_) {
+    const float2 &uv0 = uv_map_[looptri.tri[0]];
+    const float2 &uv1 = uv_map_[looptri.tri[1]];
+    const float2 &uv2 = uv_map_[looptri.tri[2]];
+    float3 bary_weights;
+    if (!barycentric_coords_v2(uv0, uv1, uv2, query_uv, bary_weights)) {
+      continue;
+    }
+    if (IN_RANGE_INCL(bary_weights.x, 0.0f, 1.0f) && IN_RANGE_INCL(bary_weights.y, 0.0f, 1.0f) &&
+        IN_RANGE_INCL(bary_weights.z, 0.0f, 1.0f)) {
+      return Result{ResultType::Ok, &looptri, bary_weights};
+    }
+  }
+  return Result{};
+}
+
+}  // namespace blender::geometry