Geometry Nodes: Greatly improve speed of some mesh primitives

Some of the BMesh primitive operators have a lot of overhead due to the
fact that they use other operators like extrusion, removing doubles,
and rotation, to build each shape rather than filling arrays directly.

Implementing the primitives directly with the Mesh data structure is
much more efficient, since it's simple to fill the result data based
on the known inputs. It also allows also skip the conversion from BMesh
to Mesh after the calculations.

Speed matters more for procedural operations than for the existing
operators accessible from the add menu, since they will be executed
every evaluation rather than once before a destructive workflow.

| Shape    |  Before (ms) |  After (ms) | Speedup (x times faster) |
| -------- | -------------| ------------| -------------------------|
| Cylinder | 1.1676       | 0.31327     | 3.72                     |
| Cone     | 4.5890       | 0.17762     | 25.8                     |
| Sphere   | 64213.3      | 13.595      | 4720                     |

The downside of this change is that there will be two implementations
for these three primitives, in these nodes and in `bmo_primitive.c`.
One option would be re-implementing the BMesh primitives in terms of
this code, but that would require `BMesh` to depend on `Mesh`, which
is currently avoided. On the other hand, it will be easier to add new
features to these nodes like different fill types for the top and the
bottom of a cylinder, rings for a cylinder, and tagging the output with
boolean attributes. Another factor to consider is that the add mesh
object operator could be implemented with these nodes, just providing
more benefit for a faster implementation.

As a future cleanup, there is room to share code that generates the
"rings" topology between different nodes that generate meshes.

Differential Revision: https://developer.blender.org/D10730

1 files changed, 220 insertions, 30 deletions

diff --git a/source/blender/nodes/geometry/nodes/node_geo_mesh_primitive_uv_sphere.cc b/source/blender/nodes/geometry/nodes/node_geo_mesh_primitive_uv_sphere.cc
index 8efba91da1a..3c8d2b5e924 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_mesh_primitive_uv_sphere.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_mesh_primitive_uv_sphere.cc
@@ -17,19 +17,16 @@
 #include "DNA_mesh_types.h"
 #include "DNA_meshdata_types.h"
 
-#include "BKE_lib_id.h"
 #include "BKE_mesh.h"
 
 #include "UI_interface.h"
 #include "UI_resources.h"
 
-#include "bmesh.h"
-
 #include "node_geometry_util.hh"
 
 static bNodeSocketTemplate geo_node_mesh_primitive_uv_sphere_in[] = {
     {SOCK_INT, N_("Segments"), 32, 0.0f, 0.0f, 0.0f, 3, 1024},
-    {SOCK_INT, N_("Rings"), 16, 0.0f, 0.0f, 0.0f, 3, 1024},
+    {SOCK_INT, N_("Rings"), 16, 0.0f, 0.0f, 0.0f, 2, 1024},
     {SOCK_FLOAT, N_("Radius"), 1.0f, 0.0f, 0.0f, 0.0f, 0.0f, FLT_MAX, PROP_DISTANCE},
     {-1, ""},
 };
@@ -65,31 +62,224 @@ static int sphere_face_total(const int segments, const int rings)
   return quads + triangles;
 }
 
