Struct of Arrays Refactor for Mesh Face Corners #102359

New Issue

Hans Goudey · 2022-11-08T17:44:37+01:00

Hans Goudey commented

2022-11-08 17:44:37 +01:00

The Change

MLoop currently contains the index of the vertex at each face corner, and the index of the edge that connects to the next vertex in the face.

typedef struct MLoop {
  /** Vertex index into an #MVert array. */
  unsigned int v;
  /** Edge index into an #MEdge array. */
  unsigned int e;
} MLoop;

The vertex indices are always necessary, they're the ground truth of the face topology. On the other hand, the edge indices aren't necessary for much of the geometry processing in Blender.

This task describes splitting MLoop into two separate arrays, usually accessed like:

Span<int> corner_verts = mesh.corner_verts(); /* The vertex of each face corner. */
Span<int> corner_edgess = mesh.corner_edges(); /* The next edge of each face corner. */

Benefits

Memory Bandwidth

Except when building meshes from scratch, the edge and vertex indices are very rarely used at the same time. However, because they are stored together, they both have to be read from memory. Currently MLoop uses 32 MB of memory for a mesh with 1 million quads. If an algorithm need to know the vertex at each face corner, which is very common, it has to read all of that. With this change, we could skip reading 16 MB.

Code Simplicity

In the end, many algorithms boil down to simple operations with indices. We have many existing utilities for processing basic arrays with indices. Using a special type that combines two indices makes it impossible to use those utilities directly. If the indices of vertices in a face are all stored contiguously then code doesn't have to know about MLoop or meshes at all to process that data.

This simplicity makes more performance improvements possible, since efforts improving performance will affect more areas and common patterns will be more visible.

Example: Iterating over edges in faces

for (const MLoop &loop : loops.slice(poly.loopstart, poly.totloop)) {
  do_something(loop.e);
}

for (const int edge_i : corner_edges.slice(poly.loopstart, poly.totloop)) {
  do_something(edge_i);
}

Example: Collecting vertex face indices

Vector<int> poly_verts;
for (const MLoop &loop : loops.slice(poly.loopstart, poly.totloop)) {
  poly_verts.append(loop.v);
}

Span<int> poly_verts = corner_verts.slice(poly.loopstart, poly.totloop);

Example: Accessing both edges and vertices

This is the worst case for the new design, but it's still pretty much the same in the end.

for (const MLoop &loop : loops.slice(poly.loopstart, poly.totloop)) {
  do_something(loop.e, loop.v);
}

for (const int corner_i : IndexRange(poly.loopstart, poly.totloop)) {
  do_something(corner_edges[corner_i], corner_verts[corner_i]);
}

Example: Geometry Nodes Input

The implementation of the "Vertex of Corner" input node can output a span directly, giving decreased overhead for most access. This shows how the new method works better for areas that are designed around a SoA paradigm.

static int get_loop_vert(const MLoop &loop)
{
  return loop.v;
}
...
return VArray<int>::ForDerivedSpan<MLoop, get_loop_vert>(mesh.loops());

return VArray<int>::ForSpan(mesh.corner_verts());

Optional Edges

For many meshes it isn't necessary to store edges if they aren't used. If we take this change further, we could skip storing the second edge index array and skip storing MEdge completely. That would save 30 MB of memory on a 1 million face grid, and save extra processing to find loose edges, etc.

That change isn't part of this task, but it's just here to show what possibilities this change allows.

Discussion

Naming

The arrays can be called corner_vert and corner_edge, moving away from the "loop" naming completely.

"Loops" have always been a confusing name for people learning Blender code. I think moving away from that word would make the code much friendlier and more obvious. The "corner vert" name just refers to the index of the vertex at each corner. "Corner edges" are the index of the next edge around the face at each corner. Reusing the "corner" prefix is similar to the naming from other mesh domains (like "vert normals") and using the other domain as the next part of the domain makes the mapping clear.

One possible downside is that it's not clear enough that "corner edge" refers to the next edge at a face corner. But that's still much easier than learning what loop.e means.

Store as Attributes

These arrays should be stored as attributes directly, rather than a special custom data type. This follows the simple design of separating storage data type from usage semantics, and allows simpler internal data-processing. With the . name prefix, we can avoid exposing users to the low-level attributes directly but keep them available as part of the attribute API or other opt-in UI in the future.

Implementation

#104424

MLoop.e and MLoop.v are used in hundreds of places, so this is a large change-- maybe one of the bigger changes in the whole mesh refactor.
However, none of the individual changes are complex, they just cover a lot of areas.

Python API

The current Python API can remain, just like the rest of the changes in the SoA refactor (parent task). It may become slightly less efficient, so we may want to add a new API that aligns better with the internal data.

Eventually the old API could be deprecated, but there is no real reason to do that any time soon.

BMesh

BMesh also has the BMLoop type. I do not propose changing that here, since the reason for the change is performance in SoA code, which doesn't work well with BMesh anyway. Naming could be changed to align better with the new Mesh naming, but that would mostly be a separate cleanup change.

