8
$\begingroup$

The title says it all. Let's say there are 3 mesh islands. I would like to create an attribute that captures the highest index vertex for each island. So if the first island is a triangle, 2nd a square and 3rd a hexagon, this attribute's value at index would be:

Index Highest index per Mesh Island
0 2
1 2
2 2
3 6
4 6
5 6
6 6
7 13
8 13
9 13
10 13
11 13
12 13
13 13

The problem obviously becomes greater when there are hundreds of mesh islands A loop node would solve this easily but without it, I feel like this is unachievable. Can someone confirm this is indeed the case? Or maybe there is a solution?

Thanks

$\endgroup$
2
  • $\begingroup$ What if vertices will be mixed? $\endgroup$
    – Crantisz
    Commented May 6, 2022 at 14:14
  • $\begingroup$ If your question has been solved, please be so kind and mark the answer that contributed to the solution as "Accepted answer". This will make it easier for others to see which path leads to the solution, and the question will no longer show as unsolved. Thank you! Here you can find more information: What should I do if someone answers my question?. If you still haven't gotten a solution to your question, please be kind enough to address it. $\endgroup$
    – quellenform
    Commented Oct 4, 2022 at 18:20

3 Answers 3

9
+100
$\begingroup$

This one works even when the indices are scrambled between the mesh islands.

Node Setup

In the following table, the column Viewer is the mesh island index and the ID is the calculated max point index within the concerning island:

solution

It uses, what I call the Array Pattern. I already used this technique in the thread Select a subset of points in geometry nodes?.

The Array Pattern

Geometry nodes don’t provide a way, to store data in arrays. But there is a way to simulate arrays.

Imagine you stored the value of every index of an array on a line with x = index and y = 0. To store a value, you place a point that holds the data on this line. Every time, you want to overwrite the value of this index, you simply place a new point on this line. The only thing, you have to make sure is, that the new point is closer to z=0 than all points at this index before.

To read a value of a certain index, you can simply use the Transfer Attribute node, to read the data from the point, that is closest to (index, 0, 0). In certain cases you have to make sure, that the spacing of the indices is large enough, so that you don’t read the next index point instead of a data point.

Concrete Solution

We start by creating one data point for every original point. Every data point represents the index of an original point:

data points

Next, we place the data points into our array. We use the Mesh Island index of the related original point as the array index. And we calculate z to z = 1 / (index + 1). And then we simply iterate over all data points and place them into the array. This way, the point with the highest index of a mesh island will be closest to z in the corresponding index bucket. We have to add 1 to the index, because index 0 would otherwise lead to 1/0 which in blender is 0.

filling the array

Finally, we iterate over our original points and transfer the value of the corresponding array index into the ID of the original point.

reading from the array

$\endgroup$
5
  • 1
    $\begingroup$ Amazing! I need to step up my game, your solution not only allows to find the maximum, but also minimum (replace right combine XYZ with z = 1) or just nth element (calculate reciprocal again as in left combine XYZ). $\endgroup$ Commented May 6, 2022 at 22:23
  • $\begingroup$ The fabulous @André Zmuda! Welcome to the club of crazy tinkerers for crazy problems! ;-) $\endgroup$
    – quellenform
    Commented May 7, 2022 at 10:07
  • $\begingroup$ Thank you @quellenform , I feel honoured :-) $\endgroup$ Commented May 7, 2022 at 20:22
  • 1
    $\begingroup$ Clever to use 1/index, which guarantees closest $\endgroup$
    – Robin Betts
    Commented May 10, 2022 at 7:01
  • 1
    $\begingroup$ Thank you @MarkusvonBroady for the reward :-) $\endgroup$ Commented May 16, 2022 at 16:29
4
+200
$\begingroup$

I love simple solutions:

1st Variant (simple approach)

The node Accumulate Field helps you to increment an initial value of $1$.

If you additionally feed the Island Index into the input Group Index your value will be incremented group by group.

Then subtract the resulting value from your current index, add the total number of points per Mesh Island and you get the highest value per Mesh Island.

Find highest index value for each Mesh Island - Variant 1

The disadvantage: This solution does not work with jumbled indexes, but only with continuous mesh island indexes as specified here in the question.

2nd Variant (can handle scrambled indexes)

Here I first accumulate the index values, grouped by Mesh Island, and then subtract the resulting leading value from the total.

