diff options
author | Bastien Montagne <montagne29@wanadoo.fr> | 2012-06-24 20:19:19 +0400 |
---|---|---|
committer | Bastien Montagne <montagne29@wanadoo.fr> | 2012-06-24 20:19:19 +0400 |
commit | df9ca0455c281ffba785a27f9cfd95135195f906 (patch) | |
tree | f7e7ec12c818406556914ce095d481ac5a0198c1 /source | |
parent | e60c2f5c3e8945b4829171cd436fe15518fb916e (diff) |
Fix [#31807] Ngon triangulation error
Notes:
*This implements a quite simple algorithm, which simply checks angles (actually, absolute cosines) of created tri and remaining face (which may be a tri, quad, or more NGon), so that both are "best" (ie avoid as much as possible too much narrow/wide corners), and also checks the new edge is OK (i.e. does not goes "out" of original face).
*Incidently, it fixes a typo in that bm_face_goodline() func!
*It's quite performant (a bit quicker than previous code, as far as I have tested it) and prevent creation of completely flat triangles as much as possible, but it's far from being a "best" solution (as it is still a "progressive" one)!
*It also introduces a new math func (in BLI_math_vector.h), cos_v3v3v3, which computes cosine (ie dot product of normalized vectors) and is roughly a quicker replacement for angle_v3v3v3, when real angles are not needed.
Diffstat (limited to 'source')
-rw-r--r-- | source/blender/blenlib/BLI_math_vector.h | 1 | ||||
-rw-r--r-- | source/blender/blenlib/intern/math_vector.c | 13 | ||||
-rw-r--r-- | source/blender/bmesh/intern/bmesh_polygon.c | 132 |
3 files changed, 127 insertions, 19 deletions
diff --git a/source/blender/blenlib/BLI_math_vector.h b/source/blender/blenlib/BLI_math_vector.h index be492fb6fdd..8499a7f219c 100644 --- a/source/blender/blenlib/BLI_math_vector.h +++ b/source/blender/blenlib/BLI_math_vector.h @@ -191,6 +191,7 @@ float angle_v2v2v2(const float a[2], const float b[2], const float c[2]); float angle_normalized_v2v2(const float a[2], const float b[2]); float angle_v3v3(const float a[3], const float b[3]); float angle_v3v3v3(const float a[3], const float b[3], const float c[3]); +float cos_v3v3v3(const float p1[3], const float p2[3], const float p3[3]); float angle_normalized_v3v3(const float v1[3], const float v2[3]); float angle_on_axis_v3v3v3_v3(const float v1[3], const float v2[3], const float v3[3], const float axis[3]); void angle_tri_v3(float angles[3], const float v1[3], const float v2[3], const float v3[3]); diff --git a/source/blender/blenlib/intern/math_vector.c b/source/blender/blenlib/intern/math_vector.c index d939576904e..5cda1c0b81f 100644 --- a/source/blender/blenlib/intern/math_vector.c +++ b/source/blender/blenlib/intern/math_vector.c @@ -136,6 +136,19 @@ float angle_v3v3v3(const float v1[3], const float v2[3], const float v3[3]) return angle_normalized_v3v3(vec1, vec2); } +/* Quicker than full angle computation */ +float cos_v3v3v3(const float p1[3], const float p2[3], const float p3[3]) +{ + float vec1[3], vec2[3]; + + sub_v3_v3v3(vec1, p2, p1); + sub_v3_v3v3(vec2, p2, p3); + normalize_v3(vec1); + normalize_v3(vec2); + + return dot_v3v3(vec1, vec2); +} + /* Return the shortest angle in radians between the 2 vectors */ float angle_v3v3(const float v1[3], const float v2[3]) { diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index 72eb4cb89e9..0b2c3040df3 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -642,7 +642,7 @@ static int bm_face_goodline(float const (*projectverts)[3], BMFace *f, //if (linecrossesf(pv1, pv2, v1, v3)) return FALSE; if (isect_point_tri_v2(pv1, v1, v2, v3) || - isect_point_tri_v2(pv1, v3, v2, v1)) + isect_point_tri_v2(pv2, v3, v2, v1)) { return FALSE; } @@ -658,18 +658,22 @@ static int bm_face_goodline(float const (*projectverts)[3], BMFace *f, * of a polygon while tessellating. * * \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 int nvert, const int use_beauty) +static BMLoop *find_ear(BMFace *f, float (*verts)[3], const int nvert, const int use_beauty, float *abscoss) { BMLoop *bestear = NULL; BMLoop *l_iter; BMLoop *l_first; + const float cos_threshold = 0.9f; + if (f->len == 4) { BMLoop *larr[4]; - int i = 0; - + int i = 0, i4; + float cos1, cos2; l_iter = l_first = BM_FACE_FIRST_LOOP(f); do { larr[i] = l_iter; @@ -677,17 +681,60 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const int nvert, const int } while ((l_iter = l_iter->next) != l_first); /* pick 0/1 based on best lenth */ - bestear = larr[(((len_squared_v3v3(larr[0]->v->co, larr[2]->v->co) > - len_squared_v3v3(larr[1]->v->co, larr[3]->v->co))) != use_beauty)]; + /* XXX Can't only rely on such test, also must check we do not get (too much) degenerated triangles!!! */ + i = (((len_squared_v3v3(larr[0]->v->co, larr[2]->v->co) > + len_squared_v3v3(larr[1]->v->co, larr[3]->v->co))) != use_beauty); + i4 = (i + 3) % 4; + /* Check produced tris aren’t too flat/narrow... + * Probably not the best test, but is quite efficient and should at least avoid null-area faces! */ + cos1 = fabsf(cos_v3v3v3(larr[i4]->v->co, larr[i]->v->co, larr[i + 1]->v->co)); + cos2 = fabsf(cos_v3v3v3(larr[i4]->v->co, larr[i + 2]->v->co, larr[i + 1]->v->co)); +#if 0 + printf("%d, (%f, %f), (%f, %f)\n", i, cos1, cos2, + fabsf(cos_v3v3v3(larr[i]->v->co, larr[i4]->v->co, larr[i + 2]->v->co)), + fabsf(cos_v3v3v3(larr[i]->v->co, larr[i + 1]->v->co, larr[i + 2]->v->co))); +#endif + if (cos1 < cos2) + cos1 = cos2; + if (cos1 > cos_threshold) { + if (cos1 > fabsf(cos_v3v3v3(larr[i]->v->co, larr[i4]->v->co, larr[i + 2]->v->co)) && + cos1 > fabsf(cos_v3v3v3(larr[i]->v->co, larr[i + 1]->v->co, larr[i + 2]->v->co))) + i = !i; + } + /* Last check we do not get overlapping triangles + * (as much as possible, ther 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), BM_elem_index_get(larr[i]->v), + BM_elem_index_get(larr[i + 1]->v), nvert)) + i = !i; +/* printf("%d\n", i);*/ + bestear = larr[i]; } else { BMVert *v1, *v2, *v3; /* float angle, bestangle = 180.0f; */ - int isear /*, i = 0 */; + float cos, tcos, bestcos = 1.0f; + float *tcoss; + int isear, i = 0, j, len; + /* Compute cos of all corners! */ 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; + + *tcoss = fabsf(cos_v3v3v3(v1->co, v2->co, v3->co)); +/* printf("tcoss: %f\n", *tcoss);*/ + tcoss++; + } while ((l_iter = l_iter->next) != l_first); + + l_iter = l_first; + tcoss = abscoss; do { isear = TRUE; @@ -695,6 +742,7 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const int nvert, const int v2 = l_iter->v; v3 = l_iter->next->v; + /* We may have already internal edges... */ if (BM_edge_exists(v1, v3)) { isear = FALSE; } @@ -706,7 +754,7 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const int nvert, const int } if (isear) { - #if 0 +#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) { @@ -717,11 +765,46 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const int nvert, const int if (angle > 20 && angle < 90) break; if (angle < 100 && i > 5) break; i += 1; - #endif +#endif - bestear = l_iter; - break; + /* 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; + + /* Compare to prev best (i.e. lowest) cos. */ + if (cos < bestcos) { + /* We must check this tri would not leave a (too much) degenerated remaining face! */ + /* For now just assume if the average of cos of all "remaining face"'s corners is below a given threshold, it’s OK. */ + float avgcos = fabsf(cos_v3v3v3(v1->co, v3->co, l_iter->next->next->v->co)); + const int i_limit = (i - 1 + len) % len; + avgcos += fabsf(cos_v3v3v3(l_iter->prev->prev->v->co, v1->co, v3->co)); + j = (i + 2) % len; + do { + avgcos += abscoss[j]; + } while ((j = (j + 1) % len) != i_limit); + avgcos /= len - 1; + + /* We need a best ear in any case... */ + if (avgcos < cos_threshold || (!bestear && avgcos < 1.0f)) { + /* OKI, keep this ear (corner...) as a potential best one! */ + bestear = l_iter; + bestcos = cos; + } +#if 0 + else + printf("Had a nice tri (higest cos of %f, current bestcos is %f), " + "but average cos of all \"remaining face\"'s corners is too high (%f)!\n", + cos, bestcos, avgcos); +#endif + } } + tcoss++; + i++; } while ((l_iter = l_iter->next) != l_first); } @@ -731,14 +814,20 @@ static BMLoop *find_ear(BMFace *f, float (*verts)[3], const int nvert, const int /** * \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 + * 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 + * with a length equal to f->len. It will be filled with the new * triangles, and will be NULL-terminated. * * \note newedgeflag sets a flag layer flag, obviously not the header flag. @@ -748,10 +837,11 @@ void BM_face_triangulate(BMesh *bm, BMFace *f, float (*projectverts)[3], const short use_beauty) { int i, done, nvert, nf_i = 0; - BMLoop *newl, *nextloop; + BMLoop *newl; BMLoop *l_iter; BMLoop *l_first; - /* BMVert *v; */ /* UNUSED */ + float *abscoss = NULL; + BLI_array_fixedstack_declare(abscoss, 16, f->len, "BM_face_triangulate: temp absolute cosines of face corners"); /* copy vertex coordinates to vertspace arra */ i = 0; @@ -764,14 +854,14 @@ void BM_face_triangulate(BMesh *bm, BMFace *f, float (*projectverts)[3], bm->elem_index_dirty |= BM_VERT; /* see above */ - ///bmesh_face_normal_update(bm, f, f->no, projectverts); + /* 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); + /* calc_poly_plane(projectverts, i); */ for (i = 0; i < nvert; i++) { projectverts[i][2] = 0.0f; } @@ -779,10 +869,10 @@ void BM_face_triangulate(BMesh *bm, BMFace *f, float (*projectverts)[3], done = FALSE; while (!done && f->len > 3) { done = TRUE; - l_iter = find_ear(f, projectverts, nvert, use_beauty); + l_iter = find_ear(f, projectverts, nvert, use_beauty, abscoss); if (l_iter) { done = FALSE; - /* v = l->v; */ /* UNUSED */ +/* printf("Subdividing face...\n");*/ f = BM_face_split(bm, l_iter->f, l_iter->prev->v, l_iter->next->v, &newl, NULL, TRUE); @@ -812,6 +902,7 @@ void BM_face_triangulate(BMesh *bm, BMFace *f, float (*projectverts)[3], } } +#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) { @@ -833,7 +924,10 @@ void BM_face_triangulate(BMesh *bm, BMFace *f, float (*projectverts)[3], l_iter = nextloop; } } - +#endif + + BLI_array_fixedstack_free(abscoss); + /* NULL-terminate */ if (newfaces) newfaces[nf_i] = NULL; } |