diff options
| -rw-r--r-- | source/blender/blenlib/BLI_math_matrix.h | 1 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/math_matrix.c | 7 | ||||
| -rw-r--r-- | source/blender/blenlib/intern/math_rotation.c | 2 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.c | 195 | ||||
| -rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.h | 2 | ||||
| -rw-r--r-- | source/blender/bmesh/tools/bmesh_triangulate.c | 15 |
6 files changed, 83 insertions, 139 deletions
diff --git a/source/blender/blenlib/BLI_math_matrix.h b/source/blender/blenlib/BLI_math_matrix.h index 415c503146c..c66536bc0e5 100644 --- a/source/blender/blenlib/BLI_math_matrix.h +++ b/source/blender/blenlib/BLI_math_matrix.h @@ -95,6 +95,7 @@ void mul_project_m4_v3(float M[4][4], float vec[3]); void mul_m3_v3(float M[3][3], float r[3]); void mul_v3_m3v3(float r[3], float M[3][3], float a[3]); +void mul_v2_m3v3(float r[2], float M[3][3], float a[3]); void mul_transposed_m3_v3(float M[3][3], float r[3]); void mul_m3_v3_double(float M[3][3], double r[3]); diff --git a/source/blender/blenlib/intern/math_matrix.c b/source/blender/blenlib/intern/math_matrix.c index 8f9ea917b8c..b7e7fea897f 100644 --- a/source/blender/blenlib/intern/math_matrix.c +++ b/source/blender/blenlib/intern/math_matrix.c @@ -411,6 +411,13 @@ void mul_v3_m3v3(float r[3], float M[3][3], float a[3]) r[2] = M[0][2] * a[0] + M[1][2] * a[1] + M[2][2] * a[2]; } +void mul_v2_m3v3(float r[2], float M[3][3], float a[3]) +{ + r[0] = M[0][0] * a[0] + M[1][0] * a[1] + M[2][0] * a[2]; + r[1] = M[0][1] * a[0] + M[1][1] * a[1] + M[2][1] * a[2]; + r[2] = M[0][2] * a[0] + M[1][2] * a[1] + M[2][2] * a[2]; +} + void mul_m3_v3(float M[3][3], float r[3]) { float tmp[3]; diff --git a/source/blender/blenlib/intern/math_rotation.c b/source/blender/blenlib/intern/math_rotation.c index b38b5a2de10..e6399ed356e 100644 --- a/source/blender/blenlib/intern/math_rotation.c +++ b/source/blender/blenlib/intern/math_rotation.c @@ -84,6 +84,8 @@ void mul_qt_qtqt(float q[4], const float q1[4], const float q2[4]) * \note: * Assumes a unit quaternion? * + * \note: multiplying by 3x3 matrix is ~25% faster. + * * in fact not, but you may want to use a unit quat, read on... * * Shortcut for 'q v q*' when \a v is actually a quaternion. diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index b8b7abdbc76..af8ae5f9454 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -297,39 +297,51 @@ static void scale_edge_v3f(float v1[3], float v2[3], const float fac) add_v3_v3v3(v2, v2, mid); } - /** - * \brief POLY ROTATE PLANE + * \brief POLY NORMAL TO MATRIX * - * Rotates a polygon so that it's - * normal is pointing towards the mesh Z axis + * Creates a 3x3 matrix from a normal. */ -void poly_rotate_plane(const float normal[3], float (*verts)[3], const int nverts) +static bool poly_normal_to_xy_mat3(float r_mat[3][3], const float normal[3]) { - - float up[3] = {0.0f, 0.0f, 1.0f}, axis[3], q[4]; - float mat[3][3]; + float up[3] = {0.0f, 0.0f, 1.0f}, axis[3]; float angle; - int i; cross_v3_v3v3(axis, normal, up); - angle = saacos(dot_v3v3(normal, up)); - if (angle < FLT_EPSILON) - return; + if (angle >= FLT_EPSILON) { + if (len_squared_v3(axis) < FLT_EPSILON) { + axis[0] = 0.0f; + axis[1] = 1.0f; + axis[2] = 0.0f; + } - if (len_squared_v3(axis) < FLT_EPSILON) { - axis[0] = 0.0f; - axis[1] = 1.0f; - axis[2] = 0.0f; + axis_angle_to_mat3(r_mat, axis, angle); + return true; } + else { + unit_m3(r_mat); + return false; + } +} - axis_angle_to_quat(q, axis, angle); - quat_to_mat3(mat, q); +/** + * \brief POLY ROTATE PLANE + * + * Rotates a polygon so that it's + * normal is pointing towards the mesh Z axis + */ +void poly_rotate_plane(const float normal[3], float (*verts)[3], const int nverts) +{ + float mat[3][3]; - for (i = 0; i < nverts; i++) - mul_m3_v3(mat, verts[i]); + if (poly_normal_to_xy_mat3(mat, normal)) { + int i; + for (i = 0; i < nverts; i++) { + mul_m3_v3(mat, verts[i]); + } + } } /** @@ -614,16 +626,16 @@ bool BM_face_point_inside_test(BMFace *f, const float co[3]) return crosses % 2 != 0; } -static bool bm_face_goodline(float const (*projectverts)[3], BMFace *f, int v1i, int v2i, int v3i) +static bool bm_face_goodline(float const (*projectverts)[2], BMFace *f, int v1i, int v2i, int v3i) { BMLoop *l_iter; BMLoop *l_first; - float v1[3], v2[3], v3[3], pv1[3]; - int i; - copy_v3_v3(v1, projectverts[v1i]); - copy_v3_v3(v2, projectverts[v2i]); - copy_v3_v3(v3, projectverts[v3i]); + float pv1[2]; + const float *v1 = projectverts[v1i]; + const float *v2 = projectverts[v2i]; + const float *v3 = projectverts[v3i]; + int i; /* v3 must be on the left side of [v1, v2] line, else we know [v1, v3] is outside of f! */ if (testedgesidef(v1, v2, v3)) { @@ -633,7 +645,7 @@ static bool bm_face_goodline(float const (*projectverts)[3], BMFace *f, int v1i, l_iter = l_first = BM_FACE_FIRST_LOOP(f); do { i = BM_elem_index_get(l_iter->v); - copy_v3_v3(pv1, projectverts[i]); + copy_v2_v2(pv1, projectverts[i]); if (ELEM3(i, v1i, v2i, v3i)) { #if 0 @@ -665,7 +677,7 @@ static bool bm_face_goodline(float const (*projectverts)[3], BMFace *f, int v1i, * \param abscoss Must be allocated by caller, and at least f->len length * (allow to avoid allocating a new one for each tri!). */ -static BMLoop *find_ear(BMFace *f, float (*verts)[3], const bool use_beauty, float *abscoss) +static BMLoop *find_ear(BMFace *f, float (*projectverts)[2], const bool use_beauty, float *abscoss) { BMLoop *bestear = NULL; @@ -711,7 +723,7 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const bool use_beauty, flo /* Last check we do not get overlapping triangles * (as much as possible, there are some cases with no good solution!) */ i4 = (i + 3) % 4; - if (!bm_face_goodline((float const (*)[3])verts, f, BM_elem_index_get(larr[i4]->v), + if (!bm_face_goodline((float const (*)[2])projectverts, f, BM_elem_index_get(larr[i4]->v), BM_elem_index_get(larr[i]->v), BM_elem_index_get(larr[i + 1]->v))) { i = !i; @@ -756,7 +768,7 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const bool use_beauty, flo if (BM_edge_exists(v1, v3)) { is_ear = false; } - else if (!bm_face_goodline((float const (*)[3])verts, f, BM_elem_index_get(v1), + else if (!bm_face_goodline((float const (*)[2])projectverts, f, BM_elem_index_get(v1), BM_elem_index_get(v2), BM_elem_index_get(v3))) { #if 0 @@ -767,19 +779,6 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const bool use_beauty, flo } if (is_ear) { -#if 0 /* Old, already commented code */ - /* if this code comes back, it needs to be converted to radians */ - angle = angle_v3v3v3(verts[v1->head.eflag2], verts[v2->head.eflag2], verts[v3->head.eflag2]); - if (!bestear || ABS(angle - 45.0f) < bestangle) { - bestear = l; - bestangle = ABS(45.0f - angle); - } - - if (angle > 20 && angle < 90) break; - if (angle < 100 && i > 5) break; - i += 1; -#endif - /* Compute highest cos (i.e. narrowest angle) of this tri. */ cos = *tcoss; tcos = fabsf(cos_v3v3v3(v2->co, v3->co, v1->co)); @@ -839,50 +838,39 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const bool use_beauty, flo * produces a "remaining" face with too much wide/narrow angles * (using cos (i.e. dot product of normalized vectors) of angles). * - * newfaces, if non-null, must be an array of BMFace pointers, - * with a length equal to f->len. It will be filled with the new - * triangles, and will be NULL-terminated. + * \param r_faces_new if non-null, must be an array of BMFace pointers, + * with a length equal to (f->len - 2). It will be filled with the new + * triangles. * * \note newedgeflag sets a flag layer flag, obviously not the header flag. */ void BM_face_triangulate(BMesh *bm, BMFace *f, - float (*projectverts)[3], BMFace **newfaces, + BMFace **r_faces_new, const bool use_beauty, const bool use_tag) { - int i, nvert, nf_i = 0; - bool done; - BMLoop *newl; + const float f_len_orig = f->len; + int i, nf_i = 0; + BMLoop *l_new; BMLoop *l_iter; BMLoop *l_first; /* BM_face_triangulate: temp absolute cosines of face corners */ - float *abscoss = BLI_array_alloca(abscoss, f->len); + float (*projectverts)[2] = BLI_array_alloca(projectverts, f_len_orig); + float *abscoss = BLI_array_alloca(abscoss, f_len_orig); + float mat[3][3]; + + poly_normal_to_xy_mat3(mat, f->no); /* copy vertex coordinates to vertspace area */ i = 0; l_iter = l_first = BM_FACE_FIRST_LOOP(f); do { - copy_v3_v3(projectverts[i], l_iter->v->co); - BM_elem_index_set(l_iter->v, i); /* set dirty! */ - i++; + mul_v2_m3v3(projectverts[i], mat, l_iter->v->co); + BM_elem_index_set(l_iter->v, i++); /* set dirty! */ } while ((l_iter = l_iter->next) != l_first); bm->elem_index_dirty |= BM_VERT; /* see above */ - /* bmesh_face_normal_update(bm, f, f->no, projectverts); */ - - calc_poly_normal(f->no, projectverts, f->len); - poly_rotate_plane(f->no, projectverts, i); - - nvert = f->len; - - /* calc_poly_plane(projectverts, i); */ - for (i = 0; i < nvert; i++) { - projectverts[i][2] = 0.0f; - } - - done = false; - while (!done && f->len > 3) { - done = true; + while (f->len > 3) { l_iter = find_ear(f, projectverts, use_beauty, abscoss); /* force triangulation - if we can't find an ear the face is degenerate */ @@ -890,70 +878,27 @@ void BM_face_triangulate(BMesh *bm, BMFace *f, l_iter = BM_FACE_FIRST_LOOP(f); } - { - done = false; -/* printf("Subdividing face...\n");*/ - f = BM_face_split(bm, l_iter->f, l_iter->prev->v, l_iter->next->v, &newl, NULL, true); - - if (UNLIKELY(!f)) { - fprintf(stderr, "%s: triangulator failed to split face! (bmesh internal error)\n", __func__); - break; - } - - copy_v3_v3(f->no, l_iter->f->no); - - if (use_tag) { - BM_elem_flag_enable(newl->e, BM_ELEM_TAG); - BM_elem_flag_enable(f, BM_ELEM_TAG); - } - - if (newfaces) - newfaces[nf_i++] = f; - -#if 0 - l = f->loopbase; - do { - if (l->v == v) { - f->loopbase = l; - break; - } - l = l->next; - } while (l != f->loopbase); -#endif +/* printf("Subdividing face...\n");*/ + f = BM_face_split(bm, l_iter->f, l_iter->prev->v, l_iter->next->v, &l_new, NULL, true); + if (UNLIKELY(!f)) { + fprintf(stderr, "%s: triangulator failed to split face! (bmesh internal error)\n", __func__); + break; } - } - BLI_assert(f->len == 3); + copy_v3_v3(f->no, l_iter->f->no); -#if 0 /* XXX find_ear should now always return a corner, so no more need for this piece of code... */ - if (f->len > 3) { - l_iter = BM_FACE_FIRST_LOOP(f); - while (l_iter->f->len > 3) { - nextloop = l_iter->next->next; - f = BM_face_split(bm, l_iter->f, l_iter->v, nextloop->v, - &newl, NULL, true); - if (!f) { - printf("triangle fan step of triangulator failed.\n"); - - /* NULL-terminate */ - if (newfaces) newfaces[nf_i] = NULL; - return; - } + if (use_tag) { + BM_elem_flag_enable(l_new->e, BM_ELEM_TAG); + BM_elem_flag_enable(f, BM_ELEM_TAG); + } - if (newfaces) newfaces[nf_i++] = f; - - BMO_elem_flag_enable(bm, newl->e, newedge_oflag); - BMO_elem_flag_enable(bm, f, newface_oflag); - l_iter = nextloop; + if (r_faces_new) { + r_faces_new[nf_i++] = f; } } -#endif - /* NULL-terminate */ - if (newfaces) { - newfaces[nf_i] = NULL; - } + BLI_assert(f->len == 3); } /** diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h index 7c2b1782584..601caae2337 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/source/blender/bmesh/intern/bmesh_polygon.h @@ -44,7 +44,7 @@ void BM_vert_normal_update_all(BMVert *v); void BM_face_normal_flip(BMesh *bm, BMFace *f); bool BM_face_point_inside_test(BMFace *f, const float co[3]); -void BM_face_triangulate(BMesh *bm, BMFace *f, float (*projectverts)[3], BMFace **newfaces, +void BM_face_triangulate(BMesh *bm, BMFace *f, BMFace **newfaces, const bool use_beauty, const bool use_tag); void BM_face_legal_splits(BMesh *bm, BMFace *f, BMLoop *(*loops)[2], int len); diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c index 7e6e41a12e6..9948a15ea56 100644 --- a/source/blender/bmesh/tools/bmesh_triangulate.c +++ b/source/blender/bmesh/tools/bmesh_triangulate.c @@ -30,7 +30,6 @@ #include "MEM_guardedalloc.h" #include "BLI_utildefines.h" -#include "BLI_array.h" #include "bmesh.h" @@ -40,27 +39,17 @@ void BM_mesh_triangulate(BMesh *bm, const bool use_beauty, const bool tag_only) { BMIter iter; BMFace *face; - float (*projectverts)[3] = NULL; - BLI_array_declare(projectverts); if (tag_only == false) { BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) { - BLI_array_empty(projectverts); - BLI_array_reserve(projectverts, face->len * 3); - - BM_face_triangulate(bm, face, projectverts, NULL, use_beauty, false); + BM_face_triangulate(bm, face, NULL, use_beauty, false); } } else { BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) { if (BM_elem_flag_test(face, BM_ELEM_TAG)) { - BLI_array_empty(projectverts); - BLI_array_grow_items(projectverts, face->len * 3); - - BM_face_triangulate(bm, face, projectverts, NULL, use_beauty, true); + BM_face_triangulate(bm, face, NULL, use_beauty, true); } } } - - BLI_array_free(projectverts); } |