Oddly enough, then checking if the value is zero takes me exactly to the point with the highest index. Then I just use the node Switch to decide if the value should be chased through the node Accumulate Field again, to copy this index value to all other points of the Mesh Island.

Find highest index value for each Mesh Island - Variant 2 - highest Index

The essential basis for this is: The last point of a Mesh Island always has the highest index value in the Mesh Island ...can't be otherwise, because Index is a continuous value, no matter which Mesh Island it belongs to.

Funny, isn`t it?

Update: Because Markus von Broady mentioned this in a comment:

Of course, the lowest index can also be found with this simple trick, using the same funny game, just nested differently:

Find highest index value for each Mesh Island - Variant 2 - lowest Index

$\endgroup$
8
  • 1
    $\begingroup$ That's smart use of Accumulate Field! You can remove the last Subtract node, because Leading is 1 more than Trailing (i - x + y - 1 = i - x -1 + y = i - (x + 1) + y) i.imgur.com/VJHgkN7.png $\endgroup$ Commented May 6, 2022 at 14:47
  • 1
    $\begingroup$ You my dear sir, are a genius ;) Really great solution. I will not set it as an answer yet, just in case someone finds has the solution for mixed vertices $\endgroup$
    – Vic Marco
    Commented May 6, 2022 at 14:59
  • 1
    $\begingroup$ Does it actually work? Wth... $\endgroup$ Commented May 9, 2022 at 18:48
  • 1
    $\begingroup$ The bounty is ending and I finally had to sit down and analyze this answer to know the correct ordering of bounties... The Viewer (or anything else) evaluates indices in order, so the last evaluated index for each island is the highest index of that island. This is effectively what Total - Leading subtraction does: Are you last in the group? The amazing part is actually the 2nd Accumulate Field node: It only gets a single non-zero value, but it's used for earlier indices to read this value. It's an equivalent of Transfer Attribute that reads from the future! $\endgroup$ Commented May 16, 2022 at 10:40
  • 1
    $\begingroup$ @quellenform , I just now recognized your 2nd variant. This is really smart. +1 $\endgroup$ Commented May 16, 2022 at 16:50
2
$\begingroup$

While blender geometry nodes are probably not Turing complete, most questions should be possible to solve with a computer programming approach. I came up with two solutions (for "messed up" vertices), both solutions are O(n^2) so use only when necessary:

  1. Set vertex id to accumulated island vertex count
  2. Set vertex id to max index of vertex which belongs to a given island.

When you try to solve some issue, that seems impossible using just geometry nodes, it is best to first write it in some programming language that you are comfortable in (for me its python).

If you just want the solution look at this:

First sollution

Since we only want the vertex count of each island we can simply count the amount of times a certain island index value is present in the island index field.

So the python code would look something like this: enter image description here

It is very hard to implement this in geo-nodes, since the += operator does not exist. We can get around this operator by using 2 "for loops": enter image description here

The idea here is that instead of increasing a value at a index, we add 1 to a (sub array) the size of vertex count. Example, at line 29 the count_island_verts for a object definde by 3 islands with 15 vertices all together would look something like this:

$$[[1,1,0,0,0,1,0,1,0,0,0,0,0,0,0],$$ $$ [0,0,1,1,1,0,1,0,0,1,0,0,0,1,0],$$ $$ [0,0,0,0,0,0,0,0,1,0,1,1,1,0,1]]$$

after the lines 30-32 we get: $$[4,6,5]$$ or in other words the "island with index=0" has 4 vertices, "island with index=1" has 6 vertices and "island with index=1" has 5 vertices.

So the next problem is we don't have any double loop nodes, but luckily most nested loops can be turned into a single loop using some math (division and modulo operator). We also don't have a good sum function, so some trickery with accumulate field node needs to be preformed:

enter image description here

Now this example can finally be implemented in geo-nodes: enter image description here

  • The "generate islands" node just creates the islands with "shufeled" vertex indexes.
  • The "get data" node take the island and returns (island count, count of all vertices, and a island index field).
  • The "single loop" node is the python program form previous picture.
  • The "delte debug and set id" is there to make sure the mesh line form "single loop" gets computed, but not drawn on screen. This is necessary because we need some geometry to iterate over, for the math to work.
  • the rest of the nodes are self explanatory.
  1. The get data node looks like this: enter image description here

  2. The delte debug node looks like this: enter image description here

  3. And the single loop looks like this: enter image description here The frames are labeled by the same convention as the python program so I recommend you look at them side by side.

Second solution:

Again we start by the simplest program possible:

enter image description here

So here we have a similar problem, there is no way to assign a value to a field index, we are going to have to use some trickery:

enter image description here

Similarly to before we create a nested array, but now we fill it with all the vertex indexes and the we look at the max. Example for 3 islands with 15 vertices combined:

$$[[0, 0, 0, 3, 0, 0, 0, 7, 0, 9, 10, 0, 0, 13, 0],$$ $$ [0, 1, 2, 0, 0, 0, 6, 0, 8, 0, 0, 0, 0, 0, 0],$$ $$ [0, 0, 0, 0, 4, 5, 0, 0, 0, 0, 0, 11, 12, 0, 14]]$$

which give an out field:

$$\text{out}=[13, 8, 14]$$

or in other words the "island with index=0" has a vertex with max index 13, "island with index=1" has a vertex with max index 8 and "island with index=1" has a vertex with max index 14.

like before we want to turn this to a single loop and remove the max function:

enter image description here

The trick here is that we extend the each "sub array" by one so we can use it as end of line "char". Then we selectively delete unwanted values from the list until we are left with only the largest value of each "sub array". The main nodes are the same as before:

enter image description here

  • The "generate islands" node just creates the islands with "shufeled" vertex indexes (same as before).
  • The "get data" node take the island and returns (island count, count of all vertices, and a island index field)-> (same as before).
  • The "single loop" node is the python program form the previous picture (the new python program).
  • The "delte debug" is there to make sure the mesh line form "single loop" gets computed, but not drawn on screen. This is necessary because we need some geometry to iterate over, for the math to work (same nodes as before).
  • the rest of the nodes are self explanatory.

Because most nodes are the same I will only post thee "single loop" node: enter image description here This is basically just logic from the python program I recommend you look at them both side by side and you will see the similarities.

In this node group I use a "delete part of field" node, which looks like this: enter image description here It takes a field, that gets "plotted" on a mesh line. Then the unnecessary geometry gets deleted and with the use of transfer attribute we transfer the remaining field values.

All these nodes together produce the following result: enter image description here

$\endgroup$
4
  • $\begingroup$ "blender geometry nodes are Turing complete" - I would bet against it, because geonodes are not iterative. If you can make an algorithm that calculates an nth frame in the game of life, then I think you can translate this solution to solve the problem #3 here for $10 000 reward: rule30prize.org $\endgroup$ Commented May 7, 2022 at 8:46
  • $\begingroup$ I am pretty sure it is not possible to do in O(n), but like in this example you can transform double loops (ei O(n^2)) to single loops which is still gona keep the O(n^2) complexity. There is no reason you couldn't go further to triple loops O(n^3) where (for h in range(n^3): ---> k=int(h/n^2), j=int(h/n) and i=int(h%n)... This way you could theoretically solve any polynomial algorithm. I am not sure about O(x^n) type programs, so take the statement "blender geometry nodes are Turing complete" with a grain of salt. All we need is for somebody to prove PN=P :). $\endgroup$
    – jst kiko
    Commented May 7, 2022 at 10:01
  • 1
    $\begingroup$ Problem is, you can't make a simulation in Geometry nodes. You can't make a simple system where spheres gravitate and bounce because that requires calculating state and repeating... Still, I'm surprised by how much can be done (though I think it could be done more easily if more nodes were available or if the attribute statistic node had a group index like the accumulate field...) $\endgroup$ Commented May 7, 2022 at 10:25
  • 1
    $\begingroup$ Yes, you are probably right. I tried to make a ODE solver using only nodes, and it works for simulations of constant potential (V(t, r)= konst), all you need are accumulate filed nodes. I managed to sort of make it work for time dependent potential (V(t,r)=V(t)) or space dependent potential (V(t,r)=V(r)), but not both (V(t,r)=V(t,r)) which is needed for multi object gravity/charge simulations. So yes, for now I don't believe there is a way to simulate any ODE system, so I have to concede. Nodes are probably not Turing complete. But I will try again if something comes to mind. $\endgroup$
    – jst kiko
    Commented May 7, 2022 at 13:21

You must log in to answer this question.

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