Curve and Mesh Topology Inputs #100020

New Issue

Jacques Lucke · 2022-07-27T12:41:05+02:00

Jacques Lucke commented

2022-07-27 12:41:05 +02:00

This is a WIP design for a more complete set of topology inputs for curves and meshes (point clouds, volumes and instances don't need nodes like that).

Goals:

Provide a more consistent way to access topology information.
Allow for deterministic ordering of neighbors using sort weights.
Don't require the use of lists. While we can support list sockets in the future, we don't have these yet and many use cases don't require them. Using lists when they are not really necessary is a recipe for making things slow.
Make it easier to chain topology input nodes by providing an element index input (that's the Index field implicitly).

Challenges:

There are many different kinds of topology lookups in various directions between domains. While there are some common patterns, some lookup directions don't fit in well with the others.
Is there a reasonable way to merge these different lookups into fewer nodes? User-defined node groups should be able to look similar.
The hardest part really seems to be the naming. I didn't find a good naming convention that fits all nodes yet. Maybe two or three conventions are necessary?

Feel free to use the .blend file below for more mockups.

topology_lookup_mockups.blend

This is a WIP design for a more complete set of topology inputs for curves and meshes (point clouds, volumes and instances don't need nodes like that). Goals: * Provide a more consistent way to access topology information. * Allow for deterministic ordering of neighbors using sort weights. * Don't require the use of lists. While we can support list sockets in the future, we don't have these yet and many use cases don't require them. Using lists when they are not really necessary is a recipe for making things slow. * Make it easier to chain topology input nodes by providing an element index input (that's the Index field implicitly). Challenges: * There are many different kinds of topology lookups in various directions between domains. While there are some common patterns, some lookup directions don't fit in well with the others. * Is there a reasonable way to merge these different lookups into fewer nodes? User-defined node groups should be able to look similar. * The hardest part really seems to be the naming. I didn't find a good naming convention that fits all nodes yet. Maybe two or three conventions are necessary? Feel free to use the .blend file below for more mockups. ![image.png](https://archive.blender.org/developer/F13322194/image.png) [topology_lookup_mockups.blend](https://archive.blender.org/developer/F13322196/topology_lookup_mockups.blend)

Jacques Lucke commented

2022-07-27 12:41:05 +02:00

Added subscriber: @JacquesLucke

Jacques Lucke commented

2022-07-27 12:50:30 +02:00

Changed status from 'Needs Triage' to: 'Confirmed'

Jacques Lucke commented

2022-07-27 12:55:20 +02:00

Added subscribers: @HooglyBoogly, @mod_moder, @guitargeek

Iliya Katushenock commented

2022-07-27 13:00:19 +02:00

Such nodes should always take the geometry as the source. Most often you use this data on other geometry. It acts as a kind of array, on the basis of which you can somehow use the topology data.
(Related to the topic of multiple context for transfer nodes)
I thought about how all these nodes require duplication so that the user can know the number of links in advance and use duplication. For this reason, in the discussion topic, I proposed a new design, the essence of which is that it itself creates a new geometry array with connection data. Thus, the meaning of these nodes is reduced to creating an array of data that is convenient for use.

https://devtalk.blender.org/t/access-to-geometry-data/24618/7

Edit:
For example, face-face connection:

1. Such nodes should always take the geometry as the source. Most often you use this data on other geometry. It acts as a kind of array, on the basis of which you can somehow use the topology data. (Related to the topic of multiple context for transfer nodes) 2. I thought about how all these nodes require duplication so that the user can know the number of links in advance and use duplication. For this reason, in the discussion topic, I proposed a new design, the essence of which is that it itself creates a new geometry array with connection data. Thus, the meaning of these nodes is reduced to creating an array of data that is convenient for use. https://devtalk.blender.org/t/access-to-geometry-data/24618/7 Edit: For example, face-face connection: ![image.png](https://archive.blender.org/developer/F13322201/image.png)

Jacques Lucke commented

2022-07-27 13:16:37 +02:00

Such nodes should always take the geometry as the source.

No. That would make them unusable in fields. Also when chaining these nodes, it's very likely that all the nodes should work in the same geometry. It's possible to wrap these nodes with e.g. a Transfer Attribute or Capture Attribute node, to create the kind of node that you want.

I proposed a new design, the essence of which is that it itself creates a new geometry array with connection data

I'm not generally against creating e.g. a Point Cloud just as a wrapper for multiple arrays, but it does not seem necessary for the kinds of topology inputs I'm targeting now. That also wouldn't make them easier, and make them impossible to use in a reusable field.
Might be worth to wait for lists sockets instead of having nodes that output a point cloud as a list alternative.

> Such nodes should always take the geometry as the source. No. That would make them unusable in fields. Also when chaining these nodes, it's very likely that all the nodes should work in the same geometry. It's possible to wrap these nodes with e.g. a Transfer Attribute or Capture Attribute node, to create the kind of node that you want. > I proposed a new design, the essence of which is that it itself creates a new geometry array with connection data I'm not generally against creating e.g. a Point Cloud just as a wrapper for multiple arrays, but it does not seem necessary for the kinds of topology inputs I'm targeting now. That also wouldn't make them easier, and make them impossible to use in a reusable field. Might be worth to wait for lists sockets instead of having nodes that output a point cloud as a list alternative.

Iliya Katushenock commented

2022-07-27 13:20:49 +02:00

I'm not generally against creating e.g. a Point Cloud just as a wrapper for multiple arrays, but it does not seem necessary for the kinds of topology inputs I'm targeting now. That also wouldn't make them easier, and make them impossible to use in a reusable field.
Might be worth to wait for lists sockets instead of having nodes that output a point cloud as a list alternative.

In total, this data has an arbitrary size. Because of this, use in the field will have the character

if (connection_count > 1){}
if (connection_count > 2){}
if (connection_count > 3){}

Since it will be very difficult to duplicate domains in one field and analyze their topology

> I'm not generally against creating e.g. a Point Cloud just as a wrapper for multiple arrays, but it does not seem necessary for the kinds of topology inputs I'm targeting now. That also wouldn't make them easier, and make them impossible to use in a reusable field. > Might be worth to wait for lists sockets instead of having nodes that output a point cloud as a list alternative. In total, this data has an arbitrary size. Because of this, use in the field will have the character ``` if (connection_count > 1){} if (connection_count > 2){} if (connection_count > 3){} ``` Since it will be very difficult to duplicate domains in one field and analyze their topology

Iliya Katushenock commented

2022-07-27 13:24:04 +02:00

In #100020#1396161, @JacquesLucke wrote:

Such nodes should always take the geometry as the source.

No. That would make them unusable in fields. Also when chaining these nodes, it's very likely that all the nodes should work in the same geometry. It's possible to wrap these nodes with e.g. a Transfer Attribute or Capture Attribute node, to create the kind of node that you want.

From the beginning, the Face Contain node (or later renamed the Mesh Contain Connection) was made to be a field only. After several tests, it became clear that these are not suitable for use for the reasons described above.

> In #100020#1396161, @JacquesLucke wrote: >> Such nodes should always take the geometry as the source. > > No. That would make them unusable in fields. Also when chaining these nodes, it's very likely that all the nodes should work in the same geometry. It's possible to wrap these nodes with e.g. a Transfer Attribute or Capture Attribute node, to create the kind of node that you want. From the beginning, the Face Contain node (or later renamed the Mesh Contain Connection) was made to be a field only. After several tests, it became clear that these are not suitable for use for the reasons described above.

Jacques Lucke commented

2022-07-27 13:26:41 +02:00

Well, obviously it depends on what you want to do. Whenever, you want to work with a variable number of elements, a workaround will be necessary currently. We shouldn't force people to use these workarounds for simpler tasks like "get the left-most vertex of the current face" though. My impression right now is that the nodes that you propose could be build out of these smaller nodes in my proposal (but not the other way around).

Iliya Katushenock commented

2022-07-27 13:33:48 +02:00

In #100020#1396164, @JacquesLucke wrote:
Well, obviously it depends on what you want to do. Whenever, you want to work with a variable number of elements, a workaround will be necessary currently. We shouldn't force people to use these workarounds for simpler tasks like "get the left-most vertex of the current face" though. My impression right now is that the nodes that you propose could be build out of these smaller nodes in my proposal (but not the other way around).

Your nodes implement link lookup functions. But they have the limitations of the current node system in terms of variable data size.

For example: if we want to create instances and transform them in the right way: points are more convenient, they are easier to copy.
Also, after several tests, I caught myself thinking that the main functionality of this comes down to spawning intans between neighbors in the right way. And also, yes, data transfer between its neighbors is relevant.

+Edit:
I'm not sure if this is accepted, but for users, groups (accumulate, sort in group, ...) are the primary solution for getting around restrictions on arbitrary size data. From this point of view, these knots do not give freedom

> In #100020#1396164, @JacquesLucke wrote: > Well, obviously it depends on what you want to do. Whenever, you want to work with a variable number of elements, a workaround will be necessary currently. We shouldn't force people to use these workarounds for simpler tasks like "get the left-most vertex of the current face" though. My impression right now is that the nodes that you propose could be build out of these smaller nodes in my proposal (but not the other way around). Your nodes implement link lookup functions. But they have the limitations of the current node system in terms of variable data size. For example: if we want to create instances and transform them in the right way: points are more convenient, they are easier to copy. Also, after several tests, I caught myself thinking that the main functionality of this comes down to spawning intans between neighbors in the right way. And also, yes, data transfer between its neighbors is relevant. +Edit: I'm not sure if this is accepted, but for users, groups (accumulate, sort in group, ...) are the primary solution for getting around restrictions on arbitrary size data. From this point of view, these knots do not give freedom

Jacques Lucke commented

2022-07-27 13:38:24 +02:00

~~Here is an example for how to get a list of all face neighbor pairs (encoded as point cloud attributes). This is just to show that it is possible.~~ (turns out that doesn't actually work this way)

~~Here is an example for how to get a list of all face neighbor pairs (encoded as point cloud attributes). This is just to show that it is possible.~~ (turns out that doesn't actually work this way) ![image.png](https://archive.blender.org/developer/F13322217/image.png)

Iliya Katushenock commented

2022-07-27 13:39:06 +02:00

But if there is a list design (which will be added, not left as a potential feature) that may appear soon and extend the general functionality of the nodes, then I think this will be solved.

Iliya Katushenock commented

2022-07-27 13:42:27 +02:00

In #100020#1396166, @JacquesLucke wrote:
Here is an example for how to get a list of all face neighbor pairs (encoded as point cloud attributes). This is just to show that it is possible.

This node system has one bug: This node has no neighbor data, as it will be evaluated for the point cloud.

Or the data that is included in it will not be relevant for the mesh. Or are you talking about combining mesh and point cloud in the same geometry as {mesh, array}?

> In #100020#1396166, @JacquesLucke wrote: > Here is an example for how to get a list of all face neighbor pairs (encoded as point cloud attributes). This is just to show that it is possible. > > ![image.png](https://archive.blender.org/developer/F13322217/image.png) This node system has one bug: This node has no neighbor data, as it will be evaluated for the point cloud. ![image.png](https://archive.blender.org/developer/F13322222/image.png) Or the data that is included in it will not be relevant for the mesh. Or are you talking about combining mesh and point cloud in the same geometry as {mesh, array}?

Jacques Lucke commented

2022-07-27 13:44:21 +02:00

Yes, lists can make some use cases significantly simpler. I'm not arguing with that. But even with lists, for some use cases the nodes proposed in the initial post are likely to be more efficient and simpler to use. Also note that we might be talking about lists in different contexts right now. Lists should be supported in within and outside of a field context.
Anyway, this task is not about adding support for lists.

This node system has one bug: This node has no neighbor data, as it will be evaluated for the point cloud.

You're right. Fixed my comment.

Yes, lists can make some use cases significantly simpler. I'm not arguing with that. But even with lists, for some use cases the nodes proposed in the initial post are likely to be more efficient and simpler to use. Also note that we might be talking about lists in different contexts right now. Lists should be supported in within and outside of a field context. Anyway, this task is not about adding support for lists. > This node system has one bug: This node has no neighbor data, as it will be evaluated for the point cloud. You're right. Fixed my comment.

Hans Goudey commented

2022-07-27 21:51:31 +02:00

I played with the mockups for a while to see if I could build some of the lookups out of others, and to experiment with the naming.
I think it's helpful to use some chart like this that shows how to find neighboring elements of each type.
Sometimes it's not so bad to build lookups from others. For example, "Vertex to Face", "Face to Vertex" and "Face to Edge" are pretty intuitive.
The others less so, but I could see that kind of flexibility being helpful anyway. I sort of got the point after a while, do I didn't do the last few.

I think this is helpful anyway, to see which of this set of nodes are the most important.
"Face to Corner", "Corner to Vertex", "Corner to Edge", "Corner to Corner", "Vertex to Edge", and "Vertex to Corner" are probably the most important.

	To Vertex	To Edge	To Face	To Corner
From Vertex
From Edge
From Face
From Corner

topology_lookup_mockups.blend

I played with the mockups for a while to see if I could build some of the lookups out of others, and to experiment with the naming. I think it's helpful to use some chart like this that shows how to find neighboring elements of each type. Sometimes it's not so bad to build lookups from others. For example, "Vertex to Face", "Face to Vertex" and "Face to Edge" are pretty intuitive. The others less so, but I could see that kind of flexibility being helpful anyway. I sort of got the point after a while, do I didn't do the last few. I think this is helpful anyway, to see which of this set of nodes are the most important. "Face to Corner", "Corner to Vertex", "Corner to Edge", "Corner to Corner", "Vertex to Edge", and "Vertex to Corner" are probably the most important. | | To Vertex | To Edge | To Face | To Corner | | -- | -- | -- | -- | -- | | From Vertex | <image src="https://archive.blender.org/developer/F13322828/image.png"> | <image src="https://archive.blender.org/developer/F13322834/image.png"> | <image src="https://archive.blender.org/developer/F13322837/image.png"> | <image src="https://archive.blender.org/developer/F13322839/image.png"> | | From Edge | <image src="https://archive.blender.org/developer/F13322843/image.png"> | <image src="https://archive.blender.org/developer/F13322917/image.png"> | <image src="https://archive.blender.org/developer/F13322910/image.png"> | <image src="https://archive.blender.org/developer/F13322906/image.png"> | | From Face | <image src="https://archive.blender.org/developer/F13322927/image.png"> | <image src="https://archive.blender.org/developer/F13322931/image.png"> | | | | From Corner | | | | <image src="https://archive.blender.org/developer/F13322936/image.png"> | [topology_lookup_mockups.blend](https://archive.blender.org/developer/F13322950/topology_lookup_mockups.blend)

Irakli Kupunia commented

2022-07-28 02:03:06 +02:00

Added subscriber: @ikakupa

Iliya Katushenock commented

2022-08-08 20:01:15 +02:00

All of these nodes must be calculated with 2 separate mechanisms:
General topology processing, returning a single GVectorArray. Most algorithms come down to

GVectorArray list(size);
for (vertices){
  list[vertex].append(something);
}

Because of this, the use of multifunctions is not possible.
Evaluating all this in its context means that the data can only be used by the domain owner. Therefore, as long as there are no lists, it will be very difficult for the user to use such data, given its arbitrary size.

This is the reason for this option:
Geometry input, return GVectorArray connections.
Entering sampling indexes and numbers, returning values.
Disregarding sorting, the usage looks like this: The node compiles the topology analysis and returns a sampling multifunction.
Now sorting. If a vertex wants to get neighbors, how to sort them? By number. Okay, what's the geometric meaning? If we enter a sorting context that has a vertex index and a neighbor index, then the user can more meaningfully return weight for sort. But, is such a complex sorting mechanism necessary?
Naturally, in this design, this sort should receive a GVectorArray of neighbors, and return a GVectorArray of weights. In this case, it can be considered as a separate node for working with lists, temporarily embedded in the nodes of the topology.

All of these nodes must be calculated with 2 separate mechanisms: General topology processing, returning a single `GVectorArray`. Most algorithms come down to ``` GVectorArray list(size); for (vertices){ list[vertex].append(something); } ``` Because of this, the use of multifunctions is not possible. Evaluating all this in its context means that the data can only be used by the domain owner. Therefore, as long as there are no lists, it will be very difficult for the user to use such data, given its arbitrary size. --- This is the reason for this option: Geometry input, return `GVectorArray` connections. Entering sampling indexes and numbers, returning values. Disregarding sorting, the usage looks like this: The node compiles the topology analysis and returns a sampling multifunction. Now sorting. If a vertex wants to get neighbors, how to sort them? By number. Okay, what's the geometric meaning? If we enter a sorting context that has a vertex index and a neighbor index, then the user can more meaningfully return weight for sort. But, is such a complex sorting mechanism necessary? Naturally, in this design, this sort should receive a `GVectorArray` of neighbors, and return a `GVectorArray` of weights. In this case, it can be considered as a separate node for working with lists, temporarily embedded in the nodes of the topology.

Iliya Katushenock commented

2022-08-13 19:23:45 +02:00

Also, separate:
Vertices belonging to the polygon.
Vertices connected to the polygon through edges
Vertices connected from polygons through adjacent polygons

And
Index (global number) and Number (neighbor number, valid only for enumeration) In order not to create confusion about what 2 polygon indices are for when iterating over adjacent polygons

Also, separate: Vertices belonging to the polygon. Vertices connected to the polygon through edges Vertices connected from polygons through adjacent polygons And Index (global number) and Number (neighbor number, valid only for enumeration) In order not to create confusion about what 2 polygon indices are for when iterating over adjacent polygons

Howard Trickey commented

2022-09-07 21:30:13 +02:00

Added subscriber: @howardt

Howard Trickey commented

2022-09-07 21:30:13 +02:00

I'm curious as to what the implementation idea is for each of these. For those that require going through whole Mesh arrays (e.g., Vertex to Edge requires going through all MEdge's), how might this be more efficient than doing that? Seems like a tradeoff between (a) just iterate through the arrays as needed; (b) caching geometry node results; (c) carrying along some general topology structure with geometry (a la BMesh), which is I guess a different form of caching.

Hans Goudey commented

2022-09-08 06:44:14 +02:00

In #100020#1413660, @howardt wrote:
I'm curious as to what the implementation idea is for each of these. For those that require going through whole Mesh arrays (e.g., Vertex to Edge requires going through all MEdge's), how might this be more efficient than doing that? Seems like a tradeoff between (a) just iterate through the arrays as needed; (b) caching geometry node results; (c) carrying along some general topology structure with geometry (a la BMesh), which is I guess a different form of caching.

I'd imagine it as a combination of the three. Caching some basic topology mappings on mesh could help a lot. It's nice that we can build some mappings out of others.
Calculating some topology data lazily is a potential way to amortize the cost of iterating over all mesh elements. Combined with generalized node caching, we should be able to reuse those geometry-owned caches much more.

> In #100020#1413660, @howardt wrote: > I'm curious as to what the implementation idea is for each of these. For those that require going through whole Mesh arrays (e.g., Vertex to Edge requires going through all MEdge's), how might this be more efficient than doing that? Seems like a tradeoff between (a) just iterate through the arrays as needed; (b) caching geometry node results; (c) carrying along some general topology structure with geometry (a la BMesh), which is I guess a different form of caching. I'd imagine it as a combination of the three. Caching some basic topology mappings on mesh could help a lot. It's nice that we can build some mappings out of others. Calculating some topology data lazily is a potential way to amortize the cost of iterating over all mesh elements. Combined with generalized node caching, we should be able to reuse those geometry-owned caches much more.

Paul Larson commented

2022-09-10 09:10:09 +02:00

Added subscriber: @GeorgiaPacific

blender-admin commented

2022-09-26 20:03:28 +02:00

This issue was referenced by 8a6dc0fac7

This issue was referenced by 8a6dc0fac71cc5eb6fc945295b9c1f51f72cc407

blender-admin commented

2022-09-28 21:38:27 +02:00

This issue was referenced by 482d431bb6

This issue was referenced by 482d431bb6735e8206961bd1115d2be7e63572b1

AgentA1cr commented

2022-10-31 19:40:22 +01:00

Added subscriber: @AgentA1cr

AgentA1cr commented

2022-10-31 21:37:10 +01:00

I'm not sure how the Edge To Corner/Face groups that you built are meant to function, but in my testing, they provide no guarantee that the Corner or Face returned is adjacent to the Edge in question, rather than merely sharing a vertex. Am I doing something wrong here?

In #100020#1396393, @HooglyBoogly wrote:
I played with the mockups for a while to see if I could build some of the lookups out of others, and to experiment with the naming.
I think it's helpful to use some chart like this that shows how to find neighboring elements of each type.
Sometimes it's not so bad to build lookups from others. For example, "Vertex to Face", "Face to Vertex" and "Face to Edge" are pretty intuitive.
The others less so, but I could see that kind of flexibility being helpful anyway. I sort of got the point after a while, do I didn't do the last few.

I think this is helpful anyway, to see which of this set of nodes are the most important.
"Face to Corner", "Corner to Vertex", "Corner to Edge", "Corner to Corner", "Vertex to Edge", and "Vertex to Corner" are probably the most important.

| | To Vertex | To Edge | To Face | To Corner |
| From Vertex | {F13322828 size=full} | {F13322834 size=full} | {F13322837 size=full} | {F13322839 size=full} |
| From Edge | {F13322843 size=full} | {F13322917 size=full} | {F13322910 size=full} | {F13322906 size=full} |
| From Face | {F13322927 size=full} | {F13322931 size=full} | | |
| From Corner | | | | {F13322936 size=full} |

topology_lookup_mockups.blend

I'm not sure how the Edge To Corner/Face groups that you built are meant to function, but in my testing, they provide no guarantee that the Corner or Face returned is adjacent to the Edge in question, rather than merely sharing a vertex. Am I doing something wrong here? ![image.png](https://archive.blender.org/developer/F13826612/image.png) > In #100020#1396393, @HooglyBoogly wrote: > I played with the mockups for a while to see if I could build some of the lookups out of others, and to experiment with the naming. > I think it's helpful to use some chart like this that shows how to find neighboring elements of each type. > Sometimes it's not so bad to build lookups from others. For example, "Vertex to Face", "Face to Vertex" and "Face to Edge" are pretty intuitive. > The others less so, but I could see that kind of flexibility being helpful anyway. I sort of got the point after a while, do I didn't do the last few. > > I think this is helpful anyway, to see which of this set of nodes are the most important. > "Face to Corner", "Corner to Vertex", "Corner to Edge", "Corner to Corner", "Vertex to Edge", and "Vertex to Corner" are probably the most important. > > | | To Vertex | To Edge | To Face | To Corner | > | From Vertex | {[F13322828](https://archive.blender.org/developer/F13322828/image.png) size=full} | {[F13322834](https://archive.blender.org/developer/F13322834/image.png) size=full} | {[F13322837](https://archive.blender.org/developer/F13322837/image.png) size=full} | {[F13322839](https://archive.blender.org/developer/F13322839/image.png) size=full} | > | From Edge | {[F13322843](https://archive.blender.org/developer/F13322843/image.png) size=full} | {[F13322917](https://archive.blender.org/developer/F13322917/image.png) size=full} | {[F13322910](https://archive.blender.org/developer/F13322910/image.png) size=full} | {[F13322906](https://archive.blender.org/developer/F13322906/image.png) size=full} | > | From Face | {[F13322927](https://archive.blender.org/developer/F13322927/image.png) size=full} | {[F13322931](https://archive.blender.org/developer/F13322931/image.png) size=full} | | | > | From Corner | | | | {[F13322936](https://archive.blender.org/developer/F13322936/image.png) size=full} | > > [topology_lookup_mockups.blend](https://archive.blender.org/developer/F13322950/topology_lookup_mockups.blend)

AgentA1cr commented

2022-12-02 15:55:15 +01:00

Just checking in on the Edge to Face/Edge to Corner issue

Hans Goudey commented

2022-12-02 16:20:18 +01:00

They probably don't work. I was just messing around with nodes to try to get an idea of what was possible, I hardly tested any of those setups. I'll bet there's another way to do it though.

AgentA1cr commented

2022-12-02 17:02:41 +01:00

I've messed with it a fair bit and haven't found anything reliable thus far. I can think of a brute-force approach that would work if you know the maximum numbers of edges per face and edges per vertex, but nothing that would work for an arbitrary number of either.

Hans Goudey commented

2022-12-02 18:11:17 +01:00

Interesting, I could see why. All this stuff is difficult until we have proper list fields. Maybe we should add a "Faces of Edge" node though, that would make it easier, and it's also a common topological query.

AgentA1cr commented

2022-12-03 03:32:38 +01:00

Yeah, that would definitely be useful, and should make corners fairly straightforward to access as well.

Sign in to join this conversation.

No Label

Download

What's New

Blender Studio

Manual

Developers Blog

Documentation

Benchmark

Blender Conference

Development Fund

One-time Donations

Curve and Mesh Topology Inputs #100020