add beauty option for triangle fill since you might want to use the initial scanfill...
[blender.git] / source / blender / bmesh / operators / bmo_triangulate.c
index 78dd721..3d78ff6 100644 (file)
  * ***** END GPL LICENSE BLOCK *****
  */
 
+/** \file blender/bmesh/operators/bmo_triangulate.c
+ *  \ingroup bmesh
+ */
+
 #include "MEM_guardedalloc.h"
+#include "DNA_listBase.h"
 
-#include "BLI_scanfill.h"
 #include "BLI_math.h"
 #include "BLI_array.h"
-#include "BLI_editVert.h"
 #include "BLI_smallhash.h"
+#include "BLI_scanfill.h"
 
 #include "bmesh.h"
-#include "bmesh_private.h"
-
-#include "bmesh_operators_private.h" /* own include */
+#include "intern/bmesh_private.h"
 
-#define EDGE_NEW       1
-#define FACE_NEW       1
+#include "intern/bmesh_operators_private.h" /* own include */
 
 #define ELE_NEW                1
 #define FACE_MARK      2
 #define EDGE_MARK      4
 
-void triangulate_exec(BMesh *bm, BMOperator *op)
+void bmo_triangulate_exec(BMesh *bm, BMOperator *op)
 {
-       BMOIter siter;
-       BMFace *face, **newfaces = NULL;
-       BLI_array_declare(newfaces);
-       float (*projectverts)[3] = NULL;
-       BLI_array_declare(projectverts);
-       int i, lastlen = 0 /* , count = 0 */;
-       
-       face = BMO_iter_new(&siter, bm, op, "faces", BM_FACE);
-       for ( ; face; face = BMO_iter_step(&siter)) {
-               if (lastlen < face->len) {
-                       BLI_array_empty(projectverts);
-                       BLI_array_empty(newfaces);
-                       for (lastlen = 0; lastlen < face->len; lastlen++) {
-                               BLI_array_growone(projectverts);
-                               BLI_array_growone(projectverts);
-                               BLI_array_growone(projectverts);
-                               BLI_array_growone(newfaces);
-                       }
-               }
+       const bool use_beauty = BMO_slot_bool_get(op->slots_in, "use_beauty");
+       BMOpSlot *slot_facemap_out = BMO_slot_get(op->slots_out, "face_map.out");
 
-               BM_Triangulate_Face(bm, face, projectverts, EDGE_NEW, FACE_NEW, newfaces);
+       BM_mesh_elem_hflag_disable_all(bm, BM_FACE | BM_EDGE, BM_ELEM_TAG, false);
+       BMO_slot_buffer_hflag_enable(bm, op->slots_in, "faces", BM_FACE, BM_ELEM_TAG, false);
 
-               BMO_slot_map_ptr_insert(bm, op, "facemap", face, face);
-               for (i = 0; newfaces[i]; i++) {
-                       BMO_slot_map_ptr_insert(bm, op, "facemap",
-                                             newfaces[i], face);
+       BM_mesh_triangulate(bm, use_beauty, true, op, slot_facemap_out);
 
-               }
-       }
-       
-       BMO_slot_from_flag(bm, op, "edgeout", EDGE_NEW, BM_EDGE);
-       BMO_slot_from_flag(bm, op, "faceout", FACE_NEW, BM_FACE);
-       
-       BLI_array_free(projectverts);
-       BLI_array_free(newfaces);
+       BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "edges.out", BM_EDGE, BM_ELEM_TAG);
+       BMO_slot_buffer_from_enabled_hflag(bm, op, op->slots_out, "faces.out", BM_FACE, BM_ELEM_TAG);
 }
 
