diff options
Diffstat (limited to 'source/blender/bmesh/operators/bmo_normals.c')
| -rw-r--r-- | source/blender/bmesh/operators/bmo_normals.c | 167 |
1 files changed, 146 insertions, 21 deletions
diff --git a/source/blender/bmesh/operators/bmo_normals.c b/source/blender/bmesh/operators/bmo_normals.c index d0f08871400..f62e445ca18 100644 --- a/source/blender/bmesh/operators/bmo_normals.c +++ b/source/blender/bmesh/operators/bmo_normals.c @@ -47,39 +47,79 @@ static bool bmo_recalc_normal_edge_filter_cb(BMElem *ele, void *UNUSED(user_data } /** - * Given an array of faces, recalculate their normals. - * this functions assumes all faces in the array are connected by edges. + * This uses a more comprehensive test to see if the furthest face from the center + * is pointing towards the center or not. * - * \param bm - * \param faces Array of connected faces. - * \param faces_len Length of \a faces - * \param oflag Flag to check before doing the actual face flipping. + * A simple test could just check the dot product of the faces-normal and the direction from the center, + * however this can fail for faces which make a sharp spike. eg: + * + * <pre> + * + + * |\ <- face + * + + + * \ \ + * \ \ + * \ +--------------+ + * \ | + * \ center -> + | + * \ | + * +------------+ + * </pre> + * + * In the example above, the a\ face can point towards the \a center + * which would end up flipping the normals inwards. + * + * To take these spikes into account, use the normals of the faces edges. */ -static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int faces_len, const short oflag) +#define USE_FACE_EDGE_NORMAL_TEST + +/** + * The center of the entire island is't necessarily well placed, + * + * This re-calculated a center relative to this face. + */ +#ifdef USE_FACE_EDGE_NORMAL_TEST +# define USE_FACE_LOCAL_CENTER_TEST +#endif + +/** + * \return a face index in \a faces and set \a r_is_flip if the face is flipped away from the center. + */ +static int recalc_face_normals_find_index(BMesh *bm, BMFace **faces, const int faces_len, bool *r_is_flip) { + float cent_area_accum = 0.0f; + float f_len_best_sq; + float cent[3], tvec[3]; - float (*faces_center)[3] = MEM_mallocN(sizeof(*faces_center) * faces_len, __func__); const float cent_fac = 1.0f / (float)faces_len; - int i, f_start_index; - const short oflag_flip = oflag | FACE_FLIP; - float f_len_best_sq; - BMFace *f; + float (*faces_center)[3] = MEM_mallocN(sizeof(*faces_center) * faces_len, __func__); + float *faces_area = MEM_mallocN(sizeof(*faces_area) * faces_len, __func__); + bool is_flip = false; + int f_start_index; + int i; - BLI_LINKSTACK_DECLARE(fstack, BMFace *); + UNUSED_VARS_NDEBUG(bm); zero_v3(cent); /* first calculate the center */ for (i = 0; i < faces_len; i++) { float *f_cent = faces_center[i]; + const float f_area = BM_face_calc_area(faces[i]); BM_face_calc_center_mean_weighted(faces[i], f_cent); - madd_v3_v3fl(cent, f_cent, cent_fac); + madd_v3_v3fl(cent, f_cent, cent_fac * f_area); + cent_area_accum += f_area; + faces_area[i] = f_area; BLI_assert(BMO_elem_flag_test(bm, faces[i], FACE_TEMP) == 0); BLI_assert(BM_face_is_normal_valid(faces[i])); } + if (cent_area_accum != 0.0f) { + mul_v3_fl(cent, 1.0f / cent_area_accum); + } + f_len_best_sq = -FLT_MAX; /* used in degenerate cases only */ f_start_index = 0; @@ -87,19 +127,104 @@ static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int f for (i = 0; i < faces_len; i++) { float f_len_test_sq; - if ((f_len_test_sq = len_squared_v3v3(faces_center[i], cent)) > f_len_best_sq) { - f_len_best_sq = f_len_test_sq; - f_start_index = i; + if (faces_area[i] > FLT_EPSILON) { + if ((f_len_test_sq = len_squared_v3v3(faces_center[i], cent)) > f_len_best_sq) { + f_len_best_sq = f_len_test_sq; + f_start_index = i; + } } } - /* make sure the starting face has the correct winding */ - sub_v3_v3v3(tvec, faces_center[f_start_index], cent); - if (dot_v3v3(tvec, faces[f_start_index]->no) < 0.0f) { - BMO_elem_flag_enable(bm, faces[f_start_index], FACE_FLIP); +#ifdef USE_FACE_EDGE_NORMAL_TEST + { + BMFace *f_test = faces[f_start_index]; + BMLoop *l_iter, *l_first; + float e_len_best_sq = -FLT_MAX; + BMLoop *l_other_best = NULL; + float no_edge[3]; + const float *no_best; + + l_iter = l_first = BM_FACE_FIRST_LOOP(f_test); + do { + if (BM_edge_is_manifold(l_iter->e) && + bmo_recalc_normal_edge_filter_cb((BMElem *)l_iter->e, NULL)) + { + BMLoop *l_other = l_iter->radial_next; + + if (len_squared_v3v3(l_iter->v->co, l_iter->next->v->co) > FLT_EPSILON) { + float e_len_test_sq; + float e_cent[3]; + mid_v3_v3v3(e_cent, l_iter->v->co, l_iter->next->v->co); + e_len_test_sq = len_squared_v3v3(cent, e_cent); + if (e_len_test_sq > e_len_best_sq) { + l_other_best = l_other; + e_len_best_sq = e_len_test_sq; + } + } + } + } while ((l_iter = l_iter->next) != l_first); + + /* furthest edge on furthest face */ + if (l_other_best) { + float e_cent[3]; + +#ifdef USE_FACE_LOCAL_CENTER_TEST + { + float f_cent_other[3]; + BM_face_calc_center_mean_weighted(l_other_best->f, f_cent_other); + mid_v3_v3v3(cent, f_cent_other, faces_center[f_start_index]); + } +#endif + mid_v3_v3v3(e_cent, l_other_best->e->v1->co, l_other_best->e->v2->co); + sub_v3_v3v3(tvec, e_cent, cent); + + madd_v3_v3v3fl(no_edge, f_test->no, l_other_best->f->no, BM_edge_is_contiguous(l_other_best->e) ? 1 : -1); + no_best = no_edge; + } + else { + sub_v3_v3v3(tvec, faces_center[f_start_index], cent); + no_best = f_test->no; + } + + is_flip = (dot_v3v3(tvec, no_best) < 0.0f); } +#else + sub_v3_v3v3(tvec, faces_center[f_start_index], cent); + is_flip = (dot_v3v3(tvec, faces[f_start_index]->no) < 0.0f); +#endif + /* make sure the starting face has the correct winding */ MEM_freeN(faces_center); + MEM_freeN(faces_area); + + *r_is_flip = is_flip; + return f_start_index; +} + +/** + * Given an array of faces, recalculate their normals. + * this functions assumes all faces in the array are connected by edges. + * + * \param bm + * \param faces Array of connected faces. + * \param faces_len Length of \a faces + * \param oflag Flag to check before doing the actual face flipping. + */ +static void bmo_recalc_face_normals_array(BMesh *bm, BMFace **faces, const int faces_len, const short oflag) +{ + int i, f_start_index; + const short oflag_flip = oflag | FACE_FLIP; + bool is_flip; + + BMFace *f; + + BLI_LINKSTACK_DECLARE(fstack, BMFace *); + + f_start_index = recalc_face_normals_find_index(bm, faces, faces_len, &is_flip); + + if (is_flip) { + BMO_elem_flag_enable(bm, faces[f_start_index], FACE_FLIP); + } /* now that we've found our starting face, make all connected faces * have the same winding. this is done recursively, using a manual |