blender/blender
blender/blender
188
597
Fork 923
Code Issues 6.3k Pull Requests 1.1k Projects 22 Wiki Activity

Point Cloud: Optimize bounding box calculation

Browse Source 
This is analagous to 6a71b2af66cf10556b21 which did the same
thing for mesh data. Two differences are that here the coordinates
are simply `float3`, and we account for the radius if it's available.
Here I observed a similar performance increase, from 50ms
average to 10ms average, with 16 million points, a 5x speedup.

The calculation is about 1.4 times faster when no radius is used, down
 to 7.3ms average. Before, the calculation was only 1.2 times faster.
This commit is contained in:
Hans Goudey 2021-12-29 18:39:08 -06:00
parent 9d3264b4fd
commit 6d7dbdbb44
Notes: blender-bot 2025-02-14 01:29:06 +00:00 
Referenced by commit 5b73017ddb, BLI: Generalize short algorithm for finding bounds
1 changed files with 60 additions and 12 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

72
source/blender/blenkernel/intern/pointcloud.cc
View File

@ -25,10 +25,13 @@
#include "DNA_object_types.h"
#include "DNA_pointcloud_types.h"
#include "BLI_float3.hh"
#include "BLI_index_range.hh"
#include "BLI_listbase.h"
#include "BLI_math.h"
#include "BLI_rand.h"
#include "BLI_span.hh"
#include "BLI_string.h"
#include "BLI_task.hh"
#include "BLI_utildefines.h"
#include "BKE_anim_data.h"
@ -51,6 +54,10 @@
#include "BLO_read_write.h"
using blender::float3;
using blender::IndexRange;
using blender::Span;
/* PointCloud datablock */
static void pointcloud_random(PointCloud *pointcloud);
@ -261,22 +268,63 @@ PointCloud *BKE_pointcloud_new_nomain(const int totpoint)
return pointcloud;
}
bool BKE_pointcloud_minmax(const struct PointCloud *pointcloud, float r_min[3], float r_max[3])
struct MinMaxResult {
float3 min;
float3 max;
};
static MinMaxResult min_max_no_radii(Span<float3> positions)
{
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) {
float3::min_max(positions[i], result.min, result.max);
}
return result;
},
[](const MinMaxResult &a, const MinMaxResult &b) {
return MinMaxResult{float3::min(a.min, b.min), float3::max(a.max, b.max)};
});
}
static MinMaxResult min_max_with_radii(Span<float3> positions, Span<float> radii)
{
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 = float3::min(positions[i] - radii[i], result.min);
result.max = float3::max(positions[i] + radii[i], result.max);
}
return result;
},
[](const MinMaxResult &a, const MinMaxResult &b) {
return MinMaxResult{float3::min(a.min, b.min), float3::max(a.max, b.max)};
});
}
bool BKE_pointcloud_minmax(const PointCloud *pointcloud, float r_min[3], float r_max[3])
{
if (!pointcloud->totpoint) {
return false;
}
float(*pointcloud_co)[3] = pointcloud->co;
float *pointcloud_radius = pointcloud->radius;
for (int a = 0; a < pointcloud->totpoint; a++) {
float *co = pointcloud_co[a];
float radius = (pointcloud_radius) ? pointcloud_radius[a] : 0.0f;
const float co_min[3] = {co[0] - radius, co[1] - radius, co[2] - radius};
const float co_max[3] = {co[0] + radius, co[1] + radius, co[2] + radius};
DO_MIN(co_min, r_min);
DO_MAX(co_max, r_max);
}
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, float3::min(min_max.min, r_min));
copy_v3_v3(r_max, float3::max(min_max.max, r_max));
return true;
}