source/blender/bmesh/operators/triangulateop.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4
   5 #include "MEM_guardedalloc.h"
   6
   7 #include "BKE_utildefines.h"
   8
   9 #include "BLI_scanfill.h"
  10 #include "BLI_math.h"
  11 #include "BLI_array.h"
  12 #include "BLI_editVert.h"
  13 #include "BLI_smallhash.h"
  14
  15 #include "bmesh.h"
  16 #include "bmesh_private.h"
  17
  18 #define EDGE_NEW        1
  19 #define FACE_NEW        1
  20
  21 #define ELE_NEW         1
  22 #define FACE_MARK       2
  23 #define EDGE_MARK       4
  24
  25 void triangulate_exec(BMesh *bm, BMOperator *op)
  26 {
  27         BMOIter siter;
  28         BMFace *face, **newfaces = NULL;
  29         BLI_array_declare(newfaces);
  30         float (*projectverts)[3] = NULL;
  31         BLI_array_declare(projectverts);
  32         int i, lastlen=0 /* , count = 0 */;
  33
  34         face = BMO_IterNew(&siter, bm, op, "faces", BM_FACE);
  35         for (; face; face=BMO_IterStep(&siter)) {
  36                 if (lastlen < face->len) {
  37                         BLI_array_empty(projectverts);
  38                         BLI_array_empty(newfaces);
  39                         for (lastlen=0; lastlen<face->len; lastlen++) {
  40                                 BLI_array_growone(projectverts);
  41                                 BLI_array_growone(projectverts);
  42                                 BLI_array_growone(projectverts);
  43                                 BLI_array_growone(newfaces);
  44                         }
  45                 }
  46
  47                 BM_Triangulate_Face(bm, face, projectverts, EDGE_NEW,
  48                                     FACE_NEW, newfaces);
  49
  50                 BMO_Insert_MapPointer(bm, op, "facemap",
  51                                       face, face);
  52                 for (i=0; newfaces[i]; i++) {
  53                         BMO_Insert_MapPointer(bm, op, "facemap",
  54                                               newfaces[i], face);
  55
  56                 }
  57         }
  58
  59         BMO_Flag_To_Slot(bm, op, "edgeout", EDGE_NEW, BM_EDGE);
  60         BMO_Flag_To_Slot(bm, op, "faceout", FACE_NEW, BM_FACE);
  61
  62         BLI_array_free(projectverts);
  63         BLI_array_free(newfaces);
  64 }
  65
  66 void bmesh_beautify_fill_exec(BMesh *bm, BMOperator *op)
  67 {
  68         BMOIter siter;
  69         BMIter iter;
  70         BMFace *f;
  71         BMEdge *e;
  72         int stop=0;
  73
  74         BMO_Flag_Buffer(bm, op, "constrain_edges", EDGE_MARK, BM_EDGE);
  75
  76         BMO_ITER(f, &siter, bm, op, "faces", BM_FACE) {
  77                 if (f->len == 3)
  78                         BMO_SetFlag(bm, f, FACE_MARK);
  79         }
  80
  81         while (!stop) {
  82                 stop = 1;
  83
  84                 BM_ITER(e, &iter, bm, BM_EDGES_OF_MESH, NULL) {
  85                         BMVert *v1, *v2, *v3, *v4, *d1, *d2;
  86                         float len1, len2, len3, len4, len5, len6, opp1, opp2, fac1, fac2;
  87                         int ok;
  88
  89                         if (BM_Edge_FaceCount(e) != 2 || BMO_TestFlag(bm, e, EDGE_MARK))
  90                                 continue;
  91                         if (!BMO_TestFlag(bm, e->l->f, FACE_MARK) || !BMO_TestFlag(bm, e->l->radial_next->f, FACE_MARK))
  92                                 continue;
  93
  94                         v1 = e->l->prev->v;
  95                         v2 = e->l->v;
  96                         v3 = e->l->radial_next->prev->v;
  97                         v4 = e->l->next->v;
  98
  99                         if (is_quad_convex_v3(v1->co, v2->co, v3->co, v4->co)) {
 100                                 /* testing rule:
 101                                 * the area divided by the total edge lengths
 102                                 */
 103                                 len1= len_v3v3(v1->co, v2->co);
 104                                 len2= len_v3v3(v2->co, v3->co);
 105                                 len3= len_v3v3(v3->co, v4->co);
 106                                 len4= len_v3v3(v4->co, v1->co);
 107                                 len5= len_v3v3(v1->co, v3->co);
 108                                 len6= len_v3v3(v2->co, v4->co);
 109
 110                                 opp1= area_tri_v3(v1->co, v2->co, v3->co);
 111                                 opp2= area_tri_v3(v1->co, v3->co, v4->co);
 112
 113                                 fac1= opp1/(len1+len2+len5) + opp2/(len3+len4+len5);
 114
 115                                 opp1= area_tri_v3(v2->co, v3->co, v4->co);
 116                                 opp2= area_tri_v3(v2->co, v4->co, v1->co);
 117
 118                                 fac2= opp1/(len2+len3+len6) + opp2/(len4+len1+len6);
 119                                 ok = 0;
 120
 121                                 if (fac1 > fac2) {
 122                                         e = BM_Rotate_Edge(bm, e, 0);
 123                                         BMO_SetFlag(bm, e, ELE_NEW);
 124
 125                                         BMO_SetFlag(bm, e->l->f, FACE_MARK|ELE_NEW);
 126                                         BMO_SetFlag(bm, e->l->radial_next->f, FACE_MARK|ELE_NEW);
 127                                         stop = 0;
 128                                 }
 129                         }
 130                 }
 131         }
 132
 133         BMO_Flag_To_Slot(bm, op, "geomout", ELE_NEW, BM_EDGE|BM_FACE);
 134 }
 135
 136 void bmesh_triangle_fill_exec(BMesh *bm, BMOperator *op)
 137 {
 138         BMOIter siter;
 139         BMEdge *e;
 140         BMOperator bmop;
 141         EditEdge *eed;
 142         EditVert *eve, *v1, *v2;
 143         EditFace *efa;
 144         SmallHash hash;
 145
 146         BLI_smallhash_init(&hash);
 147
 148         BLI_begin_edgefill();
 149
 150         BMO_ITER(e, &siter, bm, op, "edges", BM_EDGE) {
 151                 BMO_SetFlag(bm, e, EDGE_MARK);
 152
 153                 if (!BLI_smallhash_haskey(&hash, (uintptr_t)e->v1)) {
 154                         eve = BLI_addfillvert(e->v1->co);
 155                         eve->tmp.p = e->v1;
 156                         BLI_smallhash_insert(&hash, (uintptr_t)e->v1, eve);
 157                 }
 158
 159                 if (!BLI_smallhash_haskey(&hash, (uintptr_t)e->v2)) {
 160                         eve = BLI_addfillvert(e->v2->co);
 161                         eve->tmp.p = e->v2;
 162                         BLI_smallhash_insert(&hash, (uintptr_t)e->v2, eve);
 163                 }
 164
 165                 v1 = BLI_smallhash_lookup(&hash, (uintptr_t)e->v1);
 166                 v2 = BLI_smallhash_lookup(&hash, (uintptr_t)e->v2);
 167                 eed = BLI_addfilledge(v1, v2);
 168                 eed->tmp.p = e;
 169         }
 170
 171         BLI_edgefill(0);
 172
 173         for (efa=fillfacebase.first; efa; efa=efa->next) {
 174                 BMFace *f = BM_Make_QuadTri(bm, efa->v1->tmp.p, efa->v2->tmp.p, efa->v3->tmp.p, NULL, NULL, 1);
 175                 BMLoop *l;
 176                 BMIter liter;
 177
 178                 BMO_SetFlag(bm, f, ELE_NEW);
 179                 BM_ITER(l, &liter, bm, BM_LOOPS_OF_FACE, f) {
 180                         if (!BMO_TestFlag(bm, l->e, EDGE_MARK)) {
 181                                 BMO_SetFlag(bm, l->e, ELE_NEW);
 182                         }
 183                 }
 184         }
 185
 186         BLI_end_edgefill();
 187         BLI_smallhash_release(&hash);
 188
 189         /*clean up fill*/
 190         BMO_InitOpf(bm, &bmop, "beautify_fill faces=%ff constrain_edges=%fe", ELE_NEW, EDGE_MARK);
 191         BMO_Exec_Op(bm, &bmop);
 192         BMO_Flag_Buffer(bm, &bmop, "geomout", ELE_NEW, BM_FACE|BM_EDGE);
 193         BMO_Finish_Op(bm, &bmop);
 194
 195         BMO_Flag_To_Slot(bm, op, "geomout", ELE_NEW, BM_EDGE|BM_FACE);
 196 }