From 238d2f962dc7f15188ea02d65950b1d2945d029a Mon Sep 17 00:00:00 2001 From: Walid Shouman Date: Mon, 18 Nov 2013 18:20:21 +1100 Subject: BMesh Refactor: BKE_bmbvh_new can now be created without an EditMesh. This adds BM_bmesh_calc_tessellation() so we can get triangles from a bmesh without having to have an editmesh available. --- source/blender/bmesh/intern/bmesh_polygon.c | 159 ++++++++++++++++++++++++++++ source/blender/bmesh/intern/bmesh_polygon.h | 2 + 2 files changed, 161 insertions(+) (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 e88fdb8a7e8..3db6ba0e7c9 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.c +++ b/source/blender/bmesh/intern/bmesh_polygon.c @@ -31,6 +31,8 @@ #include "DNA_listBase.h" #include "DNA_modifier_types.h" +#include "MEM_guardedalloc.h" + #include "BLI_alloca.h" #include "BLI_math.h" #include "BLI_memarena.h" @@ -1268,3 +1270,160 @@ void BM_face_as_array_loop_quad(BMFace *f, BMLoop *r_loops[4]) r_loops[2] = l; l = l->next; r_loops[3] = l; } + + +/** + * \brief BM_bmesh_calc_tessellation get the looptris and its number from a certain bmesh + * \param looptris + * + * \note \a looptris Must be pre-allocated to at least the size of given by: poly_to_tri_count + */ +void BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[3], int *r_looptris_tot) +{ + /* use this to avoid locking pthread for _every_ polygon + * and calling the fill function */ +#define USE_TESSFACE_SPEEDUP + + /* this assumes all faces can be scan-filled, which isn't always true, + * worst case we over alloc a little which is acceptable */ + const int looptris_tot = poly_to_tri_count(bm->totface, bm->totloop); + + BMIter iter; + BMFace *efa; + BMLoop *l; + int i = 0; + + ScanFillContext sf_ctx; + MemArena *sf_arena = NULL; + + BM_ITER_MESH (efa, &iter, bm, BM_FACES_OF_MESH) { + /* don't consider two-edged faces */ + if (UNLIKELY(efa->len < 3)) { + /* do nothing */ + } + +#ifdef USE_TESSFACE_SPEEDUP + + /* no need to ensure the loop order, we know its ok */ + + else if (efa->len == 3) { +#if 0 + int j; + BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, j) { + looptris[i][j] = l; + } + i += 1; +#else + /* more cryptic but faster */ + BMLoop **l_ptr = looptris[i++]; + l_ptr[0] = l = BM_FACE_FIRST_LOOP(efa); + l_ptr[1] = l = l->next; + l_ptr[2] = l->next; +#endif + } + else if (efa->len == 4) { +#if 0 + BMLoop *ltmp[4]; + int j; + BLI_array_grow_items(looptris, 2); + BM_ITER_ELEM_INDEX (l, &liter, efa, BM_LOOPS_OF_FACE, j) { + ltmp[j] = l; + } + + looptris[i][0] = ltmp[0]; + looptris[i][1] = ltmp[1]; + looptris[i][2] = ltmp[2]; + i += 1; + + looptris[i][0] = ltmp[0]; + looptris[i][1] = ltmp[2]; + looptris[i][2] = ltmp[3]; + i += 1; +#else + /* more cryptic but faster */ + BMLoop **l_ptr_a = looptris[i++]; + BMLoop **l_ptr_b = looptris[i++]; + (l_ptr_a[0] = l_ptr_b[0] = l = BM_FACE_FIRST_LOOP(efa)); + (l_ptr_a[1] = l = l->next); + (l_ptr_a[2] = l_ptr_b[1] = l = l->next); + ( l_ptr_b[2] = l->next); +#endif + } + +#endif /* USE_TESSFACE_SPEEDUP */ + + else { + int j; + BMLoop *l_iter; + BMLoop *l_first; + + ScanFillVert *sf_vert, *sf_vert_last = NULL, *sf_vert_first = NULL; + /* ScanFillEdge *e; */ /* UNUSED */ + ScanFillFace *sf_tri; + int totfilltri; + + if (UNLIKELY(sf_arena == NULL)) { + sf_arena = BLI_memarena_new(BLI_SCANFILL_ARENA_SIZE, __func__); + } + + BLI_scanfill_begin_arena(&sf_ctx, sf_arena); + + /* scanfill time */ + j = 0; + l_iter = l_first = BM_FACE_FIRST_LOOP(efa); + 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; + } + + /*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, efa->no); + BLI_assert(totfilltri <= efa->len - 2); + (void)totfilltri; + + for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) { + BMLoop **l_ptr = looptris[i++]; + BMLoop *l1 = sf_tri->v1->tmp.p; + BMLoop *l2 = sf_tri->v2->tmp.p; + BMLoop *l3 = sf_tri->v3->tmp.p; + + if (BM_elem_index_get(l1) > BM_elem_index_get(l2)) { SWAP(BMLoop *, l1, l2); } + if (BM_elem_index_get(l2) > BM_elem_index_get(l3)) { SWAP(BMLoop *, l2, l3); } + if (BM_elem_index_get(l1) > BM_elem_index_get(l2)) { SWAP(BMLoop *, l1, l2); } + + l_ptr[0] = l1; + l_ptr[1] = l2; + l_ptr[2] = l3; + } + + BLI_scanfill_end_arena(&sf_ctx, sf_arena); + } + } + + if (sf_arena) { + BLI_memarena_free(sf_arena); + sf_arena = NULL; + } + + *r_looptris_tot = looptris_tot; + + BLI_assert(i <= looptris_tot); + +#undef USE_TESSFACE_SPEEDUP + +} diff --git a/source/blender/bmesh/intern/bmesh_polygon.h b/source/blender/bmesh/intern/bmesh_polygon.h index 4759c73cb4d..5d98a9a40db 100644 --- a/source/blender/bmesh/intern/bmesh_polygon.h +++ b/source/blender/bmesh/intern/bmesh_polygon.h @@ -29,6 +29,8 @@ #include "BLI_compiler_attrs.h" +void BM_bmesh_calc_tessellation(BMesh *bm, BMLoop *(*looptris)[], int *r_looptris_tot); + int BM_face_calc_tessellation(const BMFace *f, BMLoop **r_loops, int (*r_index)[3]) ATTR_WARN_UNUSED_RESULT ATTR_NONNULL(); void BM_face_calc_normal(const BMFace *f, float r_no[3]) ATTR_NONNULL(); void BM_face_calc_normal_vcos(BMesh *bm, BMFace *f, float r_no[3], -- cgit v1.2.3