Details

Reviewers

Hans Goudey (HooglyBoogly)
Jacques Lucke (JacquesLucke)

Commits

rBd54a08c8af12: Geometry Nodes: Dual Mesh Node

Summary

This node calculates the dual of the input mesh. This means that faces
get replaced with vertices and vertices with faces. In principle this only
makes sense when the mesh in manifold, but there is an option to keep
the (non-manifold) boundaries of the mesh intact.

Attributes are propagated:

Point domain goes to face domain and vice versa
Edge domain and Face corner domain gets mapped to itself

Because of the duality, when the mesh is manifold, the attributes get mapped
to themselves when applying the node twice.

Thanks to Leul Mulugeta (@Leul Mulugeta (Leul)) for help with the
ascii diagrams in the code comments.

NOTE: Does not work well with some non-manifold geometry, like an edge connected to more than 2 faces, or a vertex connected to only two faces, while not being in the boundary. This is because there is no good way to define the dual at some of those points. In the following vertex you can't order the faces surrounding it in a way such that adjacent faces remain adjacent. These types of non-manifold vertices are just removed for this reason.

Examples:

With keep boundaries and without:

This video explains the propagation of attributes:

dual_mesh_attributes.blend790 KBDownload

Diff Detail

Repository

rB Blender

Branch

dual_mesh (branched from master)

Build Status

Buildable 19114
Build 19114: arc lint + arc unit

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

This is looking pretty good! Mostly suggestions for readability inline. Then the two larger notes are about face corner attributes and the next thing:

I found an issue with face normals on a simple mesh. I hope that's a bug and not a fundamental issue with the way polygons are sorted. I don't remember if I checked the normals last time I looked at this.

Dual Mesh Test.blend784 KBDownload

I assume you probably have a file full of test meshes that you've built while working on this. It would be great to add a regression test from that after this is committed, like the other geometry nodes tests.

source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc
33	Descriptions should be phrased positively, so without the "when this is true" Maybe you have a better idea, but something like `Keep non-manifold boundaries of the input mesh in place by avoiding the dual transformation there` could work.
34	I'd suggest calling this `Dual Mesh`. Even though it repeats the node name-- I think it's also important that the socket name be descriptive.
38	Replace with `data.copy_from`
92	Unfortunately there is one more case: face corner domain attributes. Since face domain attributes are moved to vertices, it's a little hard to know what to do. I'm not sure, but it looks to me like there's a 1-1 correspondence between the face corners in the input and in the output. Does that make sense?
101	It's definitely subjective, but I'd suggest a convention I've been using for this sort of copying function recently-- `src` and `dst` or `src_attribute` and `dst_attribute`. That way it's clear every time which is which. Or some other variation of that, or no change at all. Just something to consider.
190–196	`++` is a little shorter here. Also, I know I recommended a shorter integer type here, but I realized that might be problematic if a vertex is connected to more than 256 edges. I guess a fix would be avoiding the addition if it's already 3 or greater.
221	I'd suggest a more self-documenting name than "preprocess"
246	I'm probably missing something here, but isn't it expected that vertices only connected to two polygons will be boundary vertices? I'm just wondering if the checks are redundant with the information provided from the caller.
420–421	Declare variables where they are first used.
546	This isn't really a request for a change, but just a question: I was looking at this loop, which is quite large at this point, wondering about multi-threading. Looks like much of it is hard to do in parallel, but this `sort_vertex_polys` looks like it could be done in parallel, and it seems like a fairly expensive part of the algorithm. The downside would be having to allocate space for all of the edges at the beginning. So I'd guess-- probably worth it, but correctness may be more important for now.
589	Instead of reusing the variables here, it might be more readable to declare them const and give them descriptive names.

This revision now requires changes to proceed.Nov 15 2021, 10:40 PM

Rebase and adress smaller comments

Harbormaster completed remote builds in B18683: Diff 44796.Nov 16 2021, 12:34 PM

