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
6d7dbdbb44
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
This commit is contained in:
parent
399168f3c1
commit
5b73017ddb
|
@ -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;
|
||||
}
|
||||
|
|
|
@ -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
|
|
@ -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
|
||||
|
|
|
@ -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
|
Loading…
Reference in New Issue