3
$\begingroup$

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

enter image description here

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.

enter image description here

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

$\endgroup$
4
  • 1
    $\begingroup$ I'm sorry, it's hard to understand, what you are aiming for. Could you please explain it a little bit clearer. A picture, of how it should look like would help. $\endgroup$ Apr 10, 2022 at 22:11
  • $\begingroup$ I think, now I understand your question. As soon as it is reopened, I can make a proposal, that works without sorting. Well, it depends on your preconditions, if this will be a solution for you. More concrete: Do you necessarily need the points as an input from outside or may they be created in your nodes setup? $\endgroup$ Apr 11, 2022 at 14:26
  • $\begingroup$ Sure, if you know a way to achieve something like this using other methods I would greatly appreciate it. (The precondition is that the start and end points are random particles on plane/object) $\endgroup$
    – jst kiko
    Apr 11, 2022 at 14:31
  • 2
    $\begingroup$ More sorting algorithms in this recent thread: blender.stackexchange.com/q/264857/60486 $\endgroup$ May 30, 2022 at 15:23

3 Answers 3

3
$\begingroup$

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:

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:

sort position of points by distance

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.

Index Points

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

High resolution line

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.

mapping the high res line

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

reading the positions

$\endgroup$
1
  • 1
    $\begingroup$ Sorry for not noticing this post before, nice solution. It should work faster than my solution since the quadratic complexity node is no longer needed. :) $\endgroup$
    – jst kiko
    May 7, 2022 at 15:48
4
$\begingroup$

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.

enter image description here

The main nodes look like this:

enter image description here

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

enter image description here 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: enter image description here

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

enter image description here

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:

enter image description here (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:
enter image description here

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:

enter image description here

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:

enter image description here (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:

enter image description here

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:

enter image description here

$\endgroup$
6
  • 1
    $\begingroup$ Nice solution. I especially like the way to sort a list. +1 It is (i+0), because you set the ID based on the index, which starts at 0, while min(ID) in your python is 1. $\endgroup$ Apr 29, 2022 at 15:28
  • $\begingroup$ If you would iterate over the sorted meshline instead of iterating over your original points at the end, then you could use the ID as an index to transfer the position from your original points. This way you could eliminate the "transfer by id" group. $\endgroup$ Apr 29, 2022 at 16:33
  • $\begingroup$ I don't know if I just don't understand or it doesn't work, the ID field of sorted mesh line si sorted so you get [0,1,2,3,4,5...] and that is just the index so it won't sort other fields. Tried it and had no luck is there a way you could send me a screenshot? $\endgroup$
    – jst kiko
    Apr 29, 2022 at 20:58
  • $\begingroup$ Maybe, I misinterpreted your solution. I will give it a try and come back to you. $\endgroup$ Apr 29, 2022 at 21:09
  • 1
    $\begingroup$ It seems you can remove those two nodes because the positions don't change between nodes (1) and (2): i.imgur.com/zRjE9tZ.png Other than that quite a cool work, especially the resulting animations! $\endgroup$ May 30, 2022 at 15:22
1
$\begingroup$

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.

Geometry Nodes net

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.

Place points with even index

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: enter image description here

And this is the result:

enter image description here

$\endgroup$
1
  • $\begingroup$ Thank you for your answer, but this is insufficient, the start and end points are origin points of objects created by a cell fracture effect. So I can't simply ray-cast points from start positions to points on other object following the rule that each end point needs to be closer/further then the previous. Sorry for not mentioning this, I tried to keep the question as general as possible. $\endgroup$
    – jst kiko
    Apr 12, 2022 at 7:35

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .