[Bf-blender-cvs] [9c4c8ea90f7] temp-geometry-nodes-distribute-points-cleanup: Fix heap direction, cleanups and progressive sampling
Dalai Felinto
noreply at git.blender.org
Fri Dec 11 22:19:22 CET 2020
Commit: 9c4c8ea90f7d7b3c89e928305dc42d9ed436eddf
Author: Dalai Felinto
Date: Fri Dec 11 17:52:44 2020 +0100
Branches: temp-geometry-nodes-distribute-points-cleanup
https://developer.blender.org/rB9c4c8ea90f7d7b3c89e928305dc42d9ed436eddf
Fix heap direction, cleanups and progressive sampling
The BLI_heap in Blender is a down-up heap implementation,
so the weights need to be reverted.
===================================================================
M source/blender/nodes/geometry/nodes/cySampleElim.hh
M source/blender/nodes/geometry/nodes/node_geo_point_distribute_poisson_disk.cc
===================================================================
diff --git a/source/blender/nodes/geometry/nodes/cySampleElim.hh b/source/blender/nodes/geometry/nodes/cySampleElim.hh
index 9f1e2cdb93a..94cdff456ac 100644
--- a/source/blender/nodes/geometry/nodes/cySampleElim.hh
+++ b/source/blender/nodes/geometry/nodes/cySampleElim.hh
@@ -201,7 +201,7 @@ class WeightedSampleElimination {
d_max = 2 * GetMaxPoissonDiskRadius(dimensions, outputSize);
}
DoEliminate(inputPoints, inputSize, outputPoints, outputSize, d_max, weightFunction, false);
- if (progressive && false) {
+ if (progressive) {
std::vector<PointType> tmpPoints(outputSize);
PointType *inPts = outputPoints;
PointType *outPts = tmpPoints.data();
diff --git a/source/blender/nodes/geometry/nodes/node_geo_point_distribute_poisson_disk.cc b/source/blender/nodes/geometry/nodes/node_geo_point_distribute_poisson_disk.cc
index ef7a32a3b70..8457e05d410 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_point_distribute_poisson_disk.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_point_distribute_poisson_disk.cc
@@ -37,8 +37,8 @@
namespace blender::nodes {
-static void tile_point(std::vector<float3> *tiled_points,
- std::vector<size_t> *indices,
+static void tile_point(Vector<float3> *tiled_points,
+ Vector<size_t> *indices,
const float maximum_distance,
const float3 boundbox,
float3 const &point,
@@ -50,8 +50,8 @@ static void tile_point(std::vector<float3> *tiled_points,
float3 p = point;
p[d] -= boundbox[d];
- tiled_points->push_back(p);
- indices->push_back(index);
+ tiled_points->append(p);
+ indices->append(index);
tile_point(tiled_points, indices, maximum_distance, boundbox, p, index, d + 1);
}
@@ -60,8 +60,8 @@ static void tile_point(std::vector<float3> *tiled_points,
float3 p = point;
p[d] += boundbox[d];
- tiled_points->push_back(p);
- indices->push_back(index);
+ tiled_points->append(p);
+ indices->append(index);
tile_point(tiled_points, indices, maximum_distance, boundbox, p, index, d + 1);
}
@@ -90,15 +90,15 @@ static float point_weight_influence_get(const float maximum_distance,
* For each index in the weight array add a weight based on the proximity the
* corresponding point has with its neighboors.
**/
-static void points_distance_weight_calculate(std::vector<float> *weights,
+static void points_distance_weight_calculate(Vector<float> *weights,
const size_t point_id,
- Vector<float3> const *input_points,
+ const float3 *input_points,
const void *kd_tree,
const float minimum_distance,
const float maximum_distance,
#ifndef CYHEAP
Heap *heap,
- std::vector<HeapNode *> *nodes)
+ Vector<HeapNode *> *nodes)
#else
cy::Heap *heap,
void *UNUSED(nodes))
@@ -106,7 +106,7 @@ static void points_distance_weight_calculate(std::vector<float> *weights,
{
KDTreeNearest_3d *nearest_point = nullptr;
int neighbors = BLI_kdtree_3d_range_search(
- (KDTree_3d *)kd_tree, input_points->data()[point_id], &nearest_point, maximum_distance);
+ (KDTree_3d *)kd_tree, input_points[point_id], &nearest_point, maximum_distance);
for (int i = 0; i < neighbors; i++) {
size_t neighbor_point_id = nearest_point[i].index;
@@ -125,15 +125,15 @@ static void points_distance_weight_calculate(std::vector<float> *weights,
/* In the first pass we just the weights. */
if (heap == nullptr) {
- weights->data()[point_id] += weight_influence;
+ (*weights)[point_id] += weight_influence;
}
/* When we run again we need to update the weights and the heap. */
else {
- weights->data()[neighbor_point_id] -= weight_influence;
+ (*weights)[neighbor_point_id] -= weight_influence;
#ifndef CYHEAP
- HeapNode *node = nodes->data()[neighbor_point_id];
+ HeapNode *node = (*nodes)[neighbor_point_id];
if (node != nullptr) {
- BLI_heap_node_value_update(heap, node, weights->data()[neighbor_point_id]);
+ BLI_heap_node_value_update(heap, node, -((*weights)[neighbor_point_id]));
}
#else
heap->MoveItemDown(neighbor_point_id);
@@ -160,26 +160,26 @@ static float weight_limit_fraction_get(const size_t input_size, const size_t out
/**
* Tile the input points.
*/
-static void points_tiling(Vector<float3> const *input_points,
+static void points_tiling(const float3 *input_points,
+ const size_t input_size,
void **kd_tree,
const float maximum_distance,
const float3 boundbox)
{
- std::vector<float3> tiled_points(input_points->data(),
- input_points->data() + input_points->size());
- std::vector<size_t> indices(input_points->size());
+ Vector<float3> tiled_points(input_points, input_points + input_size);
+ Vector<size_t> indices(input_size);
/* Start building a kdtree for the samples. */
- for (size_t i = 0; i < input_points->size(); i++) {
+ for (size_t i = 0; i < input_size; i++) {
indices[i] = i;
- BLI_kdtree_3d_insert(*(KDTree_3d **)kd_tree, i, input_points->data()[i]);
+ BLI_kdtree_3d_insert(*(KDTree_3d **)kd_tree, i, input_points[i]);
}
BLI_kdtree_3d_balance(*(KDTree_3d **)kd_tree);
/* Tile the tree based on the boundbox. */
- for (size_t i = 0; i < input_points->size(); i++) {
- tile_point(&tiled_points, &indices, maximum_distance, boundbox, input_points->data()[i], i);
+ for (size_t i = 0; i < input_size; i++) {
+ tile_point(&tiled_points, &indices, maximum_distance, boundbox, input_points[i], i);
}
/* Re-use the same kdtree, so free it before re-creating it. */
@@ -193,21 +193,31 @@ static void points_tiling(Vector<float3> const *input_points,
BLI_kdtree_3d_balance(*(KDTree_3d **)kd_tree);
}
-static void weighted_sample_elimination(Vector<float3> const *input_points,
- Vector<float3> *output_points,
+static void weighted_sample_elimination(const float3 *input_points,
+ const size_t input_size,
+ float3 *output_points,
+ const size_t output_size,
const float maximum_distance,
const float3 boundbox,
const bool do_copy_eliminated)
{
const float minimum_distance = maximum_distance *
- weight_limit_fraction_get(input_points->size(),
- output_points->size());
+ weight_limit_fraction_get(input_size, output_size);
- void *kd_tree = BLI_kdtree_3d_new(input_points->size());
- points_tiling(input_points, &kd_tree, maximum_distance, boundbox);
+ void *kd_tree = BLI_kdtree_3d_new(input_size);
+ const bool tiling = true;
+ if (tiling) {
+ points_tiling(input_points, input_size, &kd_tree, maximum_distance, boundbox);
+ }
+ else {
+ for (size_t i = 0; i < input_size; i++) {
+ BLI_kdtree_3d_insert((KDTree_3d *)kd_tree, i, input_points[i]);
+ }
+ BLI_kdtree_3d_balance((KDTree_3d *)kd_tree);
+ }
/* Assign weights to each sample. */
- std::vector<float> weights(input_points->size(), 0.0f);
+ Vector<float> weights(input_size, 0.0f);
for (size_t point_id = 0; point_id < weights.size(); point_id++) {
points_distance_weight_calculate(&weights,
point_id,
@@ -222,19 +232,19 @@ static void weighted_sample_elimination(Vector<float3> const *input_points,
/* Remove the points based on their weight. */
#ifndef CYHEAP
Heap *heap = BLI_heap_new_ex(weights.size());
- std::vector<HeapNode *> nodes(input_points->size(), nullptr);
+ Vector<HeapNode *> nodes(input_size, nullptr);
for (size_t i = 0; i < weights.size(); i++) {
- nodes[i] = BLI_heap_insert(heap, weights[i], POINTER_FROM_INT(i));
+ nodes[i] = BLI_heap_insert(heap, -weights[i], POINTER_FROM_INT(i));
}
#else
cy::Heap heap;
- heap.SetDataPointer(weights.data(), input_points->size());
+ heap.SetDataPointer(weights.data(), input_size);
heap.Build();
#endif
- size_t sample_size = input_points->size();
- while (sample_size > output_points->size()) {
+ size_t sample_size = input_size;
+ while (sample_size > output_size) {
/* For each sample around it, remove its weight contribution and update the heap. */
#ifndef CYHEAP
@@ -266,15 +276,20 @@ static void weighted_sample_elimination(Vector<float3> const *input_points,
}
/* Copy the samples to the output array. */
- size_t target_size = do_copy_eliminated ? input_points->size() : output_points->size();
- for (size_t i = 0; i < target_size; i++) {
+ size_t target_size = do_copy_eliminated ? input_size : output_size;
#ifndef CYHEAP
+ /* We need to traverse in the reverted order because we want
+ * to first have the points that are more isolated (lower weight). */
+ for (int i = target_size - 1; i >= 0; i--) {
size_t index = POINTER_AS_INT(BLI_heap_pop_min(heap));
+ output_points[i] = input_points[index];
+ }
#else
+ for (size_t i = 0; i < target_size; i++) {
size_t index = heap.GetIDFromHeap(i);
-#endif
- output_points->data()[i] = input_points->data()[index];
+ output_points[i] = input_points[index];
}
+#endif
/* Cleanup. */
BLI_kdtree_3d_free((KDTree_3d *)kd_tree);
@@ -283,38 +298,57 @@ static void weighted_sample_elimination(Vector<float3> const *input_points,
#endif
}
+static void progressiv
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list