Node setup (or formula) to select a given fraction of integers from a set
Another method is to multiply the integer by the golden ratio ( (sqrt(5)+1) / 2 ) and check the decimal part for some condition. This might be useful if you are looking for a more randomized selection.
Thatās the principle of an additive recurrence low-discrepancy sequence in 1D, isnāt it (exept without wraping around to a 0-1 range by taking the integer modulo 1)?
see also: https://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/
In fact Iāve recently implemented that (a low-discrepancy sequence of that type, only using a different irrational number, namely the so-called plastic ratio instead of the golden) in 2D in geometry nodes myself:
Compute n entries of a two-dimensional low-discrepancy sequence apparently referred to as weyl sequence by some authors:
[Blender 2.41]
edit: Iāve just realized the Repeat Zone -Input/-Output named āIterationā here is completely unneccessary, you can obviously omit that (and the conneted Math -node). It probably ended up in there for Iām just so used to oftentimes needing to access the current iteration in loops.
The above nodegroupās contents:
greetings, Kologe
As silly as it sounds, when I was working on this problem I did not know which keywords to Google so I came up with the math on my own. But itās nice to see a rigorous proof of my formula. I chose phi because I had read that it was the most irrational number, so I figured it had the lowest chance of generating repeating sequences. (Funfact: this is the reason the golden ratio, and thus the Fibonacci sequence is so common in nature)
Calculate the smaller (unsigned) angle between two vectors. Unsigned herein means it doesnāt differentiate clockwise- and counterclockwise direction. Works for 2D and 3D vectors.
Note the input vectors must be normalized (but you can switch on normalization within the nodegroup itself for convenience).
The method used here is robust against roundoff-errors for small angles, other than some altenatives (see the research paper its from, Ā§12).
[Blender 4.0.2 (should probably work at least as early as Blender 3.0) ]
Unsigned_Min_Angle__#00.blend (752.8 KB)
.
Doesnāt sound silly at all.
Recently I meant to wire up a formula to determine the circumcenter of an arbitrary tetrahedron. Long story short, within the dozens of Math- and Vector Math -nodes this afforded, I must have messed it up somewhere and it didnāt deliver.
First I tried to hunt for the bug a while, I eventually figured there has to be a simpler way. So I gave it some thought and figured:
No question somebody figured this out like millennia earlier than me, but sometimes figuring it out by oneself is easier than dealing with abstract formulas.
greetings, Kologe
Compute the circumcenter of an arbitrary tetrahedron from the vertex-position-vectors denoted (v0, v1, v2, v3).
Important note: You need to use a Sample Index -node to evaluate the result, else it will trip over the field-evaluation and deliver a default-vector of [0,0,0].
[Blender 4.02, should probably work at least as early as 3.0]
Circumcenter_Tetrahedron__#00.blend (902.9 KB)
After it turned out the trigonometric approach as outlined above seems to have trouble w.r.t. precision of float-arithmetic (and its tricky to determine on which āsideā of a face the tetrahedronās circumcenter must be), I again looked for alternatives.
Now Iāve settled for the matrix-math based approach (though multiplied out, given matrix-sockets, let alone -nodes arenāt there yet). See http://rodolphe-vaillant.fr/entry/127/find-a-tetrahedron-circumcenter
Much less convoluted than the first algo I tried.
greetings, Kologe
This is pretty trivial at its core, I almost feel silly posting about it, but here goes:
A hacky way of evaluating a Repeat -zone only until a condition is met (and you donāt know when or if at all this will be the case) or the hardcoded maximum of iterations have been run.
[Blender 4.01]
So its almost the equivalent of the following python for-loop:
for i in range(7):
i *= 2
if (i > 5):
break
else:
# Do some pothentially costly operation here
subdivide()
In fact it is of course the equivalent of this rather:
for i in range(7):
i *= 2
if (i > 5):
pass
else:
# Do some pothentially costly operation here
subdivide()
Anyway, I would obviously rather an actual break -condition on the Repeat -zone, which could stop the evaluation of remaining iterations for real, but for now I figured this is the best we can do.
At least it makes the Repeat -zone twiddle its thumbs and do nothing throughout the remaining iterations.
While itās all not really a proper break -condition nor a proper while -loop, in some situations it can be useful (e.g. perform a random walk until arrived within threshold of target-position or exhausted, maximum number of steps).
greetings, Kologe
Random Permutation on a given Domain:
[Blender 4.0]
Random_Permutation__#00.blend (891.3 KB)
This creates a random permutation of the indices on a given domain.
(Currently hardcoded to the Face Domain, but the 2, 3 internal changes needed to make it work on any other domain are trivial.)
Importantly, this creates a proper permutation, where nothing appears multiple times or is dropped altogether, and any element has uniform probability to end up in any place (including where it originated from)*.
So, less formally, this is like shuffling a deck of cards, while just evaluating the Random Value -node set to Integer and Max set to (Domain Size) - 1, can easily evaluate to the same random number on multiple indices.
Iterations Cutoff allows to only calculate the permutation for the first m entries for a Domain Size = n, where m <= n.
This way, if you e.g. mean to draw just a few random samples, you need not waste time on first computing the entire permutation (over the entire Domain).
greetings, Kologe
*This under the assumption geometry nodeās Random Value -node creates uniformly distributed, unbiased random integers (I wouldnāt know, but trust the devās competence).
Please, donāt use Repeat loops for this. In blender 4.1+ there is Sort Elements node for this propose.
in 4.0 you can use Points to Curvesā weight to sort things:
I have it on my radar, though I didnāt yet play around with 4.1 just yet.
So Iām, not entirely sure right now off the bat, how exayctly the Sort Elements -node helps here? Especially so in terms of avoiding the Repeat Zone?
Isnāt it such that the Sort Elements -node needs a āreference sorting orderā fed into its Sort Weight -Input Socket to begin with?
You made me curious enough to download 4.1 Beta and try:
Hereās a quad subdivided once (hence 4 faces in total). Muting/unmuting the Sort Element -node doesnāt change which Face has Index 3.
edit3: This is admittetly an irrelevant corner case, never mind.
Am I missing something?
edit2: OK, I guess you two are correct, it can be done without Repeat Zone after all (yet the result will be biased then, see post #34).
edit: @zeroskilz: Nice setup, but isnāt that susceptible to the same pitfall as any direct usage of the Random Value -nodeās output, in so far as the aforementioned might just output the same random vector multiple times (several hence colocated points, hence identical weights, hence it falls apart)?
greetings, Kologe
Like so:
Irrelevantā¦ there will always be a 1 to 1 mapping so even if values are the same, the sort will still have to pick an index.
I see, thanks.
Which leads us to the interesting detail-question of how does it pick an index in that case. Is that deterministic? Does it result in uniform probability?
@HooglyBoogly: I hope you donāt mind my pinging you, but I suspect you might be able to give some insight here.
Iām not arguing against your suggestions @zeroskilz & @mod1 (since I realized how that works), Iām only wondering. In case of doubt, Iāll put my trust in Fisher-Yates.
It remains to be tested to what the performance-impact of the Repeat Zone amounts in practice for large inputs.
greetings, Kologe
As result of Random Value is uniform, result of sort with Random Value Weight will be.
Yes, if there is multiple elements with the same Weight when order will depend on original indices of elements.
If the latter is true, the former cannot be.
For n elements, let n=3, there should be a probability p = (1/3) * (1/3) * (1/3) = (1/27) to get three times the same random value/weight.
Or maybe it would rather be p = (1/q) * (1/q) * (1/q) = (1/(q^3)), where q = number of distinct floating-point values representable. If so, the bias would be accordingly even worse, I suppose.
So the probability to get the permutation [1,2,3] from the input [1,2,3] is p = (1/27).
All possible (distinct) permutations of three elements amount to 3! = 6.
If we produce all 3! possible distinct permutations with equal probability, any given permutation should by inversion be produced with a probability p*= (1/3!) = (1/6) instead (which of course applies to the permutation [1,2,3] as any other).
Or is it me and my math (or logic) is wrong here?
greetings, Kologe
Thereās something wrong in your calculations. The random numbers used in the sorting approach donāt represent the original IDs. So you donāt produce [1,2,3] to maintain the original permutation. You produce 3 random numbers each in the range 0 to 1. The original permutation is kept, if the first random value a <= second random value b <= third random value c. But letās further reduce the problem and assume n=2. The permutation [1,2] is kept if
first random value a <= second random value b
This overall probability is
P(a<=b) = Integral(x over possible values of a){P(b>=x)/P(a==x)}
This integral on the continuous range of [0:1[ evaluates to 0.5, which is also the probability of keeping the permutation (the only other permutation is [2,1]). On discrete random number generators you get a slight bias. Letās assume we can generate random numbers with one digit after the comma. So the possible values are 0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8 and 0.9. Those are 10 possible values. The integral can be computed as a sum.
P(a<=b) = (P(b>=0.0)/P(a==0.0) + P(b>=0.1)/P(a==0.1) + P(b>=0.2)/P(a==0.2) + ā¦ + P(b>=0.9)/P(a==0.9))/10
P(a==?) = 0.1, since we can produce 10 different numbers.
P(b>=x) = 1-x
So P(a<=b) = 0.55
The more resolution the discrete numbers have, the smaller the error and the closer the result to the real probability of 0.5.
Yes, I see. I misstakenly assumed the original order was only kept if a==b==c for random numbers a, b, c.
OK, this makes more sense.
For the record, I never claimed any of the first two assumptions, nor debated the third, thatās maybe a missunderstanding or poor phrasing on my part.
This all makes perfect sense, thank you for taking the time to even bother to go through it all and also write it up. I appreciate that.
That said, what bugs me nonetheless are the following statements from the wikipedia-entry on Fisher-Yates:
Comparison with other shuffling algorithms
[ā¦]
Sorting
An alternative method assigns a random number to each element of the set to be shuffled and then sorts the set according to the assigned numbers. The sorting method has the same asymptotic time complexity as FisherāYates: although general sorting is O(n log n), numbers are efficiently sorted using Radix sort in O(n) time. Like the FisherāYates shuffle, the sorting method produces unbiased results. However, care must be taken to ensure that the assigned random numbers are never duplicated, since sorting algorithms typically do not order elements randomly in case of a tie.[11]
In other words, I think we have established:
Random Value -node set to Float produces a field of uniform probability, yet generally non-unique floats.Sort Elements -node fed a random weight as produced by Random Value -node set to Float, sorts the input according to those weights (== exactly what wikipedia refers to as alternative using sorting).Sort Elements -node fed a random weight as produced by Random Value -node set to Float, does not order elements randomly in case of a tie, but falls back to original order instead.Hence either wikipedia is wrong (and so is the source points to), or one of the above assumptions must be wrong, or I must insist Fisher-Yates gives an unbiased permutation, where Sort Elements/Points to Curves -node does not.
Taking a look at the source from wikipedia, we find (Oleg Kiselyov - āProvably perfect random shufflesā):
A commonly used shuffle algorithm attaches random tags to elements
of a sequence and then sorts the sequence by the tags. Although this
algorithm performs well in practice, it does not achieve the perfect
random shuffling.Let us consider the simplest example (which happens to be the worst
case): a sequence of two elements, [a b]. According to the
shuffle-by-random-keys algorithm, we pick two binary random numbers,
and associate the first number with the āaā element, and the second
number with the ābā element. The two numbers are the tags (keys) for
the elements of the sequence. We then sort the keyed sequence in the
ascending order of the keys. We assume a stable sort algorithm. There
are only 4 possible combinations of two binary random
numbers. Therefore, there are only four possible tagged sequences:
[(0,a) (0,b)]
[(0,a) (1,b)]
[(1,a) (0,b)]
[(1,a) (1,b)]
After the sorting, the sequences become:
[(0,a) (0,b)]
[(0,a) (1,b)]
[(0,b) (1,a)]
[(1,a) (1,b)]
As we can see, after the sorting, the sequence [a, b] is three times
more likely than the sequence [b, a]. That canāt be a perfect shuffle.
And indeed, if I may come back to your writeup, @FrankFirsching, for a second:
We can indeed rephrase this as being a purely binary decision in this n=2 case:
a <= b is equivalent to binary value 1 (or true, if you prefer).
a > b is equivalent to binary value 0 (or false).
Hence for n=2, even if we use random floats in [0-1], rather than binary random numbers, all the reasoning from Oleg Kiselyov effectively applies all the same:
Other than Kisekyov, we herein draw only one binary random number per case:
[if (a < b) set do_not_shuffle=True]
[if (a == b) set do_not_shuffle=True]
[if (a > b) set do_not_shuffle=False]
It all leads back to what wikipedia stated:
[ā¦] sorting algorithms typically do not order elements randomly in case of a tie
And we established this to be true for the Sort Elements -node either.
Thus although my reasoning two posts above was faulty, the intuition behind it seems to hold: If the random weight sorting falls back to original order in case of a draw, the entire permutation risks to be biased (unless by chance no draw occurs).
As a closing note, I want to add the Fisher-Yates algorithm is sequential by nature (if Iām not misstaken), so I donāt think a sensible way of implementing it without the Repeat Zone can be devised. Though Iād love to be proven wrong.
OK, one more thing: I realize for typical geometry-nodes usecases, the effective bias in case of a draw inherent to Sort Elements may be negligible in practice. If you think it is for your usecase, go ahead, use the shortcut.
After all, if I explore all this in such detail, its probably 1/3 Iām stubborn, 1/3 Iām curious and 1/3 the slightly condescending tone of @mod1ās original plead to use Sort Elements rubbed me the wrong way (just a little, but no hard feelings).
greetings, Kologe
I have made an addon which contains a collection of node groups which are frequently used named T3D GN Presets. You can download it and use it for free. Check out the thread here
