12
$\begingroup$

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:

Re-sort points - Screen 1

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

Re-sort points - Screen 2

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.

I think that each approach is very different, but each also has its justification. How, when, which technique is best depends very much on the situation, but in my opinion, the technique presented by Markus' is simply ingenious, and according to my tests it works very well, which is why I mark this as the accepted answer with regard to the question posed.

I have now combined and modified all four 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

enter image description here

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

Features & Capabilities

Quadratic Sorting Resolution Sorting Circular Sorting Ramp Sorting
Reliability Perfect (?)
(Review pending)
Acceptable
(Depends on density & resolution settings)
Bad
(at higher density)
Acceptable
(Depends on density)
Performance assessment Acceptable * Good *
(Depends on resolution settings)
Perfect
(if you don't care about missed points)
Bad (!!!)
Can handle identical values 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
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: Quadratic 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

This file contains all four methods presented below, all adapted for use on point clouds (!)

$\endgroup$
5
  • 1
    $\begingroup$ 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) $\endgroup$ May 30 at 11:13
  • $\begingroup$ @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. :) $\endgroup$
    – jst kiko
    Jun 6 at 8:54
  • $\begingroup$ @jstkiko ...Thanks for your contribution, I'll do that of course! $\endgroup$ Jun 6 at 10:39
  • $\begingroup$ Nice update! However I find resolution sorting definitely more performant than quadratic sorting. $\endgroup$ Jun 6 at 19:18
  • 1
    $\begingroup$ @MarkusvonBroady ...ups, that was indeed a typo! Thanks! $\endgroup$ Jun 6 at 19:21

4 Answers 4

11
$\begingroup$

"Circular Sorting Technique"

enter image description here

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:

enter image description here

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:

enter image description here

enter image description here

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

enter image description here


Step by step to the solution

  1. 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.

    enter image description here

  2. 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.

    enter image description here

  3. 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.

    enter image description here

  4. 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.

    enter image description here

  5. With the help of this index now arbitrary values can be fetched and used in another mesh/object with the node Transfer Attribute.

    enter image description here


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.

$\endgroup$
14
  • 1
    $\begingroup$ As always - a really nice solution :-) - Another approach for sorting is described by @JstKiko in the thread Sort points by distance from object. $\endgroup$ May 28 at 7:24
  • 1
    $\begingroup$ @RobinBetts Haha, this is catch-22: actually, you can only distribute something evenly if you also have continuous indexes, right? ;-) $\endgroup$ May 28 at 10:04
  • 1
    $\begingroup$ 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) $\endgroup$ May 29 at 14:32
  • 1
    $\begingroup$ 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. $\endgroup$ May 29 at 15:20
  • 1
    $\begingroup$ @AndréZmuda By the way, there is a math node that includes the "to Radians" option. $\endgroup$ May 29 at 18:05
6
+200
$\begingroup$

Sort by two criteria: x and index, in that order, so if there's two points on the same X, the index controls order. Indices are unique so such 2 criteria are enough.

$O(n^2)$ - for each vert, entire geometry is duplicated. I don't know how it compares to convex hull algorithm, which I'd consider a hacky solution - you're relying on undocumented implementation details - still, quite awesome, so keep it coming!

(left Transfer Attribute could be replaced with Field at Index node)

Accumulate Field counts for each vertex how many other vertices are either before it on X, or exactly on the same X but have lower index. That's the number of vertices that should have lower indices, and so (in 0-based indexing) it's the desired index of the currently evaluated vertex - which is saved as ID:

For clarity, this is how you would use this data to reposition the vertices:

$\endgroup$
19
  • 3
    $\begingroup$ I like this solution. It's compact and seems to be robust. $\endgroup$ May 29 at 15:11
  • 2
    $\begingroup$ @MarkusvonBroady OK, ...then I will choose "Quadratic Sorting Technique" ...? ;-) $\endgroup$ May 29 at 15:58
  • 1
    $\begingroup$ I learned Accumulate Field from you and array technique from @AndréZmuda :D $\endgroup$ May 29 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$ May 30 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$ May 30 at 16:23
3
$\begingroup$

Resolution based sorting

Since there's another thread about sorting:

Sort points by distance from object (expanded: sort any field)

I decided it would be nice to include the solution of jst kiko so this thread is complete. However, in order to not just steal his answer, I decided to improve it to allow for multiple vertices on the same x, which requires resigning from Merge by Distance.

