Blender  V3.3
reverse_uv_sampler.cc
Go to the documentation of this file.
1 /* SPDX-License-Identifier: GPL-2.0-or-later */
2 
4 
5 #include "BLI_math_geom.h"
6 #include "BLI_math_vector.hh"
7 #include "BLI_task.hh"
8 #include "BLI_timeit.hh"
9 
10 namespace blender::geometry {
11 
12 static int2 uv_to_cell_key(const float2 &uv, const int resolution)
13 {
14  return int2{uv * resolution};
15 }
16 
18  : uv_map_(uv_map), looptris_(looptris)
19 {
20  resolution_ = std::max<int>(3, std::sqrt(looptris.size()) * 2);
21 
22  for (const int looptri_index : looptris.index_range()) {
23  const MLoopTri &looptri = looptris[looptri_index];
24  const float2 &uv_0 = uv_map_[looptri.tri[0]];
25  const float2 &uv_1 = uv_map_[looptri.tri[1]];
26  const float2 &uv_2 = uv_map_[looptri.tri[2]];
27 
28  const int2 key_0 = uv_to_cell_key(uv_0, resolution_);
29  const int2 key_1 = uv_to_cell_key(uv_1, resolution_);
30  const int2 key_2 = uv_to_cell_key(uv_2, resolution_);
31 
32  const int2 min_key = math::min(math::min(key_0, key_1), key_2);
33  const int2 max_key = math::max(math::max(key_0, key_1), key_2);
34 
35  for (int key_x = min_key.x; key_x <= max_key.x; key_x++) {
36  for (int key_y = min_key.y; key_y <= max_key.y; key_y++) {
37  const int2 key{key_x, key_y};
38  looptris_by_cell_.add(key, looptri_index);
39  }
40  }
41  }
42 }
43 
45 {
46  const int2 cell_key = uv_to_cell_key(query_uv, resolution_);
47  const Span<int> looptri_indices = looptris_by_cell_.lookup(cell_key);
48 
49  float best_dist = FLT_MAX;
50  float3 best_bary_weights;
51  const MLoopTri *best_looptri;
52 
53  /* The distance to an edge that is allowed to be inside or outside the triangle. Without this,
54  * the lookup can fail for floating point accuracy reasons when the uv is almost exact on an
55  * edge. */
56  const float edge_epsilon = 0.00001f;
57 
58  for (const int looptri_index : looptri_indices) {
59  const MLoopTri &looptri = looptris_[looptri_index];
60  const float2 &uv_0 = uv_map_[looptri.tri[0]];
61  const float2 &uv_1 = uv_map_[looptri.tri[1]];
62  const float2 &uv_2 = uv_map_[looptri.tri[2]];
63  float3 bary_weights;
64  if (!barycentric_coords_v2(uv_0, uv_1, uv_2, query_uv, bary_weights)) {
65  continue;
66  }
67 
68  /* If #query_uv is in the triangle, the distance is <= 0. Otherwise, the larger the distance,
69  * the further away the uv is from the triangle. */
70  const float x_dist = std::max(-bary_weights.x, bary_weights.x - 1.0f);
71  const float y_dist = std::max(-bary_weights.y, bary_weights.y - 1.0f);
72  const float z_dist = std::max(-bary_weights.z, bary_weights.z - 1.0f);
73  const float dist = MAX3(x_dist, y_dist, z_dist);
74 
75  if (dist <= 0.0f && best_dist <= 0.0f) {
76  const float worse_dist = std::max(dist, best_dist);
77  /* Allow ignoring multiple triangle intersections if the uv is almost exactly on an edge. */
78  if (worse_dist < -edge_epsilon) {
79  /* The uv sample is in multiple triangles. */
81  }
82  }
83 
84  if (dist < best_dist) {
85  best_dist = dist;
86  best_bary_weights = bary_weights;
87  best_looptri = &looptri;
88  }
89  }
90 
91  /* Allow using the closest (but not intersecting) triangle if the uv is almost exactly on an
92  * edge. */
93  if (best_dist < edge_epsilon) {
94  return Result{ResultType::Ok, best_looptri, math::clamp(best_bary_weights, 0.0f, 1.0f)};
95  }
96 
97  return Result{};
98 }
99 
101  MutableSpan<Result> r_results) const
102 {
103  BLI_assert(query_uvs.size() == r_results.size());
104  threading::parallel_for(query_uvs.index_range(), 256, [&](const IndexRange range) {
105  for (const int i : range) {
106  r_results[i] = this->sample(query_uvs[i]);
107  }
108  });
109 }
110 
111 } // namespace blender::geometry
#define BLI_assert(a)
Definition: BLI_assert.h:46
sqrt(x)+1/max(0
bool barycentric_coords_v2(const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3])
Definition: math_geom.c:3676
#define MAX3(a, b, c)
constexpr int64_t size() const
Definition: BLI_span.hh:511
constexpr int64_t size() const
Definition: BLI_span.hh:240
constexpr IndexRange index_range() const
Definition: BLI_span.hh:401
ReverseUVSampler(const Span< float2 > uv_map, const Span< MLoopTri > looptris)
Result sample(const float2 &query_uv) const
void sample_many(Span< float2 > query_uvs, MutableSpan< Result > r_results) const
static int2 uv_to_cell_key(const float2 &uv, const int resolution)
T clamp(const T &a, const T &min, const T &max)
T min(const T &a, const T &b)
T max(const T &a, const T &b)
void parallel_for(IndexRange range, int64_t grain_size, const Function &function)
Definition: BLI_task.hh:51
unsigned int tri[3]
float max