5
$\begingroup$

Suppose I have the following geometry, which was created with Ico Sphere > Subdivide Mesh > Dual Mesh:

enter image description here

Now I apply the node Subdivide Mesh (or Subdivision Surface), which divides the mesh into smaller faces.

But how do I select the point in the middle?

enter image description here

Of course, the whole thing should work the same way for further subdivision levels, so not only for a subdivision of $1$:

enter image description here

The problem here are the faces that have exactly four vertices (all other faces are easy to figure out), where it is obviously relatively complicated to find the center.

I have of course found and tried different variants with scaling and Sample Nearest, and by comparing direction vectors based on positions, but I am looking for a solution based only on logic/mathematics.

The problem with alternative methods is mainly that when using Subdivision Surface there is a shift of the points, which makes any mechanism via vectors or comparisons not stable. That is why I am looking for a way to determine the center point via logic/index.

I'm at a loss right now. How can this be solved (with as little effort as possible and as performant as possible!)?


It turned out that due to the diversity of possible geometries, a solution based purely on mathematics is obviously really extremely complicated.

For those who want to try the solution, there are basically the following scenarios in which it should work:

  • Simple non-manifold meshes
  • Manifold meshes created with Geometry Nodes or in the editor (Cube, Ico Sphere, etc.)
  • But also meshes that have been subdivided before with the node Subdivide Mesh

So in short: I am looking for a solution that reliably finds the center point no matter which geometry is passed to the node Subdivision Surface or Subdivide Mesh, and that without chaining several subdivision nodes.

Here is the test file:


Because it was asked about in the comments: "What is the final goal of the question?"

Here is the answer:
enter image description here

I'm creating a custom node group here that does some horrible things to a mesh. The node Subdivision Surface is used within the node group, and at the end of the group a selection should be available at the output socket, so that further objects can be instantiated at these points.

$\endgroup$
7
  • $\begingroup$ can I ask what is the final goal of the question? there could be another way to see the approach (??) who knows... $\endgroup$
    – lemon
    Mar 31 at 8:13
  • $\begingroup$ @lemon I am working on a node group that does some crazy things with a mesh. In this node group the node Subdivision Surface is used. The output socket should be the center point of the subdivision as selection, so that an instantiation of objects is possible at those points after using this node group. This looks like this: i.stack.imgur.com/4Zs95.jpg ...so I don't think there is any other reliable solution than directly selecting these points (I may be wrong). $\endgroup$
    – quellenform
    Mar 31 at 8:28
  • $\begingroup$ ok, thanks. I see the "why" now. $\endgroup$
    – lemon
    Mar 31 at 8:32
  • $\begingroup$ @lemon I thank you anyway for your high quality and profound answer ...it finally showed me the right way to the solution! May I contact you in the near future by e-mail and give you a voucher (if you are interested in this node group)? $\endgroup$
    – quellenform
    Mar 31 at 8:37
  • $\begingroup$ That's very kind of you, but a simple thank you is fine with me. ; ) $\endgroup$
    – lemon
    Mar 31 at 8:41

3 Answers 3

4
$\begingroup$

The subdivision of a face follows a certain pattern. As Martynas Žiemys also correctly discovered, the points on the edges of the original faces have lower indices than the points in the center, because they are divided first.

He wrote:

Studying vertex indices when applying Subdivision Surface modifier it seems as if vertices with new increasing indices are added when subdividing. They seem to be first added to the existing edges and then they are 'connected' and vertices are added to intersections.

So that's true.

And lemon commented in his answer:

  • vertices of edges are indexed first
  • then inner vertices of faces are indexed in second (face per face)
  • and center vertex is the middle of this last indexation

And that is also true.

But both proposed solutions unfortunately did not lead to the goal and could not solve the problem satisfactorily and in all cases.

For example, if you create the following mesh with Geometry Nodes before (and this is the case in my example) and the subdivision level is greater/equal $2$, then their approach does not work:

enter image description here

So I took another look at the issue, and created a combination of math and logic game...

Reliably select the inner points of subdivided faces

Selecting the points within the faces is a relatively simple game, as it turns out.

All you need to know is how many points ($Po$) and edges ($Eo$) the original mesh had before the subdivision.

And with each subdivision ($S$), additional points are created on the existing edges. This looks like this:

Subdivision Level Additional Points on Edges
0 0
1 1
2 3
3 7
4 15
5 31
6 63

This value is obtained with $2^S-1$.

Now, multiplying this value by the number of edges existing before the subdivision, and adding it to the number of points existing before the subdivision, we get the number of all points running along the original edges after the subdivision ($Pt$):

$Pt = (2^S - 1) * Eo + Po$.

Since these points always have the lowest index of the points added by the subdivision, any index higher than or equal to this value is a point in the inside of a subdivided face.

This reliably gives you a selection that includes only the points inside the faces:

