For example on an object like a banana, a snake or a C shaped object.
Is there a way to find the 2 "endpoints" or the 2 vertices that are furthest apart using geometry nodes?
3
- $\begingroup$ Important to clarify your metric: furthest apart in 3D space, or the longest route through the geometry? $\endgroup$Robin Betts– Robin Betts2024-02-21 08:45:22 +00:00Commented Feb 21, 2024 at 8:45
- $\begingroup$ Preferrably longest route through the geometry. $\endgroup$muckyu– muckyu2024-02-21 11:20:26 +00:00Commented Feb 21, 2024 at 11:20
- 1$\begingroup$ @muckyu can you make some example meshes, manually position the points that are further apart and explain the algorithm (e.g. draw a path from one to another) on why they are considered to be the furthest apart? That would make it a good question. For example, a "shortest path" could be used to get all possible paths through edges, and then pick the longest, but it's still not really "the longest path", because you could make it shorter by going through diagonals of the faces, and then shorter still by just arbitrarily traveling through the mesh. $\endgroup$Markus von Broady– Markus von Broady2024-02-21 11:34:38 +00:00Commented Feb 21, 2024 at 11:34
Add a comment |
2 Answers
$\begingroup$ 
$\endgroup$
8 This is the most efficient way I could find: rather than measuring distances between each pair of points, I'm making a copy (copying has to be done in order to iterate on every possible pair - and a repeat zone is in general much slower than the old ways) and moving chosen point to the origin. Now the distance to this point is just the length of the position vector:
As Don Hatch notices in a comment, the "Delete Geometry" node is not required (and removing it speeds up the setup). You would want this node if the criterion for picking a point wasn't being furthest, but something that could cause a point to evaluate itself (its copy) as a winner. In such case you would keep this node. For example if "Index of Nearest" node didn't exist or if you wanted to find the nearest unconnected point (in this case you would need to blur the selection with 1 iteration to also delete immediately connected points).
You can use this group like so:
Robin Betts' convex hull optimization:
answered Feb 21, 2024 at 11:23
Markus von Broady
48.6k3 gold badges44 silver badges129 bronze badges
- 1$\begingroup$ Not sure... Could you reduce this to the same method on the convex hull? $\endgroup$Robin Betts– Robin Betts2024-02-21 12:29:56 +00:00Commented Feb 21, 2024 at 12:29
- $\begingroup$ @RobinBetts good question! I think you're correct, this could be optimized by the convex hull. The simple proof being, that convex hull never creates (does it?) new points. $\endgroup$Markus von Broady– Markus von Broady2024-02-21 13:49:49 +00:00Commented Feb 21, 2024 at 13:49
- 1$\begingroup$ @RobinBetts ...And for any point it's always another point that is the furthest, because if 2 points building in edge are in equal distance, than the edge is inside the sphere defined by this distance. The same goes for 3 points and a triangle. And if any point disappeared in convex hull, then that point was closer than some points on the hull... I think so but I'm still making some tests $\endgroup$Markus von Broady– Markus von Broady2024-02-21 13:58:31 +00:00Commented Feb 21, 2024 at 13:58
- $\begingroup$ @DonHatch good catch, since the question is about furthest points, no point is going to be furthest to itself so this node can be removed. There's more comparisons to be made then for the Attribute Statistic node, but having one less step in the higher abstraction layer is much more important as your tests confirm. $\endgroup$Markus von Broady– Markus von Broady2024-11-19 14:02:45 +00:00Commented Nov 19, 2024 at 14:02
- 1$\begingroup$ @DonHatch i.imgur.com/pQohFiU.gif $\endgroup$Markus von Broady– Markus von Broady2024-11-21 19:23:51 +00:00Commented Nov 21, 2024 at 19:23
$\begingroup$
$\endgroup$
4 Here are a couple of variations on Markus von Broady's solution. They both are still based on Markus's "quadratic geometry explosion" method (that is, explicitly constructing in memory the entire Minkowski sum of the point set A with -A), so if you try to use them on inputs a lot larger than Suzanne, you will have a bad time :-/
Variation #1
My first thought on looking at Markus's solution was that the method of finding the index at which a maximum occurs looks a bit shocking-- surely there's a more direct way to implement "index of max"?
But it seems that "Attribute Statistic (Max)" really doesn't provide a convenient way to get the index at which the max occurred. I tried searching all over for geom accumulation nodes that do return an index, that we might be able to leverage for this. The only things I found were "Index of Nearest" (which I couldn't figure out how to use at all) and "Sample Nearest". "Sample Nearest" can do almost what we want-- it can tell us the index of the point nearest the origin. But we want the point farthest from the origin instead. To do that, we can just use the "inverses" of the points (i.e. each point divided by its distance-from-origin squared), and ask which one of those is nearest the origin.
So, in this variation, I do the following:
Use an "Inverse of Position" node group, followed by "Sample Nearest", to get the index of the point farthest from the origin in the Minkowski sum object.
Also, instead of capturing the original indices on the two factor geometries and threading those through the product, I recover them from the index-into-the-big-object using math-- simply div and mod the big index by the original number of points.
Here's the "Inverse of Position" node, expanded:
I thought this was all clever and neat, but unfortunately it seems to be 7.5 times as slow as Markus's original solution :-(
(That's according to the Timings annotations in the geom node graph editor, on Suzanne with "Subdivision Surface" modifier, which increases number of vertices from 507 to 2012... and without taking convex hull.)
Variation #2
Abandoning the too-slow "Inverse of Position" -> "Sample Nearest" strategy, I tried to at least salvage the recover-the-two-indices-using-math part (which seems like a simplification, and I was hoping maybe a performance improvement too). So that means going back to the original shockingly-clunky-but-reasonably-fast method of finding the index at which a maximum occurs. I encapsulated this into an "Index of Max" node group, so at least it looks tidy from the outside.
And here's the "Index of Max" node, expanded: 
This variation seems to be the same speed as Markus's original solution (with the "Delete Geometry" node muted). So there was no measurable performance gain here after all-- the main thing of value here, perhaps, is just the reusable "Index of Max" node.
- 1$\begingroup$ "Sample Nearest" needs to build an octree, which just like "Attribute Statistic" needs to iterate over all elements to build it, but then also needs to group those elements in multiple levels of cells, so that might be why you can't get it to perform better. Also, I just call it "distance" not "Minkowski difference", but sure, you could replace "Vector Math: Length" coming to the stats node with something else. $\endgroup$Markus von Broady– Markus von Broady2024-11-21 15:53:49 +00:00Commented Nov 21, 2024 at 15:53
- 1$\begingroup$ "Also, I just call it "distance" not "Minkowski difference"," I'm not quite following what you're saying here, but maybe I wasn't clear when I used the term. (And I forgot to link to the wikipedia page). I was just trying to point out that your explicitly constructed "quadratic geometry explosion" point set object is {a-b : a in A, b in B}, which is the [Minkowski sum] of A and -B. (In this problem statement, A and B are both the original point set, but with only trivial modification, your method can handle the more general situation when A and B are two different point sets, too). ... $\endgroup$Don Hatch– Don Hatch2024-11-21 18:58:07 +00:00Commented Nov 21, 2024 at 18:58
- 1$\begingroup$ ... and I assumed the Minkowski sum of A and -B would naturally called the Minkowski difference of A and B, so I called it that... but I see now, looking at that wikipedia page, that they call this concept "An alternative definition of the Minkowski difference" (the "non-alternative" definition they discuss first seems to be something more complicated, which I haven't quite wrapped my brain around yet). (They also claim that the alternative definition "is sometimes used for computing intersection of convex shapes."; however I don't see the connection, and I wonder if this part is wrong.) $\endgroup$Don Hatch– Don Hatch2024-11-21 19:01:07 +00:00Commented Nov 21, 2024 at 19:01
- 1$\begingroup$ @MarkusvonBroady I edited my answer to avoid use of "Minkowski difference" which turned out to be ambiguous and unnecessarily confusing, and replaced it with "Minkowski sum of A and -A", with link to the wikipedia article; hopefully that's clearer. (Still kind of glossing over the fact that I'm talking about point lists rather than point sets, though) $\endgroup$Don Hatch– Don Hatch2024-11-21 19:29:23 +00:00Commented Nov 21, 2024 at 19:29