diff options
author | Hans Goudey <h.goudey@me.com> | 2022-02-16 19:53:40 +0300 |
---|---|---|
committer | Hans Goudey <h.goudey@me.com> | 2022-02-16 19:53:58 +0300 |
commit | 5b73017ddb679bb050fe13e4d9e3e5b04ea559b9 (patch) | |
tree | 4afcb238a3cb27e67a9b8abbccad124702298630 /source | |
parent | 399168f3c13fadb41c9fbec8a1b5c56cb6609343 (diff) |
BLI: Generalize short algorithm for finding bounds
Finding the greatest and/or smallest element in an array is a common
need. This commit refactors the point cloud bounds code added in
6d7dbdbb44f379682 to a more general header in blenlib.
This will allow reusing the algorithm for curves without duplicating it.
Differential Revision: https://developer.blender.org/D14053
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenkernel/intern/pointcloud.cc | 67 | ||||
-rw-r--r-- | source/blender/blenlib/BLI_bounds.hh | 89 | ||||
-rw-r--r-- | source/blender/blenlib/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/blenlib/tests/BLI_bounds_test.cc | 57 |
4 files changed, 162 insertions, 53 deletions
diff --git a/source/blender/blenkernel/intern/pointcloud.cc b/source/blender/blenkernel/intern/pointcloud.cc index 2a4e0715293..3ee46fc4f15 100644 --- a/source/blender/blenkernel/intern/pointcloud.cc +++ b/source/blender/blenkernel/intern/pointcloud.cc @@ -11,6 +11,7 @@ #include "DNA_object_types.h" #include "DNA_pointcloud_types.h" +#include "BLI_bounds.hh" #include "BLI_index_range.hh" #include "BLI_listbase.h" #include "BLI_math_vec_types.hh" @@ -254,68 +255,28 @@ PointCloud *BKE_pointcloud_new_nomain(const int totpoint) return pointcloud; } -struct MinMaxResult { - float3 min; - float3 max; -}; - -static MinMaxResult min_max_no_radii(Span<float3> positions) +static std::optional<blender::bounds::MinMaxResult<float3>> point_cloud_bounds( + const PointCloud &pointcloud) { - using namespace blender::math; - - return blender::threading::parallel_reduce( - positions.index_range(), - 1024, - MinMaxResult{float3(FLT_MAX), float3(-FLT_MAX)}, - [&](IndexRange range, const MinMaxResult &init) { - MinMaxResult result = init; - for (const int i : range) { - min_max(positions[i], result.min, result.max); - } - return result; - }, - [](const MinMaxResult &a, const MinMaxResult &b) { - return MinMaxResult{min(a.min, b.min), max(a.max, b.max)}; - }); -} - -static MinMaxResult min_max_with_radii(Span<float3> positions, Span<float> radii) -{ - using namespace blender::math; - - return blender::threading::parallel_reduce( - positions.index_range(), - 1024, - MinMaxResult{float3(FLT_MAX), float3(-FLT_MAX)}, - [&](IndexRange range, const MinMaxResult &init) { - MinMaxResult result = init; - for (const int i : range) { - result.min = min(positions[i] - radii[i], result.min); - result.max = max(positions[i] + radii[i], result.max); - } - return result; - }, - [](const MinMaxResult &a, const MinMaxResult &b) { - return MinMaxResult{min(a.min, b.min), max(a.max, b.max)}; - }); + Span<float3> positions{reinterpret_cast<float3 *>(pointcloud.co), pointcloud.totpoint}; + if (pointcloud.radius) { + Span<float> radii{pointcloud.radius, pointcloud.totpoint}; + return blender::bounds::min_max_with_radii(positions, radii); + } + return blender::bounds::min_max(positions); } bool BKE_pointcloud_minmax(const PointCloud *pointcloud, float r_min[3], float r_max[3]) { - using namespace blender::math; + using namespace blender; - if (!pointcloud->totpoint) { + const std::optional<bounds::MinMaxResult<float3>> min_max = point_cloud_bounds(*pointcloud); + if (!min_max) { return false; } - Span<float3> positions{reinterpret_cast<float3 *>(pointcloud->co), pointcloud->totpoint}; - const MinMaxResult min_max = (pointcloud->radius) ? - min_max_with_radii(positions, - {pointcloud->radius, pointcloud->totpoint}) : - min_max_no_radii(positions); - - copy_v3_v3(r_min, min(min_max.min, float3(r_min))); - copy_v3_v3(r_max, max(min_max.max, float3(r_max))); + copy_v3_v3(r_min, math::min(min_max->min, float3(r_min))); + copy_v3_v3(r_max, math::max(min_max->max, float3(r_max))); return true; } diff --git a/source/blender/blenlib/BLI_bounds.hh b/source/blender/blenlib/BLI_bounds.hh new file mode 100644 index 00000000000..ce440bef704 --- /dev/null +++ b/source/blender/blenlib/BLI_bounds.hh @@ -0,0 +1,89 @@ +/* + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + */ + +#pragma once + +/** \file + * \ingroup bli + * + * Generic algorithms for finding the largest and smallest elements in a span. + */ + +#include <optional> + +#include "BLI_math_vector.hh" +#include "BLI_task.hh" + +namespace blender::bounds { + +template<typename T> struct MinMaxResult { + T min; + T max; +}; + +/** + * Find the smallest and largest values element-wise in the span. + */ +template<typename T> static std::optional<MinMaxResult<T>> min_max(Span<T> values) +{ + if (values.is_empty()) { + return std::nullopt; + } + return threading::parallel_reduce( + values.index_range(), + 1024, + MinMaxResult<T>(), + [&](IndexRange range, const MinMaxResult<T> &init) { + MinMaxResult<T> result = init; + for (const int i : range) { + math::min_max(values[i], result.min, result.max); + } + return result; + }, + [](const MinMaxResult<T> &a, const MinMaxResult<T> &b) { + return MinMaxResult<T>{math::min(a.min, b.min), math::max(a.max, b.max)}; + }); +} + +/** + * Find the smallest and largest values element-wise in the span, adding the radius to each element + * first. The template type T is expected to have an addition operator implemented with RadiusT. + */ +template<typename T, typename RadiusT> +static std::optional<MinMaxResult<T>> min_max_with_radii(Span<T> values, Span<RadiusT> radii) +{ + BLI_assert(values.size() == radii.size()); + if (values.is_empty()) { + return std::nullopt; + } + return threading::parallel_reduce( + values.index_range(), + 1024, + MinMaxResult<T>(), + [&](IndexRange range, const MinMaxResult<T> &init) { + MinMaxResult<T> result = init; + for (const int i : range) { + result.min = math::min(values[i] - radii[i], result.min); + result.max = math::max(values[i] + radii[i], result.max); + } + return result; + }, + [](const MinMaxResult<T> &a, const MinMaxResult<T> &b) { + return MinMaxResult<T>{math::min(a.min, b.min), math::max(a.max, b.max)}; + }); +} + +} // namespace blender::bounds diff --git a/source/blender/blenlib/CMakeLists.txt b/source/blender/blenlib/CMakeLists.txt index e67d673eb73..e1b6e218ff5 100644 --- a/source/blender/blenlib/CMakeLists.txt +++ b/source/blender/blenlib/CMakeLists.txt @@ -162,6 +162,7 @@ set(SRC BLI_bitmap_draw_2d.h BLI_blenlib.h BLI_boxpack_2d.h + BLI_bounds.hh BLI_buffer.h BLI_color.hh BLI_compiler_attrs.h @@ -395,6 +396,7 @@ if(WITH_GTESTS) tests/BLI_array_store_test.cc tests/BLI_array_test.cc tests/BLI_array_utils_test.cc + tests/BLI_bounds_test.cc tests/BLI_color_test.cc tests/BLI_delaunay_2d_test.cc tests/BLI_disjoint_set_test.cc diff --git a/source/blender/blenlib/tests/BLI_bounds_test.cc b/source/blender/blenlib/tests/BLI_bounds_test.cc new file mode 100644 index 00000000000..fc3affd97de --- /dev/null +++ b/source/blender/blenlib/tests/BLI_bounds_test.cc @@ -0,0 +1,57 @@ +/* Apache License, Version 2.0 */ + +#include "testing/testing.h" + +#include "BLI_math_base.hh" + +#include "BLI_array.hh" +#include "BLI_bounds.hh" + +namespace blender::tests { + +TEST(bounds, Empty) +{ + Span<float2> empty_span{}; + EXPECT_TRUE(empty_span.is_empty()); + auto result = bounds::min_max(empty_span); + EXPECT_EQ(result, std::nullopt); +} + +TEST(bounds, MinMax) +{ + Array<float2> data = {float2(0, 1), float2(3, -1), float2(0, -2), float2(-1, 1)}; + auto result = bounds::min_max(data.as_span()); + EXPECT_EQ(result->min, float2(-1, -2)); + EXPECT_EQ(result->max, float2(3, 1)); +} + +TEST(bounds, MinMaxFloat) +{ + Array<float> data = {1.0f, 3.0f, 0.0f, -1.0f}; + auto result = bounds::min_max(data.as_span()); + EXPECT_EQ(result->min, -1.0f); + EXPECT_EQ(result->max, 3.0f); +} + +TEST(bounds, MinMaxRadii) +{ + Array<int2> data = {int2(0, 1), int2(3, -1), int2(0, -2), int2(-1, 1)}; + Array<int> radii = {5, 1, 1, 4}; + auto result = bounds::min_max_with_radii(data.as_span(), radii.as_span()); + EXPECT_EQ(result->min, int2(-5, -4)); + EXPECT_EQ(result->max, int2(5, 6)); +} + +TEST(bounds, Large) +{ + Array<int2> data(10000); + for (const int64_t i : data.index_range()) { + data[i] = int2(i, i); + } + + auto result = bounds::min_max(data.as_span()); + EXPECT_EQ(result->min, int2(0, 0)); + EXPECT_EQ(result->max, int2(9999, 9999)); +} + +} // namespace blender::tests |