Mask: add option to detect self intersections
This commit is contained in:
parent
c85e66e7fe
commit
ae8327dbf3
Notes:
blender-bot
2023-02-14 11:29:55 +01:00
Referenced by issue #37758, Mask Editor - Overlapping masks seem to be inconsistant
|
@ -108,6 +108,7 @@ class MASK_PT_layers:
|
|||
layout.prop(active_layer, "falloff")
|
||||
|
||||
row = layout.row(align=True)
|
||||
layout.prop(active_layer, "use_fill_overlap")
|
||||
layout.prop(active_layer, "use_fill_holes")
|
||||
|
||||
|
||||
|
|
|
@ -459,6 +459,7 @@ void BKE_displist_fill(ListBase *dispbase, ListBase *to, const float normal_proj
|
|||
float *f1;
|
||||
int colnr = 0, charidx = 0, cont = 1, tot, a, *index, nextcol = 0;
|
||||
int totvert;
|
||||
const int scanfill_flag = BLI_SCANFILL_CALC_REMOVE_DOUBLES | BLI_SCANFILL_CALC_POLYS | BLI_SCANFILL_CALC_HOLES;
|
||||
|
||||
if (dispbase == NULL)
|
||||
return;
|
||||
|
@ -519,7 +520,7 @@ void BKE_displist_fill(ListBase *dispbase, ListBase *to, const float normal_proj
|
|||
|
||||
/* XXX (obedit && obedit->actcol) ? (obedit->actcol-1) : 0)) { */
|
||||
if (totvert && (tot = BLI_scanfill_calc_ex(&sf_ctx,
|
||||
BLI_SCANFILL_CALC_REMOVE_DOUBLES | BLI_SCANFILL_CALC_HOLES,
|
||||
scanfill_flag,
|
||||
normal_proj)))
|
||||
{
|
||||
if (tot) {
|
||||
|
|
|
@ -918,6 +918,10 @@ void BKE_maskrasterize_handle_init(MaskRasterHandle *mr_handle, struct Mask *mas
|
|||
unsigned int face_index;
|
||||
int scanfill_flag = 0;
|
||||
|
||||
bool is_isect = false;
|
||||
ListBase isect_remvertbase = {NULL, NULL};
|
||||
ListBase isect_remedgebase = {NULL, NULL};
|
||||
|
||||
/* now we have all the splines */
|
||||
face_coords = MEM_mallocN((sizeof(float) * 3) * sf_vert_tot, "maskrast_face_coords");
|
||||
|
||||
|
@ -941,12 +945,50 @@ void BKE_maskrasterize_handle_init(MaskRasterHandle *mr_handle, struct Mask *mas
|
|||
cos += 3;
|
||||
}
|
||||
|
||||
|
||||
/* --- inefficient self-intersect case --- */
|
||||
/* if self intersections are found, its too trickty to attempt to map vertices
|
||||
* so just realloc and add entirely new vertices - the result of the self-intersect check
|
||||
*/
|
||||
if ((masklay->flag & MASK_LAYERFLAG_FILL_OVERLAP) &&
|
||||
(is_isect = BLI_scanfill_calc_self_isect(&sf_ctx,
|
||||
&isect_remvertbase,
|
||||
&isect_remedgebase)))
|
||||
{
|
||||
unsigned int sf_vert_tot_isect = (unsigned int)BLI_countlist(&sf_ctx.fillvertbase);
|
||||
unsigned int i = sf_vert_tot;
|
||||
|
||||
face_coords = MEM_reallocN(face_coords, sizeof(float[3]) * (sf_vert_tot + sf_vert_tot_isect));
|
||||
|
||||
cos = (float *)&face_coords[sf_vert_tot][0];
|
||||
|
||||
for (sf_vert = sf_ctx.fillvertbase.first; sf_vert; sf_vert = sf_vert->next) {
|
||||
copy_v3_v3(cos, sf_vert->co);
|
||||
sf_vert->tmp.u = i++;
|
||||
cos += 3;
|
||||
}
|
||||
|
||||
sf_vert_tot += sf_vert_tot_isect;
|
||||
|
||||
/* we need to calc polys after self intersect */
|
||||
scanfill_flag |= BLI_SCANFILL_CALC_POLYS;
|
||||
}
|
||||
/* --- end inefficient code --- */
|
||||
|
||||
|
||||
/* main scan-fill */
|
||||
if ((masklay->flag & MASK_LAYERFLAG_FILL_DISCRETE) == 0)
|
||||
scanfill_flag |= BLI_SCANFILL_CALC_HOLES;
|
||||
|
||||
sf_tri_tot = (unsigned int)BLI_scanfill_calc_ex(&sf_ctx, scanfill_flag, zvec);
|
||||
|
||||
if (is_isect) {
|
||||
/* add removed data back, we only need edges for feather,
|
||||
* but add verts back so they get freed along with others */
|
||||
BLI_movelisttolist(&sf_ctx.fillvertbase, &isect_remvertbase);
|
||||
BLI_movelisttolist(&sf_ctx.filledgebase, &isect_remedgebase);
|
||||
}
|
||||
|
||||
face_array = MEM_mallocN(sizeof(*face_array) * ((size_t)sf_tri_tot + (size_t)tot_feather_quads), "maskrast_face_index");
|
||||
face_index = 0;
|
||||
|
||||
|
|
|
@ -56,6 +56,13 @@ typedef struct ScanFillContext {
|
|||
|
||||
#define BLI_SCANFILL_ARENA_SIZE MEM_SIZE_OPTIMAL(1 << 14)
|
||||
|
||||
/**
|
||||
* \note this is USHRT_MAX so incrementing will set to zero
|
||||
* which happens if callers choose to increment #ScanFillContext.poly_nr before adding each curve.
|
||||
* Nowhere else in scanfill do we make use of intentional overflow like this.
|
||||
*/
|
||||
#define SF_POLY_UNSET ((unsigned short)-1)
|
||||
|
||||
typedef struct ScanFillVert {
|
||||
struct ScanFillVert *next, *prev;
|
||||
union {
|
||||
|
@ -101,12 +108,15 @@ enum {
|
|||
* removing double verts. - campbell */
|
||||
BLI_SCANFILL_CALC_REMOVE_DOUBLES = (1 << 1),
|
||||
|
||||
/* calculate isolated polygons */
|
||||
BLI_SCANFILL_CALC_POLYS = (1 << 2),
|
||||
|
||||
/* 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 << 3),
|
||||
|
||||
/* checks valid edge users - can skip for simple loops */
|
||||
BLI_SCANFILL_CALC_LOOSE = (1 << 3),
|
||||
BLI_SCANFILL_CALC_LOOSE = (1 << 4),
|
||||
};
|
||||
void BLI_scanfill_begin(ScanFillContext *sf_ctx);
|
||||
unsigned int BLI_scanfill_calc(ScanFillContext *sf_ctx, const int flag);
|
||||
|
@ -117,6 +127,13 @@ void BLI_scanfill_end(ScanFillContext *sf_ctx);
|
|||
void BLI_scanfill_begin_arena(ScanFillContext *sf_ctx, struct MemArena *arena);
|
||||
void BLI_scanfill_end_arena(ScanFillContext *sf_ctx, struct MemArena *arena);
|
||||
|
||||
|
||||
/* scanfill_utils.c */
|
||||
bool BLI_scanfill_calc_self_isect(
|
||||
ScanFillContext *sf_ctx,
|
||||
ListBase *fillvertbase,
|
||||
ListBase *filledgebase);
|
||||
|
||||
#ifdef __cplusplus
|
||||
}
|
||||
#endif
|
||||
|
|
|
@ -87,6 +87,7 @@ set(SRC
|
|||
intern/rand.c
|
||||
intern/rct.c
|
||||
intern/scanfill.c
|
||||
intern/scanfill_utils.c
|
||||
intern/smallhash.c
|
||||
intern/sort.c
|
||||
intern/sort_utils.c
|
||||
|
|
|
@ -38,7 +38,6 @@
|
|||
|
||||
#include "MEM_guardedalloc.h"
|
||||
|
||||
#include "BLI_callbacks.h"
|
||||
#include "BLI_listbase.h"
|
||||
#include "BLI_math.h"
|
||||
#include "BLI_memarena.h"
|
||||
|
@ -85,16 +84,6 @@ typedef struct ScanFillVertLink {
|
|||
#define SF_POLY_NEW 0 /* all polys initialized to this */
|
||||
#define SF_POLY_VALID 1 /* has at least 3 verts */
|
||||
|
||||
|
||||
/**
|
||||
* \note this is USHRT_MAX so incrementing will set to zero
|
||||
* which happens if callers choose to increment #ScanFillContext.poly_nr before adding each curve.
|
||||
* Nowhere else in scanfill do we make use of intentional overflow like this.
|
||||
*/
|
||||
#define SF_POLY_UNSET USHRT_MAX
|
||||
|
||||
|
||||
|
||||
/* **** FUNCTIONS FOR QSORT *************************** */
|
||||
|
||||
|
||||
|
@ -903,7 +892,7 @@ unsigned int BLI_scanfill_calc_ex(ScanFillContext *sf_ctx, const int flag, const
|
|||
sf_ctx->poly_nr = SF_POLY_UNSET;
|
||||
}
|
||||
|
||||
if (flag & BLI_SCANFILL_CALC_HOLES && (poly == 0)) {
|
||||
if (flag & BLI_SCANFILL_CALC_POLYS && (poly == 0)) {
|
||||
for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
|
||||
mul_v2_m3v3(eve->xy, mat_2d, eve->co);
|
||||
|
||||
|
|
|
@ -0,0 +1,509 @@
|
|||
/*
|
||||
* ***** BEGIN GPL LICENSE BLOCK *****
|
||||
*
|
||||
* This program is free software; you can redistribute it and/or
|
||||
* modify it under the terms of the GNU General Public License
|
||||
* as published by the Free Software Foundation; either version 2
|
||||
* of the License, or (at your option) any later version.
|
||||
*
|
||||
* This program is distributed in the hope that it will be useful,
|
||||
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
||||
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
||||
* GNU General Public License for more details.
|
||||
*
|
||||
* You should have received a copy of the GNU General Public License
|
||||
* along with this program; if not, write to the Free Software Foundation,
|
||||
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
|
||||
*
|
||||
* Contributor(s): Campbell Barton
|
||||
*
|
||||
* ***** END GPL LICENSE BLOCK *****
|
||||
*/
|
||||
|
||||
/** \file blender/blenlib/intern/scanfill_utils.c
|
||||
* \ingroup bli
|
||||
*/
|
||||
|
||||
#include <stdio.h>
|
||||
#include <math.h>
|
||||
#include <stdlib.h>
|
||||
#include <string.h>
|
||||
#include <limits.h>
|
||||
|
||||
#include "MEM_guardedalloc.h"
|
||||
|
||||
#include "BLI_listbase.h"
|
||||
#include "BLI_math.h"
|
||||
#include "BLI_utildefines.h"
|
||||
#include "BLI_strict_flags.h"
|
||||
#include "BLI_ghash.h"
|
||||
|
||||
#include "BLI_scanfill.h" /* own include */
|
||||
|
||||
|
||||
typedef struct PolyInfo {
|
||||
ScanFillEdge *edge_first, *edge_last;
|
||||
ScanFillVert *vert_outer;
|
||||
} PolyInfo;
|
||||
|
||||
typedef struct PolySort {
|
||||
float area;
|
||||
unsigned short poly_nr;
|
||||
} PolySort;
|
||||
|
||||
typedef struct ScanFillIsect {
|
||||
struct ScanFillIsect *next, *prev;
|
||||
float co[3];
|
||||
|
||||
/* newly created vertex */
|
||||
ScanFillVert *v;
|
||||
} ScanFillIsect;
|
||||
|
||||
|
||||
#define V_ISISECT 1
|
||||
#define E_ISISECT 1
|
||||
#define E_ISDELETE 2
|
||||
|
||||
|
||||
#define EFLAG_SET(eed, val) { CHECK_TYPE(eed, ScanFillEdge *); \
|
||||
(eed)->user_flag = (eed)->user_flag | (unsigned int)val; } (void)0
|
||||
#if 0
|
||||
#define EFLAG_CLEAR(eed, val) { CHECK_TYPE(eed, ScanFillEdge *); \
|
||||
(eed)->user_flag = (eed)->user_flag & ~(unsigned int)val; } (void)0
|
||||
#endif
|
||||
|
||||
#define VFLAG_SET(eve, val) { CHECK_TYPE(eve, ScanFillVert *); \
|
||||
(eve)->user_flag = (eve)->user_flag | (unsigned int)val; } (void)0
|
||||
#if 0
|
||||
#define VFLAG_CLEAR(eve, val) { CHECK_TYPE(eve, ScanFillVert *); \
|
||||
(eve)->user_flags = (eve)->user_flag & ~(unsigned int)val; } (void)0
|
||||
#endif
|
||||
|
||||
|
||||
#if 0
|
||||
void BKE_scanfill_obj_dump(ScanFillContext *sf_ctx)
|
||||
{
|
||||
FILE *f = fopen("test.obj", "w");
|
||||
unsigned int i = 1;
|
||||
|
||||
ScanFillVert *eve;
|
||||
ScanFillEdge *eed;
|
||||
|
||||
for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next, i++) {
|
||||
fprintf(f, "v %f %f %f\n", UNPACK3(eve->co));
|
||||
eve->keyindex = i;
|
||||
}
|
||||
for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
|
||||
fprintf(f, "f %d %d\n", eed->v1->keyindex, eed->v2->keyindex);
|
||||
}
|
||||
fclose(f);
|
||||
}
|
||||
#endif
|
||||
|
||||
#if 0
|
||||
void BKE_scanfill_view3d_dump(ScanFillContext *sf_ctx)
|
||||
{
|
||||
ScanFillEdge *eed;
|
||||
|
||||
bl_debug_draw_quad_clear();
|
||||
bl_debug_color_set(0x0000ff);
|
||||
|
||||
for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
|
||||
bl_debug_draw_edge_add(eed->v1->co, eed->v2->co);
|
||||
}
|
||||
}
|
||||
#endif
|
||||
|
||||
static ListBase *edge_isect_ls_ensure(GHash *isect_hash, ScanFillEdge *eed)
|
||||
{
|
||||
ListBase *e_ls;
|
||||
e_ls = BLI_ghash_lookup(isect_hash, eed);
|
||||
if (e_ls == NULL) {
|
||||
e_ls = MEM_callocN(sizeof(ListBase), __func__);
|
||||
BLI_ghash_insert(isect_hash, eed, e_ls);
|
||||
}
|
||||
return e_ls;
|
||||
}
|
||||
|
||||
static ListBase *edge_isect_ls_add(GHash *isect_hash, ScanFillEdge *eed, ScanFillIsect *isect)
|
||||
{
|
||||
ListBase *e_ls;
|
||||
LinkData *isect_link;
|
||||
e_ls = edge_isect_ls_ensure(isect_hash, eed);
|
||||
isect_link = MEM_callocN(sizeof(*isect_link), __func__);
|
||||
isect_link->data = isect;
|
||||
EFLAG_SET(eed, E_ISISECT);
|
||||
BLI_addtail(e_ls, isect_link);
|
||||
return e_ls;
|
||||
}
|
||||
|
||||
static int edge_isect_ls_sort_cb(void *thunk, void *def_a_ptr, void *def_b_ptr)
|
||||
{
|
||||
const float *co = thunk;
|
||||
|
||||
ScanFillIsect *i_a = (ScanFillIsect *)(((LinkData *)def_a_ptr)->data);
|
||||
ScanFillIsect *i_b = (ScanFillIsect *)(((LinkData *)def_b_ptr)->data);
|
||||
const float a = len_squared_v2v2(co, i_a->co);
|
||||
const float b = len_squared_v2v2(co, i_b->co);
|
||||
|
||||
if (a > b) {
|
||||
return -1;
|
||||
}
|
||||
else {
|
||||
return (a < b);
|
||||
}
|
||||
}
|
||||
|
||||
static ScanFillEdge *edge_step(PolyInfo *poly_info,
|
||||
const unsigned short poly_nr,
|
||||
ScanFillVert *v_prev, ScanFillVert *v_curr,
|
||||
ScanFillEdge *e_curr)
|
||||
{
|
||||
ScanFillEdge *eed;
|
||||
|
||||
BLI_assert(ELEM(v_prev, e_curr->v1, e_curr->v2));
|
||||
BLI_assert(ELEM(v_curr, e_curr->v1, e_curr->v2));
|
||||
|
||||
eed = (e_curr->next && e_curr != poly_info[poly_nr].edge_last) ? e_curr->next : poly_info[poly_nr].edge_first;
|
||||
if ((v_curr == eed->v1 || v_curr == eed->v2) == true &&
|
||||
(v_prev == eed->v1 || v_prev == eed->v2) == false)
|
||||
{
|
||||
return eed;
|
||||
}
|
||||
|
||||
eed = (e_curr->prev && e_curr != poly_info[poly_nr].edge_first) ? e_curr->prev : poly_info[poly_nr].edge_last;
|
||||
if ((v_curr == eed->v1 || v_curr == eed->v2) == true &&
|
||||
(v_prev == eed->v1 || v_prev == eed->v2) == false)
|
||||
{
|
||||
return eed;
|
||||
}
|
||||
|
||||
BLI_assert(0);
|
||||
return NULL;
|
||||
}
|
||||
|
||||
static bool scanfill_preprocess_self_isect(
|
||||
ScanFillContext *sf_ctx,
|
||||
PolyInfo *poly_info,
|
||||
const unsigned short poly_nr,
|
||||
ListBase *filledgebase)
|
||||
{
|
||||
PolyInfo *pi = &poly_info[poly_nr];
|
||||
GHash *isect_hash = NULL;
|
||||
ListBase isect_lb = {NULL};
|
||||
|
||||
/* warning, O(n2) check here, should use spatial lookup */
|
||||
{
|
||||
ScanFillEdge *eed;
|
||||
|
||||
for (eed = pi->edge_first;
|
||||
eed;
|
||||
eed = (eed == pi->edge_last) ? NULL : eed->next)
|
||||
{
|
||||
ScanFillEdge *eed_other;
|
||||
|
||||
for (eed_other = eed->next;
|
||||
eed_other;
|
||||
eed_other = (eed_other == pi->edge_last) ? NULL : eed_other->next)
|
||||
{
|
||||
if (!ELEM(eed->v1, eed_other->v1, eed_other->v2) &&
|
||||
!ELEM(eed->v2, eed_other->v1, eed_other->v2) &&
|
||||
(eed != eed_other))
|
||||
{
|
||||
/* check isect */
|
||||
float pt[2];
|
||||
BLI_assert(eed != eed_other);
|
||||
|
||||
if (isect_seg_seg_v2_point(eed->v1->co, eed->v2->co,
|
||||
eed_other->v1->co, eed_other->v2->co,
|
||||
pt) == 1)
|
||||
{
|
||||
ScanFillIsect *isect;
|
||||
|
||||
if (UNLIKELY(isect_hash == NULL)) {
|
||||
isect_hash = BLI_ghash_ptr_new(__func__);
|
||||
}
|
||||
|
||||
isect = MEM_mallocN(sizeof(ScanFillIsect), __func__);
|
||||
|
||||
BLI_addtail(&isect_lb, isect);
|
||||
|
||||
copy_v2_v2(isect->co, pt);
|
||||
isect->co[2] = eed->v1->co[2];
|
||||
isect->v = BLI_scanfill_vert_add(sf_ctx, isect->co);
|
||||
isect->v->poly_nr = eed->v1->poly_nr; /* NOTE: vert may belong to 2 polys now */
|
||||
VFLAG_SET(isect->v, V_ISISECT);
|
||||
edge_isect_ls_add(isect_hash, eed, isect);
|
||||
edge_isect_ls_add(isect_hash, eed_other, isect);
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
if (isect_hash == NULL) {
|
||||
return false;
|
||||
}
|
||||
|
||||
/* now subdiv the edges */
|
||||
{
|
||||
ScanFillEdge *eed;
|
||||
|
||||
for (eed = pi->edge_first;
|
||||
eed;
|
||||
eed = (eed == pi->edge_last) ? NULL : eed->next)
|
||||
{
|
||||
if (eed->user_flag & E_ISISECT) {
|
||||
ListBase *e_ls = BLI_ghash_lookup(isect_hash, eed);
|
||||
|
||||
LinkData *isect_link;
|
||||
|
||||
/* maintain coorect terminating edge */
|
||||
if (pi->edge_last == eed) {
|
||||
pi->edge_last = NULL;
|
||||
}
|
||||
|
||||
if (BLI_listbase_is_single(e_ls) == false) {
|
||||
BLI_sortlist_r(e_ls, eed->v2->co, edge_isect_ls_sort_cb);
|
||||
}
|
||||
|
||||
/* move original edge to filledgebase and add replacement
|
||||
* (which gets subdivided next) */
|
||||
{
|
||||
ScanFillEdge *eed_tmp;
|
||||
eed_tmp = BLI_scanfill_edge_add(sf_ctx, eed->v1, eed->v2);
|
||||
BLI_remlink(&sf_ctx->filledgebase, eed_tmp);
|
||||
BLI_insertlinkafter(&sf_ctx->filledgebase, eed, eed_tmp);
|
||||
BLI_remlink(&sf_ctx->filledgebase, eed);
|
||||
BLI_addtail(filledgebase, eed);
|
||||
if (pi->edge_first == eed) {
|
||||
pi->edge_first = eed_tmp;
|
||||
}
|
||||
eed = eed_tmp;
|
||||
}
|
||||
|
||||
for (isect_link = e_ls->first; isect_link; isect_link = isect_link->next) {
|
||||
ScanFillIsect *isect = isect_link->data;
|
||||
ScanFillEdge *eed_subd;
|
||||
|
||||
eed_subd = BLI_scanfill_edge_add(sf_ctx, isect->v, eed->v2);
|
||||
eed_subd->poly_nr = poly_nr;
|
||||
eed->v2 = isect->v;
|
||||
|
||||
BLI_remlink(&sf_ctx->filledgebase, eed_subd);
|
||||
BLI_insertlinkafter(&sf_ctx->filledgebase, eed, eed_subd);
|
||||
|
||||
/* step to the next edge and continue dividing */
|
||||
eed = eed_subd;
|
||||
}
|
||||
|
||||
BLI_freelistN(e_ls);
|
||||
MEM_freeN(e_ls);
|
||||
|
||||
if (pi->edge_last == NULL) {
|
||||
pi->edge_last = eed;
|
||||
}
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
BLI_freelistN(&isect_lb);
|
||||
BLI_ghash_free(isect_hash, NULL, NULL);
|
||||
|
||||
{
|
||||
ScanFillEdge *e_init;
|
||||
ScanFillEdge *e_curr;
|
||||
ScanFillEdge *e_next;
|
||||
|
||||
ScanFillVert *v_prev;
|
||||
ScanFillVert *v_curr;
|
||||
|
||||
int inside = false;
|
||||
|
||||
/* first vert */
|
||||
#if 0
|
||||
e_init = pi->edge_last;
|
||||
e_curr = e_init;
|
||||
e_next = pi->edge_first;
|
||||
|
||||
v_prev = e_curr->v1;
|
||||
v_curr = e_curr->v2;
|
||||
#else
|
||||
|
||||
/* find outside vertex */
|
||||
{
|
||||
ScanFillEdge *eed;
|
||||
ScanFillEdge *eed_prev;
|
||||
float min_x = FLT_MAX;
|
||||
|
||||
e_curr = pi->edge_last;
|
||||
e_next = pi->edge_first;
|
||||
|
||||
eed_prev = pi->edge_last;
|
||||
for (eed = pi->edge_first;
|
||||
eed;
|
||||
eed = (eed == pi->edge_last) ? NULL : eed->next)
|
||||
{
|
||||
if (eed->v2->co[0] < min_x) {
|
||||
min_x = eed->v2->co[0];
|
||||
e_curr = eed_prev;
|
||||
e_next = eed;
|
||||
|
||||
}
|
||||
eed_prev = eed;
|
||||
}
|
||||
|
||||
e_init = e_curr;
|
||||
v_prev = e_curr->v1;
|
||||
v_curr = e_curr->v2;
|
||||
}
|
||||
#endif
|
||||
|
||||
BLI_assert(e_curr->poly_nr == poly_nr);
|
||||
BLI_assert(pi->edge_last->poly_nr == poly_nr);
|
||||
|
||||
do {
|
||||
ScanFillVert *v_next;
|
||||
|
||||
v_next = (e_next->v1 == v_curr) ? e_next->v2 : e_next->v1;
|
||||
BLI_assert(ELEM(v_curr, e_next->v1, e_next->v2));
|
||||
|
||||
/* track intersections */
|
||||
if (inside) {
|
||||
EFLAG_SET(e_next, E_ISDELETE);
|
||||
}
|
||||
if (v_next->user_flag & V_ISISECT) {
|
||||
inside = !inside;
|
||||
}
|
||||
/* now step... */
|
||||
|
||||
v_prev = v_curr;
|
||||
v_curr = v_next;
|
||||
e_curr = e_next;
|
||||
|
||||
e_next = edge_step(poly_info, poly_nr, v_prev, v_curr, e_curr);
|
||||
|
||||
} while (e_curr != e_init);
|
||||
}
|
||||
|
||||
return true;
|
||||
}
|
||||
|
||||
/**
|
||||
* Call before scanfill to remove self intersections.
|
||||
*
|
||||
* \return false if no changes were made.
|
||||
*/
|
||||
bool BLI_scanfill_calc_self_isect(
|
||||
ScanFillContext *sf_ctx,
|
||||
ListBase *remvertbase,
|
||||
ListBase *remedgebase)
|
||||
{
|
||||
const unsigned int poly_tot = (unsigned int)sf_ctx->poly_nr + 1;
|
||||
unsigned int eed_index = 0;
|
||||
int totvert_new = 0;
|
||||
bool changed = false;
|
||||
|
||||
PolyInfo *poly_info = MEM_callocN(sizeof(*poly_info) * poly_tot, __func__);
|
||||
|
||||
/* get the polygon span */
|
||||
if (sf_ctx->poly_nr == 0) {
|
||||
poly_info->edge_first = sf_ctx->filledgebase.first;
|
||||
poly_info->edge_last = sf_ctx->filledgebase.last;
|
||||
}
|
||||
else {
|
||||
unsigned short poly_nr;
|
||||
ScanFillEdge *eed;
|
||||
|
||||
poly_nr = 0;
|
||||
|
||||
for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next, eed_index++) {
|
||||
|
||||
BLI_assert(eed->poly_nr == eed->v1->poly_nr);
|
||||
BLI_assert(eed->poly_nr == eed->v2->poly_nr);
|
||||
|
||||
if ((poly_info[poly_nr].edge_last != NULL) &&
|
||||
(poly_info[poly_nr].edge_last->poly_nr != eed->poly_nr))
|
||||
{
|
||||
poly_nr++;
|
||||
}
|
||||
|
||||
if (poly_info[poly_nr].edge_first == NULL) {
|
||||
poly_info[poly_nr].edge_first = eed;
|
||||
poly_info[poly_nr].edge_last = eed;
|
||||
}
|
||||
else if (poly_info[poly_nr].edge_last->poly_nr == eed->poly_nr) {
|
||||
poly_info[poly_nr].edge_last = eed;
|
||||
}
|
||||
|
||||
BLI_assert(poly_info[poly_nr].edge_first->poly_nr == poly_info[poly_nr].edge_last->poly_nr);
|
||||
}
|
||||
}
|
||||
|
||||
/* self-intersect each polygon */
|
||||
{
|
||||
unsigned short poly_nr;
|
||||
for (poly_nr = 0; poly_nr < poly_tot; poly_nr++) {
|
||||
changed |= scanfill_preprocess_self_isect(sf_ctx, poly_info, poly_nr, remedgebase);
|
||||
}
|
||||
}
|
||||
|
||||
MEM_freeN(poly_info);
|
||||
|
||||
if (changed == false) {
|
||||
return false;
|
||||
}
|
||||
|
||||
/* move free edges into own list */
|
||||
{
|
||||
ScanFillEdge *eed;
|
||||
ScanFillEdge *eed_next;
|
||||
for (eed = sf_ctx->filledgebase.first; eed; eed = eed_next) {
|
||||
eed_next = eed->next;
|
||||
if (eed->user_flag & E_ISDELETE) {
|
||||
BLI_remlink(&sf_ctx->filledgebase, eed);
|
||||
BLI_addtail(remedgebase, eed);
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
/* move free vertices into own list */
|
||||
{
|
||||
ScanFillEdge *eed;
|
||||
ScanFillVert *eve;
|
||||
ScanFillVert *eve_next;
|
||||
|
||||
for (eve = sf_ctx->fillvertbase.first; eve; eve = eve->next) {
|
||||
eve->user_flag = 0;
|
||||
eve->poly_nr = SF_POLY_UNSET;
|
||||
}
|
||||
for (eed = sf_ctx->filledgebase.first; eed; eed = eed->next) {
|
||||
eed->v1->user_flag = 1;
|
||||
eed->v2->user_flag = 1;
|
||||
eed->poly_nr = SF_POLY_UNSET;
|
||||
}
|
||||
|
||||
for (eve = sf_ctx->fillvertbase.first; eve; eve = eve_next) {
|
||||
eve_next = eve->next;
|
||||
if (eve->user_flag != 1) {
|
||||
BLI_remlink(&sf_ctx->fillvertbase, eve);
|
||||
BLI_addtail(remvertbase, eve);
|
||||
totvert_new--;
|
||||
}
|
||||
else {
|
||||
eve->user_flag = 0;
|
||||
}
|
||||
}
|
||||
}
|
||||
|
||||
/* polygon id's are no longer meaningful,
|
||||
* when removing self intersections we may have created new isolated polys */
|
||||
sf_ctx->poly_nr = SF_POLY_UNSET;
|
||||
|
||||
#if 0
|
||||
BKE_scanfill_view3d_dump(sf_ctx);
|
||||
BKE_scanfill_obj_dump(sf_ctx);
|
||||
#endif
|
||||
|
||||
return changed;
|
||||
}
|
|
@ -69,6 +69,7 @@ void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op)
|
|||
ScanFillFace *sf_tri;
|
||||
SmallHash hash;
|
||||
float normal[3], *normal_pt;
|
||||
const int scanfill_flag = BLI_SCANFILL_CALC_HOLES | BLI_SCANFILL_CALC_POLYS | BLI_SCANFILL_CALC_LOOSE;
|
||||
|
||||
BLI_smallhash_init_ex(&hash, BMO_slot_buffer_count(op->slots_in, "edges"));
|
||||
|
||||
|
@ -104,7 +105,7 @@ void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op)
|
|||
normal_pt = normal;
|
||||
}
|
||||
|
||||
BLI_scanfill_calc_ex(&sf_ctx, BLI_SCANFILL_CALC_HOLES | BLI_SCANFILL_CALC_LOOSE, normal_pt);
|
||||
BLI_scanfill_calc_ex(&sf_ctx, scanfill_flag, normal_pt);
|
||||
|
||||
for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
|
||||
BMFace *f = BM_face_create_quad_tri(bm,
|
||||
|
|
|
@ -220,6 +220,7 @@ enum {
|
|||
|
||||
/* no holes */
|
||||
MASK_LAYERFLAG_FILL_DISCRETE = (1 << 6),
|
||||
MASK_LAYERFLAG_FILL_OVERLAP = (1 << 7),
|
||||
};
|
||||
|
||||
/* masklay_shape->flag */
|
||||
|
|
|
@ -889,6 +889,11 @@ static void rna_def_mask_layer(BlenderRNA *brna)
|
|||
RNA_def_property_boolean_negative_sdna(prop, NULL, "flag", MASK_LAYERFLAG_FILL_DISCRETE);
|
||||
RNA_def_property_ui_text(prop, "Calculate Holes", "Calculate holes when filling overlapping curves");
|
||||
RNA_def_property_update(prop, NC_MASK | NA_EDITED, NULL);
|
||||
|
||||
prop = RNA_def_property(srna, "use_fill_overlap", PROP_BOOLEAN, PROP_NONE);
|
||||
RNA_def_property_boolean_sdna(prop, NULL, "flag", MASK_LAYERFLAG_FILL_OVERLAP);
|
||||
RNA_def_property_ui_text(prop, "Calculate Overlap", "Calculate self intersections and overlap before filling");
|
||||
RNA_def_property_update(prop, NC_MASK | NA_EDITED, NULL);
|
||||
}
|
||||
|
||||
static void rna_def_masklayers(BlenderRNA *brna, PropertyRNA *cprop)
|
||||
|
|
Loading…
Reference in New Issue