Blender Stack Exchange is a question and answer site for people who use Blender to create 3D graphics, animations, or games. It only takes a minute to sign up.
Sign up to join this community
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?
This is an implementation of the Reservoir Sampling Algorithm. It will select exactly k out of n.
Overview:
The group node:
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.
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:
Next, we randomly replace the selected points by points 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.
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:
Finally, we can make our selection by choosing those original points, that have a selection marker assigned:
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.
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:
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$:
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:
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$:
As you can see at around $m=5 n\ln(n)$ the algorithm should be working over 99.999 % of the time.
Here is my attempt. Create a mesh line with length of n points, then replace position of each point by distributed ones:
