diff options
author | Lukas Tönne <lukas.toenne@gmail.com> | 2022-07-26 00:43:48 +0300 |
---|---|---|
committer | Lukas Tönne <lukas.toenne@gmail.com> | 2022-07-26 00:43:48 +0300 |
commit | f081e76037432cb926be45e980eac201d337032c (patch) | |
tree | dd1225521c12ea21c0b0c3d51ec1ae3f8730755f /source/blender/geometry/intern/reverse_uv_sampler.cc | |
parent | fa2084ae58a77b1201289b6bedac427f73c762d1 (diff) | |
parent | 462f99bf38648a08226b1fba423315aec2bc577b (diff) |
Merge branch 'master' into geometry-nodes-iterative-cachegeometry-nodes-rigid-body-integration
Diffstat (limited to 'source/blender/geometry/intern/reverse_uv_sampler.cc')
-rw-r--r-- | source/blender/geometry/intern/reverse_uv_sampler.cc | 85 |
1 files changed, 77 insertions, 8 deletions
diff --git a/source/blender/geometry/intern/reverse_uv_sampler.cc b/source/blender/geometry/intern/reverse_uv_sampler.cc index 9aa98895a86..39fec40333c 100644 --- a/source/blender/geometry/intern/reverse_uv_sampler.cc +++ b/source/blender/geometry/intern/reverse_uv_sampler.cc @@ -3,30 +3,99 @@ #include "GEO_reverse_uv_sampler.hh" #include "BLI_math_geom.h" +#include "BLI_math_vector.hh" +#include "BLI_task.hh" +#include "BLI_timeit.hh" namespace blender::geometry { +static int2 uv_to_cell_key(const float2 &uv, const int resolution) +{ + return int2{uv * resolution}; +} + ReverseUVSampler::ReverseUVSampler(const Span<float2> uv_map, const Span<MLoopTri> looptris) : uv_map_(uv_map), looptris_(looptris) { + resolution_ = std::max<int>(3, std::sqrt(looptris.size()) * 2); + + for (const int looptri_index : looptris.index_range()) { + const MLoopTri &looptri = looptris[looptri_index]; + const float2 &uv_0 = uv_map_[looptri.tri[0]]; + const float2 &uv_1 = uv_map_[looptri.tri[1]]; + const float2 &uv_2 = uv_map_[looptri.tri[2]]; + + const int2 key_0 = uv_to_cell_key(uv_0, resolution_); + const int2 key_1 = uv_to_cell_key(uv_1, resolution_); + const int2 key_2 = uv_to_cell_key(uv_2, resolution_); + + const int2 min_key = math::min(math::min(key_0, key_1), key_2); + const int2 max_key = math::max(math::max(key_0, key_1), key_2); + + for (int key_x = min_key.x; key_x <= max_key.x; key_x++) { + for (int key_y = min_key.y; key_y <= max_key.y; key_y++) { + const int2 key{key_x, key_y}; + looptris_by_cell_.add(key, looptri_index); + } + } + } } 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]]; + const int2 cell_key = uv_to_cell_key(query_uv, resolution_); + const Span<int> looptri_indices = looptris_by_cell_.lookup(cell_key); + + float best_dist = FLT_MAX; + float3 best_bary_weights; + const MLoopTri *best_looptri; + + for (const int looptri_index : looptri_indices) { + const MLoopTri &looptri = looptris_[looptri_index]; + const float2 &uv_0 = uv_map_[looptri.tri[0]]; + const float2 &uv_1 = uv_map_[looptri.tri[1]]; + const float2 &uv_2 = uv_map_[looptri.tri[2]]; float3 bary_weights; - if (!barycentric_coords_v2(uv0, uv1, uv2, query_uv, bary_weights)) { + if (!barycentric_coords_v2(uv_0, uv_1, uv_2, 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}; + + /* If #query_uv is in the triangle, the distance is <= 0. Otherwise, the larger the distance, + * the further away the uv is from the triangle. */ + const float x_dist = std::max(-bary_weights.x, bary_weights.x - 1.0f); + const float y_dist = std::max(-bary_weights.y, bary_weights.y - 1.0f); + const float z_dist = std::max(-bary_weights.z, bary_weights.z - 1.0f); + const float dist = MAX3(x_dist, y_dist, z_dist); + + if (dist <= 0.0f && best_dist <= 0.0f) { + /* The uv sample is in multiple triangles. */ + return Result{ResultType::Multiple}; + } + + if (dist < best_dist) { + best_dist = dist; + best_bary_weights = bary_weights; + best_looptri = &looptri; } } + + /* Allow for a small epsilon in case the uv is on th edge. */ + if (best_dist < 0.00001f) { + return Result{ResultType::Ok, best_looptri, math::clamp(best_bary_weights, 0.0f, 1.0f)}; + } + return Result{}; } +void ReverseUVSampler::sample_many(const Span<float2> query_uvs, + MutableSpan<Result> r_results) const +{ + BLI_assert(query_uvs.size() == r_results.size()); + threading::parallel_for(query_uvs.index_range(), 256, [&](const IndexRange range) { + for (const int i : range) { + r_results[i] = this->sample(query_uvs[i]); + } + }); +} + } // namespace blender::geometry |