[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [56687] trunk/blender/source/blender/bmesh : - add generic edge-loop utility functions for bmesh.

Campbell Barton ideasman42 at gmail.com
Sat May 11 16:40:04 CEST 2013


Revision: 56687
          http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=56687
Author:   campbellbarton
Date:     2013-05-11 14:40:03 +0000 (Sat, 11 May 2013)
Log Message:
-----------
- add generic edge-loop utility functions for bmesh.
- rewrite bridge tool to use the new functions (using edge & vertex arrays was quite cumbersome).

Modified Paths:
--------------
    trunk/blender/source/blender/bmesh/CMakeLists.txt
    trunk/blender/source/blender/bmesh/bmesh.h
    trunk/blender/source/blender/bmesh/operators/bmo_connect.c

Added Paths:
-----------
    trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.c
    trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.h
    trunk/blender/source/blender/bmesh/operators/bmo_bridge.c

Modified: trunk/blender/source/blender/bmesh/CMakeLists.txt
===================================================================
--- trunk/blender/source/blender/bmesh/CMakeLists.txt	2013-05-11 13:10:39 UTC (rev 56686)
+++ trunk/blender/source/blender/bmesh/CMakeLists.txt	2013-05-11 14:40:03 UTC (rev 56687)
@@ -41,6 +41,7 @@
 set(SRC
 	operators/bmo_beautify.c
 	operators/bmo_bevel.c
+	operators/bmo_bridge.c
 	operators/bmo_connect.c
 	operators/bmo_create.c
 	operators/bmo_dissolve.c
@@ -70,6 +71,8 @@
 	intern/bmesh_construct.h
 	intern/bmesh_core.c
 	intern/bmesh_core.h
+	intern/bmesh_edgeloop.c
+	intern/bmesh_edgeloop.h
 	intern/bmesh_inline.h
 	intern/bmesh_interp.c
 	intern/bmesh_interp.h

Modified: trunk/blender/source/blender/bmesh/bmesh.h
===================================================================
--- trunk/blender/source/blender/bmesh/bmesh.h	2013-05-11 13:10:39 UTC (rev 56686)
+++ trunk/blender/source/blender/bmesh/bmesh.h	2013-05-11 14:40:03 UTC (rev 56687)
@@ -253,6 +253,7 @@
 
 #include "intern/bmesh_construct.h"
 #include "intern/bmesh_core.h"
+#include "intern/bmesh_edgeloop.h"
 #include "intern/bmesh_interp.h"
 #include "intern/bmesh_iterators.h"
 #include "intern/bmesh_log.h"

Added: trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.c	                        (rev 0)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.c	2013-05-11 14:40:03 UTC (rev 56687)
@@ -0,0 +1,300 @@
+/*
+ * ***** 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.
+ *
+ * The Original Code is Copyright (C) 2013 by Campbell Barton.
+ * All rights reserved.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/bmesh/intern/bmesh_edgeloop.c
+ *  \ingroup bmesh
+ *
+ * Generic utility functions for getting edge loops from a mesh.
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_math_vector.h"
+#include "BLI_listbase.h"
+
+#include "bmesh.h"
+
+#include "bmesh_edgeloop.h"  /* own include */
+
+typedef struct BMEdgeLoopStore {
+	struct BMEdgeLoopStore *next, *prev;
+	ListBase verts;
+	int flag;
+	int len;
+	/* optional values  to calc */
+	float co[3], no[3];
+} BMEdgeLoopStore;
+
+#define BM_EDGELOOP_IS_CLOSED (1 << 0)
+
+static int bm_vert_other_tag(BMVert *v, BMVert *v_prev,
+                             BMEdge **r_e)
+{
+	BMIter iter;
+	BMEdge *e, *e_next;
+	unsigned int count = 0;
+
+	BM_ITER_ELEM (e, &iter, v, BM_EDGES_OF_VERT) {
+		if (BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG)) {
+			BMVert *v_other = BM_edge_other_vert(e, v);
+			if (v_other != v_prev) {
+				e_next = e;
+				count++;
+			}
+		}
+	}
+
+	*r_e = e_next;
+	return count;
+}
+
+/**
+ * \return success
+ */
+static bool bm_loop_build(BMEdgeLoopStore *el_store, BMVert *v_prev, BMVert *v, int dir)
+{
+	void (*add_fn)(ListBase *, void *) = dir == 1 ? BLI_addhead : BLI_addtail;
+	BMEdge *e_next;
+	BMVert *v_next;
+	BMVert *v_first = v;
+
+	BLI_assert(ABS(dir) == 1);
+
+	if (!BM_elem_flag_test(v, BM_ELEM_INTERNAL_TAG)) {
+		return true;
+	}
+
+	while (v) {
+		LinkData *node = MEM_callocN(sizeof(*node), __func__);
+		int count;
+		node->data = v;
+		add_fn(&el_store->verts, node);
+		el_store->len++;
+		BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
+
+		count = bm_vert_other_tag(v, v_prev, &e_next);
+		if (count == 1) {
+			v_next = BM_edge_other_vert(e_next, v);
+			BM_elem_flag_disable(e_next, BM_ELEM_INTERNAL_TAG);
+			if (UNLIKELY(v_next == v_first)) {
+				el_store->flag |= BM_EDGELOOP_IS_CLOSED;
+				v_next = NULL;
+			}
+		}
+		else if (count == 0) {
+			/* pass */
+			v_next = NULL;
+		}
+		else {
+			v_next = NULL;
+			return false;
+		}
+
+		v_prev = v;
+		v = v_next;
+	}
+
+	return true;
+}
+
+/**
+ * \return listbase of listbases, each linking to a vertex.
+ */
+int BM_mesh_edgeloops_find(BMesh *bm, ListBase *r_eloops,
+                           bool (*test_fn)(BMEdge *, void *user_data), void *user_data)
+{
+	BMIter iter;
+	BMEdge *e;
+	BMVert *v;
+	int count = 0;
+
+	BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) {
+		BM_elem_flag_disable(v, BM_ELEM_INTERNAL_TAG);
+	}
+
+	/* first flush edges to tags, and tag verts */
+	BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+		if (test_fn(e, user_data)) {
+			BM_elem_flag_enable(e,     BM_ELEM_INTERNAL_TAG);
+			BM_elem_flag_enable(e->v1, BM_ELEM_INTERNAL_TAG);
+			BM_elem_flag_enable(e->v2, BM_ELEM_INTERNAL_TAG);
+		}
+		else {
+			BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
+		}
+	}
+
+	BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+		if (BM_elem_flag_test(e, BM_ELEM_INTERNAL_TAG)) {
+			BMEdgeLoopStore *el_store = MEM_callocN(sizeof(BMEdgeLoopStore), __func__);
+
+			/* add both directions */
+			if (bm_loop_build(el_store, e->v1, e->v2,  1) &&
+			    bm_loop_build(el_store, e->v2, e->v1, -1))
+			{
+				BLI_addtail(r_eloops, el_store);
+				BM_elem_flag_disable(e, BM_ELEM_INTERNAL_TAG);
+				count++;
+			}
+			else {
+				BM_edgeloop_free(r_eloops, el_store);
+			}
+		}
+	}
+	return count;
+}
+
+void BM_mesh_edgeloops_free(ListBase *eloops)
+{
+	BMEdgeLoopStore *el_store;
+	while ((el_store = eloops->first)) {
+		BM_edgeloop_free(eloops, el_store);
+	}
+}
+
+void BM_mesh_edgeloops_calc_center(BMesh *bm, ListBase *eloops)
+{
+	BMEdgeLoopStore *el_store;
+	for (el_store = eloops->first; el_store; el_store = el_store->next) {
+		BM_edgeloop_calc_center(bm, el_store);
+	}
+}
+
+void BM_mesh_edgeloops_calc_normal(BMesh *bm, ListBase *eloops)
+{
+	BMEdgeLoopStore *el_store;
+	for (el_store = eloops->first; el_store; el_store = el_store->next) {
+		BM_edgeloop_calc_normal(bm, el_store);
+	}
+}
+
+/* -------------------------------------------------------------------- */
+/* BM_edgeloop_*** functions */
+
+void BM_edgeloop_free(ListBase *eloops, BMEdgeLoopStore *el_store)
+{
+	BLI_freelistN(&el_store->verts);
+	BLI_remlink(eloops, el_store);
+	MEM_freeN(el_store);
+}
+
+bool BM_edgeloop_is_closed(BMEdgeLoopStore *el_store)
+{
+	return (el_store->flag & BM_EDGELOOP_IS_CLOSED) != 0;
+}
+
+ListBase *BM_edgeloop_verts_get(BMEdgeLoopStore *el_store)
+{
+	return &el_store->verts;
+}
+
+int BM_edgeloop_length_get(BMEdgeLoopStore *el_store)
+{
+	return el_store->len;
+}
+
+const float *BM_edgeloop_normal_get(struct BMEdgeLoopStore *el_store)
+{
+	return el_store->no;
+}
+
+const float *BM_edgeloop_center_get(struct BMEdgeLoopStore *el_store)
+{
+	return el_store->co;
+}
+
+
+#define NODE_AS_CO(n) ((BMVert *)((LinkData *)n)->data)->co
+
+void BM_edgeloop_calc_center(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store)
+{
+	LinkData *node_curr = el_store->verts.last;
+	LinkData *node_prev = ((LinkData *)el_store->verts.last)->prev;
+	LinkData *node_first = el_store->verts.first;
+	LinkData *node_next = node_first;
+
+	float const *v_prev = NODE_AS_CO(node_prev);
+	float const *v_curr = NODE_AS_CO(node_curr);
+	float const *v_next = NODE_AS_CO(node_next);
+
+	float totw = 0.0f;
+	float w_prev;
+
+	zero_v3(el_store->co);
+
+	w_prev = len_v3v3(v_prev, v_curr);
+	do {
+		const float w_curr = len_v3v3(v_curr, v_next);
+		const float w = (w_curr + w_prev);
+		madd_v3_v3fl(el_store->co, v_curr, w);
+		totw += w;
+		w_prev = w_curr;
+
+
+		node_prev = node_curr;
+		node_curr = node_next;
+		node_next = node_next->next;
+
+		if (node_next == NULL) {
+			break;
+		}
+		v_prev = v_curr;
+		v_curr = v_next;
+		v_next = NODE_AS_CO(node_next);
+	} while (1);
+
+	if (totw != 0.0f)
+		mul_v3_fl(el_store->co, 1.0f / (float) totw);
+
+}
+
+void BM_edgeloop_calc_normal(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store)
+{
+	LinkData *node_curr = el_store->verts.first;
+	float const *v_prev = NODE_AS_CO(el_store->verts.last);
+	float const *v_curr = NODE_AS_CO(node_curr);
+
+	/* Newell's Method */
+	do {
+		add_newell_cross_v3_v3v3(el_store->no, v_prev, v_curr);
+
+		if ((node_curr = node_curr->next)) {
+			v_prev = v_curr;
+			v_curr = NODE_AS_CO(node_curr);
+		}
+		else {
+			break;
+		}
+	} while (true);
+
+	if (UNLIKELY(normalize_v3(el_store->no) == 0.0f)) {
+		el_store->no[2] = 1.0f; /* other axis set to 0.0 */
+	}
+}
+
+
+void BM_edgeloop_flip(BMesh *UNUSED(bm), BMEdgeLoopStore *el_store)
+{
+	negate_v3(el_store->no);
+	BLI_reverselist(&el_store->verts);
+}


Property changes on: trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.c
___________________________________________________________________
Added: svn:eol-style
   + native

Added: trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.h
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.h	                        (rev 0)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_edgeloop.h	2013-05-11 14:40:03 UTC (rev 56687)
@@ -0,0 +1,57 @@
+/*
+ * ***** 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.
+ *
+ * The Original Code is Copyright (C) 2013 by Campbell Barton.
+ * All rights reserved.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#ifndef __BMESH_EDGELOOP_H__
+#define __BMESH_EDGELOOP_H__
+
+/** \file blender/bmesh/intern/bmesh_edgeloop.h
+ *  \ingroup bmesh
+ */
+
+struct ListBase;
+struct BMEdgeLoopStore;
+

@@ Diff output truncated at 10240 characters. @@



More information about the Bf-blender-cvs mailing list