From f0c1bc830c790f46fbe971ab7242dfb7b1cad469 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Thu, 27 Dec 2012 06:39:27 +0000 Subject: add option to BLI_scanfill_calc() - BLI_SCANFILL_CALC_HOLES, gives some speedup for BMesh ngons which never have holes and ensures predictable triangle count (totvert - 2), which is needed for pre-calculating array size. --- source/blender/blenkernel/intern/displist.c | 2 +- source/blender/blenkernel/intern/editderivedmesh.c | 37 ++++--- source/blender/blenkernel/intern/mask_rasterize.c | 2 +- source/blender/blenkernel/intern/mesh.c | 54 +++++----- source/blender/blenlib/BLI_scanfill.h | 4 + source/blender/blenlib/intern/scanfill.c | 109 +++++++++++++-------- source/blender/windowmanager/intern/wm_gesture.c | 2 +- 7 files changed, 117 insertions(+), 93 deletions(-) diff --git a/source/blender/blenkernel/intern/displist.c b/source/blender/blenkernel/intern/displist.c index 47cb18a7172..5fff8a51214 100644 --- a/source/blender/blenkernel/intern/displist.c +++ b/source/blender/blenkernel/intern/displist.c @@ -506,7 +506,7 @@ void BKE_displist_fill(ListBase *dispbase, ListBase *to, int flipnormal) } /* XXX (obedit && obedit->actcol)?(obedit->actcol-1):0)) { */ - if (totvert && (tot = BLI_scanfill_calc(&sf_ctx, BLI_SCANFILL_CALC_REMOVE_DOUBLES))) { + if (totvert && (tot = BLI_scanfill_calc(&sf_ctx, BLI_SCANFILL_CALC_REMOVE_DOUBLES | BLI_SCANFILL_CALC_HOLES))) { if (tot) { dlnew = MEM_callocN(sizeof(DispList), "filldisplist"); dlnew->type = DL_INDEX3; diff --git a/source/blender/blenkernel/intern/editderivedmesh.c b/source/blender/blenkernel/intern/editderivedmesh.c index fc0c40878db..1c43b418a1c 100644 --- a/source/blender/blenkernel/intern/editderivedmesh.c +++ b/source/blender/blenkernel/intern/editderivedmesh.c @@ -173,12 +173,10 @@ static void BMEdit_RecalcTessellation_intern(BMEditMesh *em) 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; - } + 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) { @@ -201,14 +199,12 @@ static void BMEdit_RecalcTessellation_intern(BMEditMesh *em) 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); - } + 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 } @@ -222,7 +218,7 @@ static void BMEdit_RecalcTessellation_intern(BMEditMesh *em) ScanFillVert *sf_vert, *sf_vert_last = NULL, *sf_vert_first = NULL; /* ScanFillEdge *e; */ /* UNUSED */ ScanFillFace *sf_tri; - /* int totfilltri; */ /* UNUSED */ + int totfilltri; BLI_scanfill_begin(&sf_ctx); @@ -250,9 +246,11 @@ static void BMEdit_RecalcTessellation_intern(BMEditMesh *em) /* complete the loop */ BLI_scanfill_edge_add(&sf_ctx, sf_vert_first, sf_vert); - /* totfilltri = */ BLI_scanfill_calc_ex(&sf_ctx, 0, efa->no); + totfilltri = BLI_scanfill_calc_ex(&sf_ctx, 0, efa->no); + BLI_assert(totfilltri <= efa->len - 2); 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; @@ -261,10 +259,9 @@ static void BMEdit_RecalcTessellation_intern(BMEditMesh *em) 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); } - looptris[i][0] = l1; - looptris[i][1] = l2; - looptris[i][2] = l3; - i += 1; + l_ptr[0] = l1; + l_ptr[1] = l2; + l_ptr[2] = l3; } BLI_scanfill_end(&sf_ctx); diff --git a/source/blender/blenkernel/intern/mask_rasterize.c b/source/blender/blenkernel/intern/mask_rasterize.c index 2fa928e7c07..73452b216ff 100644 --- a/source/blender/blenkernel/intern/mask_rasterize.c +++ b/source/blender/blenkernel/intern/mask_rasterize.c @@ -933,7 +933,7 @@ void BKE_maskrasterize_handle_init(MaskRasterHandle *mr_handle, struct Mask *mas } /* main scan-fill */ - sf_tri_tot = BLI_scanfill_calc_ex(&sf_ctx, 0, zvec); + sf_tri_tot = BLI_scanfill_calc_ex(&sf_ctx, BLI_SCANFILL_CALC_HOLES, zvec); face_array = MEM_mallocN(sizeof(*face_array) * (sf_tri_tot + tot_feather_quads), "maskrast_face_index"); face_index = 0; diff --git a/source/blender/blenkernel/intern/mesh.c b/source/blender/blenkernel/intern/mesh.c index 3eb96f218e4..f788bbabf4d 100644 --- a/source/blender/blenkernel/intern/mesh.c +++ b/source/blender/blenkernel/intern/mesh.c @@ -2488,7 +2488,7 @@ void BKE_mesh_loops_to_mface_corners(CustomData *fdata, CustomData *ldata, */ int BKE_mesh_recalc_tessellation(CustomData *fdata, CustomData *ldata, CustomData *pdata, - MVert *mvert, int totface, int UNUSED(totloop), + MVert *mvert, int totface, int totloop, int totpoly, /* when tessellating to recalculate normals after * we can skip copying here */ @@ -2503,15 +2503,15 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, #define TESSFACE_SCANFILL (1 << 0) #define TESSFACE_IS_QUAD (1 << 1) + const int looptris_tot = poly_to_tri_count(totpoly, totloop); + MPoly *mp, *mpoly; MLoop *ml, *mloop; - MFace *mface = NULL, *mf; - BLI_array_declare(mface); + MFace *mface, *mf; ScanFillContext sf_ctx; ScanFillVert *sf_vert, *sf_vert_last, *sf_vert_first; ScanFillFace *sf_tri; - int *mface_to_poly_map = NULL; - BLI_array_declare(mface_to_poly_map); + int *mface_to_poly_map; int lindex[4]; /* only ever use 3 in this case */ int poly_index, j, mface_index; @@ -2525,8 +2525,9 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, /* allocate the length of totfaces, avoid many small reallocs, * if all faces are tri's it will be correct, quads == 2x allocs */ - BLI_array_reserve(mface_to_poly_map, totpoly); - BLI_array_reserve(mface, totpoly); + /* take care. we are _not_ calloc'ing so be sure to initialize each field */ + mface_to_poly_map = MEM_mallocN(sizeof(*mface_to_poly_map) * looptris_tot, __func__); + mface = MEM_mallocN(sizeof(*mface) * looptris_tot, __func__); mface_index = 0; mp = mpoly; @@ -2538,8 +2539,6 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, #ifdef USE_TESSFACE_SPEEDUP #define ML_TO_MF(i1, i2, i3) \ - BLI_array_grow_one(mface_to_poly_map); \ - BLI_array_grow_one(mface); \ mface_to_poly_map[mface_index] = poly_index; \ mf = &mface[mface_index]; \ /* set loop indices, transformed to vert indices later */ \ @@ -2549,12 +2548,11 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, mf->v4 = 0; \ mf->mat_nr = mp->mat_nr; \ mf->flag = mp->flag; \ + mf->edcode = 0; \ (void)0 /* ALMOST IDENTICAL TO DEFINE ABOVE (see EXCEPTION) */ #define ML_TO_MF_QUAD() \ - BLI_array_grow_one(mface_to_poly_map); \ - BLI_array_grow_one(mface); \ mface_to_poly_map[mface_index] = poly_index; \ mf = &mface[mface_index]; \ /* set loop indices, transformed to vert indices later */ \ @@ -2564,7 +2562,7 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, mf->v4 = mp->loopstart + 3; /* EXCEPTION */ \ mf->mat_nr = mp->mat_nr; \ mf->flag = mp->flag; \ - mf->edcode |= TESSFACE_IS_QUAD; /* EXCEPTION */ \ + mf->edcode = TESSFACE_IS_QUAD; /* EXCEPTION */ \ (void)0 @@ -2607,29 +2605,26 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, BLI_scanfill_edge_add(&sf_ctx, sf_vert_last, sf_vert_first); totfilltri = BLI_scanfill_calc(&sf_ctx, 0); - if (totfilltri) { - BLI_array_grow_items(mface_to_poly_map, totfilltri); - BLI_array_grow_items(mface, totfilltri); + BLI_assert(totfilltri <= mp->totloop - 2); - for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next, mf++) { - mface_to_poly_map[mface_index] = poly_index; - mf = &mface[mface_index]; + for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next, mf++) { + mface_to_poly_map[mface_index] = poly_index; + mf = &mface[mface_index]; - /* set loop indices, transformed to vert indices later */ - mf->v1 = sf_tri->v1->keyindex; - mf->v2 = sf_tri->v2->keyindex; - mf->v3 = sf_tri->v3->keyindex; - mf->v4 = 0; + /* set loop indices, transformed to vert indices later */ + mf->v1 = sf_tri->v1->keyindex; + mf->v2 = sf_tri->v2->keyindex; + mf->v3 = sf_tri->v3->keyindex; + mf->v4 = 0; - mf->mat_nr = mp->mat_nr; - mf->flag = mp->flag; + mf->mat_nr = mp->mat_nr; + mf->flag = mp->flag; #ifdef USE_TESSFACE_SPEEDUP - mf->edcode |= TESSFACE_SCANFILL; /* tag for sorting loop indices */ + mf->edcode = TESSFACE_SCANFILL; /* tag for sorting loop indices */ #endif - mface_index++; - } + mface_index++; } BLI_scanfill_end(&sf_ctx); @@ -2639,9 +2634,10 @@ int BKE_mesh_recalc_tessellation(CustomData *fdata, CustomData_free(fdata, totface); totface = mface_index; + BLI_assert(totface <= looptris_tot); /* not essential but without this we store over-alloc'd memory in the CustomData layers */ - if (LIKELY((MEM_allocN_len(mface) / sizeof(*mface)) != totface)) { + if (LIKELY(looptris_tot != totface)) { mface = MEM_reallocN(mface, sizeof(*mface) * totface); mface_to_poly_map = MEM_reallocN(mface_to_poly_map, sizeof(*mface_to_poly_map) * totface); } diff --git a/source/blender/blenlib/BLI_scanfill.h b/source/blender/blenlib/BLI_scanfill.h index c8fd72bbbd2..5204e0dd718 100644 --- a/source/blender/blenlib/BLI_scanfill.h +++ b/source/blender/blenlib/BLI_scanfill.h @@ -101,6 +101,10 @@ enum { * Assumes ordered edges, otherwise we risk an eternal loop * removing double verts. - campbell */ BLI_SCANFILL_CALC_REMOVE_DOUBLES = (1 << 1), + + /* note: This flag removes checks for overlapping polygons. + * when this flag is set, we'll never get back more faces then (totvert - 2)*/ + BLI_SCANFILL_CALC_HOLES = (1 << 2) }; int BLI_scanfill_begin(ScanFillContext *sf_ctx); diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c index defe500cb21..45c6c5efbb3 100644 --- a/source/blender/blenlib/intern/scanfill.c +++ b/source/blender/blenlib/intern/scanfill.c @@ -630,7 +630,12 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag) /* (temporal) security: never much more faces than vertices */ totface = 0; - maxface = 2 * verts; /* 2*verts: based at a filled circle within a triangle */ + if (flag & BLI_SCANFILL_CALC_HOLES) { + maxface = 2 * verts; /* 2*verts: based at a filled circle within a triangle */ + } + else { + maxface = verts - 2; /* when we don't calc any holes, we assume face is a non overlapping loop */ + } sc = sf_ctx->_scdata; for (a = 0; a < verts; a++) { @@ -654,7 +659,7 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag) /* commented out... the ESC here delivers corrupted memory (and doesnt work during grab) */ /* if (callLocalInterruptCallBack()) break; */ - if (totface > maxface) { + if (totface >= maxface) { /* printf("Fill error: endless loop. Escaped at vert %d, tot: %d.\n", a, verts); */ a = verts; break; @@ -684,15 +689,16 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag) for (b = a + 1; b < verts; b++) { if (sc1->vert->f == 0) { if (sc1->vert->xy[1] <= miny) break; - - if (testedgeside(v1->xy, v2->xy, sc1->vert->xy)) - if (testedgeside(v2->xy, v3->xy, sc1->vert->xy)) + if (testedgeside(v1->xy, v2->xy, sc1->vert->xy)) { + if (testedgeside(v2->xy, v3->xy, sc1->vert->xy)) { if (testedgeside(v3->xy, v1->xy, sc1->vert->xy)) { /* point in triangle */ - + test = 1; break; } + } + } } sc1++; } @@ -773,12 +779,15 @@ static int scanfill(ScanFillContext *sf_ctx, PolyFill *pf, const int flag) ed1 = nexted; } } + sc++; } MEM_freeN(sf_ctx->_scdata); sf_ctx->_scdata = NULL; + BLI_assert(totface <= maxface); + return totface; } @@ -910,50 +919,68 @@ int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, const int flag, const float no /* STEP 1: COUNT POLYS */ - eve = sf_ctx->fillvertbase.first; - while (eve) { - eve->xy[0] = eve->co[co_x]; - eve->xy[1] = eve->co[co_y]; + if (flag & BLI_SCANFILL_CALC_HOLES) { + eve = sf_ctx->fillvertbase.first; + while (eve) { + eve->xy[0] = eve->co[co_x]; + eve->xy[1] = eve->co[co_y]; + + /* get first vertex with no poly number */ + if (eve->poly_nr == 0) { + poly++; + /* now a sort of select connected */ + ok = 1; + eve->poly_nr = poly; - /* get first vertex with no poly number */ - if (eve->poly_nr == 0) { - poly++; - /* now a sort of select connected */ - ok = 1; - eve->poly_nr = poly; - - while (ok) { - - ok = 0; - toggle++; - if (toggle & 1) eed = sf_ctx->filledgebase.first; - else eed = sf_ctx->filledgebase.last; - - while (eed) { - if (eed->v1->poly_nr == 0 && eed->v2->poly_nr == poly) { - eed->v1->poly_nr = poly; - eed->poly_nr = poly; - ok = 1; - } - else if (eed->v2->poly_nr == 0 && eed->v1->poly_nr == poly) { - eed->v2->poly_nr = poly; - eed->poly_nr = poly; - ok = 1; - } - else if (eed->poly_nr == 0) { - if (eed->v1->poly_nr == poly && eed->v2->poly_nr == poly) { + while (ok) { + + ok = 0; + toggle++; + if (toggle & 1) eed = sf_ctx->filledgebase.first; + else eed = sf_ctx->filledgebase.last; + + while (eed) { + if (eed->v1->poly_nr == 0 && eed->v2->poly_nr == poly) { + eed->v1->poly_nr = poly; eed->poly_nr = poly; ok = 1; } + else if (eed->v2->poly_nr == 0 && eed->v1->poly_nr == poly) { + eed->v2->poly_nr = poly; + eed->poly_nr = poly; + ok = 1; + } + else if (eed->poly_nr == 0) { + if (eed->v1->poly_nr == poly && eed->v2->poly_nr == poly) { + eed->poly_nr = poly; + ok = 1; + } + } + if (toggle & 1) eed = eed->next; + else eed = eed->prev; } - if (toggle & 1) eed = eed->next; - else eed = eed->prev; } } + eve = eve->next; + } + /* printf("amount of poly's: %d\n",poly); */ + } + else { + poly = 1; + + eve = sf_ctx->fillvertbase.first; + while (eve) { + eve->xy[0] = eve->co[co_x]; + eve->xy[1] = eve->co[co_y]; + eve->poly_nr = poly; + eve = eve->next; + } + eed = sf_ctx->filledgebase.first; + while (eed) { + eed->poly_nr = poly; + eed = eed->next; } - eve = eve->next; } - /* printf("amount of poly's: %d\n",poly); */ /* STEP 2: remove loose edges and strings of edges */ eed = sf_ctx->filledgebase.first; diff --git a/source/blender/windowmanager/intern/wm_gesture.c b/source/blender/windowmanager/intern/wm_gesture.c index 1cf44a69c17..168c2312d9f 100644 --- a/source/blender/windowmanager/intern/wm_gesture.c +++ b/source/blender/windowmanager/intern/wm_gesture.c @@ -258,7 +258,7 @@ static void draw_filled_lasso(wmGesture *gt) if (sf_vert_first) { const float zvec[3] = {0.0f, 0.0f, 1.0f}; BLI_scanfill_edge_add(&sf_ctx, sf_vert_first, sf_vert); - BLI_scanfill_calc_ex(&sf_ctx, BLI_SCANFILL_CALC_REMOVE_DOUBLES, zvec); + BLI_scanfill_calc_ex(&sf_ctx, BLI_SCANFILL_CALC_REMOVE_DOUBLES | BLI_SCANFILL_CALC_HOLES, zvec); glEnable(GL_BLEND); glColor4f(1.0, 1.0, 1.0, 0.05); -- cgit v1.2.3