Since it's resolution based, the original geometry can be snapped into equal increments, and those can be scaled to be integers - this way X coordinate can be used as a Group Index in Accumulate Field to count similar X values. An additional copy of original geometry is arranged in stacks with differing Y coordinate which stores local index per stack and therefore allows for a second sorting criterion - original index. This allows to snap new vertices as in jst kiko's answer, but instead of removing overlapping vertices, remove only the excess - then snap again, this time using the stacks and supplying current local index as Y in source position.

Step 1

On the left, calculate the X coordinate by mapping the original range of this coordinate to the 0..resolution range. Then round it to the nearest integer.

On the bottom, just reposition the vertices using this rounded-integer X, and change YZ to 0.

On the top, additionally take advantage of the coordinate being an integer, and count how many vertices land on this X. Use Trailing as Y coordinate, which is a local index of this stack. Use Capture Attribute, otherwise the Accumulate Field would be recalculated later for the new positions.

Step 2

Spawn a mesh line with resolution number of verts. Position it in the same range as the one in Map Range output in the step 1. Delete edges. Since I don't use Geometry Proximity node like jst kiko, edges don't need to be removed - still, because some vertices will be removed, if you need edges, you have to add another step at the end where you recreate the mesh line and transfer calculated positions onto it.

Snap each vertex of this "high resolution line" onto the nearest point of the original geo (with x converted to integers and YZ=0). Save that x coordinate to avoid recalculating it later. This x allows you to target the stack. Just like in step 1, calculate local index on this stack and also save it. Now search for a vert on X=stack X; Y=local index - either you find a vertex exactly there and read associated vertex'es index, or you aim too far on Y, and read last stack's vertex'es index.

Step 3

Use the obtained index of the vertex, to read the size of the stack this vertex is in. Now check if currently evaluated local index is too high for that stack - if so, remove it, as it's one of (possibly extremely many) excess vertices. Finally use the obtained index to transfer position from the original-original, untouched input geometry.

Ending remarks

The obvious flaw of this approach is that you don't know what resolution you need in order to produce correct output. If your resolution is too low, not enough verts from middle green frame "high definition mesh line" will be snapped on a stack. For example, if your geometry is a default plane with the edges subdivided, so each original edge is made of 100 verts, there's 100 verts on x=-1, and 2 verts on x=-0.98. Therefore "high definition mesh line" needs 100 verts closer to the former, at a coordinate lower than x=-0.99. So 100 verts for each 0.01, totalling 2/0.01 * 100 + 1 = 20'001 resolution.

The good news is that Suzanne lvl 2 with 7'956 vertices takes "only" 205'000 resolution to not lose any vertex in sorting, which takes only 60 ms to evaluate on my PC (ideally quellenform will measure on his PC for consistency with other tests). Resolution of 2 million takes 360 ms. 20 million: 3559 ms.

$\endgroup$
8
  • $\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$ May 31 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$ May 31 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
    May 31 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$ May 31 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$ May 31 at 19:19
2
$\begingroup$

"Ramp Sorting Technique"

enter image description here

How does this work?

This technique uses as basic mechanism the node Mesh Boolean (and likewise their disadvantages). This leads to less errors than the Circular Sorting Technique, but at extremely high density it is more computationally expensive and also not 100% error-free. Depending on the seed value, the error rate in my tests at 5000 points on 1m x 1m grid was ~0.0001%.

Roughly speaking, I extrude the points on an axis according to their value and create several slices with which I cut the enclosing shape.

Then, by separating a single edge from it and converting it into a curve, I get a line with continuous indexes that is subdivided in the intervals of the sort value.

enter image description here


Step by step to the solution

  1. First I use the node Attribute Statistics to determine the lowest and the highest value, which serves as input range for the node Map Range where these values are mapped to the range $0$ - $1$.

    enter image description here

  2. Then I reduce these points to the x-axis.

    enter image description here

  3. Next, I extrude the points along the Y-axis according to the value to be sorted.

    If I then also extrude the Z-axis, I get faces with which I split the convex hull of the slices.

    enter image description here

  4. If I then filter out the edge that runs along the X-axis and convert it into a curve, I get a curve that is divided in the distances of the points to be sorted and which has sorted indexes.

    enter image description here


Download the file and try it yourself

Important Notes: Since this technique is based on the node Mesh Boolean, but this merges vertices below a distance value, this technique may lead to unexpected results.

For normal 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.

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.
$\endgroup$
2
  • $\begingroup$ Since you're comparing, here's a dare: test all 3 solutions on Suzanne with 4 subdivision levels. :D $\endgroup$ May 29 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$ May 29 at 15:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.