From aa6c922d99f7ae170f652ffd87dc852afda0af76 Mon Sep 17 00:00:00 2001
From: Erik <ecke101@gmail.com>
Date: Sat, 27 Nov 2021 19:06:07 +0100
Subject: Geometry Nodes: Optimize Cube primitive vertex calculation

This patch gets rid of the O(N^3) complexity
of calculate_vertices. Execution time of the node is
reduced from 250ms to 140ms with 500^3 vertices.
In the future edge calculations could be done manually
and reduce the execution time even further.

Differential Revision: https://developer.blender.org/D13207
---
 release/datafiles/locale                           |  2 +-
 release/scripts/addons                             |  2 +-
 release/scripts/addons_contrib                     |  2 +-
 .../geometry/nodes/node_geo_mesh_primitive_cube.cc | 40 +++++++++++++++-------
 source/tools                                       |  2 +-
 5 files changed, 31 insertions(+), 17 deletions(-)

diff --git a/release/datafiles/locale b/release/datafiles/locale
index 24c2b841925..8ee2942570f 160000
--- a/release/datafiles/locale
+++ b/release/datafiles/locale
@@ -1 +1 @@
-Subproject commit 24c2b84192564c2c06a9ab98d8e310433266c2a4
+Subproject commit 8ee2942570f08d10484bb2328d0d1b0aaaa0367c
diff --git a/release/scripts/addons b/release/scripts/addons
index 9030e2c6d1a..f2a08d80ccd 160000
--- a/release/scripts/addons
+++ b/release/scripts/addons
@@ -1 +1 @@
-Subproject commit 9030e2c6d1aca714c7122aa5b52bf2424ee4b880
+Subproject commit f2a08d80ccd3c13af304525778df3905f95bd44d
diff --git a/release/scripts/addons_contrib b/release/scripts/addons_contrib
index 7936dde9ece..16467648282 160000
--- a/release/scripts/addons_contrib
+++ b/release/scripts/addons_contrib
@@ -1 +1 @@
-Subproject commit 7936dde9ece881d531b1a2ee6c45ddb56d30038c
+Subproject commit 16467648282500cc229c271f62201ef897f2c2c3
diff --git a/source/blender/nodes/geometry/nodes/node_geo_mesh_primitive_cube.cc b/source/blender/nodes/geometry/nodes/node_geo_mesh_primitive_cube.cc
index 46325101e6c..2542542c919 100644
--- a/source/blender/nodes/geometry/nodes/node_geo_mesh_primitive_cube.cc
+++ b/source/blender/nodes/geometry/nodes/node_geo_mesh_primitive_cube.cc
@@ -77,23 +77,37 @@ static void calculate_vertices(const CuboidConfig &config, MutableSpan<MVert> ve
 
   int vert_index = 0;
 
-  /* Though looping over all possible coordinates inside the cube only to skip them may be slow,
-   * the alternative is similar complexity to below in the poly index calculation. If this loop
-   * becomes a problem in the future it could be optimized, though only after proper performance
-   * testing. */
   for (const int z : IndexRange(config.verts_z)) {
-    for (const int y : IndexRange(config.verts_y)) {
-      for (const int x : IndexRange(config.verts_x)) {
-        /* Only plot vertices on the surface of the cuboid. */
-        if (ELEM(z, 0, config.edges_z) || ELEM(x, 0, config.edges_x) ||
-            ELEM(y, 0, config.edges_y)) {
-
+    if (ELEM(z, 0, config.edges_z)) {
+      /* Fill bottom and top. */
+      const float z_pos = z_bottom + z_delta * z;
+      for (const int y : IndexRange(config.verts_y)) {
+        const float y_pos = y_front + y_delta * y;
+        for (const int x : IndexRange(config.verts_x)) {
           const float x_pos = x_left + x_delta * x;
+          copy_v3_v3(verts[vert_index++].co, float3(x_pos, y_pos, z_pos));
+        }
+      }
+    }
+    else {
+      for (const int y : IndexRange(config.verts_y)) {
+        if (ELEM(y, 0, config.edges_y)) {
+          /* Fill y-sides. */
           const float y_pos = y_front + y_delta * y;
           const float z_pos = z_bottom + z_delta * z;
-          copy_v3_v3(verts[vert_index].co, float3(x_pos, y_pos, z_pos));
-
-          vert_index++;
+          for (const int x : IndexRange(config.verts_x)) {
+            const float x_pos = x_left + x_delta * x;
+            copy_v3_v3(verts[vert_index++].co, float3(x_pos, y_pos, z_pos));
+          }
+        }
+        else {
+          /* Fill x-sides. */
+          const float x_pos = x_left;
+          const float y_pos = y_front + y_delta * y;
+          const float z_pos = z_bottom + z_delta * z;
+          copy_v3_v3(verts[vert_index++].co, float3(x_pos, y_pos, z_pos));
+          const float x_pos2 = x_left + x_delta * config.edges_x;
+          copy_v3_v3(verts[vert_index++].co, float3(x_pos2, y_pos, z_pos));
         }
       }
     }
diff --git a/source/tools b/source/tools
index b22d19e47f4..2e8c8792488 160000
--- a/source/tools
+++ b/source/tools
@@ -1 +1 @@
-Subproject commit b22d19e47f4d0353082f3d9f30ee8d244c5266d5
+Subproject commit 2e8c879248822c8e500ed49d79acc605e5aa75b9
-- 
cgit v1.2.3