diff options
Diffstat (limited to 'source/blender/bmesh/operators/createops.c')
-rw-r--r-- | source/blender/bmesh/operators/createops.c | 1281 |
1 files changed, 1281 insertions, 0 deletions
diff --git a/source/blender/bmesh/operators/createops.c b/source/blender/bmesh/operators/createops.c new file mode 100644 index 00000000000..590fb426811 --- /dev/null +++ b/source/blender/bmesh/operators/createops.c @@ -0,0 +1,1281 @@ +#include "MEM_guardedalloc.h" + +#include "BLI_utildefines.h" + +#include "BLI_memarena.h" +#include "BLI_mempool.h" +#include "BLI_heap.h" +#include "BLI_ghash.h" +#include "BLI_blenlib.h" +#include "BLI_math.h" +#include "BLI_array.h" +#include "BLI_smallhash.h" +#include "BLI_rand.h" + +#include "bmesh.h" +#include "bmesh_operators_private.h" + +#define EDGE_MARK 1 +#define EDGE_VIS 2 + +#define FACE_NEW 1 + +#define ELE_NEW 1 +#define ELE_OUT 2 +#define ELE_ORIG 4 + +#define FACE_IGNORE 16 + +typedef struct EPathNode { + struct EPathNode *next, *prev; + BMVert *v; + BMEdge *e; + BMEdge *cure; +} EPathNode; + +typedef struct EPath { + ListBase nodes; + float weight; + int group; +} EPath; + +typedef struct PathBase { + BLI_mempool *nodepool, *pathpool; +} PathBase; + +typedef struct EdgeData { + int tag; + int ftag; + + struct { + struct BMEdge *next, *prev; + } dlink1; + struct { + struct BMEdge *next, *prev; + } dlink2; +} EdgeData; + +typedef struct VertData { + BMEdge *e; + float no[3], offco[3], sco[3]; /*offco is vertex coordinate slightly offset randomly*/ + int tag; +} VertData; + +static int count_edge_faces(BMesh *bm, BMEdge *e); + +/**** rotation system code ***/ + +#define rs_get_edge_link(e, v, ed) ((v) == ((BMEdge*)(e))->v1 ? (Link*)&(((EdgeData*)(ed))->dlink1) : (Link*)&(((EdgeData*)(ed))->dlink2)) + +static int rotsys_append_edge(struct BMEdge *e, struct BMVert *v, + EdgeData *edata, VertData *vdata) +{ + EdgeData *ed = &edata[BM_GetIndex(e)]; + VertData *vd = &vdata[BM_GetIndex(v)]; + + if (!vd->e) { + Link *e1 = (Link*)rs_get_edge_link(e, v, ed); + + vd->e = e; + e1->next = e1->prev = (Link*)e; + } else { + Link *e1, *e2, *e3; + EdgeData *ved = &edata[BM_GetIndex(vd->e)]; + + e1 = rs_get_edge_link(e, v, ed); + e2 = rs_get_edge_link(vd->e, v, ved); + e3 = e2->prev ? rs_get_edge_link(e2->prev, v, &edata[BM_GetIndex(e2->prev)]) : NULL; + + e1->next = (Link*)vd->e; + e1->prev = e2->prev; + + e2->prev = (Link*)e; + if (e3) + e3->next = (Link*)e; + } + + return 1; +} + +static void UNUSED_FUNCTION(rotsys_remove_edge)(struct BMEdge *e, struct BMVert *v, + EdgeData *edata, VertData *vdata) +{ + EdgeData *ed = edata + BM_GetIndex(e); + VertData *vd = vdata + BM_GetIndex(v); + Link *e1, *e2; + + e1 = rs_get_edge_link(e, v, ed); + if (e1->prev) { + e2 = rs_get_edge_link(e1->prev, v, ed); + e2->next = e1->next; + } + + if (e1->next) { + e2 = rs_get_edge_link(e1->next, v, ed); + e2->prev = e1->prev; + } + + if (vd->e == e) + vd->e = (e != (BMEdge *)e1->next) ? (BMEdge*)e1->next : NULL; + + e1->next = e1->prev = NULL; +} + +static struct BMEdge *rotsys_nextedge(struct BMEdge *e, struct BMVert *v, + EdgeData *edata, VertData *UNUSED(vdata)) +{ + if (v == e->v1) + return edata[BM_GetIndex(e)].dlink1.next; + if (v == e->v2) + return edata[BM_GetIndex(e)].dlink2.next; + return NULL; +} + +static BMEdge *rotsys_prevedge(BMEdge *e, BMVert *v, + EdgeData *edata, VertData *UNUSED(vdata)) +{ + if (v == e->v1) + return edata[BM_GetIndex(e)].dlink1.prev; + if (v == e->v2) + return edata[BM_GetIndex(e)].dlink2.prev; + return NULL; +} + +static void rotsys_reverse(struct BMEdge *UNUSED(e), struct BMVert *v, EdgeData *edata, VertData *vdata) +{ + BMEdge **edges = NULL; + BMEdge *e2; + BLI_array_staticdeclare(edges, 256); + int i, totedge; + + e2 = vdata[BM_GetIndex(v)].e; + do { + BLI_array_append(edges, e2); + e2 = rotsys_nextedge(e2, v, edata, vdata); + } while (e2 != vdata[BM_GetIndex(v)].e); + + totedge = BLI_array_count(edges); + for (i=0; i<totedge/2; i++) { + SWAP(BMEdge*, edges[i], edges[totedge-1-i]); + } + + vdata[BM_GetIndex(v)].e = NULL; + for (i=0; i<totedge; i++) { + rotsys_append_edge(edges[i], v, edata, vdata); + } + + BLI_array_free(edges); +} + +static int UNUSED_FUNCTION(rotsys_count)(struct BMVert *v, EdgeData *edata, VertData *vdata) +{ + BMEdge *e = vdata[BM_GetIndex(v)].e; + int i=0; + + if (!e) + return 0; + + do { + if (!e) + return 0; + e = rotsys_nextedge(e, v, edata, vdata); + + if (i >= (1<<20)) { + printf("bmesh error: infinite loop in disk cycle!\n"); + return 0; + } + + i += 1; + } while (e != vdata[BM_GetIndex(v)].e); + + return i; +} + +static int UNUSED_FUNCTION(rotsys_fill_faces)(BMesh *bm, EdgeData *edata, VertData *vdata) +{ + BMIter iter; + BMEdge *e, **edges = NULL; + BLI_array_declare(edges); + BMVert *v, **verts = NULL; + BMFace *f; + BLI_array_declare(verts); + SmallHash visithash, *hash=&visithash; + int i; + + BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) { + BMEdge *e2, *starte; + BMVert *startv; + int rad, ok; + + rad = count_edge_faces(bm, e); + + if (rad < 2) + starte = e; + else + continue; + + /*do two passes, going forward then backward*/ + for (i=0; i<2; i++) { + BLI_smallhash_init(hash); + + BLI_array_empty(verts); + BLI_array_empty(edges); + + startv = v = starte->v1; + e2 = starte; + ok = 1; + if (!v || !e2) + continue; + + do { + if (BLI_smallhash_haskey(hash, (intptr_t)e2) + || BLI_smallhash_haskey(hash, (intptr_t)v)) { + ok = 0; + break; + } + + BLI_array_append(verts, v); + BLI_array_append(edges, e2); + + BLI_smallhash_insert(hash, (intptr_t)e2, NULL); + + v = BM_OtherEdgeVert(e2, v); + e2 = i ? rotsys_prevedge(e2, v, edata, vdata) : rotsys_nextedge(e2, v, edata, vdata); + } while (e2 != starte && v != startv); + + BLI_smallhash_release(hash); + + if (!ok || BLI_array_count(edges) < 3) + continue; + + f = BM_Make_Ngon(bm, verts[0], verts[1], edges, BLI_array_count(edges), 1); + if (!f) + continue; + } + } + + return 0; +} + +static void rotsys_make_consistent(BMesh *bm, EdgeData *edata, VertData *vdata) +{ + BMIter iter; + BMEdge *e; + BMVert *v, **stack=NULL; + BLI_array_declare(stack); + int i; + + for (i=0; i<bm->totvert; i++) { + vdata[i].tag = 0; + } + + while (1) { + VertData *vd; + BMVert *startv = NULL; + float dis; + + v = BMIter_New(&iter, bm, BM_VERTS_OF_MESH, NULL); + for (i=0; i<bm->totvert; i++, BMIter_Step(&iter)) { + vd = vdata + BM_GetIndex(v); + + if (vd->tag) + continue; + + if (!startv || dot_v3v3(vd->offco, vd->offco) > dis) { + dis = dot_v3v3(vd->offco, vd->offco); + startv = v; + } + } + + if (!startv) + break; + + vd = vdata + BM_GetIndex(startv); + + BLI_array_empty(stack); + BLI_array_append(stack, startv); + + vd->tag = 1; + + while (BLI_array_count(stack)) { + v = BLI_array_pop(stack); + vd = vdata + BM_GetIndex(v); + + if (!vd->e) + continue; + + e = vd->e; + do { + BMVert *v2 = BM_OtherEdgeVert(e, v); + VertData *vd2 = vdata + BM_GetIndex(v2); + + if (dot_v3v3(vd->no, vd2->no) < 0.0f+FLT_EPSILON*2) { + rotsys_reverse(e, v2, edata, vdata); + mul_v3_fl(vd2->no, -1.0f); + } + + if (!vd2->tag) { + BLI_array_append(stack, v2); + vd2->tag = 1; + } + + e = rotsys_nextedge(e, v, edata, vdata); + } while (e != vd->e); + } + } + + BLI_array_free(stack); +} + +static void init_rotsys(BMesh *bm, EdgeData *edata, VertData *vdata) +{ + BMIter iter; + BMEdge *e; + BMEdge **edges = NULL; + BLI_array_staticdeclare(edges, 256); + BMVert *v; + /*BMVert **verts = NULL; */ + /*BLI_array_staticdeclare(verts, 256);*/ /*UNUSED*/ + int i; + + #define SIGN(n) ((n)<0.0f) + + BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) { + BMIter eiter; + float no[3], cent[3]; + int j, k=0, totedge=0; + + if (BM_GetIndex(v) == -1) + continue; + + BLI_array_empty(edges); + + BM_ITER(e, &eiter, bm, BM_EDGES_OF_VERT, v) { + if (BMO_TestFlag(bm, e, EDGE_MARK)) { + BLI_array_append(edges, e); + totedge++; + } + } + + copy_v3_v3(cent, v->co); + + zero_v3(no); + for (i=0; i<totedge; i++) { + BMEdge *e1, *e2; + float cno[3], vec1[3], vec2[3]; + + e1 = edges[i]; + e2 = edges[(i+1)%totedge]; + + sub_v3_v3v3(vec1, (BM_OtherEdgeVert(e1, v))->co, v->co); + sub_v3_v3v3(vec2, (BM_OtherEdgeVert(e2, v))->co, v->co); + + cross_v3_v3v3(cno, vec1, vec2); + normalize_v3(cno); + + if (i && dot_v3v3(cno, no) < 0.0f+FLT_EPSILON*10) + mul_v3_fl(cno, -1.0f); + + add_v3_v3(no, cno); + normalize_v3(no); + } + + /*generate plane-flattened coordinates*/ + for (i=0; i<totedge; i++) { + BMEdge *e1; + BMVert *v2; + float cvec[3], vec1[3]; + + e1 = edges[i]; + v2 = BM_OtherEdgeVert(e1, v); + + sub_v3_v3v3(vec1, v2->co, v->co); + + cross_v3_v3v3(cvec, vec1, no); + cross_v3_v3v3(vec1, cvec, no); + normalize_v3(vec1); + + mul_v3_fl(vec1, len_v3v3(v2->co, v->co)); + add_v3_v3(vec1, v->co); + + copy_v3_v3(vdata[BM_GetIndex(v2)].sco, vec1); + } + + BLI_srandom(0); + + /*first, ensure no 0 or 180 angles between adjacent + (and that adjacent's adjacent) edges*/ + for (i=0, k=0; i<totedge; i++) { + BMEdge *e1, *e2, *e3=NULL; + BMVert *v1, *v2, *v3; + VertData *vd1, *vd2, *vd3; + float vec1[3], vec2[3], vec3[3], size; + int s1, s2, s3; + + if (totedge < 3) + continue; + + e1 = edges[(i+totedge-1) % totedge]; + e2 = edges[i]; + e3 = edges[(i+1) % totedge]; + + v1 = BM_OtherEdgeVert(e1, v); v2 = BM_OtherEdgeVert(e2, v); v3 = BM_OtherEdgeVert(e3, v); + vd1 = vdata+BM_GetIndex(v1); vd2 = vdata+BM_GetIndex(v2); vd3 = vdata+BM_GetIndex(v3); + + sub_v3_v3v3(vec1, vd1->sco, cent); + sub_v3_v3v3(vec2, vd2->sco, cent); + sub_v3_v3v3(vec3, vd3->sco, cent); + + size = (len_v3(vec1) + len_v3(vec3)) * 0.01f; + normalize_v3(vec1); normalize_v3(vec2); normalize_v3(vec3); + + #ifdef STRAIGHT + #undef STRAIGHT + #endif + #define STRAIGHT(vec11, vec22) (fabsf(dot_v3v3((vec11), (vec22))) > 1.0f - ((float)FLT_EPSILON*1000.0f)) + + s1 = STRAIGHT(vec1, vec2); s2 = STRAIGHT(vec2, vec3); s3 = STRAIGHT(vec1, vec3); + + if (s1 || s2 || s3) { + copy_v3_v3(cent, v->co); + + for (j=0; j<3; j++) { + float fac = (BLI_frand()-0.5f)*size; + cent[j] += fac; + } + + if (k < 2000) { + i = 0; + k++; + continue; + } else { + k++; + continue; + } + + } + } + + copy_v3_v3(vdata[BM_GetIndex(v)].offco, cent); + //copy_v3_v3(v->co, cent); + + /*now, sort edges so the triangle fan of all edges + has a consistent normal. this is the same as + sorting by polar coordinates along a group normal*/ + for (j=0; j<totedge; j++) { + for (i=0; i<totedge; i++) { + BMEdge *e1, *e2, *e3=NULL; + BMVert *v1, *v2, *v3; + VertData *vd1, *vd2, *vd3; + float vec1[3], vec2[3], vec3[3], n1[3], n2[3], n3[3]; + int s1, s2, s3; + + e1 = edges[(i+totedge-1) % totedge]; + e2 = edges[i]; + e3 = edges[(i+1) % totedge]; + + v1 = BM_OtherEdgeVert(e1, v); v2 = BM_OtherEdgeVert(e2, v); v3 = BM_OtherEdgeVert(e3, v); + vd1 = vdata+BM_GetIndex(v1); vd2 = vdata+BM_GetIndex(v2); vd3 = vdata+BM_GetIndex(v3); + + sub_v3_v3v3(vec1, vd1->sco, cent); + sub_v3_v3v3(vec2, vd2->sco, cent); + sub_v3_v3v3(vec3, vd3->sco, cent); + + cross_v3_v3v3(n1, vec1, vec2); + cross_v3_v3v3(n2, vec2, vec3); + cross_v3_v3v3(n3, vec1, vec3); + + /* Other way to determine if two vectors approach are (nearly) parallel: the + cross product of the two vectors will approach zero */ + s1 = (dot_v3v3(n1, n1) < (0.0f + FLT_EPSILON*10)); + s2 = (dot_v3v3(n2, n2) < (0.0f + FLT_EPSILON*10)); + s3 = (totedge < 3) ? 0 : (dot_v3v3(n3, n3) < (0.0f + FLT_EPSILON*10)); + + normalize_v3(n1); normalize_v3(n2); normalize_v3(n3); + + if (s1 || s2 || s3) { + fprintf(stderr, "%s: s1: %d, s2: %d, s3: %dx (bmesh internal error)\n", __func__, s1, s2, s3); + } + if (dot_v3v3(n1, n2) < 0.0f) { + if (dot_v3v3(n1, n3) >= 0.0f + FLT_EPSILON*10) { + SWAP(BMEdge*, edges[i], edges[(i+1)%totedge]); + } else { + SWAP(BMEdge*, edges[(i+totedge-1)%totedge], edges[(i+1)%totedge]) + SWAP(BMEdge*, edges[i], edges[(i+1)%totedge]) + } + } + } + } + + #undef STRAIGHT + + zero_v3(no); + + /*yay, edges is sorted*/ + for (i=0; i<totedge; i++) { + BMEdge *e1 = edges[i], *e2 = edges[(i+1)%totedge]; + float eno[3]; + + normal_tri_v3(eno, BM_OtherEdgeVert(e1, v)->co, v->co, BM_OtherEdgeVert(e2, v)->co); + add_v3_v3(no, eno); + + rotsys_append_edge(edges[i], v, edata, vdata); + } + + normalize_v3(no); + copy_v3_v3(vdata[BM_GetIndex(v)].no, no); + } + + /*now, make sure rotation system is topologically consistent + (e.g. vert normals consistently point either inside or outside)*/ + rotsys_make_consistent(bm, edata, vdata); + + //rotsys_fill_faces(bm, edata, vdata); + +#if 0 + /*create visualizing geometry*/ + BMVert *lastv; + BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) { + BMVert *v2; + BMFace *f; + int totedge = BM_Vert_EdgeCount(v); + + if (BM_GetIndex(v) == -1) + continue; + + //cv = BM_Make_Vert(bm, cent, v); + //BM_SetIndex(cv, -1); /* set_dirty! */ + i = 0; + e = vdata[BM_GetIndex(v)].e; + lastv = NULL; + do { + BMEdge *e2; + BMVert *v2; + float f = ((float)i / (float)totedge)*0.35 + 0.05; + float co[3]; + + if (!e) + break; + + if (!BM_OtherEdgeVert(e, v)) + continue; + + sub_v3_v3v3(co, (BM_OtherEdgeVert(e, v))->co, vdata[BM_GetIndex(v)].offco); + mul_v3_fl(co, f); + add_v3_v3(co, vdata[BM_GetIndex(v)].offco); + + v2 = BM_Make_Vert(bm, co, NULL); + BM_SetIndex(v2, -1); /* set_dirty! */ + //BM_Make_Edge(bm, cv, v2, NULL, 0); + + BM_Select(bm, v2, 1); + if (lastv) { + e2 = + BM_Make_Edge(bm, lastv, v2, NULL, 0); + BM_Select(bm, e2, 1); + } + + lastv = v2; + + e = rotsys_nextedge(e, v, edata, vdata); + i++; + } while (e != vdata[BM_GetIndex(v)].e); + } +#endif + + BLI_array_free(edges); +} + +static PathBase *edge_pathbase_new(void) +{ + PathBase *pb = MEM_callocN(sizeof(PathBase), "PathBase"); + + pb->nodepool = BLI_mempool_create(sizeof(EPathNode), 1, 512, TRUE, FALSE); + pb->pathpool = BLI_mempool_create(sizeof(EPath), 1, 512, TRUE, FALSE); + + return pb; +} + +static void edge_pathbase_free(PathBase *pathbase) +{ + BLI_mempool_destroy(pathbase->nodepool); + BLI_mempool_destroy(pathbase->pathpool); + MEM_freeN(pathbase); +} + +static EPath *edge_copy_add_path(PathBase *pb, EPath *path, BMVert *appendv, BMEdge *e) +{ + EPath *path2; + EPathNode *node, *node2; + + path2 = BLI_mempool_alloc(pb->pathpool); + path2->nodes.first = path2->nodes.last = NULL; + path2->weight = 0.0f; + path2->group = path->group; + + for (node=path->nodes.first; node; node=node->next) { + node2 = BLI_mempool_alloc(pb->nodepool); + *node2 = *node; + BLI_addtail(&path2->nodes, node2); + } + + node2 = BLI_mempool_alloc(pb->nodepool); + node2->v = appendv; + node2->e = e; + node2->cure = NULL; + + BLI_addtail(&path2->nodes, node2); + + return path2; +} + +static EPath *edge_path_new(PathBase *pb, BMVert *start, BMEdge *starte) +{ + EPath *path; + EPathNode *node; + + path = BLI_mempool_alloc(pb->pathpool); + node = BLI_mempool_alloc(pb->nodepool); + + path->nodes.first = path->nodes.last = NULL; + + node->v = start; + node->e = starte; + node->cure = NULL; + + BLI_addtail(&path->nodes, node); + path->weight = 0.0f; + + return path; +} + +static float edge_weight_path(EPath *path, EdgeData *edata, VertData *UNUSED(vdata)) +{ + EPathNode *node, *first=path->nodes.first; + float w = 0.0; + + for (node=path->nodes.first; node; node=node->next) { + if (node->e && node != path->nodes.first) { + w += edata[BM_GetIndex(node->e)].ftag; + if (node->prev) { + /*BMESH_TODO*/ + (void)first; + //w += len_v3v3(node->v->co, first->e->v1->co)*0.0001f; + //w += len_v3v3(node->v->co, first->e->v2->co)*0.0001f; + } + } + + w += 1.0f; + } + + return w; +} + + +static void edge_free_path(PathBase *pathbase, EPath *path) +{ + EPathNode *node, *next; + + for (node=path->nodes.first; node; node=next) { + next = node->next; + BLI_mempool_free(pathbase->nodepool, node); + } + + BLI_mempool_free(pathbase->pathpool, path); +} + +static EPath *edge_find_shortest_path(BMesh *bm, BMOperator *op, BMEdge *edge, EdgeData *edata, + VertData *vdata, PathBase *pathbase, int group) +{ + BMEdge *e; + GHash *gh = BLI_ghash_new(BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "createops find shortest path"); + BMVert *v1, *v2; + BMVert **verts = NULL; + BLI_array_staticdeclare(verts, 1024); + Heap *heap = BLI_heap_new(); + EPath *path = NULL, *path2; + BMVert *startv; + BMVert *endv; + EPathNode *node; + int i, use_restrict = BMO_Get_Int(op, "use_restrict"); + + startv = edata[BM_GetIndex(edge)].ftag ? edge->v2 : edge->v1; + endv = edata[BM_GetIndex(edge)].ftag ? edge->v1 : edge->v2; + + path = edge_path_new(pathbase, startv, edge); + BLI_ghash_insert(gh, startv, NULL); + BLI_heap_insert(heap, path->weight, path); + path->group = group; + + while (BLI_heap_size(heap)) { + VertData *vd; + EPathNode *last; + BMFace *f = NULL; + + path = BLI_heap_popmin(heap); + last = path->nodes.last; + v1 = last->v; + + if (v1 == endv) { + /*make sure this path loop doesn't already exist*/ + i = 0; + BLI_array_empty(verts); + for (i=0, node = path->nodes.first; node; node=node->next, i++) { + BLI_array_growone(verts); + verts[i] = node->v; + } + + if (BM_Face_Exists(bm, verts, i, &f)) { + if (!BMO_TestFlag(bm, f, FACE_IGNORE)) { + BLI_ghash_remove(gh, endv, NULL, NULL); + continue; + } + } + break; + } + + vd = vdata + BM_GetIndex(v1); + if (!vd->e) + continue; + + v2 = NULL; + while (1) { + if (!last->cure) { + last->cure = e = vdata[BM_GetIndex(last->v)].e; + } else { + last->cure = e = rotsys_nextedge(last->cure, last->v, edata, vdata); + if (last->cure == vdata[BM_GetIndex(last->v)].e) { + v2 = NULL; + break; + } + } + + if (e == edge || !BMO_TestFlag(bm, e, EDGE_MARK)) { + continue; + } + + v2 = BM_OtherEdgeVert(e, last->v); + + if (BLI_ghash_haskey(gh, v2)) { + v2 = NULL; + continue; + } + + if (use_restrict && BMO_InMap(bm, op, "restrict", e)) { + int group = BMO_Get_MapInt(bm, op, "restrict", e); + + if (!(group & path->group)) { + v2 = NULL; + continue; + } + } + + break; + } + + if (!v2) { + if (path) { + edge_free_path(pathbase, path); + path = NULL; + } + continue; + } + + /*add path back into heap*/ + BLI_heap_insert(heap, path->weight, path); + + /*put v2 in gh map*/ + BLI_ghash_insert(gh, v2, NULL); + + path2 = edge_copy_add_path(pathbase, path, v2, e); + path2->weight = edge_weight_path(path2, edata, vdata); + + BLI_heap_insert(heap, path2->weight, path2); + } + + if (path && ((EPathNode*)path->nodes.last)->v != endv) { + edge_free_path(pathbase, path); + path = NULL; + } + + BLI_array_free(verts); + BLI_heap_free(heap, NULL); + BLI_ghash_free(gh, NULL, NULL); + + return path; +} + +static int count_edge_faces(BMesh *bm, BMEdge *e) +{ + int i=0; + BMLoop *l = e->l; + + if (!l) + return 0; + + do { + if (!BMO_TestFlag(bm, l->f, FACE_IGNORE)) + i++; + + l = l->radial_next; + } while (l != e->l); + + return i; +} + +void bmesh_edgenet_fill_exec(BMesh *bm, BMOperator *op) +{ + BMIter iter; + BMOIter siter; + BMFace *f; + BMEdge *e, *edge; + BMVert **verts = NULL; + BLI_array_declare(verts); + EPath *path; + EPathNode *node; + EdgeData *edata; + VertData *vdata; + BMEdge **edges = NULL; + PathBase *pathbase = edge_pathbase_new(); + BLI_array_declare(edges); + int use_restrict = BMO_Get_Int(op, "use_restrict"); + int i, j, group = 0; + unsigned int winding[2]; /* accumulte winding directions for each edge which has a face */ + + if (!bm->totvert || !bm->totedge) + return; + + edata = MEM_callocN(sizeof(EdgeData)*bm->totedge, "EdgeData"); + vdata = MEM_callocN(sizeof(VertData)*bm->totvert, "VertData"); + + BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE); + BMO_Flag_Buffer(bm, op, "excludefaces", FACE_IGNORE, BM_FACE); + + BM_ElemIndex_Ensure(bm, BM_VERT); + + BM_ITER(f, &iter, bm, BM_FACES_OF_MESH, NULL) { + BMO_SetFlag(bm, f, ELE_ORIG); + } + + i = 0; + BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) { + BM_SetIndex(e, i); /* set_inline */ + + if (!BMO_TestFlag(bm, e, EDGE_MARK)) { + edata[i].tag = 2; + } + + i++; + } + bm->elem_index_dirty &= ~BM_EDGE; + + init_rotsys(bm, edata, vdata); + + while (1) { + edge = NULL; + group = 0; + + BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) { + /*if restrict is on, only start on faces in the restrict map*/ + if (use_restrict && !BMO_InMap(bm, op, "restrict", e)) + continue; + + if (edata[BM_GetIndex(e)].tag < 2) { + edge = e; + + if (use_restrict) { + int i=0, j=0, gi=0; + + group = BMO_Get_MapInt(bm, op, "restrict", e); + + for (i=0; i<30; i++) { + if (group & (1<<i)) { + j++; + gi = i; + + if (j-1 == edata[BM_GetIndex(e)].tag) + break; + } + } + + group = 1<<gi; + } + + break; + } + } + + if (!edge) + break; + + edata[BM_GetIndex(edge)].tag += 1; + + path = edge_find_shortest_path(bm, op, edge, edata, vdata, pathbase, group); + if (!path) + continue; + + winding[0]= winding[1]= 0; + + BLI_array_empty(edges); + BLI_array_empty(verts); + i = 0; + for (node=path->nodes.first; node; node=node->next) { + if (!node->next) + continue; + + e = BM_Edge_Exist(node->v, node->next->v); + + /*this should never happen*/ + if (!e) + break; + + /* check on the winding */ + if (e->l) { + BMVert *test_v1, *test_v2; + /* we want to use the reverse winding to the existing order */ + BM_Edge_OrderedVerts(edge, &test_v2, &test_v1); + + /* edges vote on which winding wins out */ + winding[(test_v1 == node->v)]++; + } + + edata[BM_GetIndex(e)].ftag++; + BLI_array_growone(edges); + edges[i++] = e; + + BLI_array_append(verts, node->v); + } + + BLI_array_growone(edges); + edges[i++] = edge; + edata[BM_GetIndex(edge)].ftag++; + + for (j=0; j<i; j++) { + if (count_edge_faces(bm, edges[j]) >= 2) { + edge_free_path(pathbase, path); + break; + } + } + + if (j != i) + continue; + + if (i) { + BMVert *v1, *v2; + + /* to define the winding order must select first edge, + * otherwise we could leave this as-is */ + edge= edges[0]; + + /* if these are even it doesnt really matter what to do, + * with consistent geometry one will be zero, the choice is clear */ + if (winding[0] > winding[1]) { + v1= verts[0]; + v2= verts[1]; + } + else { + v1= verts[1]; + v2= verts[0]; + } + + f = BM_Make_Ngon(bm, v1, v2, edges, i, 1); + if (f && !BMO_TestFlag(bm, f, ELE_ORIG)) { + BMO_SetFlag(bm, f, FACE_NEW); + } + + if (use_restrict) + BMO_Insert_MapInt(bm, op, "faceout_groupmap", f, path->group); + } + + edge_free_path(pathbase, path); + } + + BMO_Flag_To_Slot(bm, op, "faceout", FACE_NEW, BM_FACE); + + BLI_array_free(edges); + BLI_array_free(verts); + edge_pathbase_free(pathbase); + MEM_freeN(edata); + MEM_freeN(vdata); +} + +static BMEdge *edge_next(BMesh *bm, BMEdge *e) +{ + BMIter iter; + BMEdge *e2; + int i; + + for (i=0; i<2; i++) { + BM_ITER(e2, &iter, bm, BM_EDGES_OF_VERT, i?e->v2:e->v1) { + if (BMO_TestFlag(bm, e2, EDGE_MARK) + && !BMO_TestFlag(bm, e2, EDGE_VIS) && e2 != e) + { + return e2; + } + } + } + + return NULL; +} + +void bmesh_edgenet_prepare(BMesh *bm, BMOperator *op) +{ + BMOIter siter; + BMEdge *e; + BMEdge **edges1 = NULL, **edges2 = NULL, **edges; + BLI_array_declare(edges1); + BLI_array_declare(edges2); + BLI_array_declare(edges); + int ok = 1; + int i, count; + + BMO_Flag_Buffer(bm, op, "edges", EDGE_MARK, BM_EDGE); + + /*validate that each edge has at most one other tagged edge in the + disk cycle around each of it's vertices*/ + BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) { + for (i=0; i<2; i++) { + count = BMO_Vert_CountEdgeFlags(bm, i?e->v2:e->v1, EDGE_MARK); + if (count > 2) { + ok = 0; + break; + } + } + + if (!ok) break; + } + + /*we don't have valid edge layouts, return*/ + if (!ok) + return; + + + /*find connected loops within the input edges*/ + count = 0; + while (1) { + BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) { + if (!BMO_TestFlag(bm, e, EDGE_VIS)) { + if (BMO_Vert_CountEdgeFlags(bm, e->v1, EDGE_MARK)==1) + break; + if (BMO_Vert_CountEdgeFlags(bm, e->v2, EDGE_MARK)==1) + break; + } + } + + if (!e) break; + + if (!count) + edges = edges1; + else if (count==1) + edges = edges2; + else break; + + i = 0; + while (e) { + BMO_SetFlag(bm, e, EDGE_VIS); + BLI_array_growone(edges); + edges[i] = e; + + e = edge_next(bm, e); + i++; + } + + if (!count) { + edges1 = edges; + BLI_array_set_length(edges1, BLI_array_count(edges)); + } else { + edges2 = edges; + BLI_array_set_length(edges2, BLI_array_count(edges)); + } + + BLI_array_empty(edges); + count++; + } + + if (edges1 && BLI_array_count(edges1) > 2 && BM_Edge_Share_Vert(edges1[0], edges1[BLI_array_count(edges1)-1])) { + if (edges2 && BLI_array_count(edges2) > 2 && BM_Edge_Share_Vert(edges2[0], edges2[BLI_array_count(edges2)-1])) { + BLI_array_free(edges1); + BLI_array_free(edges2); + return; + } else { + edges1 = edges2; + edges2 = NULL; + } + } + + if (edges2 && BLI_array_count(edges2) > 2 && BM_Edge_Share_Vert(edges2[0], edges2[BLI_array_count(edges2)-1])) { + edges2 = NULL; + } + + /*two unconnected loops, connect them*/ + if (edges1 && edges2) { + BMVert *v1, *v2, *v3, *v4; + + if (BLI_array_count(edges1)==1) { + v1 = edges1[0]->v1; + v2 = edges1[0]->v2; + } else { + if (BM_Vert_In_Edge(edges1[1], edges1[0]->v1)) + v1 = edges1[0]->v2; + else v1 = edges1[0]->v1; + + i = BLI_array_count(edges1)-1; + if (BM_Vert_In_Edge(edges1[i-1], edges1[i]->v1)) + v2 = edges1[i]->v2; + else v2 = edges1[i]->v1; + } + + if (BLI_array_count(edges2)==1) { + v3 = edges2[0]->v1; + v4 = edges2[0]->v2; + } else { + if (BM_Vert_In_Edge(edges2[1], edges2[0]->v1)) + v3 = edges2[0]->v2; + else v3 = edges2[0]->v1; + + i = BLI_array_count(edges2)-1; + if (BM_Vert_In_Edge(edges2[i-1], edges2[i]->v1)) + v4 = edges2[i]->v2; + else v4 = edges2[i]->v1; + } + + /* avoid sqrt for comparison */ + if (len_squared_v3v3(v1->co, v3->co) + len_squared_v3v3(v2->co, v4->co) > + len_squared_v3v3(v1->co, v4->co) + len_squared_v3v3(v2->co, v3->co)) + { + BMVert *v; + v = v3; + v3 = v4; + v4 = v; + } + + e = BM_Make_Edge(bm, v1, v3, NULL, 1); + BMO_SetFlag(bm, e, ELE_NEW); + e = BM_Make_Edge(bm, v2, v4, NULL, 1); + BMO_SetFlag(bm, e, ELE_NEW); + } else if (edges1) { + BMVert *v1, *v2; + + if (BLI_array_count(edges1) > 1) { + if (BM_Vert_In_Edge(edges1[1], edges1[0]->v1)) + v1 = edges1[0]->v2; + else v1 = edges1[0]->v1; + + i = BLI_array_count(edges1)-1; + if (BM_Vert_In_Edge(edges1[i-1], edges1[i]->v1)) + v2 = edges1[i]->v2; + else v2 = edges1[i]->v1; + + e = BM_Make_Edge(bm, v1, v2, NULL, 1); + BMO_SetFlag(bm, e, ELE_NEW); + } + } + + BMO_Flag_To_Slot(bm, op, "edgeout", ELE_NEW, BM_EDGE); + + BLI_array_free(edges1); + BLI_array_free(edges2); +} + +/*this is essentially new fkey*/ +void bmesh_contextual_create_exec(BMesh *bm, BMOperator *op) +{ + BMOperator op2; + BMOIter oiter; + BMIter iter; + BMHeader *h; + BMVert *v, *verts[4]; + BMEdge *e; + BMFace *f; + int totv=0, tote=0, totf=0, amount; + + /*count number of each element type we were passed*/ + BMO_ITER(h, &oiter, bm, op, "geom", BM_VERT|BM_EDGE|BM_FACE) { + switch (h->htype) { + case BM_VERT: totv++; break; + case BM_EDGE: tote++; break; + case BM_FACE: totf++; break; + } + + BMO_SetFlag(bm, h, ELE_NEW); + } + + /*call edgenet create*/ + /* call edgenet prepare op so additional face creation cases work*/ + BMO_InitOpf(bm, &op2, "edgenet_prepare edges=%fe", ELE_NEW); + BMO_Exec_Op(bm, &op2); + BMO_Flag_Buffer(bm, &op2, "edgeout", ELE_NEW, BM_EDGE); + BMO_Finish_Op(bm, &op2); + + BMO_InitOpf(bm, &op2, "edgenet_fill edges=%fe", ELE_NEW); + BMO_Exec_Op(bm, &op2); + + /*return if edge net create did something*/ + if (BMO_CountSlotBuf(bm, &op2, "faceout")) { + BMO_CopySlot(&op2, op, "faceout", "faceout"); + BMO_Finish_Op(bm, &op2); + return; + } + + BMO_Finish_Op(bm, &op2); + + /*now call dissolve faces*/ + BMO_InitOpf(bm, &op2, "dissolvefaces faces=%ff", ELE_NEW); + BMO_Exec_Op(bm, &op2); + + /*if we dissolved anything, then return.*/ + if (BMO_CountSlotBuf(bm, &op2, "regionout")) { + BMO_CopySlot(&op2, op, "regionout", "faceout"); + BMO_Finish_Op(bm, &op2); + return; + } + + BMO_Finish_Op(bm, &op2); + + /*now, count how many verts we have*/ + amount = 0; + BM_ITER(v, &iter, bm, BM_VERTS_OF_MESH, NULL) { + if (BMO_TestFlag(bm, v, ELE_NEW)) { + verts[amount] = v; + amount++; + + if (amount > 4) break; + } + } + + if (amount == 2) { + /*create edge*/ + e = BM_Make_Edge(bm, verts[0], verts[1], NULL, 1); + BMO_SetFlag(bm, e, ELE_OUT); + } else if (amount == 3) { + /*create triangle*/ + BM_Make_QuadTri(bm, verts[0], verts[1], verts[2], NULL, NULL, 1); + } else if (amount == 4) { + f = NULL; + + /* the order of vertices can be anything, 6 cases to check */ + if( is_quad_convex_v3(verts[0]->co, verts[1]->co, verts[2]->co, verts[3]->co) ) { + f= BM_Make_QuadTri(bm, verts[0], verts[1], verts[2], verts[3], NULL, 1); + } + else if( is_quad_convex_v3(verts[0]->co, verts[2]->co, verts[3]->co, verts[1]->co) ) { + f= BM_Make_QuadTri(bm, verts[0], verts[2], verts[3], verts[1], NULL, 1); + } + else if( is_quad_convex_v3(verts[0]->co, verts[2]->co, verts[1]->co, verts[3]->co) ) { + f= BM_Make_QuadTri(bm, verts[0], verts[2], verts[1], verts[3], NULL, 1); + } + else if( is_quad_convex_v3(verts[0]->co, verts[1]->co, verts[3]->co, verts[2]->co) ) { + f= BM_Make_QuadTri(bm, verts[0], verts[1], verts[3], verts[2], NULL, 1); + } + else if( is_quad_convex_v3(verts[0]->co, verts[3]->co, verts[2]->co, verts[1]->co) ) { + f= BM_Make_QuadTri(bm, verts[0], verts[3], verts[2], verts[1], NULL, 1); + } + else if( is_quad_convex_v3(verts[0]->co, verts[3]->co, verts[1]->co, verts[2]->co) ) { + f= BM_Make_QuadTri(bm, verts[0], verts[3], verts[1], verts[2], NULL, 1); + } + else { + printf("cannot find nice quad from concave set of vertices\n"); + } + + if (f) BMO_SetFlag(bm, f, ELE_OUT); + } +} |