Mon Oct 19 13:25:59 CEST 2020

Commit: f68493f5bee352d4a7feb90c2488a264607c84ac
Author: Joseph Eagar
Date:   Mon Oct 19 04:10:34 2020 -0700
Branches: temp-trimesh-sculpt
https://developer.blender.org/rBf68493f5bee352d4a7feb90c2488a264607c84ac

Little design study for new API to replace various pbvh/sculpt
iterators (uncomment PROXY_ADVANCED in BKE_pbvh to enable):
 + Same idea as existing pbvh proxies.
 + Based on "struct of arrays" approach.
 + New ProxyVeryArray structure holds all the coordinates,
   normals, indices, neighbor references, color, mask, etc
   data--basically everything in PBVHVertIter and SculptNeightborIter.
 + Only the desired data is stored.  Client code can pass a mask
   stating which data layers it wants; e.g. normals, coordiantes, etc.

There's a lot of advantages to this approach: simpler and more
maintainable code, possibility of SSE/opencl/cuda vectorization down
the line, etc.

More importantly for this branch, it should be a great profiling tool.
No more trying to figure out which bit of API cruft is causing the CPU
cache to go haywire.  I can eliminate a lot of performance bugs and
concentrate on the ones related to DynTopo.

===================================================================

M	source/blender/blenkernel/BKE_pbvh.h
M	source/blender/blenkernel/intern/pbvh.c
M	source/blender/blenkernel/intern/pbvh_intern.h
M	source/blender/editors/sculpt_paint/sculpt.c
M	source/blender/editors/sculpt_paint/sculpt_intern.h
M	source/blender/editors/sculpt_paint/sculpt_smooth.c

===================================================================

diff --git a/source/blender/blenkernel/BKE_pbvh.h b/source/blender/blenkernel/BKE_pbvh.h
index 73718ba33bf..3cdbad8885e 100644
--- a/source/blender/blenkernel/BKE_pbvh.h
+++ b/source/blender/blenkernel/BKE_pbvh.h
@@ -58,6 +58,77 @@ struct TaskParallelTLS;
 typedef struct PBVH PBVH;
 typedef struct PBVHNode PBVHNode;
 
+#define PROXY_ADVANCED
+
+// experimental performance test of "data-based programming" approach
+#ifdef PROXY_ADVANCED
+typedef struct ProxyKey {
+  int node;
+  int pindex;
+} ProxyKey;
+
+#  define MAX_PROXY_NEIGHBORS 12
+
+typedef struct ProxyVertArray {
+  float **ownerco;
+  short **ownerno;
+  float (*co)[3];
+  float (*fno)[3];
+  short (*no)[3];
+  float *mask, **ownermask;
+  int *index;
+  float **ownercolor, (*color)[4];
+
+  ProxyKey (*neighbors)[MAX_PROXY_NEIGHBORS];
+
+  int size;
+  int datamask;
+
+  GHash *indexmap;
+} ProxyVertArray;
+
+typedef enum {
+  PV_OWNERCO = 1,
+  PV_OWNERNO = 2,
+  PV_CO = 4,
+  PV_NO = 8,
+  PV_MASK = 16,
+  PV_OWNERMASK = 32,
+  PV_INDEX = 64,
+  PV_OWNERCOLOR = 128,
+  PV_COLOR = 256,
+  PV_NEIGHBORS = 512
+} ProxyVertField;
+
+typedef struct ProxyVertUpdateRec {
+  float *co, *no, *mask, *color;
+  int index, newindex;
+} ProxyVertUpdateRec;
+
+#  define PBVH_PROXY_DEFAULT CO | INDEX | MASK
+
+struct SculptSession;
+
+void BKE_pbvh_ensure_proxyarrays(struct SculptSession *ss, PBVH *pbvh, int mask);
+void BKE_pbvh_load_proxyarrays(PBVH *pbvh, PBVHNode **nodes, int totnode, int mask);
+
+void BKE_pbvh_ensure_proxyarray(
+    struct SculptSession *ss,
+    struct PBVH *pbvh,
+    struct PBVHNode *node,
+    int mask,
+    struct GHash
+        *vert_node_map,  // vert_node_map maps vertex SculptIdxs to PBVHNode indices; optional
+    bool check_indexmap,
+    bool force_update);
+void BKE_pbvh_gather_proxyarray(PBVH *pbvh, PBVHNode **nodes, int totnode);
+
+void BKE_pbvh_free_proxyarray(struct PBVH *pbvh, struct PBVHNode *node);
+void BKE_pbvh_update_proxyvert(struct PBVH *pbvh, struct PBVHNode *node, ProxyVertUpdateRec *rec);
+ProxyVertArray *BKE_pbvh_get_proxyarrays(struct PBVH *pbvh, struct PBVHNode *node);
+
+#endif
+
 typedef struct {
   float (*co)[3];
 } PBVHProxyNode;
@@ -107,12 +178,16 @@ void TMElemSet_remove(TMElemSet *ts, void *elem, bool ignoreExist);
 bool TMElemSet_has(TMElemSet *ts, void *elem);
 
 #define TMS_ITER(v, ts) \
-{int _i1; for (_i1=0; _i1<ts->cur; _i1++) {\
-  if (!ts->elems[_i1])\
-    continue;\
-  v = ts->elems[_i1];
-
-#define TMS_ITER_END }}
+  { \
+    int _i1; \
+    for (_i1 = 0; _i1 < ts->cur; _i1++) { \
+      if (!ts->elems[_i1]) \
+        continue; \
+      v = ts->elems[_i1];
+
+#define TMS_ITER_END \
+  } \
+  }
 
 void BKE_pbvh_set_frustum_planes(PBVH *pbvh, PBVHFrustumPlanes *planes);
 void BKE_pbvh_get_frustum_planes(PBVH *pbvh, PBVHFrustumPlanes *planes);
@@ -155,14 +230,14 @@ void BKE_pbvh_build_bmesh(PBVH *pbvh,
                           const int cd_vert_node_offset,
                           const int cd_face_node_offset);
 void BKE_pbvh_build_trimesh(PBVH *bvh,
-  struct TM_TriMesh *bm,
-  bool smooth_shading,
-  struct TriMeshLog *log,
-  const int cd_vert_node_offset,
-  const int cd_face_node_offset);
+                            struct TM_TriMesh *bm,
+                            bool smooth_shading,
+                            struct TriMeshLog *log,
+                            const int cd_vert_node_offset,
+                            const int cd_face_node_offset);
 
 void BKE_pbvh_free(PBVH *bvh);
-//void BKE_pbvh_free_layer_disp(PBVH *bvh);
+// void BKE_pbvh_free_layer_disp(PBVH *bvh);
 
 /* Hierarchical Search in the BVH, two methods:
  * - for each hit calling a callback
@@ -207,10 +282,10 @@ bool BKE_pbvh_bmesh_node_raycast_detail(PBVHNode *node,
                                         float *depth,
                                         float *r_edge_length);
 bool BKE_pbvh_trimesh_node_raycast_detail(PBVHNode *node,
-  const float ray_start[3],
-  struct IsectRayPrecalc *isect_precalc,
-  float *depth,
-  float *r_edge_length);
+                                          const float ray_start[3],
+                                          struct IsectRayPrecalc *isect_precalc,
+                                          float *depth,
+                                          float *r_edge_length);
 
 /* for orthographic cameras, project the far away ray segment points to the root node so
  * we can have better precision. */
@@ -248,12 +323,7 @@ void BKE_pbvh_draw_debug_cb(
     void *user_data);
 
 /* PBVH Access */
-typedef enum {
-  PBVH_FACES,
-  PBVH_GRIDS,
-  PBVH_BMESH,
-  PBVH_TRIMESH
-} PBVHType;
+typedef enum { PBVH_FACES, PBVH_GRIDS, PBVH_BMESH, PBVH_TRIMESH } PBVHType;
 
 PBVHType BKE_pbvh_type(const PBVH *pbvh);
 bool BKE_pbvh_has_faces(const PBVH *pbvh);
@@ -297,12 +367,13 @@ bool BKE_pbvh_bmesh_update_topology(PBVH *pbvh,
                                     const bool use_projected);
 
 bool BKE_pbvh_trimesh_update_topology(PBVH *bvh,
-  PBVHTopologyUpdateMode mode,
-  const float center[3],
-  const float view_normal[3],
-  float radius,
-  const bool use_frontface,
-  const bool use_projected, int sym_axis);
+                                      PBVHTopologyUpdateMode mode,
+                                      const float center[3],
+                                      const float view_normal[3],
+                                      float radius,
+                                      const bool use_frontface,
+                                      const bool use_projected,
+                                      int sym_axis);
 /* Node Access */
 
 void BKE_pbvh_node_mark_update(PBVHNode *node);
@@ -503,30 +574,32 @@ void pbvh_vertex_iter_init(PBVH *pbvh, PBVHNode *node, PBVHVertexIter *vi, int m
           } \
         } \
         else if (vi.tm_vdata) { \
-          TMVert *tv = NULL;\
-          while (!tv) {\
-            if (!vi.tm_cur_set->elems || vi.ti >= vi.tm_cur_set->cur) {\
-              if (vi.tm_cur_set != vi.tm_other_verts) {\
-                vi.tm_cur_set = vi.tm_other_verts;\
-                vi.ti = 0;\
-                if (!vi.tm_cur_set->elems || vi.ti >= vi.tm_other_verts->cur) {\
-                  break;\
-                }\
-              } else {\
-                break;\
-              }\
-            } else {\
-              tv = vi.tm_cur_set->elems[vi.ti++];\
-              if (tv && BLI_safepool_elem_is_dead(tv)) {\
-                printf("dead vert: %p\n", tv);\
-                tv = NULL;\
-              }\
-            }\
-          }\
-          if (!tv) {\
-            continue;\
-          }\
-          vi.tm_vert = tv;\
+          TMVert *tv = NULL; \
+          while (!tv) { \
+            if (!vi.tm_cur_set->elems || vi.ti >= vi.tm_cur_set->cur) { \
+              if (vi.tm_cur_set != vi.tm_other_verts) { \
+                vi.tm_cur_set = vi.tm_other_verts; \
+                vi.ti = 0; \
+                if (!vi.tm_cur_set->elems || vi.ti >= vi.tm_other_verts->cur) { \
+                  break; \
+                } \
+              } \
+              else { \
+                break; \
+              } \
+            } \
+            else { \
+              tv = vi.tm_cur_set->elems[vi.ti++]; \
+              if (tv && BLI_safepool_elem_is_dead(tv)) { \
+                printf("dead vert: %p\n", tv); \
+                tv = NULL; \
+              } \
+            } \
+          } \
+          if (!tv) { \
+            continue; \
+          } \
+          vi.tm_vert = tv; \
           vi.visible = !TM_elem_flag_test_bool(vi.tm_vert, TM_ELEM_HIDDEN); \
           if (mode == PBVH_ITER_UNIQUE && !vi.visible) { \
             continue; \
@@ -535,7 +608,7 @@ void pbvh_vertex_iter_init(PBVH *pbvh, PBVHNode *node, PBVHVertexIter *vi, int m
           vi.fno = vi.tm_vert->no; \
           vi.index = (SculptIdx)vi.tm_vert; \
           vi.mask = TM_ELEM_CD_GET_VOID_P(vi.tm_vert, vi.cd_vert_mask_offset); \
-        }\
+        } \
         else { \
           if (!BLI_gsetIterator_done(&vi.bm_unique_verts)) { \
             vi.bm_vert = BLI_gsetIterator_getKey(&vi.bm_unique_verts); \
diff --git a/source/blender/blenkernel/intern/pbvh.c b/source/blender/blenkernel/intern/pbvh.c
index 59320ca0d49..773565b4b24 100644
--- a/source/blender/blenkernel/intern/pbvh.c
+++ b/source/blender/blenkernel/intern/pbvh.c
@@ -2451,7 +2451,7 @@ bool BKE_pbvh_node_raycast(PBVH *pbvh,
                                     face_normal);
       break;
     case PBVH_TRIMESH:
-      //TM_mesh_elem_index_ensure(pbvh->tm, TM_VERTEX);
+      // TM_mesh_elem_index_ensure(pbvh->tm, TM_VERTEX);
       hit = pbvh_trimesh_node_raycast(node,
                                       ray_start,
                                       ray_normal,
@@ -3003,16 +3003,18 @@ PBVHProxyNode *BKE_pbvh_node_add_proxy(PBVH *pbvh, PBVHNode *node)
   return node->proxies + index;
 }
 
-void BKE_pbvh_node_free_proxies(PBVHNode *node)
+void BKE_pbvh_node_free_proxies(PBVH *pbvh, PBVHNode *node)
 {
   for (int p = 0; p < node->proxy_count; p++) {
     MEM_freeN(node->proxies[p].co);
     node->proxies[p].co = NULL;
   }
 
-  MEM_freeN(node->proxies);
-  node->proxies = NULL;
+  if (node->proxies) {
+    MEM_freeN(node->proxies);
+  }
 
+  node->proxies = NULL;
   node->proxy_count = 0;
 }
 
@@ -3218,3 +3220,378 @@ void BKE_pbvh_respect_hide_set(PBVH *pbvh, bool respect_hide)
 {
   pbvh->respect_hide = respect_hide;
 }
+
+#ifdef PROXY_ADVANCED
+// TODO: if this really works, make sure to pull the neighbor iterator out of sculpt.c and put it
+// here
+/* clang-format off */
+#  include "BKE_context.h"
+#  include "DNA_object_types.h"
+#  include "DNA_scene_types.h"
+#  include "../../editors/sculpt_paint/sculpt_intern.h"
+/* clang-format on */
+
+int checkalloc(void **data, int esize, int oldsize, int newsize, int emask, int umask)
+{
+  if (!*data && (emask & umask)) {
+    *data = MEM_callocN(newsize * esize, "pbvh proxy vert arrays");
+    return emask;
+  }
+  // update channel if it already was allocated once, or is requested by umask
+  else if (newsize != oldsize && (*data || (emask & umask))) {
+    *data = MEM_reallocN(data, newsize * esize);
+    return emask;
+  }
+
+  return 0;
+}
+
+void BKE_pbvh_e

@@ Diff output truncated at 10240 characters. @@

