[Bf-blender-cvs] [1fc2764aaf0] geometry-nodes-distribute-points: Add debug timer prints to possion for fututer performance discussions
Sebastian Parborg
noreply at git.blender.org
Mon Nov 30 00:29:19 CET 2020
Commit: 1fc2764aaf039866807d796b69d0a26fb251d52c
Author: Sebastian Parborg
Date: Mon Nov 30 00:28:36 2020 +0100
Branches: geometry-nodes-distribute-points
https://developer.blender.org/rB1fc2764aaf039866807d796b69d0a26fb251d52c
Add debug timer prints to possion for fututer performance discussions
===================================================================
M source/blender/nodes/geometry/nodes/cySampleElim.hh
M source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc
===================================================================
diff --git a/source/blender/nodes/geometry/nodes/cySampleElim.hh b/source/blender/nodes/geometry/nodes/cySampleElim.hh
index 4703aed34d6..84cce8a9198 100644
--- a/source/blender/nodes/geometry/nodes/cySampleElim.hh
+++ b/source/blender/nodes/geometry/nodes/cySampleElim.hh
@@ -60,10 +60,13 @@
//-------------------------------------------------------------------------------
#include "MEM_guardedalloc.h"
+
#include <BLI_assert.h>
#include <BLI_float3.hh>
#include <BLI_heap.h>
#include <BLI_kdtree.h>
+#include <BLI_timeit.hh>
+
#include <cmath>
#include <functional>
#include <vector>
@@ -870,8 +873,11 @@ class WeightedSampleElimination {
}
});
};
- for (SIZE_TYPE i = 0; i < inputSize; i++) {
- AddWeights(i, inputPoints[i]);
+ {
+ SCOPED_TIMER("poisson KDtree weight assignmet");
+ for (SIZE_TYPE i = 0; i < inputSize; i++) {
+ AddWeights(i, inputPoints[i]);
+ }
}
// Build a heap for the samples using their weights
@@ -895,16 +901,20 @@ class WeightedSampleElimination {
});
};
SIZE_TYPE sampleSize = inputSize;
- // Stop when the top heap item has a weight of zero.
- // We have to return at least one point otherwise the heap triggers a ASAN error
- while (heap.GetTopItem() > (0.5f * 1e-5f) && heap.NumItemsInHeap() > 1) {
- // Pull the top sample from heap
- SIZE_TYPE i = heap.GetTopItemID();
- heap.Pop();
- // For each sample around it, remove its weight contribution and update
- // the heap
- RemoveWeights(i, inputPoints[i]);
- sampleSize--;
+
+ {
+ SCOPED_TIMER("poisson Heap weight elimination");
+ // Stop when the top heap item has a weight of zero.
+ // We have to return at least one point otherwise the heap triggers a ASAN error
+ while (heap.GetTopItem() > (0.5f * 1e-5f) && heap.NumItemsInHeap() > 1) {
+ // Pull the top sample from heap
+ SIZE_TYPE i = heap.GetTopItemID();
+ heap.Pop();
+ // For each sample around it, remove its weight contribution and update
+ // the heap
+ RemoveWeights(i, inputPoints[i]);
+ sampleSize--;
+ }
}
// Copy the samples to the output array
diff --git a/source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc b/source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc
index 23c0c6af6fd..4755eb27bea 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_point_distribute.cc
@@ -19,6 +19,7 @@
#include "BLI_math_vector.h"
#include "BLI_rand.hh"
#include "BLI_span.hh"
+#include "BLI_timeit.hh"
#include "DNA_mesh_types.h"
#include "DNA_meshdata_types.h"
@@ -123,74 +124,88 @@ static Vector<float3> poisson_scatter_points_from_mesh(const Mesh *mesh,
int quality = 5;
Vector<bool> remove_point;
- for (const int looptri_index : IndexRange(looptris_len)) {
- const MLoopTri &looptri = looptris[looptri_index];
- const int v0_index = mesh->mloop[looptri.tri[0]].v;
- const int v1_index = mesh->mloop[looptri.tri[1]].v;
- const int v2_index = mesh->mloop[looptri.tri[2]].v;
- const float3 v0_pos = mesh->mvert[v0_index].co;
- const float3 v1_pos = mesh->mvert[v1_index].co;
- const float3 v2_pos = mesh->mvert[v2_index].co;
- const float area = area_tri_v3(v0_pos, v1_pos, v2_pos);
- const float v0_density_factor = std::max(0.0f, density_factors[v0_index]);
- const float v1_density_factor = std::max(0.0f, density_factors[v1_index]);
- const float v2_density_factor = std::max(0.0f, density_factors[v2_index]);
-
- const int looptri_seed = BLI_hash_int(looptri_index + seed);
- RandomNumberGenerator looptri_rng(looptri_seed);
-
- const float points_amount_fl = quality * area / (2.0f * sqrtf(3.0f) * min_dist * min_dist);
- const float add_point_probability = fractf(points_amount_fl);
- const bool add_point = add_point_probability > looptri_rng.get_float();
- const int point_amount = (int)points_amount_fl + (int)add_point;
-
- for (int i = 0; i < point_amount; i++) {
- const float3 bary_coords = looptri_rng.get_barycentric_coordinates();
- float3 point_pos;
- interp_v3_v3v3v3(point_pos, v0_pos, v1_pos, v2_pos, bary_coords);
- points.append(point_pos);
-
- const float weight = bary_coords[0] * v0_density_factor +
- bary_coords[1] * v1_density_factor + bary_coords[2] * v2_density_factor;
- remove_point.append(looptri_rng.get_float() <= density * weight);
+ {
+ SCOPED_TIMER("poisson random dist points");
+
+ for (const int looptri_index : IndexRange(looptris_len)) {
+ const MLoopTri &looptri = looptris[looptri_index];
+ const int v0_index = mesh->mloop[looptri.tri[0]].v;
+ const int v1_index = mesh->mloop[looptri.tri[1]].v;
+ const int v2_index = mesh->mloop[looptri.tri[2]].v;
+ const float3 v0_pos = mesh->mvert[v0_index].co;
+ const float3 v1_pos = mesh->mvert[v1_index].co;
+ const float3 v2_pos = mesh->mvert[v2_index].co;
+ const float area = area_tri_v3(v0_pos, v1_pos, v2_pos);
+ const float v0_density_factor = std::max(0.0f, density_factors[v0_index]);
+ const float v1_density_factor = std::max(0.0f, density_factors[v1_index]);
+ const float v2_density_factor = std::max(0.0f, density_factors[v2_index]);
+
+ const int looptri_seed = BLI_hash_int(looptri_index + seed);
+ RandomNumberGenerator looptri_rng(looptri_seed);
+
+ const float points_amount_fl = quality * area / (2.0f * sqrtf(3.0f) * min_dist * min_dist);
+ const float add_point_probability = fractf(points_amount_fl);
+ const bool add_point = add_point_probability > looptri_rng.get_float();
+ const int point_amount = (int)points_amount_fl + (int)add_point;
+
+ for (int i = 0; i < point_amount; i++) {
+ const float3 bary_coords = looptri_rng.get_barycentric_coordinates();
+ float3 point_pos;
+ interp_v3_v3v3v3(point_pos, v0_pos, v1_pos, v2_pos, bary_coords);
+ points.append(point_pos);
+
+ const float weight = bary_coords[0] * v0_density_factor +
+ bary_coords[1] * v1_density_factor +
+ bary_coords[2] * v2_density_factor;
+ remove_point.append(looptri_rng.get_float() <= density * weight);
+ }
}
}
// Eliminate the scattered points until we get a possion distribution.
-
- cy::WeightedSampleElimination<float3, float, 3, size_t> wse;
+ std::vector<size_t> output_idx;
Vector<float3> output_points(points.size());
- bool is_progressive = false;
-
- float d_max = 2 * min_dist;
-
- float d_min = d_max * wse.GetWeightLimitFraction(points.size(), points.size() / quality);
- float alpha = wse.GetParamAlpha();
- std::vector<size_t> output_idx = wse.Eliminate_all(
- points.data(),
- points.size(),
- output_points.data(),
- output_points.size(),
- is_progressive,
- d_max,
- 2,
- [d_min, alpha](float3 const & /*unused*/, float3 const & /*unused*/, float d2, float d_max) {
- float d = sqrtf(d2);
- if (d < d_min) {
- d = d_min;
- }
- return std::pow(1.0f - d / d_max, alpha);
- });
-
- output_points.resize(output_idx.size());
- points.clear();
- points.reserve(output_points.size());
-
- for (int i = 0; i < output_points.size(); i++) {
- if (!remove_point[output_idx[i]]) {
- continue;
+ {
+ SCOPED_TIMER("Total poisson sample elim");
+
+ cy::WeightedSampleElimination<float3, float, 3, size_t> wse;
+ bool is_progressive = false;
+
+ float d_max = 2 * min_dist;
+
+ float d_min = d_max * wse.GetWeightLimitFraction(points.size(), points.size() / quality);
+ float alpha = wse.GetParamAlpha();
+ output_idx = wse.Eliminate_all(
+ points.data(),
+ points.size(),
+ output_points.data(),
+ output_points.size(),
+ is_progressive,
+ d_max,
+ 2,
+ [d_min,
+ alpha](float3 const & /*unused*/, float3 const & /*unused*/, float d2, float d_max) {
+ float d = sqrtf(d2);
+ if (d < d_min) {
+ d = d_min;
+ }
+ return std::pow(1.0f - d / d_max, alpha);
+ });
+ }
+
+ // Check if we have any points we should remove from the final possion distribition.
+ {
+ SCOPED_TIMER("poisson weight map elim");
+ output_points.resize(output_idx.size());
+ points.clear();
+ points.reserve(output_points.size());
+
+ for (int i = 0; i < output_points.size(); i++) {
+ if (!remove_point[output_idx[i]]) {
+ continue;
+ }
+ points.append(output_points[i]);
}
- points.append(output_points[i]);
}
return points;
More information about the Bf-blender-cvs
mailing list