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

Question

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

Answer 1

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.

Answer 2

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, 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:

Answer 3

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: