Geometry Nodes: Poisson disk point distribution node/method

This patch does two things:
* Introduce a Seed to the random distribution method
* Bring in a new distribution method for the point scattering node

Patch Review: https://developer.blender.org/D9787

Note: This commit doesn't not handle doversion. Which means that users
need to manually update their files that were using the Point Distribute
node and reconnect inputs to the "Maximum Density" socket.

Original patch by Sebastian Parborg, with changes to not rely on the cy
libraries and overall cleanup.

Patch review by Jacques Lucke, besides help with the new "heap" system
that was required for this algorithm.

Based on Cem Yuksel. 2015. Sample Elimination for Generating Poisson Disk
Sample. Sets. Computer Graphics Forum 34, 2 (May 2015), 25-32
http://www.cemyuksel.com/research/sampleelimination/

1 files changed, 19 insertions, 0 deletions

diff --git a/source/blender/blenlib/intern/BLI_kdopbvh.c b/source/blender/blenlib/intern/BLI_kdopbvh.c
index f126c5a977b..0f90ad3a490 100644
--- a/source/blender/blenlib/intern/BLI_kdopbvh.c
+++ b/source/blender/blenlib/intern/BLI_kdopbvh.c
@@ -1076,6 +1076,25 @@ float BLI_bvhtree_get_epsilon(const BVHTree *tree)
   return tree->epsilon;
 }
 
+/**
+ * This function returns the bounding box of the BVH tree.
+ */
+void BLI_bvhtree_get_bounding_box(BVHTree *tree, float r_bb_min[3], float r_bb_max[3])
+{
+  BVHNode *root = tree->nodes[tree->totleaf];
+  if (root != NULL) {
+    const float bb_min[3] = {root->bv[0], root->bv[2], root->bv[4]};
+    const float bb_max[3] = {root->bv[1], root->bv[3], root->bv[5]};
+    copy_v3_v3(r_bb_min, bb_min);
+    copy_v3_v3(r_bb_max, bb_max);
+  }
+  else {
+    BLI_assert(false);
+    zero_v3(r_bb_min);
+    zero_v3(r_bb_max);
+  }
+}
+
 /** \} */
 
 /* -------------------------------------------------------------------- */