diff options
Diffstat (limited to 'source/blender/bmesh/intern')
17 files changed, 2794 insertions, 2019 deletions
diff --git a/source/blender/bmesh/intern/bmesh_core.c b/source/blender/bmesh/intern/bmesh_core.c index cf907862120..e72c689ddfb 100644 --- a/source/blender/bmesh/intern/bmesh_core.c +++ b/source/blender/bmesh/intern/bmesh_core.c @@ -1805,7 +1805,8 @@ BMEdge *bmesh_kernel_join_edge_kill_vert(BMesh *bm, BMVert *v_kill, const bool do_del, const bool check_edge_exists, - const bool kill_degenerate_faces) + const bool kill_degenerate_faces, + const bool kill_duplicate_faces) { BMEdge *e_old; BMVert *v_old, *v_target; @@ -1840,6 +1841,9 @@ BMEdge *bmesh_kernel_join_edge_kill_vert(BMesh *bm, BLI_SMALLSTACK_DECLARE(faces_degenerate, BMFace *); BMLoop *l_kill_next; + /* Candidates for being duplicate. */ + BLI_SMALLSTACK_DECLARE(faces_duplicate_candidate, BMFace *); + #ifndef NDEBUG /* For verification later, count valence of 'v_old' and 'v_target' */ valence1 = bmesh_disk_count(v_old); @@ -1877,9 +1881,14 @@ BMEdge *bmesh_kernel_join_edge_kill_vert(BMesh *bm, /* fix len attribute of face */ l_kill->f->len--; - if (kill_degenerate_faces) { - if (l_kill->f->len < 3) { - BLI_SMALLSTACK_PUSH(faces_degenerate, l_kill->f); + if (kill_degenerate_faces && (l_kill->f->len < 3)) { + BLI_SMALLSTACK_PUSH(faces_degenerate, l_kill->f); + } + else { + /* The duplicate test isn't reliable at this point as `e_splice` might be set, + * so the duplicate test needs to run once the edge has been spliced. */ + if (kill_duplicate_faces) { + BLI_SMALLSTACK_PUSH(faces_duplicate_candidate, l_kill->f); } } l_kill_next = l_kill->radial_next; @@ -1940,6 +1949,15 @@ BMEdge *bmesh_kernel_join_edge_kill_vert(BMesh *bm, } } + if (kill_duplicate_faces) { + BMFace *f_kill; + while ((f_kill = BLI_SMALLSTACK_POP(faces_duplicate_candidate))) { + if (BM_face_find_double(f_kill)) { + BM_face_kill(bm, f_kill); + } + } + } + BM_CHECK_ELEMENT(v_old); BM_CHECK_ELEMENT(v_target); BM_CHECK_ELEMENT(e_old); diff --git a/source/blender/bmesh/intern/bmesh_core.h b/source/blender/bmesh/intern/bmesh_core.h index df73984e6cf..8f7580714ae 100644 --- a/source/blender/bmesh/intern/bmesh_core.h +++ b/source/blender/bmesh/intern/bmesh_core.h @@ -115,7 +115,8 @@ BMEdge *bmesh_kernel_join_edge_kill_vert(BMesh *bm, BMVert *v_kill, const bool do_del, const bool check_edge_exists, - const bool kill_degenerate_faces); + const bool kill_degenerate_faces, + const bool kill_duplicate_faces); BMVert *bmesh_kernel_join_vert_kill_edge(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, diff --git a/source/blender/bmesh/intern/bmesh_iterators_inline.h b/source/blender/bmesh/intern/bmesh_iterators_inline.h index c384fb03cd9..81b6a58e58b 100644 --- a/source/blender/bmesh/intern/bmesh_iterators_inline.h +++ b/source/blender/bmesh/intern/bmesh_iterators_inline.h @@ -188,18 +188,18 @@ BLI_INLINE void BM_iter_parallel(BMesh *bm, const char itype, TaskParallelMempoolFunc func, void *userdata, - const bool use_threading) + const TaskParallelSettings *settings) { /* inlining optimizes out this switch when called with the defined type */ switch ((BMIterType)itype) { case BM_VERTS_OF_MESH: - BLI_task_parallel_mempool(bm->vpool, userdata, func, use_threading); + BLI_task_parallel_mempool(bm->vpool, userdata, func, settings); break; case BM_EDGES_OF_MESH: - BLI_task_parallel_mempool(bm->epool, userdata, func, use_threading); + BLI_task_parallel_mempool(bm->epool, userdata, func, settings); break; case BM_FACES_OF_MESH: - BLI_task_parallel_mempool(bm->fpool, userdata, func, use_threading); + BLI_task_parallel_mempool(bm->fpool, userdata, func, settings); break; default: /* should never happen */ diff --git a/source/blender/bmesh/intern/bmesh_mesh.c b/source/blender/bmesh/intern/bmesh_mesh.c index 5e879d41d43..d0c6bc83088 100644 --- a/source/blender/bmesh/intern/bmesh_mesh.c +++ b/source/blender/bmesh/intern/bmesh_mesh.c @@ -25,22 +25,14 @@ #include "DNA_listBase.h" #include "DNA_scene_types.h" -#include "BLI_bitmap.h" -#include "BLI_linklist_stack.h" #include "BLI_listbase.h" #include "BLI_math.h" -#include "BLI_stack.h" -#include "BLI_task.h" #include "BLI_utildefines.h" -#include "BKE_editmesh.h" -#include "BKE_global.h" +#include "BKE_customdata.h" #include "BKE_mesh.h" -#include "BKE_multires.h" -#include "atomic_ops.h" - -#include "intern/bmesh_private.h" +#include "bmesh.h" /* used as an extern, defined in bmesh.h */ const BMAllocTemplate bm_mesh_allocsize_default = {512, 1024, 2048, 512}; @@ -319,1653 +311,6 @@ void BM_mesh_free(BMesh *bm) } /** - * Helpers for #BM_mesh_normals_update and #BM_verts_calc_normal_vcos - */ - -/* We use that existing internal API flag, - * 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 mesh_edges_calc_vectors_cb(void *userdata, MempoolIterData *mp_e) -{ - BMEdgesCalcVectorsData *data = userdata; - BMEdge *e = (BMEdge *)mp_e; - - if (e->l) { - const float *v1_co = data->vcos ? data->vcos[BM_elem_index_get(e->v1)] : e->v1->co; - const float *v2_co = data->vcos ? data->vcos[BM_elem_index_get(e->v2)] : e->v2->co; - sub_v3_v3v3(data->edgevec[BM_elem_index_get(e)], v2_co, v1_co); - normalize_v3(data->edgevec[BM_elem_index_get(e)]); - } - else { - /* the edge vector will not be needed when the edge has no radial */ - } -} - -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)); - - BMEdgesCalcVectorsData data = { - .vcos = vcos, - .edgevec = edgevec, - }; - - BM_iter_parallel( - bm, BM_EDGES_OF_MESH, mesh_edges_calc_vectors_cb, &data, bm->totedge >= BM_OMP_LIMIT); -} - -typedef struct BMVertsCalcNormalsData { - /* Read-only data. */ - const float (*fnos)[3]; - const float (*edgevec)[3]; - const float (*vcos)[3]; - - /* Read-write data, protected by an atomic-based fake spin-lock like system. */ - float (*vnos)[3]; -} BMVertsCalcNormalsData; - -static void mesh_verts_calc_normals_accum_cb(void *userdata, MempoolIterData *mp_f) -{ -#define FLT_EQ_NONAN(_fa, _fb) (*((const uint32_t *)&_fa) == *((const uint32_t *)&_fb)) - - BMVertsCalcNormalsData *data = userdata; - BMFace *f = (BMFace *)mp_f; - - const float *f_no = data->fnos ? data->fnos[BM_elem_index_get(f)] : f->no; - - BMLoop *l_first, *l_iter; - l_iter = l_first = BM_FACE_FIRST_LOOP(f); - do { - const float *e1diff, *e2diff; - float dotprod; - float fac; - - /* calculate the dot product of the two edges that - * meet at the loop's vertex */ - e1diff = data->edgevec[BM_elem_index_get(l_iter->prev->e)]; - e2diff = data->edgevec[BM_elem_index_get(l_iter->e)]; - dotprod = dot_v3v3(e1diff, e2diff); - - /* 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 */ - if ((l_iter->prev->e->v1 == l_iter->prev->v) ^ (l_iter->e->v1 == l_iter->v)) { - dotprod = -dotprod; - } - - fac = saacos(-dotprod); - - if (fac != fac) { /* NAN detection. */ - /* Degenerated case, nothing to do here, just ignore that vertex. */ - continue; - } - - /* accumulate weighted face normal into the vertex's normal */ - float *v_no = data->vnos ? data->vnos[BM_elem_index_get(l_iter->v)] : l_iter->v->no; - - /* This block is a lockless threadsafe madd_v3_v3fl. - * It uses the first float of the vector as a sort of cheap spin-lock, - * assuming FLT_MAX is a safe 'illegal' value that cannot be set here otherwise. - * It also assumes that collisions between threads are highly unlikely, - * else performances would be quite bad here. */ - float virtual_lock = v_no[0]; - while (true) { - /* This loops until following conditions are met: - * - v_no[0] has same value as virtual_lock (i.e. it did not change since last try). - * - v_no[0] was not FLT_MAX, i.e. it was not locked by another thread. - */ - const float vl = atomic_cas_float(&v_no[0], virtual_lock, FLT_MAX); - if (FLT_EQ_NONAN(vl, virtual_lock) && vl != FLT_MAX) { - break; - } - virtual_lock = vl; - } - BLI_assert(v_no[0] == FLT_MAX); - /* Now we own that normal value, and can change it. - * But first scalar of the vector must not be changed yet, it's our lock! */ - virtual_lock += f_no[0] * fac; - v_no[1] += f_no[1] * fac; - v_no[2] += f_no[2] * fac; - /* Second atomic operation to 'release' - * our lock on that vector and set its first scalar value. */ - /* Note that we do not need to loop here, since we 'locked' v_no[0], - * nobody should have changed it in the mean time. */ - virtual_lock = atomic_cas_float(&v_no[0], FLT_MAX, virtual_lock); - BLI_assert(virtual_lock == FLT_MAX); - - } while ((l_iter = l_iter->next) != l_first); - -#undef FLT_EQ_NONAN -} - -static void mesh_verts_calc_normals_normalize_cb(void *userdata, MempoolIterData *mp_v) -{ - BMVertsCalcNormalsData *data = userdata; - BMVert *v = (BMVert *)mp_v; - - float *v_no = data->vnos ? data->vnos[BM_elem_index_get(v)] : v->no; - if (UNLIKELY(normalize_v3(v_no) == 0.0f)) { - const float *v_co = data->vcos ? data->vcos[BM_elem_index_get(v)] : v->co; - normalize_v3_v3(v_no, v_co); - } -} - -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)); - - BMVertsCalcNormalsData data = { - .fnos = fnos, - .edgevec = edgevec, - .vcos = vcos, - .vnos = vnos, - }; - - BM_iter_parallel( - bm, BM_FACES_OF_MESH, mesh_verts_calc_normals_accum_cb, &data, bm->totface >= BM_OMP_LIMIT); - - /* normalize the accumulated vertex normals */ - BM_iter_parallel(bm, - BM_VERTS_OF_MESH, - mesh_verts_calc_normals_normalize_cb, - &data, - bm->totvert >= BM_OMP_LIMIT); -} - -static void mesh_faces_calc_normals_cb(void *UNUSED(userdata), MempoolIterData *mp_f) -{ - BMFace *f = (BMFace *)mp_f; - - BM_face_normal_update(f); -} - -/** - * \brief BMesh Compute Normals - * - * Updates the normals of a mesh. - */ -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 */ - BM_iter_parallel( - bm, BM_FACES_OF_MESH, mesh_faces_calc_normals_cb, NULL, bm->totface >= BM_OMP_LIMIT); - - /* Zero out vertex normals */ - BMIter viter; - BMVert *v; - int i; - - BM_ITER_MESH_INDEX (v, &viter, bm, BM_VERTS_OF_MESH, i) { - BM_elem_index_set(v, i); /* set_inline */ - zero_v3(v->no); - } - bm->elem_index_dirty &= ~BM_VERT; - - /* 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, NULL); - - /* Add weighted face normals to vertices, and normalize vert normals. */ - bm_mesh_verts_calc_normals(bm, (const float(*)[3])edgevec, NULL, NULL, NULL); - MEM_freeN(edgevec); -} - -/** - * \brief BMesh Compute Normals from/to external data. - * - * Computes the vertex normals of a mesh into vnos, - * using given vertex coordinates (vcos) and polygon normals (fnos). - */ -void BM_verts_calc_normal_vcos(BMesh *bm, - const float (*fnos)[3], - 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, (const float(*)[3])edgevec, fnos, vcos, vnos); - MEM_freeN(edgevec); -} - -/** - * Helpers for #BM_mesh_loop_normals_update and #BM_loops_calc_normal_vcos - */ -static void bm_mesh_edges_sharp_tag(BMesh *bm, - const float (*vnos)[3], - const float (*fnos)[3], - float (*r_lnos)[3], - const float split_angle, - const bool do_sharp_edges_tag) -{ - BMIter eiter; - BMEdge *e; - int i; - - const bool check_angle = (split_angle < (float)M_PI); - const float split_angle_cos = check_angle ? cosf(split_angle) : -1.0f; - - { - char htype = BM_VERT | BM_LOOP; - if (fnos) { - htype |= BM_FACE; - } - BM_mesh_elem_index_ensure(bm, htype); - } - - /* This first loop checks which edges are actually smooth, - * and pre-populate lnos with vnos (as if they were all smooth). */ - BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) { - BMLoop *l_a, *l_b; - - BM_elem_index_set(e, i); /* set_inline */ - BM_elem_flag_disable(e, BM_ELEM_TAG); /* Clear tag (means edge is sharp). */ - - /* An edge with only two loops, might be smooth... */ - if (BM_edge_loop_pair(e, &l_a, &l_b)) { - bool is_angle_smooth = true; - if (check_angle) { - const float *no_a = fnos ? fnos[BM_elem_index_get(l_a->f)] : l_a->f->no; - const float *no_b = fnos ? fnos[BM_elem_index_get(l_b->f)] : l_b->f->no; - is_angle_smooth = (dot_v3v3(no_a, no_b) >= split_angle_cos); - } - - /* We only tag edges that are *really* smooth: - * If the angle between both its polys' normals is below split_angle value, - * and it is tagged as such, - * and both its faces are smooth, - * and both its faces have compatible (non-flipped) normals, - * i.e. both loops on the same edge do not share the same vertex. - */ - if (BM_elem_flag_test(e, BM_ELEM_SMOOTH) && BM_elem_flag_test(l_a->f, BM_ELEM_SMOOTH) && - BM_elem_flag_test(l_b->f, BM_ELEM_SMOOTH) && l_a->v != l_b->v) { - if (is_angle_smooth) { - const float *no; - BM_elem_flag_enable(e, BM_ELEM_TAG); - - /* linked vertices might be fully smooth, copy their normals to loop ones. */ - if (r_lnos) { - no = vnos ? vnos[BM_elem_index_get(l_a->v)] : l_a->v->no; - copy_v3_v3(r_lnos[BM_elem_index_get(l_a)], no); - no = vnos ? vnos[BM_elem_index_get(l_b->v)] : l_b->v->no; - copy_v3_v3(r_lnos[BM_elem_index_get(l_b)], no); - } - } - else if (do_sharp_edges_tag) { - /* Note that we do not care about the other sharp-edge cases - * (sharp poly, non-manifold edge, etc.), - * only tag edge as sharp when it is due to angle threshold. */ - BM_elem_flag_disable(e, BM_ELEM_SMOOTH); - } - } - } - } - - bm->elem_index_dirty &= ~BM_EDGE; -} - -/** - * Check whether given loop is part of an unknown-so-far cyclic smooth fan, or not. - * Needed because cyclic smooth fans have no obvious 'entry point', - * and yet we need to walk them once, and only once. - */ -bool BM_loop_check_cyclic_smooth_fan(BMLoop *l_curr) -{ - BMLoop *lfan_pivot_next = l_curr; - BMEdge *e_next = l_curr->e; - - BLI_assert(!BM_elem_flag_test(lfan_pivot_next, BM_ELEM_TAG)); - BM_elem_flag_enable(lfan_pivot_next, BM_ELEM_TAG); - - while (true) { - /* Much simpler than in sibling code with basic Mesh data! */ - lfan_pivot_next = BM_vert_step_fan_loop(lfan_pivot_next, &e_next); - - if (!lfan_pivot_next || !BM_elem_flag_test(e_next, BM_ELEM_TAG)) { - /* Sharp loop/edge, so not a cyclic smooth fan... */ - return false; - } - /* Smooth loop/edge... */ - if (BM_elem_flag_test(lfan_pivot_next, BM_ELEM_TAG)) { - if (lfan_pivot_next == l_curr) { - /* We walked around a whole cyclic smooth fan - * without finding any already-processed loop, - * means we can use initial l_curr/l_prev edge as start for this smooth fan. */ - return true; - } - /* ... already checked in some previous looping, we can abort. */ - return false; - } - /* ... we can skip it in future, and keep checking the smooth fan. */ - BM_elem_flag_enable(lfan_pivot_next, BM_ELEM_TAG); - } -} - -/** - * BMesh version of BKE_mesh_normals_loop_split() in mesh_evaluate.c - * Will use first clnors_data array, and fallback to cd_loop_clnors_offset - * (use NULL and -1 to not use clnors). - * - * \note This sets #BM_ELEM_TAG which is used in tool code (e.g. T84426). - * we could add a low-level API flag for this, see #BM_ELEM_API_FLAG_ENABLE and friends. - */ -static void bm_mesh_loops_calc_normals(BMesh *bm, - const float (*vcos)[3], - const float (*fnos)[3], - float (*r_lnos)[3], - MLoopNorSpaceArray *r_lnors_spacearr, - const short (*clnors_data)[2], - const int cd_loop_clnors_offset, - const bool do_rebuild) -{ - BMIter fiter; - BMFace *f_curr; - const bool has_clnors = clnors_data || (cd_loop_clnors_offset != -1); - - MLoopNorSpaceArray _lnors_spacearr = {NULL}; - - /* Temp normal stack. */ - BLI_SMALLSTACK_DECLARE(normal, float *); - /* Temp clnors stack. */ - BLI_SMALLSTACK_DECLARE(clnors, short *); - /* Temp edge vectors stack, only used when computing lnor spacearr. */ - BLI_Stack *edge_vectors = NULL; - - { - char htype = 0; - if (vcos) { - htype |= BM_VERT; - } - /* Face/Loop indices are set inline below. */ - BM_mesh_elem_index_ensure(bm, htype); - } - - if (!r_lnors_spacearr && has_clnors) { - /* We need to compute lnor spacearr if some custom lnor data are given to us! */ - r_lnors_spacearr = &_lnors_spacearr; - } - if (r_lnors_spacearr) { - BKE_lnor_spacearr_init(r_lnors_spacearr, bm->totloop, MLNOR_SPACEARR_BMLOOP_PTR); - edge_vectors = BLI_stack_new(sizeof(float[3]), __func__); - } - - /* Clear all loops' tags (means none are to be skipped for now). */ - int index_face, index_loop = 0; - BM_ITER_MESH_INDEX (f_curr, &fiter, bm, BM_FACES_OF_MESH, index_face) { - BMLoop *l_curr, *l_first; - - BM_elem_index_set(f_curr, index_face); /* set_inline */ - - l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr); - do { - BM_elem_index_set(l_curr, index_loop++); /* set_inline */ - BM_elem_flag_disable(l_curr, BM_ELEM_TAG); - } while ((l_curr = l_curr->next) != l_first); - } - bm->elem_index_dirty &= ~(BM_FACE | BM_LOOP); - - /* We now know edges that can be smoothed (they are tagged), - * and edges that will be hard (they aren't). - * Now, time to generate the normals. - */ - BM_ITER_MESH (f_curr, &fiter, bm, BM_FACES_OF_MESH) { - BMLoop *l_curr, *l_first; - - l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr); - do { - if (do_rebuild && !BM_ELEM_API_FLAG_TEST(l_curr, BM_LNORSPACE_UPDATE) && - !(bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL)) { - continue; - } - /* A smooth edge, we have to check for cyclic smooth fan case. - * If we find a new, never-processed cyclic smooth fan, we can do it now using that loop/edge - * as 'entry point', otherwise we can skip it. */ - - /* Note: In theory, we could make bm_mesh_loop_check_cyclic_smooth_fan() store - * mlfan_pivot's in a stack, to avoid having to fan again around - * the vert during actual computation of clnor & clnorspace. However, this would complicate - * the code, add more memory usage, and - * BM_vert_step_fan_loop() is quite cheap in term of CPU cycles, - * so really think it's not worth it. */ - if (BM_elem_flag_test(l_curr->e, BM_ELEM_TAG) && - (BM_elem_flag_test(l_curr, BM_ELEM_TAG) || !BM_loop_check_cyclic_smooth_fan(l_curr))) { - } - else if (!BM_elem_flag_test(l_curr->e, BM_ELEM_TAG) && - !BM_elem_flag_test(l_curr->prev->e, BM_ELEM_TAG)) { - /* Simple case (both edges around that vertex are sharp in related polygon), - * this vertex just takes its poly normal. - */ - const int l_curr_index = BM_elem_index_get(l_curr); - const float *no = fnos ? fnos[BM_elem_index_get(f_curr)] : f_curr->no; - copy_v3_v3(r_lnos[l_curr_index], no); - - /* If needed, generate this (simple!) lnor space. */ - if (r_lnors_spacearr) { - float vec_curr[3], vec_prev[3]; - MLoopNorSpace *lnor_space = BKE_lnor_space_create(r_lnors_spacearr); - - { - const BMVert *v_pivot = l_curr->v; - const float *co_pivot = vcos ? vcos[BM_elem_index_get(v_pivot)] : v_pivot->co; - const BMVert *v_1 = BM_edge_other_vert(l_curr->e, v_pivot); - const float *co_1 = vcos ? vcos[BM_elem_index_get(v_1)] : v_1->co; - const BMVert *v_2 = BM_edge_other_vert(l_curr->prev->e, v_pivot); - const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co; - - sub_v3_v3v3(vec_curr, co_1, co_pivot); - normalize_v3(vec_curr); - sub_v3_v3v3(vec_prev, co_2, co_pivot); - normalize_v3(vec_prev); - } - - BKE_lnor_space_define(lnor_space, r_lnos[l_curr_index], vec_curr, vec_prev, NULL); - /* We know there is only one loop in this space, - * no need to create a linklist in this case... */ - BKE_lnor_space_add_loop(r_lnors_spacearr, lnor_space, l_curr_index, l_curr, true); - - if (has_clnors) { - const short(*clnor)[2] = clnors_data ? &clnors_data[l_curr_index] : - (const void *)BM_ELEM_CD_GET_VOID_P( - l_curr, cd_loop_clnors_offset); - BKE_lnor_space_custom_data_to_normal(lnor_space, *clnor, r_lnos[l_curr_index]); - } - } - } - /* We *do not need* to check/tag loops as already computed! - * Due to the fact a loop only links to one of its two edges, - * a same fan *will never be walked more than once!* - * Since we consider edges having neighbor faces with inverted (flipped) normals as sharp, - * we are sure that no fan will be skipped, even only considering the case - * (sharp curr_edge, smooth prev_edge), and not the alternative - * (smooth curr_edge, sharp prev_edge). - * All this due/thanks to link between normals and loop ordering. - */ - else { - /* We have to fan around current vertex, until we find the other non-smooth edge, - * and accumulate face normals into the vertex! - * Note in case this vertex has only one sharp edge, - * this is a waste because the normal is the same as the vertex normal, - * but I do not see any easy way to detect that (would need to count number of sharp edges - * per vertex, I doubt the additional memory usage would be worth it, especially as it - * should not be a common case in real-life meshes anyway). - */ - BMVert *v_pivot = l_curr->v; - BMEdge *e_next; - const BMEdge *e_org = l_curr->e; - BMLoop *lfan_pivot, *lfan_pivot_next; - int lfan_pivot_index; - float lnor[3] = {0.0f, 0.0f, 0.0f}; - float vec_curr[3], vec_next[3], vec_org[3]; - - /* We validate clnors data on the fly - cheapest way to do! */ - int clnors_avg[2] = {0, 0}; - const short(*clnor_ref)[2] = NULL; - int clnors_nbr = 0; - bool clnors_invalid = false; - - const float *co_pivot = vcos ? vcos[BM_elem_index_get(v_pivot)] : v_pivot->co; - - MLoopNorSpace *lnor_space = r_lnors_spacearr ? BKE_lnor_space_create(r_lnors_spacearr) : - NULL; - - BLI_assert((edge_vectors == NULL) || BLI_stack_is_empty(edge_vectors)); - - lfan_pivot = l_curr; - lfan_pivot_index = BM_elem_index_get(lfan_pivot); - e_next = lfan_pivot->e; /* Current edge here, actually! */ - - /* Only need to compute previous edge's vector once, - * then we can just reuse old current one! */ - { - const BMVert *v_2 = BM_edge_other_vert(e_next, v_pivot); - const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co; - - sub_v3_v3v3(vec_org, co_2, co_pivot); - normalize_v3(vec_org); - copy_v3_v3(vec_curr, vec_org); - - if (r_lnors_spacearr) { - BLI_stack_push(edge_vectors, vec_org); - } - } - - while (true) { - /* Much simpler than in sibling code with basic Mesh data! */ - lfan_pivot_next = BM_vert_step_fan_loop(lfan_pivot, &e_next); - if (lfan_pivot_next) { - BLI_assert(lfan_pivot_next->v == v_pivot); - } - else { - /* next edge is non-manifold, we have to find it ourselves! */ - e_next = (lfan_pivot->e == e_next) ? lfan_pivot->prev->e : lfan_pivot->e; - } - - /* Compute edge vector. - * NOTE: We could pre-compute those into an array, in the first iteration, - * instead of computing them twice (or more) here. - * However, time gained is not worth memory and time lost, - * given the fact that this code should not be called that much in real-life meshes. - */ - { - const BMVert *v_2 = BM_edge_other_vert(e_next, v_pivot); - const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co; - - sub_v3_v3v3(vec_next, co_2, co_pivot); - normalize_v3(vec_next); - } - - { - /* Code similar to accumulate_vertex_normals_poly_v3. */ - /* Calculate angle between the two poly edges incident on this vertex. */ - const BMFace *f = lfan_pivot->f; - const float fac = saacos(dot_v3v3(vec_next, vec_curr)); - const float *no = fnos ? fnos[BM_elem_index_get(f)] : f->no; - /* Accumulate */ - madd_v3_v3fl(lnor, no, fac); - - if (has_clnors) { - /* Accumulate all clnors, if they are not all equal we have to fix that! */ - const short(*clnor)[2] = clnors_data ? &clnors_data[lfan_pivot_index] : - (const void *)BM_ELEM_CD_GET_VOID_P( - lfan_pivot, cd_loop_clnors_offset); - if (clnors_nbr) { - clnors_invalid |= ((*clnor_ref)[0] != (*clnor)[0] || - (*clnor_ref)[1] != (*clnor)[1]); - } - else { - clnor_ref = clnor; - } - clnors_avg[0] += (*clnor)[0]; - clnors_avg[1] += (*clnor)[1]; - clnors_nbr++; - /* We store here a pointer to all custom lnors processed. */ - BLI_SMALLSTACK_PUSH(clnors, (short *)*clnor); - } - } - - /* We store here a pointer to all loop-normals processed. */ - BLI_SMALLSTACK_PUSH(normal, (float *)r_lnos[lfan_pivot_index]); - - if (r_lnors_spacearr) { - /* Assign current lnor space to current 'vertex' loop. */ - BKE_lnor_space_add_loop( - r_lnors_spacearr, lnor_space, lfan_pivot_index, lfan_pivot, false); - if (e_next != e_org) { - /* We store here all edges-normalized vectors processed. */ - BLI_stack_push(edge_vectors, vec_next); - } - } - - if (!BM_elem_flag_test(e_next, BM_ELEM_TAG) || (e_next == e_org)) { - /* Next edge is sharp, we have finished with this fan of faces around this vert! */ - break; - } - - /* Copy next edge vector to current one. */ - copy_v3_v3(vec_curr, vec_next); - /* Next pivot loop to current one. */ - lfan_pivot = lfan_pivot_next; - lfan_pivot_index = BM_elem_index_get(lfan_pivot); - } - - { - float lnor_len = normalize_v3(lnor); - - /* If we are generating lnor spacearr, we can now define the one for this fan. */ - if (r_lnors_spacearr) { - if (UNLIKELY(lnor_len == 0.0f)) { - /* Use vertex normal as fallback! */ - copy_v3_v3(lnor, r_lnos[lfan_pivot_index]); - lnor_len = 1.0f; - } - - BKE_lnor_space_define(lnor_space, lnor, vec_org, vec_next, edge_vectors); - - if (has_clnors) { - if (clnors_invalid) { - short *clnor; - - clnors_avg[0] /= clnors_nbr; - clnors_avg[1] /= clnors_nbr; - /* Fix/update all clnors of this fan with computed average value. */ - - /* Prints continuously when merge custom normals, so commenting. */ - /* printf("Invalid clnors in this fan!\n"); */ - - while ((clnor = BLI_SMALLSTACK_POP(clnors))) { - // print_v2("org clnor", clnor); - clnor[0] = (short)clnors_avg[0]; - clnor[1] = (short)clnors_avg[1]; - } - // print_v2("new clnors", clnors_avg); - } - else { - /* We still have to consume the stack! */ - while (BLI_SMALLSTACK_POP(clnors)) { - /* pass */ - } - } - BKE_lnor_space_custom_data_to_normal(lnor_space, *clnor_ref, lnor); - } - } - - /* In case we get a zero normal here, just use vertex normal already set! */ - if (LIKELY(lnor_len != 0.0f)) { - /* Copy back the final computed normal into all related loop-normals. */ - float *nor; - - while ((nor = BLI_SMALLSTACK_POP(normal))) { - copy_v3_v3(nor, lnor); - } - } - else { - /* We still have to consume the stack! */ - while (BLI_SMALLSTACK_POP(normal)) { - /* pass */ - } - } - } - - /* Tag related vertex as sharp, to avoid fanning around it again - * (in case it was a smooth one). */ - if (r_lnors_spacearr) { - BM_elem_flag_enable(l_curr->v, BM_ELEM_TAG); - } - } - } while ((l_curr = l_curr->next) != l_first); - } - - if (r_lnors_spacearr) { - BLI_stack_free(edge_vectors); - if (r_lnors_spacearr == &_lnors_spacearr) { - BKE_lnor_spacearr_free(r_lnors_spacearr); - } - } -} - -/* This threshold is a bit touchy (usual float precision issue), this value seems OK. */ -#define LNOR_SPACE_TRIGO_THRESHOLD (1.0f - 1e-4f) - -/** - * Check each current smooth fan (one lnor space per smooth fan!), and if all its - * matching custom lnors are not (enough) equal, add sharp edges as needed. - */ -static bool bm_mesh_loops_split_lnor_fans(BMesh *bm, - MLoopNorSpaceArray *lnors_spacearr, - const float (*new_lnors)[3]) -{ - BLI_bitmap *done_loops = BLI_BITMAP_NEW((size_t)bm->totloop, __func__); - bool changed = false; - - BLI_assert(lnors_spacearr->data_type == MLNOR_SPACEARR_BMLOOP_PTR); - - for (int i = 0; i < bm->totloop; i++) { - if (!lnors_spacearr->lspacearr[i]) { - /* This should not happen in theory, but in some rare case (probably ugly geometry) - * we can get some NULL loopspacearr at this point. :/ - * Maybe we should set those loops' edges as sharp? - */ - BLI_BITMAP_ENABLE(done_loops, i); - if (G.debug & G_DEBUG) { - printf("WARNING! Getting invalid NULL loop space for loop %d!\n", i); - } - continue; - } - - if (!BLI_BITMAP_TEST(done_loops, i)) { - /* Notes: - * * In case of mono-loop smooth fan, we have nothing to do. - * * Loops in this linklist are ordered (in reversed order compared to how they were - * discovered by BKE_mesh_normals_loop_split(), but this is not a problem). - * Which means if we find a mismatching clnor, - * we know all remaining loops will have to be in a new, different smooth fan/lnor space. - * * In smooth fan case, we compare each clnor against a ref one, - * to avoid small differences adding up into a real big one in the end! - */ - if (lnors_spacearr->lspacearr[i]->flags & MLNOR_SPACE_IS_SINGLE) { - BLI_BITMAP_ENABLE(done_loops, i); - continue; - } - - LinkNode *loops = lnors_spacearr->lspacearr[i]->loops; - BMLoop *prev_ml = NULL; - const float *org_nor = NULL; - - while (loops) { - BMLoop *ml = loops->link; - const int lidx = BM_elem_index_get(ml); - const float *nor = new_lnors[lidx]; - - if (!org_nor) { - org_nor = nor; - } - else if (dot_v3v3(org_nor, nor) < LNOR_SPACE_TRIGO_THRESHOLD) { - /* Current normal differs too much from org one, we have to tag the edge between - * previous loop's face and current's one as sharp. - * We know those two loops do not point to the same edge, - * since we do not allow reversed winding in a same smooth fan. - */ - BMEdge *e = (prev_ml->e == ml->prev->e) ? prev_ml->e : ml->e; - - BM_elem_flag_disable(e, BM_ELEM_TAG | BM_ELEM_SMOOTH); - changed = true; - - org_nor = nor; - } - - prev_ml = ml; - loops = loops->next; - BLI_BITMAP_ENABLE(done_loops, lidx); - } - - /* We also have to check between last and first loops, - * otherwise we may miss some sharp edges here! - * This is just a simplified version of above while loop. - * See T45984. */ - loops = lnors_spacearr->lspacearr[i]->loops; - if (loops && org_nor) { - BMLoop *ml = loops->link; - const int lidx = BM_elem_index_get(ml); - const float *nor = new_lnors[lidx]; - - if (dot_v3v3(org_nor, nor) < LNOR_SPACE_TRIGO_THRESHOLD) { - BMEdge *e = (prev_ml->e == ml->prev->e) ? prev_ml->e : ml->e; - - BM_elem_flag_disable(e, BM_ELEM_TAG | BM_ELEM_SMOOTH); - changed = true; - } - } - } - } - - MEM_freeN(done_loops); - return changed; -} - -/** - * Assign custom normal data from given normal vectors, averaging normals - * from one smooth fan as necessary. - */ -static void bm_mesh_loops_assign_normal_data(BMesh *bm, - MLoopNorSpaceArray *lnors_spacearr, - short (*r_clnors_data)[2], - const int cd_loop_clnors_offset, - const float (*new_lnors)[3]) -{ - BLI_bitmap *done_loops = BLI_BITMAP_NEW((size_t)bm->totloop, __func__); - - BLI_SMALLSTACK_DECLARE(clnors_data, short *); - - BLI_assert(lnors_spacearr->data_type == MLNOR_SPACEARR_BMLOOP_PTR); - - for (int i = 0; i < bm->totloop; i++) { - if (!lnors_spacearr->lspacearr[i]) { - BLI_BITMAP_ENABLE(done_loops, i); - if (G.debug & G_DEBUG) { - printf("WARNING! Still getting invalid NULL loop space in second loop for loop %d!\n", i); - } - continue; - } - - if (!BLI_BITMAP_TEST(done_loops, i)) { - /* Note we accumulate and average all custom normals in current smooth fan, - * to avoid getting different clnors data (tiny differences in plain custom normals can - * give rather huge differences in computed 2D factors). - */ - LinkNode *loops = lnors_spacearr->lspacearr[i]->loops; - - if (lnors_spacearr->lspacearr[i]->flags & MLNOR_SPACE_IS_SINGLE) { - BMLoop *ml = (BMLoop *)loops; - const int lidx = BM_elem_index_get(ml); - - BLI_assert(lidx == i); - - const float *nor = new_lnors[lidx]; - short *clnor = r_clnors_data ? &r_clnors_data[lidx] : - BM_ELEM_CD_GET_VOID_P(ml, cd_loop_clnors_offset); - - BKE_lnor_space_custom_normal_to_data(lnors_spacearr->lspacearr[i], nor, clnor); - BLI_BITMAP_ENABLE(done_loops, i); - } - else { - int nbr_nors = 0; - float avg_nor[3]; - short clnor_data_tmp[2], *clnor_data; - - zero_v3(avg_nor); - - while (loops) { - BMLoop *ml = loops->link; - const int lidx = BM_elem_index_get(ml); - const float *nor = new_lnors[lidx]; - short *clnor = r_clnors_data ? &r_clnors_data[lidx] : - BM_ELEM_CD_GET_VOID_P(ml, cd_loop_clnors_offset); - - nbr_nors++; - add_v3_v3(avg_nor, nor); - BLI_SMALLSTACK_PUSH(clnors_data, clnor); - - loops = loops->next; - BLI_BITMAP_ENABLE(done_loops, lidx); - } - - mul_v3_fl(avg_nor, 1.0f / (float)nbr_nors); - BKE_lnor_space_custom_normal_to_data( - lnors_spacearr->lspacearr[i], avg_nor, clnor_data_tmp); - - while ((clnor_data = BLI_SMALLSTACK_POP(clnors_data))) { - clnor_data[0] = clnor_data_tmp[0]; - clnor_data[1] = clnor_data_tmp[1]; - } - } - } - } - - MEM_freeN(done_loops); -} - -/** - * Compute internal representation of given custom normals (as an array of float[2] or data layer). - * - * It also makes sure the mesh matches those custom normals, by marking new sharp edges to split - * the smooth fans when loop normals for the same vertex are different, or averaging the normals - * instead, depending on the do_split_fans parameter. - */ -static void bm_mesh_loops_custom_normals_set(BMesh *bm, - const float (*vcos)[3], - const float (*vnos)[3], - const float (*fnos)[3], - MLoopNorSpaceArray *r_lnors_spacearr, - short (*r_clnors_data)[2], - const int cd_loop_clnors_offset, - float (*new_lnors)[3], - const int cd_new_lnors_offset, - bool do_split_fans) -{ - BMFace *f; - BMLoop *l; - BMIter liter, fiter; - float(*cur_lnors)[3] = MEM_mallocN(sizeof(*cur_lnors) * bm->totloop, __func__); - - BKE_lnor_spacearr_clear(r_lnors_spacearr); - - /* Tag smooth edges and set lnos from vnos when they might be completely smooth... - * When using custom loop normals, disable the angle feature! */ - bm_mesh_edges_sharp_tag(bm, vnos, fnos, cur_lnors, (float)M_PI, false); - - /* Finish computing lnos by accumulating face normals - * in each fan of faces defined by sharp edges. */ - bm_mesh_loops_calc_normals( - bm, vcos, fnos, cur_lnors, r_lnors_spacearr, r_clnors_data, cd_loop_clnors_offset, false); - - /* Extract new normals from the data layer if necessary. */ - float(*custom_lnors)[3] = new_lnors; - - if (new_lnors == NULL) { - custom_lnors = MEM_mallocN(sizeof(*new_lnors) * bm->totloop, __func__); - - BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { - BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { - const float *normal = BM_ELEM_CD_GET_VOID_P(l, cd_new_lnors_offset); - copy_v3_v3(custom_lnors[BM_elem_index_get(l)], normal); - } - } - } - - /* Validate the new normals. */ - for (int i = 0; i < bm->totloop; i++) { - if (is_zero_v3(custom_lnors[i])) { - copy_v3_v3(custom_lnors[i], cur_lnors[i]); - } - else { - normalize_v3(custom_lnors[i]); - } - } - - /* Now, check each current smooth fan (one lnor space per smooth fan!), - * and if all its matching custom lnors are not equal, add sharp edges as needed. */ - if (do_split_fans && bm_mesh_loops_split_lnor_fans(bm, r_lnors_spacearr, custom_lnors)) { - /* If any sharp edges were added, run bm_mesh_loops_calc_normals() again to get lnor - * spacearr/smooth fans matching the given custom lnors. */ - BKE_lnor_spacearr_clear(r_lnors_spacearr); - - bm_mesh_loops_calc_normals( - bm, vcos, fnos, cur_lnors, r_lnors_spacearr, r_clnors_data, cd_loop_clnors_offset, false); - } - - /* And we just have to convert plain object-space custom normals to our - * lnor space-encoded ones. */ - bm_mesh_loops_assign_normal_data( - bm, r_lnors_spacearr, r_clnors_data, cd_loop_clnors_offset, custom_lnors); - - MEM_freeN(cur_lnors); - - if (custom_lnors != new_lnors) { - MEM_freeN(custom_lnors); - } -} - -static void bm_mesh_loops_calc_normals_no_autosmooth(BMesh *bm, - const float (*vnos)[3], - const float (*fnos)[3], - float (*r_lnos)[3]) -{ - BMIter fiter; - BMFace *f_curr; - - { - char htype = BM_LOOP; - if (vnos) { - htype |= BM_VERT; - } - if (fnos) { - htype |= BM_FACE; - } - BM_mesh_elem_index_ensure(bm, htype); - } - - BM_ITER_MESH (f_curr, &fiter, bm, BM_FACES_OF_MESH) { - BMLoop *l_curr, *l_first; - const bool is_face_flat = !BM_elem_flag_test(f_curr, BM_ELEM_SMOOTH); - - l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr); - do { - const float *no = is_face_flat ? (fnos ? fnos[BM_elem_index_get(f_curr)] : f_curr->no) : - (vnos ? vnos[BM_elem_index_get(l_curr->v)] : l_curr->v->no); - copy_v3_v3(r_lnos[BM_elem_index_get(l_curr)], no); - - } while ((l_curr = l_curr->next) != l_first); - } -} - -#if 0 /* Unused currently */ -/** - * \brief BMesh Compute Loop Normals - * - * Updates the loop normals of a mesh. - * Assumes vertex and face normals are valid (else call BM_mesh_normals_update() first)! - */ -void BM_mesh_loop_normals_update(BMesh *bm, - const bool use_split_normals, - const float split_angle, - float (*r_lnos)[3], - MLoopNorSpaceArray *r_lnors_spacearr, - const short (*clnors_data)[2], - const int cd_loop_clnors_offset) -{ - const bool has_clnors = clnors_data || (cd_loop_clnors_offset != -1); - - if (use_split_normals) { - /* Tag smooth edges and set lnos from vnos when they might be completely smooth... - * When using custom loop normals, disable the angle feature! */ - bm_mesh_edges_sharp_tag(bm, NULL, NULL, has_clnors ? (float)M_PI : split_angle, r_lnos); - - /* Finish computing lnos by accumulating face normals - * in each fan of faces defined by sharp edges. */ - bm_mesh_loops_calc_normals( - bm, NULL, NULL, r_lnos, r_lnors_spacearr, clnors_data, cd_loop_clnors_offset); - } - else { - BLI_assert(!r_lnors_spacearr); - bm_mesh_loops_calc_normals_no_autosmooth(bm, NULL, NULL, r_lnos); - } -} -#endif - -/** - * \brief BMesh Compute Loop Normals from/to external data. - * - * Compute split normals, i.e. vertex normals associated with each poly (hence 'loop normals'). - * Useful to materialize sharp edges (or non-smooth faces) without actually modifying the geometry - * (splitting edges). - */ -void BM_loops_calc_normal_vcos(BMesh *bm, - const float (*vcos)[3], - const float (*vnos)[3], - const float (*fnos)[3], - const bool use_split_normals, - const float split_angle, - float (*r_lnos)[3], - MLoopNorSpaceArray *r_lnors_spacearr, - short (*clnors_data)[2], - const int cd_loop_clnors_offset, - const bool do_rebuild) -{ - const bool has_clnors = clnors_data || (cd_loop_clnors_offset != -1); - - if (use_split_normals) { - /* Tag smooth edges and set lnos from vnos when they might be completely smooth... - * When using custom loop normals, disable the angle feature! */ - bm_mesh_edges_sharp_tag(bm, vnos, fnos, r_lnos, has_clnors ? (float)M_PI : split_angle, false); - - /* Finish computing lnos by accumulating face normals - * in each fan of faces defined by sharp edges. */ - bm_mesh_loops_calc_normals( - bm, vcos, fnos, r_lnos, r_lnors_spacearr, clnors_data, cd_loop_clnors_offset, do_rebuild); - } - else { - BLI_assert(!r_lnors_spacearr); - bm_mesh_loops_calc_normals_no_autosmooth(bm, vnos, fnos, r_lnos); - } -} - -/** - * Define sharp edges as needed to mimic 'autosmooth' from angle threshold. - * - * Used when defining an empty custom loop normals data layer, - * to keep same shading as with autosmooth! - */ -void BM_edges_sharp_from_angle_set(BMesh *bm, const float split_angle) -{ - if (split_angle >= (float)M_PI) { - /* Nothing to do! */ - return; - } - - bm_mesh_edges_sharp_tag(bm, NULL, NULL, NULL, split_angle, true); -} - -void BM_lnorspacearr_store(BMesh *bm, float (*r_lnors)[3]) -{ - BLI_assert(bm->lnor_spacearr != NULL); - - if (!CustomData_has_layer(&bm->ldata, CD_CUSTOMLOOPNORMAL)) { - BM_data_layer_add(bm, &bm->ldata, CD_CUSTOMLOOPNORMAL); - } - - int cd_loop_clnors_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL); - - BM_loops_calc_normal_vcos(bm, - NULL, - NULL, - NULL, - true, - M_PI, - r_lnors, - bm->lnor_spacearr, - NULL, - cd_loop_clnors_offset, - false); - bm->spacearr_dirty &= ~(BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL); -} - -#define CLEAR_SPACEARRAY_THRESHOLD(x) ((x) / 2) - -void BM_lnorspace_invalidate(BMesh *bm, const bool do_invalidate_all) -{ - if (bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL) { - return; - } - if (do_invalidate_all || bm->totvertsel > CLEAR_SPACEARRAY_THRESHOLD(bm->totvert)) { - bm->spacearr_dirty |= BM_SPACEARR_DIRTY_ALL; - return; - } - if (bm->lnor_spacearr == NULL) { - bm->spacearr_dirty |= BM_SPACEARR_DIRTY_ALL; - return; - } - - BMVert *v; - BMLoop *l; - BMIter viter, liter; - /* Note: we could use temp tag of BMItem for that, - * but probably better not use it in such a low-level func? - * --mont29 */ - BLI_bitmap *done_verts = BLI_BITMAP_NEW(bm->totvert, __func__); - - BM_mesh_elem_index_ensure(bm, BM_VERT); - - /* When we affect a given vertex, we may affect following smooth fans: - * - all smooth fans of said vertex; - * - all smooth fans of all immediate loop-neighbors vertices; - * This can be simplified as 'all loops of selected vertices and their immediate neighbors' - * need to be tagged for update. - */ - BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) { - if (BM_elem_flag_test(v, BM_ELEM_SELECT)) { - BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) { - BM_ELEM_API_FLAG_ENABLE(l, BM_LNORSPACE_UPDATE); - - /* Note that we only handle unselected neighbor vertices here, main loop will take care of - * selected ones. */ - if ((!BM_elem_flag_test(l->prev->v, BM_ELEM_SELECT)) && - !BLI_BITMAP_TEST(done_verts, BM_elem_index_get(l->prev->v))) { - - BMLoop *l_prev; - BMIter liter_prev; - BM_ITER_ELEM (l_prev, &liter_prev, l->prev->v, BM_LOOPS_OF_VERT) { - BM_ELEM_API_FLAG_ENABLE(l_prev, BM_LNORSPACE_UPDATE); - } - BLI_BITMAP_ENABLE(done_verts, BM_elem_index_get(l_prev->v)); - } - - if ((!BM_elem_flag_test(l->next->v, BM_ELEM_SELECT)) && - !BLI_BITMAP_TEST(done_verts, BM_elem_index_get(l->next->v))) { - - BMLoop *l_next; - BMIter liter_next; - BM_ITER_ELEM (l_next, &liter_next, l->next->v, BM_LOOPS_OF_VERT) { - BM_ELEM_API_FLAG_ENABLE(l_next, BM_LNORSPACE_UPDATE); - } - BLI_BITMAP_ENABLE(done_verts, BM_elem_index_get(l_next->v)); - } - } - - BLI_BITMAP_ENABLE(done_verts, BM_elem_index_get(v)); - } - } - - MEM_freeN(done_verts); - bm->spacearr_dirty |= BM_SPACEARR_DIRTY; -} - -void BM_lnorspace_rebuild(BMesh *bm, bool preserve_clnor) -{ - BLI_assert(bm->lnor_spacearr != NULL); - - if (!(bm->spacearr_dirty & (BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL))) { - return; - } - BMFace *f; - BMLoop *l; - BMIter fiter, liter; - - float(*r_lnors)[3] = MEM_callocN(sizeof(*r_lnors) * bm->totloop, __func__); - float(*oldnors)[3] = preserve_clnor ? MEM_mallocN(sizeof(*oldnors) * bm->totloop, __func__) : - NULL; - - int cd_loop_clnors_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL); - - BM_mesh_elem_index_ensure(bm, BM_LOOP); - - if (preserve_clnor) { - BLI_assert(bm->lnor_spacearr->lspacearr != NULL); - - BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { - BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { - if (BM_ELEM_API_FLAG_TEST(l, BM_LNORSPACE_UPDATE) || - bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL) { - short(*clnor)[2] = BM_ELEM_CD_GET_VOID_P(l, cd_loop_clnors_offset); - int l_index = BM_elem_index_get(l); - - BKE_lnor_space_custom_data_to_normal( - bm->lnor_spacearr->lspacearr[l_index], *clnor, oldnors[l_index]); - } - } - } - } - - if (bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL) { - BKE_lnor_spacearr_clear(bm->lnor_spacearr); - } - BM_loops_calc_normal_vcos(bm, - NULL, - NULL, - NULL, - true, - M_PI, - r_lnors, - bm->lnor_spacearr, - NULL, - cd_loop_clnors_offset, - true); - MEM_freeN(r_lnors); - - BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { - BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { - if (BM_ELEM_API_FLAG_TEST(l, BM_LNORSPACE_UPDATE) || - bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL) { - if (preserve_clnor) { - short(*clnor)[2] = BM_ELEM_CD_GET_VOID_P(l, cd_loop_clnors_offset); - int l_index = BM_elem_index_get(l); - BKE_lnor_space_custom_normal_to_data( - bm->lnor_spacearr->lspacearr[l_index], oldnors[l_index], *clnor); - } - BM_ELEM_API_FLAG_DISABLE(l, BM_LNORSPACE_UPDATE); - } - } - } - - MEM_SAFE_FREE(oldnors); - bm->spacearr_dirty &= ~(BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL); - -#ifndef NDEBUG - BM_lnorspace_err(bm); -#endif -} - -/** - * \warning This function sets #BM_ELEM_TAG on loops & edges via #bm_mesh_loops_calc_normals, - * take care to run this before setting up tags. - */ -void BM_lnorspace_update(BMesh *bm) -{ - if (bm->lnor_spacearr == NULL) { - bm->lnor_spacearr = MEM_callocN(sizeof(*bm->lnor_spacearr), __func__); - } - if (bm->lnor_spacearr->lspacearr == NULL) { - float(*lnors)[3] = MEM_callocN(sizeof(*lnors) * bm->totloop, __func__); - - BM_lnorspacearr_store(bm, lnors); - - MEM_freeN(lnors); - } - else if (bm->spacearr_dirty & (BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL)) { - BM_lnorspace_rebuild(bm, false); - } -} - -void BM_normals_loops_edges_tag(BMesh *bm, const bool do_edges) -{ - BMFace *f; - BMEdge *e; - BMIter fiter, eiter; - BMLoop *l_curr, *l_first; - - if (do_edges) { - int index_edge; - BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, index_edge) { - BMLoop *l_a, *l_b; - - BM_elem_index_set(e, index_edge); /* set_inline */ - BM_elem_flag_disable(e, BM_ELEM_TAG); - if (BM_edge_loop_pair(e, &l_a, &l_b)) { - if (BM_elem_flag_test(e, BM_ELEM_SMOOTH) && l_a->v != l_b->v) { - BM_elem_flag_enable(e, BM_ELEM_TAG); - } - } - } - bm->elem_index_dirty &= ~BM_EDGE; - } - - int index_face, index_loop = 0; - BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, index_face) { - BM_elem_index_set(f, index_face); /* set_inline */ - l_curr = l_first = BM_FACE_FIRST_LOOP(f); - do { - BM_elem_index_set(l_curr, index_loop++); /* set_inline */ - BM_elem_flag_disable(l_curr, BM_ELEM_TAG); - } while ((l_curr = l_curr->next) != l_first); - } - bm->elem_index_dirty &= ~(BM_FACE | BM_LOOP); -} - -/** - * Auxiliary function only used by rebuild to detect if any spaces were not marked as invalid. - * Reports error if any of the lnor spaces change after rebuilding, meaning that all the possible - * lnor spaces to be rebuilt were not correctly marked. - */ -#ifndef NDEBUG -void BM_lnorspace_err(BMesh *bm) -{ - bm->spacearr_dirty |= BM_SPACEARR_DIRTY_ALL; - bool clear = true; - - MLoopNorSpaceArray *temp = MEM_callocN(sizeof(*temp), __func__); - temp->lspacearr = NULL; - - BKE_lnor_spacearr_init(temp, bm->totloop, MLNOR_SPACEARR_BMLOOP_PTR); - - int cd_loop_clnors_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL); - float(*lnors)[3] = MEM_callocN(sizeof(*lnors) * bm->totloop, __func__); - BM_loops_calc_normal_vcos( - bm, NULL, NULL, NULL, true, M_PI, lnors, temp, NULL, cd_loop_clnors_offset, true); - - for (int i = 0; i < bm->totloop; i++) { - int j = 0; - j += compare_ff( - temp->lspacearr[i]->ref_alpha, bm->lnor_spacearr->lspacearr[i]->ref_alpha, 1e-4f); - j += compare_ff( - temp->lspacearr[i]->ref_beta, bm->lnor_spacearr->lspacearr[i]->ref_beta, 1e-4f); - j += compare_v3v3( - temp->lspacearr[i]->vec_lnor, bm->lnor_spacearr->lspacearr[i]->vec_lnor, 1e-4f); - j += compare_v3v3( - temp->lspacearr[i]->vec_ortho, bm->lnor_spacearr->lspacearr[i]->vec_ortho, 1e-4f); - j += compare_v3v3( - temp->lspacearr[i]->vec_ref, bm->lnor_spacearr->lspacearr[i]->vec_ref, 1e-4f); - - if (j != 5) { - clear = false; - break; - } - } - BKE_lnor_spacearr_free(temp); - MEM_freeN(temp); - MEM_freeN(lnors); - BLI_assert(clear); - - bm->spacearr_dirty &= ~BM_SPACEARR_DIRTY_ALL; -} -#endif - -static void bm_loop_normal_mark_indiv_do_loop(BMLoop *l, - BLI_bitmap *loops, - MLoopNorSpaceArray *lnor_spacearr, - int *totloopsel, - const bool do_all_loops_of_vert) -{ - if (l != NULL) { - const int l_idx = BM_elem_index_get(l); - - if (!BLI_BITMAP_TEST(loops, l_idx)) { - /* If vert and face selected share a loop, mark it for editing. */ - BLI_BITMAP_ENABLE(loops, l_idx); - (*totloopsel)++; - - if (do_all_loops_of_vert) { - /* If required, also mark all loops shared by that vertex. - * This is needed when loop spaces may change - * (i.e. when some faces or edges might change of smooth/sharp status). */ - BMIter liter; - BMLoop *lfan; - BM_ITER_ELEM (lfan, &liter, l->v, BM_LOOPS_OF_VERT) { - const int lfan_idx = BM_elem_index_get(lfan); - if (!BLI_BITMAP_TEST(loops, lfan_idx)) { - BLI_BITMAP_ENABLE(loops, lfan_idx); - (*totloopsel)++; - } - } - } - else { - /* Mark all loops in same loop normal space (aka smooth fan). */ - if ((lnor_spacearr->lspacearr[l_idx]->flags & MLNOR_SPACE_IS_SINGLE) == 0) { - for (LinkNode *node = lnor_spacearr->lspacearr[l_idx]->loops; node; node = node->next) { - const int lfan_idx = BM_elem_index_get((BMLoop *)node->link); - if (!BLI_BITMAP_TEST(loops, lfan_idx)) { - BLI_BITMAP_ENABLE(loops, lfan_idx); - (*totloopsel)++; - } - } - } - } - } - } -} - -/* Mark the individual clnors to be edited, if multiple selection methods are used. */ -static int bm_loop_normal_mark_indiv(BMesh *bm, BLI_bitmap *loops, const bool do_all_loops_of_vert) -{ - BMEditSelection *ese, *ese_prev; - int totloopsel = 0; - - const bool sel_verts = (bm->selectmode & SCE_SELECT_VERTEX) != 0; - const bool sel_edges = (bm->selectmode & SCE_SELECT_EDGE) != 0; - const bool sel_faces = (bm->selectmode & SCE_SELECT_FACE) != 0; - const bool use_sel_face_history = sel_faces && (sel_edges || sel_verts); - - BM_mesh_elem_index_ensure(bm, BM_LOOP); - - BLI_assert(bm->lnor_spacearr != NULL); - BLI_assert(bm->lnor_spacearr->data_type == MLNOR_SPACEARR_BMLOOP_PTR); - - if (use_sel_face_history) { - /* Using face history allows to select a single loop from a single face... - * Note that this is On² piece of code, - * but it is not designed to be used with huge selection sets, - * rather with only a few items selected at most.*/ - /* Goes from last selected to the first selected element. */ - for (ese = bm->selected.last; ese; ese = ese->prev) { - if (ese->htype == BM_FACE) { - /* If current face is selected, - * then any verts to be edited must have been selected before it. */ - for (ese_prev = ese->prev; ese_prev; ese_prev = ese_prev->prev) { - if (ese_prev->htype == BM_VERT) { - bm_loop_normal_mark_indiv_do_loop( - BM_face_vert_share_loop((BMFace *)ese->ele, (BMVert *)ese_prev->ele), - loops, - bm->lnor_spacearr, - &totloopsel, - do_all_loops_of_vert); - } - else if (ese_prev->htype == BM_EDGE) { - BMEdge *e = (BMEdge *)ese_prev->ele; - bm_loop_normal_mark_indiv_do_loop(BM_face_vert_share_loop((BMFace *)ese->ele, e->v1), - loops, - bm->lnor_spacearr, - &totloopsel, - do_all_loops_of_vert); - - bm_loop_normal_mark_indiv_do_loop(BM_face_vert_share_loop((BMFace *)ese->ele, e->v2), - loops, - bm->lnor_spacearr, - &totloopsel, - do_all_loops_of_vert); - } - } - } - } - } - else { - if (sel_faces) { - /* Only select all loops of selected faces. */ - BMLoop *l; - BMFace *f; - BMIter liter, fiter; - BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { - if (BM_elem_flag_test(f, BM_ELEM_SELECT)) { - BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { - bm_loop_normal_mark_indiv_do_loop( - l, loops, bm->lnor_spacearr, &totloopsel, do_all_loops_of_vert); - } - } - } - } - if (sel_edges) { - /* Only select all loops of selected edges. */ - BMLoop *l; - BMEdge *e; - BMIter liter, eiter; - BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) { - if (BM_elem_flag_test(e, BM_ELEM_SELECT)) { - BM_ITER_ELEM (l, &liter, e, BM_LOOPS_OF_EDGE) { - bm_loop_normal_mark_indiv_do_loop( - l, loops, bm->lnor_spacearr, &totloopsel, do_all_loops_of_vert); - /* Loops actually 'have' two edges, or said otherwise, a selected edge actually selects - * *two* loops in each of its faces. We have to find the other one too. */ - if (BM_vert_in_edge(e, l->next->v)) { - bm_loop_normal_mark_indiv_do_loop( - l->next, loops, bm->lnor_spacearr, &totloopsel, do_all_loops_of_vert); - } - else { - BLI_assert(BM_vert_in_edge(e, l->prev->v)); - bm_loop_normal_mark_indiv_do_loop( - l->prev, loops, bm->lnor_spacearr, &totloopsel, do_all_loops_of_vert); - } - } - } - } - } - if (sel_verts) { - /* Select all loops of selected verts. */ - BMLoop *l; - BMVert *v; - BMIter liter, viter; - BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) { - if (BM_elem_flag_test(v, BM_ELEM_SELECT)) { - BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) { - bm_loop_normal_mark_indiv_do_loop( - l, loops, bm->lnor_spacearr, &totloopsel, do_all_loops_of_vert); - } - } - } - } - } - - return totloopsel; -} - -static void loop_normal_editdata_init( - BMesh *bm, BMLoopNorEditData *lnor_ed, BMVert *v, BMLoop *l, const int offset) -{ - BLI_assert(bm->lnor_spacearr != NULL); - BLI_assert(bm->lnor_spacearr->lspacearr != NULL); - - const int l_index = BM_elem_index_get(l); - short *clnors_data = BM_ELEM_CD_GET_VOID_P(l, offset); - - lnor_ed->loop_index = l_index; - lnor_ed->loop = l; - - float custom_normal[3]; - BKE_lnor_space_custom_data_to_normal( - bm->lnor_spacearr->lspacearr[l_index], clnors_data, custom_normal); - - lnor_ed->clnors_data = clnors_data; - copy_v3_v3(lnor_ed->nloc, custom_normal); - copy_v3_v3(lnor_ed->niloc, custom_normal); - - lnor_ed->loc = v->co; -} - -BMLoopNorEditDataArray *BM_loop_normal_editdata_array_init(BMesh *bm, - const bool do_all_loops_of_vert) -{ - BMLoop *l; - BMVert *v; - BMIter liter, viter; - - int totloopsel = 0; - - BLI_assert(bm->spacearr_dirty == 0); - - BMLoopNorEditDataArray *lnors_ed_arr = MEM_callocN(sizeof(*lnors_ed_arr), __func__); - lnors_ed_arr->lidx_to_lnor_editdata = MEM_callocN( - sizeof(*lnors_ed_arr->lidx_to_lnor_editdata) * bm->totloop, __func__); - - if (!CustomData_has_layer(&bm->ldata, CD_CUSTOMLOOPNORMAL)) { - BM_data_layer_add(bm, &bm->ldata, CD_CUSTOMLOOPNORMAL); - } - const int cd_custom_normal_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL); - - BM_mesh_elem_index_ensure(bm, BM_LOOP); - - BLI_bitmap *loops = BLI_BITMAP_NEW(bm->totloop, __func__); - - /* This function define loop normals to edit, based on selection modes and history. */ - totloopsel = bm_loop_normal_mark_indiv(bm, loops, do_all_loops_of_vert); - - if (totloopsel) { - BMLoopNorEditData *lnor_ed = lnors_ed_arr->lnor_editdata = MEM_mallocN( - sizeof(*lnor_ed) * totloopsel, __func__); - - BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) { - BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) { - if (BLI_BITMAP_TEST(loops, BM_elem_index_get(l))) { - loop_normal_editdata_init(bm, lnor_ed, v, l, cd_custom_normal_offset); - lnors_ed_arr->lidx_to_lnor_editdata[BM_elem_index_get(l)] = lnor_ed; - lnor_ed++; - } - } - } - lnors_ed_arr->totloop = totloopsel; - } - - MEM_freeN(loops); - lnors_ed_arr->cd_custom_normal_offset = cd_custom_normal_offset; - return lnors_ed_arr; -} - -void BM_loop_normal_editdata_array_free(BMLoopNorEditDataArray *lnors_ed_arr) -{ - MEM_SAFE_FREE(lnors_ed_arr->lnor_editdata); - MEM_SAFE_FREE(lnors_ed_arr->lidx_to_lnor_editdata); - MEM_freeN(lnors_ed_arr); -} - -/** - * \warning This function sets #BM_ELEM_TAG on loops & edges via #bm_mesh_loops_calc_normals, - * take care to run this before setting up tags. - */ -bool BM_custom_loop_normals_to_vector_layer(BMesh *bm) -{ - BMFace *f; - BMLoop *l; - BMIter liter, fiter; - - if (!CustomData_has_layer(&bm->ldata, CD_CUSTOMLOOPNORMAL)) { - return false; - } - - BM_lnorspace_update(bm); - BM_mesh_elem_index_ensure(bm, BM_LOOP); - - /* Create a loop normal layer. */ - if (!CustomData_has_layer(&bm->ldata, CD_NORMAL)) { - BM_data_layer_add(bm, &bm->ldata, CD_NORMAL); - - CustomData_set_layer_flag(&bm->ldata, CD_NORMAL, CD_FLAG_TEMPORARY); - } - - const int cd_custom_normal_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL); - const int cd_normal_offset = CustomData_get_offset(&bm->ldata, CD_NORMAL); - - BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { - BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { - const int l_index = BM_elem_index_get(l); - const short *clnors_data = BM_ELEM_CD_GET_VOID_P(l, cd_custom_normal_offset); - float *normal = BM_ELEM_CD_GET_VOID_P(l, cd_normal_offset); - - BKE_lnor_space_custom_data_to_normal( - bm->lnor_spacearr->lspacearr[l_index], clnors_data, normal); - } - } - - return true; -} - -void BM_custom_loop_normals_from_vector_layer(BMesh *bm, bool add_sharp_edges) -{ - if (!CustomData_has_layer(&bm->ldata, CD_CUSTOMLOOPNORMAL) || - !CustomData_has_layer(&bm->ldata, CD_NORMAL)) { - return; - } - - const int cd_custom_normal_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL); - const int cd_normal_offset = CustomData_get_offset(&bm->ldata, CD_NORMAL); - - if (bm->lnor_spacearr == NULL) { - bm->lnor_spacearr = MEM_callocN(sizeof(*bm->lnor_spacearr), __func__); - } - - bm_mesh_loops_custom_normals_set(bm, - NULL, - NULL, - NULL, - bm->lnor_spacearr, - NULL, - cd_custom_normal_offset, - NULL, - cd_normal_offset, - add_sharp_edges); - - bm->spacearr_dirty &= ~(BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL); -} - -/** * \brief BMesh Begin Edit * * Functions for setting up a mesh for editing and cleaning up after diff --git a/source/blender/bmesh/intern/bmesh_mesh.h b/source/blender/bmesh/intern/bmesh_mesh.h index c1c2f17d7c1..456275cf157 100644 --- a/source/blender/bmesh/intern/bmesh_mesh.h +++ b/source/blender/bmesh/intern/bmesh_mesh.h @@ -25,6 +25,7 @@ struct BMAllocTemplate; struct BMLoopNorEditDataArray; struct MLoopNorSpaceArray; +struct BMPartialUpdate; void BM_mesh_elem_toolflags_ensure(BMesh *bm); void BM_mesh_elem_toolflags_clear(BMesh *bm); @@ -40,43 +41,6 @@ void BM_mesh_free(BMesh *bm); void BM_mesh_data_free(BMesh *bm); void BM_mesh_clear(BMesh *bm); -void BM_mesh_normals_update(BMesh *bm); -void BM_verts_calc_normal_vcos(BMesh *bm, - const float (*fnos)[3], - const float (*vcos)[3], - float (*vnos)[3]); -void BM_loops_calc_normal_vcos(BMesh *bm, - const float (*vcos)[3], - const float (*vnos)[3], - const float (*fnos)[3], - const bool use_split_normals, - const float split_angle, - float (*r_lnos)[3], - struct MLoopNorSpaceArray *r_lnors_spacearr, - short (*clnors_data)[2], - const int cd_loop_clnors_offset, - const bool do_rebuild); - -bool BM_loop_check_cyclic_smooth_fan(BMLoop *l_curr); -void BM_lnorspacearr_store(BMesh *bm, float (*r_lnors)[3]); -void BM_lnorspace_invalidate(BMesh *bm, const bool do_invalidate_all); -void BM_lnorspace_rebuild(BMesh *bm, bool preserve_clnor); -void BM_lnorspace_update(BMesh *bm); -void BM_normals_loops_edges_tag(BMesh *bm, const bool do_edges); -#ifndef NDEBUG -void BM_lnorspace_err(BMesh *bm); -#endif - -/* Loop Generics */ -struct BMLoopNorEditDataArray *BM_loop_normal_editdata_array_init(BMesh *bm, - const bool do_all_loops_of_vert); -void BM_loop_normal_editdata_array_free(struct BMLoopNorEditDataArray *lnors_ed_arr); - -bool BM_custom_loop_normals_to_vector_layer(struct BMesh *bm); -void BM_custom_loop_normals_from_vector_layer(struct BMesh *bm, bool add_sharp_edges); - -void BM_edges_sharp_from_angle_set(BMesh *bm, const float split_angle); - void bmesh_edit_begin(BMesh *bm, const BMOpTypeFlag type_flag); void bmesh_edit_end(BMesh *bm, const BMOpTypeFlag type_flag); diff --git a/source/blender/bmesh/intern/bmesh_mesh_normals.c b/source/blender/bmesh/intern/bmesh_mesh_normals.c new file mode 100644 index 00000000000..a3eae6dabe8 --- /dev/null +++ b/source/blender/bmesh/intern/bmesh_mesh_normals.c @@ -0,0 +1,1859 @@ +/* + * 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. + */ + +/** \file + * \ingroup bmesh + * + * BM mesh normal calculation functions. + */ + +#include "MEM_guardedalloc.h" + +#include "DNA_scene_types.h" + +#include "BLI_bitmap.h" +#include "BLI_linklist_stack.h" +#include "BLI_math.h" +#include "BLI_stack.h" +#include "BLI_task.h" +#include "BLI_utildefines.h" + +#include "BKE_editmesh.h" +#include "BKE_global.h" +#include "BKE_mesh.h" + +#include "intern/bmesh_private.h" + +/* -------------------------------------------------------------------- */ +/** \name Update Vertex & Face Normals + * \{ */ + +/** + * Helpers for #BM_mesh_normals_update and #BM_verts_calc_normal_vcos + */ + +/* We use that existing internal API flag, + * 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. */ + float (*vnos)[3]; +} BMVertsCalcNormalsWithCoordsData; + +BLI_INLINE void bm_vert_calc_normals_accum_loop(const BMLoop *l_iter, + const float (*edgevec)[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); + if ((l_iter->prev->e->v1 == l_iter->prev->v) ^ (l_iter->e->v1 == l_iter->v)) { + dotprod = -dotprod; + } + const float fac = saacos(-dotprod); + /* NAN detection, otherwise this is a degenerated case, ignore that vertex in this case. */ + if (fac == fac) { /* NAN detection. */ + madd_v3_v3fl(v_no, f_no, fac); + } +} + +static void bm_vert_calc_normals_impl(const float (*edgevec)[3], BMVert *v) +{ + float *v_no = v->no; + zero_v3(v_no); + BMEdge *e_first = v->e; + if (e_first != NULL) { + BMEdge *e_iter = e_first; + do { + BMLoop *l_first = e_iter->l; + if (l_first != NULL) { + 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); + } + } while ((l_iter = l_iter->radial_next) != l_first); + } + } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != e_first); + + if (LIKELY(normalize_v3(v_no) != 0.0f)) { + return; + } + } + /* Fallback normal. */ + normalize_v3_v3(v_no, v->co); +} + +static void bm_vert_calc_normals_cb(void *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); +} + +static void bm_vert_calc_normals_with_coords(BMVert *v, BMVertsCalcNormalsWithCoordsData *data) +{ + 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) { + BMEdge *e_iter = e_first; + do { + BMLoop *l_first = e_iter->l; + if (l_first != NULL) { + BMLoop *l_iter = l_first; + do { + if (l_iter->v == v) { + bm_vert_calc_normals_accum_loop( + l_iter, data->edgevec, data->fnos[BM_elem_index_get(l_iter->f)], v_no); + } + } while ((l_iter = l_iter->radial_next) != l_first); + } + } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != e_first); + + if (LIKELY(normalize_v3(v_no) != 0.0f)) { + return; + } + } + /* Fallback normal. */ + normalize_v3_v3(v_no, data->vcos[BM_elem_index_get(v)]); +} + +static void bm_vert_calc_normals_with_coords_cb(void *userdata, + MempoolIterData *mp_v, + const TaskParallelTLS *__restrict UNUSED(tls)) +{ + BMVertsCalcNormalsWithCoordsData *data = userdata; + BMVert *v = (BMVert *)mp_v; + bm_vert_calc_normals_with_coords(v, data); +} + +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)); + + 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); + } + else { + BLI_assert(!ELEM(NULL, fnos, vnos)); + BMVertsCalcNormalsWithCoordsData data = { + .edgevec = edgevec, + .fnos = fnos, + .vcos = vcos, + .vnos = vnos, + }; + BM_iter_parallel(bm, BM_VERTS_OF_MESH, bm_vert_calc_normals_with_coords_cb, &data, &settings); + } +} + +static void bm_face_calc_normals_cb(void *UNUSED(userdata), + MempoolIterData *mp_f, + const TaskParallelTLS *__restrict UNUSED(tls)) +{ + BMFace *f = (BMFace *)mp_f; + + BM_face_calc_normal(f, f->no); +} + +/** + * \brief BMesh Compute Normals + * + * Updates the normals of a mesh. + */ +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); + settings.use_threading = bm->totedge >= BM_OMP_LIMIT; + + 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); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Update Vertex & Face Normals (Partial Updates) + * \{ */ + +static void bm_partial_faces_parallel_range_calc_normals_cb( + void *userdata, const int iter, const TaskParallelTLS *__restrict UNUSED(tls)) +{ + BMFace *f = ((BMFace **)userdata)[iter]; + 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); +} + +/** + * 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) +{ + 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); + + /* Faces. */ + 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); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Update Vertex & Face Normals (Custom Coords) + * \{ */ + +/** + * \brief BMesh Compute Normals from/to external data. + * + * Computes the vertex normals of a mesh into vnos, + * using given vertex coordinates (vcos) and polygon normals (fnos). + */ +void BM_verts_calc_normal_vcos(BMesh *bm, + const float (*fnos)[3], + 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); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Tagging Utility Functions + * \{ */ + +void BM_normals_loops_edges_tag(BMesh *bm, const bool do_edges) +{ + BMFace *f; + BMEdge *e; + BMIter fiter, eiter; + BMLoop *l_curr, *l_first; + + if (do_edges) { + int index_edge; + BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, index_edge) { + BMLoop *l_a, *l_b; + + BM_elem_index_set(e, index_edge); /* set_inline */ + BM_elem_flag_disable(e, BM_ELEM_TAG); + if (BM_edge_loop_pair(e, &l_a, &l_b)) { + if (BM_elem_flag_test(e, BM_ELEM_SMOOTH) && l_a->v != l_b->v) { + BM_elem_flag_enable(e, BM_ELEM_TAG); + } + } + } + bm->elem_index_dirty &= ~BM_EDGE; + } + + int index_face, index_loop = 0; + BM_ITER_MESH_INDEX (f, &fiter, bm, BM_FACES_OF_MESH, index_face) { + BM_elem_index_set(f, index_face); /* set_inline */ + l_curr = l_first = BM_FACE_FIRST_LOOP(f); + do { + BM_elem_index_set(l_curr, index_loop++); /* set_inline */ + BM_elem_flag_disable(l_curr, BM_ELEM_TAG); + } while ((l_curr = l_curr->next) != l_first); + } + bm->elem_index_dirty &= ~(BM_FACE | BM_LOOP); +} + +/** + * Helpers for #BM_mesh_loop_normals_update and #BM_loops_calc_normal_vcos + */ +static void bm_mesh_edges_sharp_tag(BMesh *bm, + const float (*vnos)[3], + const float (*fnos)[3], + float (*r_lnos)[3], + const float split_angle, + const bool do_sharp_edges_tag) +{ + BMIter eiter; + BMEdge *e; + int i; + + const bool check_angle = (split_angle < (float)M_PI); + const float split_angle_cos = check_angle ? cosf(split_angle) : -1.0f; + + { + char htype = BM_VERT | BM_LOOP; + if (fnos) { + htype |= BM_FACE; + } + BM_mesh_elem_index_ensure(bm, htype); + } + + /* This first loop checks which edges are actually smooth, + * and pre-populate lnos with vnos (as if they were all smooth). */ + BM_ITER_MESH_INDEX (e, &eiter, bm, BM_EDGES_OF_MESH, i) { + BMLoop *l_a, *l_b; + + BM_elem_index_set(e, i); /* set_inline */ + BM_elem_flag_disable(e, BM_ELEM_TAG); /* Clear tag (means edge is sharp). */ + + /* An edge with only two loops, might be smooth... */ + if (BM_edge_loop_pair(e, &l_a, &l_b)) { + bool is_angle_smooth = true; + if (check_angle) { + const float *no_a = fnos ? fnos[BM_elem_index_get(l_a->f)] : l_a->f->no; + const float *no_b = fnos ? fnos[BM_elem_index_get(l_b->f)] : l_b->f->no; + is_angle_smooth = (dot_v3v3(no_a, no_b) >= split_angle_cos); + } + + /* We only tag edges that are *really* smooth: + * If the angle between both its polys' normals is below split_angle value, + * and it is tagged as such, + * and both its faces are smooth, + * and both its faces have compatible (non-flipped) normals, + * i.e. both loops on the same edge do not share the same vertex. + */ + if (BM_elem_flag_test(e, BM_ELEM_SMOOTH) && BM_elem_flag_test(l_a->f, BM_ELEM_SMOOTH) && + BM_elem_flag_test(l_b->f, BM_ELEM_SMOOTH) && l_a->v != l_b->v) { + if (is_angle_smooth) { + const float *no; + BM_elem_flag_enable(e, BM_ELEM_TAG); + + /* linked vertices might be fully smooth, copy their normals to loop ones. */ + if (r_lnos) { + no = vnos ? vnos[BM_elem_index_get(l_a->v)] : l_a->v->no; + copy_v3_v3(r_lnos[BM_elem_index_get(l_a)], no); + no = vnos ? vnos[BM_elem_index_get(l_b->v)] : l_b->v->no; + copy_v3_v3(r_lnos[BM_elem_index_get(l_b)], no); + } + } + else if (do_sharp_edges_tag) { + /* Note that we do not care about the other sharp-edge cases + * (sharp poly, non-manifold edge, etc.), + * only tag edge as sharp when it is due to angle threshold. */ + BM_elem_flag_disable(e, BM_ELEM_SMOOTH); + } + } + } + } + + bm->elem_index_dirty &= ~BM_EDGE; +} + +/** + * Define sharp edges as needed to mimic 'autosmooth' from angle threshold. + * + * Used when defining an empty custom loop normals data layer, + * to keep same shading as with auto-smooth! + */ +void BM_edges_sharp_from_angle_set(BMesh *bm, const float split_angle) +{ + if (split_angle >= (float)M_PI) { + /* Nothing to do! */ + return; + } + + bm_mesh_edges_sharp_tag(bm, NULL, NULL, NULL, split_angle, true); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Loop Normals Calculation API + * \{ */ + +/** + * Check whether given loop is part of an unknown-so-far cyclic smooth fan, or not. + * Needed because cyclic smooth fans have no obvious 'entry point', + * and yet we need to walk them once, and only once. + */ +bool BM_loop_check_cyclic_smooth_fan(BMLoop *l_curr) +{ + BMLoop *lfan_pivot_next = l_curr; + BMEdge *e_next = l_curr->e; + + BLI_assert(!BM_elem_flag_test(lfan_pivot_next, BM_ELEM_TAG)); + BM_elem_flag_enable(lfan_pivot_next, BM_ELEM_TAG); + + while (true) { + /* Much simpler than in sibling code with basic Mesh data! */ + lfan_pivot_next = BM_vert_step_fan_loop(lfan_pivot_next, &e_next); + + if (!lfan_pivot_next || !BM_elem_flag_test(e_next, BM_ELEM_TAG)) { + /* Sharp loop/edge, so not a cyclic smooth fan... */ + return false; + } + /* Smooth loop/edge... */ + if (BM_elem_flag_test(lfan_pivot_next, BM_ELEM_TAG)) { + if (lfan_pivot_next == l_curr) { + /* We walked around a whole cyclic smooth fan + * without finding any already-processed loop, + * means we can use initial l_curr/l_prev edge as start for this smooth fan. */ + return true; + } + /* ... already checked in some previous looping, we can abort. */ + return false; + } + /* ... we can skip it in future, and keep checking the smooth fan. */ + BM_elem_flag_enable(lfan_pivot_next, BM_ELEM_TAG); + } +} + +/** + * BMesh version of BKE_mesh_normals_loop_split() in mesh_evaluate.c + * Will use first clnors_data array, and fallback to cd_loop_clnors_offset + * (use NULL and -1 to not use clnors). + * + * \note This sets #BM_ELEM_TAG which is used in tool code (e.g. T84426). + * we could add a low-level API flag for this, see #BM_ELEM_API_FLAG_ENABLE and friends. + */ +static void bm_mesh_loops_calc_normals(BMesh *bm, + const float (*vcos)[3], + const float (*fnos)[3], + float (*r_lnos)[3], + MLoopNorSpaceArray *r_lnors_spacearr, + const short (*clnors_data)[2], + const int cd_loop_clnors_offset, + const bool do_rebuild) +{ + BMIter fiter; + BMFace *f_curr; + const bool has_clnors = clnors_data || (cd_loop_clnors_offset != -1); + + MLoopNorSpaceArray _lnors_spacearr = {NULL}; + + /* Temp normal stack. */ + BLI_SMALLSTACK_DECLARE(normal, float *); + /* Temp clnors stack. */ + BLI_SMALLSTACK_DECLARE(clnors, short *); + /* Temp edge vectors stack, only used when computing lnor spacearr. */ + BLI_Stack *edge_vectors = NULL; + + { + char htype = 0; + if (vcos) { + htype |= BM_VERT; + } + /* Face/Loop indices are set inline below. */ + BM_mesh_elem_index_ensure(bm, htype); + } + + if (!r_lnors_spacearr && has_clnors) { + /* We need to compute lnor spacearr if some custom lnor data are given to us! */ + r_lnors_spacearr = &_lnors_spacearr; + } + if (r_lnors_spacearr) { + BKE_lnor_spacearr_init(r_lnors_spacearr, bm->totloop, MLNOR_SPACEARR_BMLOOP_PTR); + edge_vectors = BLI_stack_new(sizeof(float[3]), __func__); + } + + /* Clear all loops' tags (means none are to be skipped for now). */ + int index_face, index_loop = 0; + BM_ITER_MESH_INDEX (f_curr, &fiter, bm, BM_FACES_OF_MESH, index_face) { + BMLoop *l_curr, *l_first; + + BM_elem_index_set(f_curr, index_face); /* set_inline */ + + l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr); + do { + BM_elem_index_set(l_curr, index_loop++); /* set_inline */ + BM_elem_flag_disable(l_curr, BM_ELEM_TAG); + } while ((l_curr = l_curr->next) != l_first); + } + bm->elem_index_dirty &= ~(BM_FACE | BM_LOOP); + + /* We now know edges that can be smoothed (they are tagged), + * and edges that will be hard (they aren't). + * Now, time to generate the normals. + */ + BM_ITER_MESH (f_curr, &fiter, bm, BM_FACES_OF_MESH) { + BMLoop *l_curr, *l_first; + + l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr); + do { + if (do_rebuild && !BM_ELEM_API_FLAG_TEST(l_curr, BM_LNORSPACE_UPDATE) && + !(bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL)) { + continue; + } + /* A smooth edge, we have to check for cyclic smooth fan case. + * If we find a new, never-processed cyclic smooth fan, we can do it now using that loop/edge + * as 'entry point', otherwise we can skip it. */ + + /* Note: In theory, we could make bm_mesh_loop_check_cyclic_smooth_fan() store + * mlfan_pivot's in a stack, to avoid having to fan again around + * the vert during actual computation of clnor & clnorspace. However, this would complicate + * the code, add more memory usage, and + * BM_vert_step_fan_loop() is quite cheap in term of CPU cycles, + * so really think it's not worth it. */ + if (BM_elem_flag_test(l_curr->e, BM_ELEM_TAG) && + (BM_elem_flag_test(l_curr, BM_ELEM_TAG) || !BM_loop_check_cyclic_smooth_fan(l_curr))) { + } + else if (!BM_elem_flag_test(l_curr->e, BM_ELEM_TAG) && + !BM_elem_flag_test(l_curr->prev->e, BM_ELEM_TAG)) { + /* Simple case (both edges around that vertex are sharp in related polygon), + * this vertex just takes its poly normal. + */ + const int l_curr_index = BM_elem_index_get(l_curr); + const float *no = fnos ? fnos[BM_elem_index_get(f_curr)] : f_curr->no; + copy_v3_v3(r_lnos[l_curr_index], no); + + /* If needed, generate this (simple!) lnor space. */ + if (r_lnors_spacearr) { + float vec_curr[3], vec_prev[3]; + MLoopNorSpace *lnor_space = BKE_lnor_space_create(r_lnors_spacearr); + + { + const BMVert *v_pivot = l_curr->v; + const float *co_pivot = vcos ? vcos[BM_elem_index_get(v_pivot)] : v_pivot->co; + const BMVert *v_1 = BM_edge_other_vert(l_curr->e, v_pivot); + const float *co_1 = vcos ? vcos[BM_elem_index_get(v_1)] : v_1->co; + const BMVert *v_2 = BM_edge_other_vert(l_curr->prev->e, v_pivot); + const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co; + + sub_v3_v3v3(vec_curr, co_1, co_pivot); + normalize_v3(vec_curr); + sub_v3_v3v3(vec_prev, co_2, co_pivot); + normalize_v3(vec_prev); + } + + BKE_lnor_space_define(lnor_space, r_lnos[l_curr_index], vec_curr, vec_prev, NULL); + /* We know there is only one loop in this space, + * no need to create a linklist in this case... */ + BKE_lnor_space_add_loop(r_lnors_spacearr, lnor_space, l_curr_index, l_curr, true); + + if (has_clnors) { + const short(*clnor)[2] = clnors_data ? &clnors_data[l_curr_index] : + (const void *)BM_ELEM_CD_GET_VOID_P( + l_curr, cd_loop_clnors_offset); + BKE_lnor_space_custom_data_to_normal(lnor_space, *clnor, r_lnos[l_curr_index]); + } + } + } + /* We *do not need* to check/tag loops as already computed! + * Due to the fact a loop only links to one of its two edges, + * a same fan *will never be walked more than once!* + * Since we consider edges having neighbor faces with inverted (flipped) normals as sharp, + * we are sure that no fan will be skipped, even only considering the case + * (sharp curr_edge, smooth prev_edge), and not the alternative + * (smooth curr_edge, sharp prev_edge). + * All this due/thanks to link between normals and loop ordering. + */ + else { + /* We have to fan around current vertex, until we find the other non-smooth edge, + * and accumulate face normals into the vertex! + * Note in case this vertex has only one sharp edge, + * this is a waste because the normal is the same as the vertex normal, + * but I do not see any easy way to detect that (would need to count number of sharp edges + * per vertex, I doubt the additional memory usage would be worth it, especially as it + * should not be a common case in real-life meshes anyway). + */ + BMVert *v_pivot = l_curr->v; + BMEdge *e_next; + const BMEdge *e_org = l_curr->e; + BMLoop *lfan_pivot, *lfan_pivot_next; + int lfan_pivot_index; + float lnor[3] = {0.0f, 0.0f, 0.0f}; + float vec_curr[3], vec_next[3], vec_org[3]; + + /* We validate clnors data on the fly - cheapest way to do! */ + int clnors_avg[2] = {0, 0}; + const short(*clnor_ref)[2] = NULL; + int clnors_nbr = 0; + bool clnors_invalid = false; + + const float *co_pivot = vcos ? vcos[BM_elem_index_get(v_pivot)] : v_pivot->co; + + MLoopNorSpace *lnor_space = r_lnors_spacearr ? BKE_lnor_space_create(r_lnors_spacearr) : + NULL; + + BLI_assert((edge_vectors == NULL) || BLI_stack_is_empty(edge_vectors)); + + lfan_pivot = l_curr; + lfan_pivot_index = BM_elem_index_get(lfan_pivot); + e_next = lfan_pivot->e; /* Current edge here, actually! */ + + /* Only need to compute previous edge's vector once, + * then we can just reuse old current one! */ + { + const BMVert *v_2 = BM_edge_other_vert(e_next, v_pivot); + const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co; + + sub_v3_v3v3(vec_org, co_2, co_pivot); + normalize_v3(vec_org); + copy_v3_v3(vec_curr, vec_org); + + if (r_lnors_spacearr) { + BLI_stack_push(edge_vectors, vec_org); + } + } + + while (true) { + /* Much simpler than in sibling code with basic Mesh data! */ + lfan_pivot_next = BM_vert_step_fan_loop(lfan_pivot, &e_next); + if (lfan_pivot_next) { + BLI_assert(lfan_pivot_next->v == v_pivot); + } + else { + /* next edge is non-manifold, we have to find it ourselves! */ + e_next = (lfan_pivot->e == e_next) ? lfan_pivot->prev->e : lfan_pivot->e; + } + + /* Compute edge vector. + * NOTE: We could pre-compute those into an array, in the first iteration, + * instead of computing them twice (or more) here. + * However, time gained is not worth memory and time lost, + * given the fact that this code should not be called that much in real-life meshes. + */ + { + const BMVert *v_2 = BM_edge_other_vert(e_next, v_pivot); + const float *co_2 = vcos ? vcos[BM_elem_index_get(v_2)] : v_2->co; + + sub_v3_v3v3(vec_next, co_2, co_pivot); + normalize_v3(vec_next); + } + + { + /* Code similar to accumulate_vertex_normals_poly_v3. */ + /* Calculate angle between the two poly edges incident on this vertex. */ + const BMFace *f = lfan_pivot->f; + const float fac = saacos(dot_v3v3(vec_next, vec_curr)); + const float *no = fnos ? fnos[BM_elem_index_get(f)] : f->no; + /* Accumulate */ + madd_v3_v3fl(lnor, no, fac); + + if (has_clnors) { + /* Accumulate all clnors, if they are not all equal we have to fix that! */ + const short(*clnor)[2] = clnors_data ? &clnors_data[lfan_pivot_index] : + (const void *)BM_ELEM_CD_GET_VOID_P( + lfan_pivot, cd_loop_clnors_offset); + if (clnors_nbr) { + clnors_invalid |= ((*clnor_ref)[0] != (*clnor)[0] || + (*clnor_ref)[1] != (*clnor)[1]); + } + else { + clnor_ref = clnor; + } + clnors_avg[0] += (*clnor)[0]; + clnors_avg[1] += (*clnor)[1]; + clnors_nbr++; + /* We store here a pointer to all custom lnors processed. */ + BLI_SMALLSTACK_PUSH(clnors, (short *)*clnor); + } + } + + /* We store here a pointer to all loop-normals processed. */ + BLI_SMALLSTACK_PUSH(normal, (float *)r_lnos[lfan_pivot_index]); + + if (r_lnors_spacearr) { + /* Assign current lnor space to current 'vertex' loop. */ + BKE_lnor_space_add_loop( + r_lnors_spacearr, lnor_space, lfan_pivot_index, lfan_pivot, false); + if (e_next != e_org) { + /* We store here all edges-normalized vectors processed. */ + BLI_stack_push(edge_vectors, vec_next); + } + } + + if (!BM_elem_flag_test(e_next, BM_ELEM_TAG) || (e_next == e_org)) { + /* Next edge is sharp, we have finished with this fan of faces around this vert! */ + break; + } + + /* Copy next edge vector to current one. */ + copy_v3_v3(vec_curr, vec_next); + /* Next pivot loop to current one. */ + lfan_pivot = lfan_pivot_next; + lfan_pivot_index = BM_elem_index_get(lfan_pivot); + } + + { + float lnor_len = normalize_v3(lnor); + + /* If we are generating lnor spacearr, we can now define the one for this fan. */ + if (r_lnors_spacearr) { + if (UNLIKELY(lnor_len == 0.0f)) { + /* Use vertex normal as fallback! */ + copy_v3_v3(lnor, r_lnos[lfan_pivot_index]); + lnor_len = 1.0f; + } + + BKE_lnor_space_define(lnor_space, lnor, vec_org, vec_next, edge_vectors); + + if (has_clnors) { + if (clnors_invalid) { + short *clnor; + + clnors_avg[0] /= clnors_nbr; + clnors_avg[1] /= clnors_nbr; + /* Fix/update all clnors of this fan with computed average value. */ + + /* Prints continuously when merge custom normals, so commenting. */ + /* printf("Invalid clnors in this fan!\n"); */ + + while ((clnor = BLI_SMALLSTACK_POP(clnors))) { + // print_v2("org clnor", clnor); + clnor[0] = (short)clnors_avg[0]; + clnor[1] = (short)clnors_avg[1]; + } + // print_v2("new clnors", clnors_avg); + } + else { + /* We still have to consume the stack! */ + while (BLI_SMALLSTACK_POP(clnors)) { + /* pass */ + } + } + BKE_lnor_space_custom_data_to_normal(lnor_space, *clnor_ref, lnor); + } + } + + /* In case we get a zero normal here, just use vertex normal already set! */ + if (LIKELY(lnor_len != 0.0f)) { + /* Copy back the final computed normal into all related loop-normals. */ + float *nor; + + while ((nor = BLI_SMALLSTACK_POP(normal))) { + copy_v3_v3(nor, lnor); + } + } + else { + /* We still have to consume the stack! */ + while (BLI_SMALLSTACK_POP(normal)) { + /* pass */ + } + } + } + + /* Tag related vertex as sharp, to avoid fanning around it again + * (in case it was a smooth one). */ + if (r_lnors_spacearr) { + BM_elem_flag_enable(l_curr->v, BM_ELEM_TAG); + } + } + } while ((l_curr = l_curr->next) != l_first); + } + + if (r_lnors_spacearr) { + BLI_stack_free(edge_vectors); + if (r_lnors_spacearr == &_lnors_spacearr) { + BKE_lnor_spacearr_free(r_lnors_spacearr); + } + } +} + +/* This threshold is a bit touchy (usual float precision issue), this value seems OK. */ +#define LNOR_SPACE_TRIGO_THRESHOLD (1.0f - 1e-4f) + +/** + * Check each current smooth fan (one lnor space per smooth fan!), and if all its + * matching custom lnors are not (enough) equal, add sharp edges as needed. + */ +static bool bm_mesh_loops_split_lnor_fans(BMesh *bm, + MLoopNorSpaceArray *lnors_spacearr, + const float (*new_lnors)[3]) +{ + BLI_bitmap *done_loops = BLI_BITMAP_NEW((size_t)bm->totloop, __func__); + bool changed = false; + + BLI_assert(lnors_spacearr->data_type == MLNOR_SPACEARR_BMLOOP_PTR); + + for (int i = 0; i < bm->totloop; i++) { + if (!lnors_spacearr->lspacearr[i]) { + /* This should not happen in theory, but in some rare case (probably ugly geometry) + * we can get some NULL loopspacearr at this point. :/ + * Maybe we should set those loops' edges as sharp? + */ + BLI_BITMAP_ENABLE(done_loops, i); + if (G.debug & G_DEBUG) { + printf("WARNING! Getting invalid NULL loop space for loop %d!\n", i); + } + continue; + } + + if (!BLI_BITMAP_TEST(done_loops, i)) { + /* Notes: + * * In case of mono-loop smooth fan, we have nothing to do. + * * Loops in this linklist are ordered (in reversed order compared to how they were + * discovered by BKE_mesh_normals_loop_split(), but this is not a problem). + * Which means if we find a mismatching clnor, + * we know all remaining loops will have to be in a new, different smooth fan/lnor space. + * * In smooth fan case, we compare each clnor against a ref one, + * to avoid small differences adding up into a real big one in the end! + */ + if (lnors_spacearr->lspacearr[i]->flags & MLNOR_SPACE_IS_SINGLE) { + BLI_BITMAP_ENABLE(done_loops, i); + continue; + } + + LinkNode *loops = lnors_spacearr->lspacearr[i]->loops; + BMLoop *prev_ml = NULL; + const float *org_nor = NULL; + + while (loops) { + BMLoop *ml = loops->link; + const int lidx = BM_elem_index_get(ml); + const float *nor = new_lnors[lidx]; + + if (!org_nor) { + org_nor = nor; + } + else if (dot_v3v3(org_nor, nor) < LNOR_SPACE_TRIGO_THRESHOLD) { + /* Current normal differs too much from org one, we have to tag the edge between + * previous loop's face and current's one as sharp. + * We know those two loops do not point to the same edge, + * since we do not allow reversed winding in a same smooth fan. + */ + BMEdge *e = (prev_ml->e == ml->prev->e) ? prev_ml->e : ml->e; + + BM_elem_flag_disable(e, BM_ELEM_TAG | BM_ELEM_SMOOTH); + changed = true; + + org_nor = nor; + } + + prev_ml = ml; + loops = loops->next; + BLI_BITMAP_ENABLE(done_loops, lidx); + } + + /* We also have to check between last and first loops, + * otherwise we may miss some sharp edges here! + * This is just a simplified version of above while loop. + * See T45984. */ + loops = lnors_spacearr->lspacearr[i]->loops; + if (loops && org_nor) { + BMLoop *ml = loops->link; + const int lidx = BM_elem_index_get(ml); + const float *nor = new_lnors[lidx]; + + if (dot_v3v3(org_nor, nor) < LNOR_SPACE_TRIGO_THRESHOLD) { + BMEdge *e = (prev_ml->e == ml->prev->e) ? prev_ml->e : ml->e; + + BM_elem_flag_disable(e, BM_ELEM_TAG | BM_ELEM_SMOOTH); + changed = true; + } + } + } + } + + MEM_freeN(done_loops); + return changed; +} + +/** + * Assign custom normal data from given normal vectors, averaging normals + * from one smooth fan as necessary. + */ +static void bm_mesh_loops_assign_normal_data(BMesh *bm, + MLoopNorSpaceArray *lnors_spacearr, + short (*r_clnors_data)[2], + const int cd_loop_clnors_offset, + const float (*new_lnors)[3]) +{ + BLI_bitmap *done_loops = BLI_BITMAP_NEW((size_t)bm->totloop, __func__); + + BLI_SMALLSTACK_DECLARE(clnors_data, short *); + + BLI_assert(lnors_spacearr->data_type == MLNOR_SPACEARR_BMLOOP_PTR); + + for (int i = 0; i < bm->totloop; i++) { + if (!lnors_spacearr->lspacearr[i]) { + BLI_BITMAP_ENABLE(done_loops, i); + if (G.debug & G_DEBUG) { + printf("WARNING! Still getting invalid NULL loop space in second loop for loop %d!\n", i); + } + continue; + } + + if (!BLI_BITMAP_TEST(done_loops, i)) { + /* Note we accumulate and average all custom normals in current smooth fan, + * to avoid getting different clnors data (tiny differences in plain custom normals can + * give rather huge differences in computed 2D factors). + */ + LinkNode *loops = lnors_spacearr->lspacearr[i]->loops; + + if (lnors_spacearr->lspacearr[i]->flags & MLNOR_SPACE_IS_SINGLE) { + BMLoop *ml = (BMLoop *)loops; + const int lidx = BM_elem_index_get(ml); + + BLI_assert(lidx == i); + + const float *nor = new_lnors[lidx]; + short *clnor = r_clnors_data ? &r_clnors_data[lidx] : + BM_ELEM_CD_GET_VOID_P(ml, cd_loop_clnors_offset); + + BKE_lnor_space_custom_normal_to_data(lnors_spacearr->lspacearr[i], nor, clnor); + BLI_BITMAP_ENABLE(done_loops, i); + } + else { + int nbr_nors = 0; + float avg_nor[3]; + short clnor_data_tmp[2], *clnor_data; + + zero_v3(avg_nor); + + while (loops) { + BMLoop *ml = loops->link; + const int lidx = BM_elem_index_get(ml); + const float *nor = new_lnors[lidx]; + short *clnor = r_clnors_data ? &r_clnors_data[lidx] : + BM_ELEM_CD_GET_VOID_P(ml, cd_loop_clnors_offset); + + nbr_nors++; + add_v3_v3(avg_nor, nor); + BLI_SMALLSTACK_PUSH(clnors_data, clnor); + + loops = loops->next; + BLI_BITMAP_ENABLE(done_loops, lidx); + } + + mul_v3_fl(avg_nor, 1.0f / (float)nbr_nors); + BKE_lnor_space_custom_normal_to_data( + lnors_spacearr->lspacearr[i], avg_nor, clnor_data_tmp); + + while ((clnor_data = BLI_SMALLSTACK_POP(clnors_data))) { + clnor_data[0] = clnor_data_tmp[0]; + clnor_data[1] = clnor_data_tmp[1]; + } + } + } + } + + MEM_freeN(done_loops); +} + +/** + * Compute internal representation of given custom normals (as an array of float[2] or data layer). + * + * It also makes sure the mesh matches those custom normals, by marking new sharp edges to split + * the smooth fans when loop normals for the same vertex are different, or averaging the normals + * instead, depending on the do_split_fans parameter. + */ +static void bm_mesh_loops_custom_normals_set(BMesh *bm, + const float (*vcos)[3], + const float (*vnos)[3], + const float (*fnos)[3], + MLoopNorSpaceArray *r_lnors_spacearr, + short (*r_clnors_data)[2], + const int cd_loop_clnors_offset, + float (*new_lnors)[3], + const int cd_new_lnors_offset, + bool do_split_fans) +{ + BMFace *f; + BMLoop *l; + BMIter liter, fiter; + float(*cur_lnors)[3] = MEM_mallocN(sizeof(*cur_lnors) * bm->totloop, __func__); + + BKE_lnor_spacearr_clear(r_lnors_spacearr); + + /* Tag smooth edges and set lnos from vnos when they might be completely smooth... + * When using custom loop normals, disable the angle feature! */ + bm_mesh_edges_sharp_tag(bm, vnos, fnos, cur_lnors, (float)M_PI, false); + + /* Finish computing lnos by accumulating face normals + * in each fan of faces defined by sharp edges. */ + bm_mesh_loops_calc_normals( + bm, vcos, fnos, cur_lnors, r_lnors_spacearr, r_clnors_data, cd_loop_clnors_offset, false); + + /* Extract new normals from the data layer if necessary. */ + float(*custom_lnors)[3] = new_lnors; + + if (new_lnors == NULL) { + custom_lnors = MEM_mallocN(sizeof(*new_lnors) * bm->totloop, __func__); + + BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { + BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { + const float *normal = BM_ELEM_CD_GET_VOID_P(l, cd_new_lnors_offset); + copy_v3_v3(custom_lnors[BM_elem_index_get(l)], normal); + } + } + } + + /* Validate the new normals. */ + for (int i = 0; i < bm->totloop; i++) { + if (is_zero_v3(custom_lnors[i])) { + copy_v3_v3(custom_lnors[i], cur_lnors[i]); + } + else { + normalize_v3(custom_lnors[i]); + } + } + + /* Now, check each current smooth fan (one lnor space per smooth fan!), + * and if all its matching custom lnors are not equal, add sharp edges as needed. */ + if (do_split_fans && bm_mesh_loops_split_lnor_fans(bm, r_lnors_spacearr, custom_lnors)) { + /* If any sharp edges were added, run bm_mesh_loops_calc_normals() again to get lnor + * spacearr/smooth fans matching the given custom lnors. */ + BKE_lnor_spacearr_clear(r_lnors_spacearr); + + bm_mesh_loops_calc_normals( + bm, vcos, fnos, cur_lnors, r_lnors_spacearr, r_clnors_data, cd_loop_clnors_offset, false); + } + + /* And we just have to convert plain object-space custom normals to our + * lnor space-encoded ones. */ + bm_mesh_loops_assign_normal_data( + bm, r_lnors_spacearr, r_clnors_data, cd_loop_clnors_offset, custom_lnors); + + MEM_freeN(cur_lnors); + + if (custom_lnors != new_lnors) { + MEM_freeN(custom_lnors); + } +} + +static void bm_mesh_loops_calc_normals_no_autosmooth(BMesh *bm, + const float (*vnos)[3], + const float (*fnos)[3], + float (*r_lnos)[3]) +{ + BMIter fiter; + BMFace *f_curr; + + { + char htype = BM_LOOP; + if (vnos) { + htype |= BM_VERT; + } + if (fnos) { + htype |= BM_FACE; + } + BM_mesh_elem_index_ensure(bm, htype); + } + + BM_ITER_MESH (f_curr, &fiter, bm, BM_FACES_OF_MESH) { + BMLoop *l_curr, *l_first; + const bool is_face_flat = !BM_elem_flag_test(f_curr, BM_ELEM_SMOOTH); + + l_curr = l_first = BM_FACE_FIRST_LOOP(f_curr); + do { + const float *no = is_face_flat ? (fnos ? fnos[BM_elem_index_get(f_curr)] : f_curr->no) : + (vnos ? vnos[BM_elem_index_get(l_curr->v)] : l_curr->v->no); + copy_v3_v3(r_lnos[BM_elem_index_get(l_curr)], no); + + } while ((l_curr = l_curr->next) != l_first); + } +} + +#if 0 /* Unused currently */ +/** + * \brief BMesh Compute Loop Normals + * + * Updates the loop normals of a mesh. + * Assumes vertex and face normals are valid (else call BM_mesh_normals_update() first)! + */ +void BM_mesh_loop_normals_update(BMesh *bm, + const bool use_split_normals, + const float split_angle, + float (*r_lnos)[3], + MLoopNorSpaceArray *r_lnors_spacearr, + const short (*clnors_data)[2], + const int cd_loop_clnors_offset) +{ + const bool has_clnors = clnors_data || (cd_loop_clnors_offset != -1); + + if (use_split_normals) { + /* Tag smooth edges and set lnos from vnos when they might be completely smooth... + * When using custom loop normals, disable the angle feature! */ + bm_mesh_edges_sharp_tag(bm, NULL, NULL, has_clnors ? (float)M_PI : split_angle, r_lnos); + + /* Finish computing lnos by accumulating face normals + * in each fan of faces defined by sharp edges. */ + bm_mesh_loops_calc_normals( + bm, NULL, NULL, r_lnos, r_lnors_spacearr, clnors_data, cd_loop_clnors_offset); + } + else { + BLI_assert(!r_lnors_spacearr); + bm_mesh_loops_calc_normals_no_autosmooth(bm, NULL, NULL, r_lnos); + } +} +#endif + +/** + * \brief BMesh Compute Loop Normals from/to external data. + * + * Compute split normals, i.e. vertex normals associated with each poly (hence 'loop normals'). + * Useful to materialize sharp edges (or non-smooth faces) without actually modifying the geometry + * (splitting edges). + */ +void BM_loops_calc_normal_vcos(BMesh *bm, + const float (*vcos)[3], + const float (*vnos)[3], + const float (*fnos)[3], + const bool use_split_normals, + const float split_angle, + float (*r_lnos)[3], + MLoopNorSpaceArray *r_lnors_spacearr, + short (*clnors_data)[2], + const int cd_loop_clnors_offset, + const bool do_rebuild) +{ + const bool has_clnors = clnors_data || (cd_loop_clnors_offset != -1); + + if (use_split_normals) { + /* Tag smooth edges and set lnos from vnos when they might be completely smooth... + * When using custom loop normals, disable the angle feature! */ + bm_mesh_edges_sharp_tag(bm, vnos, fnos, r_lnos, has_clnors ? (float)M_PI : split_angle, false); + + /* Finish computing lnos by accumulating face normals + * in each fan of faces defined by sharp edges. */ + bm_mesh_loops_calc_normals( + bm, vcos, fnos, r_lnos, r_lnors_spacearr, clnors_data, cd_loop_clnors_offset, do_rebuild); + } + else { + BLI_assert(!r_lnors_spacearr); + bm_mesh_loops_calc_normals_no_autosmooth(bm, vnos, fnos, r_lnos); + } +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Loop Normal Space API + * \{ */ + +void BM_lnorspacearr_store(BMesh *bm, float (*r_lnors)[3]) +{ + BLI_assert(bm->lnor_spacearr != NULL); + + if (!CustomData_has_layer(&bm->ldata, CD_CUSTOMLOOPNORMAL)) { + BM_data_layer_add(bm, &bm->ldata, CD_CUSTOMLOOPNORMAL); + } + + int cd_loop_clnors_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL); + + BM_loops_calc_normal_vcos(bm, + NULL, + NULL, + NULL, + true, + M_PI, + r_lnors, + bm->lnor_spacearr, + NULL, + cd_loop_clnors_offset, + false); + bm->spacearr_dirty &= ~(BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL); +} + +#define CLEAR_SPACEARRAY_THRESHOLD(x) ((x) / 2) + +void BM_lnorspace_invalidate(BMesh *bm, const bool do_invalidate_all) +{ + if (bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL) { + return; + } + if (do_invalidate_all || bm->totvertsel > CLEAR_SPACEARRAY_THRESHOLD(bm->totvert)) { + bm->spacearr_dirty |= BM_SPACEARR_DIRTY_ALL; + return; + } + if (bm->lnor_spacearr == NULL) { + bm->spacearr_dirty |= BM_SPACEARR_DIRTY_ALL; + return; + } + + BMVert *v; + BMLoop *l; + BMIter viter, liter; + /* Note: we could use temp tag of BMItem for that, + * but probably better not use it in such a low-level func? + * --mont29 */ + BLI_bitmap *done_verts = BLI_BITMAP_NEW(bm->totvert, __func__); + + BM_mesh_elem_index_ensure(bm, BM_VERT); + + /* When we affect a given vertex, we may affect following smooth fans: + * - all smooth fans of said vertex; + * - all smooth fans of all immediate loop-neighbors vertices; + * This can be simplified as 'all loops of selected vertices and their immediate neighbors' + * need to be tagged for update. + */ + BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) { + if (BM_elem_flag_test(v, BM_ELEM_SELECT)) { + BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) { + BM_ELEM_API_FLAG_ENABLE(l, BM_LNORSPACE_UPDATE); + + /* Note that we only handle unselected neighbor vertices here, main loop will take care of + * selected ones. */ + if ((!BM_elem_flag_test(l->prev->v, BM_ELEM_SELECT)) && + !BLI_BITMAP_TEST(done_verts, BM_elem_index_get(l->prev->v))) { + + BMLoop *l_prev; + BMIter liter_prev; + BM_ITER_ELEM (l_prev, &liter_prev, l->prev->v, BM_LOOPS_OF_VERT) { + BM_ELEM_API_FLAG_ENABLE(l_prev, BM_LNORSPACE_UPDATE); + } + BLI_BITMAP_ENABLE(done_verts, BM_elem_index_get(l_prev->v)); + } + + if ((!BM_elem_flag_test(l->next->v, BM_ELEM_SELECT)) && + !BLI_BITMAP_TEST(done_verts, BM_elem_index_get(l->next->v))) { + + BMLoop *l_next; + BMIter liter_next; + BM_ITER_ELEM (l_next, &liter_next, l->next->v, BM_LOOPS_OF_VERT) { + BM_ELEM_API_FLAG_ENABLE(l_next, BM_LNORSPACE_UPDATE); + } + BLI_BITMAP_ENABLE(done_verts, BM_elem_index_get(l_next->v)); + } + } + + BLI_BITMAP_ENABLE(done_verts, BM_elem_index_get(v)); + } + } + + MEM_freeN(done_verts); + bm->spacearr_dirty |= BM_SPACEARR_DIRTY; +} + +void BM_lnorspace_rebuild(BMesh *bm, bool preserve_clnor) +{ + BLI_assert(bm->lnor_spacearr != NULL); + + if (!(bm->spacearr_dirty & (BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL))) { + return; + } + BMFace *f; + BMLoop *l; + BMIter fiter, liter; + + float(*r_lnors)[3] = MEM_callocN(sizeof(*r_lnors) * bm->totloop, __func__); + float(*oldnors)[3] = preserve_clnor ? MEM_mallocN(sizeof(*oldnors) * bm->totloop, __func__) : + NULL; + + int cd_loop_clnors_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL); + + BM_mesh_elem_index_ensure(bm, BM_LOOP); + + if (preserve_clnor) { + BLI_assert(bm->lnor_spacearr->lspacearr != NULL); + + BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { + BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { + if (BM_ELEM_API_FLAG_TEST(l, BM_LNORSPACE_UPDATE) || + bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL) { + short(*clnor)[2] = BM_ELEM_CD_GET_VOID_P(l, cd_loop_clnors_offset); + int l_index = BM_elem_index_get(l); + + BKE_lnor_space_custom_data_to_normal( + bm->lnor_spacearr->lspacearr[l_index], *clnor, oldnors[l_index]); + } + } + } + } + + if (bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL) { + BKE_lnor_spacearr_clear(bm->lnor_spacearr); + } + BM_loops_calc_normal_vcos(bm, + NULL, + NULL, + NULL, + true, + M_PI, + r_lnors, + bm->lnor_spacearr, + NULL, + cd_loop_clnors_offset, + true); + MEM_freeN(r_lnors); + + BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { + BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { + if (BM_ELEM_API_FLAG_TEST(l, BM_LNORSPACE_UPDATE) || + bm->spacearr_dirty & BM_SPACEARR_DIRTY_ALL) { + if (preserve_clnor) { + short(*clnor)[2] = BM_ELEM_CD_GET_VOID_P(l, cd_loop_clnors_offset); + int l_index = BM_elem_index_get(l); + BKE_lnor_space_custom_normal_to_data( + bm->lnor_spacearr->lspacearr[l_index], oldnors[l_index], *clnor); + } + BM_ELEM_API_FLAG_DISABLE(l, BM_LNORSPACE_UPDATE); + } + } + } + + MEM_SAFE_FREE(oldnors); + bm->spacearr_dirty &= ~(BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL); + +#ifndef NDEBUG + BM_lnorspace_err(bm); +#endif +} + +/** + * \warning This function sets #BM_ELEM_TAG on loops & edges via #bm_mesh_loops_calc_normals, + * take care to run this before setting up tags. + */ +void BM_lnorspace_update(BMesh *bm) +{ + if (bm->lnor_spacearr == NULL) { + bm->lnor_spacearr = MEM_callocN(sizeof(*bm->lnor_spacearr), __func__); + } + if (bm->lnor_spacearr->lspacearr == NULL) { + float(*lnors)[3] = MEM_callocN(sizeof(*lnors) * bm->totloop, __func__); + + BM_lnorspacearr_store(bm, lnors); + + MEM_freeN(lnors); + } + else if (bm->spacearr_dirty & (BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL)) { + BM_lnorspace_rebuild(bm, false); + } +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Loop Normal Edit Data Array API + * + * Utilities for creating/freeing #BMLoopNorEditDataArray. + * \{ */ + +/** + * Auxiliary function only used by rebuild to detect if any spaces were not marked as invalid. + * Reports error if any of the lnor spaces change after rebuilding, meaning that all the possible + * lnor spaces to be rebuilt were not correctly marked. + */ +#ifndef NDEBUG +void BM_lnorspace_err(BMesh *bm) +{ + bm->spacearr_dirty |= BM_SPACEARR_DIRTY_ALL; + bool clear = true; + + MLoopNorSpaceArray *temp = MEM_callocN(sizeof(*temp), __func__); + temp->lspacearr = NULL; + + BKE_lnor_spacearr_init(temp, bm->totloop, MLNOR_SPACEARR_BMLOOP_PTR); + + int cd_loop_clnors_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL); + float(*lnors)[3] = MEM_callocN(sizeof(*lnors) * bm->totloop, __func__); + BM_loops_calc_normal_vcos( + bm, NULL, NULL, NULL, true, M_PI, lnors, temp, NULL, cd_loop_clnors_offset, true); + + for (int i = 0; i < bm->totloop; i++) { + int j = 0; + j += compare_ff( + temp->lspacearr[i]->ref_alpha, bm->lnor_spacearr->lspacearr[i]->ref_alpha, 1e-4f); + j += compare_ff( + temp->lspacearr[i]->ref_beta, bm->lnor_spacearr->lspacearr[i]->ref_beta, 1e-4f); + j += compare_v3v3( + temp->lspacearr[i]->vec_lnor, bm->lnor_spacearr->lspacearr[i]->vec_lnor, 1e-4f); + j += compare_v3v3( + temp->lspacearr[i]->vec_ortho, bm->lnor_spacearr->lspacearr[i]->vec_ortho, 1e-4f); + j += compare_v3v3( + temp->lspacearr[i]->vec_ref, bm->lnor_spacearr->lspacearr[i]->vec_ref, 1e-4f); + + if (j != 5) { + clear = false; + break; + } + } + BKE_lnor_spacearr_free(temp); + MEM_freeN(temp); + MEM_freeN(lnors); + BLI_assert(clear); + + bm->spacearr_dirty &= ~BM_SPACEARR_DIRTY_ALL; +} +#endif + +static void bm_loop_normal_mark_indiv_do_loop(BMLoop *l, + BLI_bitmap *loops, + MLoopNorSpaceArray *lnor_spacearr, + int *totloopsel, + const bool do_all_loops_of_vert) +{ + if (l != NULL) { + const int l_idx = BM_elem_index_get(l); + + if (!BLI_BITMAP_TEST(loops, l_idx)) { + /* If vert and face selected share a loop, mark it for editing. */ + BLI_BITMAP_ENABLE(loops, l_idx); + (*totloopsel)++; + + if (do_all_loops_of_vert) { + /* If required, also mark all loops shared by that vertex. + * This is needed when loop spaces may change + * (i.e. when some faces or edges might change of smooth/sharp status). */ + BMIter liter; + BMLoop *lfan; + BM_ITER_ELEM (lfan, &liter, l->v, BM_LOOPS_OF_VERT) { + const int lfan_idx = BM_elem_index_get(lfan); + if (!BLI_BITMAP_TEST(loops, lfan_idx)) { + BLI_BITMAP_ENABLE(loops, lfan_idx); + (*totloopsel)++; + } + } + } + else { + /* Mark all loops in same loop normal space (aka smooth fan). */ + if ((lnor_spacearr->lspacearr[l_idx]->flags & MLNOR_SPACE_IS_SINGLE) == 0) { + for (LinkNode *node = lnor_spacearr->lspacearr[l_idx]->loops; node; node = node->next) { + const int lfan_idx = BM_elem_index_get((BMLoop *)node->link); + if (!BLI_BITMAP_TEST(loops, lfan_idx)) { + BLI_BITMAP_ENABLE(loops, lfan_idx); + (*totloopsel)++; + } + } + } + } + } + } +} + +/* Mark the individual clnors to be edited, if multiple selection methods are used. */ +static int bm_loop_normal_mark_indiv(BMesh *bm, BLI_bitmap *loops, const bool do_all_loops_of_vert) +{ + BMEditSelection *ese, *ese_prev; + int totloopsel = 0; + + const bool sel_verts = (bm->selectmode & SCE_SELECT_VERTEX) != 0; + const bool sel_edges = (bm->selectmode & SCE_SELECT_EDGE) != 0; + const bool sel_faces = (bm->selectmode & SCE_SELECT_FACE) != 0; + const bool use_sel_face_history = sel_faces && (sel_edges || sel_verts); + + BM_mesh_elem_index_ensure(bm, BM_LOOP); + + BLI_assert(bm->lnor_spacearr != NULL); + BLI_assert(bm->lnor_spacearr->data_type == MLNOR_SPACEARR_BMLOOP_PTR); + + if (use_sel_face_history) { + /* Using face history allows to select a single loop from a single face... + * Note that this is O(n^2) piece of code, + * but it is not designed to be used with huge selection sets, + * rather with only a few items selected at most.*/ + /* Goes from last selected to the first selected element. */ + for (ese = bm->selected.last; ese; ese = ese->prev) { + if (ese->htype == BM_FACE) { + /* If current face is selected, + * then any verts to be edited must have been selected before it. */ + for (ese_prev = ese->prev; ese_prev; ese_prev = ese_prev->prev) { + if (ese_prev->htype == BM_VERT) { + bm_loop_normal_mark_indiv_do_loop( + BM_face_vert_share_loop((BMFace *)ese->ele, (BMVert *)ese_prev->ele), + loops, + bm->lnor_spacearr, + &totloopsel, + do_all_loops_of_vert); + } + else if (ese_prev->htype == BM_EDGE) { + BMEdge *e = (BMEdge *)ese_prev->ele; + bm_loop_normal_mark_indiv_do_loop(BM_face_vert_share_loop((BMFace *)ese->ele, e->v1), + loops, + bm->lnor_spacearr, + &totloopsel, + do_all_loops_of_vert); + + bm_loop_normal_mark_indiv_do_loop(BM_face_vert_share_loop((BMFace *)ese->ele, e->v2), + loops, + bm->lnor_spacearr, + &totloopsel, + do_all_loops_of_vert); + } + } + } + } + } + else { + if (sel_faces) { + /* Only select all loops of selected faces. */ + BMLoop *l; + BMFace *f; + BMIter liter, fiter; + BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { + if (BM_elem_flag_test(f, BM_ELEM_SELECT)) { + BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { + bm_loop_normal_mark_indiv_do_loop( + l, loops, bm->lnor_spacearr, &totloopsel, do_all_loops_of_vert); + } + } + } + } + if (sel_edges) { + /* Only select all loops of selected edges. */ + BMLoop *l; + BMEdge *e; + BMIter liter, eiter; + BM_ITER_MESH (e, &eiter, bm, BM_EDGES_OF_MESH) { + if (BM_elem_flag_test(e, BM_ELEM_SELECT)) { + BM_ITER_ELEM (l, &liter, e, BM_LOOPS_OF_EDGE) { + bm_loop_normal_mark_indiv_do_loop( + l, loops, bm->lnor_spacearr, &totloopsel, do_all_loops_of_vert); + /* Loops actually 'have' two edges, or said otherwise, a selected edge actually selects + * *two* loops in each of its faces. We have to find the other one too. */ + if (BM_vert_in_edge(e, l->next->v)) { + bm_loop_normal_mark_indiv_do_loop( + l->next, loops, bm->lnor_spacearr, &totloopsel, do_all_loops_of_vert); + } + else { + BLI_assert(BM_vert_in_edge(e, l->prev->v)); + bm_loop_normal_mark_indiv_do_loop( + l->prev, loops, bm->lnor_spacearr, &totloopsel, do_all_loops_of_vert); + } + } + } + } + } + if (sel_verts) { + /* Select all loops of selected verts. */ + BMLoop *l; + BMVert *v; + BMIter liter, viter; + BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) { + if (BM_elem_flag_test(v, BM_ELEM_SELECT)) { + BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) { + bm_loop_normal_mark_indiv_do_loop( + l, loops, bm->lnor_spacearr, &totloopsel, do_all_loops_of_vert); + } + } + } + } + } + + return totloopsel; +} + +static void loop_normal_editdata_init( + BMesh *bm, BMLoopNorEditData *lnor_ed, BMVert *v, BMLoop *l, const int offset) +{ + BLI_assert(bm->lnor_spacearr != NULL); + BLI_assert(bm->lnor_spacearr->lspacearr != NULL); + + const int l_index = BM_elem_index_get(l); + short *clnors_data = BM_ELEM_CD_GET_VOID_P(l, offset); + + lnor_ed->loop_index = l_index; + lnor_ed->loop = l; + + float custom_normal[3]; + BKE_lnor_space_custom_data_to_normal( + bm->lnor_spacearr->lspacearr[l_index], clnors_data, custom_normal); + + lnor_ed->clnors_data = clnors_data; + copy_v3_v3(lnor_ed->nloc, custom_normal); + copy_v3_v3(lnor_ed->niloc, custom_normal); + + lnor_ed->loc = v->co; +} + +BMLoopNorEditDataArray *BM_loop_normal_editdata_array_init(BMesh *bm, + const bool do_all_loops_of_vert) +{ + BMLoop *l; + BMVert *v; + BMIter liter, viter; + + int totloopsel = 0; + + BLI_assert(bm->spacearr_dirty == 0); + + BMLoopNorEditDataArray *lnors_ed_arr = MEM_callocN(sizeof(*lnors_ed_arr), __func__); + lnors_ed_arr->lidx_to_lnor_editdata = MEM_callocN( + sizeof(*lnors_ed_arr->lidx_to_lnor_editdata) * bm->totloop, __func__); + + if (!CustomData_has_layer(&bm->ldata, CD_CUSTOMLOOPNORMAL)) { + BM_data_layer_add(bm, &bm->ldata, CD_CUSTOMLOOPNORMAL); + } + const int cd_custom_normal_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL); + + BM_mesh_elem_index_ensure(bm, BM_LOOP); + + BLI_bitmap *loops = BLI_BITMAP_NEW(bm->totloop, __func__); + + /* This function define loop normals to edit, based on selection modes and history. */ + totloopsel = bm_loop_normal_mark_indiv(bm, loops, do_all_loops_of_vert); + + if (totloopsel) { + BMLoopNorEditData *lnor_ed = lnors_ed_arr->lnor_editdata = MEM_mallocN( + sizeof(*lnor_ed) * totloopsel, __func__); + + BM_ITER_MESH (v, &viter, bm, BM_VERTS_OF_MESH) { + BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) { + if (BLI_BITMAP_TEST(loops, BM_elem_index_get(l))) { + loop_normal_editdata_init(bm, lnor_ed, v, l, cd_custom_normal_offset); + lnors_ed_arr->lidx_to_lnor_editdata[BM_elem_index_get(l)] = lnor_ed; + lnor_ed++; + } + } + } + lnors_ed_arr->totloop = totloopsel; + } + + MEM_freeN(loops); + lnors_ed_arr->cd_custom_normal_offset = cd_custom_normal_offset; + return lnors_ed_arr; +} + +void BM_loop_normal_editdata_array_free(BMLoopNorEditDataArray *lnors_ed_arr) +{ + MEM_SAFE_FREE(lnors_ed_arr->lnor_editdata); + MEM_SAFE_FREE(lnors_ed_arr->lidx_to_lnor_editdata); + MEM_freeN(lnors_ed_arr); +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Custom Normals / Vector Layer Conversion + * \{ */ + +/** + * \warning This function sets #BM_ELEM_TAG on loops & edges via #bm_mesh_loops_calc_normals, + * take care to run this before setting up tags. + */ +bool BM_custom_loop_normals_to_vector_layer(BMesh *bm) +{ + BMFace *f; + BMLoop *l; + BMIter liter, fiter; + + if (!CustomData_has_layer(&bm->ldata, CD_CUSTOMLOOPNORMAL)) { + return false; + } + + BM_lnorspace_update(bm); + BM_mesh_elem_index_ensure(bm, BM_LOOP); + + /* Create a loop normal layer. */ + if (!CustomData_has_layer(&bm->ldata, CD_NORMAL)) { + BM_data_layer_add(bm, &bm->ldata, CD_NORMAL); + + CustomData_set_layer_flag(&bm->ldata, CD_NORMAL, CD_FLAG_TEMPORARY); + } + + const int cd_custom_normal_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL); + const int cd_normal_offset = CustomData_get_offset(&bm->ldata, CD_NORMAL); + + BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { + BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) { + const int l_index = BM_elem_index_get(l); + const short *clnors_data = BM_ELEM_CD_GET_VOID_P(l, cd_custom_normal_offset); + float *normal = BM_ELEM_CD_GET_VOID_P(l, cd_normal_offset); + + BKE_lnor_space_custom_data_to_normal( + bm->lnor_spacearr->lspacearr[l_index], clnors_data, normal); + } + } + + return true; +} + +void BM_custom_loop_normals_from_vector_layer(BMesh *bm, bool add_sharp_edges) +{ + if (!CustomData_has_layer(&bm->ldata, CD_CUSTOMLOOPNORMAL) || + !CustomData_has_layer(&bm->ldata, CD_NORMAL)) { + return; + } + + const int cd_custom_normal_offset = CustomData_get_offset(&bm->ldata, CD_CUSTOMLOOPNORMAL); + const int cd_normal_offset = CustomData_get_offset(&bm->ldata, CD_NORMAL); + + if (bm->lnor_spacearr == NULL) { + bm->lnor_spacearr = MEM_callocN(sizeof(*bm->lnor_spacearr), __func__); + } + + bm_mesh_loops_custom_normals_set(bm, + NULL, + NULL, + NULL, + bm->lnor_spacearr, + NULL, + cd_custom_normal_offset, + NULL, + cd_normal_offset, + add_sharp_edges); + + bm->spacearr_dirty &= ~(BM_SPACEARR_DIRTY | BM_SPACEARR_DIRTY_ALL); +} + +/** \} */ diff --git a/source/blender/bmesh/intern/bmesh_mesh_normals.h b/source/blender/bmesh/intern/bmesh_mesh_normals.h new file mode 100644 index 00000000000..41191340e9e --- /dev/null +++ b/source/blender/bmesh/intern/bmesh_mesh_normals.h @@ -0,0 +1,62 @@ +/* + * 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 "bmesh_class.h" + +void BM_mesh_normals_update(BMesh *bm); +void BM_mesh_normals_update_with_partial(BMesh *bm, const struct BMPartialUpdate *bmpinfo); + +void BM_verts_calc_normal_vcos(BMesh *bm, + const float (*fnos)[3], + const float (*vcos)[3], + float (*vnos)[3]); +void BM_loops_calc_normal_vcos(BMesh *bm, + const float (*vcos)[3], + const float (*vnos)[3], + const float (*fnos)[3], + const bool use_split_normals, + const float split_angle, + float (*r_lnos)[3], + struct MLoopNorSpaceArray *r_lnors_spacearr, + short (*clnors_data)[2], + const int cd_loop_clnors_offset, + const bool do_rebuild); + +bool BM_loop_check_cyclic_smooth_fan(BMLoop *l_curr); +void BM_lnorspacearr_store(BMesh *bm, float (*r_lnors)[3]); +void BM_lnorspace_invalidate(BMesh *bm, const bool do_invalidate_all); +void BM_lnorspace_rebuild(BMesh *bm, bool preserve_clnor); +void BM_lnorspace_update(BMesh *bm); +void BM_normals_loops_edges_tag(BMesh *bm, const bool do_edges); +#ifndef NDEBUG +void BM_lnorspace_err(BMesh *bm); +#endif + +/* Loop Generics */ +struct BMLoopNorEditDataArray *BM_loop_normal_editdata_array_init(BMesh *bm, + const bool do_all_loops_of_vert); +void BM_loop_normal_editdata_array_free(struct BMLoopNorEditDataArray *lnors_ed_arr); + +bool BM_custom_loop_normals_to_vector_layer(struct BMesh *bm); +void BM_custom_loop_normals_from_vector_layer(struct BMesh *bm, bool add_sharp_edges); + +void BM_edges_sharp_from_angle_set(BMesh *bm, const float split_angle); diff --git a/source/blender/bmesh/intern/bmesh_mesh_partial_update.c b/source/blender/bmesh/intern/bmesh_mesh_partial_update.c new file mode 100644 index 00000000000..7b01b61d4fa --- /dev/null +++ b/source/blender/bmesh/intern/bmesh_mesh_partial_update.c @@ -0,0 +1,254 @@ +/* + * 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. + */ + +/** \file + * \ingroup bmesh + * + * Generate data needed for partially updating mesh information. + * Currently this is used for normals and tessellation. + * + * Transform is the obvious use case where there is no need to update normals or tessellation + * for geometry which has not been modified. + * + * In the future this could be integrated into GPU updates too. + * + * Potential Improvements + * ====================== + * + * Some calculations could be significantly limited in the case of affine transformations + * (tessellation is an obvious candidate). Where only faces which have a mix + * of tagged and untagged vertices would need to be recalculated. + * + * In general this would work well besides some corner cases such as scaling to zero. + * Although the exact result may depend on the normal (for N-GONS), + * so for now update the tessellation of all tagged geometry. + */ + +#include "DNA_object_types.h" + +#include "MEM_guardedalloc.h" + +#include "BLI_alloca.h" +#include "BLI_bitmap.h" +#include "BLI_math_vector.h" + +#include "bmesh.h" + +/** + * Grow by 1.5x (rounding up). + * + * \note Use conservative reallocation since the initial sizes reserved + * may be close to (or exactly) the number of elements needed. + */ +#define GROW(len_alloc) ((len_alloc) + ((len_alloc) - ((len_alloc) / 2))) +#define GROW_ARRAY(mem, len_alloc) \ + { \ + mem = MEM_reallocN(mem, (sizeof(*mem)) * ((len_alloc) = GROW(len_alloc))); \ + } \ + ((void)0) + +#define GROW_ARRAY_AS_NEEDED(mem, len_alloc, index) \ + if (UNLIKELY(len_alloc == index)) { \ + GROW_ARRAY(mem, len_alloc); \ + } + +BLI_INLINE bool partial_elem_vert_ensure(BMPartialUpdate *bmpinfo, + BLI_bitmap *verts_tag, + BMVert *v) +{ + const int i = BM_elem_index_get(v); + if (!BLI_BITMAP_TEST(verts_tag, i)) { + BLI_BITMAP_ENABLE(verts_tag, i); + GROW_ARRAY_AS_NEEDED(bmpinfo->verts, bmpinfo->verts_len_alloc, bmpinfo->verts_len); + bmpinfo->verts[bmpinfo->verts_len++] = v; + return true; + } + 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) +{ + const int i = BM_elem_index_get(f); + if (!BLI_BITMAP_TEST(faces_tag, i)) { + BLI_BITMAP_ENABLE(faces_tag, i); + GROW_ARRAY_AS_NEEDED(bmpinfo->faces, bmpinfo->faces_len_alloc, bmpinfo->faces_len); + bmpinfo->faces[bmpinfo->faces_len++] = f; + return true; + } + return false; +} + +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) +{ + /* The caller is doing something wrong if this isn't the case. */ + BLI_assert(verts_len <= bm->totvert); + + BMPartialUpdate *bmpinfo = MEM_callocN(sizeof(*bmpinfo), __func__); + + /* 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)); + + if (params->do_normals || params->do_tessellate) { + /* - Extend to all vertices connected faces: + * In the case of tessellation this is enough. + * + * In the case of vertex normal calculation, + * All the relevant connectivity data can be accessed from the faces + * (there is no advantage in storing connected edges or vertices in this pass). + * + * NOTE: In the future it may be useful to differentiate between vertices + * that are directly marked (by the filter function when looping over all vertices). + * And vertices marked from indirect connections. + * This would require an extra tag array, so avoid this unless it's needed. + */ + + /* Faces. */ + if (bmpinfo->faces == NULL) { + bmpinfo->faces_len_alloc = default_faces_len_alloc; + bmpinfo->faces = MEM_mallocN((sizeof(BMFace *) * bmpinfo->faces_len_alloc), __func__); + faces_tag = BLI_BITMAP_NEW((size_t)bm->totface, __func__); + } + + BMVert *v; + BMIter iter; + int i; + BM_ITER_MESH_INDEX (v, &iter, bm, BM_VERTS_OF_MESH, i) { + BM_elem_index_set(v, i); /* set_inline */ + if (!filter_fn(v, user_data)) { + continue; + } + BMEdge *e_iter = v->e; + if (e_iter != NULL) { + /* Loop over edges. */ + BMEdge *e_first = v->e; + do { + BMLoop *l_iter = e_iter->l; + if (e_iter->l != NULL) { + BMLoop *l_first = e_iter->l; + /* Loop over radial loops. */ + do { + if (l_iter->v == v) { + partial_elem_face_ensure(bmpinfo, faces_tag, l_iter->f); + } + } while ((l_iter = l_iter->radial_next) != l_first); + } + } while ((e_iter = BM_DISK_EDGE_NEXT(e_iter, v)) != e_first); + } + } + } + + if (params->do_normals) { + /* - Extend to all faces vertices: + * Any changes to the faces normal needs to update all surrounding vertices. + * + * - Extend to all these vertices connected edges: + * These and needed to access those vertices edge vectors in normal calculation logic. + */ + + /* Vertices. */ + if (bmpinfo->verts == NULL) { + bmpinfo->verts_len_alloc = default_verts_len_alloc; + bmpinfo->verts = MEM_mallocN((sizeof(BMVert *) * bmpinfo->verts_len_alloc), __func__); + 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); + } while ((l_iter = l_iter->next) != l_first); + } + } + + if (verts_tag) { + MEM_freeN(verts_tag); + } + if (edges_tag) { + MEM_freeN(edges_tag); + } + if (faces_tag) { + MEM_freeN(faces_tag); + } + + bmpinfo->params = *params; + + return bmpinfo; +} + +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); + } + MEM_freeN(bmpinfo); +} 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..b31ec127744 --- /dev/null +++ b/source/blender/bmesh/intern/bmesh_mesh_partial_update.h @@ -0,0 +1,64 @@ +/* + * 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; + + /** 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); diff --git a/source/blender/bmesh/intern/bmesh_mesh_tessellate.c b/source/blender/bmesh/intern/bmesh_mesh_tessellate.c new file mode 100644 index 00000000000..7a95e52ce25 --- /dev/null +++ b/source/blender/bmesh/intern/bmesh_mesh_tessellate.c @@ -0,0 +1,457 @@ +/* + * 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. + */ + +/** \file + * \ingroup bmesh + * + * This file contains code for polygon tessellation + * (creating triangles from polygons). + */ + +#include "DNA_meshdata_types.h" + +#include "MEM_guardedalloc.h" + +#include "BLI_alloca.h" +#include "BLI_heap.h" +#include "BLI_linklist.h" +#include "BLI_math.h" +#include "BLI_memarena.h" +#include "BLI_polyfill_2d.h" +#include "BLI_polyfill_2d_beautify.h" +#include "BLI_task.h" + +#include "bmesh.h" +#include "bmesh_tools.h" + +/** + * On systems with 32+ cores, + * only a very small number of faces has any advantage single threading (in the 100's). + * Note that between 500-2000 quads, the difference isn't so much + * (tessellation isn't a bottleneck in this case anyway). + * Avoid the slight overhead of using threads in this case. + */ +#define BM_FACE_TESSELLATE_THREADED_LIMIT 1024 + +/* -------------------------------------------------------------------- */ +/** \name Default Mesh Tessellation + * \{ */ + +static int mesh_calc_tessellation_for_face(BMLoop *(*looptris)[3], + BMFace *efa, + MemArena **pf_arena_p) +{ + switch (efa->len) { + case 3: { + /* `0 1 2` -> `0 1 2` */ + BMLoop *l; + BMLoop **l_ptr = looptris[0]; + l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa); + l_ptr[1] = l = l->next; + l_ptr[2] = l->next; + return 1; + } + case 4: { + /* `0 1 2 3` -> (`0 1 2`, `0 2 3`) */ + BMLoop *l; + BMLoop **l_ptr_a = looptris[0]; + BMLoop **l_ptr_b = looptris[1]; + (l_ptr_a[0] = l_ptr_b[0] = l = BM_FACE_FIRST_LOOP(efa)); + (l_ptr_a[1] = l = l->next); + (l_ptr_a[2] = l_ptr_b[1] = l = l->next); + (l_ptr_b[2] = l->next); + + if (UNLIKELY(is_quad_flip_v3_first_third_fast( + l_ptr_a[0]->v->co, l_ptr_a[1]->v->co, l_ptr_a[2]->v->co, l_ptr_b[2]->v->co))) { + /* Flip out of degenerate 0-2 state. */ + l_ptr_a[2] = l_ptr_b[2]; + l_ptr_b[0] = l_ptr_a[1]; + } + return 2; + } + default: { + BMLoop *l_iter, *l_first; + BMLoop **l_arr; + + float axis_mat[3][3]; + float(*projverts)[2]; + uint(*tris)[3]; + + const int tris_len = efa->len - 2; + + MemArena *pf_arena = *pf_arena_p; + if (UNLIKELY(pf_arena == NULL)) { + pf_arena = *pf_arena_p = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); + } + + tris = BLI_memarena_alloc(pf_arena, sizeof(*tris) * tris_len); + l_arr = BLI_memarena_alloc(pf_arena, sizeof(*l_arr) * efa->len); + projverts = BLI_memarena_alloc(pf_arena, sizeof(*projverts) * efa->len); + + axis_dominant_v3_to_m3_negate(axis_mat, efa->no); + + int i = 0; + l_iter = l_first = BM_FACE_FIRST_LOOP(efa); + do { + l_arr[i] = l_iter; + mul_v2_m3v3(projverts[i], axis_mat, l_iter->v->co); + i++; + } while ((l_iter = l_iter->next) != l_first); + + BLI_polyfill_calc_arena(projverts, efa->len, 1, tris, pf_arena); + + for (i = 0; i < tris_len; i++) { + BMLoop **l_ptr = looptris[i]; + uint *tri = tris[i]; + + l_ptr[0] = l_arr[tri[0]]; + l_ptr[1] = l_arr[tri[1]]; + l_ptr[2] = l_arr[tri[2]]; + } + + BLI_memarena_clear(pf_arena); + return tris_len; + } + } +} + +/** + * \brief BM_mesh_calc_tessellation get the looptris and its number from a certain bmesh + * \param looptris: + * + * \note \a looptris Must be pre-allocated to at least the size of given by: poly_to_tri_count + */ +static void bm_mesh_calc_tessellation__single_threaded(BMesh *bm, BMLoop *(*looptris)[3]) +{ +#ifndef NDEBUG + const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop); +#endif + + BMIter iter; + BMFace *efa; + int i = 0; + + MemArena *pf_arena = NULL; + + BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { + BLI_assert(efa->len >= 3); + i += mesh_calc_tessellation_for_face(looptris + i, efa, &pf_arena); + } + + if (pf_arena) { + BLI_memarena_free(pf_arena); + pf_arena = NULL; + } + + BLI_assert(i <= looptris_tot); +} + +struct TessellationUserTLS { + MemArena *pf_arena; +}; + +static void mesh_calc_tessellation_for_face_fn(void *__restrict userdata, + MempoolIterData *mp_f, + const TaskParallelTLS *__restrict tls) +{ + struct TessellationUserTLS *tls_data = tls->userdata_chunk; + BMLoop *(*looptris)[3] = userdata; + BMFace *f = (BMFace *)mp_f; + BMLoop *l = BM_FACE_FIRST_LOOP(f); + const int offset = BM_elem_index_get(l) - (BM_elem_index_get(f) * 2); + mesh_calc_tessellation_for_face(looptris + offset, f, &tls_data->pf_arena); +} + +static void mesh_calc_tessellation_for_face_free_fn(const void *__restrict UNUSED(userdata), + void *__restrict tls_v) +{ + struct TessellationUserTLS *tls_data = tls_v; + if (tls_data->pf_arena) { + BLI_memarena_free(tls_data->pf_arena); + } +} + +static void bm_mesh_calc_tessellation__multi_threaded(BMesh *bm, BMLoop *(*looptris)[3]) +{ + BM_mesh_elem_index_ensure(bm, BM_LOOP | BM_FACE); + + TaskParallelSettings settings; + struct TessellationUserTLS tls_dummy = {NULL}; + BLI_parallel_mempool_settings_defaults(&settings); + settings.userdata_chunk = &tls_dummy; + settings.userdata_chunk_size = sizeof(tls_dummy); + settings.func_free = mesh_calc_tessellation_for_face_free_fn; + BM_iter_parallel(bm, BM_FACES_OF_MESH, mesh_calc_tessellation_for_face_fn, looptris, &settings); +} + +void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3]) +{ + if (bm->totface < BM_FACE_TESSELLATE_THREADED_LIMIT) { + bm_mesh_calc_tessellation__single_threaded(bm, looptris); + } + else { + bm_mesh_calc_tessellation__multi_threaded(bm, looptris); + } +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Default Tessellation (Partial Updates) + * \{ */ + +struct PartialTessellationUserData { + BMFace **faces; + BMLoop *(*looptris)[3]; +}; + +struct PartialTessellationUserTLS { + MemArena *pf_arena; +}; + +static void mesh_calc_tessellation_for_face_partial_fn(void *__restrict userdata, + const int index, + const TaskParallelTLS *__restrict tls) +{ + struct PartialTessellationUserTLS *tls_data = tls->userdata_chunk; + struct PartialTessellationUserData *data = userdata; + BMFace *f = data->faces[index]; + BMLoop *l = BM_FACE_FIRST_LOOP(f); + const int offset = BM_elem_index_get(l) - (BM_elem_index_get(f) * 2); + mesh_calc_tessellation_for_face(data->looptris + offset, f, &tls_data->pf_arena); +} + +static void mesh_calc_tessellation_for_face_partial_free_fn( + const void *__restrict UNUSED(userdata), void *__restrict tls_v) +{ + struct PartialTessellationUserTLS *tls_data = tls_v; + if (tls_data->pf_arena) { + BLI_memarena_free(tls_data->pf_arena); + } +} + +static void bm_mesh_calc_tessellation_with_partial__multi_threaded(BMLoop *(*looptris)[3], + const BMPartialUpdate *bmpinfo) +{ + const int faces_len = bmpinfo->faces_len; + BMFace **faces = bmpinfo->faces; + + struct PartialTessellationUserData data = { + .faces = faces, + .looptris = looptris, + }; + struct PartialTessellationUserTLS tls_dummy = {NULL}; + TaskParallelSettings settings; + BLI_parallel_range_settings_defaults(&settings); + settings.use_threading = true; + settings.userdata_chunk = &tls_dummy; + settings.userdata_chunk_size = sizeof(tls_dummy); + settings.func_free = mesh_calc_tessellation_for_face_partial_free_fn; + + BLI_task_parallel_range( + 0, faces_len, &data, mesh_calc_tessellation_for_face_partial_fn, &settings); +} + +static void bm_mesh_calc_tessellation_with_partial__single_threaded(BMLoop *(*looptris)[3], + const BMPartialUpdate *bmpinfo) +{ + const int faces_len = bmpinfo->faces_len; + BMFace **faces = bmpinfo->faces; + + MemArena *pf_arena = NULL; + + for (int index = 0; index < faces_len; index++) { + BMFace *f = faces[index]; + BMLoop *l = BM_FACE_FIRST_LOOP(f); + const int offset = BM_elem_index_get(l) - (BM_elem_index_get(f) * 2); + mesh_calc_tessellation_for_face(looptris + offset, f, &pf_arena); + } + + if (pf_arena) { + BLI_memarena_free(pf_arena); + } +} + +void BM_mesh_calc_tessellation_with_partial(BMesh *bm, + BMLoop *(*looptris)[3], + const BMPartialUpdate *bmpinfo) +{ + BLI_assert(bmpinfo->params.do_tessellate); + + BM_mesh_elem_index_ensure(bm, BM_LOOP | BM_FACE); + + if (bmpinfo->faces_len < BM_FACE_TESSELLATE_THREADED_LIMIT) { + bm_mesh_calc_tessellation_with_partial__single_threaded(looptris, bmpinfo); + } + else { + bm_mesh_calc_tessellation_with_partial__multi_threaded(looptris, bmpinfo); + } +} + +/** \} */ + +/* -------------------------------------------------------------------- */ +/** \name Beauty Mesh Tessellation + * + * Avoid degenerate triangles. + * \{ */ + +static int mesh_calc_tessellation_for_face_beauty(BMLoop *(*looptris)[3], + BMFace *efa, + MemArena **pf_arena_p, + Heap **pf_heap_p) +{ + switch (efa->len) { + case 3: { + BMLoop *l; + BMLoop **l_ptr = looptris[0]; + l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa); + l_ptr[1] = l = l->next; + l_ptr[2] = l->next; + return 1; + } + case 4: { + BMLoop *l_v1 = BM_FACE_FIRST_LOOP(efa); + BMLoop *l_v2 = l_v1->next; + BMLoop *l_v3 = l_v2->next; + BMLoop *l_v4 = l_v1->prev; + + /* #BM_verts_calc_rotate_beauty performs excessive checks we don't need! + * It's meant for rotating edges, it also calculates a new normal. + * + * Use #BLI_polyfill_beautify_quad_rotate_calc since we have the normal. + */ +#if 0 + const bool split_13 = (BM_verts_calc_rotate_beauty( + l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0) < 0.0f); +#else + float axis_mat[3][3], v_quad[4][2]; + axis_dominant_v3_to_m3(axis_mat, efa->no); + mul_v2_m3v3(v_quad[0], axis_mat, l_v1->v->co); + mul_v2_m3v3(v_quad[1], axis_mat, l_v2->v->co); + mul_v2_m3v3(v_quad[2], axis_mat, l_v3->v->co); + mul_v2_m3v3(v_quad[3], axis_mat, l_v4->v->co); + + const bool split_13 = BLI_polyfill_beautify_quad_rotate_calc( + v_quad[0], v_quad[1], v_quad[2], v_quad[3]) < 0.0f; +#endif + + BMLoop **l_ptr_a = looptris[0]; + BMLoop **l_ptr_b = looptris[1]; + if (split_13) { + l_ptr_a[0] = l_v1; + l_ptr_a[1] = l_v2; + l_ptr_a[2] = l_v3; + + l_ptr_b[0] = l_v1; + l_ptr_b[1] = l_v3; + l_ptr_b[2] = l_v4; + } + else { + l_ptr_a[0] = l_v1; + l_ptr_a[1] = l_v2; + l_ptr_a[2] = l_v4; + + l_ptr_b[0] = l_v2; + l_ptr_b[1] = l_v3; + l_ptr_b[2] = l_v4; + } + return 2; + } + default: { + MemArena *pf_arena = *pf_arena_p; + Heap *pf_heap = *pf_heap_p; + if (UNLIKELY(pf_arena == NULL)) { + pf_arena = *pf_arena_p = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); + pf_heap = *pf_heap_p = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE); + } + + BMLoop *l_iter, *l_first; + BMLoop **l_arr; + + float axis_mat[3][3]; + float(*projverts)[2]; + uint(*tris)[3]; + + const int tris_len = efa->len - 2; + + tris = BLI_memarena_alloc(pf_arena, sizeof(*tris) * tris_len); + l_arr = BLI_memarena_alloc(pf_arena, sizeof(*l_arr) * efa->len); + projverts = BLI_memarena_alloc(pf_arena, sizeof(*projverts) * efa->len); + + axis_dominant_v3_to_m3_negate(axis_mat, efa->no); + + int i = 0; + l_iter = l_first = BM_FACE_FIRST_LOOP(efa); + do { + l_arr[i] = l_iter; + mul_v2_m3v3(projverts[i], axis_mat, l_iter->v->co); + i++; + } while ((l_iter = l_iter->next) != l_first); + + BLI_polyfill_calc_arena(projverts, efa->len, 1, tris, pf_arena); + + BLI_polyfill_beautify(projverts, efa->len, tris, pf_arena, pf_heap); + + for (i = 0; i < tris_len; i++) { + BMLoop **l_ptr = looptris[i]; + uint *tri = tris[i]; + + l_ptr[0] = l_arr[tri[0]]; + l_ptr[1] = l_arr[tri[1]]; + l_ptr[2] = l_arr[tri[2]]; + } + + BLI_memarena_clear(pf_arena); + + return tris_len; + } + } +} + +/** + * A version of #BM_mesh_calc_tessellation that avoids degenerate triangles. + */ +void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3]) +{ +#ifndef NDEBUG + const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop); +#endif + + BMIter iter; + BMFace *efa; + int i = 0; + + MemArena *pf_arena = NULL; + + /* use_beauty */ + Heap *pf_heap = NULL; + + BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { + BLI_assert(efa->len >= 3); + i += mesh_calc_tessellation_for_face_beauty(looptris + i, efa, &pf_arena, &pf_heap); + } + + if (pf_arena) { + BLI_memarena_free(pf_arena); + + BLI_heap_free(pf_heap, NULL); + } + + BLI_assert(i <= looptris_tot); +} + +/** \} */ diff --git a/source/blender/bmesh/intern/bmesh_mesh_tessellate.h b/source/blender/bmesh/intern/bmesh_mesh_tessellate.h new file mode 100644 index 00000000000..f68a91cb988 --- /dev/null +++ b/source/blender/bmesh/intern/bmesh_mesh_tessellate.h @@ -0,0 +1,30 @@ +/* + * 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 + */ + +struct BMPartialUpdate; + +void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3]); +void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3]); + +void BM_mesh_calc_tessellation_with_partial(BMesh *bm, + BMLoop *(*looptris)[3], + const struct BMPartialUpdate *bmpinfo); diff --git a/source/blender/bmesh/intern/bmesh_mods.c b/source/blender/bmesh/intern/bmesh_mods.c index 8e5ed9c3bf0..76e32667804 100644 --- a/source/blender/bmesh/intern/bmesh_mods.c +++ b/source/blender/bmesh/intern/bmesh_mods.c @@ -72,7 +72,7 @@ bool BM_vert_dissolve(BMesh *bm, BMVert *v) } if (!v->e->l) { if (len == 2) { - return (BM_vert_collapse_edge(bm, v->e, v, true, true) != NULL); + return (BM_vert_collapse_edge(bm, v->e, v, true, true, true) != NULL); } /* used to kill the vertex here, but it may be connected to faces. * so better do nothing */ @@ -82,7 +82,7 @@ bool BM_vert_dissolve(BMesh *bm, BMVert *v) } if (len == 2 && BM_vert_face_count_is_equal(v, 1)) { /* boundary vertex on a face */ - return (BM_vert_collapse_edge(bm, v->e, v, true, true) != NULL); + return (BM_vert_collapse_edge(bm, v->e, v, true, true, true) != NULL); } return BM_disk_dissolve(bm, v); } @@ -133,7 +133,7 @@ bool BM_disk_dissolve(BMesh *bm, BMVert *v) if (UNLIKELY(!BM_faces_join_pair(bm, e->l, e->l->radial_next, true))) { return false; } - if (UNLIKELY(!BM_vert_collapse_faces(bm, v->e, v, 1.0, true, false, true))) { + if (UNLIKELY(!BM_vert_collapse_faces(bm, v->e, v, 1.0, true, false, true, true))) { return false; } #endif @@ -141,7 +141,7 @@ bool BM_disk_dissolve(BMesh *bm, BMVert *v) } if (keepedge == NULL && len == 2) { /* collapse the vertex */ - e = BM_vert_collapse_faces(bm, v->e, v, 1.0, true, true, true); + e = BM_vert_collapse_faces(bm, v->e, v, 1.0, true, true, true, true); if (!e) { return false; @@ -184,7 +184,8 @@ bool BM_disk_dissolve(BMesh *bm, BMVert *v) /* collapse the vertex */ /* note, the baseedge can be a boundary of manifold, use this as join_faces arg */ - e = BM_vert_collapse_faces(bm, baseedge, v, 1.0, true, !BM_edge_is_boundary(baseedge), true); + e = BM_vert_collapse_faces( + bm, baseedge, v, 1.0, true, !BM_edge_is_boundary(baseedge), true, true); if (!e) { return false; @@ -432,7 +433,8 @@ BMEdge *BM_vert_collapse_faces(BMesh *bm, float fac, const bool do_del, const bool join_faces, - const bool kill_degenerate_faces) + const bool kill_degenerate_faces, + const bool kill_duplicate_faces) { BMEdge *e_new = NULL; BMVert *tv = BM_edge_other_vert(e_kill, v_kill); @@ -503,7 +505,8 @@ BMEdge *BM_vert_collapse_faces(BMesh *bm, /* same as BM_vert_collapse_edge() however we already * have vars to perform this operation so don't call. */ e_new = bmesh_kernel_join_edge_kill_vert( - bm, e_kill, v_kill, do_del, true, kill_degenerate_faces); + bm, e_kill, v_kill, do_del, true, kill_degenerate_faces, kill_duplicate_faces); + /* e_new = BM_edge_exists(tv, tv2); */ /* same as return above */ } @@ -517,8 +520,12 @@ BMEdge *BM_vert_collapse_faces(BMesh *bm, * * \return The New Edge */ -BMEdge *BM_vert_collapse_edge( - BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, const bool kill_degenerate_faces) +BMEdge *BM_vert_collapse_edge(BMesh *bm, + BMEdge *e_kill, + BMVert *v_kill, + const bool do_del, + const bool kill_degenerate_faces, + const bool kill_duplicate_faces) { /* nice example implementation but we want loops to have their customdata * accounted for */ @@ -546,7 +553,8 @@ BMEdge *BM_vert_collapse_edge( #else /* with these args faces are never joined, same as above * but account for loop customdata */ - return BM_vert_collapse_faces(bm, e_kill, v_kill, 1.0f, do_del, false, kill_degenerate_faces); + return BM_vert_collapse_faces( + bm, e_kill, v_kill, 1.0f, do_del, false, kill_degenerate_faces, kill_duplicate_faces); #endif } diff --git a/source/blender/bmesh/intern/bmesh_mods.h b/source/blender/bmesh/intern/bmesh_mods.h index 7491c309754..4328187b95e 100644 --- a/source/blender/bmesh/intern/bmesh_mods.h +++ b/source/blender/bmesh/intern/bmesh_mods.h @@ -51,12 +51,14 @@ BMEdge *BM_vert_collapse_faces(BMesh *bm, float fac, const bool do_del, const bool join_faces, - const bool kill_degenerate_faces); + const bool kill_degenerate_faces, + const bool kill_duplicate_faces); BMEdge *BM_vert_collapse_edge(BMesh *bm, BMEdge *e_kill, BMVert *v_kill, const bool do_del, - const bool kill_degenerate_faces); + const bool kill_degenerate_faces, + const bool kill_duplicate_faces); BMVert *BM_edge_collapse(BMesh *bm, BMEdge *e_kill, diff --git a/source/blender/bmesh/intern/bmesh_operators.c b/source/blender/bmesh/intern/bmesh_operators.c index c2421939aa8..e47fd1c035d 100644 --- a/source/blender/bmesh/intern/bmesh_operators.c +++ b/source/blender/bmesh/intern/bmesh_operators.c @@ -421,10 +421,10 @@ void BMO_slot_mat_set(BMOperator *op, slot->data.p = BLI_memarena_alloc(op->arena, sizeof(float[4][4])); if (size == 4) { - copy_m4_m4(slot->data.p, (float(*)[4])mat); + copy_m4_m4(slot->data.p, (const float(*)[4])mat); } else if (size == 3) { - copy_m4_m3(slot->data.p, (float(*)[3])mat); + copy_m4_m3(slot->data.p, (const float(*)[3])mat); } else { fprintf(stderr, "%s: invalid size argument %d (bmesh internal error)\n", __func__, size); diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index 4ae2cc67140..5397098a7f3 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -18,8 +18,7 @@ * \ingroup bmesh * * This file contains code for dealing - * with polygons (normal/area calculation, - * tessellation, etc) + * with polygons (normal/area calculation, tessellation, etc) */ #include "DNA_listBase.h" @@ -1523,289 +1522,3 @@ void BM_face_as_array_loop_quad(BMFace *f, BMLoop *r_loops[4]) l = l->next; r_loops[3] = l; } - -/** - * \brief BM_mesh_calc_tessellation get the looptris and its number from a certain bmesh - * \param looptris: - * - * \note \a looptris Must be pre-allocated to at least the size of given by: poly_to_tri_count - */ -void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot) -{ - /* use this to avoid locking pthread for _every_ polygon - * and calling the fill function */ -#define USE_TESSFACE_SPEEDUP - - /* this assumes all faces can be scan-filled, which isn't always true, - * worst case we over alloc a little which is acceptable */ -#ifndef NDEBUG - const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop); -#endif - - BMIter iter; - BMFace *efa; - int i = 0; - - MemArena *arena = NULL; - - BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { - /* don't consider two-edged faces */ - if (UNLIKELY(efa->len < 3)) { - /* do nothing */ - } - -#ifdef USE_TESSFACE_SPEEDUP - - /* no need to ensure the loop order, we know its ok */ - - else if (efa->len == 3) { -# if 0 - int j; - BM_ITER_ELEM_INDEX(l, &liter, efa, BM_LOOPS_OF_FACE, j) { - looptris[i][j] = l; - } - i += 1; -# else - /* more cryptic but faster */ - BMLoop *l; - BMLoop **l_ptr = looptris[i++]; - l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa); - l_ptr[1] = l = l->next; - l_ptr[2] = l->next; -# endif - } - else if (efa->len == 4) { -# if 0 - BMLoop *ltmp[4]; - int j; - BLI_array_grow_items(looptris, 2); - BM_ITER_ELEM_INDEX(l, &liter, efa, BM_LOOPS_OF_FACE, j) { - ltmp[j] = l; - } - - looptris[i][0] = ltmp[0]; - looptris[i][1] = ltmp[1]; - looptris[i][2] = ltmp[2]; - i += 1; - - looptris[i][0] = ltmp[0]; - looptris[i][1] = ltmp[2]; - looptris[i][2] = ltmp[3]; - i += 1; -# else - /* more cryptic but faster */ - BMLoop *l; - BMLoop **l_ptr_a = looptris[i++]; - BMLoop **l_ptr_b = looptris[i++]; - (l_ptr_a[0] = l_ptr_b[0] = l = BM_FACE_FIRST_LOOP(efa)); - (l_ptr_a[1] = l = l->next); - (l_ptr_a[2] = l_ptr_b[1] = l = l->next); - (l_ptr_b[2] = l->next); -# endif - - if (UNLIKELY(is_quad_flip_v3_first_third_fast( - l_ptr_a[0]->v->co, l_ptr_a[1]->v->co, l_ptr_a[2]->v->co, l_ptr_b[2]->v->co))) { - /* flip out of degenerate 0-2 state. */ - l_ptr_a[2] = l_ptr_b[2]; - l_ptr_b[0] = l_ptr_a[1]; - } - } - -#endif /* USE_TESSFACE_SPEEDUP */ - - else { - int j; - - BMLoop *l_iter; - BMLoop *l_first; - BMLoop **l_arr; - - float axis_mat[3][3]; - float(*projverts)[2]; - uint(*tris)[3]; - - const int totfilltri = efa->len - 2; - - if (UNLIKELY(arena == NULL)) { - arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); - } - - tris = BLI_memarena_alloc(arena, sizeof(*tris) * totfilltri); - l_arr = BLI_memarena_alloc(arena, sizeof(*l_arr) * efa->len); - projverts = BLI_memarena_alloc(arena, sizeof(*projverts) * efa->len); - - axis_dominant_v3_to_m3_negate(axis_mat, efa->no); - - j = 0; - l_iter = l_first = BM_FACE_FIRST_LOOP(efa); - do { - l_arr[j] = l_iter; - mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co); - j++; - } while ((l_iter = l_iter->next) != l_first); - - BLI_polyfill_calc_arena(projverts, efa->len, 1, tris, arena); - - for (j = 0; j < totfilltri; j++) { - BMLoop **l_ptr = looptris[i++]; - uint *tri = tris[j]; - - l_ptr[0] = l_arr[tri[0]]; - l_ptr[1] = l_arr[tri[1]]; - l_ptr[2] = l_arr[tri[2]]; - } - - BLI_memarena_clear(arena); - } - } - - if (arena) { - BLI_memarena_free(arena); - arena = NULL; - } - - *r_looptris_tot = i; - - BLI_assert(i <= looptris_tot); - -#undef USE_TESSFACE_SPEEDUP -} - -/** - * A version of #BM_mesh_calc_tessellation that avoids degenerate triangles. - */ -void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot) -{ - /* this assumes all faces can be scan-filled, which isn't always true, - * worst case we over alloc a little which is acceptable */ -#ifndef NDEBUG - const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop); -#endif - - BMIter iter; - BMFace *efa; - int i = 0; - - MemArena *pf_arena = NULL; - - /* use_beauty */ - Heap *pf_heap = NULL; - - BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { - /* don't consider two-edged faces */ - if (UNLIKELY(efa->len < 3)) { - /* do nothing */ - } - else if (efa->len == 3) { - BMLoop *l; - BMLoop **l_ptr = looptris[i++]; - l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa); - l_ptr[1] = l = l->next; - l_ptr[2] = l->next; - } - else if (efa->len == 4) { - BMLoop *l_v1 = BM_FACE_FIRST_LOOP(efa); - BMLoop *l_v2 = l_v1->next; - BMLoop *l_v3 = l_v2->next; - BMLoop *l_v4 = l_v1->prev; - - /* #BM_verts_calc_rotate_beauty performs excessive checks we don't need! - * It's meant for rotating edges, it also calculates a new normal. - * - * Use #BLI_polyfill_beautify_quad_rotate_calc since we have the normal. - */ -#if 0 - const bool split_13 = (BM_verts_calc_rotate_beauty( - l_v1->v, l_v2->v, l_v3->v, l_v4->v, 0, 0) < 0.0f); -#else - float axis_mat[3][3], v_quad[4][2]; - axis_dominant_v3_to_m3(axis_mat, efa->no); - mul_v2_m3v3(v_quad[0], axis_mat, l_v1->v->co); - mul_v2_m3v3(v_quad[1], axis_mat, l_v2->v->co); - mul_v2_m3v3(v_quad[2], axis_mat, l_v3->v->co); - mul_v2_m3v3(v_quad[3], axis_mat, l_v4->v->co); - - const bool split_13 = BLI_polyfill_beautify_quad_rotate_calc( - v_quad[0], v_quad[1], v_quad[2], v_quad[3]) < 0.0f; -#endif - - BMLoop **l_ptr_a = looptris[i++]; - BMLoop **l_ptr_b = looptris[i++]; - if (split_13) { - l_ptr_a[0] = l_v1; - l_ptr_a[1] = l_v2; - l_ptr_a[2] = l_v3; - - l_ptr_b[0] = l_v1; - l_ptr_b[1] = l_v3; - l_ptr_b[2] = l_v4; - } - else { - l_ptr_a[0] = l_v1; - l_ptr_a[1] = l_v2; - l_ptr_a[2] = l_v4; - - l_ptr_b[0] = l_v2; - l_ptr_b[1] = l_v3; - l_ptr_b[2] = l_v4; - } - } - else { - int j; - - BMLoop *l_iter; - BMLoop *l_first; - BMLoop **l_arr; - - float axis_mat[3][3]; - float(*projverts)[2]; - unsigned int(*tris)[3]; - - const int totfilltri = efa->len - 2; - - if (UNLIKELY(pf_arena == NULL)) { - pf_arena = BLI_memarena_new(BLI_MEMARENA_STD_BUFSIZE, __func__); - pf_heap = BLI_heap_new_ex(BLI_POLYFILL_ALLOC_NGON_RESERVE); - } - - tris = BLI_memarena_alloc(pf_arena, sizeof(*tris) * totfilltri); - l_arr = BLI_memarena_alloc(pf_arena, sizeof(*l_arr) * efa->len); - projverts = BLI_memarena_alloc(pf_arena, sizeof(*projverts) * efa->len); - - axis_dominant_v3_to_m3_negate(axis_mat, efa->no); - - j = 0; - l_iter = l_first = BM_FACE_FIRST_LOOP(efa); - do { - l_arr[j] = l_iter; - mul_v2_m3v3(projverts[j], axis_mat, l_iter->v->co); - j++; - } while ((l_iter = l_iter->next) != l_first); - - BLI_polyfill_calc_arena(projverts, efa->len, 1, tris, pf_arena); - - BLI_polyfill_beautify(projverts, efa->len, tris, pf_arena, pf_heap); - - for (j = 0; j < totfilltri; j++) { - BMLoop **l_ptr = looptris[i++]; - unsigned int *tri = tris[j]; - - l_ptr[0] = l_arr[tri[0]]; - l_ptr[1] = l_arr[tri[1]]; - l_ptr[2] = l_arr[tri[2]]; - } - - BLI_memarena_clear(pf_arena); - } - } - - if (pf_arena) { - BLI_memarena_free(pf_arena); - - BLI_heap_free(pf_heap, NULL); - } - - *r_looptris_tot = i; - - BLI_assert(i <= looptris_tot); -} diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h index 8c2b9ee0bff..2c32cd39002 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/source/blender/bmesh/intern/bmesh_polygon.h @@ -21,12 +21,10 @@ */ struct Heap; +struct BMPartialUpdate; #include "BLI_compiler_attrs.h" -void BM_mesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot); -void BM_mesh_calc_tessellation_beauty(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot); - void BM_face_calc_tessellation(const BMFace *f, const bool use_fixed_quad, BMLoop **r_loops, diff --git a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c index dcf9717465c..0754564fa47 100644 --- a/source/blender/bmesh/intern/bmesh_polygon_edgenet.c +++ b/source/blender/bmesh/intern/bmesh_polygon_edgenet.c @@ -106,7 +106,7 @@ static void normalize_v2_m3_v3v3(float out[2], /** * \note Be sure to update #bm_face_split_edgenet_find_loop_pair_exists - * when making changed to edge picking logic. + * when making changes to edge picking logic. */ static bool bm_face_split_edgenet_find_loop_pair(BMVert *v_init, const float face_normal[3], @@ -456,8 +456,8 @@ static bool bm_face_split_edgenet_find_loop(BMVert *v_init, * Splits a face into many smaller faces defined by an edge-net. * handle customdata and degenerate cases. * - * - isolated holes or unsupported face configurations, will be ignored. - * - customdata calculations aren't efficient + * - Isolated holes or unsupported face configurations, will be ignored. + * - Customdata calculations aren't efficient * (need to calculate weights for each vert). */ bool BM_face_split_edgenet(BMesh *bm, @@ -593,7 +593,7 @@ bool BM_face_split_edgenet(BMesh *bm, BMIter iter; BMLoop *l_other; - /* see: #BM_loop_interp_from_face for similar logic */ + /* See: #BM_loop_interp_from_face for similar logic. */ void **blocks = BLI_array_alloca(blocks, f->len); float(*cos_2d)[2] = BLI_array_alloca(cos_2d, f->len); float *w = BLI_array_alloca(w, f->len); @@ -1064,7 +1064,7 @@ static int bm_face_split_edgenet_find_connection(const struct EdgeGroup_FindConn #ifdef USE_PARTIAL_CONNECT /** - * Used to identify edges that get split off when making island from partial connection. + * Used to identify edges that get split off when making island from partial connection. * fptr should be a BMFace*, but is a void* for general interface to BM_vert_separate_tested_edges */ static bool test_tagged_and_notface(BMEdge *e, void *fptr) @@ -1211,7 +1211,7 @@ static bool bm_vert_partial_connect_check_overlap(const int *remap, const int v_a_index, const int v_b_index) { - /* connected to eachother */ + /* Connected to each other. */ if (UNLIKELY((remap[v_a_index] == v_b_index) || (remap[v_b_index] == v_a_index))) { return true; } @@ -1226,7 +1226,7 @@ static bool bm_vert_partial_connect_check_overlap(const int *remap, * \param use_partial_connect: Support for handling islands connected by only a single edge, * \note that this is quite slow so avoid using where possible. * \param mem_arena: Avoids many small allocs & should be cleared after each use. - * take care since \a r_edge_net_new is stored in \a r_edge_net_new. + * take care since \a edge_net_new is stored in \a r_edge_net_new. */ bool BM_face_split_edgenet_connect_islands(BMesh *bm, BMFace *f, @@ -1246,7 +1246,7 @@ bool BM_face_split_edgenet_connect_islands(BMesh *bm, * * Keep the first part fast since it will run very often for edge-nets that have no holes. * - * \note Don't use the mem_arena unless he have holes to fill. + * \note Don't use the mem_arena unless we have holes to fill. * (avoid thrashing the area when the initial check isn't so intensive on the stack). */ @@ -1572,7 +1572,7 @@ bool BM_face_split_edgenet_connect_islands(BMesh *bm, if (g->has_prev_edge == false) { BMVert *v_origin = g->vert_span.min; - + /* Index of BMVert for the edge group connection with `v_origin`. */ const int index_other = bm_face_split_edgenet_find_connection(&args, v_origin, false); // BLI_assert(index_other >= 0 && index_other < (int)vert_arr_len); @@ -1598,7 +1598,7 @@ bool BM_face_split_edgenet_connect_islands(BMesh *bm, { BMVert *v_origin = g->vert_span.max; - + /* Index of BMVert for the edge group connection with `v_origin`. */ const int index_other = bm_face_split_edgenet_find_connection(&args, v_origin, true); // BLI_assert(index_other >= 0 && index_other < (int)vert_arr_len); @@ -1660,7 +1660,7 @@ finally: struct TempVertPair *tvp = temp_vert_pairs.list; do { /* its _very_ unlikely the edge exists, - * however splicing may case this. see: T48012 */ + * however splicing may cause this. see: T48012 */ if (!BM_edge_exists(tvp->v_orig, tvp->v_temp)) { BM_vert_splice(bm, tvp->v_orig, tvp->v_temp); } |