Edit Mesh: partial updates for normal and face tessellation

This patch exposes functionality for performing partial mesh updates
for normal calculation and face tessellation while transforming a mesh.

The partial update data only needs to be generated once,
afterwards the cached connectivity information can be reused
(with the exception of changing proportional editing radius).

Currently this is only used for transform, in the future it could be
used for other operators as well as the transform panel.

The best-case overall speedup while transforming geometry is about
1.45x since the time to update a small number of normals and faces is
negligible.

For an additional speedup partial face tessellation is multi-threaded,
this gives ~15x speedup on my system (timing tessellation alone).
Exact results depend on the number of CPU cores available.

Ref D11494

Reviewed By: mano-wii

1 files changed, 69 insertions, 0 deletions

diff --git a/source/blender/bmesh/intern/bmesh_mesh_partial_update.h b/source/blender/bmesh/intern/bmesh_mesh_partial_update.h
new file mode 100644
index 00000000000..c0c9b275fa4
--- /dev/null
+++ b/source/blender/bmesh/intern/bmesh_mesh_partial_update.h
@@ -0,0 +1,69 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+#pragma once
+
+/** \file
+ * \ingroup bmesh
+ */
+
+#include "BLI_compiler_attrs.h"
+
+/**
+ * Parameters used to determine which kinds of data needs to be generated.
+ */
+typedef struct BMPartialUpdate_Params {
+  bool do_normals;
+  bool do_tessellate;
+} BMPartialUpdate_Params;
+
+/**
+ * Cached data to speed up partial updates.
+ *
+ * Hints:
+ *
+ * - Avoid creating this data for single updates,
+ *   it should be created and reused across multiple updates to gain a significant benefit
+ *   (while transforming geometry for example).
+ *
+ * - Partial normal updates use face & loop indices,
+ *   setting them to dirty values between updates will slow down normal recalculation.
+ */
+typedef struct BMPartialUpdate {
+  BMVert **verts;
+  BMEdge **edges;
+  BMFace **faces;
+  int verts_len, verts_len_alloc;
+  int edges_len, edges_len_alloc;
+  int faces_len, faces_len_alloc;
+  /**
+   * Faces at the end of `faces` that don't need to have the normals recalculated
+   * but must be included when waiting the vertex normals.
+   */
+  int faces_len_normal_calc_accumulate;
+
+  /** Store the parameters used in creation so invalid use can be asserted. */
+  BMPartialUpdate_Params params;
+} BMPartialUpdate;
+
+BMPartialUpdate *BM_mesh_partial_create_from_verts(BMesh *bm,
+                                                   const BMPartialUpdate_Params *params,
+                                                   const int verts_len,
+                                                   bool (*filter_fn)(BMVert *, void *user_data),
+                                                   void *user_data)
+    ATTR_NONNULL(1, 2, 4) ATTR_WARN_UNUSED_RESULT;
+
+void BM_mesh_partial_destroy(BMPartialUpdate *bmpinfo) ATTR_NONNULL(1);