I took a look at the normals in my test file, and they are all over the place 😢
The problem is indeed that the polygon sorting is arbitrary at the moment (I tried adding a reverse at the end, and all the normals flipped).
I see two options, using normals of the input mesh to determine the sorting order this would require vertex normals to be available),
or adding a 'recalculate normals' after the computation.

source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc
38	That was what I did first, but it complains about the sizes not being the same.
246	Sadly this is not the case. Even in Suzanne there is vertex not on the boundary connected to only two faces. An example is something like this:
546	So the idea would be to do a `parallel_for` on the `vertex_poly_indices` array to sort the polygons in parallel before this loop? I think that makes sense, but would indeed need an extra allocation for all the edges.

The problem is indeed that the polygon sorting is arbitrary at the moment

Oh no, that's what I was afraid of. I think the first option you describe would be better, the second seems a bit arbitrary. Do you think the vertex normals are necessary though, or just the face normals (which are much easier to calculate)?
One reason it's worth doing is that this sorting of polygons around a vertex will come up in other situations, and it would be nice to have relatively generic code that does it.

source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc
38	Ah right. In that case, if you like, you can use `dst.take_front(src.size()).copy_from(src)`
246	Makes sense. Thanks!
546	Yeah, right. Maybe it's best to try that as a separate step after this is finished.

Hans Goudey (HooglyBoogly) mentioned this in T93203: Geometry Nodes 3.1 Targets.Nov 20 2021, 6:10 PM

Refactor poly sorting to preserve orientation
Copy over corner attributes
Use enums to make code clearer

The normals are now consistent with the input mesh. This
is done by copying the order in which the input loops go,
and thus doesn't require any normals to be calculated
beforehand.

Harbormaster completed remote builds in B18972: Diff 45280.Nov 25 2021, 2:42 PM

Sort polygons in parallel

This adds a nice speedup for bigger meshes.

Harbormaster completed remote builds in B18974: Diff 45284.Nov 25 2021, 3:57 PM

Andy Cuccaro (AndyCuccaro) removed a subscriber: Andy Cuccaro (AndyCuccaro).Nov 26 2021, 1:41 PM

Looking good! I doubt I'll have more comments the next time I look at this.

The whole file should be in its own namespace: rB1df8abff257030ba79bc23dc321f35494f4d91c5
The node type callbacks have simpler names now: rBfab39440e94d94b0a6ea8ef7771312adbab98e66

source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc
33	I noticed that "Preserve Boundaries" doesn't quite fit with the default width of the node, but "Keep Boundaries" does. What do you think about that?
41	You can use the following to make sure it's stored with a small size: enum EdgeType : int8_t{ Then you can just use `EdgeType` and `VertexType` everywhere in the code to avoid the generic `int8_t` Actually, you could even do this: enum class EdgeType : int8_t{ Loose = 0, /* No polygons connected to it. / Boundary = 1, / An edge connected to exactly one polygon. / Normal = 2, / A normal edge (connected to two polygons). / NonManifold = 3, / An edge connected to more than two polygons. */ }; Then you can refer to the enum like `EdgeType::Boundary` elsewhere in the code, which looks pretty nice in my opinion.
63	I think something like this is preferable (moving the constant check out of the loop): if (preserve_boundaries) { int out_i = 0; for (const int i : data.index_range()) { if (ELEM(vertex_map[i], VERT_TYPE_NORMAL, VERT_TYPE_BOUNDARY)) { r_data[out_i] = data[i]; out_i++; } } } else { int out_i = 0; for (const int i : data.index_range()) { if (vertex_map[i] == VERT_TYPE_NORMAL) { r_data[out_i] = data[i]; out_i++; } } }
165–175	I think this part of the comment is unnecessary now.
251	If you feel like it, an ASCII diagram explaining the relationship between the faces, edges, and corners array might be helpful. Only if you want to though.
255	The `edge_map` name is a bit misleading, maybe `edge_types` would make more sense? Here and elsewhere.
269–270	How about this? `for (const int loop_index : IndexRange(poly.loopstart, poly.totloop)) {`
286–288	Does this comment still apply? I'm having trouble understanding how that connects to the changes you did to make the normals match.
301	I don't get a warning for it for some reason, but to me this looks like an "else after break", similar to "else after return". Maybe?
347	`for (const int i : IndexRange(connected_polygons.size() - 1))`
411	This "needs_swap" variable could use a comment.
416	Switch the if else order to avoid the negation here
537	I think `Vector<std::pair<int, int>>` would be a bit more efficient (smaller vector reallocations) and more clear, since we don't care about the other stuff in `MEdge` here.
583	It might be nice to say what a "vertex like V" is, since it's not obvious the first time you read it.
618

