diff options
author | Tamito Kajiyama <rd6t-kjym@asahi-net.or.jp> | 2013-02-10 14:17:59 +0400 |
---|---|---|
committer | Tamito Kajiyama <rd6t-kjym@asahi-net.or.jp> | 2013-02-10 14:17:59 +0400 |
commit | ac9ec06ec121589fedbfeaa10137140b45bfd668 (patch) | |
tree | ab08f9528136f0b8813593b78621f869d98d655e /source/blender/bmesh | |
parent | 3c064f4553e4be988fe4fcec450b59b935fa3c80 (diff) | |
parent | 63af7068ad17f30a526ccb81fbe74253b064bc89 (diff) |
Merged changes in the trunk up to revision 54421.
Conflicts resolved:
release/datafiles/startup.blend
release/scripts/startup/bl_ui/properties_render.py
source/blender/SConscript
source/blender/blenloader/intern/readfile.c
Diffstat (limited to 'source/blender/bmesh')
-rw-r--r-- | source/blender/bmesh/CMakeLists.txt | 2 | ||||
-rw-r--r-- | source/blender/bmesh/bmesh.h | 3 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_log.c | 16 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh.c | 2 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_mesh_conv.c | 10 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_opdefines.c | 5 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_operators.c | 6 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.c | 242 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.h | 5 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_queries.c | 66 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_queries.h | 4 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_walkers_impl.c | 2 | ||||
-rw-r--r-- | source/blender/bmesh/operators/bmo_connect.c | 11 | ||||
-rw-r--r-- | source/blender/bmesh/operators/bmo_triangulate.c | 104 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_bevel.c | 13 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_triangulate.c | 87 | ||||
-rw-r--r-- | source/blender/bmesh/tools/bmesh_triangulate.h | 36 |
17 files changed, 362 insertions, 252 deletions
diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt index d49686f204a..bf719a5c790 100644 --- a/source/blender/bmesh/CMakeLists.txt +++ b/source/blender/bmesh/CMakeLists.txt @@ -114,6 +114,8 @@ set(SRC tools/bmesh_decimate.h tools/bmesh_edgesplit.c tools/bmesh_edgesplit.h + tools/bmesh_triangulate.c + tools/bmesh_triangulate.h bmesh.h bmesh_class.h diff --git a/source/blender/bmesh/bmesh.h b/source/blender/bmesh/bmesh.h index f593f78bab7..3b33513b575 100644 --- a/source/blender/bmesh/bmesh.h +++ b/source/blender/bmesh/bmesh.h @@ -268,8 +268,9 @@ extern "C" { #include "intern/bmesh_inline.h" -#include "tools/bmesh_decimate.h" #include "tools/bmesh_bevel.h" +#include "tools/bmesh_decimate.h" +#include "tools/bmesh_triangulate.h" #ifdef __cplusplus } diff --git a/source/blender/bmesh/intern/bmesh_log.c b/source/blender/bmesh/intern/bmesh_log.c index 1337cb7c8eb..36a5412e401 100644 --- a/source/blender/bmesh/intern/bmesh_log.c +++ b/source/blender/bmesh/intern/bmesh_log.c @@ -252,8 +252,22 @@ static void bm_log_faces_unmake(BMesh *bm, BMLog *log, GHash *faces) void *key = BLI_ghashIterator_getKey(&gh_iter); unsigned int id = GET_INT_FROM_POINTER(key); BMFace *f = bm_log_face_from_id(log, id); + BMEdge *e_tri[3]; + BMLoop *l_iter; + int i; + l_iter = BM_FACE_FIRST_LOOP(f); + for (i = 0; i < 3; i++, l_iter = l_iter->next) { + e_tri[i] = l_iter->e; + } + + /* Remove any unused edges */ BM_face_kill(bm, f); + for (i = 0; i < 3; i++) { + if (BM_edge_is_wire(e_tri[i])) { + BM_edge_kill(bm, e_tri[i]); + } + } } } @@ -722,7 +736,7 @@ void BM_log_redo(BMesh *bm, BMLog *log) * vertex in the map of added vertices. * * If the vertex already existed prior to the current log entry, a - * seperate key/value map of modified vertices is used (using the + * separate key/value map of modified vertices is used (using the * vertex's ID as the key). The values stored in that case are * the vertex's original state so that an undo can restore the * previous state. diff --git a/source/blender/bmesh/intern/bmesh_mesh.c b/source/blender/bmesh/intern/bmesh_mesh.c index e72ad5dae3c..3c4fa490477 100644 --- a/source/blender/bmesh/intern/bmesh_mesh.c +++ b/source/blender/bmesh/intern/bmesh_mesh.c @@ -245,7 +245,7 @@ void BM_mesh_free(BMesh *bm) BM_mesh_data_free(bm); if (bm->py_handle) { - /* keep this out of 'BM_mesh_data_free' because we wan't python + /* keep this out of 'BM_mesh_data_free' because we want python * to be able to clear the mesh and maintain access. */ extern void bpy_bm_generic_invalidate(void *self); diff --git a/source/blender/bmesh/intern/bmesh_mesh_conv.c b/source/blender/bmesh/intern/bmesh_mesh_conv.c index a63b715fd14..6697430a88d 100644 --- a/source/blender/bmesh/intern/bmesh_mesh_conv.c +++ b/source/blender/bmesh/intern/bmesh_mesh_conv.c @@ -162,7 +162,11 @@ char BM_mesh_cd_flag_from_bmesh(BMesh *bm) return cd_flag; } -/* Mesh -> BMesh */ +/** + * \brief Mesh -> BMesh + * + * \warning This function doesn't calculate face normals. + */ void BM_mesh_bm_from_me(BMesh *bm, Mesh *me, bool set_key, int act_key_nr) { MVert *mvert; @@ -465,7 +469,9 @@ void BM_mesh_bm_from_me(BMesh *bm, Mesh *me, bool set_key, int act_key_nr) } -/* BMesh -> Mesh */ +/** + * \brief BMesh -> Mesh + */ static BMVert **bm_to_mesh_vertex_map(BMesh *bm, int ototvert) { BMVert **vertMap = NULL; diff --git a/source/blender/bmesh/intern/bmesh_opdefines.c b/source/blender/bmesh/intern/bmesh_opdefines.c index 4147da82363..c5eeceb43a3 100644 --- a/source/blender/bmesh/intern/bmesh_opdefines.c +++ b/source/blender/bmesh/intern/bmesh_opdefines.c @@ -1436,7 +1436,7 @@ static BMOpDefine bmo_beautify_fill_def = { "beautify_fill", /* slots_in */ {{"faces", BMO_OP_SLOT_ELEMENT_BUF, {BM_FACE}}, /* input faces */ - {"constrain_edges", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}}, /* edges that can't be flipped */ + {"edges", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}}, /* edges that can be flipped */ {{'\0'}}, }, /* slots_out */ @@ -1455,7 +1455,8 @@ static BMOpDefine bmo_beautify_fill_def = { static BMOpDefine bmo_triangle_fill_def = { "triangle_fill", /* slots_in */ - {{"edges", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}}, /* input edges */ + {{"use_beauty", BMO_OP_SLOT_BOOL}, + {"edges", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}}, /* input edges */ {{'\0'}}, }, /* slots_out */ diff --git a/source/blender/bmesh/intern/bmesh_operators.c b/source/blender/bmesh/intern/bmesh_operators.c index 3308a014d25..98958596324 100644 --- a/source/blender/bmesh/intern/bmesh_operators.c +++ b/source/blender/bmesh/intern/bmesh_operators.c @@ -562,7 +562,7 @@ static int bmo_mesh_flag_count(BMesh *bm, const char htype, const short oflag, BMElemF *ele_f; int i; - BLI_assert(ELEM(true, false, test_for_enabled)); + BLI_assert((unsigned int)test_for_enabled <= 1); for (i = 0; i < 3; i++) { if (htype & flag_types[i]) { @@ -938,7 +938,7 @@ static void bmo_slot_buffer_from_flag(BMesh *bm, BMOperator *op, int totelement, i = 0; BLI_assert(op->slots_in == slot_args || op->slots_out == slot_args); - BLI_assert(ELEM(true, false, test_for_enabled)); + BLI_assert((unsigned int)test_for_enabled <= 1); if (test_for_enabled) totelement = BMO_mesh_enabled_flag_count(bm, htype, oflag); @@ -1586,7 +1586,7 @@ static int bmo_opname_to_opcode(const char *opname) * **Utility** * * Pass an existing slot which is copied to either an input or output slot. - * Taking the operator and slot-name pair of args. + * Taking the operator and slot-name pair of args (BMOperator *, const char *). * - `s` - slot_in (lower case) * - `S` - slot_out (upper case) * diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index 5c3d164c768..1aa4d7c5e00 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -297,7 +297,6 @@ static void scale_edge_v3f(float v1[3], float v2[3], const float fac) add_v3_v3v3(v2, v2, mid); } - /** * \brief POLY ROTATE PLANE * @@ -306,30 +305,14 @@ static void scale_edge_v3f(float v1[3], float v2[3], const float fac) */ void poly_rotate_plane(const float normal[3], float (*verts)[3], const int nverts) { - - float up[3] = {0.0f, 0.0f, 1.0f}, axis[3], q[4]; float mat[3][3]; - float angle; - int i; - - cross_v3_v3v3(axis, normal, up); - - angle = saacos(dot_v3v3(normal, up)); - - if (angle < FLT_EPSILON) - return; - if (len_squared_v3(axis) < FLT_EPSILON) { - axis[0] = 0.0f; - axis[1] = 1.0f; - axis[2] = 0.0f; + if (axis_dominant_v3_to_m3(mat, normal)) { + int i; + for (i = 0; i < nverts; i++) { + mul_m3_v3(mat, verts[i]); + } } - - axis_angle_to_quat(q, axis, angle); - quat_to_mat3(mat, q); - - for (i = 0; i < nverts; i++) - mul_m3_v3(mat, verts[i]); } /** @@ -614,16 +597,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 +616,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 @@ -659,13 +642,14 @@ static bool bm_face_goodline(float const (*projectverts)[3], BMFace *f, int v1i, * \brief Find Ear * * Used by tessellator to find the next triangle to 'clip off' of a polygon while tessellating. + * * \param f The face to search. - * \param verts an array of face vert coords. + * \param projectverts an array of face vert coords. * \param use_beauty Currently only applies to quads, can be extended later on. * \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 *poly_find_ear(BMFace *f, float (*projectverts)[2], const bool use_beauty, float *abscoss) { BMLoop *bestear = NULL; @@ -711,7 +695,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; @@ -721,73 +705,38 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const bool use_beauty, flo } else { - BMVert *v1, *v2, *v3; - /* float angle, bestangle = 180.0f; */ - float cos, tcos, bestcos = 1.0f; - float *tcoss; - bool is_ear; - int i = 0, j, len; + float cos, bestcos = 1.0f; + int i, j, len; /* Compute cos of all corners! */ + i = 0; l_iter = l_first = BM_FACE_FIRST_LOOP(f); len = l_iter->f->len; - tcoss = abscoss; do { - v1 = l_iter->prev->v; - v2 = l_iter->v; - v3 = l_iter->next->v; + const BMVert *v1 = l_iter->prev->v; + const BMVert *v2 = l_iter->v; + const BMVert *v3 = l_iter->next->v; - *tcoss = fabsf(cos_v3v3v3(v1->co, v2->co, v3->co)); + abscoss[i] = fabsf(cos_v3v3v3(v1->co, v2->co, v3->co)); /* printf("tcoss: %f\n", *tcoss);*/ - tcoss++; + i++; } while ((l_iter = l_iter->next) != l_first); + i = 0; l_iter = l_first; - tcoss = abscoss; do { - is_ear = true; - - v1 = l_iter->prev->v; - v2 = l_iter->v; - v3 = l_iter->next->v; + const BMVert *v1 = l_iter->prev->v; + const BMVert *v2 = l_iter->v; + const BMVert *v3 = l_iter->next->v; - /* We may have already internal edges... */ - if (BM_edge_exists(v1, v3)) { - is_ear = false; - } - else if (!bm_face_goodline((float const (*)[3])verts, f, BM_elem_index_get(v1), - BM_elem_index_get(v2), BM_elem_index_get(v3))) + 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 - printf("(%d, %d, %d) would not be a valid tri!\n", - BM_elem_index_get(v1), BM_elem_index_get(v2), BM_elem_index_get(v3)); -#endif - is_ear = false; - } - - 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)); - if (tcos > cos) - cos = tcos; - tcos = fabsf(cos_v3v3v3(v3->co, v1->co, v2->co)); - if (tcos > cos) - cos = tcos; + cos = max_fff(abscoss[i], + fabsf(cos_v3v3v3(v2->co, v3->co, v1->co)), + fabsf(cos_v3v3v3(v3->co, v1->co, v2->co))); /* Compare to prev best (i.e. lowest) cos. */ if (cos < bestcos) { @@ -816,7 +765,6 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const bool use_beauty, flo #endif } } - tcoss++; i++; } while ((l_iter = l_iter->next) != l_first); } @@ -827,129 +775,71 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const bool use_beauty, flo /** * \brief BMESH TRIANGULATE FACE * - * --- Prev description (wasn’t correct, ear clipping was currently simply picking the first tri in the loop!) - * Triangulates a face using a simple 'ear clipping' algorithm that tries to - * favor non-skinny triangles (angles less than 90 degrees). - * - * If the triangulator has bits left over (or cannot triangulate at all) - * it uses a simple fan triangulation, - * --- End of prev description - * - * Currently tries to repeatedly find the best triangle (i.e. the most "open" one), provided it does not + * Currently repeatedly find the best triangle (i.e. the most "open" one), provided it does not * 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. + * \note use_tag tags new flags and edges. */ -void BM_face_triangulate(BMesh *bm, BMFace *f, float (*projectverts)[3], const short newedge_oflag, - const short newface_oflag, BMFace **newfaces, const bool use_beauty) +void BM_face_triangulate(BMesh *bm, BMFace *f, + 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]; + + axis_dominant_v3_to_m3(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; - l_iter = find_ear(f, projectverts, use_beauty, abscoss); + while (f->len > 3) { + l_iter = poly_find_ear(f, projectverts, use_beauty, abscoss); /* force triangulation - if we can't find an ear the face is degenerate */ if (l_iter == NULL) { 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); - BMO_elem_flag_enable(bm, newl->e, newedge_oflag); - BMO_elem_flag_enable(bm, f, newface_oflag); - - 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 a0c6ac5eeaa..601caae2337 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/source/blender/bmesh/intern/bmesh_polygon.h @@ -44,9 +44,8 @@ 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], - const short newedge_oflag, const short newface_oflag, BMFace **newfaces, - const bool use_beauty); +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/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c index 7ed23aaf1f8..2284e183d97 100644 --- a/source/blender/bmesh/intern/bmesh_queries.c +++ b/source/blender/bmesh/intern/bmesh_queries.c @@ -763,6 +763,19 @@ int BM_edge_is_manifold(BMEdge *e) #endif /** + * Tests that the edge is manifold and + * that both its faces point the same way. + */ +bool BM_edge_is_contiguous(BMEdge *e) +{ + const BMLoop *l = e->l; + const BMLoop *l_other = l->radial_next; + return (l && (l_other != l) && /* not 0 or 1 face users */ + (l_other->radial_next == l) && /* 2 face users */ + (l_other->v != l->v)); +} + +/** * Tests whether or not an edge is on the boundary * of a shell (has one face associated with it) */ @@ -1007,6 +1020,22 @@ void BM_edge_ordered_verts(BMEdge *edge, BMVert **r_v1, BMVert **r_v2) } /** + * Check if the loop is convex or concave + * (depends on face normal) + */ +bool BM_loop_is_convex(BMLoop *l) +{ + float e_dir_prev[3]; + float e_dir_next[3]; + float l_no[3]; + + sub_v3_v3v3(e_dir_prev, l->prev->v->co, l->v->co); + sub_v3_v3v3(e_dir_next, l->next->v->co, l->v->co); + cross_v3_v3v3(l_no, e_dir_next, e_dir_prev); + return dot_v3v3(l_no, l->f->no) > 0.0f; +} + +/** * Calculates the angle between the previous and next loops * (angle at this loops face corner). * @@ -1034,7 +1063,7 @@ void BM_loop_calc_face_normal(BMLoop *l, float r_normal[3]) l->v->co, l->next->v->co) != 0.0f) { - return; + /* pass */ } else { copy_v3_v3(r_normal, l->f->no); @@ -1042,6 +1071,29 @@ void BM_loop_calc_face_normal(BMLoop *l, float r_normal[3]) } /** + * \brief BM_loop_calc_face_direction + * + * Calculate the direction a loop is pointing. + * + * \param l The loop to calculate the direction at + * \param r_dir Resulting direction + */ +void BM_loop_calc_face_direction(BMLoop *l, float r_dir[3]) +{ + float v_prev[3]; + float v_next[3]; + + sub_v3_v3v3(v_prev, l->v->co, l->prev->v->co); + sub_v3_v3v3(v_next, l->next->v->co, l->v->co); + + normalize_v3(v_prev); + normalize_v3(v_next); + + add_v3_v3v3(r_dir, v_prev, v_next); + normalize_v3(r_dir); +} + +/** * \brief BM_loop_calc_face_tangent * * Calculate the tangent at this loop corner or fallback to the face normal on straight lines. @@ -1054,23 +1106,27 @@ void BM_loop_calc_face_tangent(BMLoop *l, float r_tangent[3]) { float v_prev[3]; float v_next[3]; + float dir[3]; sub_v3_v3v3(v_prev, l->prev->v->co, l->v->co); sub_v3_v3v3(v_next, l->v->co, l->next->v->co); normalize_v3(v_prev); normalize_v3(v_next); + add_v3_v3v3(dir, v_prev, v_next); - if (compare_v3v3(v_prev, v_next, FLT_EPSILON) == false) { - float dir[3]; + if (compare_v3v3(v_prev, v_next, FLT_EPSILON * 10.0f) == false) { float nor[3]; /* for this purpose doesn't need to be normalized */ - add_v3_v3v3(dir, v_prev, v_next); cross_v3_v3v3(nor, v_prev, v_next); + /* concave face check */ + if (UNLIKELY(dot_v3v3(nor, l->f->no) < 0.0f)) { + negate_v3(nor); + } cross_v3_v3v3(r_tangent, dir, nor); } else { /* prev/next are the same - compare with face normal since we don't have one */ - cross_v3_v3v3(r_tangent, v_next, l->f->no); + cross_v3_v3v3(r_tangent, dir, l->f->no); } normalize_v3(r_tangent); diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h index 9892700162e..7cb5749a4bf 100644 --- a/source/blender/bmesh/intern/bmesh_queries.h +++ b/source/blender/bmesh/intern/bmesh_queries.h @@ -61,9 +61,13 @@ bool BM_edge_is_wire(BMEdge *e); bool BM_vert_is_manifold(BMVert *v); bool BM_edge_is_manifold(BMEdge *e); bool BM_edge_is_boundary(BMEdge *e); +bool BM_edge_is_contiguous(BMEdge *e); + +bool BM_loop_is_convex(BMLoop *l); float BM_loop_calc_face_angle(BMLoop *l); void BM_loop_calc_face_normal(BMLoop *l, float r_normal[3]); +void BM_loop_calc_face_direction(BMLoop *l, float r_normal[3]); void BM_loop_calc_face_tangent(BMLoop *l, float r_tangent[3]); float BM_edge_calc_face_angle(BMEdge *e); diff --git a/source/blender/bmesh/intern/bmesh_walkers_impl.c b/source/blender/bmesh/intern/bmesh_walkers_impl.c index bbe02a49967..ac6d4089372 100644 --- a/source/blender/bmesh/intern/bmesh_walkers_impl.c +++ b/source/blender/bmesh/intern/bmesh_walkers_impl.c @@ -858,7 +858,7 @@ static void *bmw_EdgeringWalker_step(BMWalker *walker) if (!EDGE_CHECK(e)) { /* walker won't traverse to a non-manifold edge, but may * be started on one, and should not traverse *away* from - * a non-manfold edge (non-manifold edges are never in an + * a non-manifold edge (non-manifold edges are never in an * edge ring with manifold edges */ return e; } diff --git a/source/blender/bmesh/operators/bmo_connect.c b/source/blender/bmesh/operators/bmo_connect.c index 3a0e18b9ee5..9a17ebea38d 100644 --- a/source/blender/bmesh/operators/bmo_connect.c +++ b/source/blender/bmesh/operators/bmo_connect.c @@ -359,6 +359,17 @@ void bmo_bridge_loops_exec(BMesh *bm, BMOperator *op) /* Last point of loop 2 */ v4 = get_outer_vert(bm, ee2[clamp_index(-1, BLI_array_count(ee2))]); + /* ugh, happens when bridging single edges, user could just make a face + * but better support it for sake of completeness */ + if (v1 == v2) { + BLI_assert(BLI_array_count(ee1) == 1); + v2 = (vv1[0] == v2) ? vv1[1] : vv1[0]; + } + if (v3 == v4) { + BLI_assert(BLI_array_count(ee2) == 1); + v4 = (vv2[0] == v4) ? vv2[1] : vv2[0]; + } + /* If v1 is a better match for v4 than v3, AND v2 is a better match * for v3 than v4, the loops are in opposite directions, so reverse * the order of reads from vv1. We can avoid sqrt for comparison */ diff --git a/source/blender/bmesh/operators/bmo_triangulate.c b/source/blender/bmesh/operators/bmo_triangulate.c index 744f706681d..3d78ff64876 100644 --- a/source/blender/bmesh/operators/bmo_triangulate.c +++ b/source/blender/bmesh/operators/bmo_triangulate.c @@ -37,45 +37,22 @@ #include "intern/bmesh_operators_private.h" /* own include */ -#define EDGE_NEW 1 -#define FACE_NEW 1 - #define ELE_NEW 1 #define FACE_MARK 2 #define EDGE_MARK 4 void bmo_triangulate_exec(BMesh *bm, BMOperator *op) { - BMOIter siter; - BMFace *face, **newfaces = NULL; - BLI_array_declare(newfaces); - float (*projectverts)[3] = NULL; - BLI_array_declare(projectverts); - int i; const bool use_beauty = BMO_slot_bool_get(op->slots_in, "use_beauty"); BMOpSlot *slot_facemap_out = BMO_slot_get(op->slots_out, "face_map.out"); - for (face = BMO_iter_new(&siter, op->slots_in, "faces", BM_FACE); face; face = BMO_iter_step(&siter)) { - - BLI_array_empty(projectverts); - BLI_array_empty(newfaces); - - BLI_array_grow_items(projectverts, face->len * 3); - BLI_array_grow_items(newfaces, face->len); + BM_mesh_elem_hflag_disable_all(bm, BM_FACE | BM_EDGE, BM_ELEM_TAG, false); + BMO_slot_buffer_hflag_enable(bm, op->slots_in, "faces", BM_FACE, BM_ELEM_TAG, false); - BM_face_triangulate(bm, face, projectverts, EDGE_NEW, FACE_NEW, newfaces, use_beauty); + BM_mesh_triangulate(bm, use_beauty, true, op, slot_facemap_out); - BMO_slot_map_elem_insert(op, slot_facemap_out, face, face); - for (i = 0; newfaces[i]; i++) { - BMO_slot_map_elem_insert(op, slot_facemap_out, newfaces[i], face); - } - } - - BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "edges.out", BM_EDGE, EDGE_NEW); - BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "faces.out", BM_FACE, FACE_NEW); - - BLI_array_free(projectverts); - BLI_array_free(newfaces); + BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "edges.out", BM_EDGE, BM_ELEM_TAG); + BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "faces.out", BM_FACE, BM_ELEM_TAG); } void bmo_beautify_fill_exec(BMesh *bm, BMOperator *op) @@ -86,7 +63,7 @@ void bmo_beautify_fill_exec(BMesh *bm, BMOperator *op) BMEdge *e; int stop = 0; - BMO_slot_buffer_flag_enable(bm, op->slots_in, "constrain_edges", BM_EDGE, EDGE_MARK); + BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK); BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) { if (f->len == 3) { @@ -98,9 +75,11 @@ void bmo_beautify_fill_exec(BMesh *bm, BMOperator *op) stop = 1; BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { - BMVert *v1, *v2, *v3, *v4; + float v1_xy[2], v2_xy[2], v3_xy[2], v4_xy[2]; + float no[3]; + float axis_mat[3][3]; - if (!BM_edge_is_manifold(e) || BMO_elem_flag_test(bm, e, EDGE_MARK)) { + if (!BM_edge_is_manifold(e) || !BMO_elem_flag_test(bm, e, EDGE_MARK)) { continue; } @@ -110,37 +89,51 @@ void bmo_beautify_fill_exec(BMesh *bm, BMOperator *op) continue; } - v1 = e->l->prev->v; - v2 = e->l->v; - v3 = e->l->radial_next->prev->v; - v4 = e->l->next->v; - - if (is_quad_convex_v3(v1->co, v2->co, v3->co, v4->co)) { + { + float *v1, *v2, *v3, *v4; + float no_a[3], no_b[3]; + v1 = e->l->prev->v->co; + v2 = e->l->v->co; + v3 = e->l->radial_next->prev->v->co; + v4 = e->l->next->v->co; + + normal_tri_v3(no_a, v1, v2, v3); + normal_tri_v3(no_b, v1, v3, v4); + add_v3_v3v3(no, no_a, no_b); + normalize_v3(no); + axis_dominant_v3_to_m3(axis_mat, no); + mul_v2_m3v3(v1_xy, axis_mat, v1); + mul_v2_m3v3(v2_xy, axis_mat, v2); + mul_v2_m3v3(v3_xy, axis_mat, v3); + mul_v2_m3v3(v4_xy, axis_mat, v4); + } + + if (is_quad_convex_v2(v1_xy, v2_xy, v3_xy, v4_xy)) { float len1, len2, len3, len4, len5, len6, opp1, opp2, fac1, fac2; /* testing rule: * the area divided by the total edge lengths */ - len1 = len_v3v3(v1->co, v2->co); - len2 = len_v3v3(v2->co, v3->co); - len3 = len_v3v3(v3->co, v4->co); - len4 = len_v3v3(v4->co, v1->co); - len5 = len_v3v3(v1->co, v3->co); - len6 = len_v3v3(v2->co, v4->co); + len1 = len_v2v2(v1_xy, v2_xy); + len2 = len_v2v2(v2_xy, v3_xy); + len3 = len_v2v2(v3_xy, v4_xy); + len4 = len_v2v2(v4_xy, v1_xy); + len5 = len_v2v2(v1_xy, v3_xy); + len6 = len_v2v2(v2_xy, v4_xy); - opp1 = area_tri_v3(v1->co, v2->co, v3->co); - opp2 = area_tri_v3(v1->co, v3->co, v4->co); + opp1 = area_tri_v2(v1_xy, v2_xy, v3_xy); + opp2 = area_tri_v2(v1_xy, v3_xy, v4_xy); fac1 = opp1 / (len1 + len2 + len5) + opp2 / (len3 + len4 + len5); - opp1 = area_tri_v3(v2->co, v3->co, v4->co); - opp2 = area_tri_v3(v2->co, v4->co, v1->co); + opp1 = area_tri_v2(v2_xy, v3_xy, v4_xy); + opp2 = area_tri_v2(v2_xy, v4_xy, v1_xy); fac2 = opp1 / (len2 + len3 + len6) + opp2 / (len4 + len1 + len6); if (fac1 > fac2) { e = BM_edge_rotate(bm, e, false, BM_EDGEROT_CHECK_EXISTS); if (e) { - BMO_elem_flag_enable(bm, e, ELE_NEW); + BMO_elem_flag_enable(bm, e, ELE_NEW | EDGE_MARK); BMO_elem_flag_enable(bm, e->l->f, FACE_MARK | ELE_NEW); BMO_elem_flag_enable(bm, e->l->radial_next->f, FACE_MARK | ELE_NEW); @@ -156,9 +149,9 @@ void bmo_beautify_fill_exec(BMesh *bm, BMOperator *op) void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op) { + const bool use_beauty = BMO_slot_bool_get(op->slots_in, "use_beauty"); BMOIter siter; BMEdge *e; - BMOperator bmop; ScanFillContext sf_ctx; /* ScanFillEdge *sf_edge; */ /* UNUSED */ ScanFillVert *sf_vert, *sf_vert_1, *sf_vert_2; @@ -210,11 +203,14 @@ void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op) BLI_scanfill_end(&sf_ctx); BLI_smallhash_release(&hash); - /* clean up fill */ - BMO_op_initf(bm, &bmop, op->flag, "beautify_fill faces=%ff constrain_edges=%fe", ELE_NEW, EDGE_MARK); - BMO_op_exec(bm, &bmop); - BMO_slot_buffer_flag_enable(bm, bmop.slots_out, "geom.out", BM_FACE | BM_EDGE, ELE_NEW); - BMO_op_finish(bm, &bmop); + if (use_beauty) { + BMOperator bmop; + + BMO_op_initf(bm, &bmop, op->flag, "beautify_fill faces=%ff edges=%Fe", ELE_NEW, EDGE_MARK); + BMO_op_exec(bm, &bmop); + BMO_slot_buffer_flag_enable(bm, bmop.slots_out, "geom.out", BM_FACE | BM_EDGE, ELE_NEW); + BMO_op_finish(bm, &bmop); + } BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom.out", BM_EDGE | BM_FACE, ELE_NEW); } diff --git a/source/blender/bmesh/tools/bmesh_bevel.c b/source/blender/bmesh/tools/bmesh_bevel.c index 5461e5fe788..1e74354603b 100644 --- a/source/blender/bmesh/tools/bmesh_bevel.c +++ b/source/blender/bmesh/tools/bmesh_bevel.c @@ -384,6 +384,7 @@ static void offset_in_two_planes(EdgeHalf *e1, EdgeHalf *e2, EdgeHalf *emid, int iret; BLI_assert(f1 != NULL && f2 != NULL); + (void)f1, (void)f2; /* UNUSED */ /* get direction vectors for two offset lines */ sub_v3_v3v3(dir1, v->co, BM_edge_other_vert(e1->e, v)->co); @@ -518,7 +519,7 @@ static int bev_ccw_test(BMEdge *a, BMEdge *b, BMFace *f) * We want M to make M*A=B where A has the left side above, as columns * and B has the right side as columns - both extended into homogeneous coords. * So M = B*(Ainverse). Doing Ainverse by hand gives the code below. -*/ + */ static int make_unit_square_map(const float va[3], const float vmid[3], const float vb[3], float r_mat[4][4]) { @@ -1304,7 +1305,7 @@ static void fix_vmesh_tangents(VMesh *vm, BevVert *bv) /* Also want (i, 1, k) snapped to plane of adjacent face for * 1 < k < ns - 1, but current initial cage and subdiv rules - * ensure this, so nothing to do */ + * ensure this, so nothing to do */ } while ((bndv = bndv->next) != vm->boundstart); } @@ -1654,7 +1655,13 @@ static void build_vmesh(BevelParams *bp, BMesh *bm, BevVert *bv) if (v->ebev) { va = mesh_vert(vm, i, 0, 0)->co; vb = mesh_vert(vm, i, 0, ns)->co; - project_to_edge(v->ebev->e, va, vb, midco); + if (bv->edgecount == 3 && bv->selcount == 1) { + /* special case: profile cuts the third face, so line it up with that */ + copy_v3_v3(midco, bv->v->co); + } + else { + project_to_edge(v->ebev->e, va, vb, midco); + } for (k = 1; k < ns; k++) { get_point_on_round_edge(v->ebev, k, va, midco, vb, co); copy_v3_v3(mesh_vert(vm, i, 0, k)->co, co); diff --git a/source/blender/bmesh/tools/bmesh_triangulate.c b/source/blender/bmesh/tools/bmesh_triangulate.c new file mode 100644 index 00000000000..79f6c76afc7 --- /dev/null +++ b/source/blender/bmesh/tools/bmesh_triangulate.c @@ -0,0 +1,87 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * Contributor(s): Joseph Eagar + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/bmesh/tools/bmesh_triangulate.c + * \ingroup bmesh + * + * Triangulate. + * + */ + +#include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" +#include "BLI_array.h" + +#include "bmesh.h" + +#include "bmesh_triangulate.h" /* own include */ + +/** + * a version of #BM_face_triangulate that maps to #BMOpSlot + */ +static void bm_face_triangulate_mapping(BMesh *bm, BMFace *face, const bool use_beauty, const bool use_tag, + BMOperator *op, BMOpSlot *slot_facemap_out) +{ + const int faces_array_tot = face->len - 3; + BMFace **faces_array = BLI_array_alloca(faces_array, faces_array_tot); + BLI_assert(face->len > 3); + + BM_face_triangulate(bm, face, faces_array, use_beauty, use_tag); + + if (faces_array) { + int i; + BMO_slot_map_elem_insert(op, slot_facemap_out, face, face); + for (i = 0; i < faces_array_tot; i++) { + BMO_slot_map_elem_insert(op, slot_facemap_out, faces_array[i], face); + } + } +} + + +void BM_mesh_triangulate(BMesh *bm, const bool use_beauty, const bool tag_only, + BMOperator *op, BMOpSlot *slot_facemap_out) +{ + BMIter iter; + BMFace *face; + + if (slot_facemap_out) { + /* same as below but call: bm_face_triangulate_mapping() */ + BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) { + if (face->len > 3) { + if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) { + bm_face_triangulate_mapping(bm, face, use_beauty, tag_only, + op, slot_facemap_out); + } + } + } + } + else { + BM_ITER_MESH (face, &iter, bm, BM_FACES_OF_MESH) { + if (face->len > 3) { + if (tag_only == false || BM_elem_flag_test(face, BM_ELEM_TAG)) { + BM_face_triangulate(bm, face, NULL, use_beauty, tag_only); + } + } + } + } +} diff --git a/source/blender/bmesh/tools/bmesh_triangulate.h b/source/blender/bmesh/tools/bmesh_triangulate.h new file mode 100644 index 00000000000..936a90d3a16 --- /dev/null +++ b/source/blender/bmesh/tools/bmesh_triangulate.h @@ -0,0 +1,36 @@ +/* + * ***** BEGIN GPL LICENSE BLOCK ***** + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version 2 + * of the License, or (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program; if not, write to the Free Software Foundation, + * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. + * + * Contributor(s): Joseph Eagar + * + * ***** END GPL LICENSE BLOCK ***** + */ + +/** \file blender/bmesh/tools/bmesh_triangulate.h + * \ingroup bmesh + * + * Triangulate. + * + */ + +#ifndef __BMESH_TRIAMGULATE_H__ +#define __BMESH_TRIAMGULATE_H__ + +void BM_mesh_triangulate(BMesh *bm, const bool use_beauty, const bool tag_only, + BMOperator *op, BMOpSlot *slot_facemap_out); + +#endif /* __BMESH_TRIAMGULATE_H__ */ |