-static Mesh *create_uv_sphere_mesh_bmesh(const float radius, const int segments, const int rings)
+static void calculate_sphere_vertex_data(MutableSpan<MVert> verts,
+                                         const float radius,
+                                         const int segments,
+                                         const int rings)
+{
+  const float delta_theta = M_PI / rings;
+  const float delta_phi = (2 * M_PI) / segments;
+
+  copy_v3_v3(verts[0].co, float3(0.0f, 0.0f, radius));
+  normal_float_to_short_v3(verts[0].no, float3(0.0f, 0.0f, 1.0f));
+
+  int vert_index = 1;
+  float theta = delta_theta;
+  for (const int UNUSED(ring) : IndexRange(rings - 1)) {
+    float phi = 0.0f;
+    const float z = cosf(theta);
+    for (const int UNUSED(segment) : IndexRange(segments)) {
+      const float sin_theta = std::sin(theta);
+      const float x = sin_theta * std::cos(phi);
+      const float y = sin_theta * std::sin(phi);
+      copy_v3_v3(verts[vert_index].co, float3(x, y, z) * radius);
+      normal_float_to_short_v3(verts[vert_index].no, float3(x, y, z));
+      phi += delta_phi;
+      vert_index++;
+    }
+    theta += delta_theta;
+  }
+
+  copy_v3_v3(verts.last().co, float3(0.0f, 0.0f, -radius));
+  normal_float_to_short_v3(verts.last().no, float3(0.0f, 0.0f, -1.0f));
+}
+
+static void calculate_sphere_edge_indices(MutableSpan<MEdge> edges,
+                                          const int segments,
+                                          const int rings)
+{
+  int edge_index = 0;
+
+  /* Add the edges connecting the top vertex to the first ring. */
+  const int first_vert_ring_index_start = 1;
+  for (const int segment : IndexRange(segments)) {
+    MEdge &edge = edges[edge_index++];
+    edge.v1 = 0;
+    edge.v2 = first_vert_ring_index_start + segment;
+    edge.flag = ME_EDGEDRAW | ME_EDGERENDER;
+  }
+
+  int ring_vert_index_start = 1;
+  for (const int ring : IndexRange(rings - 1)) {
+    const int next_ring_vert_index_start = ring_vert_index_start + segments;
+
+    /* Add the edges running along each ring. */
+    for (const int segment : IndexRange(segments)) {
+      MEdge &edge = edges[edge_index++];
+      edge.v1 = ring_vert_index_start + segment;
+      edge.v2 = ring_vert_index_start + ((segment + 1) % segments);
+      edge.flag = ME_EDGEDRAW | ME_EDGERENDER;
+    }
+
+    /* Add the edges connecting to the next ring. */
+    if (ring < rings - 2) {
+      for (const int segment : IndexRange(segments)) {
+        MEdge &edge = edges[edge_index++];
+        edge.v1 = ring_vert_index_start + segment;
+        edge.v2 = next_ring_vert_index_start + segment;
+        edge.flag = ME_EDGEDRAW | ME_EDGERENDER;
+      }
+    }
+    ring_vert_index_start += segments;
+  }
+
+  /* Add the edges connecting the last ring to the bottom vertex. */
+  const int last_vert_index = sphere_vert_total(segments, rings) - 1;
+  const int last_vert_ring_start = last_vert_index - segments;
+  for (const int segment : IndexRange(segments)) {
+    MEdge &edge = edges[edge_index++];
+    edge.v1 = last_vert_index;
+    edge.v2 = last_vert_ring_start + segment;
+    edge.flag = ME_EDGEDRAW | ME_EDGERENDER;
+  }
+}
+
+static void calculate_sphere_faces(MutableSpan<MLoop> loops,
+                                   MutableSpan<MPoly> polys,
+                                   const int segments,
+                                   const int rings)
 {
-  const float4x4 transform = float4x4::identity();
-
-  const BMeshCreateParams bmcp = {true};
-  const BMAllocTemplate allocsize = {sphere_vert_total(segments, rings),
-                                     sphere_edge_total(segments, rings),
-                                     sphere_corner_total(segments, rings),
-                                     sphere_face_total(segments, rings)};
-  BMesh *bm = BM_mesh_create(&allocsize, &bmcp);
-
-  BMO_op_callf(bm,
-               BMO_FLAG_DEFAULTS,
-               "create_uvsphere u_segments=%i v_segments=%i diameter=%f matrix=%m4 calc_uvs=%b",
-               segments,
-               rings,
-               radius,
-               transform.values,
-               true);
-
-  BMeshToMeshParams params{};
-  params.calc_object_remap = false;
-  Mesh *mesh = (Mesh *)BKE_id_new_nomain(ID_ME, nullptr);
-  BM_mesh_bm_to_me(nullptr, bm, mesh, &params);
-  BM_mesh_free(bm);
+  int loop_index = 0;
+  int poly_index = 0;
+
+  /* Add the triangles conntected to the top vertex. */
+  const int first_vert_ring_index_start = 1;
+  for (const int segment : IndexRange(segments)) {
+    MPoly &poly = polys[poly_index++];
+    poly.loopstart = loop_index;
+    poly.totloop = 3;
+    MLoop &loop_a = loops[loop_index++];
+    loop_a.v = 0;
+    loop_a.e = segment;
+    MLoop &loop_b = loops[loop_index++];
+    loop_b.v = first_vert_ring_index_start + segment;
+    loop_b.e = segments + segment;
+    MLoop &loop_c = loops[loop_index++];
+    loop_c.v = first_vert_ring_index_start + (segment + 1) % segments;
+    loop_c.e = (segment + 1) % segments;
+  }
+
+  int ring_vert_index_start = 1;
+  int ring_edge_index_start = segments;
+  for (const int UNUSED(ring) : IndexRange(1, rings - 2)) {
+    const int next_ring_vert_index_start = ring_vert_index_start + segments;
+    const int next_ring_edge_index_start = ring_edge_index_start + segments * 2;
+    const int ring_vertical_edge_index_start = ring_edge_index_start + segments;
+
+    for (const int segment : IndexRange(segments)) {
+      MPoly &poly = polys[poly_index++];
+      poly.loopstart = loop_index;
+      poly.totloop = 4;
+
+      MLoop &loop_a = loops[loop_index++];
+      loop_a.v = ring_vert_index_start + segment;
+      loop_a.e = ring_vertical_edge_index_start + segment;
+      MLoop &loop_b = loops[loop_index++];
+      loop_b.v = next_ring_vert_index_start + segment;
+      loop_b.e = next_ring_edge_index_start + segment;
+      MLoop &loop_c = loops[loop_index++];
+      loop_c.v = next_ring_vert_index_start + (segment + 1) % segments;
+      loop_c.e = ring_vertical_edge_index_start + (segment + 1) % segments;
+      MLoop &loop_d = loops[loop_index++];
+      loop_d.v = ring_vert_index_start + (segment + 1) % segments;
+      loop_d.e = ring_edge_index_start + segment;
+    }
+    ring_vert_index_start += segments;
+    ring_edge_index_start += segments * 2;
+  }
+
+  /* Add the triangles connected to the bottom vertex. */
+  const int last_edge_ring_start = segments * (rings - 2) * 2 + segments;
+  const int bottom_edge_fan_start = last_edge_ring_start + segments;
+  const int last_vert_index = sphere_vert_total(segments, rings) - 1;
+  const int last_vert_ring_start = last_vert_index - segments;
+  for (const int segment : IndexRange(segments)) {
+    MPoly &poly = polys[poly_index++];
+    poly.loopstart = loop_index;
+    poly.totloop = 3;
+
+    MLoop &loop_a = loops[loop_index++];
+    loop_a.v = last_vert_index;
+    loop_a.e = bottom_edge_fan_start + (segment + 1) % segments;
+    MLoop &loop_b = loops[loop_index++];
+    loop_b.v = last_vert_ring_start + (segment + 1) % segments;
+    loop_b.e = last_edge_ring_start + segment;
+    MLoop &loop_c = loops[loop_index++];
+    loop_c.v = last_vert_ring_start + segment;
+    loop_c.e = bottom_edge_fan_start + segment;
+  }
+}
+
+static void calculate_sphere_uvs(Mesh *mesh, const float segments, const float rings)
+{
+  MeshComponent mesh_component;
+  mesh_component.replace(mesh, GeometryOwnershipType::Editable);
+  OutputAttributePtr uv_attribute = mesh_component.attribute_try_get_for_output(
+      "uv_map", ATTR_DOMAIN_CORNER, CD_PROP_FLOAT2, nullptr);
+  MutableSpan<float2> uvs = uv_attribute->get_span_for_write_only<float2>();
+
+  int loop_index = 0;
+  const float dy = 1.0f / rings;
+
+  for (const int i_segment : IndexRange(segments)) {
+    const float segment = static_cast<float>(i_segment);
+    uvs[loop_index++] = float2((segment + 0.5f) / segments, 0.0f);
+    uvs[loop_index++] = float2(segment / segments, dy);
+    uvs[loop_index++] = float2((segment + 1.0f) / segments, dy);
+  }
+
+  for (const int i_ring : IndexRange(1, rings - 2)) {
+    const float ring = static_cast<float>(i_ring);
+    for (const int i_segment : IndexRange(segments)) {
+      const float segment = static_cast<float>(i_segment);
+      uvs[loop_index++] = float2(segment / segments, ring / rings);
+      uvs[loop_index++] = float2(segment / segments, (ring + 1.0f) / rings);
+      uvs[loop_index++] = float2((segment + 1.0f) / segments, (ring + 1.0f) / rings);
+      uvs[loop_index++] = float2((segment + 1.0f) / segments, ring / rings);
+    }
+  }
+
+  for (const int i_segment : IndexRange(segments)) {
+    const float segment = static_cast<float>(i_segment);
+    uvs[loop_index++] = float2((segment + 0.5f) / segments, 1.0f);
+    uvs[loop_index++] = float2((segment + 1.0f) / segments, 1.0f - dy);
+    uvs[loop_index++] = float2(segment / segments, 1.0f - dy);
+  }
+
+  uv_attribute.apply_span_and_save();
+}
+
+static Mesh *create_uv_sphere_mesh(const float radius, const int segments, const int rings)
+{
+  Mesh *mesh = BKE_mesh_new_nomain(sphere_vert_total(segments, rings),
+                                   sphere_edge_total(segments, rings),
+                                   0,
+                                   sphere_corner_total(segments, rings),
+                                   sphere_face_total(segments, rings));
+  MutableSpan<MVert> verts{mesh->mvert, mesh->totvert};
+  MutableSpan<MLoop> loops{mesh->mloop, mesh->totloop};
+  MutableSpan<MEdge> edges{mesh->medge, mesh->totedge};
+  MutableSpan<MPoly> polys{mesh->mpoly, mesh->totpoly};
+
+  calculate_sphere_vertex_data(verts, radius, segments, rings);
+
+  calculate_sphere_edge_indices(edges, segments, rings);
+
+  calculate_sphere_faces(loops, polys, segments, rings);
+
+  calculate_sphere_uvs(mesh, segments, rings);
+
+  BLI_assert(BKE_mesh_is_valid(mesh));
 
   return mesh;
 }
@@ -98,14 +288,14 @@ static void geo_node_mesh_primitive_uv_sphere_exec(GeoNodeExecParams params)
 {
   const int segments_num = params.extract_input<int>("Segments");
   const int rings_num = params.extract_input<int>("Rings");
-  if (segments_num < 3 || rings_num < 3) {
+  if (segments_num < 3 || rings_num < 2) {
     params.set_output("Geometry", GeometrySet());
     return;
   }
 
   const float radius = params.extract_input<float>("Radius");
 
-  Mesh *mesh = create_uv_sphere_mesh_bmesh(radius, segments_num, rings_num);
+  Mesh *mesh = create_uv_sphere_mesh(radius, segments_num, rings_num);
   params.set_output("Geometry", GeometrySet::create_with_mesh(mesh));
 }