# The Change `MLoop` currently contains the index of the vertex at each face corner, and the index of the edge that connects to the next vertex in the face. ```cpp typedef struct MLoop { /** Vertex index into an #MVert array. */ unsigned int v; /** Edge index into an #MEdge array. */ unsigned int e; } MLoop; ``` The vertex indices are always necessary, they're the ground truth of the face topology. On the other hand, the edge indices aren't necessary for much of the geometry processing in Blender. This task describes splitting `MLoop` into two separate arrays, usually accessed like: ```cpp Span<int> corner_verts = mesh.corner_verts(); /* The vertex of each face corner. */ Span<int> corner_edgess = mesh.corner_edges(); /* The next edge of each face corner. */ ``` # Benefits ## Memory Bandwidth Except when building meshes from scratch, the edge and vertex indices are very rarely used at the same time. However, because they are stored together, they both have to be read from memory. Currently `MLoop` uses 32 MB of memory for a mesh with 1 million quads. If an algorithm need to know the vertex at each face corner, which is very common, it has to read all of that. With this change, we could skip reading 16 MB. ## Code Simplicity In the end, many algorithms boil down to simple operations with indices. We have many existing utilities for processing basic arrays with indices. Using a special type that combines two indices makes it impossible to use those utilities directly. If the indices of vertices in a face are all stored contiguously then code doesn't have to know about `MLoop` or meshes at all to process that data. This simplicity makes more performance improvements possible, since efforts improving performance will affect more areas and common patterns will be more visible. ### Example: Iterating over edges in faces ```cpp for (const MLoop &loop : loops.slice(poly.loopstart, poly.totloop)) { do_something(loop.e); } ``` ```cpp for (const int edge_i : corner_edges.slice(poly.loopstart, poly.totloop)) { do_something(edge_i); } ``` ### Example: Collecting vertex face indices ```cpp Vector<int> poly_verts; for (const MLoop &loop : loops.slice(poly.loopstart, poly.totloop)) { poly_verts.append(loop.v); } ``` ```cpp Span<int> poly_verts = corner_verts.slice(poly.loopstart, poly.totloop); ``` ### Example: Accessing both edges and vertices This is the worst case for the new design, but it's still pretty much the same in the end. ```cpp for (const MLoop &loop : loops.slice(poly.loopstart, poly.totloop)) { do_something(loop.e, loop.v); } ``` ```cpp for (const int corner_i : IndexRange(poly.loopstart, poly.totloop)) { do_something(corner_edges[corner_i], corner_verts[corner_i]); } ``` ### Example: Geometry Nodes Input The implementation of the "Vertex of Corner" input node can output a span directly, giving decreased overhead for most access. This shows how the new method works better for areas that are designed around a SoA paradigm. ```cpp static int get_loop_vert(const MLoop &loop) { return loop.v; } ... return VArray<int>::ForDerivedSpan<MLoop, get_loop_vert>(mesh.loops()); ``` ```cpp return VArray<int>::ForSpan(mesh.corner_verts()); ``` ## Optional Edges For many meshes it isn't necessary to store edges if they aren't used. If we take this change further, we could skip storing the second edge index array and skip storing `MEdge` completely. That would save 30 MB of memory on a 1 million face grid, and save extra processing to find loose edges, etc. That change isn't part of this task, but it's just here to show what possibilities this change allows. # Discussion ## Naming The arrays can be called `corner_vert` and `corner_edge`, moving away from the "loop" naming completely. "Loops" have always been a confusing name for people learning Blender code. I think moving away from that word would make the code much friendlier and more obvious. The "corner vert" name just refers to the index of the vertex at each corner. "Corner edges" are the index of the next edge around the face at each corner. Reusing the "corner" prefix is similar to the naming from other mesh domains (like "vert normals") and using the other domain as the next part of the domain makes the mapping clear. One possible downside is that it's not clear enough that "corner edge" refers to the *next* edge at a face corner. But that's still much easier than learning what `loop.e` means. ## Store as Attributes These arrays should be stored as attributes directly, rather than a special custom data type. This follows the simple design of separating storage data type from usage semantics, and allows simpler internal data-processing. With the `.` name prefix, we can avoid exposing users to the low-level attributes directly but keep them available as part of the attribute API or other opt-in UI in the future. # Implementation #104424 `MLoop.e` and `MLoop.v` are used in hundreds of places, so this is a large change-- maybe one of the bigger changes in the whole mesh refactor. However, none of the individual changes are complex, they just cover a lot of areas. ## Python API The current Python API can remain, just like the rest of the changes in the SoA refactor (parent task). It may become slightly less efficient, so we may want to add a new API that aligns better with the internal data. Eventually the old API could be deprecated, but there is no real reason to do that any time soon. ## BMesh BMesh also has the `BMLoop` type. I do not propose changing that here, since the reason for the change is performance in SoA code, which doesn't work well with BMesh anyway. Naming could be changed to align better with the new `Mesh` naming, but that would mostly be a separate cleanup change.

❤️ 3 🚀 1

Hans Goudey referenced this issue

2023-02-07 19:39:51 +01:00

Mesh: Replace MLoop struct with generic attributes #104424

Hans Goudey referenced this issue

2023-02-28 19:41:41 +01:00

Mesh Struct of Arrays Refactor #95965

Hans Goudey referenced this issue from a commit

2023-03-20 15:55:26 +01:00

Mesh: Replace MLoop struct with generic attributes

Hans Goudey added

Status