Add BMesh and WM symmetrize operators
authorNicholas Bishop <nicholasbishop@gmail.com>
Mon, 15 Oct 2012 23:50:09 +0000 (23:50 +0000)
committerNicholas Bishop <nicholasbishop@gmail.com>
Mon, 15 Oct 2012 23:50:09 +0000 (23:50 +0000)
* The symmetrize operation makes the input mesh elements symmetrical,
  but unlike mirroring it only copies in one direction. The edges and
  faces that cross the plane of symmetry are split as needed to
  enforce symmetry.

* The symmetrize operator can be controlled with the "direction"
  property, which combines the choices of symmetry plane and
  positive-negative/negative-positive. The enum for this is
  BMO_SymmDirection.

* Added menu items in the top-level Mesh menu and the WKEY specials
  menu.

* Documentation:
  http://wiki.blender.org/index.php/User:Nicholasbishop/Symmetrize

* Reviewed by Brecht:
  https://codereview.appspot.com/6618059

release/scripts/startup/bl_ui/space_view3d.py
source/blender/bmesh/CMakeLists.txt
source/blender/bmesh/intern/bmesh_opdefines.c
source/blender/bmesh/intern/bmesh_operator_api.h
source/blender/bmesh/intern/bmesh_operators_private.h
source/blender/bmesh/operators/bmo_symmetrize.c [new file with mode: 0644]
source/blender/editors/mesh/editmesh_tools.c
source/blender/editors/mesh/mesh_intern.h
source/blender/editors/mesh/mesh_ops.c

index f0ee965aa5462d47843a2e00f09eac62fb817a10..e96bc696087a49cc0940525a28890c6b5baf2c97 100644 (file)
@@ -1668,7 +1668,7 @@ class VIEW3D_MT_edit_mesh(Menu):
         layout.menu("VIEW3D_MT_uv_map", text="UV Unwrap...")
 
         layout.separator()
-
+        layout.operator("mesh.symmetrize")
         layout.operator("view3d.edit_mesh_extrude_move_normal", text="Extrude Region")
         layout.operator("view3d.edit_mesh_extrude_individual_move", text="Extrude Individual")
         layout.operator("mesh.duplicate_move")
@@ -1719,6 +1719,7 @@ class VIEW3D_MT_edit_mesh_specials(Menu):
         layout.operator("mesh.shape_propagate_to_all")
         layout.operator("mesh.select_vertex_path")
         layout.operator("mesh.sort_elements")
+        layout.operator("mesh.symmetrize")
 
 
 class VIEW3D_MT_edit_mesh_select_mode(Menu):
