blender
/
blender
136
406
Fork 589
Code Issues 6.2k Pull Requests 758 Projects 19 Wiki Activity

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
This commit is contained in:
Erik Abrahamsson 2021-11-27 19:06:07 +01:00
parent d2f4fb68f5
commit aa6c922d99
5 changed files with 31 additions and 17 deletions
Show Stats Download Patch File Download Diff File Expand all files Collapse all files

2
release/datafiles/locale

@ -1 +1 @@
Subproject commit 24c2b84192564c2c06a9ab98d8e310433266c2a4
Subproject commit 8ee2942570f08d10484bb2328d0d1b0aaaa0367c

2
release/scripts/addons

@ -1 +1 @@
Subproject commit 9030e2c6d1aca714c7122aa5b52bf2424ee4b880
Subproject commit f2a08d80ccd3c13af304525778df3905f95bd44d

2
release/scripts/addons_contrib

@ -1 +1 @@
Subproject commit 7936dde9ece881d531b1a2ee6c45ddb56d30038c
Subproject commit 16467648282500cc229c271f62201ef897f2c2c3

40
source/blender/nodes/geometry/nodes/node_geo_mesh_primitive_cube.cc
View File

@ -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));
}
}
}

2
source/tools

@ -1 +1 @@
Subproject commit b22d19e47f4d0353082f3d9f30ee8d244c5266d5
Subproject commit 2e8c879248822c8e500ed49d79acc605e5aa75b9