This revision now requires changes to proceed.Nov 29 2021, 5:05 PM

Rebase master
Refactor enum to enum class
Cleanup: variable names and better comments

Harbormaster completed remote builds in B19071: Diff 45449.Nov 29 2021, 10:11 PM

Wannes Malfait (Wannes) added inline comments.Nov 29 2021, 10:12 PM

source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc
286–288	There is again a pathological case that I'm referring to here (see image). The orientation of the central n-gon in the dual is determined by the orientation of the polygon which gets chosen as first. In the top circle the orientation of the first polygon (index 4) is red, so the central n-gon is red. For the bottom circle the orientation of the first polygon (index 0) is blue, so the central n-gon is blue. For the boundaries, the same thing applies, although the situation is a little bit different here because the first polygon needs to have a boundary edge. TLDR: If the polygons around a vertex have inconsistent orientations, then the resulting polygon will pretty much have a random orientation.
537	I was using `MEdge` because it lets me 'transfer' things like sharp and seam edges. Not sure if we should just ignore those completely.

Just some notes on comment formatting and a style comment, otherwise this looks good!

source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc
50–64	I'd suggest two changes here: Add return statements in the switch, to avoid the need for a variable and a `break` Add the assert outside the switch to avoid the need for `default` Same for the vertex switch
148–150	Like wrapping is a little weird here:
286–288	Okay, thanks for the explanation! Let's make sure these examples get into the manual and a regression test :)
288–308	IMO this is a bit easier to read if these two are next to each other:
681–705	I think it's nice to take up a little less space for this, maybe it could be horizontal too? I also think the "thanks" note belongs in the commit message/patch description rather than the node.

Please provide a file that shows the attribute propagation working in the original post. The file can be a bit similar to the one in D13338.

source/blender/nodes/geometry/nodes/node_geo_dual_mesh.cc
32	Add `.supported_type(GEO_COMPONENT_TYPE_MESH)`.
53	Return the new edge type directly. Remove the `default` case and add `BLI_assert_unreachable` after the switch. After the assert just return `Loose` (doesn't matter).

This revision now requires changes to proceed.Nov 30 2021, 5:03 PM

Fix corner attribute interpolating
Cleanup: comments and switch case

Harbormaster completed remote builds in B19112: Diff 45506.Nov 30 2021, 8:50 PM

Wannes Malfait (Wannes) edited the summary of this revision. (Show Details)Nov 30 2021, 8:56 PM

Wannes Malfait (Wannes) edited the summary of this revision. (Show Details)Nov 30 2021, 9:21 PM

Face attribute propagation for boundary vertices

Previously boundary verts where ignored in face attribute
propagation because they don't come from faces. With this
it copies the attribute from the nearest face for boundary
vertices. (Nearest face, because faces get mapped to points
in the dual so face attributes are converted to point
attributes.)

Harbormaster completed remote builds in B19114: Diff 45510.Nov 30 2021, 11:11 PM

Jacques Lucke (JacquesLucke) accepted this revision.Dec 1 2021, 11:57 AM

Jacques Lucke (JacquesLucke) added inline comments.