enter image description here
(Inverse selection, points lying along original edges).

Find the middle point within this selection

If a face has 3, 5, 6 or more vertices, then this procedure is simple.

For a face that does not have four vertices, the center point is always the point whose number of adjacent points is equal to the number of vertices of the original face.

But it is even simpler, as I found out:
For a face that does not have four vertices, the point in the middle after a subdivision always has the lowest index of all points lying within the face!

enter image description here
(Subdivided pentagon with lowest index in the center)

Thus only one switch is needed to distinguish between faces with four vertices and all others.

For faces with four vertices, the middle point always has the middle value of the values of all points lying within a face.

enter image description here
(Index Range from $741$ to $749$, and the center has index $745$)

And to do this, you need to calculate how many points lie within a face.

Since this depends on the subdivision level, this is achieved by the following formula:

$\frac{(2^S-1)^2-1}{2}$

And so, for example, with a number of $9$ points, you would have selected the point with the index $4$ (Reminder: The index starts counting at $0$).

With the previously mentioned switch you can now toggle between the value $0$ (for faces with more than four vertices) and this average value (for faces with exactly four vertices).

In the last step we only have to compare the current index with these values.

And in this case we have to start counting again at $0$ for each face, so we politely ask the node Accumulate Field to create a new counter for each face, so that the indices of all points that are inside a face and start in a new face will always start counting at $0$.

Since I capture the index of the faces in the domain Face before the subdivision with Capture Attribute, these values remain in the points even after the subdivision. This is because the interpolation (from Face to Point) of these values only takes place at the points along the original edges, but not at the points created by the subdivision inside the original faces. Thus all points within the original faces always receive the same original value, which I use as a Group Index for Accumulate Field. This way the counter can start counting again at $0$ for each original face.

enter image description here
(All points within a face use the original face index as Group input of Accumulate Field)

enter image description here
(Iterate through the indices of a face and capture the midpoint with index $4$)

So if one of the indices obtained in this way is equal to the value calculated before, then it is the midpoint of a subdivided face:

And in this example, with a subdivision level of $2$, the center index is $4$.

...Yay! The center point has been found!

enter image description here

enter image description here

And the node group ended up being simpler than initially thought:

enter image description here


And the coolest thing about this solution is:

  • This node group can handle faces with any number of vertices.
  • It can be used with all geometries, even if they were created in a "strange" way.
  • The solution is extremely performant.

enter image description here


(Blender 3.4+)

$\endgroup$
5
  • $\begingroup$ Thanks for the detailed explanation.... but still, to me, there is some magic at the end!! What I understand (I think): accumulate field is based on the original face index, and does a repartition of indices (flag count) for the indices above the one corresponding to the edges. But by which magic all that comes to the final indices approprietally? How are they themselves "linked" to the good original face index? $\endgroup$
    – lemon
    Mar 31 at 10:48
  • $\begingroup$ @lemon Since I capture the index of the faces in the domain Face before the subdivision with Capture Attribute, these values remain in the points even after the subdivision. This is because the interpolation (from Face to Point) of these values only takes place at the points along the edges, but not at the points within the original face. Thus all points within the original faces always receive the same original value, which I use as a Group Index for Accumulate Field. This way the counter can start counting again at $0$ for each original face. $\endgroup$
    – quellenform
    Mar 31 at 11:00
  • $\begingroup$ Thanks, that's clear. A way of thinking I'm not used to! But very interesting. $\endgroup$
    – lemon
    Mar 31 at 12:26
  • 1
    $\begingroup$ @lemon Thank you for your interesting question, I have added to the answer accordingly to make this easier to understand. $\endgroup$
    – quellenform
    Mar 31 at 12:34
  • 1
    $\begingroup$ Amasing answer! Figuring this out must have been one hell of a job, but also explaining it in such a clear manner... It was so weirdly satisfying to read it. Especially after trying to figure it out for a while. :D I think I might save this for future to link to as an example of well formed question and answer. Honestly. And the pictures... even a table... This is seriously inspiring. :D $\endgroup$ Apr 1 at 2:57
2
$\begingroup$

Studying vertex indices when applying Subdivision Surface modifier it seems as if vertices with new increasing indices are added when subdividing. They seem to be first added to the existing edges and then they are 'connected' and vertices are added to intersections.

If I have a cube, it seems vertices at the centers of faces are created the last. So it seems that the number of last indices matching the number of faces in the original mesh will be the center vertices of the faces. Further subdivisions don't seem to matter, because after the first subdivision the centers remain the same.

enter image description here

This seems to also be the case if I dissolve one vert of the cube to have geometry that's not so regular as a cube(further testing might be needed):

enter image description here

So if it's all correct as far, you would have to get all the indices that are greater than the amount of verts in mesh subdivided once minus the amount of faces in the original mesh. To pass that information to higher subdivisions, we could store an attribute. It will get interpolated with higher subdivisions, but the original verts will retain value of 1:

