# Find highest index value for each Mesh Island. Is it possible? Geometry Nodes

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

• What if vertices will be mixed? May 6, 2022 at 14:14

This one works even when the indices are scrambled between the mesh islands. 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:  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: 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. Finally, we iterate over our original points and transfer the value of the corresponding array index into the ID of the original point. • 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). May 6, 2022 at 22:23
• The fabulous @André Zmuda! Welcome to the club of crazy tinkerers for crazy problems! ;-) May 7, 2022 at 10:07
• Thank you @quellenform , I feel honoured :-) May 7, 2022 at 20:22
• Clever to use 1/index, which guarantees closest May 10, 2022 at 7:01
• Thank you @MarkusvonBroady for the reward :-) May 16, 2022 at 16:29

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. 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. 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, isnt 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:  • 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 May 6, 2022 at 14:47
• 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 May 6, 2022 at 14:59
• Does it actually work? Wth... May 9, 2022 at 18:48
• 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! May 16, 2022 at 10:40
• @quellenform , I just now recognized your 2nd variant. This is really smart. +1 May 16, 2022 at 16:50

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: 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": 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: Now this example can finally be implemented in geo-nodes: • 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: 2. The delte debug node looks like this: 3. And the single loop looks like this: 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: 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: 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: 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: • 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: 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: 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: • "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 May 7, 2022 at 8:46
• 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 :). May 7, 2022 at 10:01
• 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...) May 7, 2022 at 10:25
• 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. May 7, 2022 at 13:21