bmesh py api: expose BM_face_calc_tangent_*
authorCampbell Barton <ideasman42@gmail.com>
Sun, 12 Jun 2016 02:22:38 +0000 (12:22 +1000)
committerCampbell Barton <ideasman42@gmail.com>
Sun, 12 Jun 2016 05:12:34 +0000 (15:12 +1000)
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
source/blender/bmesh/intern/bmesh_polygon.c
source/blender/bmesh/intern/bmesh_polygon.h
source/blender/editors/transform/transform_orientations.c
source/blender/python/bmesh/bmesh_py_types.c

index 3fe888736f06a46461adef1f990286a511b17fae..d6ca7239e39d482c8c154b2d2e77b2aa61737b20 100644 (file)
@@ -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);
        }
 }
 
index 62b29e61d08ce6340ef5e2a363aed371e1ae422d..79051a2490f1c1dbf8ef7b829747a26ffb899153 100644 (file)
@@ -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);
+       }
 }
 
 /**
index 8f0df81af73d76b8ba3e1db6fb250f0af9ddddf4..1e50a504875daa59116d086d3fb3231e5b2bb1a3 100644 (file)
@@ -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__ */
index 59d2485c964f710340b9c3221fdba263698d0e82..90a4aa3614dad07454dd9ecf252af98b93aa417f 100644 (file)
@@ -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 {
index a0722af522b1bd5e706e89c2f3f4149b92d45e60..fe4360d1e3b29a30f944ec435955daf04c7ef3c6 100644 (file)
@@ -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},