index 4bce7a6ff51c6b7e627695388c7d712225d11a40..c23eb60561470b294963941507b47b2402b58388 100644 (file)
@@ -52,6 +52,7 @@ set(SRC
        operators/bmo_mirror.c
        operators/bmo_primitive.c
        operators/bmo_removedoubles.c
+       operators/bmo_symmetrize.c
        operators/bmo_subdivide.c
        operators/bmo_subdivide.h
        operators/bmo_triangulate.c
index 362157ad71b83d1077bff56bb9fabdff0b2dee20..f50de0d6ee4c9d2417962175ea2e30223af70218 100644 (file)
@@ -1182,6 +1182,29 @@ static BMOpDefine bmo_convex_hull_def = {
        0
 };
 
+/*
+ * Symmetrize
+ *
+ * Mekes the mesh elements in the "input" slot symmetrical. Unlike
+ * normal mirroring, it only copies in one direction, as specified by
+ * the "direction" slot. The edges and faces that cross the plane of
+ * symmetry are split as needed to enforce symmetry.
+ *
+ * All new vertices, edges, and faces are added to the "geomout" slot.
+ */
+static BMOpDefine bmo_symmetrize_def = {
+       "symmetrize",
+       {{BMO_OP_SLOT_ELEMENT_BUF, "input"},
+        {BMO_OP_SLOT_INT, "direction"},
+
+        /* Outputs */
+        {BMO_OP_SLOT_ELEMENT_BUF, "geomout"},
+
+        {0} /* null-terminating sentinel */},
+       bmo_symmetrize_exec,
+       0
+};
+
 BMOpDefine *opdefines[] = {
        &bmo_automerge_def,
        &bmo_average_vert_facedata_def,
@@ -1246,6 +1269,7 @@ BMOpDefine *opdefines[] = {
        &bmo_split_def,
        &bmo_split_edges_def,
        &bmo_subdivide_edges_def,
+       &bmo_symmetrize_def,
        &bmo_transform_def,
        &bmo_translate_def,
        &bmo_triangle_fill_def,
index 0674103162c3ee579950a66a83486ec1922de509..a2f4cdc8c6a2608dcbe844ff172a92b67ce80a9f 100644 (file)
@@ -266,6 +266,16 @@ enum {
        DEL_ONLYTAGGED
 };
 
+typedef enum {
+       BMO_SYMMETRIZE_NEGATIVE_X,
+       BMO_SYMMETRIZE_NEGATIVE_Y,
+       BMO_SYMMETRIZE_NEGATIVE_Z,
+
+       BMO_SYMMETRIZE_POSITIVE_X,
+       BMO_SYMMETRIZE_POSITIVE_Y,
+       BMO_SYMMETRIZE_POSITIVE_Z,
+} BMO_SymmDirection;
+
 void BMO_op_flag_enable(BMesh *bm, BMOperator *op, const int op_flag);
 void BMO_op_flag_disable(BMesh *bm, BMOperator *op, const int op_flag);
 
index dc1bdaa468902729007c1bd9c7d2025396f9af14..fa239bb6ceb36ba9ad7c05d5099180364ca18453 100644 (file)
@@ -96,6 +96,7 @@ void bmo_spin_exec(BMesh *bm, BMOperator *op);
 void bmo_split_edges_exec(BMesh *bm, BMOperator *op);
 void bmo_split_exec(BMesh *bm, BMOperator *op);
 void bmo_subdivide_edges_exec(BMesh *bm, BMOperator *op);
+void bmo_symmetrize_exec(BMesh *bm, BMOperator *op);
 void bmo_transform_exec(BMesh *bm, BMOperator *op);
 void bmo_translate_exec(BMesh *bm, BMOperator *op);
 void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op);
diff --git a/source/blender/bmesh/operators/bmo_symmetrize.c b/source/blender/bmesh/operators/bmo_symmetrize.c
new file mode 100644 (file)
index 0000000..2a1cc80
--- /dev/null
@@ -0,0 +1,663 @@
+/*
+ * ***** 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): Nicholas Bishop
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+#include "MEM_guardedalloc.h"
+
+#include "BLI_array.h"
+#include "BLI_math.h"
+#include "BLI_utildefines.h"
+
+#include "bmesh.h"
+#include "intern/bmesh_operators_private.h"
+
+enum {
+       SYMM_OUTPUT_GEOM = (1 << 0)
+};
+
+/* Note: don't think there's much need to make these user-adjustable? */
+#define SYMM_AXIS_THRESHOLD 0.00002f
+#define SYMM_VERT_THRESHOLD 0.00002f
+
+typedef enum {
+       /* Coordinate lies on the side being copied from */
+       SYMM_SIDE_KEEP,
+       /* Coordinate lies on the side being copied from and within the
+        * axis threshold */
+       SYMM_SIDE_AXIS,
+       /* Coordinate lies on the side being copied to */
+       SYMM_SIDE_KILL
+} SymmSide;
+
+typedef struct {
+       BMesh *bm;
+       BMOperator *op;
+
+       int axis;
+       BMO_SymmDirection direction;
+
+       /* Maps from input vertices to their mirrors. If the vertex
+        * doesn't have a mirror, it's not in this map. If the vertex is
+        * within the axis threshold, it's mapped to itself. */
+       GHash *vert_symm_map;
+
+       /* Edges that cross the symmetry plane and are asymmetric get
+        * split. This map goes from input edges to output vertices. If an
+        * edge is not split, it's not in this map. */
+       GHash *edge_split_map;
+} Symm;
+
+/* Return which side the coordinate lies on */
+static SymmSide symm_co_side(const Symm *symm,
+                                                        const float *co)
+{
+       float comp = co[symm->axis];
+       if (ELEM3(symm->direction,
+                         BMO_SYMMETRIZE_NEGATIVE_X,
+                         BMO_SYMMETRIZE_NEGATIVE_Y,
+                         BMO_SYMMETRIZE_NEGATIVE_Z))
+       {
+               comp = -comp;
+       }
+
+       if (comp >= 0) {
+               if (comp < SYMM_AXIS_THRESHOLD)
+                       return SYMM_SIDE_AXIS;
+               else
+                       return SYMM_SIDE_KEEP;
+       }
+       else
+               return SYMM_SIDE_KILL;
+}
+
+/* Output vertices and the vert_map array */
+static void symm_verts_mirror(Symm *symm)
+{
+       BMOIter oiter;
+       BMVert *src_v, *dst_v;
+
+       symm->vert_symm_map = BLI_ghash_ptr_new(AT);
+
+       BMO_ITER (src_v, &oiter, symm->bm, symm->op, "input", BM_VERT) {
+               SymmSide side = symm_co_side(symm, src_v->co);
+               float co[3];
+
+               switch (side) {
+                       case SYMM_SIDE_KEEP:
+                               /* The vertex is outside the axis area; output its mirror */
+                               copy_v3_v3(co, src_v->co);
+                               co[symm->axis] = -co[symm->axis];
+
+                               dst_v = BM_vert_create(symm->bm, co, src_v);
+                               BMO_elem_flag_enable(symm->bm, dst_v, SYMM_OUTPUT_GEOM);
+                               BLI_ghash_insert(symm->vert_symm_map, src_v, dst_v);
+                               break;
+
+                       case SYMM_SIDE_AXIS:
+                               /* The vertex is within the axis area, snap to center */
+                               src_v->co[symm->axis] = 0;
+                               /* Vertex isn't copied, map to itself */
+                               BLI_ghash_insert(symm->vert_symm_map, src_v, src_v);
+                               break;
+
+                       case SYMM_SIDE_KILL:
+                               /* The vertex does not lie in the half-space being
+                                * copied from, nothing to do */
+                               break;
+               }
+       }
+}
+
+static int symm_edge_crosses_axis(const Symm *symm, const BMEdge *e)
+{
+       const int sides[2] = {symm_co_side(symm, e->v1->co),
+                                                 symm_co_side(symm, e->v2->co)};
+
+       return ((sides[0] != SYMM_SIDE_AXIS) &&
+                       (sides[1] != SYMM_SIDE_AXIS) &&
+                       (sides[0] != sides[1]));
+}
+
+/* Output edge split vertices for asymmetric edges and the edge_splits
+ * mapping array */
+static void symm_split_asymmetric_edges(Symm *symm)
+{
+       BMOIter oiter;
+       BMEdge *e;
+
+       symm->edge_split_map = BLI_ghash_ptr_new(AT);
+
+       BMO_ITER (e, &oiter, symm->bm, symm->op, "input", BM_EDGE) {
+               float flipped[3];
+
+               copy_v3_v3(flipped, e->v1->co);
+               flipped[symm->axis] = -flipped[symm->axis];
+
+               if (symm_edge_crosses_axis(symm, e) &&
+                       (!compare_v3v3(e->v2->co, flipped, SYMM_VERT_THRESHOLD)))
+               {
+                       /* Endpoints lie on opposite sides and are asymmetric */
+
+                       BMVert *v;
+                       float lambda = 0, edge_dir[3], co[3];
+                       float plane_co[3][3][3] = {
+                               /* axis == 0 */
+                               {{0, 0, 0}, {0, 1, 0}, {0, 0, 1}},
+                               /* axis == 1 */
+                               {{0, 0, 0}, {1, 0, 0}, {0, 0, 1}},
+                               /* axis == 2 */
+                               {{0, 0, 0}, {1, 0, 0}, {0, 1, 0}},
+                       };
+                       int r;
+
+                       /* Find intersection of edge with symmetry plane */
+                       sub_v3_v3v3(edge_dir, e->v2->co, e->v1->co);
+                       normalize_v3(edge_dir);
+                       r = isect_ray_plane_v3(e->v1->co,
+                                                                  edge_dir,
+                                                                  plane_co[symm->axis][0],
+                                                                  plane_co[symm->axis][1],
+                                                                  plane_co[symm->axis][2],
+                                                                  &lambda, TRUE);
+                       BLI_assert(r);
+
+                       madd_v3_v3v3fl(co, e->v1->co, edge_dir, lambda);
+                       co[symm->axis] = 0;
+
+                       /* Edge is asymmetric, split it with a new vertex */
+                       v = BM_vert_create(symm->bm, co, e->v1);
+                       BMO_elem_flag_enable(symm->bm, v, SYMM_OUTPUT_GEOM);
+                       BLI_ghash_insert(symm->edge_split_map, e, v);
+               }
+       }
+}
+
+static void symm_mirror_edges(Symm *symm)
+{
+       BMOIter oiter;
+       BMEdge *e;
+
+       BMO_ITER (e, &oiter, symm->bm, symm->op, "input", BM_EDGE) {
+               BMVert *v1 = NULL, *v2 = NULL;
+               BMEdge *e_new;
+
+               v1 = BLI_ghash_lookup(symm->vert_symm_map, e->v1);
+               v2 = BLI_ghash_lookup(symm->vert_symm_map, e->v2);
+
+               if (v1 && v2) {
+                       e_new = BM_edge_create(symm->bm, v1, v2, e, TRUE);
+                       BMO_elem_flag_enable(symm->bm, e_new, SYMM_OUTPUT_GEOM);
+               }
+               else if (v1 || v2) {
+                       if (BLI_ghash_haskey(symm->edge_split_map, e)) {
+                               BMVert *v_split = BLI_ghash_lookup(symm->edge_split_map, e);
+
+                               /* Output the keep side of the split edge */
+                               if (!v1) {
+                                       e_new = BM_edge_create(symm->bm, v_split, e->v2, e, TRUE);
+                                       BMO_elem_flag_enable(symm->bm, e_new, SYMM_OUTPUT_GEOM);
+                                       v1 = v_split;
+                               }
+                               else {
+                                       e_new = BM_edge_create(symm->bm, e->v1, v_split, e, TRUE);
+                                       BMO_elem_flag_enable(symm->bm, e_new, SYMM_OUTPUT_GEOM);
+                                       v2 = v_split;
+                               }
+
+                               /* Output the kill side of the split edge */
+                               e_new = BM_edge_create(symm->bm, v1, v2, e, TRUE);
+                               BMO_elem_flag_enable(symm->bm, e_new, SYMM_OUTPUT_GEOM);
+                       }
+               }
+       }
+}
+
+/****************************** SymmPoly ******************************/
+
+typedef struct {
+       /* Indices into the source mvert array (or -1 if not in that array) */
+       BMVert **src_verts;
+       /* Indices into the destination mvert array, these are vertices
+        * created by an edge split (-1 for vertices not created by edge
+        * split) */
+       BMVert **edge_verts;
+
+       /* Number of vertices in the polygon */
+       int len;
+
+       /* True only if none of the polygon's edges were split */
+       int already_symmetric;
+} SymmPoly;
+
+static void symm_poly_with_splits(const Symm *symm,
+                                                                 BMFace *f,
+                                                                 SymmPoly *out)
+{
+       BMIter iter;
+       BMLoop *l;
+       int i;
+
+       /* Count vertices and check for edge splits */
+       out->len = f->len;
+       out->already_symmetric = TRUE;
+       BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
+               if (BLI_ghash_haskey(symm->edge_split_map, l->e)) {
+                       out->len++;
+                       out->already_symmetric = FALSE;
+               }
+       }
+
+       i = 0;
+       BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
+               BMVert *split = BLI_ghash_lookup(symm->edge_split_map, l->e);
+
+               out->src_verts[i] = l->v;
+               out->edge_verts[i] = NULL;
+               i++;
+
+               if (split) {
+                       out->src_verts[i] = NULL;
+                       out->edge_verts[i] = split;
+                       i++;
+               }
+       }
+}
+
+static const float *symm_poly_co(const SymmPoly *sp, int v)
+{
+       if (sp->src_verts[v])
+               return sp->src_verts[v]->co;
+       else if (sp->edge_verts[v])
+               return sp->edge_verts[v]->co;
+       else
+               return NULL;
+}
+
+static SymmSide symm_poly_co_side(const Symm *symm,
+                                                                 const SymmPoly *sp,
+                                                                 int v)
+{
+       return symm_co_side(symm, symm_poly_co(sp, v));
+}
+
+/* Return the index of the vertex in the destination array at corner
+ * 'v' of the polygon, or -1 if not in that array */
+static BMVert *symm_poly_dst(const SymmPoly *sp, int v)
+{
+       if (sp->edge_verts[v])
+               return sp->edge_verts[v];
+       else if (sp->src_verts[v])
+               return sp->src_verts[v];
+       else
+               return NULL;
+}
+
+/* Same as above, but returns the index of the mirror if available, or
+ * the same index if on the axis, or -1 otherwise */
+static BMVert *symm_poly_mirror_dst(const Symm *symm,
+                                                                       const SymmPoly *sp,
+                                                                       int v)
+{
+       if (sp->edge_verts[v])
+               return sp->edge_verts[v];
+       else if (sp->src_verts[v]) {
+               if (BLI_ghash_haskey(symm->vert_symm_map, sp->src_verts[v]))
+                       return BLI_ghash_lookup(symm->vert_symm_map, sp->src_verts[v]);
+               else
+                       return sp->src_verts[v];
+       }
+       else
+               return NULL;
+}
+
+static int symm_poly_next_crossing(const Symm *symm,
+                                                                  const SymmPoly *sp,
+                                                                  int start,
+                                                                  int *l1,
+                                                                  int *l2)
+{
+       int i;
+
+       for (i = 0; i < sp->len; i++) {
+               (*l1) = (start + i) % sp->len;
+               (*l2) = ((*l1) + 1) % sp->len;
+
+               if ((symm_poly_co_side(symm, sp, *l1) == SYMM_SIDE_KILL) ^
+                       (symm_poly_co_side(symm, sp, *l2) == SYMM_SIDE_KILL))
+               {
+                       return TRUE;
+               }
+       }
+
+       BLI_assert(!"symm_poly_next_crossing failed");
+       return FALSE;
+}
+
+static BMFace *symm_face_create_v(BMesh *bm, BMVert **fv, BMEdge **fe, int len)
+{
+       BMFace *f_new;
+       int i;
+
+       for (i = 0; i < len; i++) {
+               int j = (i + 1) % len;
+               fe[i] = BM_edge_exists(fv[i], fv[j]);
+               if (!fe[i]) {
+                       fe[i] = BM_edge_create(bm, fv[i], fv[j], NULL, FALSE);
+                       BMO_elem_flag_enable(bm, fe[i], SYMM_OUTPUT_GEOM);
+               }
+       }
+       f_new = BM_face_create(bm, fv, fe, len, TRUE);
+       BM_face_select_set(bm, f_new, TRUE);
+       BMO_elem_flag_enable(bm, f_new, SYMM_OUTPUT_GEOM);
+       return f_new;
+}
+
+static void symm_mesh_output_poly_zero_splits(Symm *symm,
+                                                                                         SymmPoly *sp,
+                                                                                         BMVert **fv,
+                                                                                         BMEdge **fe,
+                                                                                         int segment_len,
+                                                                                         int start)
+{
+       int i, j;
+
+       j = 0;
+
+       /* Output the keep side of the input polygon */
+       for (i = 0; i < segment_len; i++) {
+               const int offset = (start + i) % sp->len;
+               BLI_assert(sp->src_verts[offset]);
+               fv[j++] = sp->src_verts[offset];
+       }
+
+       /* Output the kill side of the polygon */
+       for (i = segment_len - 1; i >=0; i--) {
+               const int offset = (start + i) % sp->len;
+
+               if (symm_poly_co_side(symm, sp, offset) == SYMM_SIDE_KEEP) {
+                       BLI_assert(sp->src_verts[offset]);
+                       fv[j++] = BLI_ghash_lookup(symm->vert_symm_map,
+                                                                          sp->src_verts[offset]);
+               }
+       }
+
+       symm_face_create_v(symm->bm, fv, fe, j);
+}
+
+static void symm_mesh_output_poly_with_splits(Symm *symm,
+                                                                                         SymmPoly *sp,
+                                                                                         BMVert **fv,
+                                                                                         BMEdge **fe,
+                                                                                         int segment_len,
+                                                                                         int start)
+{
+       int i;
+
+       /* Output the keep side of the input polygon */
+
+       for (i = 0; i < segment_len; i++) {
+               const int offset = (start + i) % sp->len;
+               BMVert *v = symm_poly_dst(sp, offset);
+
+               BLI_assert(v);
+
+               fv[i] = v;
+       }
+
+       symm_face_create_v(symm->bm, fv, fe, segment_len);
+
+       /* Output the kill side of the input polygon */
+
+       for (i = 0; i < segment_len; i++) {
+               const int offset = (start + i) % sp->len;
+               BMVert *v = symm_poly_mirror_dst(symm, sp, offset);
+
+               fv[segment_len - i - 1] = v;
+
+       }
+
+       symm_face_create_v(symm->bm, fv, fe, segment_len);
+}
+
+static void symm_mirror_polygons(Symm *symm)
+{
+       BMOIter oiter;
+       BMFace *f;
+       BMVert **pv = NULL;
+       BMVert **fv = NULL;
+       BMEdge **fe = NULL;
+       BLI_array_declare(pv);
+       BLI_array_declare(fv);
+       BLI_array_declare(fe);
+
+       BMO_ITER (f, &oiter, symm->bm, symm->op, "input", BM_FACE) {
+               BMIter iter;
+               BMLoop *l;
+               int mirror_all = TRUE, ignore_all = TRUE;
+
+               /* Check if entire polygon can be mirrored or ignored */
+               BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
+                       const SymmSide side = symm_co_side(symm, l->v->co);
+                       if (side == SYMM_SIDE_KILL)
+                               mirror_all = FALSE;
+                       else if (side == SYMM_SIDE_KEEP)
+                               ignore_all = FALSE;
+               }
+
+               if (mirror_all) {
+                       int i;
+
+                       /* Make a mirrored copy of the polygon */
+
+                       BLI_array_empty(fv);
+                       BLI_array_empty(fe);
+                       BLI_array_grow_items(fv, f->len);
+                       BLI_array_grow_items(fe, f->len);
+
+                       i = f->len;
+                       BM_ITER_ELEM (l, &iter, f, BM_LOOPS_OF_FACE) {
+                               i--;
+
+                               if (symm_co_side(symm, l->v->co) == SYMM_SIDE_KEEP)
+                                       fv[i] = BLI_ghash_lookup(symm->vert_symm_map, l->v);
+                               else
+                                       fv[i] = l->v;
+                       }
+
+                       symm_face_create_v(symm->bm, fv, fe, f->len);
+               }
+               else if (ignore_all) {
+                       BM_face_kill(symm->bm, f);
+               }
+               else {
+                       SymmPoly sp;
+                       int l1, l2, l3, l4;
+                       int double_l2, double_l3;
+                       int segment_len;
+
+                       BLI_array_empty(pv);
+                       BLI_array_grow_items(pv, f->len * 4);
+                       sp.src_verts = pv;
+                       sp.edge_verts = pv + f->len * 2;
+                       symm_poly_with_splits(symm, f, &sp);
+
+                       /* Find first loop edge crossing the axis */
+                       symm_poly_next_crossing(symm, &sp, 0, &l1, &l2);
+
+                       /* If crossing isn't kill to keep, find the next one */
+                       if (symm_poly_co_side(symm, &sp, l1) != SYMM_SIDE_KILL) {
+                               symm_poly_next_crossing(symm, &sp, l2, &l1, &l2);
+                       }
+
+                       /* Find next crossing (keep to kill) */
+                       symm_poly_next_crossing(symm, &sp, l2, &l3, &l4);
+
+                       if (l2 == l3)
+                               segment_len = 0;
+                       else if (l2 < l3)
+                               segment_len = l3 - l2 + 1;
+                       else
+                               segment_len = (sp.len - l2 + 1) + l3;
+
+                       double_l2 = symm_poly_co_side(symm, &sp, l2) == SYMM_SIDE_KEEP;
+                       double_l3 = symm_poly_co_side(symm, &sp, l3) == SYMM_SIDE_KEEP;
+
+                       /* Calculate number of new polygons/loops */
+                       if (segment_len == 0) {
+                       }
+                       else if (sp.already_symmetric) {
+                               int new_loops;
+
+                               if (double_l2 && double_l3)
+                                       new_loops = segment_len * 2;
+                               else if (!double_l2 && !double_l3)
+                                       new_loops = segment_len * 2 - 2;
+                               else
+                                       new_loops = segment_len * 2 - 1;
+
+                               BLI_array_empty(fv);
+                               BLI_array_empty(fe);
+                               BLI_array_grow_items(fv, new_loops);
+                               BLI_array_grow_items(fe, new_loops);
+
+                               symm_mesh_output_poly_zero_splits(symm, &sp,
+                                                                                                 fv, fe,
+                                                                                                 segment_len, l2);
+                               BM_face_kill(symm->bm, f);
+                       }
+                       else if (!double_l2 && !double_l3) {
+                               BLI_array_empty(fv);
+                               BLI_array_empty(fe);
+                               BLI_array_grow_items(fv, segment_len);
+                               BLI_array_grow_items(fe, segment_len);
+
+                               symm_mesh_output_poly_with_splits(symm, &sp,
+                                                                                                 fv, fe,
+                                                                                                 segment_len,
+                                                                                                 l2);
+
+                               BM_face_kill(symm->bm, f);
+                       }
+                       else {
+                               BLI_array_empty(fv);
+                               BLI_array_empty(fe);
+                               BLI_array_grow_items(fv, segment_len);
+                               BLI_array_grow_items(fe, segment_len);
+
+                               symm_mesh_output_poly_with_splits(symm, &sp,
+                                                                                                 fv, fe,
+                                                                                                 segment_len,
+                                                                                                 l2);
+
+                               BM_face_kill(symm->bm, f);
+
+                               /* Output bridge triangle */
+
+                               BLI_array_empty(fv);
+                               BLI_array_empty(fe);
+                               BLI_array_grow_items(fv, 3);
+                               BLI_array_grow_items(fe, 3);
+
+                               if (double_l2) {
+                                       fv[0] = symm_poly_dst(&sp, l2);
+                                       fv[1] = symm_poly_mirror_dst(symm, &sp, l2);
+                                       fv[2] = symm_poly_dst(&sp, l3);
+                               }
+                               else if (double_l3) {
+                                       fv[0] = symm_poly_dst(&sp, l3);
+                                       fv[1] = symm_poly_mirror_dst(symm, &sp, l3);
+                                       fv[2] = symm_poly_dst(&sp, l2);
+                               }
+
+                               BLI_assert(fv[0] && fv[1] && fv[2]);
+
+                               symm_face_create_v(symm->bm, fv, fe, 3);
+                       }
+               }
+       }
+
+       BLI_array_free(pv);
+       BLI_array_free(fv);
+       BLI_array_free(fe);
+}
+
+/* Remove unused edges and vertices from the side being copied to */
+static void symm_kill_unused(Symm *symm)
+{
+       BMOIter oiter;
+       BMEdge *e;
+       BMVert *v;
+
+       /* Kill unused edges */
+       BMO_ITER (e, &oiter, symm->bm, symm->op, "input", BM_EDGE) {
+               const int crosses = symm_edge_crosses_axis(symm, e);
+               const int symmetric = (crosses &&
+                                                          (!BLI_ghash_haskey(symm->edge_split_map, e)));
+
+               if (((symm_co_side(symm, e->v1->co) == SYMM_SIDE_KILL) ||
+                        (symm_co_side(symm, e->v2->co) == SYMM_SIDE_KILL)) &&
+                       !symmetric)
+               {
+                       /* The edge might be used by a face outside the input set */
+                       if (BM_edge_face_count(e) == 0)
+                               BM_edge_kill(symm->bm, e);
+               }
+       }
+
+       /* Kill unused vertices */
+       BMO_ITER (v, &oiter, symm->bm, symm->op, "input", BM_VERT) {
+               if (symm_co_side(symm, v->co) == SYMM_SIDE_KILL) {
+                       if (BM_vert_edge_count(v) == 0)
+                               BM_vert_kill(symm->bm, v);
+               }
+       }
+}
+
+void bmo_symmetrize_exec(BMesh *bm, BMOperator *op)
+{
+       Symm symm;
+       BMO_SymmDirection direction = BMO_slot_int_get(op, "direction");
+
+       symm.bm = bm;
+       symm.op = op;
+       symm.axis = (ELEM(direction,
+                                         BMO_SYMMETRIZE_NEGATIVE_X,
+                                         BMO_SYMMETRIZE_POSITIVE_X) ? 0 :
+                                ELEM(direction,
+                                         BMO_SYMMETRIZE_NEGATIVE_Y,
+                                         BMO_SYMMETRIZE_POSITIVE_Y) ? 1 :
+                                ELEM(direction,
+                                         BMO_SYMMETRIZE_NEGATIVE_Z,
+                                         BMO_SYMMETRIZE_POSITIVE_Z) ? 2 : 0);
+       symm.direction = direction;
+
+       symm_verts_mirror(&symm);
+       symm_split_asymmetric_edges(&symm);
+       symm_mirror_edges(&symm);
+       symm_mirror_polygons(&symm);
+       symm_kill_unused(&symm);
+
+       BLI_ghash_free(symm.vert_symm_map, NULL, NULL);
+       BLI_ghash_free(symm.edge_split_map, NULL, NULL);
+
+       BMO_slot_buffer_from_enabled_flag(bm, op, "geomout", BM_ALL,
+                                         SYMM_OUTPUT_GEOM);
+}
index 69cfe79728e659c14f963c1ce3f27089395d168b..d8dce98a009203cffa668ead5d5ba859c078c7d5 100644 (file)
@@ -41,6 +41,7 @@
 #include "RNA_define.h"
 #include "RNA_access.h"
 