enter image description here

I am sure it is possible to put it into one node group that takes care of the cases of 1 subdivision and more than 1 subdivisions so you have only one number input.

This is getting a bit complex for me, so I might be mistaken in some or possibly many ways. Here is the file:

$\endgroup$
5
  • $\begingroup$ Thank you for this great answer! This works fine, but unfortunately not in my specific case. Since I'm looking for a solution where I use the subdivision levels in a single node instead of multiple nodes serially, unfortunately this solution doesn't help me. Especially when using Subdivision Surface and its special properties Edge Crease and Vertex Crease it does not work well unfortunately. However, I can confirm that with a serial setup and using Subdivide Mesh, the center point is reliably found for all shapes I tested! Anyway: Well analyzed and well implemented! $\endgroup$
    – quellenform
    Mar 28 at 8:58
  • 1
    $\begingroup$ Maybe it's possible to somehow just take the indices from a separate subdivide node and use them in another. But It doesn't seem to work for me. Anyway, I think you know more than me about nodes in general, maybe you could find a way based on that the center vertices get created last after first subdivision. Maybe it's possible to calculate the indices before subdivision just based on the initial mesh using math only. $\endgroup$ Mar 28 at 10:11
  • $\begingroup$ "Maybe it's possible to calculate the indices before subdivision just based on the initial mesh using math only." ...yes, that would be exactly the solution I am looking for here. ...and I know that this is not easy (at least I haven't found a really satisfying answer yet) :D $\endgroup$
    – quellenform
    Mar 28 at 11:05
  • 1
    $\begingroup$ I think I am starting to figure it out. It seems like subdivision modifier works differently than subdivision node. Modifier subdivides in iterations and the node seems to subdivide the edges as many times as there are subdivisions first and only then fill the middle and it does it face by face. It is definitely possible to calculate where the centers will be. Just a matter of coming up with the equation. $\endgroup$ Mar 28 at 12:33
  • $\begingroup$ Yes, you are completely on the right track: Regarding indices, the points on the edges have lower values than the points in the center! In the meantime, I have even found a solution, but I'm curious to see what else you come up with. $\endgroup$
    – quellenform
    Mar 28 at 13:41
2
$\begingroup$

For quad meshes only.

enter image description here

As Martynas found that face centers have the last indices for the first subdivision, we can complete observing that

  • vertices of edges are indexed first
  • then inner vertices of faces are indexed in second (face per face)
  • and center vertex is the middle of this last indexation

(at least, these rules seem to work in my test cases)

We can know:

  • total amount of vertices Vt and faces Ft
  • number of original faces Fo, knowing the subdivisions n is Fo = Ft / 4**n
  • inner vertices per face (the one that are not in the borders: 1, 9, 49, 225, 961 etc.) is Vi = (2**n - 1)**2
  • border vertices Vb = Vt - Ft * Vi

So, the first center comes at I0 = Vb + floor(Vi / 2). And the consecutive other face centers have (index - I0) % Vi == 0 (with index - I0 positive or null).

Which is in GN the following:

enter image description here

$\endgroup$
11
  • $\begingroup$ Wow, incredible, that's a pretty good answer! That's exactly the mathematical solution I was looking for! But! ...unfortunately, that doesn't work for every geometry (Even if it strictly answers the question). If you use any geometry that you create with Geometry Nodes or an existing mesh, it works wonderfully. But as soon as you use a geometry that has been subdivided before with Subdivide Mesh, this variant unfortunately does not work. Here is the test file: blend-exchange.com/b/EEr0MWMq Do you have an idea how to solve this problem? $\endgroup$
    – quellenform
    Mar 29 at 14:54
  • 1
    $\begingroup$ mmm... i hadn't thought of that... :( ... I'll take a look... $\endgroup$
    – lemon
    Mar 29 at 15:07
  • $\begingroup$ Thank you! I think at the latest here, it becomes really complicated :D ...that's the reason why I used a trick. But mathematically speaking, you obviously have even more understanding than I do. I will be grateful if you find a solution. $\endgroup$
    – quellenform
    Mar 29 at 15:10
  • $\begingroup$ ok, I've opened your file. But this answer can only work with quad only faces (quads before subdivision), is it the case in your settings? (I don't think so) $\endgroup$
    – lemon
    Mar 29 at 15:14
  • $\begingroup$ Yes, there are also quads. These are different shapes that have faces with 3-5 vertices. And one of these shape was created before with Subdivide Mesh. And unfortunately this solution cannot be applied to this one. I am looking for a solution that reliably selects the center point no matter what the topology in front of it is. The test file contains my and your solution (switchable), and as soon as the subdivision level is >=2, it unfortunately does not work anymore. In the node group itself there is another switch that handles non-quad faces differently. $\endgroup$
    – quellenform
    Mar 29 at 15:26

You must log in to answer this question.

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