5
$\begingroup$

I have a geometry consisting of a number of (say, $n$), points.

I would like to select a subset of $k < n$ points and construct instances on them using Instances on Points. How to do this?

I know there is a "selection" I can use for Distribute points on faces, but how do I use it to select exactly $k$ points at random?

$\endgroup$
2
  • $\begingroup$ do you have a specific property you want to use to select the k points, or do you just want k selected at random? $\endgroup$ Apr 24, 2022 at 20:04
  • $\begingroup$ I want them selected at random $\endgroup$
    – sygi
    Apr 24, 2022 at 21:39

4 Answers 4

8
$\begingroup$

This is an implementation of the Reservoir Sampling Algorithm. It will select exactly k out of n.

demo

demo 2

Overview:

node net

The group node:

group node

The Reservoir Sampling Algorithm

Here is the pseudo code from Wikipedia:

> (* S has items to sample, R will contain the result *)
> ReservoirSample(S[1..n], R[1..k])
>   // fill the reservoir array
>   for i := 1 to k
>       R[i] := S[i]
>
>   // replace elements with gradually decreasing probability
>   for i := k+1 to n
>     (* randomInteger(a, b) generates a uniform integer from the inclusive range {a, ..., b} *)
>     j := randomInteger(1, i)
>     if j <= k
>         R[j] := S[i]

The algorithm starts with selecting the first k elements. R is an array, that stores the selection. S is the set of all points. Then, it goes through all other points and substitutes randomly one of the selected elements in R by the current point. In the end, R holds the selected points.

As indices in geometry nodes start with 0, we have to slightly modify this algorithm.

Implementing the Algorithm

Geometry nodes don’t provide a way, to store data in arrays. Thus, we need a substitute for it. Instead, we use a meshline with k points, to store the selection. I call them selection marker. Additionally, we create a meshline with n points, that represent the indices of the original points. To mark an index as selected, we place the corresponding point on the position of the selection marker. To be precise, we don’t place the index point exactly on the selection marker, but a little above. I will explain later, why we do it like this.

The following image shows the selection of the first k elements:

Selecting the first k elements

Next, we randomly replace the selected points by points from k+1 to n:

select randomly from k+1 to n

But geometry nodes do not allow us to change other elements, than the one we currently access through the context. This means, we can’t overwrite the already selected. Instead, we place every new selection closer to the selection marker than the ones before by using an Accumulate Field node. And this is the reason, why we did not place the selected index points exactly on the selection marker.

overwriting selection

Now, that we have made our selection, we can place the selection marker points right on the selected original points. Therefore, we read the index from the index point, that is closest to the selection marker point and use this to read the position from the original point:

Place selection markers

Finally, we can make our selection by choosing those original points, that have a selection marker assigned:

Do the selection

$\endgroup$
3
  • 2
    $\begingroup$ This looks heroic.. I've been racking my brains trying to figure out how to do this without iteration :) $\endgroup$
    – Robin Betts
    Apr 25, 2022 at 19:11
  • $\begingroup$ Wish I could UV this twice! Mine is occasionally failing.. Convex Hull isn't doing the perfect job. Needs work :) $\endgroup$
    – Robin Betts
    Apr 25, 2022 at 20:07
  • $\begingroup$ Thank you, @RobinBetts :-) - I like your solution, as well. It's clever and compact. And to be honest, my brain feels boiled now ;-). $\endgroup$ Apr 25, 2022 at 20:12
3
$\begingroup$

Node Group to accomplish goal

Blender's Geometry Nodes don't handle random values very well, so you have to settle for an approximation. This node group will give any given instance a change of $k$ out of $n$ of being selected. That's not exactly what you want, but getting exactly $k$ is not really possible.

The example just instances Suzanne on a grid. $N$ is the number of points available on the grid, so it's calculated from the grid's X and Y counts. $k$ is a value you set in the "Make Random Selection" box. The randomness is generated by using each grid point's index as a seed for the random number generator. The selection logic is fairly straightforward and the output of the less than node is a Boolean that affects the selection variable.

$\endgroup$
2
$\begingroup$

I have found another solution that is simpler than André Zmuda solution. Though it does still suffer from some statistical approximations like Marty Fouts solution, but the "mistakes" are much less prominent.

The shuffle method:

The idea is to randomly shuffle a selection filed that consists of $k$ ones and $n-k$ zeros. This can be achieved with field at index node, if the index list is randomly distributed.

All nodes together look like this: enter image description here

We start by crating a field of length $m$ that consists of elements $\in\{0, 1, \dots (n-1)\}$. Length $m$ must be large enough for all $n$ elements to be present in the field (from my testing I recommend $m\approx 5n \ln(n) $, more information at the end). Then we "plot" these values on a line and delete duplicates using merge by distance node. If $m$ was sufficiently large we should be left with a filed of length $n$. We can than use this field to randomly shuffle any input field using transfer by index node.

Example, $n=10$, $k=3$, $m=15$:

  1. We generate the random list -> $[3, 1, 0, 9, 1, 7, 8, 7, 2, 5, 4, 6, 0, 4, 1]$
  2. Generate a bool list (index<$k$) -> $[1, 1, 1, 0, 0,0,0,0,0, 0]$
  3. Remove duplicate form first list ->$[3, 1, 0, 9, 7, 8, 2, 5, 4, 6]$
  4. transfer "bool list" by index -> $[0, 1, 1, 0, 0, 0, 1,0,0,0] $
  5. Use this list to select instances.

Picking the right $m$:

We want to know the probability of $n$ different elements being present in selection of $m>n$ elements. I tried to solve this problem analytically, but I am not even sure if analytical solution exists so instead I ran a few simulations:

enter image description here

From the graph we can see, that by doubling $n$ the lines move by a constant amount to the right -> $ln(n)$ factor. The x axis of the graph is also scaled by $1/n$ so this give us the proportionality $n \ln(n)$. Lastly we need the constant which is dependent on how wrong we allow the program to be.

At $n=50$:

  • If $m\approx 310$, then 1 in 10 seeds will give a wrong result. -> scalar factor= 1,6
  • If $m\approx 420$, then 1 in 100 seeds will give a wrong result. -> scalar factor= 2,1
  • If $m\approx 525$, then 1 in 1000 seeds will give a wrong result. -> scalar factor= 2,68
  • If $m\approx 700$, then 1 in 10000 seeds will give a wrong result. -> scalar factor=3,58
  • If $m\approx 825$, then 1 in 100000 seeds will give a wrong result. -> scalar factor=4,2

As you can see at around $m=5 n\ln(n)$ the algorithm should be working over 99.999 % of the time.

$\endgroup$
1
  • $\begingroup$ Very interesting approach. +1 $\endgroup$ May 9, 2022 at 19:56
0
$\begingroup$

Here is my attempt. Create a mesh line with length of n points, then replace position of each point by distributed ones:

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ This always selects the first k points and not random k points. $\endgroup$ Apr 26, 2022 at 5:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .