diff options
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh_normals.c | 226 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh_partial_update.c | 43 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh_partial_update.h | 2 |
3 files changed, 69 insertions, 202 deletions
diff --git a/source/blender/bmesh/intern/bmesh_mesh_normals.c b/source/blender/bmesh/intern/bmesh_mesh_normals.c index a3eae6dabe8..bf30f3a52e1 100644 --- a/source/blender/bmesh/intern/bmesh_mesh_normals.c +++ b/source/blender/bmesh/intern/bmesh_mesh_normals.c @@ -49,67 +49,9 @@ * assuming no other tool using it would run concurrently to clnors editing. */ #define BM_LNORSPACE_UPDATE _FLAG_MF -typedef struct BMEdgesCalcVectorsData { - /* Read-only data. */ - const float (*vcos)[3]; - - /* Read-write data, but no need to protect it, no concurrency to fear here. */ - float (*edgevec)[3]; -} BMEdgesCalcVectorsData; - -static void bm_edge_calc_vectors_cb(void *userdata, - MempoolIterData *mp_e, - const TaskParallelTLS *__restrict UNUSED(tls)) -{ - BMEdge *e = (BMEdge *)mp_e; - /* The edge vector will not be needed when the edge has no radial. */ - if (e->l != NULL) { - float(*edgevec)[3] = userdata; - float *e_diff = edgevec[BM_elem_index_get(e)]; - sub_v3_v3v3(e_diff, e->v2->co, e->v1->co); - normalize_v3(e_diff); - } -} - -static void bm_edge_calc_vectors_with_coords_cb(void *userdata, - MempoolIterData *mp_e, - const TaskParallelTLS *__restrict UNUSED(tls)) -{ - BMEdge *e = (BMEdge *)mp_e; - /* The edge vector will not be needed when the edge has no radial. */ - if (e->l != NULL) { - BMEdgesCalcVectorsData *data = userdata; - float *e_diff = data->edgevec[BM_elem_index_get(e)]; - sub_v3_v3v3( - e_diff, data->vcos[BM_elem_index_get(e->v2)], data->vcos[BM_elem_index_get(e->v1)]); - normalize_v3(e_diff); - } -} - -static void bm_mesh_edges_calc_vectors(BMesh *bm, float (*edgevec)[3], const float (*vcos)[3]) -{ - BM_mesh_elem_index_ensure(bm, BM_EDGE | (vcos ? BM_VERT : 0)); - - TaskParallelSettings settings; - BLI_parallel_mempool_settings_defaults(&settings); - settings.use_threading = bm->totedge >= BM_OMP_LIMIT; - - if (vcos == NULL) { - BM_iter_parallel(bm, BM_EDGES_OF_MESH, bm_edge_calc_vectors_cb, edgevec, &settings); - } - else { - BMEdgesCalcVectorsData data = { - .edgevec = edgevec, - .vcos = vcos, - }; - BM_iter_parallel(bm, BM_EDGES_OF_MESH, bm_edge_calc_vectors_with_coords_cb, &data, &settings); - } -} - typedef struct BMVertsCalcNormalsWithCoordsData { /* Read-only data. */ const float (*fnos)[3]; - const float (*edgevec)[3]; const float (*vcos)[3]; /* Write data. */ @@ -117,13 +59,12 @@ typedef struct BMVertsCalcNormalsWithCoordsData { } BMVertsCalcNormalsWithCoordsData; BLI_INLINE void bm_vert_calc_normals_accum_loop(const BMLoop *l_iter, - const float (*edgevec)[3], + const float e1diff[3], + const float e2diff[3], const float f_no[3], float v_no[3]) { /* Calculate the dot product of the two edges that meet at the loop's vertex. */ - const float *e1diff = edgevec[BM_elem_index_get(l_iter->prev->e)]; - const float *e2diff = edgevec[BM_elem_index_get(l_iter->e)]; /* Edge vectors are calculated from e->v1 to e->v2, so adjust the dot product if one but not * both loops actually runs from from e->v2 to e->v1. */ float dotprod = dot_v3v3(e1diff, e2diff); @@ -132,25 +73,61 @@ BLI_INLINE void bm_vert_calc_normals_accum_loop(const BMLoop *l_iter, } const float fac = saacos(-dotprod); /* NAN detection, otherwise this is a degenerated case, ignore that vertex in this case. */ - if (fac == fac) { /* NAN detection. */ + if (fac == fac) { madd_v3_v3fl(v_no, f_no, fac); } } -static void bm_vert_calc_normals_impl(const float (*edgevec)[3], BMVert *v) +static void bm_vert_calc_normals_impl(BMVert *v) { + /* Note on redundant unit-length edge-vector calculation: + * + * This functions calculates unit-length edge-vector for every loop edge + * in practice this means 2x `sqrt` calls per face-corner connected to each vertex. + * + * Previously (2.9x and older), the edge vectors were calculated and stored for reuse. + * However the overhead of did not perform well (~16% slower - single & multi-threaded) + * when compared with calculating the values as they are needed. + * + * For simple grid topologies this function calculates the edge-vectors 4x times. + * There is some room for improved performance by storing the edge-vectors for reuse locally + * in this function, reducing the number of redundant `sqrtf` in half (2x instead of 4x). + * so face loops that share an edge would not calculate it multiple times. + * From my tests the performance improvements are so small they're difficult to measure, + * the time saved removing `sqrtf` calls is lost on storing and looking up the information, + * even in the case of `BLI_smallhash.h` & small inline lookup tables. + * + * Further, local data structures would need to support cases where + * stack memory isn't sufficient - adding additional complexity for corner-cases + * (a vertex that has thousands of connected edges for example). + * Unless there are important use-cases that benefit from edge-vector caching, + * keep this simple and calculate ~4x as many edge-vectors. + * + * In conclusion, the cost of caching & looking up edge-vectors both globally or per-vertex + * doesn't save enough time to make it worthwhile. + * - Campbell. */ + float *v_no = v->no; zero_v3(v_no); + BMEdge *e_first = v->e; if (e_first != NULL) { + float e1diff[3], e2diff[3]; BMEdge *e_iter = e_first; do { BMLoop *l_first = e_iter->l; if (l_first != NULL) { + sub_v3_v3v3(e2diff, e_iter->v1->co, e_iter->v2->co); + normalize_v3(e2diff); + BMLoop *l_iter = l_first; do { if (l_iter->v == v) { - bm_vert_calc_normals_accum_loop(l_iter, edgevec, l_iter->f->no, v_no); + BMEdge *e_prev = l_iter->prev->e; + sub_v3_v3v3(e1diff, e_prev->v1->co, e_prev->v2->co); + normalize_v3(e1diff); + + bm_vert_calc_normals_accum_loop(l_iter, e1diff, e2diff, l_iter->f->no, v_no); } } while ((l_iter = l_iter->radial_next) != l_first); } @@ -164,32 +141,44 @@ static void bm_vert_calc_normals_impl(const float (*edgevec)[3], BMVert *v) normalize_v3_v3(v_no, v->co); } -static void bm_vert_calc_normals_cb(void *userdata, +static void bm_vert_calc_normals_cb(void *UNUSED(userdata), MempoolIterData *mp_v, const TaskParallelTLS *__restrict UNUSED(tls)) { - const float(*edgevec)[3] = userdata; BMVert *v = (BMVert *)mp_v; - bm_vert_calc_normals_impl(edgevec, v); + bm_vert_calc_normals_impl(v); } static void bm_vert_calc_normals_with_coords(BMVert *v, BMVertsCalcNormalsWithCoordsData *data) { + /* See #bm_vert_calc_normals_impl note on performance. */ float *v_no = data->vnos[BM_elem_index_get(v)]; zero_v3(v_no); /* Loop over edges. */ BMEdge *e_first = v->e; if (e_first != NULL) { + float e1diff[3], e2diff[3]; BMEdge *e_iter = e_first; do { BMLoop *l_first = e_iter->l; if (l_first != NULL) { + sub_v3_v3v3(e2diff, + data->vcos[BM_elem_index_get(e_iter->v1)], + data->vcos[BM_elem_index_get(e_iter->v2)]); + normalize_v3(e2diff); + BMLoop *l_iter = l_first; do { if (l_iter->v == v) { + BMEdge *e_prev = l_iter->prev->e; + sub_v3_v3v3(e1diff, + data->vcos[BM_elem_index_get(e_prev->v1)], + data->vcos[BM_elem_index_get(e_prev->v2)]); + normalize_v3(e1diff); + bm_vert_calc_normals_accum_loop( - l_iter, data->edgevec, data->fnos[BM_elem_index_get(l_iter->f)], v_no); + l_iter, e1diff, e2diff, data->fnos[BM_elem_index_get(l_iter->f)], v_no); } } while ((l_iter = l_iter->radial_next) != l_first); } @@ -213,24 +202,22 @@ static void bm_vert_calc_normals_with_coords_cb(void *userdata, } static void bm_mesh_verts_calc_normals(BMesh *bm, - const float (*edgevec)[3], const float (*fnos)[3], const float (*vcos)[3], float (*vnos)[3]) { - BM_mesh_elem_index_ensure(bm, (BM_EDGE | BM_FACE) | ((vnos || vcos) ? BM_VERT : 0)); + BM_mesh_elem_index_ensure(bm, BM_FACE | ((vnos || vcos) ? BM_VERT : 0)); TaskParallelSettings settings; BLI_parallel_mempool_settings_defaults(&settings); settings.use_threading = bm->totvert >= BM_OMP_LIMIT; if (vcos == NULL) { - BM_iter_parallel(bm, BM_VERTS_OF_MESH, bm_vert_calc_normals_cb, (void *)edgevec, &settings); + BM_iter_parallel(bm, BM_VERTS_OF_MESH, bm_vert_calc_normals_cb, NULL, &settings); } else { BLI_assert(!ELEM(NULL, fnos, vnos)); BMVertsCalcNormalsWithCoordsData data = { - .edgevec = edgevec, .fnos = fnos, .vcos = vcos, .vnos = vnos, @@ -255,11 +242,6 @@ static void bm_face_calc_normals_cb(void *UNUSED(userdata), */ void BM_mesh_normals_update(BMesh *bm) { - float(*edgevec)[3] = MEM_mallocN(sizeof(*edgevec) * bm->totedge, __func__); - - /* Parallel mempool iteration does not allow generating indices inline anymore. */ - BM_mesh_elem_index_ensure(bm, (BM_EDGE | BM_FACE)); - /* Calculate all face normals. */ TaskParallelSettings settings; BLI_parallel_mempool_settings_defaults(&settings); @@ -267,11 +249,8 @@ void BM_mesh_normals_update(BMesh *bm) BM_iter_parallel(bm, BM_FACES_OF_MESH, bm_face_calc_normals_cb, NULL, &settings); - bm_mesh_edges_calc_vectors(bm, edgevec, NULL); - /* Add weighted face normals to vertices, and normalize vert normals. */ - bm_mesh_verts_calc_normals(bm, edgevec, NULL, NULL, NULL); - MEM_freeN(edgevec); + bm_mesh_verts_calc_normals(bm, NULL, NULL, NULL); } /** \} */ @@ -287,40 +266,26 @@ static void bm_partial_faces_parallel_range_calc_normals_cb( BM_face_calc_normal(f, f->no); } -static void bm_partial_edges_parallel_range_calc_vectors_cb( - void *userdata, const int iter, const TaskParallelTLS *__restrict UNUSED(tls)) -{ - BMEdge *e = ((BMEdge **)((void **)userdata)[0])[iter]; - float *r_edgevec = ((float(*)[3])((void **)userdata)[1])[iter]; - sub_v3_v3v3(r_edgevec, e->v1->co, e->v2->co); - normalize_v3(r_edgevec); -} - static void bm_partial_verts_parallel_range_calc_normal_cb( void *userdata, const int iter, const TaskParallelTLS *__restrict UNUSED(tls)) { - BMVert *v = ((BMVert **)((void **)userdata)[0])[iter]; - const float(*edgevec)[3] = (const float(*)[3])((void **)userdata)[1]; - bm_vert_calc_normals_impl(edgevec, v); + BMVert *v = ((BMVert **)userdata)[iter]; + bm_vert_calc_normals_impl(v); } /** * A version of #BM_mesh_normals_update that updates a subset of geometry, * used to avoid the overhead of updating everything. */ -void BM_mesh_normals_update_with_partial(BMesh *bm, const BMPartialUpdate *bmpinfo) +void BM_mesh_normals_update_with_partial(BMesh *UNUSED(bm), const BMPartialUpdate *bmpinfo) { BLI_assert(bmpinfo->params.do_normals); BMVert **verts = bmpinfo->verts; - BMEdge **edges = bmpinfo->edges; BMFace **faces = bmpinfo->faces; const int verts_len = bmpinfo->verts_len; - const int edges_len = bmpinfo->edges_len; const int faces_len = bmpinfo->faces_len; - float(*edgevec)[3] = MEM_mallocN(sizeof(*edgevec) * edges_len, __func__); - TaskParallelSettings settings; BLI_parallel_range_settings_defaults(&settings); @@ -328,58 +293,9 @@ void BM_mesh_normals_update_with_partial(BMesh *bm, const BMPartialUpdate *bmpin BLI_task_parallel_range( 0, faces_len, faces, bm_partial_faces_parallel_range_calc_normals_cb, &settings); - /* Temporarily override the edge indices, - * storing the correct indices in the case they're not dirty. - * - * \note in most cases indices are modified and #BMesh.elem_index_dirty is set. - * This is an exceptional case where indices are restored because the worst case downside - * of marking the edge indices dirty would require a full loop over all edges to - * correct the indices in other functions which need them to be valid. - * When moving a few vertices on a high poly mesh setting and restoring connected - * edges has very little overhead compared with restoring all edge indices. */ - int *edge_index_value = NULL; - if ((bm->elem_index_dirty & BM_EDGE) == 0) { - edge_index_value = MEM_mallocN(sizeof(*edge_index_value) * edges_len, __func__); - - for (int i = 0; i < edges_len; i++) { - BMEdge *e = edges[i]; - edge_index_value[i] = BM_elem_index_get(e); - BM_elem_index_set(e, i); /* set_dirty! (restore before this function exits). */ - } - } - else { - for (int i = 0; i < edges_len; i++) { - BMEdge *e = edges[i]; - BM_elem_index_set(e, i); /* set_dirty! (already dirty) */ - } - } - - { - /* Verts. */ - - /* Compute normalized direction vectors for each edge. - * Directions will be used for calculating the weights of the face normals on the vertex - * normals. */ - void *data[2] = {edges, edgevec}; - BLI_task_parallel_range( - 0, edges_len, data, bm_partial_edges_parallel_range_calc_vectors_cb, &settings); - - /* Calculate vertex normals. */ - data[0] = verts; - BLI_task_parallel_range( - 0, verts_len, data, bm_partial_verts_parallel_range_calc_normal_cb, &settings); - } - - if (edge_index_value != NULL) { - for (int i = 0; i < edges_len; i++) { - BMEdge *e = edges[i]; - BM_elem_index_set(e, edge_index_value[i]); /* set_ok (restore) */ - } - - MEM_freeN(edge_index_value); - } - - MEM_freeN(edgevec); + /* Verts. */ + BLI_task_parallel_range( + 0, verts_len, verts, bm_partial_verts_parallel_range_calc_normal_cb, &settings); } /** \} */ @@ -399,16 +315,8 @@ void BM_verts_calc_normal_vcos(BMesh *bm, const float (*vcos)[3], float (*vnos)[3]) { - float(*edgevec)[3] = MEM_mallocN(sizeof(*edgevec) * bm->totedge, __func__); - - /* Compute normalized direction vectors for each edge. - * Directions will be used for calculating the weights of the face normals on the vertex normals. - */ - bm_mesh_edges_calc_vectors(bm, edgevec, vcos); - /* Add weighted face normals to vertices, and normalize vert normals. */ - bm_mesh_verts_calc_normals(bm, edgevec, fnos, vcos, vnos); - MEM_freeN(edgevec); + bm_mesh_verts_calc_normals(bm, fnos, vcos, vnos); } /** \} */ diff --git a/source/blender/bmesh/intern/bmesh_mesh_partial_update.c b/source/blender/bmesh/intern/bmesh_mesh_partial_update.c index 7b01b61d4fa..267705aa7c7 100644 --- a/source/blender/bmesh/intern/bmesh_mesh_partial_update.c +++ b/source/blender/bmesh/intern/bmesh_mesh_partial_update.c @@ -79,20 +79,6 @@ BLI_INLINE bool partial_elem_vert_ensure(BMPartialUpdate *bmpinfo, return false; } -BLI_INLINE bool partial_elem_edge_ensure(BMPartialUpdate *bmpinfo, - BLI_bitmap *edges_tag, - BMEdge *e) -{ - const int i = BM_elem_index_get(e); - if (!BLI_BITMAP_TEST(edges_tag, i)) { - BLI_BITMAP_ENABLE(edges_tag, i); - GROW_ARRAY_AS_NEEDED(bmpinfo->edges, bmpinfo->edges_len_alloc, bmpinfo->edges_len); - bmpinfo->edges[bmpinfo->edges_len++] = e; - return true; - } - return false; -} - BLI_INLINE bool partial_elem_face_ensure(BMPartialUpdate *bmpinfo, BLI_bitmap *faces_tag, BMFace *f) @@ -121,17 +107,15 @@ BMPartialUpdate *BM_mesh_partial_create_from_verts(BMesh *bm, /* Reserve more edges than vertices since it's common for a grid topology * to use around twice as many edges as vertices. */ const int default_verts_len_alloc = verts_len; - const int default_edges_len_alloc = min_ii(bm->totedge, verts_len * 2); const int default_faces_len_alloc = min_ii(bm->totface, verts_len); /* Allocate tags instead of using #BM_ELEM_TAG because the caller may already be using tags. * Further, walking over all geometry to clear the tags isn't so efficient. */ BLI_bitmap *verts_tag = NULL; - BLI_bitmap *edges_tag = NULL; BLI_bitmap *faces_tag = NULL; /* Set vert inline. */ - BM_mesh_elem_index_ensure(bm, (BM_EDGE | BM_FACE)); + BM_mesh_elem_index_ensure(bm, BM_FACE); if (params->do_normals || params->do_tessellate) { /* - Extend to all vertices connected faces: @@ -197,29 +181,12 @@ BMPartialUpdate *BM_mesh_partial_create_from_verts(BMesh *bm, verts_tag = BLI_BITMAP_NEW((size_t)bm->totvert, __func__); } - /* Edges. */ - if (bmpinfo->edges == NULL) { - bmpinfo->edges_len_alloc = default_edges_len_alloc; - bmpinfo->edges = MEM_mallocN((sizeof(BMEdge *) * bmpinfo->edges_len_alloc), __func__); - edges_tag = BLI_BITMAP_NEW((size_t)bm->totedge, __func__); - } - for (int i = 0; i < bmpinfo->faces_len; i++) { BMFace *f = bmpinfo->faces[i]; BMLoop *l_iter, *l_first; l_iter = l_first = BM_FACE_FIRST_LOOP(f); do { - if (!partial_elem_vert_ensure(bmpinfo, verts_tag, l_iter->v)) { - continue; - } - BMVert *v = l_iter->v; - BMEdge *e_first = v->e; - BMEdge *e_iter = e_first; - do { - if (e_iter->l) { - partial_elem_edge_ensure(bmpinfo, edges_tag, e_iter); - } - } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != e_first); + partial_elem_vert_ensure(bmpinfo, verts_tag, l_iter->v); } while ((l_iter = l_iter->next) != l_first); } } @@ -227,9 +194,6 @@ BMPartialUpdate *BM_mesh_partial_create_from_verts(BMesh *bm, if (verts_tag) { MEM_freeN(verts_tag); } - if (edges_tag) { - MEM_freeN(edges_tag); - } if (faces_tag) { MEM_freeN(faces_tag); } @@ -244,9 +208,6 @@ void BM_mesh_partial_destroy(BMPartialUpdate *bmpinfo) if (bmpinfo->verts) { MEM_freeN(bmpinfo->verts); } - if (bmpinfo->edges) { - MEM_freeN(bmpinfo->edges); - } if (bmpinfo->faces) { MEM_freeN(bmpinfo->faces); } diff --git a/source/blender/bmesh/intern/bmesh_mesh_partial_update.h b/source/blender/bmesh/intern/bmesh_mesh_partial_update.h index b31ec127744..3dbfb985e92 100644 --- a/source/blender/bmesh/intern/bmesh_mesh_partial_update.h +++ b/source/blender/bmesh/intern/bmesh_mesh_partial_update.h @@ -44,10 +44,8 @@ typedef struct BMPartialUpdate_Params { */ 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; /** Store the parameters used in creation so invalid use can be asserted. */ |