[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [57653] trunk/blender/source/blender: Extend existing editmesh connect tool so it can connect across multiple faces .
Campbell Barton
ideasman42 at gmail.com
Sat Jun 22 19:25:02 CEST 2013
Revision: 57653
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=57653
Author: campbellbarton
Date: 2013-06-22 17:25:02 +0000 (Sat, 22 Jun 2013)
Log Message:
-----------
Extend existing editmesh connect tool so it can connect across multiple faces.
only use this when 2 vertices are selected, otherwise use the same behavior as before.
This works a little like a fast knife tool, but it only cuts straight lines and doesnt depend on the view-port.
Examples:
- http://www.graphicall.org/ftp/ideasman42/mesh_connect_pair.png
- http://www.graphicall.org/ftp/ideasman42/mesh_connect_pair_curve.png
Modified Paths:
--------------
trunk/blender/source/blender/bmesh/CMakeLists.txt
trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c
trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h
trunk/blender/source/blender/bmesh/operators/bmo_connect.c
trunk/blender/source/blender/editors/mesh/editmesh_tools.c
Added Paths:
-----------
trunk/blender/source/blender/bmesh/operators/bmo_connect_pair.c
Modified: trunk/blender/source/blender/bmesh/CMakeLists.txt
===================================================================
--- trunk/blender/source/blender/bmesh/CMakeLists.txt 2013-06-22 14:35:09 UTC (rev 57652)
+++ trunk/blender/source/blender/bmesh/CMakeLists.txt 2013-06-22 17:25:02 UTC (rev 57653)
@@ -43,6 +43,7 @@
operators/bmo_bevel.c
operators/bmo_bridge.c
operators/bmo_connect.c
+ operators/bmo_connect_pair.c
operators/bmo_create.c
operators/bmo_dissolve.c
operators/bmo_dupe.c
Modified: trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c 2013-06-22 14:35:09 UTC (rev 57652)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_opdefines.c 2013-06-22 17:25:02 UTC (rev 57653)
@@ -841,6 +841,26 @@
};
/*
+ * Connect Verts.
+ *
+ * Split faces by adding edges that connect **verts**.
+ */
+static BMOpDefine bmo_connect_vert_pair_def = {
+ "connect_vert_pair",
+ /* slots_in */
+ {{"verts", BMO_OP_SLOT_ELEMENT_BUF, {BM_VERT}},
+ {{'\0'}},
+ },
+ /* slots_out */
+ {{"edges.out", BMO_OP_SLOT_ELEMENT_BUF, {BM_EDGE}},
+ {{'\0'}},
+ },
+ bmo_connect_vert_pair_exec,
+ BMO_OPTYPE_FLAG_UNTAN_MULTIRES | BMO_OPTYPE_FLAG_NORMALS_CALC | BMO_OPTYPE_FLAG_SELECT_FLUSH,
+};
+
+
+/*
* Extrude Faces.
*
* Extrude operator (does not transform)
@@ -1685,6 +1705,7 @@
&bmo_collapse_def,
&bmo_collapse_uvs_def,
&bmo_connect_verts_def,
+ &bmo_connect_vert_pair_def,
&bmo_contextual_create_def,
#ifdef WITH_BULLET
&bmo_convex_hull_def,
Modified: trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h
===================================================================
--- trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h 2013-06-22 14:35:09 UTC (rev 57652)
+++ trunk/blender/source/blender/bmesh/intern/bmesh_operators_private.h 2013-06-22 17:25:02 UTC (rev 57653)
@@ -40,6 +40,7 @@
void bmo_collapse_exec(BMesh *bm, BMOperator *op);
void bmo_collapse_uvs_exec(BMesh *bm, BMOperator *op);
void bmo_connect_verts_exec(BMesh *bm, BMOperator *op);
+void bmo_connect_vert_pair_exec(BMesh *bm, BMOperator *op);
void bmo_contextual_create_exec(BMesh *bm, BMOperator *op);
void bmo_convex_hull_exec(BMesh *bm, BMOperator *op);
void bmo_create_circle_exec(BMesh *bm, BMOperator *op);
Modified: trunk/blender/source/blender/bmesh/operators/bmo_connect.c
===================================================================
--- trunk/blender/source/blender/bmesh/operators/bmo_connect.c 2013-06-22 14:35:09 UTC (rev 57652)
+++ trunk/blender/source/blender/bmesh/operators/bmo_connect.c 2013-06-22 17:25:02 UTC (rev 57653)
@@ -23,7 +23,7 @@
/** \file blender/bmesh/operators/bmo_connect.c
* \ingroup bmesh
*
- * Connect verts across faces (splits faces) and bridge tool.
+ * Connect verts across faces (splits faces).
*/
#include "MEM_guardedalloc.h"
Added: trunk/blender/source/blender/bmesh/operators/bmo_connect_pair.c
===================================================================
--- trunk/blender/source/blender/bmesh/operators/bmo_connect_pair.c (rev 0)
+++ trunk/blender/source/blender/bmesh/operators/bmo_connect_pair.c 2013-06-22 17:25:02 UTC (rev 57653)
@@ -0,0 +1,546 @@
+/*
+ * ***** 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/bmesh/operators/bmo_connect_pair.c
+ * \ingroup bmesh
+ *
+ * Connect vertex pair across multiple faces (splits faces).
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_math.h"
+#include "BLI_utildefines.h"
+
+#include "bmesh.h"
+
+#include "intern/bmesh_operators_private.h" /* own include */
+
+#include "BLI_mempool.h"
+#include "BLI_listbase.h"
+
+/**
+ * Method for connecting across many faces.
+ *
+ * - use the line between both verts and their normal average to construct a matrix.
+ * - using the matrix, we can find all intersecting verts/edges and build connection data.
+ * - then walk the connected data and find the shortest path (as we do with other shortest-path functions).
+ * - if the connection can't be found - fail.
+ * - with the connection found, split all edges tagging verts (or tag verts that sit on the intersection).
+ * - run the standard connect operator.
+ */
+
+#define CONNECT_EPS 0.0001f
+#define VERT_OUT 1
+
+// #define DEBUG_PRINT
+
+typedef struct PathContext {
+ ListBase state_lb;
+ float matrix[3][3];
+ float axis_sep;
+
+ BMVert *v_a, *v_b;
+
+ BLI_mempool *link_pool;
+} PathContext;
+
+/**
+ * Single linked list where each item contains state and points to previous path item.
+ */
+typedef struct PathLink {
+ struct PathLink *next;
+ BMElem *ele; /* edge or vert */
+ BMElem *ele_from; /* edge or face we game from (not 'next->ele') */
+} PathLink;
+
+typedef struct PathLinkState {
+ struct PathLinkState *next, *prev;
+
+ /* chain of links */
+ struct PathLink *link_last;
+
+ /* length along links */
+ float dist;
+ float co_prev[3];
+} PathLinkState;
+
+/* only the x axis */
+static float mul_v1_m3v3(float M[3][3], const float a[3])
+{
+ return M[0][0] * a[0] + M[1][0] * a[1] + M[2][0] * a[2];
+}
+
+static int state_isect_co_pair(const PathContext *pc,
+ const float co_a[3], const float co_b[3])
+{
+ const float diff_a = mul_v1_m3v3((float (*)[3])pc->matrix, co_a) - pc->axis_sep;
+ const float diff_b = mul_v1_m3v3((float (*)[3])pc->matrix, co_b) - pc->axis_sep;
+
+ const int test_a = (fabsf(diff_a) < CONNECT_EPS) ? 0 : (diff_a < 0.0f) ? -1 : 1;
+ const int test_b = (fabsf(diff_b) < CONNECT_EPS) ? 0 : (diff_b < 0.0f) ? -1 : 1;
+
+ if ((test_a && test_b) && (test_a != test_b)) {
+ return 1; /* on either side */
+ }
+ else {
+ return 0;
+ }
+}
+
+static int state_isect_co_exact(const PathContext *pc,
+ const float co[3])
+{
+ const float diff = mul_v1_m3v3((float (*)[3])pc->matrix, co) - pc->axis_sep;
+ return (fabsf(diff) < CONNECT_EPS);
+}
+
+static float state_calc_co_pair_fac(const PathContext *pc,
+ const float co_a[3], const float co_b[3])
+{
+ float diff_a, diff_b, diff_tot;
+
+ diff_a = fabsf(mul_v1_m3v3((float (*)[3])pc->matrix, co_a) - pc->axis_sep);
+ diff_b = fabsf(mul_v1_m3v3((float (*)[3])pc->matrix, co_b) - pc->axis_sep);
+ diff_tot = (diff_a + diff_b);
+ return (diff_tot > FLT_EPSILON) ? (diff_a / diff_tot) : 0.5f;
+}
+
+static void state_calc_co_pair(const PathContext *pc,
+ const float co_a[3], const float co_b[3],
+ float r_co[3])
+{
+ const float fac = state_calc_co_pair_fac(pc, co_a, co_b);
+ interp_v3_v3v3(r_co, co_a, co_b, fac);
+}
+
+/**
+ * Ideally we wouldn't need this and for most cases we don't.
+ * But when a face has vertices that are on the boundary more then once this becomes tricky.
+ */
+static bool state_link_find(PathLinkState *state, BMElem *ele)
+{
+ PathLink *link = state->link_last;
+ BLI_assert(ELEM3(ele->head.htype, BM_VERT, BM_EDGE, BM_FACE));
+ if (link) {
+ do {
+ if (link->ele == ele) {
+ return true;
+ }
+ } while ((link = link->next));
+ }
+ return false;
+}
+
+static void state_link_add(PathContext *pc, PathLinkState *state,
+ BMElem *ele, BMElem *ele_from)
+{
+ PathLink *step_new = BLI_mempool_alloc(pc->link_pool);
+ BLI_assert(ele != ele_from);
+ BLI_assert(state_link_find(state, ele) == false);
+
+#ifdef DEBUG_PRINT
+ printf("%s: adding to state %p:%d, %.4f - ", __func__, state, BLI_findindex(&pc->state_lb, state), state->dist);
+ if (ele->head.htype == BM_VERT) {
+ printf("vert %d, ", BM_elem_index_get(ele));
+ }
+ else if (ele->head.htype == BM_EDGE) {
+ printf("edge %d, ", BM_elem_index_get(ele));
+ }
+ else {
+ BLI_assert(0);
+ }
+
+ if (ele_prev == NULL) {
+ printf("from NULL\n");
+ }
+ else if (ele_prev->head.htype == BM_EDGE) {
+ printf("from edge %d\n", BM_elem_index_get(ele_prev));
+ }
+ else if (ele_prev->head.htype == BM_FACE) {
+ printf("from face %d\n", BM_elem_index_get(ele_prev));
+ }
+ else {
+ BLI_assert(0);
+ }
+#endif
+
+ /* track distance */
+ {
+ float co[3];
+ if (ele->head.htype == BM_VERT) {
+ copy_v3_v3(co, ((BMVert *)ele)->co);
+ }
+ else if (ele->head.htype == BM_EDGE) {
+ state_calc_co_pair(pc, ((BMEdge *)ele)->v1->co, ((BMEdge *)ele)->v2->co, co);
+ }
+ else {
+ BLI_assert(0);
+ }
+
+ /* tally distance */
+ if (ele_from) {
+ state->dist += len_v3v3(state->co_prev, co);
+ }
+ copy_v3_v3(state->co_prev, co);
+ }
+
+ step_new->ele = ele;
+ step_new->ele_from = ele_from;
+ step_new->next = state->link_last;
+ state->link_last = step_new;
+}
+
+static PathLinkState *state_dupe_add(PathContext *pc,
+ PathLinkState *state, const PathLinkState *state_orig)
+{
+ state = MEM_mallocN(sizeof(*state), __func__);
+ *state = *state_orig;
+ BLI_addhead(&pc->state_lb, state);
+ return state;
+}
+
+/* walk around the face edges */
+static PathLinkState *state_step__face_edges(PathContext *pc,
+ PathLinkState *state, const PathLinkState *state_orig,
+ BMLoop *l_iter, BMLoop *l_last)
+{
+ do {
+ if (state_isect_co_pair(pc, l_iter->v->co, l_iter->next->v->co)) {
+ BMElem *ele_next = (BMElem *)l_iter->e;
+ BMElem *ele_next_from = (BMElem *)l_iter->f;
+
+ if (state_link_find(state, ele_next) == false) {
+ if (state_orig->link_last != state->link_last) {
+ state = state_dupe_add(pc, state, state_orig);
+ }
+ state_link_add(pc, state, ele_next, ele_next_from);
+ }
+ }
+ } while ((l_iter = l_iter->next) != l_last);
+ return state;
+}
+
+/* walk around the face verts */
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list