How can I re-sort the points/indexes of an object in geometry nodes?

Question

I wonder if there is a possibility to re-sort the indexes of a mesh according to a certain criterion?

Again and again in Geometry Nodes unfavorable situations arise where the point distribution or their indexes are in irregular order.

For example, I want to re-sort the points distributed on a grid with the node Distribute Points on Faces along a certain axis so that I can process them in order.

If I convert the distributed points for example with the node Mesh Line into a curve, a totally confused pattern comes out, because the indexes are distributed in a random order:

However, I would like the indexes to be sorted and numbered from right to left so I can create a line along those points:

Bonus task: The whole thing should at best also work with three-dimensional objects, because just a grid is sometimes pretty bland.

PS: I know there are "hacky solutions" out there, but that's what I really want to avoid and find a solid and as simple as possible logic based technique.

Techniques comparison

Even though it's not a contest here, I'm providing an overview of the answers below.

Each approach is very different, but each also has its justification. How, when, which technique is best depends very much on the situation.

I have now combined and modified all five techniques in such a way that they are meaningfully comparable, and run according to the following criteria:

All get as input any test value (float/integer)
All process points in the point domain
All provide the sorted index as result for further processing

(Native Sorting, Quadratic Sorting, Resolution Sorting, Circular Sorting, Ramp Sorting)

Features & Capabilities

	Native Sorting	Quadratic Sorting	Resolution Sorting	Circular Sorting	Ramp Sorting
