From 8b1731e13dcd0d9ef98520f62fe0c841218bfd00 Mon Sep 17 00:00:00 2001 From: Campbell Barton Date: Tue, 4 Feb 2014 02:54:19 +1100 Subject: Scanfill: skip checks for loose edges when they can't occur Only editmesh needs this, text, curves, masks - can all skip this check --- source/blender/blenlib/BLI_scanfill.h | 5 +- source/blender/blenlib/intern/scanfill.c | 92 ++++++++++++++---------- source/blender/bmesh/operators/bmo_triangulate.c | 2 +- 3 files changed, 59 insertions(+), 40 deletions(-) (limited to 'source') diff --git a/source/blender/blenlib/BLI_scanfill.h b/source/blender/blenlib/BLI_scanfill.h index 52f5decb4f4..3caa69f91c6 100644 --- a/source/blender/blenlib/BLI_scanfill.h +++ b/source/blender/blenlib/BLI_scanfill.h @@ -98,7 +98,10 @@ enum { /* 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) + BLI_SCANFILL_CALC_HOLES = (1 << 2), + + /* checks valid edge users - can skip for simple loops */ + BLI_SCANFILL_CALC_LOOSE = (1 << 3), }; void BLI_scanfill_begin(ScanFillContext *sf_ctx); unsigned int BLI_scanfill_calc(ScanFillContext *sf_ctx, const int flag); diff --git a/source/blender/blenlib/intern/scanfill.c b/source/blender/blenlib/intern/scanfill.c index 54c8b0f5b72..b12e982c708 100644 --- a/source/blender/blenlib/intern/scanfill.c +++ b/source/blender/blenlib/intern/scanfill.c @@ -337,7 +337,7 @@ static bool boundinsideEV(ScanFillEdge *eed, ScanFillVert *eve) static void testvertexnearedge(ScanFillContext *sf_ctx) { - /* only vertices with (->h == 1) are being tested for + /* only vertices with (->edge_tot == 1) are being tested for * being close to an edge, if true insert */ ScanFillVert *eve; @@ -927,48 +927,64 @@ unsigned int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, const int flag, const } /* STEP 2: remove loose edges and strings of edges */ - for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) { - if (eed->v1->edge_tot++ > 250) break; - if (eed->v2->edge_tot++ > 250) break; - } - if (eed) { - /* otherwise it's impossible to be sure you can clear vertices */ + if (flag & BLI_SCANFILL_CALC_LOOSE) { + for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) { + if (eed->v1->edge_tot++ > 250) break; + if (eed->v2->edge_tot++ > 250) break; + } + if (eed) { + /* otherwise it's impossible to be sure you can clear vertices */ #ifdef DEBUG - printf("No vertices with 250 edges allowed!\n"); + printf("No vertices with 250 edges allowed!\n"); #endif - return 0; - } - - /* does it only for vertices with (->h == 1) */ - testvertexnearedge(sf_ctx); - - ok = true; - while (ok) { - ok = false; - - toggle++; - for (eed = (toggle & 1) ? sf_ctx->filledgebase.first : sf_ctx->filledgebase.last; - eed; - eed = eed_next) - { - eed_next = (toggle & 1) ? eed->next : eed->prev; - if (eed->v1->edge_tot == 1) { - eed->v2->edge_tot--; - BLI_remlink(&sf_ctx->fillvertbase, eed->v1); - BLI_remlink(&sf_ctx->filledgebase, eed); - ok = true; - } - else if (eed->v2->edge_tot == 1) { - eed->v1->edge_tot--; - BLI_remlink(&sf_ctx->fillvertbase, eed->v2); - BLI_remlink(&sf_ctx->filledgebase, eed); - ok = true; + return 0; + } + + /* does it only for vertices with (->edge_tot == 1) */ + testvertexnearedge(sf_ctx); + + ok = true; + while (ok) { + ok = false; + + toggle++; + for (eed = (toggle & 1) ? sf_ctx->filledgebase.first : sf_ctx->filledgebase.last; + eed; + eed = eed_next) + { + eed_next = (toggle & 1) ? eed->next : eed->prev; + if (eed->v1->edge_tot == 1) { + eed->v2->edge_tot--; + BLI_remlink(&sf_ctx->fillvertbase, eed->v1); + BLI_remlink(&sf_ctx->filledgebase, eed); + ok = true; + } + else if (eed->v2->edge_tot == 1) { + eed->v1->edge_tot--; + BLI_remlink(&sf_ctx->fillvertbase, eed->v2); + BLI_remlink(&sf_ctx->filledgebase, eed); + ok = true; + } } } + if (sf_ctx->filledgebase.first == NULL) { + /* printf("All edges removed\n"); */ + return 0; + } } - if (sf_ctx->filledgebase.first == NULL) { - /* printf("All edges removed\n"); */ - return 0; + else { + /* skip checks for loose edges */ + for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) { + eed->v1->edge_tot++; + eed->v2->edge_tot++; + } +#ifdef DEBUG + /* ensure we're right! */ + for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) { + BLI_assert(eed->v1->edge_tot != 1); + BLI_assert(eed->v2->edge_tot != 1); + } +#endif } diff --git a/source/blender/bmesh/operators/bmo_triangulate.c b/source/blender/bmesh/operators/bmo_triangulate.c index 30ae01ef713..b66c91678c0 100644 --- a/source/blender/bmesh/operators/bmo_triangulate.c +++ b/source/blender/bmesh/operators/bmo_triangulate.c @@ -104,7 +104,7 @@ void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op) normal_pt = normal; } - BLI_scanfill_calc_ex(&sf_ctx, BLI_SCANFILL_CALC_HOLES, normal_pt); + BLI_scanfill_calc_ex(&sf_ctx, BLI_SCANFILL_CALC_HOLES | BLI_SCANFILL_CALC_LOOSE, normal_pt); for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) { BMFace *f = BM_face_create_quad_tri(bm, -- cgit v1.2.3