diff options
author | Campbell Barton <ideasman42@gmail.com> | 2013-01-29 19:05:23 +0400 |
---|---|---|
committer | Campbell Barton <ideasman42@gmail.com> | 2013-01-29 19:05:23 +0400 |
commit | 2b875a947ff831dd8f7d4b5bc2d5df10f614864d (patch) | |
tree | 768be65da6d7433515bb17a4e2897c1ed30b32ef /source | |
parent | d18fca88b9b292631b02fe98055372d4746866c3 (diff) |
skip calculating the normal for each face when triangulating, all callers make sure its valid. also remove some commented code (more then one generation of bmesh old).
Diffstat (limited to 'source')
-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); } |