Reliability	Perfect	Perfect (?) (Review pending)	Acceptable (Depends on density & resolution settings)	Bad (at higher density)	Acceptable (Depends on density)
Performance assessment	Perfect	Acceptable *	Good * (Depends on resolution settings)	Perfect (if you don't care about missed points)	Bad (!!!)
Can handle identical values	Yes	Yes	Yes, partially (Depends on resolution settings)	No	No

*With a few points (below ~400), Quadratic Sorting is actually faster than Resolution Sorting. However, Resolution Sorting shows its strength with many values to be sorted and clearly outperforms Quadratic Sorting!

Note: I tried to make a comparison of the timings, but since the variants work too differently in the end and that depends on too many factors, it's not really possible to do that in a meaningful way.

Advantages & Disadvantages

	Advantages	Disadvantages
Native Sorting	Captures all points, Best performance	-
Quadratic Sorting	Captures all points (?) (Review pending)	Average performance
Resolution Sorting	Performance depends on adjustable resolution	Performance/Reliability depends on adjustable resolution Has a small error rate at high density
Circular Sorting	Is ultra-fast *	"Swallows" points very easily at higher density
Ramp Sorting	-	Is computationally intensive at high density Does not work reliably at high density

*The "Circular Sorting Technique" is so fast mainly because at high density the more points are discarded and thus no real comparison to other methods can be made!

Use cases

If you set a high value on precision and no point should be lost: Native Sorting
If you set a high value on precision and you have less then ~5000 (?) Points: Quadtratic Sorting
If you need a good result, but can live with a small error rate: Resolution Sorting
If you need it really fast, and if you don't care about precise detection: Circular Sorting
If you are totally crazy and feel like experimenting: Ramp Sorting

Download the comparison and try it yourself

_{(Blender 3.2+, all methods except "Native Sorting")}

_{(Blender 3.4+, all five methods)}

These files are all adapted for use on point clouds (!)

nice comparison, though circular sorting doesn't get much slower because it just diregards more and more points. For my test of 5000 points, 4585 (91.7%) remained unsorted: i.imgur.com/9reNsbg.gif - so it's like taking my solution, removing 91.7% points, and then sorting 500 points instead of 5000 points. Still, it's a problem in itself to figure which points to remove, so I might actually use the Circular Sorting in the future... Also consider this: $\bbox[red, 5px]{\color{white}{\mathbf{NO}}}$ (color table) — Markus von Broady, Commented May 30, 2022 at 11:13
@quellenform if it wouldn't take to much of your time, could you update the question with "resolution based sorting". I would like to see how it compares to other methods. :) — jst kiko, Commented Jun 6, 2022 at 8:54
@Kuboå This setup is NOT a reorganization of the points, but only a mapping of the indices. Have a look at the file with the comparisons. There you see, for example, that in the group "_Visualize" I transfer these mapped indices with Sample Index to the positions of a line. So the sorted index only says which point should put at this index, and it depends on you what you do with this information. Does this make more sense to you? — quellenform, Commented Dec 1, 2022 at 18:24
@Kuboå So you want to know which point is on the far left? After sorting, the lowest value is the point with the index $15$, which is why it is assigned to point $0$. therefore you have to use Sample Index to fetch the sorted value, and make a comparison with the current index of the points. Something like this: i.sstatic.net/o8TQ3.png — quellenform, Commented Dec 2, 2022 at 9:06

quellenform · Accepted Answer · 2022-05-29 17:53:49Z

"Circular Sorting Technique"

How does this work?

Roughly speaking, I assign a range of the value to be sorted to a range from $0$ to $\pi$, which results in the distribution of points on a semicircle.

On the resulting shape, I apply a mesh trick that gives me a curve with ordered points.

This may sound rather muddled now, but it is really quite easy to understand if you represent it with pictures...

For example, if you distribute points on a grid with the node Distribute Points on Faces, and display the value of the X-axis on a semicircle, it looks like this:

If you now create a convex hull from the points on the semicircle and convert them back into curves, you get nicely sorted points. This works basically with arbitrary values.

Here you can see an example of sorting along the X-axis and along the Y-axis:

And this is how it looks, for example, with a grid rotating on the Z-axis:

Step by step to the solution

First of all, you define by which value you want to sort. In this example I use the X-axis and separate it from the single points.
Next I use the node Attribute Statistics to determine the lowest and the highest value, which serves as input range for the node Map Range.

I then map the values used here to a semicircle, so that the previously captured value of the X-axis is distributed along this semicircle.
Then I create a line with the node Mesh Line, whose subdivision corresponds to the number of the original points, and set their positions to the previously created positions on the semicircle.

I achieve this by simply rotating a vector with the previously obtained angle.
And now comes the crucial step: I first capture the index of each point, so that I can later determine the original index, and then I use the nodes Convex Hull and Mesh to Curve.

The ingenious thing about this is that Convex Hull forms a mesh hull around the points previously distributed on the semicircle, but this does not yet lead to the goal.

Only by using the node Mesh to Curve, this mesh is transformed into a curve, whose indexes are ordered continuously from left to right.

Since the original index was previously captured with the node Capture Attribute, a connection between the new ordered indexes and the original indexes can be established with Transfer Attribute.
With the help of this index now arbitrary values can be fetched and used in another mesh/object with the node Transfer Attribute.

Download the file and try it yourself

Important Notes: Since this technique is based on the node Convex Hull, but this ignores distances between vertices below a certain value and combines the points arbitrarily, this technique may lead to unexpected results.

For less densely distributed points it works great, but as soon as the vertices are very close to each other along the sort (or even identical), they are ignored.

in this particular case: if the points on the circle are distributed with an angle of less than $0.01°$, they will not be recognized. (Thanks to @Robin Betts for the attentive reading).

Q & A

Q: It does not work at all with my mesh! Why?
A: Since this technique counts the points in the domain Points with the node Domain Size, and a mesh returns Vertices and is not a Point Cloud, you have two options:

Either you apply the node Mesh to Points before, which converts your mesh to points.
Or you switch the contained node Domain Size from Points to Mesh.

Q: Why actually a semicircle and not a whole circle?
A: Because the numbering is finally done by converting the convex hull into a curve with the node Mesh to Curve, which uses the longest edge as a reference point for the first vertex.

As always - a really nice solution :-) - Another approach for sorting is described by @JstKiko in the thread Sort points by distance from object. — André Zmuda, Commented May 28, 2022 at 7:24
@RobinBetts Haha, this is catch-22: actually, you can only distribute something evenly if you also have continuous indexes, right? ;-) — quellenform, Commented May 28, 2022 at 10:04
For testing float accuracy, you might find this snippet useful (paste it into Python console): import numpy as np; start = 1; f"{np.nextafter(np.float16(start), np.float16(inf))-start:.10f}" - it displays the smallest possible step in float16 that Blender uses. For start = 1 it's about 0.001, but for start = 10 it's significantly bigger at 0.0078125, and for start = 0 it's only 0.000000059604644775390625 (5.96...e-08) — Markus von Broady, Commented May 29, 2022 at 14:32
Actually it's float32 not float16, Blender does use float16 in some places, but in geonodes it uses float32, so the actual numbers for start = 0, 1, 10 are roughly 1.4e-45, 1.19e-07, 9.54e-07 quite more precision. — Markus von Broady, Commented May 29, 2022 at 15:20
@AndréZmuda By the way, there is a math node that includes the "to Radians" option. — quellenform, Commented May 29, 2022 at 18:05

