[Bf-blender-cvs] [9df6a53] master: Knife: use BM_face_split_edgenet for detecting holes
Campbell Barton
noreply at git.blender.org
Sat Dec 12 18:00:16 CET 2015
Commit: 9df6a539a2c93c2b8fe32d0d5b564c62bbadba9a
Author: Campbell Barton
Date: Sun Dec 13 03:46:36 2015 +1100
Branches: master
https://developer.blender.org/rB9df6a539a2c93c2b8fe32d0d5b564c62bbadba9a
Knife: use BM_face_split_edgenet for detecting holes
Knife had its own code for detecting holes which worked quite well,
but would prefer to use generic bmesh API call here.
===================================================================
M source/blender/editors/mesh/editmesh_knife.c
===================================================================
diff --git a/source/blender/editors/mesh/editmesh_knife.c b/source/blender/editors/mesh/editmesh_knife.c
index 818526a..5b9af2f 100644
--- a/source/blender/editors/mesh/editmesh_knife.c
+++ b/source/blender/editors/mesh/editmesh_knife.c
@@ -75,6 +75,9 @@
#include "mesh_intern.h" /* own include */
+/* detect isolated holes and fill them */
+#define USE_NET_ISLAND_CONNECT
+
#define KMAXDIST 10 /* max mouse distance from edge before not detecting it */
/* WARNING: knife float precision is fragile:
@@ -166,6 +169,11 @@ typedef struct KnifeTool_OpData {
MemArena *arena;
+#ifdef USE_NET_ISLAND_CONNECT
+ /* cleared each use */
+ MemArena *arena_edgenet;
+#endif
+
GHash *origvertmap;
GHash *origedgemap;
GHash *kedgefacemap;
@@ -2205,330 +2213,6 @@ static int sort_verts_by_dist_cb(void *co_p, const void *cur_a_p, const void *cu
else return 0;
}
-/* The chain so far goes from an instantiated vertex to kfv (some may be reversed).
- * If possible, complete the chain to another instantiated vertex and return 1, else return 0.
- * The visited hash says which KnifeVert's have already been tried, not including kfv. */
-static bool find_chain_search(KnifeTool_OpData *kcd, KnifeVert *kfv, ListBase *fedges, SmallHash *visited,
- ListBase *chain)
-{
- Ref *r;
- KnifeEdge *kfe;
- KnifeVert *kfv_other;
-
- if (kfv->v)
- return true;
-
- BLI_smallhash_insert(visited, (uintptr_t)kfv, NULL);
- /* Try all possible next edges. Could either go through fedges
- * (all the KnifeEdges for the face being cut) or could go through
- * kve->edges and restrict to cutting face and uninstantiated edges.
- * Not clear which is better. Let's do the first. */
- for (r = fedges->first; r; r = r->next) {
- kfe = r->ref;
- kfv_other = NULL;
- if (kfe->v1 == kfv)
- kfv_other = kfe->v2;
- else if (kfe->v2 == kfv)
- kfv_other = kfe->v1;
- if (kfv_other && !BLI_smallhash_haskey(visited, (uintptr_t)kfv_other)) {
- knife_append_list(kcd, chain, kfe);
- if (find_chain_search(kcd, kfv_other, fedges, visited, chain))
- return true;
- BLI_remlink(chain, chain->last);
- }
- }
- return false;
-}
-
-static ListBase *find_chain_from_vertex(KnifeTool_OpData *kcd, KnifeEdge *kfe, BMVert *v, ListBase *fedges)
-{
- SmallHash visited_, *visited = &visited_;
- ListBase *ans;
- bool found;
-
- ans = knife_empty_list(kcd);
- knife_append_list(kcd, ans, kfe);
- found = false;
- BLI_smallhash_init(visited);
- if (kfe->v1->v == v) {
- BLI_smallhash_insert(visited, (uintptr_t)(kfe->v1), NULL);
- found = find_chain_search(kcd, kfe->v2, fedges, visited, ans);
- }
- else {
- BLI_assert(kfe->v2->v == v);
- BLI_smallhash_insert(visited, (uintptr_t)(kfe->v2), NULL);
- found = find_chain_search(kcd, kfe->v1, fedges, visited, ans);
- }
-
- BLI_smallhash_release(visited);
-
- if (found)
- return ans;
- else
- return NULL;
-}
-
-/* Find a chain in fedges from one instantiated vertex to another.
- * Remove the edges in the chain from fedges and return a separate list of the chain. */
-static ListBase *find_chain(KnifeTool_OpData *kcd, ListBase *fedges)
-{
- Ref *r, *ref;
- KnifeEdge *kfe;
- BMVert *v1, *v2;
- ListBase *ans;
-
- ans = NULL;
-
- for (r = fedges->first; r; r = r->next) {
- kfe = r->ref;
- v1 = kfe->v1->v;
- v2 = kfe->v2->v;
- if (v1 && v2) {
- ans = knife_empty_list(kcd);
- knife_append_list(kcd, ans, kfe);
- break;
- }
- if (v1)
- ans = find_chain_from_vertex(kcd, kfe, v1, fedges);
- else if (v2)
- ans = find_chain_from_vertex(kcd, kfe, v2, fedges);
- if (ans)
- break;
- }
- if (ans) {
- BLI_assert(!BLI_listbase_is_empty(ans));
- for (r = ans->first; r; r = r->next) {
- ref = find_ref(fedges, r->ref);
- BLI_assert(ref != NULL);
- BLI_remlink(fedges, ref);
- }
- }
- return ans;
-}
-
-/* The hole so far goes from kfvfirst to kfv (some may be reversed).
- * If possible, complete the hole back to kfvfirst and return 1, else return 0.
- * The visited hash says which KnifeVert's have already been tried, not including kfv or kfvfirst. */
-static bool find_hole_search(KnifeTool_OpData *kcd, KnifeVert *kfvfirst, KnifeVert *kfv, ListBase *fedges,
- SmallHash *visited, ListBase *hole)
-{
- Ref *r;
- KnifeEdge *kfe, *kfelast;
- KnifeVert *kfv_other;
-
- if (kfv == kfvfirst)
- return true;
-
- BLI_smallhash_insert(visited, (uintptr_t)kfv, NULL);
- kfelast = ((Ref *)hole->last)->ref;
- for (r = fedges->first; r; r = r->next) {
- kfe = r->ref;
- if (kfe == kfelast)
- continue;
- if (kfe->v1->v || kfe->v2->v)
- continue;
- kfv_other = NULL;
- if (kfe->v1 == kfv)
- kfv_other = kfe->v2;
- else if (kfe->v2 == kfv)
- kfv_other = kfe->v1;
- if (kfv_other && !BLI_smallhash_haskey(visited, (uintptr_t)kfv_other)) {
- knife_append_list(kcd, hole, kfe);
- if (find_hole_search(kcd, kfvfirst, kfv_other, fedges, visited, hole))
- return true;
- BLI_remlink(hole, hole->last);
- }
- }
- return false;
-}
-
-/* Find a hole (simple cycle with no instantiated vertices).
- * Remove the edges in the cycle from fedges and return a separate list of the cycle */
-static ListBase *find_hole(KnifeTool_OpData *kcd, ListBase *fedges)
-{
- ListBase *ans;
- Ref *r, *ref;
- KnifeEdge *kfe;
- SmallHash visited_, *visited = &visited_;
- bool found;
-
- ans = NULL;
- found = false;
-
- for (r = fedges->first; r && !found; r = r->next) {
- kfe = r->ref;
- if (kfe->v1->v || kfe->v2->v || kfe->v1 == kfe->v2)
- continue;
-
- BLI_smallhash_init(visited);
- ans = knife_empty_list(kcd);
- knife_append_list(kcd, ans, kfe);
-
- found = find_hole_search(kcd, kfe->v1, kfe->v2, fedges, visited, ans);
-
- BLI_smallhash_release(visited);
- }
-
- if (found) {
- for (r = ans->first; r; r = r->next) {
- kfe = r->ref;
- ref = find_ref(fedges, r->ref);
- if (ref)
- BLI_remlink(fedges, ref);
- }
- return ans;
- }
- else {
- return NULL;
- }
-}
-
-/* Try to find "nice" diagonals - short, and far apart from each other.
- * If found, return true and make a 'main chain' going across f which uses
- * the two diagonals and one part of the hole, and a 'side chain' that
- * completes the hole. */
-static bool find_hole_chains(KnifeTool_OpData *kcd, ListBase *hole, BMFace *f, ListBase **mainchain,
- ListBase **sidechain)
-{
- float (*fco)[2], (*hco)[2];
- BMVert **fv;
- KnifeVert **hv;
- KnifeEdge **he;
- Ref *r;
- KnifeVert *kfv, *kfvother;
- KnifeEdge *kfe;
- ListBase *chain;
- BMVert *v;
- BMIter iter;
- int nh, nf, i, j, k, m, ax, ay, sep = 0 /* Quite warnings */, bestsep;
- int besti[2], bestj[2];
- float dist_sq, dist_best_sq;
-
- nh = BLI_listbase_count(hole);
- nf = f->len;
- if (nh < 2 || nf < 3)
- return false;
-
- /* Gather 2d projections of hole and face vertex coordinates.
- * Use best-axis projection - not completely accurate, maybe revisit */
- axis_dominant_v3(&ax, &ay, f->no);
- hco = BLI_memarena_alloc(kcd->arena, nh * sizeof(float[2]));
- fco = BLI_memarena_alloc(kcd->arena, nf * sizeof(float[2]));
- hv = BLI_memarena_alloc(kcd->arena, nh * sizeof(KnifeVert *));
- fv = BLI_memarena_alloc(kcd->arena, nf * sizeof(BMVert *));
- he = BLI_memarena_alloc(kcd->arena, nh * sizeof(KnifeEdge *));
-
- i = 0;
- kfv = NULL;
- kfvother = NULL;
- for (r = hole->first; r; r = r->next) {
- kfe = r->ref;
- he[i] = kfe;
- if (kfvother == NULL) {
- kfv = kfe->v1;
- }
- else {
- kfv = kfvother;
- BLI_assert(kfv == kfe->v1 || kfv == kfe->v2);
- }
- hco[i][0] = kfv->co[ax];
- hco[i][1] = kfv->co[ay];
- hv[i] = kfv;
- kfvother = (kfe->v1 == kfv) ? kfe->v2 : kfe->v1;
- i++;
- }
-
- j = 0;
- BM_ITER_ELEM (v, &iter, f, BM_VERTS_OF_FACE) {
- fco[j][0] = v->co[ax];
- fco[j][1] = v->co[ay];
- fv[j] = v;
- j++;
- }
-
- /* For first diagonal (m == 0), want shortest length.
- * For second diagonal (m == 1), want max separation of index of hole
- * vertex from the hole vertex used in the first diagonal, and from there
- * want the one with shortest length not to the same vertex as the first diagonal. */
- for (m = 0; m < 2; m++) {
- besti[m] = -1;
- bestj[m] = -1;
- dist_best_sq = FLT_MAX;
- bestsep = 0;
- for (i = 0; i < nh; i++) {
- if (m == 1) {
- if (i == besti[0])
- continue;
- sep = (i + nh - besti[0]) % nh;
- sep = MIN2(sep, nh - sep);
- if (sep < bestsep)
- continue;
- dist_best_sq = FLT_MAX;
- }
- for (j = 0; j < nf; j++) {
- bool ok;
-
- if (m == 1 && j == bestj[0])
- continue;
- dist_sq = len_squared_v2v2(hco[i], fco[j]);
- if (dist_sq > dist_best_sq)
- continue;
-
- ok = true;
- for (k = 0; k < nh && ok; k++) {
- if (k == i || (k + 1) % nh == i)
- continue;
- if (isect_seg_seg_v2(hco[i], fco[j], hco[k], hco[(k + 1) % nh]))
- ok = false;
- }
- if (!ok)
- continue;
- for (k = 0; k < nf && ok; k++) {
- if (k == j || (k + 1) % nf == j)
- continue;
- if (isect_seg_seg_v2(hco[i], fco[j], fco[k], fco[(k + 1) % nf]))
- ok = false;
- }
- if (ok) {
- besti[m] = i;
- bestj[m] = j;
- if (m == 1)
- bestsep = sep;
- dist_best_sq = dist_sq;
- }
- }
- }
- }
-
- if (besti[0] != -1 && besti[1] != -1) {
- BLI_assert(besti[0] != besti[1] && bestj[0] != bestj[1]);
- kfe = new_knife_edge(kcd);
- kfe->v1 = get_bm_knife_vert(kcd, fv[bestj[0]]);
- kfe->v2 = hv[besti[0]];
- chain = knife_empty_list(kcd);
- knife_append_list(kcd, chain, kfe);
- for (i = besti[0]; i != besti[1]; i = (i + 1) % nh) {
- knife_append_list(kcd, chain, he[i]);
- }
- kfe = new_knife_edge(kcd);
- kfe->v1 = hv[besti[1]];
- kfe->v2 = get_bm_knife_vert(kcd, fv[bestj[1]]);
- knife_append_list(kcd, chain, kfe);
- *mainchain = chain;
-
- chain = knife_empty_list(kcd);
- for (i = besti[1]; i != besti[0]; i = (i + 1) % nh) {
- knife_append_list(kcd, chain, he[i]);
- }
- *sidechain = chain;
-
- return true;
- }
- else {
- return false;
- }
-}
-
static bool knife_verts_edge_in_face(KnifeVert *v1, KnifeVert *v2, BMFace *f)
{
bool v1_inside, v2_inside;
@@ -2572,201 +2256,110 @@ static bool knife_verts_edge_in_face(KnifeVert *v1, KnifeVert *v2, BMFace *f)
return false;
}
-static bool knife_edge_in_face(KnifeEdge *kfe, BM
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list