Blender V5.3
reverse_uv_sampler.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: GPL-2.0-or-later */
4
8
9#include <algorithm>
10#include <fmt/format.h>
11
13
14#include "BLI_bounds.hh"
17#include "BLI_map.hh"
18#include "BLI_math_geom_c.hh"
19#include "BLI_math_vector.hh"
20#include "BLI_offset_indices.hh"
21#include "BLI_task.hh"
22#include "BLI_vector_set.hh"
23#include "PRF_profile.hh"
24
25namespace blender::geometry {
26
39
46
49 int x_min;
50 int x_max;
51};
52
58
63
64static int2 uv_to_cell(const float2 &uv, const int resolution)
65{
66 return int2{uv * resolution};
67}
68
70 const int resolution,
71 const Span<float2> uv_map)
72{
73 const float2 &uv_0 = uv_map[tri[0]];
74 const float2 &uv_1 = uv_map[tri[1]];
75 const float2 &uv_2 = uv_map[tri[2]];
76
77 const int2 cell_0 = uv_to_cell(uv_0, resolution);
78 const int2 cell_1 = uv_to_cell(uv_1, resolution);
79 const int2 cell_2 = uv_to_cell(uv_2, resolution);
80
81 const int2 min_cell = math::min(math::min(cell_0, cell_1), cell_2);
82 const int2 max_cell = math::max(math::max(cell_0, cell_1), cell_2);
83
84 return {min_cell, max_cell};
85}
86
92static void sort_tris_into_rows(const Span<float2> uv_map,
93 const Span<int3> corner_tris,
94 const int resolution,
96{
97 threading::parallel_for(corner_tris.index_range(), 256, [&](const IndexRange tris_range) {
98 LocalData &local_data = data_per_thread.local();
99 for (const int tri_i : tris_range) {
100 const int3 &tri = corner_tris[tri_i];
101
102 /* Compute the cells that the triangle touches approximately. */
103 const Bounds<int2> cell_bounds = tri_to_cell_bounds(tri, resolution, uv_map);
104 const TriWithRange tri_with_range{tri_i, cell_bounds.min.x, cell_bounds.max.x};
105
106 /* Go over each row that the triangle is in. */
107 for (int cell_y = cell_bounds.min.y; cell_y <= cell_bounds.max.y; cell_y++) {
108 LocalRowData &row = *local_data.rows.lookup_or_add_cb(
109 cell_y, [&]() { return local_data.allocator.construct<LocalRowData>(); });
110 row.tris.append(local_data.allocator, tri_with_range);
111 row.x_min = std::min<int>(row.x_min, cell_bounds.min.x);
112 row.x_max = std::max<int>(row.x_max, cell_bounds.max.x);
113 }
114 }
115 });
116}
117
122static void finish_rows(const Span<int> all_ys,
123 const Span<const LocalData *> local_data_vec,
124 const Bounds<int> y_bounds,
125 ReverseUVSampler::LookupGrid &lookup_grid)
126{
127 threading::parallel_for(all_ys.index_range(), 8, [&](const IndexRange all_ys_range) {
128 Vector<const LocalRowData *, 32> local_rows;
129 for (const int y : all_ys.slice(all_ys_range)) {
130 Row &row = lookup_grid.rows[y - y_bounds.min];
131
132 local_rows.clear();
133 for (const LocalData *local_data : local_data_vec) {
134 if (const destruct_ptr<LocalRowData> *local_row = local_data->rows.lookup_ptr(y)) {
135 local_rows.append(local_row->get());
136 }
137 }
138
139 int x_min = INT32_MAX;
140 int x_max = INT32_MIN;
141 for (const LocalRowData *local_row : local_rows) {
142 x_min = std::min(x_min, local_row->x_min);
143 x_max = std::max(x_max, local_row->x_max);
144 }
145
146 const int x_num = x_max - x_min + 1;
147 row.offsets.reinitialize(x_num + 1);
148 {
149 /* Count how many triangles are in each cell in the current row. */
150 MutableSpan<int> counts = row.offsets;
151 counts.fill(0);
152 for (const LocalRowData *local_row : local_rows) {
153 for (const TriWithRange &tri_with_range : local_row->tris) {
154 for (int x = tri_with_range.x_min; x <= tri_with_range.x_max; x++) {
155 counts[x - x_min]++;
156 }
157 }
158 }
159 offset_indices::accumulate_counts_to_offsets(counts);
160 }
161 const int tri_indices_num = row.offsets.last();
162 row.tri_indices.reinitialize(tri_indices_num);
163
164 /* Populate the array containing all triangle indices in all cells in this row. */
165 Array<int, 1000> current_offsets(x_num, 0);
166 for (const LocalRowData *local_row : local_rows) {
167 for (const TriWithRange &tri_with_range : local_row->tris) {
168 for (int x = tri_with_range.x_min; x <= tri_with_range.x_max; x++) {
169 const int offset_x = x - x_min;
170 row.tri_indices[row.offsets[offset_x] + current_offsets[offset_x]] =
171 tri_with_range.tri_index;
172 current_offsets[offset_x]++;
173 }
174 }
175 }
176
177 row.x_min = x_min;
178 row.x_max = x_max;
179 }
180 });
181}
182
184 : uv_map_(uv_map), corner_tris_(corner_tris), lookup_grid_(std::make_unique<LookupGrid>())
185{
187 /* A lower resolution means that there will be fewer cells and more triangles in each cell. Fewer
188 * cells make construction faster, but more triangles per cell make lookup slower. This value
189 * needs to be determined experimentally. */
190 resolution_ = std::max<int>(3, std::sqrt(corner_tris.size()) * 3);
191 if (corner_tris.is_empty()) {
192 return;
193 }
194
196 sort_tris_into_rows(uv_map_, corner_tris_, resolution_, data_per_thread);
197
198 VectorSet<int> all_ys;
199 Vector<const LocalData *> local_data_vec;
200 for (const LocalData &local_data : data_per_thread) {
201 local_data_vec.append(&local_data);
202 for (const int y : local_data.rows.keys()) {
203 all_ys.add(y);
204 }
205 }
206
207 const Bounds<int> y_bounds = *bounds::min_max(all_ys.as_span());
208 lookup_grid_->y_min = y_bounds.min;
209
210 const int rows_num = y_bounds.max - y_bounds.min + 1;
211 lookup_grid_->rows.reinitialize(rows_num);
212
213 finish_rows(all_ys, local_data_vec, y_bounds, *lookup_grid_);
214}
215
217 const ReverseUVSampler::LookupGrid &lookup_grid)
218{
219 if (cell.y < lookup_grid.y_min) {
220 return {};
221 }
222 if (cell.y >= lookup_grid.y_min + lookup_grid.rows.size()) {
223 return {};
224 }
225 const Row &row = lookup_grid.rows[cell.y - lookup_grid.y_min];
226 if (cell.x < row.x_min) {
227 return {};
228 }
229 if (cell.x > row.x_max) {
230 return {};
231 }
232 if (row.tri_indices.is_empty()) {
233 return {};
234 }
235 const int offset = row.offsets[cell.x - row.x_min];
236 const int tris_num = row.offsets[cell.x - row.x_min + 1] - offset;
237 return row.tri_indices.as_span().slice(offset, tris_num);
238}
239
241{
242 const int2 cell = uv_to_cell(query_uv, resolution_);
243 const Span<int> tri_indices = lookup_tris_in_cell(cell, *lookup_grid_);
244
245 float best_dist = FLT_MAX;
246 float3 best_bary_weights;
247 int best_tri_index;
248
249 /* The distance to an edge that is allowed to be inside or outside the triangle. Without this,
250 * the lookup can fail for floating point accuracy reasons when the uv is almost exact on an
251 * edge. */
252 const float edge_epsilon = 0.00001f;
253 /* If uv triangles are very small, it may look like the query hits multiple triangles due to
254 * floating point precision issues. Better just pick one of the triangles instead of failing the
255 * entire operation in this case. */
256 const float area_epsilon = 0.00001f;
257
258 for (const int tri_i : tri_indices) {
259 const int3 &tri = corner_tris_[tri_i];
260 const float2 &uv_0 = uv_map_[tri[0]];
261 const float2 &uv_1 = uv_map_[tri[1]];
262 const float2 &uv_2 = uv_map_[tri[2]];
263 float3 bary_weights;
264 if (!barycentric_coords_v2(uv_0, uv_1, uv_2, query_uv, bary_weights)) {
265 continue;
266 }
267
268 /* If #query_uv is in the triangle, the distance is <= 0. Otherwise, the larger the distance,
269 * the further away the uv is from the triangle. */
270 const float x_dist = std::max(-bary_weights.x, bary_weights.x - 1.0f);
271 const float y_dist = std::max(-bary_weights.y, bary_weights.y - 1.0f);
272 const float z_dist = std::max(-bary_weights.z, bary_weights.z - 1.0f);
273 const float dist = std::max({x_dist, y_dist, z_dist});
274
275 if (dist <= 0.0f && best_dist <= 0.0f) {
276 const float worse_dist = std::max(dist, best_dist);
277 /* Allow ignoring multiple triangle intersections if the uv is almost exactly on an edge. */
278 if (worse_dist < -edge_epsilon) {
279 const int3 &best_tri = corner_tris_[tri_i];
280 const float best_tri_area = area_tri_v2(
281 uv_map_[best_tri[0]], uv_map_[best_tri[1]], uv_map_[best_tri[2]]);
282 const float current_tri_area = area_tri_v2(uv_0, uv_1, uv_2);
283 if (best_tri_area > area_epsilon && current_tri_area > area_epsilon) {
284 /* The uv sample is in multiple triangles. */
286 }
287 }
288 }
289
290 if (dist < best_dist) {
291 best_dist = dist;
292 best_bary_weights = bary_weights;
293 best_tri_index = tri_i;
294 }
295 }
296
297 /* Allow using the closest (but not intersecting) triangle if the uv is almost exactly on an
298 * edge. */
299 if (best_dist < edge_epsilon) {
300 return Result{ResultType::Ok, best_tri_index, math::clamp(best_bary_weights, 0.0f, 1.0f)};
301 }
302
303 return Result{};
304}
305
307
309 MutableSpan<Result> r_results) const
310{
311 PRF_scope_with_name("ReverseUVSampler::sample_many", ProfileCategory::Default);
312 BLI_assert(query_uvs.size() == r_results.size());
313 threading::parallel_for(query_uvs.index_range(), 256, [&](const IndexRange range) {
314 for (const int i : range) {
315 r_results[i] = this->sample(query_uvs[i]);
316 }
317 });
318}
319
320} // namespace blender::geometry
#define INT32_MAX
#define INT32_MIN
#define PRF_scope_with_name(ui_name, category)
#define PRF_scope(category)
Span< T > as_span() const
Definition BLI_array.hh:254
bool is_empty() const
Definition BLI_array.hh:275
constexpr int64_t size() const
Definition BLI_span.hh:499
constexpr int64_t size() const
Definition BLI_span.hh:256
constexpr IndexRange index_range() const
Definition BLI_span.hh:405
constexpr bool is_empty() const
Definition BLI_span.hh:264
bool add(const Key &key)
Span< Key > as_span() const
void append(const T &value)
ReverseUVSampler(Span< float2 > uv_map, Span< int3 > corner_tris)
Result sample(const float2 &query_uv) const
void sample_many(Span< float2 > query_uvs, MutableSpan< Result > r_results) const
#define FLT_MAX
std::optional< Bounds< T > > min_max(const std::optional< Bounds< T > > &a, const T &b)
Definition BLI_bounds.hh:56
static void finish_rows(const Span< int > all_ys, const Span< const LocalData * > local_data_vec, const Bounds< int > y_bounds, ReverseUVSampler::LookupGrid &lookup_grid)
static Span< int > lookup_tris_in_cell(const int2 cell, const ReverseUVSampler::LookupGrid &lookup_grid)
static void sort_tris_into_rows(const Span< float2 > uv_map, const Span< int3 > corner_tris, const int resolution, threading::EnumerableThreadSpecific< LocalData > &data_per_thread)
static Bounds< int2 > tri_to_cell_bounds(const int3 &tri, const int resolution, const Span< float2 > uv_map)
static int2 uv_to_cell(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(const IndexRange range, const int64_t grain_size, const Function &function, const TaskSizeHints &size_hints=detail::TaskSizeHints_Static(1))
Definition BLI_task.hh:69
BLI_assert(slot->slot_subtype.map==BMO_OP_SLOT_SUBTYPE_MAP_FLT)
VecBase< int32_t, 2 > int2
VecBase< float, 2 > float2
VecBase< int32_t, 3 > int3
MINLINE float area_tri_v2(const float v1[2], const float v2[2], const float v3[2])
bool barycentric_coords_v2(const float v1[2], const float v2[2], const float v3[2], const float co[2], float w[3])
VecBase< float, 3 > float3
Map< int, destruct_ptr< LocalRowData > > rows
linear_allocator::ChunkedList< TriWithRange, 8 > tris