-void bmesh_beautify_fill_exec(BMesh *bm, BMOperator *op)
+void bmo_beautify_fill_exec(BMesh *bm, BMOperator *op)
 {
        BMOIter siter;
        BMIter iter;
@@ -87,58 +63,80 @@ void bmesh_beautify_fill_exec(BMesh *bm, BMOperator *op)
        BMEdge *e;
        int stop = 0;
        
-       BMO_slot_buffer_flag(bm, op, "constrain_edges", EDGE_MARK, BM_EDGE);
+       BMO_slot_buffer_flag_enable(bm, op->slots_in, "edges", BM_EDGE, EDGE_MARK);
        
-       BMO_ITER(f, &siter, bm, op, "faces", BM_FACE) {
-               if (f->len == 3)
-                       BMO_elem_flag_set(bm, f, FACE_MARK);
+       BMO_ITER (f, &siter, op->slots_in, "faces", BM_FACE) {
+               if (f->len == 3) {
+                       BMO_elem_flag_enable(bm, f, FACE_MARK);
+               }
        }
 
        while (!stop) {
                stop = 1;
                
-               BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
-                       BMVert *v1, *v2, *v3, *v4;
+               BM_ITER_MESH (e, &iter, bm, BM_EDGES_OF_MESH) {
+                       float v1_xy[2], v2_xy[2], v3_xy[2], v4_xy[2];
+                       float no[3];
+                       float axis_mat[3][3];
                        
-                       if (BM_edge_face_count(e) != 2 || BMO_elem_flag_test(bm, e, EDGE_MARK))
+                       if (!BM_edge_is_manifold(e) || !BMO_elem_flag_test(bm, e, EDGE_MARK)) {
                                continue;
-                       if (!BMO_elem_flag_test(bm, e->l->f, FACE_MARK) || !BMO_elem_flag_test(bm, e->l->radial_next->f, FACE_MARK))
+                       }
+
+                       if (!BMO_elem_flag_test(bm, e->l->f, FACE_MARK) ||
+                           !BMO_elem_flag_test(bm, e->l->radial_next->f, FACE_MARK))
+                       {
                                continue;
+                       }
                        
-                       v1 = e->l->prev->v;
-                       v2 = e->l->v;
-                       v3 = e->l->radial_next->prev->v;
-                       v4 = e->l->next->v;
-                       
-                       if (is_quad_convex_v3(v1->co, v2->co, v3->co, v4->co)) {
+                       {
+                               float *v1, *v2, *v3, *v4;
+                               float no_a[3], no_b[3];
+                               v1 = e->l->prev->v->co;
+                               v2 = e->l->v->co;
+                               v3 = e->l->radial_next->prev->v->co;
+                               v4 = e->l->next->v->co;
+
+                               normal_tri_v3(no_a, v1, v2, v3);
+                               normal_tri_v3(no_b, v1, v3, v4);
+                               add_v3_v3v3(no, no_a, no_b);
+                               normalize_v3(no);
+                               axis_dominant_v3_to_m3(axis_mat, no);
+                               mul_v2_m3v3(v1_xy, axis_mat, v1);
+                               mul_v2_m3v3(v2_xy, axis_mat, v2);
+                               mul_v2_m3v3(v3_xy, axis_mat, v3);
+                               mul_v2_m3v3(v4_xy, axis_mat, v4);
+                       }
+
+                       if (is_quad_convex_v2(v1_xy, v2_xy, v3_xy, v4_xy)) {
                                float len1, len2, len3, len4, len5, len6, opp1, opp2, fac1, fac2;
                                /* testing rule:
-                               * the area divided by the total edge lengths
-                               */
-                               len1 = len_v3v3(v1->co, v2->co);
-                               len2 = len_v3v3(v2->co, v3->co);
-                               len3 = len_v3v3(v3->co, v4->co);
-                               len4 = len_v3v3(v4->co, v1->co);
-                               len5 = len_v3v3(v1->co, v3->co);
-                               len6 = len_v3v3(v2->co, v4->co);
-
-                               opp1 = area_tri_v3(v1->co, v2->co, v3->co);
-                               opp2 = area_tri_v3(v1->co, v3->co, v4->co);
+                                * the area divided by the total edge lengths
+                                */
+                               len1 = len_v2v2(v1_xy, v2_xy);
+                               len2 = len_v2v2(v2_xy, v3_xy);
+                               len3 = len_v2v2(v3_xy, v4_xy);
+                               len4 = len_v2v2(v4_xy, v1_xy);
+                               len5 = len_v2v2(v1_xy, v3_xy);
+                               len6 = len_v2v2(v2_xy, v4_xy);
+
+                               opp1 = area_tri_v2(v1_xy, v2_xy, v3_xy);
+                               opp2 = area_tri_v2(v1_xy, v3_xy, v4_xy);
 
                                fac1 = opp1 / (len1 + len2 + len5) + opp2 / (len3 + len4 + len5);
 
-                               opp1 = area_tri_v3(v2->co, v3->co, v4->co);
-                               opp2 = area_tri_v3(v2->co, v4->co, v1->co);
+                               opp1 = area_tri_v2(v2_xy, v3_xy, v4_xy);
+                               opp2 = area_tri_v2(v2_xy, v4_xy, v1_xy);
 
                                fac2 = opp1 / (len2 + len3 + len6) + opp2 / (len4 + len1 + len6);
                                
                                if (fac1 > fac2) {
-                                       e = BM_edge_rotate(bm, e, 0);
+                                       e = BM_edge_rotate(bm, e, false, BM_EDGEROT_CHECK_EXISTS);
                                        if (e) {
-                                               BMO_elem_flag_set(bm, e, ELE_NEW);
+                                               BMO_elem_flag_enable(bm, e, ELE_NEW | EDGE_MARK);
 
-                                               BMO_elem_flag_set(bm, e->l->f, FACE_MARK|ELE_NEW);
-                                               BMO_elem_flag_set(bm, e->l->radial_next->f, FACE_MARK|ELE_NEW);
+                                               BMO_elem_flag_enable(bm, e->l->f, FACE_MARK | ELE_NEW);
+                                               BMO_elem_flag_enable(bm, e->l->radial_next->f, FACE_MARK | ELE_NEW);
                                                stop = 0;
                                        }
                                }
@@ -146,69 +144,73 @@ void bmesh_beautify_fill_exec(BMesh *bm, BMOperator *op)
                }
        }
        
-       BMO_slot_from_flag(bm, op, "geomout", ELE_NEW, BM_EDGE|BM_FACE);
+       BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom.out", BM_EDGE | BM_FACE, ELE_NEW);
 }
 
-void bmesh_triangle_fill_exec(BMesh *bm, BMOperator *op)
+void bmo_triangle_fill_exec(BMesh *bm, BMOperator *op)
 {
+       const bool use_beauty = BMO_slot_bool_get(op->slots_in, "use_beauty");
        BMOIter siter;
        BMEdge *e;
-       BMOperator bmop;
-       EditEdge *eed;
-       EditVert *eve, *v1, *v2;
-       EditFace *efa;
+       ScanFillContext sf_ctx;
+       /* ScanFillEdge *sf_edge; */ /* UNUSED */
+       ScanFillVert *sf_vert, *sf_vert_1, *sf_vert_2;
+       ScanFillFace *sf_tri;
        SmallHash hash;
 
        BLI_smallhash_init(&hash);
        
-       BLI_begin_edgefill();
+       BLI_scanfill_begin(&sf_ctx);
        
-       BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
-               BMO_elem_flag_set(bm, e, EDGE_MARK);
+       BMO_ITER (e, &siter, op->slots_in, "edges", BM_EDGE) {
+               BMO_elem_flag_enable(bm, e, EDGE_MARK);
                
                if (!BLI_smallhash_haskey(&hash, (uintptr_t)e->v1)) {
-                       eve = BLI_addfillvert(e->v1->co);
-                       eve->tmp.p = e->v1;
-                       BLI_smallhash_insert(&hash, (uintptr_t)e->v1, eve);
+                       sf_vert = BLI_scanfill_vert_add(&sf_ctx, e->v1->co);
+                       sf_vert->tmp.p = e->v1;
+                       BLI_smallhash_insert(&hash, (uintptr_t)e->v1, sf_vert);
                }
                
                if (!BLI_smallhash_haskey(&hash, (uintptr_t)e->v2)) {
-                       eve = BLI_addfillvert(e->v2->co);
-                       eve->tmp.p = e->v2;
-                       BLI_smallhash_insert(&hash, (uintptr_t)e->v2, eve);
+                       sf_vert = BLI_scanfill_vert_add(&sf_ctx, e->v2->co);
+                       sf_vert->tmp.p = e->v2;
+                       BLI_smallhash_insert(&hash, (uintptr_t)e->v2, sf_vert);
                }
                
-               v1 = BLI_smallhash_lookup(&hash, (uintptr_t)e->v1);
-               v2 = BLI_smallhash_lookup(&hash, (uintptr_t)e->v2);
-               eed = BLI_addfilledge(v1, v2);
-               eed->tmp.p = e;
+               sf_vert_1 = BLI_smallhash_lookup(&hash, (uintptr_t)e->v1);
+               sf_vert_2 = BLI_smallhash_lookup(&hash, (uintptr_t)e->v2);
+               /* sf_edge = */ BLI_scanfill_edge_add(&sf_ctx, sf_vert_1, sf_vert_2);
+               /* sf_edge->tmp.p = e; */ /* UNUSED */
        }
        
-       BLI_edgefill(0);
+       BLI_scanfill_calc(&sf_ctx, BLI_SCANFILL_CALC_HOLES);
        
-       for (efa = fillfacebase.first; efa; efa = efa->next) {
+       for (sf_tri = sf_ctx.fillfacebase.first; sf_tri; sf_tri = sf_tri->next) {
                BMFace *f = BM_face_create_quad_tri(bm,
-                                                efa->v1->tmp.p, efa->v2->tmp.p, efa->v3->tmp.p, NULL,
-                                                NULL, TRUE);
+                                                   sf_tri->v1->tmp.p, sf_tri->v2->tmp.p, sf_tri->v3->tmp.p, NULL,
+                                                   NULL, true);
                BMLoop *l;
                BMIter liter;
                
-               BMO_elem_flag_set(bm, f, ELE_NEW);
-               BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
+               BMO_elem_flag_enable(bm, f, ELE_NEW);
+               BM_ITER_ELEM (l, &liter, f, BM_LOOPS_OF_FACE) {
                        if (!BMO_elem_flag_test(bm, l->e, EDGE_MARK)) {
-                               BMO_elem_flag_set(bm, l->e, ELE_NEW);
+                               BMO_elem_flag_enable(bm, l->e, ELE_NEW);
                        }
                }
        }
        
-       BLI_end_edgefill();
+       BLI_scanfill_end(&sf_ctx);
        BLI_smallhash_release(&hash);
        
-       /* clean up fill */
-       BMO_op_initf(bm, &bmop, "beautify_fill faces=%ff constrain_edges=%fe", ELE_NEW, EDGE_MARK);
-       BMO_op_exec(bm, &bmop);
-       BMO_slot_buffer_flag(bm, &bmop, "geomout", ELE_NEW, BM_FACE|BM_EDGE);
-       BMO_op_finish(bm, &bmop);
+       if (use_beauty) {
+               BMOperator bmop;
+
+               BMO_op_initf(bm, &bmop, op->flag, "beautify_fill faces=%ff edges=%Fe", ELE_NEW, EDGE_MARK);
+               BMO_op_exec(bm, &bmop);
+               BMO_slot_buffer_flag_enable(bm, bmop.slots_out, "geom.out", BM_FACE | BM_EDGE, ELE_NEW);
+               BMO_op_finish(bm, &bmop);
+       }
        
-       BMO_slot_from_flag(bm, op, "geomout", ELE_NEW, BM_EDGE|BM_FACE);
+       BMO_slot_buffer_from_enabled_flag(bm, op, op->slots_out, "geom.out", BM_EDGE | BM_FACE, ELE_NEW);
 }