[Bf-blender-cvs] SVN commit: /data/svn/bf-blender [58118] branches/ soc-2013-meshdata_transfer/source/blender/bmesh/operators/bmo_connect_pair. c: repair bad merge
Campbell Barton
ideasman42 at gmail.com
Tue Jul 9 12:15:33 CEST 2013
Revision: 58118
http://projects.blender.org/scm/viewvc.php?view=rev&root=bf-blender&revision=58118
Author: campbellbarton
Date: 2013-07-09 10:15:33 +0000 (Tue, 09 Jul 2013)
Log Message:
-----------
repair bad merge
Added Paths:
-----------
branches/soc-2013-meshdata_transfer/source/blender/bmesh/operators/bmo_connect_pair.c
Copied: branches/soc-2013-meshdata_transfer/source/blender/bmesh/operators/bmo_connect_pair.c (from rev 58117, trunk/blender/source/blender/bmesh/operators/bmo_connect_pair.c)
===================================================================
--- branches/soc-2013-meshdata_transfer/source/blender/bmesh/operators/bmo_connect_pair.c (rev 0)
+++ branches/soc-2013-meshdata_transfer/source/blender/bmesh/operators/bmo_connect_pair.c 2013-07-09 10:15:33 UTC (rev 58118)
@@ -0,0 +1,548 @@
+/*
+ * ***** 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_from == NULL) {
+ printf("from NULL\n");
+ }
+ else if (ele_from->head.htype == BM_EDGE) {
+ printf("from edge %d\n", BM_elem_index_get(ele_from));
+ }
+ else if (ele_from->head.htype == BM_FACE) {
+ printf("from face %d\n", BM_elem_index_get(ele_from));
+ }
+ 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 */
+static PathLinkState *state_step__face_verts(PathContext *pc,
+ PathLinkState *state, const PathLinkState *state_orig,
+ BMLoop *l_iter, BMLoop *l_last)
+{
+ do {
+ if (state_isect_co_exact(pc, l_iter->v->co)) {
+ BMElem *ele_next = (BMElem *)l_iter->v;
+ 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;
+}
+
+static bool state_step(PathContext *pc, PathLinkState *state)
+{
+ PathLinkState state_orig = *state;
+ BMElem *ele = state->link_last->ele;
+ const void *ele_from = state->link_last->ele_from;
+
+ if (ele->head.htype == BM_EDGE) {
+ BMEdge *e = (BMEdge *)ele;
+
+ BMIter liter;
+ BMLoop *l_start;
+
+ BM_ITER_ELEM (l_start, &liter, e, BM_LOOPS_OF_EDGE) {
+ if (l_start->f != ele_from) {
+ /* very similar to block below */
+ if (BM_vert_in_face(l_start->f, pc->v_b)) {
+ if (state_orig.link_last != state->link_last) {
+ state = state_dupe_add(pc, state, &state_orig);
+ }
+
+ state_link_add(pc, state, (BMElem *)pc->v_b, (BMElem *)l_start->f);
+ }
+ else {
+ state = state_step__face_edges(pc, state, &state_orig,
+ l_start->next, l_start);
+ state = state_step__face_verts(pc, state, &state_orig,
+ l_start->next->next, l_start);
+ }
+ }
+ }
+ }
+ else if (ele->head.htype == BM_VERT) {
+ BMVert *v = (BMVert *)ele;
+
+ /* vert loops */
+ {
+ BMIter liter;
+ BMLoop *l_start;
+
+ BM_ITER_ELEM (l_start, &liter, v, BM_LOOPS_OF_VERT) {
+ if (l_start->f != ele_from) {
+ /* very similar to block above */
+ if (BM_vert_in_face(l_start->f, pc->v_b)) {
+ BMElem *ele_next = (BMElem *)pc->v_b;
+ BMElem *ele_next_from = (BMElem *)l_start->f;
+
+ 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);
+ }
+ else {
+ state = state_step__face_edges(pc, state, &state_orig,
+ l_start->next, l_start->prev);
+ if (l_start->f->len > 3) {
+ /* adjacent verts are handled in state_step__vert_edges */
+ state = state_step__face_verts(pc, state, &state_orig,
+ l_start->next->next, l_start->prev);
+ }
+ }
+ }
+ }
+ }
+
+ /* vert edges */
+ {
+ BMIter eiter;
+ BMEdge *e;
+ BM_ITER_ELEM (e, &eiter, v, BM_EDGES_OF_VERT) {
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list