[Bf-blender-cvs] [b9ebf44] master: BMesh: intersect tool
Campbell Barton
noreply at git.blender.org
Mon Aug 18 09:09:42 CEST 2014
Commit: b9ebf441396ed58027dd13390a84ef268386324b
Author: Campbell Barton
Date: Wed Mar 19 15:28:38 2014 +1100
Branches: master
https://developer.blender.org/rBb9ebf441396ed58027dd13390a84ef268386324b
BMesh: intersect tool
Modeling tool to cut intersections into geometry (like boolean, without calculating inside/outside).
Faces are split along intersections, leaving new edges selected.
Access from Face menu.
===================================================================
M release/scripts/startup/bl_ui/space_view3d.py
M source/blender/bmesh/CMakeLists.txt
A source/blender/bmesh/tools/bmesh_intersect.c
A source/blender/bmesh/tools/bmesh_intersect.h
M source/blender/editors/mesh/editmesh_intersect.c
M source/blender/editors/mesh/mesh_intern.h
M source/blender/editors/mesh/mesh_ops.c
===================================================================
diff --git a/release/scripts/startup/bl_ui/space_view3d.py b/release/scripts/startup/bl_ui/space_view3d.py
index eb2aaf2..b748699 100644
--- a/release/scripts/startup/bl_ui/space_view3d.py
+++ b/release/scripts/startup/bl_ui/space_view3d.py
@@ -2266,6 +2266,7 @@ class VIEW3D_MT_edit_mesh_faces(Menu):
layout.operator("mesh.inset")
layout.operator("mesh.bevel").vertex_only = False
layout.operator("mesh.solidify")
+ layout.operator("mesh.intersect")
layout.operator("mesh.wireframe")
layout.separator()
diff --git a/source/blender/bmesh/CMakeLists.txt b/source/blender/bmesh/CMakeLists.txt
index 2cd256e..a43e835 100644
--- a/source/blender/bmesh/CMakeLists.txt
+++ b/source/blender/bmesh/CMakeLists.txt
@@ -136,6 +136,8 @@ set(SRC
tools/bmesh_edgenet.h
tools/bmesh_edgesplit.c
tools/bmesh_edgesplit.h
+ tools/bmesh_intersect.c
+ tools/bmesh_intersect.h
tools/bmesh_path.c
tools/bmesh_path.h
tools/bmesh_triangulate.c
diff --git a/source/blender/bmesh/tools/bmesh_intersect.c b/source/blender/bmesh/tools/bmesh_intersect.c
new file mode 100644
index 0000000..173ae95
--- /dev/null
+++ b/source/blender/bmesh/tools/bmesh_intersect.c
@@ -0,0 +1,1294 @@
+/*
+ * ***** 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.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/bmesh/tools/bmesh_intersect.c
+ * \ingroup bmesh
+ *
+ * Cut meshes along intersections.
+ *
+ * Boolean-like modeling operation (without calculating inside/outside).
+ *
+ * Supported:
+ * - Concave faces.
+ * - Non-planare faces.
+ * - Custom-data (UV's etc).
+ *
+ * Unsupported:
+ * - Intersecting between different meshes.
+ * - No support for holes (cutting a hole into a single face).
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_math.h"
+#include "BLI_utildefines.h"
+#include "BLI_memarena.h"
+#include "BLI_alloca.h"
+#include "BLI_sort_utils.h"
+
+#include "BLI_linklist_stack.h"
+#include "BLI_stackdefines.h"
+#include "BLI_array.h"
+
+#include "BLI_kdopbvh.h"
+
+#include "bmesh.h"
+#include "bmesh_intersect.h" /* own include */
+
+#include "tools/bmesh_edgesplit.h"
+
+#include "BLI_strict_flags.h"
+
+/*
+ * Some of these depend on each other:
+ */
+
+/* splice verts into existing edges */
+#define USE_SPLICE
+/* split faces by intersecting edges */
+#define USE_NET
+/* split resulting edges */
+#define USE_SEPARATE
+/* remove verts created by intersecting triangles */
+#define USE_DISSOLVE
+
+/* strict asserts that may fail in practice (handy for debugging cases which should succeed) */
+// #define USE_PARANOID
+/* use accelerated overlap check */
+#define USE_BVH
+
+
+static void tri_v3_scale(
+ float v1[3], float v2[3], float v3[3],
+ const float t)
+{
+ float p[3];
+
+ mid_v3_v3v3v3(p, v1, v2, v3);
+
+ interp_v3_v3v3(v1, p, v1, t);
+ interp_v3_v3v3(v2, p, v2, t);
+ interp_v3_v3v3(v3, p, v3, t);
+}
+
+#ifdef USE_DISSOLVE
+/* other edge when a vert only has 2 edges */
+static BMEdge *bm_vert_other_edge(BMVert *v, BMEdge *e)
+{
+ BLI_assert(BM_vert_is_edge_pair(v));
+ BLI_assert(BM_vert_in_edge(e, v));
+
+ if (v->e != e) {
+ return v->e;
+ }
+ else {
+ return BM_DISK_EDGE_NEXT(v->e, v);
+ }
+}
+#endif
+
+enum ISectType {
+ IX_NONE = -1,
+ IX_EDGE_TRI_EDGE0,
+ IX_EDGE_TRI_EDGE1,
+ IX_EDGE_TRI_EDGE2,
+ IX_EDGE_TRI,
+ IX_TOT,
+};
+
+struct ISectEpsilon {
+ float eps, eps_sq;
+ float eps2x, eps2x_sq;
+ float eps_margin, eps_margin_sq;
+};
+
+struct ISectState {
+ BMesh *bm;
+ GHash *edgetri_cache; /* int[4]: BMVert */
+ GHash *edge_verts; /* BMEdge: LinkList(of verts), new and original edges */
+ GHash *face_edges; /* BMFace-index: LinkList(of edges), only original faces */
+ GSet *wire_edges; /* BMEdge (could use tags instead) */
+ LinkNode *vert_dissolve; /* BMVert's */
+
+ MemArena *mem_arena;
+
+ struct ISectEpsilon epsilon;
+};
+
+/**
+ * Store as value in GHash so we can get list-length without counting every time.
+ * Also means we don't need to update the GHash value each time.
+ */
+struct LinkBase {
+ LinkNode *list;
+ unsigned int list_len;
+};
+
+static bool ghash_insert_link(
+ GHash *gh, void *key, void *val, bool use_test,
+ MemArena *mem_arena)
+{
+ struct LinkBase *ls_base;
+ LinkNode *ls;
+
+ ls_base = BLI_ghash_lookup(gh, key);
+
+ if (ls_base) {
+ if (use_test && (BLI_linklist_index(ls_base->list, key) != -1)) {
+ return false;
+ }
+ }
+ else {
+ ls_base = BLI_memarena_alloc(mem_arena, sizeof(*ls_base));
+ ls_base->list = NULL;
+ ls_base->list_len = 0;
+ BLI_ghash_insert(gh, key, ls_base);
+ }
+
+ ls = BLI_memarena_alloc(mem_arena, sizeof(*ls));
+ ls->next = ls_base->list;
+ ls->link = val;
+ ls_base->list = ls;
+ ls_base->list_len += 1;
+
+ return true;
+}
+
+struct vert_sort_t {
+ float val;
+ BMVert *v;
+};
+
+#ifdef USE_SPLICE
+static void edge_verts_sort(BMEdge *e, struct LinkBase *v_ls_base)
+{
+ /* not optimal but list will be typically < 5 */
+ const float *co = e->v1->co;
+ unsigned int i;
+ struct vert_sort_t *vert_sort = BLI_array_alloca(vert_sort, v_ls_base->list_len);
+ LinkNode *node;
+
+ BLI_assert(v_ls_base->list_len > 1);
+
+ for (i = 0, node = v_ls_base->list; i < v_ls_base->list_len; i++, node = node->next) {
+ BMVert *v = node->link;
+ BLI_assert(v->head.htype == BM_VERT);
+ vert_sort[i].val = len_squared_v3v3(co, v->co);
+ vert_sort[i].v = v;
+ }
+
+ qsort(vert_sort, v_ls_base->list_len, sizeof(*vert_sort), BLI_sortutil_cmp_float_reverse);
+
+ for (i = 0, node = v_ls_base->list; i < v_ls_base->list_len; i++, node = node->next) {
+ node->link = vert_sort[i].v;
+ }
+}
+#endif
+
+static void edge_verts_add(
+ struct ISectState *s,
+ BMEdge *e,
+ BMVert *v,
+ const bool use_test
+ )
+{
+ BLI_assert(e->head.htype == BM_EDGE);
+ BLI_assert(v->head.htype == BM_VERT);
+ ghash_insert_link(s->edge_verts, (void *)e, v, use_test, s->mem_arena);
+}
+
+static void face_edges_add(
+ struct ISectState *s,
+ const int f_index,
+ BMEdge *e,
+ const bool use_test)
+{
+ void *f_index_key = SET_INT_IN_POINTER(f_index);
+ BLI_assert(e->head.htype == BM_EDGE);
+ BLI_assert(BM_edge_in_face(e, s->bm->ftable[f_index]) == false);
+ BLI_assert(BM_elem_index_get(s->bm->ftable[f_index]) == f_index);
+
+ ghash_insert_link(s->face_edges, f_index_key, e, use_test, s->mem_arena);
+}
+
+#ifdef USE_NET
+static void face_edges_split(
+ BMesh *bm,
+ BMFace *f,
+ struct LinkBase *e_ls_base)
+{
+ unsigned int i;
+ BMEdge **edge_arr = BLI_array_alloca(edge_arr, e_ls_base->list_len);
+ LinkNode *node;
+ BLI_assert(f->head.htype == BM_FACE);
+
+ for (i = 0, node = e_ls_base->list; i < e_ls_base->list_len; i++, node = node->next) {
+ edge_arr[i] = node->link;
+ }
+ BLI_assert(node == NULL);
+
+#ifdef USE_DUMP
+ printf("# %s: %d %u\n", __func__, BM_elem_index_get(f), e_ls_base->list_len);
+#endif
+
+ BM_face_split_edgenet(bm, f, edge_arr, (int)e_ls_base->list_len, NULL, NULL);
+}
+#endif
+
+#ifdef USE_DISSOLVE
+static void vert_dissolve_add(
+ struct ISectState *s,
+ BMVert *v)
+{
+ BLI_assert(v->head.htype == BM_VERT);
+ BLI_assert(!BM_elem_flag_test(v, BM_ELEM_TAG));
+ BLI_assert(BLI_linklist_index(s->vert_dissolve, v) == -1);
+
+ BM_elem_flag_enable(v, BM_ELEM_TAG);
+ BLI_linklist_prepend_arena(&s->vert_dissolve, v, s->mem_arena);
+}
+#endif
+
+static enum ISectType intersect_line_tri(
+ const float p0[3], const float p1[3],
+ const float *t_cos[3], const float t_nor[3],
+ float r_ix[3],
+ const struct ISectEpsilon *e)
+{
+ float p_dir[3];
+ unsigned int i_t0;
+ float fac;
+
+ sub_v3_v3v3(p_dir, p0, p1);
+ normalize_v3(p_dir);
+
+ for (i_t0 = 0; i_t0 < 3; i_t0++) {
+ const unsigned int i_t1 = (i_t0 + 1) % 3;
+ float te_dir[3];
+
+ sub_v3_v3v3(te_dir, t_cos[i_t0], t_cos[i_t1]);
+ normalize_v3(te_dir);
+ if (fabsf(dot_v3v3(p_dir, te_dir)) >= 1.0f - e->eps) {
+ /* co-linear */
+ }
+ else {
+ float ix_pair[2][3];
+ int ix_pair_type;
+
+ ix_pair_type = isect_line_line_epsilon_v3(p0, p1, t_cos[i_t0], t_cos[i_t1], ix_pair[0], ix_pair[1], 0.0f);
+
+ if (ix_pair_type != 0) {
+ if (ix_pair_type == 1) {
+ copy_v3_v3(ix_pair[1], ix_pair[0]);
+ }
+
+ if ((ix_pair_type == 1) ||
+ (len_squared_v3v3(ix_pair[0], ix_pair[1]) <= e->eps_margin_sq))
+ {
+ fac = line_point_factor_v3(ix_pair[1], t_cos[i_t0], t_cos[i_t1]);
+ if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
+ fac = line_point_factor_v3(ix_pair[0], p0, p1);
+ if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
+ copy_v3_v3(r_ix, ix_pair[0]);
+ return (IX_EDGE_TRI_EDGE0 + i_t0);
+ }
+ }
+ }
+ }
+ }
+ }
+
+ /* check ray isn't planar with tri */
+ if (fabsf(dot_v3v3(p_dir, t_nor)) >= e->eps) {
+ if (isect_line_tri_epsilon_v3(p0, p1, t_cos[0], t_cos[1], t_cos[2], &fac, NULL, 0.0f)) {
+ if ((fac >= e->eps_margin) && (fac <= 1.0f - e->eps_margin)) {
+ interp_v3_v3v3(r_ix, p0, p1, fac);
+ if (min_fff(len_squared_v3v3(t_cos[0], r_ix),
+ len_squared_v3v3(t_cos[1], r_ix),
+ len_squared_v3v3(t_cos[2], r_ix)) >= e->eps_margin_sq)
+ {
+ return IX_EDGE_TRI;
+ }
+ }
+ }
+ }
+
+ /* r_ix may be unset */
+ return IX_NONE;
+}
+
+static BMVert *bm_isect_edge_tri(
+ struct ISectState *s,
+ BMVert *e_v0, BMVert *e_v1,
+ BMVert *t[3], const int t_index,
+ const float *t_cos[3], const float t_nor[3],
+ enum ISectT
@@ Diff output truncated at 10240 characters. @@
More information about the Bf-blender-cvs
mailing list