From aa6c922d99f7ae170f652ffd87dc852afda0af76 Mon Sep 17 00:00:00 2001 From: Erik 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 --- .../geometry/nodes/node_geo_mesh_primitive_cube.cc | 40 +++++++++++++++------- 1 file changed, 27 insertions(+), 13 deletions(-) (limited to 'source/blender/nodes/geometry') 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 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)); } } } -- cgit v1.2.3