quellenform · Accepted Answer · 2024-04-27 18:26:51Z

"Native Sorting Technique"

Blender 3.4+

In version 3.4 there is an interesting new node, which allows a native sorting of the points of a curve based on a weighting.

The node is called Points of Curve, and returns the index of a specific point of the curve depending on the value passed.

To achieve sorting with this, first the point cloud is converted into a curve, and the sorting criterion is used as Weights for Points of Curve.

Basically all possible sorting can be done in this way:

_{(Blender 3.4+)}

Examples

Here you can find an example of use (in which, funnily enough, exactly the opposite should be generated, namely a jumble of the indices): How to randomize/shuffle indices in Distribute Points on Volume?
And here is a nice practical example that uses a texture map as a sorting criterion (thanks to @RobinBetts for this creative idea!): Sorting Indices of points circularly

As you can see: Only the value that is passed as sort criterion is decisive.

Blender 4.0+

The concept of weighting has been used in some other nodes since version 4.0, and Points to Curve is available here with precisely this feature.

This converts points into curves and uses the weighting as a criterion for the order of the points to be used.

As a result, a curve is obtained whose points are arranged exactly according to the value of the weighting.

This curve can then be converted back into points if necessary.

Blender 4.1+

Well, Blender is (fortunately) evolving, and so are the possibilities for sorting elements natively.

In simple terms, the current solution should therefore be presented with a single node without any detours:

This is great news! I'll wait for the stable version as usual, and I would hope we would just get a general sorting field already… — Markus von Broady, Commented Oct 23, 2022 at 22:06
In Blender 4.0.0 beta a new node Points to Curves is available by which the points can be sorted directly (if the original index is needed afterwards use Capture Attributecan be used). See also: link — Patter, Commented Nov 12, 2023 at 12:01
@Patter Thanks for the tip! ...I noticed it almost at the same time and updated the answer ;-) — quellenform, Commented Nov 12, 2023 at 12:04

Markus von Broady · Accepted Answer · 2023-07-28 11:57:48Z

8

+200

Quadratic Sort (Pre B3.4)

This is one of outdated answers that would unnecessarily bury (currently) objectively the best answer by quellenform. You can still access this answer by reading the previous revision.

edited Jul 28, 2023 at 11:57

answered May 29, 2022 at 12:33

Markus von Broady

42.6k3 gold badges37 silver badges107 bronze badges

3

$\begingroup$ I like this solution. It's compact and seems to be robust. $\endgroup$
– André Zmuda
Commented May 29, 2022 at 15:11
2

$\begingroup$ @MarkusvonBroady OK, ...then I will choose "Quadratic Sorting Technique" ...? ;-) $\endgroup$
– quellenform ♦
Commented May 29, 2022 at 15:58
1

$\begingroup$ I learned Accumulate Field from you and array technique from @AndréZmuda :D $\endgroup$
– Markus von Broady
Commented May 29, 2022 at 19:52
1

$\begingroup$ @RobinBetts Loops are available, just not while loops - iterating over geometry is an equivalent of for v in geo.vertices, and what I'm doing here is for i in verts: for j in verts or rather x2=x*len(x); for v in x2. Parallel may improve the speed but not complexity... And I would expect that Blender eventually will introduce Sorted Field node... But then it would be nice to have some sequence bigger than Vector to sort by more than 3 criteria... $\endgroup$
– Markus von Broady
Commented May 30, 2022 at 9:33
1

$\begingroup$ @MarkusvonBroady Only, that these for loops have some major limitations, that make life so hard: You can only change the item, that you hold in your hand; you can only see the state of your geometry before starting the loop, which makes the Accumulate Field node necessary. - Oh, I forgot - you may as well create geometry at the point, that you hold in your hand, when using the Instance on Point "loop". - We would already have much more possibilities, if we had not these limitations ;-) $\endgroup$
– André Zmuda
Commented May 30, 2022 at 16:23

