From 0488af00fe95d9af32215d38394994013f09bb2b Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Wed, 13 Mar 2013 06:32:08 +0000 Subject: fix for crash with laplacian smooth when unselected ngons were used, volume calculation assumed unselected face were not ngons. - added convenience function BM_face_calc_tessellation() to get triangles from an ngon. - expose volume function as BM_mesh_calc_volume(). --- source/blender/bmesh/intern/bmesh_polygon.c | 102 +++++++++++++++++++++++++++- source/blender/bmesh/intern/bmesh_polygon.h | 1 + source/blender/bmesh/intern/bmesh_queries.c | 30 ++++++++ source/blender/bmesh/intern/bmesh_queries.h | 2 + 4 files changed, 133 insertions(+), 2 deletions(-) (limited to 'source/blender/bmesh/intern') diff --git a/source/blender/bmesh/intern/bmesh_polygon.c b/source/blender/bmesh/intern/bmesh_polygon.c index 9592c34fc75..c77e1603885 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -35,12 +35,16 @@ * degenerate faces. */ -#include "BLI_math.h" -#include "BLI_array.h" +#include "DNA_listBase.h" #include "MEM_guardedalloc.h" +#include "BLI_math.h" +#include "BLI_array.h" +#include "BLI_scanfill.h" + #include "bmesh.h" + #include "intern/bmesh_private.h" /** @@ -150,6 +154,100 @@ static void bm_face_calc_poly_normal_vertex_cos(BMFace *f, float n[3], } } +/** + * For tools that insist on using triangles, ideally we would cache this data. + * + * \param r_loops Empty array of loops, (f->len) + * \param r_index Empty array of loops, ((f->len - 2) * 3) + */ +void BM_face_calc_tessellation(BMFace *f, BMLoop **r_loops, int (*_r_index)[3]) +{ + int *r_index = (int *)_r_index; + BMLoop *l_first = BM_FACE_FIRST_LOOP(f); + BMLoop *l_iter; + + if (f->len == 3) { + *r_loops++ = (l_iter = l_first); + *r_loops++ = (l_iter = l_iter->next); + *r_loops++ = ( l_iter->next); + + r_index[0] = 0; + r_index[1] = 1; + r_index[2] = 2; + } + else if (f->len == 4) { + BMLoop *l_iter; + *r_loops++ = (l_iter = l_first); + *r_loops++ = (l_iter = l_iter->next); + *r_loops++ = (l_iter = l_iter->next); + *r_loops++ = ( l_iter->next); + + r_index[0] = 0; + r_index[1] = 1; + r_index[2] = 2; + + r_index[3] = 0; + r_index[4] = 2; + r_index[5] = 3; + } + else { + int j; + + ScanFillContext sf_ctx; + ScanFillVert *sf_vert, *sf_vert_last = NULL, *sf_vert_first = NULL; + /* ScanFillEdge *e; */ /* UNUSED */ + ScanFillFace *sf_tri; + int totfilltri; + + BLI_scanfill_begin(&sf_ctx); + + j = 0; + l_iter = l_first; + do { + sf_vert = BLI_scanfill_vert_add(&sf_ctx, l_iter->v->co); + sf_vert->tmp.p = l_iter; + + if (sf_vert_last) { + /* e = */ BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert); + } + + sf_vert_last = sf_vert; + if (sf_vert_first == NULL) { + sf_vert_first = sf_vert; + } + + r_loops[j] = l_iter; + + /* mark order */ + BM_elem_index_set(l_iter, j++); /* set_loop */ + + } while ((l_iter = l_iter->next) != l_first); + + /* complete the loop */ + BLI_scanfill_edge_add(&sf_ctx, sf_vert_first, sf_vert); + + totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, f->no); + BLI_assert(totfilltri <= f->len - 2); + (void)totfilltri; + + for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) { + int i1 = BM_elem_index_get((BMLoop *)sf_tri->v1->tmp.p); + int i2 = BM_elem_index_get((BMLoop *)sf_tri->v2->tmp.p); + int i3 = BM_elem_index_get((BMLoop *)sf_tri->v3->tmp.p); + + if (i1 > i2) { SWAP(int, i1, i2); } + if (i2 > i3) { SWAP(int, i2, i3); } + if (i1 > i2) { SWAP(int, i1, i2); } + + *r_index++ = i1; + *r_index++ = i2; + *r_index++ = i3; + } + + BLI_scanfill_end(&sf_ctx); + } +} + /** * get the area of the face */ diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h index 601caae2337..ccb85449808 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/source/blender/bmesh/intern/bmesh_polygon.h @@ -27,6 +27,7 @@ * \ingroup bmesh */ +void BM_face_calc_tessellation(BMFace *f, BMLoop **r_loops, int (*r_index)[3]); float BM_face_calc_area(BMFace *f); float BM_face_calc_perimeter(BMFace *f); void BM_face_calc_center_bounds(BMFace *f, float center[3]); diff --git a/source/blender/bmesh/intern/bmesh_queries.c b/source/blender/bmesh/intern/bmesh_queries.c index 70df0b56607..54950f2af82 100644 --- a/source/blender/bmesh/intern/bmesh_queries.c +++ b/source/blender/bmesh/intern/bmesh_queries.c @@ -1652,3 +1652,33 @@ bool BM_face_is_any_edge_flag_test(BMFace *f, const char hflag) } while ((l_iter = l_iter->next) != l_first); return false; } + +float BM_mesh_calc_volume(BMesh *bm) +{ + /* warning, calls own tessellation function, may be slow */ + float vol = 0.0f; + BMFace *f; + BMIter fiter; + + BM_ITER_MESH (f, &fiter, bm, BM_FACES_OF_MESH) { + const int tottri = f->len - 2; + BMLoop **loops = BLI_array_alloca(loops, f->len); + int (*index)[3] = BLI_array_alloca(index, tottri); + int j; + + BM_face_calc_tessellation(f, loops, index); + + for (j = 0; j < tottri; j++) { + const float *p1 = loops[index[j][0]]->v->co; + const float *p2 = loops[index[j][1]]->v->co; + const float *p3 = loops[index[j][2]]->v->co; + + /* co1.dot(co2.cross(co3)) / 6.0 */ + float cross[3]; + cross_v3_v3v3(cross, p2, p3); + vol += (1.0f / 6.0f) * dot_v3v3(p1, cross); + } + } + + return fabsf(vol); +} diff --git a/source/blender/bmesh/intern/bmesh_queries.h b/source/blender/bmesh/intern/bmesh_queries.h index 7cb5749a4bf..f894912aad3 100644 --- a/source/blender/bmesh/intern/bmesh_queries.h +++ b/source/blender/bmesh/intern/bmesh_queries.h @@ -110,4 +110,6 @@ bool BM_edge_is_any_vert_flag_test(BMEdge *e, const char hflag); bool BM_face_is_any_vert_flag_test(BMFace *f, const char hflag); bool BM_face_is_any_edge_flag_test(BMFace *f, const char hflag); +float BM_mesh_calc_volume(BMesh *bm); + #endif /* __BMESH_QUERIES_H__ */ -- cgit v1.2.3