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

Question

I have two sets of points and I need to connect them with curves using geometry nodes. The problem is the that curves need to connect two points based on their distance from two objects.

Example, a point from (set 1) which is closest to (object 1), gets connected to a point from (set 2) which is closest to (object 2). Then the next closest and the next...

So I use geometry proximity to get distance from object and then I would like to sort this points so that their index matches up with their proximity. If there is another workaround that, would be cool too.

The nodes are a bit messy, but this is the basic functionality I want to achieve.

Answer 1

As mentioned in my comment, following I will explain a solution based on your idea of sorting. The main difference is, that this solution eliminates the transfer by id group.

Here is my node setup:

Comparable to your solution, I start with computing the distances for all the points in both point sets. Next, I sort all positions of the points in each point set by the distance to the reference point. Finally, lines with two points are generated and the start and end points are positioned based on the sorted positions of each set.

This is the Sort Position of Points by Distance node group:

The group node first creates a set of points that represent the indices of the corresponding original point set. The IDs are set to the index values. The points are placed on the z axis with z = distance.

Next, a high resolution line is generated, on the z-axis from min(distance) to max(distance).

Then this line is mapped, as explained in your solution. The ID is transfered from the index points. Now we have a set of points with sorted original indices in the ID.

Using Transfer Attribute nodes, we can read the position of the original points sorted by distance.

Answer 2

After a few weeks I tried again using a more computer programming approach and figured it out. That being said the solution is fairly complex and future readers should probably just learn how to use python in blender, or I might have overlooked a node that makes this trivial, or a sort field node might be released in 3.2 which makes this approach completely obsolete.

But still this is as far as I know the best way to sort a field using only geometry nodes and no programming. So as stated in the question I wanted to connect two random sets of point based on their distance from an empty (picture 1). But the same approach should work for sorting any field.

The main nodes look like this:

I won't go into detail for each node, otherwise this post is going to be multiple pages long:

The get distances node has two inputs, the main object and an empty object, the node deletes all faces and edges. And it outputs all vertices (as geometry), point count and distance (between each point and the empty).

The last node "connect points node" takes the original points and two sorted fields of start and end positions. It instances curves on points and then using set position node connects the two sorted fields.

Now for the interesting nodes, the "sort list" node takes the count (len of field), any unsorted field and a resolution count. It outputs a debug geometry, the sorted list and a list of ids (index of each value for unsorted field, look at the next few pictures).

As you can see the ID list orders vertices by distance but the vertex positions are still not sorted that will be achieved with "transfer by ID" node.

The nodes for "sort list" node look this:

The main idea is placing the original field on a line, and then merge a "sorted" (i.e. normal mesh line) by distance to the field vertices. Lastly it returns the vertex positions as a sorted field. (Excuse my poor drawing, but it shows the idea of how the node works):

This works and technically doesn't add much computational complexity. I am guessing the "geometry proximity" is O(n log(n)), and the full "sort field" should overall still stay O(n log(n)). But the resolution (ie point count of the new meshline) must be carefully picked, the distance between two closest points of the original field must be larger than a distance between points of the new meshline.

Now we figured out how to sort a field, but we want to sort a second field (vertex positions) by values of the first field (distances). That is why we created the ID field, but we still need alot of work to be able to iterate over field by ID value. So what is the problem instead of "field at index" we need "index at field" node, look at the next example:

$$\text{distances}=[2.3, \, 4.7,\, 4.2,\, 4.3,\, 3.1,\, 2.1] $$ $$\downarrow \text{"sort field node"}$$ $$\text{ID}=[2, \, 6,\, 4,\, 5,\, 3,\, 1]$$ $$\downarrow \text{some math and logic}$$ $$\text{index_l}=[5, \, 0,\, 4,\, 2,\, 3,\, 1]$$ $$\downarrow \text{field at index (field=distances, index=index_l)}$$ $$\text{new distances}=[2.1, \, 2.3,\, 3.1,\, 4.2,\, 4.3,\, 4.7] $$

This way we can sort any field by another field. In python we could achieve this with the next example:

(it is not the optimal python code, but it is simple enough to be translatable to blender geo-nodes)

So next problem, Blender nodes have no loop function, but they do have field math and field logic. And we know that all "single pass" nested loops (with no exit logic) can be translated into a single loop of n^2 iterations:

Next problem we have no if statements in blender, but with compare functions we can get a Field of 0 and 1 which we can use as a multiplier of some other field and achieve the same result:

which outputs: $$[0,\, 0,\, 0,\, 0,\, 0,\, 5,\, 0,\, 0,\, 0,\, 0,\, 0,\, 0,\, 0,\, 0,\, 0,\, 0,\, 4,\, 0,\, 0,\, 0,\, 2,\, 0,\, 0,\, 0,\, 0,\, 0,\, 0,\, 3,\, 0,\, 0,\, 0,\, 1,\, 0,\, 0,\, 0,\, 0] $$

As we can see the numbers are in correct order, the only thing we need to do is get rid of all excess zeros. As far as I know the only way to delete field values is to use delete geometry node. So we "plot" our values on a mesh line and then use the not(boll_list) as delete geometry selection and we should get the desired index_l. In nodes this program looks like this:

(I am not entirely sure why in nodes instead of (i+1)==IDs[j] the program works with (i+0)==IDs[j], so if anyone wants to explore this further I would greatly appreciate it.)

Lastly, why did I go trough all this trouble to sort a list. I wanted to create a fracture and rebuild modifier. I sort of achieved the desired result:

but I didn't like the fractures intersecting, by sorting the start and end positions I managed to achieve an effect that looks like this:

Answer 3

My approach is, to create a bunch of lines and then place their endpoints randomly but sticking to a rule. Let’s say, the n-th line has the points A(n) and B(n), where A(n) belongs to target object A and B(n) belongs to target object B. Then you place A(n) so that it is further away from A than A(n-1) and correspondingly you proceed with B(n).

Here is a concrete example. To keep it simple, I placed the points along two lines pointing away from the target objects. But you could place them anywhere on a plane or an object as well. Admittedly it will be more difficult to place them on an object in the correct sequence.

First, I create some lines with 2 points. Then I place the points of these lines, that have an even index relative to object A. I do this by adding a vector to the position of A. As I use the Accumulate Field node, this vector will grow with each point.

Correspondingly I place the points with uneven index relative to object B.

The rest is “eye candy”: I place little red balls on the points related to object A and little blue balls on the points related to object B.

This is, how the Evenindex Node looks like:

And this is the result: