[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [59193] trunk/blender/source/blender/bmesh : rewrite edgenet fill bmesh operator.
Campbell Barton
ideasman42 at gmail.com
Fri Aug 16 16:18:54 CEST 2013
Revision: 59193
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=59193
Author: campbellbarton
Date: 2013-08-16 14:18:54 +0000 (Fri, 16 Aug 2013)
Log Message:
-----------
rewrite edgenet fill bmesh operator.
previous code created faces with mixed face-flipping and could get very slow,
test with ~60,000 edges here hung my system for over 2min (didnt wait for it to finish), new code executes in about 1 second.
new code doesn't attempt to flip faces correctly, its quite involved to do so, especially when the new faces are not created adjacent to eachother.
so simpler to calculate normals afterwards.
Modified Paths:
--------------
trunk/blender/source/blender/bmesh/CMakeLists.txt
trunk/blender/source/blender/bmesh/bmesh.h
trunk/blender/source/blender/bmesh/operators/bmo_create.c
trunk/blender/source/blender/bmesh/operators/bmo_edgenet.c
trunk/blender/source/blender/bmesh/operators/bmo_normals.c
Added Paths:
-----------
trunk/blender/source/blender/bmesh/tools/bmesh_edgenet.c
trunk/blender/source/blender/bmesh/tools/bmesh_edgenet.h
Modified: trunk/blender/source/blender/bmesh/CMakeLists.txt
===================================================================
--- trunk/blender/source/blender/bmesh/CMakeLists.txt 2013-08-16 14:12:52 UTC (rev 59192)
+++ trunk/blender/source/blender/bmesh/CMakeLists.txt 2013-08-16 14:18:54 UTC (rev 59193)
@@ -123,6 +123,8 @@
tools/bmesh_decimate_dissolve.c
tools/bmesh_decimate_unsubdivide.c
tools/bmesh_decimate.h
+ tools/bmesh_edgenet.c
+ tools/bmesh_edgenet.h
tools/bmesh_edgesplit.c
tools/bmesh_edgesplit.h
tools/bmesh_path.c
Modified: trunk/blender/source/blender/bmesh/bmesh.h
===================================================================
--- trunk/blender/source/blender/bmesh/bmesh.h 2013-08-16 14:12:52 UTC (rev 59192)
+++ trunk/blender/source/blender/bmesh/bmesh.h 2013-08-16 14:18:54 UTC (rev 59193)
@@ -271,6 +271,7 @@
#include "tools/bmesh_bevel.h"
#include "tools/bmesh_decimate.h"
+#include "tools/bmesh_edgenet.h"
#include "tools/bmesh_edgesplit.h"
#include "tools/bmesh_path.h"
#include "tools/bmesh_triangulate.h"
Modified: trunk/blender/source/blender/bmesh/operators/bmo_create.c
===================================================================
--- trunk/blender/source/blender/bmesh/operators/bmo_create.c 2013-08-16 14:12:52 UTC (rev 59192)
+++ trunk/blender/source/blender/bmesh/operators/bmo_create.c 2013-08-16 14:18:54 UTC (rev 59193)
@@ -145,6 +145,7 @@
/* EdgeNet Create */
if (tote != 0) {
/* call edgenet prepare op so additional face creation cases work */
+
BMOperator op_sub;
BMO_op_initf(bm, &op_sub, op->flag, "edgenet_prepare edges=%fe", ELE_NEW);
BMO_op_exec(bm, &op_sub);
Modified: trunk/blender/source/blender/bmesh/operators/bmo_edgenet.c
===================================================================
--- trunk/blender/source/blender/bmesh/operators/bmo_edgenet.c 2013-08-16 14:12:52 UTC (rev 59192)
+++ trunk/blender/source/blender/bmesh/operators/bmo_edgenet.c 2013-08-16 14:18:54 UTC (rev 59193)
@@ -48,1017 +48,38 @@
#define ELE_NEW 1
#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;
- BMDiskLink v1_disk_link, v2_disk_link;
-} 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 * */
-
-BLI_INLINE BMDiskLink *rs_edge_link_get(BMEdge *e, BMVert *v, EdgeData *e_data)
-{
- return v == ((BMEdge *)e)->v1 ? &(((EdgeData *)e_data)->v1_disk_link) :
- &(((EdgeData *)e_data)->v2_disk_link);
-}
-
-static bool rotsys_append_edge(BMEdge *e, BMVert *v,
- EdgeData *edata, VertData *vdata)
-{
- EdgeData *ed = &edata[BM_elem_index_get(e)];
- VertData *vd = &vdata[BM_elem_index_get(v)];
-
- if (!vd->e) {
- Link *e1 = (Link *)rs_edge_link_get(e, v, ed);
-
- vd->e = e;
- e1->next = e1->prev = (Link *)e;
- }
- else {
- BMDiskLink *dl1, *dl2, *dl3;
- EdgeData *ved = &edata[BM_elem_index_get(vd->e)];
-
- dl1 = rs_edge_link_get(e, v, ed);
- dl2 = rs_edge_link_get(vd->e, v, ved);
- dl3 = dl2->prev ? rs_edge_link_get(dl2->prev, v, &edata[BM_elem_index_get(dl2->prev)]) : NULL;
-
- dl1->next = vd->e;
- dl1->prev = dl2->prev;
-
- dl2->prev = e;
- if (dl3) {
- dl3->next = e;
- }
- }
-
- return true;
-}
-
-static void UNUSED_FUNCTION(rotsys_remove_edge)(BMEdge *e, BMVert *v,
- EdgeData *edata, VertData *vdata)
-{
- EdgeData *ed = edata + BM_elem_index_get(e);
- VertData *vd = vdata + BM_elem_index_get(v);
- BMDiskLink *e1, *e2;
-
- e1 = rs_edge_link_get(e, v, ed);
- if (e1->prev) {
- e2 = rs_edge_link_get(e1->prev, v, ed);
- e2->next = e1->next;
- }
-
- if (e1->next) {
- e2 = rs_edge_link_get(e1->next, v, ed);
- e2->prev = e1->prev;
- }
-
- if (vd->e == e)
- vd->e = (e != e1->next) ? e1->next : NULL;
-
- e1->next = e1->prev = NULL;
-}
-
-static BMEdge *rotsys_nextedge(BMEdge *e, BMVert *v,
- EdgeData *edata, VertData *UNUSED(vdata))
-{
- if (v == e->v1)
- return edata[BM_elem_index_get(e)].v1_disk_link.next;
- if (v == e->v2)
- return edata[BM_elem_index_get(e)].v2_disk_link.next;
- return NULL;
-}
-
-static BMEdge *rotsys_prevedge(BMEdge *e, BMVert *v,
- EdgeData *edata, VertData *UNUSED(vdata))
-{
- if (v == e->v1)
- return edata[BM_elem_index_get(e)].v1_disk_link.prev;
- if (v == e->v2)
- return edata[BM_elem_index_get(e)].v2_disk_link.prev;
- return NULL;
-}
-
-static void rotsys_reverse(BMEdge *UNUSED(e), BMVert *v, EdgeData *edata, VertData *vdata)
-{
- BMEdge **edges = NULL;
- BMEdge *e_first;
- BMEdge *e;
- BLI_array_staticdeclare(edges, BM_DEFAULT_NGON_STACK_SIZE);
- int i, totedge;
-
- e = e_first = vdata[BM_elem_index_get(v)].e;
- do {
- BLI_array_append(edges, e);
- e = rotsys_nextedge(e, v, edata, vdata);
- } while (e != e_first);
-
- totedge = BLI_array_count(edges);
- for (i = 0; i < totedge / 2; i++) {
- SWAP(BMEdge *, edges[i], edges[totedge - 1 - i]);
- }
-
- vdata[BM_elem_index_get(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)(BMVert *v, EdgeData *edata, VertData *vdata)
-{
- BMEdge *e = vdata[BM_elem_index_get(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_elem_index_get(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_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
- 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, (uintptr_t)e2) ||
- BLI_smallhash_haskey(hash, (uintptr_t)v))
- {
- ok = 0;
- break;
- }
-
- BLI_array_append(verts, v);
- BLI_array_append(edges, e2);
-
- BLI_smallhash_insert(hash, (uintptr_t)e2, NULL);
-
- v = BM_edge_other_vert(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_face_create_ngon(bm, verts[0], verts[1], edges, BLI_array_count(edges), BM_CREATE_NO_DOUBLE);
- if (UNLIKELY(f == NULL)) {
- 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;
-
- BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
- vd = vdata + BM_elem_index_get(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_elem_index_get(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_elem_index_get(v);
-
- if (!vd->e)
- continue;
-
- e = vd->e;
- do {
- BMVert *v2 = BM_edge_other_vert(e, v);
- VertData *vd2 = vdata + BM_elem_index_get(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, BM_DEFAULT_NGON_STACK_SIZE);
- BMVert *v;
- RNG *rng;
- /* BMVert **verts = NULL; */
- /* BLI_array_staticdeclare(verts, BM_DEFAULT_NGON_STACK_SIZE); */ /* UNUSE */
- int i;
-
- BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
- BMIter eiter;
- float no[3], cent[3];
- int j, k = 0, totedge = 0;
-
- if (BM_elem_index_get(v) == -1)
- continue;
-
- BLI_array_empty(edges);
-
- BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
- if (BMO_elem_flag_test(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_edge_other_vert(e1, v))->co, v->co);
- sub_v3_v3v3(vec2, (BM_edge_other_vert(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_edge_other_vert(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_elem_index_get(v2)].sco, vec1);
- }
-
- rng = BLI_rng_new_srandom(0);
-
- /* first, ensure no 0 or 180 angles between adjacent
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list