From 65df2fd9976178c98db5401ff4e965047e35afdb Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Sun, 12 Jun 2016 12:22:38 +1000 Subject: bmesh py api: expose BM_face_calc_tangent_* D1988 by @wisaac, with own edits and improvements. This improves on existing tangent calculation functions too. - BM_face_calc_tangent_auto: Chooses method based on number of sides, used by manipulator (not exposed to Python). - BM_face_calc_tangent_edge: from longest edge. - BM_face_calc_tangent_edge_pair: from longest edge-pair (most useful with quads). - BM_face_calc_tangent_edge_diagonal: edge farthest from any vertex. - BM_face_calc_tangent_vert_diagonal: vert farthest from any vertex. Also optimize BM_vert_tri_calc_tangent_edge* functions to avoid sqrt. --- source/blender/bmesh/intern/bmesh_marking.c | 2 +- source/blender/bmesh/intern/bmesh_polygon.c | 242 +++++++++++++++++++-- source/blender/bmesh/intern/bmesh_polygon.h | 9 +- .../editors/transform/transform_orientations.c | 4 +- source/blender/python/bmesh/bmesh_py_types.c | 80 +++++++ 5 files changed, 308 insertions(+), 29 deletions(-) diff --git a/source/blender/bmesh/intern/bmesh_marking.c b/source/blender/bmesh/intern/bmesh_marking.c index 3fe888736f0..d6ca7239e39 100644 --- a/source/blender/bmesh/intern/bmesh_marking.c +++ b/source/blender/bmesh/intern/bmesh_marking.c @@ -904,7 +904,7 @@ void BM_editselection_plane(BMEditSelection *ese, float r_plane[3]) } else if (ese->htype == BM_FACE) { BMFace *efa = (BMFace *)ese->ele; - BM_face_calc_plane(efa, r_plane); + BM_face_calc_tangent_auto(efa, r_plane); } } diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index 62b29e61d08..79051a2490f 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -286,64 +286,258 @@ float BM_face_calc_perimeter(const BMFace *f) return perimeter; } -void BM_vert_tri_calc_plane(BMVert *verts[3], float r_plane[3]) +/** + * Utility function to calculate the edge which is most different from the other two. + * + * \return The first edge index, where the second vertex is ``(index + 1) % 3``. + */ +static int bm_vert_tri_find_unique_edge(BMVert *verts[3]) { - float lens[3]; + /* find the most 'unique' loop, (greatest difference to others) */ +#if 1 + /* optimized version that avoids sqrt */ float difs[3]; - int order[3] = {0, 1, 2}; + for (int i_prev = 1, i_curr = 2, i_next = 0; + i_next < 3; + i_prev = i_curr, i_curr = i_next++) + { + const float *co = verts[i_curr]->co; + const float *co_other[2] = {verts[i_prev]->co, verts[i_next]->co}; + float proj_dir[3]; + mid_v3_v3v3(proj_dir, co_other[0], co_other[1]); + sub_v3_v3(proj_dir, co); + + float proj_pair[2][3]; + project_v3_v3v3(proj_pair[0], co_other[0], proj_dir); + project_v3_v3v3(proj_pair[1], co_other[1], proj_dir); + difs[i_next] = len_squared_v3v3(proj_pair[0], proj_pair[1]); + } +#else + const float lens[3] = { + len_v3v3(verts[0]->co, verts[1]->co), + len_v3v3(verts[1]->co, verts[2]->co), + len_v3v3(verts[2]->co, verts[0]->co), + }; + const float difs[3] = { + fabsf(lens[1] - lens[2]), + fabsf(lens[2] - lens[0]), + fabsf(lens[0] - lens[1]), + }; +#endif - lens[0] = len_v3v3(verts[0]->co, verts[1]->co); - lens[1] = len_v3v3(verts[1]->co, verts[2]->co); - lens[2] = len_v3v3(verts[2]->co, verts[0]->co); + int order[3] = {0, 1, 2}; + axis_sort_v3(difs, order); - /* find the shortest or the longest loop */ - difs[0] = fabsf(lens[1] - lens[2]); - difs[1] = fabsf(lens[2] - lens[0]); - difs[2] = fabsf(lens[0] - lens[1]); + return order[0]; +} - axis_sort_v3(difs, order); - sub_v3_v3v3(r_plane, verts[order[0]]->co, verts[(order[0] + 1) % 3]->co); +/** + * Calculate a tangent from any 3 vertices. + * + * The tangent aligns to the most *unique* edge + * (the edge most unlike the other two). + * + * \param r_tangent: Calculated unit length tangent (return value). + */ +void BM_vert_tri_calc_tangent_edge(BMVert *verts[3], float r_tangent[3]) +{ + const int index = bm_vert_tri_find_unique_edge(verts); + + sub_v3_v3v3(r_tangent, verts[index]->co, verts[(index + 1) % 3]->co); + + normalize_v3(r_tangent); } /** - * Compute a meaningful direction along the face (use for manipulator axis). - * \note result isnt normalized. + * Calculate a tangent from any 3 vertices, + * + * The tangent follows the center-line formed by the most unique edges center + * and the opposite vertex. + * + * \param r_tangent: Calculated unit length tangent (return value). */ -void BM_face_calc_plane(const BMFace *f, float r_plane[3]) +void BM_vert_tri_calc_tangent_edge_pair(BMVert *verts[3], float r_tangent[3]) +{ + const int index = bm_vert_tri_find_unique_edge(verts); + + const float *v_a = verts[index]->co; + const float *v_b = verts[(index + 1) % 3]->co; + const float *v_other = verts[(index + 2) % 3]->co; + + mid_v3_v3v3(r_tangent, v_a, v_b); + sub_v3_v3v3(r_tangent, v_other, r_tangent); + + normalize_v3(r_tangent); +} + +/** + * Compute the tanget of the face, using the longest edge. + */ +void BM_face_calc_tangent_edge(const BMFace *f, float r_tangent[3]) +{ + const BMLoop *l_long = BM_face_find_longest_loop((BMFace *)f); + + sub_v3_v3v3(r_tangent, l_long->v->co, l_long->next->v->co); + + normalize_v3(r_tangent); + +} + +/** + * Compute the tanget of the face, using the two longest disconected edges. + * + * \param r_tangent: Calculated unit length tangent (return value). + */ +void BM_face_calc_tangent_edge_pair(const BMFace *f, float r_tangent[3]) { if (f->len == 3) { BMVert *verts[3]; BM_face_as_array_vert_tri((BMFace *)f, verts); - BM_vert_tri_calc_plane(verts, r_plane); + BM_vert_tri_calc_tangent_edge_pair(verts, r_tangent); } else if (f->len == 4) { + /* Use longest edge pair */ BMVert *verts[4]; float vec[3], vec_a[3], vec_b[3]; - // BM_iter_as_array(NULL, BM_VERTS_OF_FACE, efa, (void **)verts, 4); BM_face_as_array_vert_quad((BMFace *)f, verts); sub_v3_v3v3(vec_a, verts[3]->co, verts[2]->co); sub_v3_v3v3(vec_b, verts[0]->co, verts[1]->co); - add_v3_v3v3(r_plane, vec_a, vec_b); + add_v3_v3v3(r_tangent, vec_a, vec_b); sub_v3_v3v3(vec_a, verts[0]->co, verts[3]->co); sub_v3_v3v3(vec_b, verts[1]->co, verts[2]->co); add_v3_v3v3(vec, vec_a, vec_b); - /* use the biggest edge length */ - if (len_squared_v3(r_plane) < len_squared_v3(vec)) { - copy_v3_v3(r_plane, vec); + /* use the longest edge length */ + if (len_squared_v3(r_tangent) < len_squared_v3(vec)) { + copy_v3_v3(r_tangent, vec); } } else { - const BMLoop *l_long = BM_face_find_longest_loop((BMFace *)f); + /* For ngons use two longest disconnected edges */ + BMLoop *l_long = BM_face_find_longest_loop((BMFace *)f); + BMLoop *l_long_other = NULL; - sub_v3_v3v3(r_plane, l_long->v->co, l_long->next->v->co); + float len_max_sq = 0.0f; + float vec_a[3], vec_b[3]; + + BMLoop *l_iter = l_long->prev->prev; + BMLoop *l_last = l_long->next; + + do { + const float len_sq = len_squared_v3v3(l_iter->v->co, l_iter->next->v->co); + if (len_sq >= len_max_sq) { + l_long_other = l_iter; + len_max_sq = len_sq; + } + } while ((l_iter = l_iter->prev) != l_last); + + sub_v3_v3v3(vec_a, l_long->next->v->co, l_long->v->co); + sub_v3_v3v3(vec_b, l_long_other->v->co, l_long_other->next->v->co); + add_v3_v3v3(r_tangent, vec_a, vec_b); + + /* Edges may not be opposite side of the ngon, + * this could cause problems for ngons with multiple-aligned edges of the same length. + * Fallback to longest edge. */ + if (UNLIKELY(normalize_v3(r_tangent) == 0.0f)) { + normalize_v3_v3(r_tangent, vec_a); + } } +} - normalize_v3(r_plane); +/** + * Compute the tanget of the face, using the edge farthest away from any vertex in the face. + * + * \param r_tangent: Calculated unit length tangent (return value). + */ +void BM_face_calc_tangent_edge_diagonal(const BMFace *f, float r_tangent[3]) +{ + BMLoop *l_iter, *l_first; + + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + + /* incase of degenerate faces */ + zero_v3(r_tangent); + + /* warning: O(n^2) loop here, take care! */ + float dist_max_sq = 0.0f; + do { + BMLoop *l_iter_other = l_iter->next; + BMLoop *l_iter_last = l_iter->prev; + do { + BLI_assert(!ELEM(l_iter->v->co, l_iter_other->v->co, l_iter_other->next->v->co)); + float co_other[3], vec[3]; + closest_to_line_segment_v3(co_other, l_iter->v->co, l_iter_other->v->co, l_iter_other->next->v->co); + sub_v3_v3v3(vec, l_iter->v->co, co_other); + + const float dist_sq = len_squared_v3(vec); + if (dist_sq > dist_max_sq) { + dist_max_sq = dist_sq; + copy_v3_v3(r_tangent, vec); + } + } while ((l_iter_other = l_iter_other->next) != l_iter_last); + } while ((l_iter = l_iter->next) != l_first); + + normalize_v3(r_tangent); +} + +/** + * Compute the tanget of the face, using longest distance between vertices on the face. + * + * \note The logic is almost identical to #BM_face_calc_tangent_edge_diagonal + */ +void BM_face_calc_tangent_vert_diagonal(const BMFace *f, float r_tangent[3]) +{ + BMLoop *l_iter, *l_first; + + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + + /* incase of degenerate faces */ + zero_v3(r_tangent); + + /* warning: O(n^2) loop here, take care! */ + float dist_max_sq = 0.0f; + do { + BMLoop *l_iter_other = l_iter->next; + do { + float vec[3]; + sub_v3_v3v3(vec, l_iter->v->co, l_iter_other->v->co); + + const float dist_sq = len_squared_v3(vec); + if (dist_sq > dist_max_sq) { + dist_max_sq = dist_sq; + copy_v3_v3(r_tangent, vec); + } + } while ((l_iter_other = l_iter_other->next) != l_iter); + } while ((l_iter = l_iter->next) != l_first); + + normalize_v3(r_tangent); +} + +/** + * Compute a meaningful direction along the face (use for manipulator axis). + * + * \note Callers shouldn't depend on the *exact* method used here. + */ +void BM_face_calc_tangent_auto(const BMFace *f, float r_tangent[3]) +{ + if (f->len == 3) { + /* most 'unique' edge of a triangle */ + BMVert *verts[3]; + BM_face_as_array_vert_tri((BMFace *)f, verts); + BM_vert_tri_calc_tangent_edge(verts, r_tangent); + } + else if (f->len == 4) { + /* longest edge pair of a quad */ + BM_face_calc_tangent_edge_pair((BMFace *)f, r_tangent); + } + else { + /* longest edge of an ngon */ + BM_face_calc_tangent_edge((BMFace *)f, r_tangent); + } } /** diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h index 8f0df81af73..1e50a504875 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/source/blender/bmesh/intern/bmesh_polygon.h @@ -45,7 +45,11 @@ float BM_face_calc_normal_vcos( float BM_face_calc_normal_subset(const BMLoop *l_first, const BMLoop *l_last, float r_no[3]) ATTR_NONNULL(); float BM_face_calc_area(const BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); float BM_face_calc_perimeter(const BMFace *f) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); -void BM_face_calc_plane(const BMFace *f, float r_plane[3]) ATTR_NONNULL(); +void BM_face_calc_tangent_edge(const BMFace *f, float r_plane[3]) ATTR_NONNULL(); +void BM_face_calc_tangent_edge_pair(const BMFace *f, float r_plane[3]) ATTR_NONNULL(); +void BM_face_calc_tangent_edge_diagonal(const BMFace *f, float r_plane[3]) ATTR_NONNULL(); +void BM_face_calc_tangent_vert_diagonal(const BMFace *f, float r_plane[3]) ATTR_NONNULL(); +void BM_face_calc_tangent_auto(const BMFace *f, float r_plane[3]) ATTR_NONNULL(); void BM_face_calc_center_bounds(const BMFace *f, float center[3]) ATTR_NONNULL(); void BM_face_calc_center_mean(const BMFace *f, float center[3]) ATTR_NONNULL(); void BM_face_calc_center_mean_vcos( @@ -90,6 +94,7 @@ void BM_face_as_array_vert_quad(BMFace *f, BMVert *r_verts[4]) ATTR_NONNULL(); void BM_face_as_array_loop_tri(BMFace *f, BMLoop *r_loops[3]) ATTR_NONNULL(); void BM_face_as_array_loop_quad(BMFace *f, BMLoop *r_loops[4]) ATTR_NONNULL(); -void BM_vert_tri_calc_plane(BMVert *verts[3], float r_plane[3]); +void BM_vert_tri_calc_tangent_edge(BMVert *verts[3], float r_tangent[3]); +void BM_vert_tri_calc_tangent_edge_pair(BMVert *verts[3], float r_tangent[3]); #endif /* __BMESH_POLYGON_H__ */ diff --git a/source/blender/editors/transform/transform_orientations.c b/source/blender/editors/transform/transform_orientations.c index 59d2485c964..90a4aa3614d 100644 --- a/source/blender/editors/transform/transform_orientations.c +++ b/source/blender/editors/transform/transform_orientations.c @@ -636,7 +636,7 @@ int getTransformOrientation_ex(const bContext *C, float normal[3], float plane[3 BM_ITER_MESH (efa, &iter, em->bm, BM_FACES_OF_MESH) { if (BM_elem_flag_test(efa, BM_ELEM_SELECT)) { - BM_face_calc_plane(efa, vec); + BM_face_calc_tangent_auto(efa, vec); add_v3_v3(normal, efa->no); add_v3_v3(plane, vec); } @@ -690,7 +690,7 @@ int getTransformOrientation_ex(const bContext *C, float normal[3], float plane[3 sub_v3_v3v3(plane, v_pair[0]->co, v_pair[1]->co); } else { - BM_vert_tri_calc_plane(v_tri, plane); + BM_vert_tri_calc_tangent_edge(v_tri, plane); } } else { diff --git a/source/blender/python/bmesh/bmesh_py_types.c b/source/blender/python/bmesh/bmesh_py_types.c index a0722af522b..fe4360d1e3b 100644 --- a/source/blender/python/bmesh/bmesh_py_types.c +++ b/source/blender/python/bmesh/bmesh_py_types.c @@ -1803,6 +1803,82 @@ static PyObject *bpy_bmface_calc_perimeter(BPy_BMFace *self) } +PyDoc_STRVAR(bpy_bmface_calc_tangent_edge_doc, +".. method:: calc_tangent_edge()\n" +"\n" +" Return face tangent based on longest edge.\n" +"\n" +" :return: a normalized vector.\n" +" :rtype: :class:`mathutils.Vector`\n" +); +static PyObject *bpy_bmface_calc_tangent_edge(BPy_BMFace *self) +{ + float tangent[3]; + + BPY_BM_CHECK_OBJ(self); + BM_face_calc_tangent_edge(self->f, tangent); + return Vector_CreatePyObject(tangent, 3, NULL); +} + + +PyDoc_STRVAR(bpy_bmface_calc_tangent_edge_pair_doc, +".. method:: calc_tangent_edge_pair()\n" +"\n" +" Return face tangent based on the two longest disconected edges.\n" +"\n" +" - Tris: Use the edge pair with the most similar lengths.\n" +" - Quads: Use the longest edge pair.\n" +" - NGons: Use the two longest disconnected edges.\n" +"\n" +" :return: a normalized vector.\n" +" :rtype: :class:`mathutils.Vector`\n" +); +static PyObject *bpy_bmface_calc_tangent_edge_pair(BPy_BMFace *self) +{ + float tangent[3]; + + BPY_BM_CHECK_OBJ(self); + BM_face_calc_tangent_edge_pair(self->f, tangent); + return Vector_CreatePyObject(tangent, 3, NULL); +} + + +PyDoc_STRVAR(bpy_bmface_calc_tangent_edge_diagonal_doc, +".. method:: calc_tangent_edge_diagonal()\n" +"\n" +" Return face tangent based on the edge farthest from any vertex.\n" +"\n" +" :return: a normalized vector.\n" +" :rtype: :class:`mathutils.Vector`\n" +); +static PyObject *bpy_bmface_calc_tangent_edge_diagonal(BPy_BMFace *self) +{ + float tangent[3]; + + BPY_BM_CHECK_OBJ(self); + BM_face_calc_tangent_edge_diagonal(self->f, tangent); + return Vector_CreatePyObject(tangent, 3, NULL); +} + + +PyDoc_STRVAR(bpy_bmface_calc_tangent_vert_diagonal_doc, +".. method:: calc_tangent_vert_diagonal()\n" +"\n" +" Return face tangent based on the two most distent vertices.\n" +"\n" +" :return: a normalized vector.\n" +" :rtype: :class:`mathutils.Vector`\n" +); +static PyObject *bpy_bmface_calc_tangent_vert_diagonal(BPy_BMFace *self) +{ + float tangent[3]; + + BPY_BM_CHECK_OBJ(self); + BM_face_calc_tangent_vert_diagonal(self->f, tangent); + return Vector_CreatePyObject(tangent, 3, NULL); +} + + PyDoc_STRVAR(bpy_bmface_calc_center_mean_doc, ".. method:: calc_center_median()\n" "\n" @@ -2702,6 +2778,10 @@ static struct PyMethodDef bpy_bmface_methods[] = { {"calc_area", (PyCFunction)bpy_bmface_calc_area, METH_NOARGS, bpy_bmface_calc_area_doc}, {"calc_perimeter", (PyCFunction)bpy_bmface_calc_perimeter, METH_NOARGS, bpy_bmface_calc_perimeter_doc}, + {"calc_tangent_edge", (PyCFunction)bpy_bmface_calc_tangent_edge, METH_NOARGS, bpy_bmface_calc_tangent_edge_doc}, + {"calc_tangent_edge_pair", (PyCFunction)bpy_bmface_calc_tangent_edge_pair, METH_NOARGS, bpy_bmface_calc_tangent_edge_pair_doc}, + {"calc_tangent_edge_diagonal", (PyCFunction)bpy_bmface_calc_tangent_edge_diagonal, METH_NOARGS, bpy_bmface_calc_tangent_edge_diagonal_doc}, + {"calc_tangent_vert_diagonal", (PyCFunction)bpy_bmface_calc_tangent_vert_diagonal, METH_NOARGS, bpy_bmface_calc_tangent_vert_diagonal_doc}, {"calc_center_median", (PyCFunction)bpy_bmface_calc_center_mean, METH_NOARGS, bpy_bmface_calc_center_mean_doc}, {"calc_center_median_weighted", (PyCFunction)bpy_bmface_calc_center_mean_weighted, METH_NOARGS, bpy_bmface_calc_center_mean_weighted_doc}, {"calc_center_bounds", (PyCFunction)bpy_bmface_calc_center_bounds, METH_NOARGS, bpy_bmface_calc_center_bounds_doc}, -- cgit v1.2.3