I'm doing some buildings and, as some dimension varies, I found a way to center the doors and windows on specific faces selected via different materials. However the door is "lifted" up. More verticies on the upper edge more the door is shifted on +Z Axis. There is a way to stay at the center, the REAL center of that rectangle?
3 Answers
Mesh to Points
—Faces node generates the points at the average of all of each face’s vertices, so when you add more vertices at the top edge of a face by dividing the neighboring face, you're adding more Z value to that position, thus moving it up. I'm not aware of a native, simpler method, so to get the real (mass) center of the face you need to do some math. Here's a setup that would calculate the center of mass for each face:
That setup's from user LordoftheFleas on BlenderArtists. Here's a slightly simplified, updated version courtesy of @Robin-Betts:
Here's the result:
I'm attaching the blend file so instead of re-creating the setup from scratch you can just append the node group "FaceCenterOfMass" and link it to your Mesh to Points
node as you see in the screenshot.
⚠ Updated version (Blender 3.3):
⚠ 2024-11-25 update
The .blend above assumes "Triangulate" node gives index of each face being triangulated to the first resulting triangle within that face. This assumption holds true for all Blender versions so far, but since version 4.0 official documentation explicitly states it is not guaranteed:
Blender 4.0 Manual: Geometry Nodes: Inspection: Geometry Randomization
The easy fix is to use the new "Sort" node in Blender 4.0, to sort triangles by captured face index. However this would make it impossible to create a tool working both in Blender 3.3 and the potential future versions changing indices. Therefore I [MvB here] decided to reimplement the setup in Blender 3.3 LTE.
2nd problem: the setup was assuming the original face area and sum of resulting tris areas are equal, but apparently it wasn't the case. Perhaps simply "Fixed" triangulation method should be used, but what I did is just accumulate the face areas the same way positions are accumulated.
-
$\begingroup$ Brilliant. When you've got a moment. can you give a brief description of the math you're doing? Having trouble reverse-engineering. $\endgroup$– Robin Betts ♦Commented Nov 19, 2022 at 19:54
-
1$\begingroup$ @RobinBetts Found it: blenderartists.org/t/… If you can put it into words, I'm all ears. I can kinda sorta follow it, but get lost at the Accumulate Field node. $\endgroup$– KuboåCommented Nov 19, 2022 at 20:05
-
1$\begingroup$ Okydoky.. Rebuilt for 3.3 with a slightly different transfer method (I prefer by index, if possible, so as to avoid a search though geometry for 'closest') . The group finds the center of mass of a face by finding the mean location of the centers of mass of its constituent triangles, weighted by triangle-area. I /you can pop in an edit, if you like. Just IMO, but I think it might be diplomatic to credit the original author of this one. There's no shame in that :) Well found, and nicely presented! $\endgroup$– Robin Betts ♦Commented Nov 20, 2022 at 10:17
-
1$\begingroup$ @DonHatch old way And geometry randomization test (colors change, but mapping stay correct, notice I don't care which triangle of the pair I get, because in R.Betts' setup both have the same accumulated data). Using sorting: new way and test $\endgroup$ Commented Nov 26 at 10:47
-
1$\begingroup$ @MarkusvonBroady it looks like they have indeed changed the triangulation order in a way that breaks the old bad revisions of both this answer and my first one, in blender 4.4.alpha, in this change. On a cube, old order: i.sstatic.net/nSkiySAP.png new order: i.sstatic.net/kZeyFGFb.png $\endgroup$ Commented Dec 3 at 12:39
Here is a second solution, that resolves pretty much all the things I was trying to do in my first solution.
- All the "Capture Attribute" nodes are gone.
- The "Triangulate" node is gone (that must be a relatively heavyweight operation when the number of vertices on a face is large, and it's not necessary).
- The Geometry input is gone (and the Geometry output was already gone)-- so this is now a "pure field" node group (not sure whether I'm using the right word for that).
- This also turned out to be a nice exercise and example of of walking around faces and doing computations on them in geometry nodes, using the "Face of Corner", "Corners of Face", and "Vertex of Corner" nodes. I'll be using this for reference in the future. [Edit: also incorporated suggestions from Markus von Broady in comments, pointing out how to use these nodes more concisely.]
Rough details of the algorithm
Like the previous solution, this solution's overall strategy is to accumulate the moment (centroid times area) and area, and to take their quotient at the end. But this solution uses a different formula for the incremental moments and areas. It does still triangulate in a sense; however it's a cheap O(n) trivial triangulation into a triangle fan from the polygon's first vertex. (Mathematically, any point in space can be used as the hub of this triangulation; if the origin is used, then the calculations amount to using the shoelace formula projected to each of the three coordinate planes. But using one of the polygon's vertices instead helps reduce numerical error in the case that the polygon is far from the origin.) The weight for each triangle's centroid is the signed area of the triangle (more precisely, the signed area of the triangle's projection onto the polygon's best-fit plane, in a sense; that is, the plane perpendicular to the polygon's area-weighted normal vector, which is a well-defined thing for any polygon, even if skew).
This formula has the following properties for various kinds of polygons.
In the case of a non-skew non-self-intersecting polygon, the answer is the usual one, mathematically agreeing with that given by the more expensive positive-triangulation-based solutions.
For a self-intersecting non-skew polygon, this definition of center-of-mass is still mathematically well-defined and triangulation independent (unlike the previous method). On the other hand, it doesn't have the nice boundedness guarantee of the previous method, and in fact it goes to infinity (in a well-defined way) as the polygon's signed area goes to zero. In the case the polygon's signed area is exactly zero (e.g. a perfect bowtie quad), the formula will yield zero divided by zero, which blender will probably turn into the zero vector (I haven't checked).
For a skew (non-coplanar) polygon, like the previous algorithm, the answer is triangulation-dependent (in this case that just means it's dependent on the choice of "first vertex" of the polygon).
More precisely: if we decompose the answer into two components, by projecting it parallel and perpendicular to the polygon's normal, then the component perpendicular to the normal is well-defined and triangulation-independent (it is, precisely, the centroid of the planar projection of the polygon) but the component parallel to the normal is triangulation-dependent, which is unfortunate. (Research problem: it would be nice to get some kind of best-fit formula for the parallel-to-normal component that is triangulation-independent even for skew polygons; I have some ideas for this.)
Here is the geometry node graph. (Thanks to Markus von Broady for simplifications.) I have added annotations wherever there is a graph edge corresponding to a concept with a clear name, so hopefully this is mostly self-documenting for anyone wanting to inspect it in detail.
The fact that this node group is now a pure field makes it extremely easy to use. For example, it can be used as drop-in replacement for a "Position" node as the Position input to a "Mesh to Points" node, without any need to thread a Geometry through it:
-
$\begingroup$ OK, I analyzed this with exception of one thing: why the dot product part of the setup? Is it supposed to minimize the effect of triangulation on the result? I've done a naive/simplest approach of just finding a centroid for each triangle and doing a weighted average, see: i.imgur.com/6b91NQv.png your nodes purposefully left in your style so it's more visible what is changed. The maximum distance between my and your calculations is exactly 0 for Suzanne. $\endgroup$ Commented Nov 23 at 14:44
-
$\begingroup$ BIG PLUS for "pure field" (I also don't know if there's a better name), it's 10× faster, but keep in mind "Capture Attribute" isn't always slower, in fact I think the main reason it supports multiple inputs is for optimization; Blender often isn't as smart as you'd assume based on experience in programming: my tests (29 Aug '24) show "Set Position" node will evaluate raycast twice unnecessarily and you can optimize it with combining "Capture Attribute" node: 1, 2, 3 $\endgroup$ Commented Nov 23 at 14:44
-
$\begingroup$ The answer could benefit from explaining in context the shoelace, maybe even with an animation as it iterates over virtual triangles in winding order (CCW), with 2 tris having 0 area. Also consider how some people could get confused and think doubling area comes from quads having 2 tris. In general, people tend to prefer watching cat videos instead of reading, so walls of texts don't earn rep, shorter answers get much more rep, except if you add step by step explanations with visuals. And I know, not everyone wants to prostitute self for rep, but it communicates what people find helpful. $\endgroup$ Commented Nov 23 at 14:45
-
$\begingroup$ Some nitpicks: 1) you can read position of a face corner, no need to change context to vertex of the corner; 2) "Corner Index" by default uses "Index" field; 3) "Offset Corner in Face" node; 4) you used "Face of Corner: Face Index" in one place, but "Evaluate on Domain: Face" in another. $\endgroup$ Commented Nov 23 at 14:46
-
$\begingroup$ Whoops! I'm sorry, I'm actually getting a small difference between your and my methods, my comparison method had a bug. $\endgroup$ Commented Nov 23 at 15:02
EDIT 2024/11/26: The problem pointed out by Markus von Broady in comments (bad assumption about order of tris in Triangulation node result) has been fixed. The fix uses a safe efficient method of transfer from the triangulated geometry back to the original geometry, involving no "Nearest" transfer (bvh trees) and no "Sort Elements".
Note that this is my first answer; see my second answer for a leaner solution, which I prefer.
I started with Robin Betts' solution (given in Kuboå's answer before Markus von Broady's fix), and was able to simplify and tune it some more. (See Appendix at the bottom of this answer for expansion of the "Sample Inverse Index" node.)
The two "Accumulate Field" nodes are essentially the two summations in the following formula for polygon centroid (center-of-area), where the summation is over the triangles in the chosen triangulation of the polygon:
$$ \mathrm{\frac{\sum{Centroid(tri_i) Area(tri_i)}}{\sum{Area(tri_i)}}} $$
The simplifications and improvements are:
It uses only two "Capture Attribute" nodes instead of four (I'd like to use no "Capture Attribute" nodes, but I don't see how) (UPDATE: I figured it out; see my second solution)
It doesn't have a Geometry output (it seemed to be unnecessary, since it ended up being the same as the Geometry input). (I'd like to get rid of the Geometry input and all mention of Geometries, too, making this node group a "pure field", but I don't see how.) (UPDATE: I figured it out; see my second solution)
Instead of using the blender-calculated "Face Area" per-face attribute on the original faces, it calculates its own, as the sum of the triangle areas in the chosen triangulation. I think this is a good idea because it guarantees the effective per-triangle weights sum to 1, even if the polygon is slightly skew or self-intersecting (in which case this computed area will be triangulation-dependent, and in fact the thing called "Face Area" is probably computed by a different method such as the shoelace formula which will likely disagree with the sum of tri areas no matter what triangulation is chosen). That in turn guarantees the nice sanity property that the computed answer will lie within the convex hull of the input vertices, no matter how skew and snarled up the polygon is.
The screencast below demonstrates the stability improvement:
- First using TestFCM_centroid_of_vertices: the centroid is stable (stays within convex hull of verts) but of course it's not the centroid of area.
- Switch to TestFCM_robin_betts: properly computes centroid of area, but goes unstable, as expected, when the polygon is self-intersecting
- Switch to TestFCM_donhatch: properly computes centroid of area, and stable even when polygon is self-intersecting.
Another example of the stability improvement: when we run the improved solution on Suzanne, we can see that some of the wild answer points have been brought under control (so they are inside the convex hulls of the respective faces):
(Blender 4.2)
This blend file has a menu that allows you to switch among various methods described in three answers and comments, including this one:
Appendix: Expansion of the "Sample Inverse Index" node
The transfer of the answer positions from the triangles back to the original faces is encapsulated in this "Sample Inverse Index" node, shown below. This is the part that both Robin Betts's solution and my solution got wrong initially.
Some notes about this part:
This method used here is safe and fast (linear-ish): its time grows proportionately to mesh size, as expected, when it is run on suzanne with catmull-clark subdivision surface with increasing subdivision levels, each of which increases the mesh size by approximately 4x. I got times L3:36ms, L4:142ms, L5:533ms, L6:2021ms.
It does not use "Nearest" sampling (referred to as the "old way" in Markus von Broady's comments, and used in the latest revision of Kuboå's answer). "Old way" seems to be shockingly slow as mesh size increases; running it (specifically MvB's latest revision of Kuboå's answer) on suzanne with subdiv surface, I got times L3:43ms, L4:371ms, L5:5131ms, L6:199343ms (more than 3 minutes, so 98.6x slower than my way at this level).
- Further details on the surprising worse-than-quadratic asymptotic behavior of "Sample Nearest" node: I looked into this, and found that if you have a "Sample Nearest" node that makes A nearest-point queries on an attribute of size B, then for some reason Blender repeatedly creates a bvhtree on B, ⌈A/8192⌉ times, which takes takes time ⌈A/8192⌉ B log2(B). So in this application where A=B=N=(number of faces), the timing behavior is hockey-stick-shaped, starting out looking linear-ish O(N log(N)) and switching to asymptotically quadratic-ish O(N² log(N)) at around N=8192.
It does not use the "new way" ("Sort Elements" node, introduced fairly recently) either. I have not done any timing of "new way" yet, but my initial impression is that it's an unnecessarily heavy tool for this basic O(n) problem of inverting a lookup table.
Usage of this "Sample Inverse Index" node is analogous to the "Sample Index" node, except that type=Vector and domain=Face are hard-coded (I don't see a way to make those parameters/properties/options of a custom node), so if you want it on some other type and domain, you have to copy the node group and change these hard-codings inside it.
The next lower-level helper node is "Invert Mapping on Faces". Note that the domain=Faces is still hard-coded here, but the type=Vector is not. Expanded:
The next lower-level helper node after that is "Invert Mapping on Points". At this level, it works on a point cloud geometry, so this helper is fully reusable (no hard-coding of mesh element domain nor data type). Expanded:
Finally, the lowest-level helper is "Invert Permutation on Points", which is the core of the inverse-index-sampling problem: inverting a permutation. It works by first using a "Join Geometry" node to concatenate the input permutation with the identity permutation of the same length (using the ID attribute instead of anonymous attributes for simplicity), then applies an "Accumulate Field" node on the joined list with GroupID=Value and Value=Index (i.e. swapping the order of these two inputs, from how this node is usually used); then the second half of the "Trailing" output is the desired inverse permutation. See the annotations in the picture for more details of what's going on here.
-
$\begingroup$ ⚠ This solution assumes first triangle of each triangulated n-gon keeps the face index of this n-gon. However this is not guaranteed to be true in future: docs.blender.org/manual/en/4.0/modeling/geometry_nodes/… $\endgroup$ Commented Nov 22 at 13:22
-
$\begingroup$ @MarkusvonBroady Oh, my. Yes, this solution is bogus. I'm surprised the assumption holds at all. In fact, staring at this node graph now, it doesn't even look meaningful to me at all; I'm shocked that it works. Do you see a fix? I imagine it might involve putting back one or both of the "Capture Attributes" nodes that I removed from Robin Betts's solution since it seemed to work without them, but without really understanding what I was doing (and I still don't, unfortunately). $\endgroup$ Commented Nov 22 at 19:48
-
$\begingroup$ I'm thinking it would be a good idea to make and use a "triangulate and scramble" node, to make sure I'm not depending on any bogus assumptions like this. $\endgroup$ Commented Nov 22 at 19:49
-
$\begingroup$ Yes, there the original face index is stored and used for grouping in accumulate field. I still haven't had time to analyze your 2nd answer, don't be discouraged by no upvotes yet, though in general answers to old questions get next to no rep... $\endgroup$ Commented Nov 22 at 20:56
-
$\begingroup$ @MarkusvonBroady Heh, yeah I was wondering why this answer keeps getting upvotes despite it being questionable and, it turns out, bogus, while my second answer, which I think is solid (and I think I actually understand it completely, unlike this one) has gotten zero. I have added a WARNING to this one, pending fixing or discarding it. $\endgroup$ Commented Nov 22 at 23:20