20
$\begingroup$

Say I got some points distribut on a sphere, how could I get the distance of each point to its nearest point, for example, in pic 1, there is a point A, and its nearest point is B, and what I want is the distance r_A, and for each point X, I need an r_X. enter image description here

The Geometry Proximity node do provide a distance value, but for each point, the value is 0, if I use a Map Range node to invert the values, the values I got for the points is the maximum setted in Map Range node. enter image description here enter image description here

Could I make this in GN?

$\endgroup$
1
  • 1
    $\begingroup$ unfortunately AFAIK this isn't possible with geometry nodes at the moment. But hopefully will be possible in the future. If you can't wait and want to do it anyway and you are willing to learn something new you should have a look to animation nodes. This amazing add-on can do such things. $\endgroup$
    – Chris
    Commented Dec 25, 2021 at 8:51

3 Answers 3

28
+500
$\begingroup$

Since the nodes have evolved a lot over time, there are now more solutions available:

  • For Blender 3.6+ ...just follow this guide
  • For Blender 3.4+ check out @Patter's answer below
  • For Blender 3.1+ use "The shortest edge trick"

...and if you want to get an overview of which node is available in which Blender version, follow this answer: Can't find the node! Which node is available in which Blender version?

Find Nearest Point (Blender 3.6+)

With Blender version 3.6 a new node is available that makes this task a lot easier: Index of Nearest.

In this case, the node simply returns the index of the nearest element, which makes it just as easy to query its position with Sample Index:

enter image description here


(Blender 3.6+)

"The shortest edge trick" (Blender 3.1+)

...that's what I call this technique now.

In contrast to the quadratic complexity approach, this technique offers the advantage that only a fraction of the vertices necessary for the calculation is created, since only a triangulated mesh is used as a basis.

So this approach has a clear advantage in terms of speed, especially when the number of points to be calculated is high (500+).

How does it work?

The basic idea here is to shorten all edges between the points proportionally, and thus find the closest point. This method saves a lot of calculations and complexity and is basically applicable to any shape (grid, sphere, cube, etc.):

In the case of a grid with slightly offset points, the principle of operation is simplified as follows:

How could I get the distance of a point to its nearest point - Concept

If the points are now moved, the edge length changes, which always takes the shortest path due to triangulation:

How could I get the distance of a point to its nearest point - Concept Animation

The only necessary basis is therefore to always have an optimally triangulated mesh as a starting point.

Depending on the type of mesh, this can be achieved in different ways.

  • In the case of a sphere you can simply use the node Convex Hull.
  • If you are using a grid with the Distribute Points on Faces node, you can achieve the triangulated mesh with the example I outlined in this answer: Selectively join points using geometry nodes
  • And for other shapes you can use various other tricks.

The rule is simply: if the points are connected at least once over the shortest distance by an edge, then you already have the necessary information.

What is the result?

In this concrete example, the solution applied to a sphere looks like this in the final result:

How could I get the distance of a point to its nearest point - Animation 1

How could I get the distance of a point to its nearest point - Animation 2

Step by step to the solution

  1. First create your points with Distribute Points on Faces.

    How could I get the distance of a point to its nearest point - Step 1

  2. In the case of a sphere, the Convex Hull node makes it easy to obtain the required triangulated mesh without missing a point. For other shapes, it is best to create the mesh using the Triangulate (Shortest Diagonal) node.

    How could I get the distance of a point to its nearest point - Step 2

  3. Using the nodes Extrude Mesh, Split Edges and Separate Geometry you get the isolated edges of this mesh.

    How could I get the distance of a point to its nearest point - Step 3

  4. Then reduce the scale of each edge by half.

    How could I get the distance of a point to its nearest point - Step 4

  5. Now that the edges are reduced in proportion to their length, you can reliably find the nearest point with the node Geometry Proximity. If you then calculate the direction vector between your originally created points and the position results of Geometry Proximity, you will know in which direction the shortest vector points.

    How could I get the distance of a point to its nearest point - Step 5

  6. In the last step you only have to correct the length. Since you have shortened the edges by 50% before, you simply scale the direction vector by $4$, which is exactly the point you were looking for (Apart from a few minor rounding errors).

    How could I get the distance of a point to its nearest point - Step

The final result is this (Each previously created point is here connected to the nearest point):

How could I get the distance of a point to its nearest point - Result

...and with animated Seed/Density it looks like this:

How could I get the distance of a point to its nearest point - Animation 3

Here is an overview of the node group:

How could I get the distance of a point to its nearest point - Node Group

Here is the blend file (I added an additional view for debugging):


(Blender 3.1+)

...and as a bonus I added the animation to the blend file too, because it's so nice to see the thing in motion (even though I won't win any beauty contests with the node tree, but it's meant as a little animation example).

