source/blender/bmesh/operators/subdivideop.c

   1 #include "MEM_guardedalloc.h"
   2
   3 #include "BKE_utildefines.h"
   4
   5 #include "bmesh.h"
   6 #include "BLI_arithb.h"
   7
   8 #include <stdio.h>
   9
  10 /*
  11 note: this is a pattern-based edge subdivider.
  12 it tries to match a pattern to edge selections on faces.
  13 it was a fairly easy exercise to test the bmesh api; it
  14 doesn't support multicuts, so it won't actually be used.
  15
  16 the patterns are defined as followed:
  17
  18 the patterns are defined for the state of the face after
  19 initial splitting.  each edge that was split is flagged, as is
  20 the new resulting edge.
  21
  22 subdpattern pattern = {
  23         //boolean flags for if an edge should have been split or not
  24         {1, 0, 0, 0},
  25         //connection values for verts,
  26         {2, -1, -1, -1},
  27         //second stage split flags, splits newly created edges
  28         {0, 0, 0, 0, 1},
  29         //second stage connection values for verts, connects stuff again.
  30         {-1, -1, -1, -1, 3},
  31         4 //len of face before second stage splits, but after initial edge splits
  32 };
  33
  34 */
  35 typedef struct subdpattern {
  36         int seledges[20]; //selected edges mask, for splitting
  37         int connectverts[20]; //verts to connect;
  38
  39         int secondstage_splitedges[20];
  40         //verts to connect afterwards.  size must be len + number
  41         //of edges split in secondstage_splitedges
  42         int secondstage_connect[20];
  43
  44         int len; /*total number of verts*/
  45 } subdpattern;
  46
  47 /*generic subdivision rules:
  48
  49   * two selected edges in a face should make a link
  50     between them.
  51
  52   * one edge should do, what? make pretty topology, or just
  53     split the edge only?
  54 */
  55
  56 /*note: the patterns are rotated as necassary to
  57   match the input geometry.  they're also based on the
  58   post-splitted state of the faces.  note that
  59   second stage splitted stuff doesn't count
  60   for pattern->len!*/
  61
  62 /*
  63      v2
  64     /  \
  65 v1 s_e1 e2
  66   /e0     \
  67 v0---e3----v3
  68
  69 handle case of one edge selected.
  70 */
  71
  72 subdpattern t_1edge = {
  73         {1, 1, 0, 0},
  74         {-1, 3, -1, -1},
  75         {0},
  76         {-1, -1, -1, -1, -1, -1, -1, -1, -1},
  77         4
  78 };
  79
  80
  81 /*
  82      v2
  83     /  \e2
  84 v1 e1   e3 v3
  85   /e0     \
  86 v0---e4----v4
  87
  88 handle case of two edges selected.
  89 */
  90 subdpattern t_2edge = {
  91         {1, 1, 1, 1, 0},
  92         {-1, 3, -1, -1, -1},
  93         {0},
  94         {-1, -1, -1, -1, -1, -1, -1, -1, -1},
  95         5
  96 };
  97
  98 /*
  99      v2
 100     /  \e2
 101 v1 e1   e3 v3
 102   /e0     \
 103 v0--e5--e4-v4
 104      v5
 105
 106 handle case of one edge selected.
 107 make an edge between v1 and v5,
 108 v5 and v3, and v3 and v1
 109 */
 110 subdpattern t_3edge = {
 111         {1, 1, 1, 1, 1, 1},
 112         {-1, 5, -1, 1, -1, 3}, //creates e6
 113         {0},
 114         {-1, -1, -1, -1, -1, -1, -1},
 115         6
 116 };
 117
 118 /*
 119       e3
 120 v4---------v3
 121 |          |
 122 |e4        | e2
 123 |          |
 124 |e0   e1   |
 125 v0---v1----v2
 126
 127 connect v1 to v4 and v3
 128
 129 */
 130 subdpattern q_1edge = {
 131         {1, 1, 0, 0, 0},
 132         {-1, 3, -1, -1, 1},
 133         {0},
 134         {-1, -1, -1, -1, -1, -1, -1, -1, -1},
 135         5
 136 };
 137
 138 /*
 139       e4
 140 v5---------v4
 141 |          |
 142 |e5        | e3
 143 |          |v3
 144 |e0   e1   | e2
 145 v0---v1----v2
 146
 147 connect v1 to v3
 148
 149 */
 150 subdpattern q_2adjedge = {
 151         {1, 1, 1, 1, 0, 0},
 152         {-1, 3, -1, -1, -1, -1},
 153         {0, 0, 0, 0, 0, 0, 1},
 154         {-1, -1, -1, -1, -1, 6, -1, -1, -1},
 155         6
 156 };
 157
 158
 159 /*
 160    e4 v4 e3
 161 v5---------v3
 162 |          |
 163 |e5        |
 164 |          | e2
 165 |  e0   e1 |
 166 v0---v1----v2
 167
 168 connect v1 to v4
 169
 170 */
 171 subdpattern q_2opedge = {
 172         {1, 1, 0, 1, 1, 0},
 173         {-1, 4, -1, -1, -1, -1},
 174         {0},
 175         {-1, -1, -1, -1, -1, -1, -1, -1, -1},
 176         6
 177 };
 178
 179 /*
 180    e5 v5 e4
 181 v6---------v4
 182 |          |
 183 |e6        | e3
 184 |          | v3
 185 |  e0   e1 | e2
 186 v0---v1----v2
 187
 188 connect v1 to v5, v1 to v3, and v3 to v5
 189
 190 */
 191 subdpattern q_3edge = {
 192         {1, 1, 1, 1, 1, 1, 0},
 193         {-1, 3, -1, 5, -1, 1, -1},
 194         {0},
 195         {-1, -1, -1, -1, -1, -1, -1, -1, -1},
 196         7
 197 };
 198
 199 /*
 200    e5 v5 e4
 201 v6---------v4
 202 |          |
 203 |e6        | e3
 204 |v7        | v3
 205 |e7 e0  e1 | e2
 206 v0---v1----v2
 207
 208 connect v1 to v5, split edge, than connect
 209 v3 and v7 to v8 (new vert from split)
 210
 211 */
 212 subdpattern q_4edge = {
 213         {1, 1, 1, 1, 1, 1, 1, 1},
 214         {-1, 5, -1, -1, -1, -1, -1, -1},
 215         {0, 0, 0, 0, 0, 0, 0, 0, 1},
 216         {-1, -1, -1, 8, -1, -1, -1, 8, -1},
 217         8
 218 };
 219
 220 subdpattern *patterns[] = {
 221         &t_1edge,
 222         &t_2edge,
 223         &t_3edge,
 224         &q_1edge,
 225         &q_2adjedge,
 226         &q_2opedge,
 227         &q_3edge,
 228         &q_4edge,
 229 };
 230
 231 #define PLEN    (sizeof(patterns) / sizeof(void*))
 232
 233 #define SUBD_SPLIT      1
 234 #define FACE_NEW        1
 235 #define MAX_FACE        10
 236
 237 void esubdivide_exec(BMesh *bmesh, BMOperator *op)
 238 {
 239         BMOpSlot *einput;
 240         BMEdge *edge, *nedge, *edges[MAX_FACE];
 241         BMFace *face, *nf;
 242         BMLoop *nl, *loop;
 243         BMVert *v1, *verts[MAX_FACE], *lastv;
 244         BMIter fiter, eiter;
 245         subdpattern *pat;
 246         int i, j, matched, a, b, newlen, newvlen;
 247
 248         BMO_Flag_Buffer(bmesh, op, BMOP_ESUBDIVIDE_EDGES, SUBD_SPLIT);
 249
 250         einput = BMO_GetSlot(op, BMOP_ESUBDIVIDE_EDGES);
 251
 252         /*first go through and split edges*/
 253         for (i=0; i<einput->len; i++) {
 254                 edge = ((BMEdge**)einput->data.p)[i];
 255                 v1 = BM_Split_Edge(bmesh, edge->v1, edge, &nedge, 0.5, 1);
 256                 BMO_SetFlag(bmesh, v1, SUBD_SPLIT);
 257                 BMO_SetFlag(bmesh, nedge, SUBD_SPLIT);
 258         }
 259
 260         /*now go through all the faces and connect the new geometry*/
 261         for (face = BMIter_New(&fiter, bmesh, BM_FACES, NULL); face; face=BMIter_Step(&fiter)) {
 262                 matched = 0;
 263                 if (BMO_TestFlag(bmesh, face, FACE_NEW)) continue;
 264
 265                 if (face->len < MAX_FACE) {
 266                         /*try all possible pattern rotations*/
 267                         for (i=0; i<PLEN; i++) {
 268                                 if (patterns[i]->len != face->len) continue;
 269                                 lastv = NULL;
 270                                 for (j=0; j<patterns[i]->len; j++) {
 271                                         for (a=0, loop=BMIter_New(&eiter, bmesh, BM_LOOPS_OF_FACE,face); loop; a++, loop=BMIter_Step(&eiter)) {
 272                                                 b = (j + a) % patterns[i]->len;
 273
 274                                                 edge = loop->e;
 275                                                 verts[b] = loop->v;
 276                                                 edges[b] = edge;
 277                                                 if (!(patterns[i]->seledges[b] == BMO_TestFlag(bmesh, edge, SUBD_SPLIT))) break;
 278
 279                                                 lastv = verts[b];
 280                                         }
 281
 282                                         if (a == face->len) {
 283                                                 matched = 1;
 284                                                 pat = patterns[i];
 285                                                 break;
 286                                         }
 287                                 }
 288                                 if (matched) break;
 289                         }
 290                 }
 291
 292                 if (matched) {
 293                         /*first stage*/
 294                         newlen = pat->len;
 295                         for (i=0; i<pat->len; i++) {
 296                                 if (pat->connectverts[i] != -1) {
 297                                         edges[newlen++] = BM_Connect_Verts(bmesh, verts[i], verts[pat->connectverts[i]], &nf);
 298                                         BMO_SetFlag(bmesh, nf, FACE_NEW);
 299                                 }
 300                         }
 301
 302                         newvlen = pat->len;
 303                         /*second stage*/
 304                         for (i; i<newlen; i++) {
 305                                 if (pat->secondstage_splitedges[i]) {
 306                                         v1 = BM_Split_Edge(bmesh, edges[i]->v1, edges[i], &nedge, 0.5, 1);
 307                                         verts[newvlen++] = v1;
 308                                 }
 309                         }
 310
 311                         for (i=0; i<newvlen; i++) {
 312                                 if (pat->secondstage_connect[i] != -1) {
 313                                         edges[newlen++] = BM_Connect_Verts(bmesh, verts[i], verts[pat->secondstage_connect[i]], &nf);
 314                                         BMO_SetFlag(bmesh, nf, FACE_NEW);
 315                                 }
 316                         }
 317                 } else { /*no match in the pattern*/
 318                         /*this should do some sort of generic subdivision*/
 319                 }
 320         }
 321 }