| Show 14 more comments

Markus von Broady · Accepted Answer · 2023-07-28 11:53:25Z

5

Resolution based sorting (pre B3.4)

This is one of outdated answers that would unnecessarily bury (currently) objectively the best answer by quellenform. You can still access this answer by reading the previous revision.

edited Jul 28, 2023 at 11:53

answered May 30, 2022 at 22:57

Markus von Broady

42.6k3 gold badges37 silver badges107 bronze badges

$\begingroup$ Great, thanks (also to @jstkiko) for the contribution! A few more days and we have all the relevant variants of the sorting options together in one thread ;-) $\endgroup$
– quellenform ♦
Commented May 31, 2022 at 0:49
$\begingroup$ I think this could be possibly optimized: read the stack size as early as possible to remove the excess geometry first; or maybe create multiple mesh line geometries going from 0;0;0 to 0;0;0 and having vert counts of 1, 10, 100, 1000, 10000 or vert counts of 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, and then joining them as instances and instancing them on the "high res mesh line" taking log10/log2 of the stack size as instance index. The main sampling line now could have much less resolution, as verts would be added on demand... $\endgroup$
– Markus von Broady
Commented May 31, 2022 at 8:45
1

$\begingroup$ @MarkusvonBroady thank you for summarizing and improving my solution. I was offline for a couple of days so I couldn't post it myself. $\endgroup$
– jst kiko
Commented May 31, 2022 at 9:25
1

$\begingroup$ @MarkusvonBroady I have built a node, that calculates the minimum delta of an attribute. This way, you could know, which resolution you need. The only drawback is it's complexity: O(n²). Originally I intended to integrate it into the solution of JstKiko. But I didn't because of this drawback. Here you may take a look at it: min_delta_attribute.blend $\endgroup$
– André Zmuda
Commented May 31, 2022 at 19:12
1

$\begingroup$ ... and it crashes on my computer with a high number of vertices due to the grid. Maybe because I currently only have onboard graphics. If you experience the same: This could be resolved by replacing the grid with instances of meshlines and adapting the solution to it. $\endgroup$
– André Zmuda
Commented May 31, 2022 at 19:19

| Show 3 more comments

quellenform · Accepted Answer · 2023-11-15 15:34:21Z

3

"Ramp Sorting Technique"

This is one of the outdated answers that would unnecessarily bury the (currently) objectively best answer from quellenform. You can still access this answer by reading the previous revision.

edited Nov 15, 2023 at 15:34

answered May 29, 2022 at 13:59

quellenform♦

39.6k10 gold badges56 silver badges149 bronze badges

$\begingroup$ Since you're comparing, here's a dare: test all 3 solutions on Suzanne with 4 subdivision levels. :D $\endgroup$
– Markus von Broady
Commented May 29, 2022 at 14:44
$\begingroup$ I tested this without subdivision and got ~1.7 seconds, so I didn't dare to try subdivisions. The Convex Hull answer was blazing fast and was dealing even with 4 subdivision levels. Though when I decided to randomize on X a little by applying subdiv and using proportional editing - it crashed (probably even unrelated to your setup :D). My solution was very fast without subdivisions, scaled very well to one subdivision but at lvl 2 crashed :D. Though when I resign from edges (> to points > to verts) it survives lvl 2 and takes 3 seconds... $\endgroup$
– Markus von Broady
Commented May 29, 2022 at 15:11

Add a comment |

Fred I. R. · Accepted Answer · 2024-05-03 21:05:49Z

1

Another approach is to Sort Elements with a Gradient texture.

on Linear:

on Radial:

Edit: the setup:

the blend:

I hope it helps.

edited May 3 at 21:05

answered May 3 at 10:49

Fred I. R.

1,0493 silver badges12 bronze badges

$\begingroup$ From a technical point of view, this is exactly the solution I suggest in my answer for version 4.1+, because you are only adding the sorting criterion here. But a nice idea! $\endgroup$
– quellenform ♦
Commented May 3 at 11:08
$\begingroup$ @quellenform Yes, it's not revolutionary.Thanks, from you it's mean a lot... $\endgroup$
– Fred I. R.
Commented May 3 at 11:15

Add a comment |

Stack Exchange Network

How can I re-sort the points/indexes of an object in geometry nodes?