Useful Hints

  • This solution works best by converting a mesh into triangles with the shortest edge length! Quads are less suitable here, because they may produce false positives.
  • If you do not use a sphere, it is best to create the mesh using the Triangulate (Shortest Diagonal) node.
  • If you use a sphere, this works best with a sphere of the type Ico Sphere in a higher resolution.
  • Remember: If you use a sphere like in this example, the calculated distance is of course also the shortest straight path between the points. The real distance on a sphere would actually be the angle between the points multiplied by the radius of the sphere. The angle is obtained with the formula: $\alpha = 2 \ast \arcsin (\frac {s}{r \ast 2})$
  • If you get false positive results with this method due to closely spaced points or highly stretched triangles, simply change the scaling. For example, instead of first reducing the length with a factor of $0.5$ and then multiplying by $4$, you can reduce by a factor of $0.8$ and then multiply by $10$.
$\endgroup$
7
  • 2
    $\begingroup$ You second animated image is like a magnetic solar flare effect; nice! $\endgroup$
    – james_t
    Commented Apr 23, 2022 at 15:58
  • $\begingroup$ this is genius, though it seems doesn't work for volume distributed points $\endgroup$
    – Daedra
    Commented May 20, 2022 at 9:47
  • $\begingroup$ @Daedra You're right, and if you find a (slim and easy) solution for volume distributed points, I'd be happy too ;-) Anyway, in relation to your question and the representation therein (distributed points on a sphere), I would still consider my answer as a solution, wouldn't I? $\endgroup$
    – quellenform
    Commented May 20, 2022 at 10:07
  • $\begingroup$ Yes, this is the better answer for my question, I will mark this $\endgroup$
    – Daedra
    Commented May 22, 2022 at 8:18
  • 1
    $\begingroup$ Brilliant solution. You can skip steps 3 and 4 using a Mesh to Points (Edges) node. This gives a new point cloud whose position is the midpoint of the edges. Then use the Geometry Proximity node to compare the original point cloud with this new one, giving half the distance between points to its nearest neighbour. $\endgroup$
    – Kenny
    Commented Sep 30, 2022 at 15:46
13
+50
$\begingroup$

It is technicality possible, but I would recommend searching for a different solution. The idea is to create as many copies of an object as the number of points that are in said object (or produced on object). Then we move this copies far away, so that the distance between object copies is grater than any distance between points of one object. Then we selectively separate one vertex of each object and make it source position "geometry proximity node" the rest we use as target geometry. This will give us closest distances between points.

enter image description here

(I am working on a laptop so the picture quality is bad look at the pictures below)

enter image description here enter image description here enter image description here

I recommend you look at the geometry before all the delete nodes to make sure that the copies are spaced far enough. If they are not, then increase the mesh line offset.

$\endgroup$
3
  • 2
    $\begingroup$ Basically raise the geometry to the power of 2 and modulo by the original number of verts, that's smart :) I think we need more nodes which have the "2nd best match" output, just like the "2nd cell distance" in voronoi texture node. $\endgroup$ Commented Apr 12, 2022 at 14:44
  • $\begingroup$ @MarkusvonBroady this can be done by delete the nearest point then recalculate the nearest distance $\endgroup$
    – Daedra
    Commented Apr 13, 2022 at 7:02
  • 1
    $\begingroup$ I don't think that is why MarkusvonBroady wants this functionality. If 2nd best match was included in the proximity node the (n^2 complexity) is not needed since you can just plug the same object as Target and Source Positon. The 1st closest will give you a field of zeros and 2nd closest will give the field of distances between points. $\endgroup$
    – jst kiko
    Commented Apr 13, 2022 at 9:56
2
$\begingroup$

For Blender version 3.4.1 I found another solution using newer nodes (which didn't exist at the time of the other answers):

  • Edge Vertices
  • Edges of Vertex
  • Sample Index

It's several times faster than the older (still very nice) solution of @quellenform (depends on the number of points but I saw improvements of > 100x). Another advantage is that there is no problem with "false positives".

Idea:

  • Find the index of the shortest edge for each vertex by Edges of Vertex sorting by the edge length (given by Edge Vertices)
  • For each vertex find the other end of that shortest edge (sample the vertex indices of both ends of the shortest edge by Sample Index and then find out which is the one with another index than the current vertex).

Blend file:

It just creates cones pointing to the nearest other point (cone length = 1/2 distance).

For comparison it also contains the solution of @quellenform (Find Nearest 1) and a group making a triangulated mesh from points distributed on a surface (and that original surface) (Surface Points to Mesh).

Find Nearest 2 node group: enter image description here

Simple example:
enter image description here

Also works with non-convex meshes:
(this is not a feature of the Find Nearest 2 node but of the helper node Surface Points to Mesh)
enter image description here

$\endgroup$

You must log in to answer this question.

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