diff options
Diffstat (limited to 'source/blender/editors/mesh/editmesh_intersect.c')
-rw-r--r-- | source/blender/editors/mesh/editmesh_intersect.c | 400 |
1 files changed, 400 insertions, 0 deletions
diff --git a/source/blender/editors/mesh/editmesh_intersect.c b/source/blender/editors/mesh/editmesh_intersect.c new file mode 100644 index 00000000000..df6776950d7 --- /dev/null +++ b/source/blender/editors/mesh/editmesh_intersect.c @@ -0,0 +1,400 @@ +/* + * ***** 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/editors/mesh/editmesh_intersect.c + * \ingroup edmesh + */ + +#include "MEM_guardedalloc.h" + +#include "DNA_object_types.h" + +#include "BLI_math.h" +#include "BLI_array.h" +#include "BLI_linklist_stack.h" + + +#include "BKE_context.h" +#include "BKE_report.h" +#include "BKE_editmesh.h" + +#include "RNA_access.h" +#include "RNA_define.h" + +#include "WM_api.h" +#include "WM_types.h" + +#include "ED_mesh.h" +#include "ED_screen.h" + +#include "intern/bmesh_private.h" + +#include "mesh_intern.h" /* own include */ + +#include "tools/bmesh_intersect.h" + + +/* -------------------------------------------------------------------- */ +/* Cut intersections into geometry */ + +/** + * Compare selected with its self. + */ +static int bm_face_isect_self(BMFace *f, void *UNUSED(user_data)) +{ + if (BM_elem_flag_test(f, BM_ELEM_SELECT)) { + return 0; + } + else { + return -1; + } +} + +/** + * Compare selected/unselected. + */ +static int bm_face_isect_pair(BMFace *f, void *UNUSED(user_data)) +{ + if (BM_elem_flag_test(f, BM_ELEM_HIDDEN)) { + return -1; + } + else if (BM_elem_flag_test(f, BM_ELEM_SELECT)) { + return 0; + } + else { + return 1; + } +} + +enum { + ISECT_SEL = 0, + ISECT_SEL_UNSEL = 1, +}; + +static EnumPropertyItem isect_mode_items[] = { + {ISECT_SEL, "SELECT", 0, "Self Intersect", + "Self intersect selected faces"}, + {ISECT_SEL_UNSEL, "SELECT_UNSELECT", 0, "Selected/Unselected", + "Intersect selected with unselected faces"}, + {0, NULL, 0, NULL, NULL} +}; + +static int edbm_intersect_exec(bContext *C, wmOperator *op) +{ + Object *obedit = CTX_data_edit_object(C); + BMEditMesh *em = BKE_editmesh_from_object(obedit); + BMesh *bm = em->bm; + const int mode = RNA_enum_get(op->ptr, "mode"); + int (*test_fn)(BMFace *, void *); + bool use_separate = RNA_boolean_get(op->ptr, "use_separate"); + const float eps = RNA_float_get(op->ptr, "threshold"); + bool use_self; + bool has_isect; + + switch (mode) { + case ISECT_SEL: + test_fn = bm_face_isect_self; + use_self = true; + break; + default: /* ISECT_SEL_UNSEL */ + test_fn = bm_face_isect_pair; + use_self = false; + break; + } + + + has_isect = BM_mesh_intersect( + bm, + em->looptris, em->tottri, + test_fn, NULL, + use_self, use_separate, + eps); + + + if (has_isect) { + BM_mesh_elem_hflag_disable_all(em->bm, BM_VERT | BM_EDGE | BM_FACE, BM_ELEM_SELECT, false); + + if (em->bm->selectmode & (SCE_SELECT_VERTEX | SCE_SELECT_EDGE)) { + BMIter iter; + BMEdge *e; + + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (BM_elem_flag_test(e, BM_ELEM_TAG)) { + BM_edge_select_set(bm, e, true); + } + } + } + + EDBM_mesh_normals_update(em); + EDBM_update_generic(em, true, true); + } + else { + BKE_report(op->reports, RPT_WARNING, "No intersections found"); + } + + return OPERATOR_FINISHED; +} + +void MESH_OT_intersect(struct wmOperatorType *ot) +{ + /* identifiers */ + ot->name = "Intersect"; + ot->description = "Cut an intersection into faces"; + ot->idname = "MESH_OT_intersect"; + + /* api callbacks */ + ot->exec = edbm_intersect_exec; + ot->poll = ED_operator_editmesh; + + /* props */ + RNA_def_enum(ot->srna, "mode", isect_mode_items, ISECT_SEL_UNSEL, "Source", ""); + RNA_def_boolean(ot->srna, "use_separate", true, "Separate", ""); + RNA_def_float(ot->srna, "threshold", 0.000001f, 0.0, 0.01, "Merge threshold", "", 0.0, 0.001); + + /* flags */ + ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO; +} + + +/* -------------------------------------------------------------------- */ +/* Face Split by Edges */ + + +/** \name Face/Edge Split + * \{ */ + +static void bm_face_split_by_edges(BMesh *bm, BMFace *f, const char hflag) +{ + BMEdge **edge_net = NULL; + BLI_array_declare(edge_net); + + const int f_index = BM_elem_index_get(f); + + BMLoop *l_iter; + BMLoop *l_first; + BMVert *v; + + BMFace **face_arr; + int face_arr_len; + + /* likely this will stay very small + * all verts pushed into this stack _must_ have their previous edges set! */ + BLI_SMALLSTACK_DECLARE(vert_stack, BMVert *); + BLI_SMALLSTACK_DECLARE(vert_stack_next, BMVert *); + + + /* collect all edges */ + l_iter = l_first = BM_FACE_FIRST_LOOP(f); + do { + BMIter iter; + BMEdge *e; + + BM_ITER_ELEM (e, &iter, l_iter->v, BM_EDGES_OF_VERT) { + if (BM_elem_flag_test(e, hflag) && + (BM_elem_index_get(e) == f_index)) + { + v = BM_edge_other_vert(e, l_iter->v); + v->e = e; + + BLI_SMALLSTACK_PUSH(vert_stack, v); + BLI_array_append(edge_net, e); + } + } + } while ((l_iter = l_iter->next) != l_first); + + + + /* now assign all */ + /* pop free values into the next stack */ + while ((v = BLI_SMALLSTACK_POP_EX(vert_stack, vert_stack_next))) { + BMIter eiter; + BMEdge *e_next; + + BM_ITER_ELEM (e_next, &eiter, v, BM_EDGES_OF_VERT) { + if (BM_elem_flag_test(e_next, hflag) && + (BM_elem_index_get(e_next) == -1)) + { + BMVert *v_next; + v_next = BM_edge_other_vert(e_next, v); + BM_elem_index_set(e_next, f_index); + BLI_SMALLSTACK_PUSH(vert_stack_next, v_next); + BLI_array_append(edge_net, e_next); + } + } + + if (BLI_SMALLSTACK_IS_EMPTY(vert_stack)) { + BLI_SMALLSTACK_SWAP(vert_stack, vert_stack_next); + } + } + + BM_face_split_edgenet(bm, f, edge_net, BLI_array_count(edge_net), &face_arr, &face_arr_len); + BLI_array_free(edge_net); + + if (face_arr_len) { + int i; + for (i = 0; i < face_arr_len; i++) { + BM_face_select_set(bm, face_arr[i], true); + BM_elem_flag_disable(face_arr[i], hflag); + } + } + + if (face_arr) { + MEM_freeN(face_arr); + } +} + +static int edbm_face_split_by_edges_exec(bContext *C, wmOperator *UNUSED(op)) +{ + Object *obedit = CTX_data_edit_object(C); + BMEditMesh *em = BKE_editmesh_from_object(obedit); + BMesh *bm = em->bm; + const char hflag = BM_ELEM_TAG; + + BMVert *v; + BMEdge *e; + BMFace *f; + BMIter iter; + + BLI_SMALLSTACK_DECLARE(loop_stack, BMLoop *); + + BM_ITER_MESH (v, &iter, bm, BM_VERTS_OF_MESH) { + BM_elem_flag_disable(v, hflag); + } + + /* edge index is set to -1 then used to assosiate them with faces */ + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (BM_elem_flag_test(e, BM_ELEM_SELECT) && BM_edge_is_wire(e)) { + BM_elem_flag_enable(e, hflag); + + BM_elem_flag_enable(e->v1, hflag); + BM_elem_flag_enable(e->v2, hflag); + + } + else { + BM_elem_flag_disable(e, hflag); + } + BM_elem_index_set(e, -1); /* set_dirty */ + } + + BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) { + if (BM_elem_flag_test(f, BM_ELEM_SELECT)) { + BM_elem_flag_enable(f, hflag); + } + else { + BM_elem_flag_disable(f, hflag); + } + } + + BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) { + if (BM_elem_flag_test(e, hflag)) { + BMIter viter; + BM_ITER_ELEM (v, &viter, e, BM_VERTS_OF_EDGE) { + BMIter liter; + BMLoop *l; + + unsigned int loop_stack_len; + BMLoop *l_best = NULL; + + BLI_assert(BLI_SMALLSTACK_IS_EMPTY(loop_stack)); + loop_stack_len = 0; + + BM_ITER_ELEM (l, &liter, v, BM_LOOPS_OF_VERT) { + if (BM_elem_flag_test(l->f, hflag)) { + BLI_SMALLSTACK_PUSH(loop_stack, l); + loop_stack_len++; + } + } + + if (loop_stack_len == 0) { + /* pass */ + } + else if (loop_stack_len == 1) { + l_best = BLI_SMALLSTACK_POP(loop_stack); + } + else { + /* complicated case, match the edge with a face-loop */ + + BMVert *v_other = BM_edge_other_vert(e, v); + float e_dir[3]; + + /* we wan't closest to zero */ + float dot_best = FLT_MAX; + + sub_v3_v3v3(e_dir, v_other->co, v->co); + normalize_v3(e_dir); + + while ((l = BLI_SMALLSTACK_POP(loop_stack))) { + float dot_test; + + /* Check dot first to save on expensive angle-comparison. + * ideal case is 90d difference == 0.0 dot */ + dot_test = fabsf(dot_v3v3(e_dir, l->f->no)); + if (dot_test < dot_best) { + + /* check we're in the correct corner (works with convex loops too) */ + if (angle_signed_on_axis_v3v3v3_v3(l->prev->v->co, l->v->co, v_other->co, l->f->no) < + angle_signed_on_axis_v3v3v3_v3(l->prev->v->co, l->v->co, l->next->v->co, l->f->no)) + { + dot_best = dot_test; + l_best = l; + } + } + } + } + + if (l_best) { + BM_elem_index_set(e, BM_elem_index_get(l_best->f)); /* set_dirty */ + } + } + } + } + + bm->elem_index_dirty |= BM_EDGE; + + + BM_ITER_MESH (f, &iter, bm, BM_FACES_OF_MESH) { + if (BM_elem_flag_test(f, hflag)) { + bm_face_split_by_edges(bm, f, hflag); + } + } + + EDBM_mesh_normals_update(em); + EDBM_update_generic(em, true, true); + + return OPERATOR_FINISHED; +} + + +void MESH_OT_face_split_by_edges(struct wmOperatorType *ot) +{ + /* identifiers */ + ot->name = "Split by Edges"; + ot->description = "Split faces by loose edges"; + ot->idname = "MESH_OT_face_split_by_edges"; + + /* api callbacks */ + ot->exec = edbm_face_split_by_edges_exec; + ot->poll = ED_operator_editmesh; + + /* flags */ + ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO; +} + +/** \} */ |