+#include "BLI_array.h"
 #include "BLI_blenlib.h"
 #include "BLI_noise.h"
 #include "BLI_math.h"
@@ -50,6 +51,7 @@
 #include "BKE_context.h"
 #include "BKE_cdderivedmesh.h"
 #include "BKE_depsgraph.h"
+#include "BKE_mesh.h"
 #include "BKE_object.h"
 #include "BKE_report.h"
 #include "BKE_texture.h"
@@ -5393,3 +5395,54 @@ void MESH_OT_convex_hull(wmOperatorType *ot)
 
        join_triangle_props(ot);
 }
+
+static int mesh_symmetrize_exec(bContext *C, wmOperator *op)
+{
+       Object *obedit = CTX_data_edit_object(C);
+       BMEditMesh *em = BMEdit_FromObject(obedit);
+       BMOperator bmop;
+
+       EDBM_op_init(em, &bmop, op, "symmetrize input=%hvef direction=%i",
+                                BM_ELEM_SELECT, RNA_enum_get(op->ptr, "direction"));
+       BMO_op_exec(em->bm, &bmop);
+
+       if (!EDBM_op_finish(em, &bmop, op, TRUE)) {
+               return OPERATOR_CANCELLED;
+       }
+       else {
+               EDBM_update_generic(C, em, TRUE);
+               EDBM_selectmode_flush(em);
+               return OPERATOR_FINISHED;
+       }
+}
+
+void MESH_OT_symmetrize(struct wmOperatorType *ot)
+{
+       static EnumPropertyItem direction_items[] = {
+               {BMO_SYMMETRIZE_NEGATIVE_X, "NEGATIVE_X", 0, "-X to +X", ""},
+               {BMO_SYMMETRIZE_POSITIVE_X, "POSITIVE_X", 0, "+X to -X", ""},
+
+               {BMO_SYMMETRIZE_NEGATIVE_Y, "NEGATIVE_Y", 0, "-Y to +Y", ""},
+               {BMO_SYMMETRIZE_POSITIVE_Y, "POSITIVE_Y", 0, "+Y to -Y", ""},
+
+               {BMO_SYMMETRIZE_NEGATIVE_Z, "NEGATIVE_Z", 0, "-Z to +Z", ""},
+               {BMO_SYMMETRIZE_POSITIVE_Z, "POSITIVE_Z", 0, "+Z to -Z", ""},
+               {0, NULL, 0, NULL, NULL},
+       };
+
+       /* identifiers */
+       ot->name = "Symmetrize";
+       ot->description = "Enforce symmetry (both form and topological) across an axis";
+       ot->idname = "MESH_OT_symmetrize";
+
+       /* api callbacks */
+       ot->exec = mesh_symmetrize_exec;
+       ot->poll = ED_operator_editmesh;
+
+       /* flags */
+       ot->flag = OPTYPE_REGISTER | OPTYPE_UNDO;
+
+       ot->prop = RNA_def_enum(ot->srna, "direction", direction_items,
+                                                       BMO_SYMMETRIZE_NEGATIVE_X,
+                                                       "Direction", "Which sides to copy from and to");
+}
index 2676316c66db54f515c490d6ecdab965d4074471..5fcf4fe4377f93b690a2fba33018cb38aeaf6e35 100644 (file)
@@ -214,6 +214,8 @@ void MESH_OT_vert_slide(struct wmOperatorType *ot);
 
 void MESH_OT_convex_hull(struct wmOperatorType *ot);
 
+void MESH_OT_symmetrize(struct wmOperatorType *ot);
+
 /* ******************* mesh_navmesh.c */
 void MESH_OT_navmesh_make(struct wmOperatorType *ot);
 void MESH_OT_navmesh_face_copy(struct wmOperatorType *ot);
index 8ba9b3fe4e7e9fe37aad19a84694740f777377c4..8a575e57a60e309d06a4917b22f0fb30da4381d1 100644 (file)
@@ -166,6 +166,8 @@ void ED_operatortypes_mesh(void)
 
        WM_operatortype_append(MESH_OT_convex_hull);
 
+       WM_operatortype_append(MESH_OT_symmetrize);
+
 #ifdef WITH_GAMEENGINE
        WM_operatortype_append(MESH_OT_navmesh_make);
        WM_operatortype_append(MESH_OT_navmesh_face_copy);