Begin port of edge subdivide (with multicut) to
[blender.git] / source / blender / bmesh / operators / subdivideop.c
1 #include "MEM_guardedalloc.h"
2
3 #include "BKE_utildefines.h"
4
5 #include "BLI_arithb.h"
6 #include "BLI_rand.h"
7
8 #include "DNA_object_types.h"
9
10 #include "ED_mesh.h"
11
12 #include "bmesh.h"
13 #include "mesh_intern.h"
14
15 #include <stdio.h>
16 #include <stdlib.h>
17 #include <string.h>
18 #include <math.h>
19
20 #define SUBD_SPLIT      1
21 #define FACE_NEW        1
22 #define MAX_FACE        800
23
24 /*
25 note: this is a pattern-based edge subdivider.
26 it tries to match a pattern to edge selections on faces,
27 then executes functions to cut them.
28 */
29 typedef struct subdpattern {
30         int seledges[20]; //selected edges mask, for splitting
31
32         /*verts starts at the first new vert cut, not the first vert in the
33           face*/
34         void (*connectexec)(BMesh *bm, BMFace *face, BMVert **verts, 
35                             int numcuts, int beauty, float rad);
36         int len; /*total number of verts*/
37 } subdpattern;
38
39 /*generic subdivision rules:
40   
41   * two selected edges in a face should make a link
42     between them.
43
44   * one edge should do, what? make pretty topology, or just
45     split the edge only?
46 */
47
48
49 /* calculates offset for co, based on fractal, sphere or smooth settings  */
50 static void alter_co(float *co, BMEdge *edge, float rad, int beauty, float perc)
51 {
52         float vec1[3], fac;
53         
54         if(beauty & B_SMOOTH) {
55                 /* we calculate an offset vector vec1[], to be added to *co */
56                 float len, fac, nor[3], nor1[3], nor2[3];
57                 
58                 VecSubf(nor, edge->v1->co, edge->v2->co);
59                 len= 0.5f*Normalize(nor);
60         
61                 VECCOPY(nor1, edge->v1->no);
62                 VECCOPY(nor2, edge->v2->no);
63         
64                 /* cosine angle */
65                 fac= nor[0]*nor1[0] + nor[1]*nor1[1] + nor[2]*nor1[2] ;
66                 
67                 vec1[0]= fac*nor1[0];
68                 vec1[1]= fac*nor1[1];
69                 vec1[2]= fac*nor1[2];
70         
71                 /* cosine angle */
72                 fac= -nor[0]*nor2[0] - nor[1]*nor2[1] - nor[2]*nor2[2] ;
73                 
74                 vec1[0]+= fac*nor2[0];
75                 vec1[1]+= fac*nor2[1];
76                 vec1[2]+= fac*nor2[2];
77                 
78                 vec1[0]*= rad*len;
79                 vec1[1]*= rad*len;
80                 vec1[2]*= rad*len;
81                 
82                 co[0] += vec1[0];
83                 co[1] += vec1[1];
84                 co[2] += vec1[2];
85         }
86         else {
87                 if(rad > 0.0) {   /* subdivide sphere */
88                         Normalize(co);
89                         co[0]*= rad;
90                         co[1]*= rad;
91                         co[2]*= rad;
92                 }
93                 else if(rad< 0.0) {  /* fractal subdivide */
94                         fac= rad* VecLenf(edge->v1->co, edge->v2->co);
95                         vec1[0]= fac*(float)(0.5-BLI_drand());
96                         vec1[1]= fac*(float)(0.5-BLI_drand());
97                         vec1[2]= fac*(float)(0.5-BLI_drand());
98                         VecAddf(co, co, vec1);
99                 }
100
101         }
102 }
103
104 /* assumes in the edge is the correct interpolated vertices already */
105 /* percent defines the interpolation, rad and beauty are for special options */
106 /* results in new vertex with correct coordinate, vertex normal and weight group info */
107 static BMVert *bm_subdivide_edge_addvert(BMesh *bm, BMEdge *edge, float rad, 
108                                          int beauty, float percent, BMEdge **out)
109 {
110         BMVert *ev;
111 //      float co[3];
112         
113         ev = BM_Split_Edge(bm, edge->v1, edge, out, percent, 1);
114
115         /* offset for smooth or sphere or fractal */
116         alter_co(ev->co, edge, rad, beauty, percent);
117
118 #if 0 //TODO
119         /* clip if needed by mirror modifier */
120         if (edge->v1->f2) {
121                 if ( edge->v1->f2 & edge->v2->f2 & 1) {
122                         co[0]= 0.0f;
123                 }
124                 if ( edge->v1->f2 & edge->v2->f2 & 2) {
125                         co[1]= 0.0f;
126                 }
127                 if ( edge->v1->f2 & edge->v2->f2 & 4) {
128                         co[2]= 0.0f;
129                 }
130         }
131 #endif  
132         
133         return ev;
134 }
135
136 static BMVert *subdivideedgenum(BMesh *bm, BMEdge *edge, 
137                                 int curpoint, int totpoint, float rad, 
138                                 int beauty, BMEdge **newe)
139 {
140         BMVert *ev;
141         float percent;
142          
143         if (beauty & (B_PERCENTSUBD) && totpoint == 1)
144                 /*I guess the idea is vertices store what
145                   percent to use?*/
146                 //percent=(float)(edge->tmp.l)/32768.0f;
147                 percent= 1.0; //edge->tmp.fp;
148         else {
149                 percent= 1.0f/(float)(totpoint+1-curpoint);
150
151         }
152         
153         /*{
154                 float co[3], co2[3];
155                 VecSubf(co, edge->v2->co, edge->v1->co);
156                 VecMulf(co, 1.0f/(float)(totpoint+1-curpoint));
157                 VecAddf(co2, edge->v1->co, co);
158 */
159                 ev= bm_subdivide_edge_addvert(bm, edge, rad, beauty, percent, newe);
160 /*              VECCOPY(ev->co, co2);
161         }
162 */      
163         return ev;
164 }
165
166 static void bm_subdivide_multicut(BMesh *bm, BMEdge *edge, float rad,
167                                   int beauty, int numcuts) {
168         BMEdge *eed = edge, *newe;
169         BMVert *v;
170         int i;
171
172         for(i=0;i<numcuts;i++) {
173                 v = subdivideedgenum(bm, eed, i, numcuts, rad, beauty, &newe);
174                 BMO_SetFlag(bm, v, SUBD_SPLIT);
175                 BMO_SetFlag(bm, eed, SUBD_SPLIT);
176         }
177 }
178
179 /*note: the patterns are rotated as necassary to
180   match the input geometry.  they're based on the
181   pre-split state of the  face*/
182
183 /*
184      
185 v3---------v2
186 |          |
187 |          |
188 |          |
189 |          |
190 v4---v0---v1
191
192 */
193 static void q_1edge_split(BMesh *bm, BMFace *face, BMVert **vlist, int numcuts,
194                           int beauty, float rad) {
195         BMFace *nf;
196         int i, add;
197
198         /*if it's odd, the middle face is a quad, otherwise it's a triangle*/
199         if (numcuts % 2==0) {
200                 add = 2;
201                 for (i=0; i<numcuts; i++) {
202                         if (i == numcuts/2) add -= 1;
203                         BM_Connect_Verts(bm, vlist[i], vlist[numcuts+add], &nf);
204                 }
205         } else {
206                 add = 2;
207                 for (i=0; i<numcuts; i++) {
208                         BM_Connect_Verts(bm, vlist[i], vlist[numcuts+add], &nf);
209                         if (i == numcuts/2) {
210                                 add -= 1;
211                                 BM_Connect_Verts(bm, vlist[i], vlist[numcuts+add], &nf);
212                         }
213                 }
214
215         }
216 }
217
218 subdpattern q_1edge = {
219         {1, 0, 0, 0},
220         q_1edge_split,
221         4,
222 };
223
224
225 /*
226  
227 v4---v3---v2
228 |     s    |
229 |          |
230 |          |
231 |     s    |
232 v5---v0---v1
233
234 */
235 static void q_2edge_op_split(BMesh *bm, BMFace *face, BMVert **vlist, 
236                              int numcuts, int beauty, float rad) {
237         BMFace *nf;
238         int i;
239         
240         for (i=0; i<numcuts; i++) {
241                 BM_Connect_Verts(bm, vlist[i], vlist[(numcuts-i-1)+numcuts+2], &nf);
242         }
243 }
244
245 subdpattern q_2edge_op = {
246         {1, 0, 1, 0},
247         q_2edge_op_split,
248         4,
249 };
250
251 /*
252 v6--------v5
253 |          |
254 |          |v4s
255 |          |v3s
256 |   s  s   |
257 v7-v0--v1-v2
258
259 */
260 static void q_2edge_split(BMesh *bm, BMFace *face, BMVert **vlist, 
261                              int numcuts, int beauty, float rad) {
262         BMFace *nf;
263         int i;
264         
265         for (i=0; i<numcuts; i++) {
266                 BM_Connect_Verts(bm, vlist[i], vlist[numcuts+(numcuts-i)], &nf);
267         }
268         BM_Connect_Verts(bm, vlist[numcuts*2+3], vlist[numcuts*2+1], &nf);
269 }
270
271 subdpattern q_2edge = {
272         {1, 1, 0, 0},
273         q_2edge_split,
274         4,
275 };
276
277 /*  s   s
278 v8--v7--v6-v5
279 |          |
280 |          v4 s
281 |          |
282 |          v3 s
283 |   s  s   |
284 v9-v0--v1-v2
285
286 */
287 static void q_3edge_split(BMesh *bm, BMFace *face, BMVert **vlist, 
288                              int numcuts, int beauty, float rad) {
289         BMFace *nf;
290         int i, add=0;
291         
292         for (i=0; i<numcuts; i++) {
293                 if (i == numcuts/2) {
294                         if (numcuts % 2 != 0) {
295                                 BM_Connect_Verts(bm, vlist[numcuts-i-1+add], vlist[i+numcuts+1], &nf);
296                         }
297                         add = numcuts*2+2;
298                 }
299                 BM_Connect_Verts(bm, vlist[numcuts-i-1+add], vlist[i+numcuts+1], &nf);
300         }
301
302         for (i=0; i<numcuts/2+1; i++) {
303                 BM_Connect_Verts(bm, vlist[i], vlist[(numcuts-i)+numcuts*2+1], &nf);
304         }
305 }
306
307 subdpattern q_3edge = {
308         {1, 1, 1, 0},
309         q_3edge_split,
310         4,
311 };
312
313 /*
314  
315            v8--v7-v6--v5
316            |     s    |
317            |v9 s     s|v4
318 first line |          |   last line
319            |v10s s   s|v3
320            v11-v0--v1-v2
321
322            it goes from bottom up
323 */
324 static void q_4edge_split(BMesh *bm, BMFace *face, BMVert **vlist, int numcuts,
325                           int beauty, float rad) {
326         BMFace *nf;
327         BMVert *v;
328         BMEdge *e, *ne;
329         BMVert **lines = MEM_callocN(sizeof(BMVert*)*(numcuts+2)*(numcuts+2),
330                                      "q_4edge_split");
331         int i, j, a, b, s=numcuts+2, totv=numcuts*4+4;
332
333         /*build a 2-dimensional array of verts,
334           containing every vert (and all new ones)
335           in the face.*/
336
337         /*first line*/
338         for (i=0; i<numcuts+2; i++) {
339                 lines[i] = vlist[numcuts*3+2+(numcuts-i+1)];
340         }
341
342         /*last line*/
343         for (i=0; i<numcuts+2; i++) {
344                 lines[(s-1)*s+i] = vlist[numcuts+i];
345         }
346         
347         /*first and last members of middle lines*/
348         for (i=0; i<numcuts; i++) {
349                 a = i;
350                 b = numcuts + 1 + numcuts + 1 + (numcuts - i - 1);
351                 
352                 e = BM_Connect_Verts(bm, vlist[a], vlist[b], &nf);
353                 
354                 lines[(i+1)*s] = vlist[a];
355                 lines[(i+1)*s + s-1] = vlist[b];
356
357                 for (a=0; a<numcuts; a++) {
358                         v = subdivideedgenum(bm, e, a, numcuts, rad, beauty, &ne);
359                         lines[(i+1)*s+a+1] = v;
360                 }
361         }
362
363         for (i=1; i<numcuts+2; i++) {
364                 for (j=1; j<numcuts+1; j++) {
365                         a = i*s + j;
366                         b = (i-1)*s + j;
367                         BM_Connect_Verts(bm, lines[a], lines[b], &nf);
368                 }
369         }
370
371         /*
372         for (i=0; i<numcuts; i++) {
373                 a = i;
374                 b = numcuts + 1 + numcuts + 1 + (numcuts - i - 1);
375                 BM_Connect_Verts(bm, vlist[a], vlist[b], &nf);
376         }*/
377
378         MEM_freeN(lines);
379 }
380
381 subdpattern q_4edge = {
382         {1, 1, 1, 1},
383         q_4edge_split,
384         4,
385 };
386
387 subdpattern *patterns[] = {
388         &q_1edge,
389         &q_2edge_op,
390         &q_4edge,
391         &q_3edge,
392         &q_2edge,
393 };
394
395 #define PLEN    (sizeof(patterns) / sizeof(void*))
396
397 typedef struct subd_facedata {
398         BMVert *start; subdpattern *pat;
399 } subd_facedata;
400
401 void esubdivide_exec(BMesh *bmesh, BMOperator *op)
402 {
403         BMOpSlot *einput;
404         BMEdge *edge, *edges[MAX_FACE];
405         BMFace *face;
406         BMLoop *nl;
407         BMVert *verts[MAX_FACE];
408         BMIter fiter, liter;
409         subdpattern *pat;
410         float rad;
411         int i, j, matched, a, b, numcuts, flag, selaction;
412         subd_facedata *facedata = NULL;
413         V_DECLARE(facedata);
414         
415         BMO_Flag_Buffer(bmesh, op, BMOP_ESUBDIVIDE_EDGES, SUBD_SPLIT);
416         
417         numcuts = BMO_GetSlot(op, BMOP_ESUBDIVIDE_NUMCUTS)->data.i;
418         flag = BMO_GetSlot(op, BMOP_ESUBDIVIDE_FLAG)->data.i;
419         rad = BMO_GetSlot(op, BMOP_ESUBDIVIDE_RADIUS)->data.f;
420         selaction = BMO_GetSlot(op, BMOP_ESUBDIVIDE_SELACTION)->data.i;
421
422         einput = BMO_GetSlot(op, BMOP_ESUBDIVIDE_EDGES);
423         
424         /*first go through and split edges*/
425         for (i=0; i<einput->len; i++) {
426                 edge = ((BMEdge**)einput->data.p)[i];
427                 BMO_SetFlag(bmesh, edge, SUBD_SPLIT);
428         }
429         
430         for (face=BMIter_New(&fiter, bmesh, BM_FACES, NULL);
431              face; face=BMIter_Step(&fiter)) {
432                 /*figure out which pattern to use*/
433                 if (face->len > MAX_FACE) continue;
434
435                 i = 0;
436                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
437                      nl; nl=BMIter_Step(&liter)) {
438                         edges[i] = nl->e;
439                         verts[i] = nl->v;
440                         i++;
441                 }
442
443                 for (i=0; i<PLEN; i++) {
444                         pat = patterns[i];
445                         if (pat->len == face->len) {
446                                 for (a=0; a<pat->len; a++) {
447                                 matched = 1;
448                                 for (b=0; b<pat->len; b++) {
449                                         j = (b + a) % pat->len;
450                                         if ((!!BMO_TestFlag(bmesh, edges[j], SUBD_SPLIT))
451                                                 != (!!pat->seledges[b])) {
452                                                         matched = 0;
453                                                         break;
454                                         }
455                                 }
456                                 if (matched) break;
457                                 }
458                                 if (matched) {
459                                         V_GROW(facedata);
460                                         BMO_SetFlag(bmesh, face, SUBD_SPLIT);
461                                         j = V_COUNT(facedata) - 1;
462                                         facedata[j].pat = pat;
463                                         facedata[j].start = verts[a];
464                                         break;
465                                 }
466                         }
467                 }
468         }
469
470         /*go through and split edges*/
471         for (i=0; i<einput->len; i++) {
472                 edge = ((BMEdge**)einput->data.p)[i];
473                 bm_subdivide_multicut(bmesh, edge, rad, flag, numcuts);
474                 //BM_Split_Edge_Multi(bmesh, edge, numcuts);
475         }
476
477         //if (facedata) V_FREE(facedata);
478         //return;
479
480         i = 0;
481         for (face=BMIter_New(&fiter, bmesh, BM_FACES, NULL);
482              face; face=BMIter_Step(&fiter)) {
483                 /*figure out which pattern to use*/
484                 if (face->len > MAX_FACE) continue;
485                 if (BMO_TestFlag(bmesh, face, SUBD_SPLIT) == 0) continue;
486                 
487                 pat = facedata[i].pat;
488                 if (!pat) continue;
489
490                 j = a = 0;
491                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
492                      nl; nl=BMIter_Step(&liter)) {
493                         if (nl->v == facedata[i].start) {
494                                 a = j+1;
495                                 break;
496                         }
497                         j++;
498                 }
499
500                 j = 0;
501                 for (nl=BMIter_New(&liter, bmesh, BM_LOOPS_OF_FACE, face);
502                      nl; nl=BMIter_Step(&liter)) {
503                         b = (j-a+face->len) % face->len;
504                         verts[b] = nl->v;
505                         j += 1;
506                 }
507                 
508                 pat->connectexec(bmesh, face, verts, numcuts, flag, rad);
509                 i++;
510         }
511
512         if (facedata) V_FREE(facedata);
513 }
514
515 /*editmesh-emulating function*/
516 void BM_esubdivideflag(Object *obedit, BMesh *bm, int flag, float rad, 
517                        int beauty, int numcuts, int seltype) {
518         BMOperator op;
519
520         BMO_Init_Op(&op, BMOP_ESUBDIVIDE);
521         BMO_Set_Int(&op, BMOP_ESUBDIVIDE_NUMCUTS, numcuts);
522         BMO_Set_Int(&op, BMOP_ESUBDIVIDE_FLAG, beauty);
523         BMO_Set_Float(&op, BMOP_ESUBDIVIDE_RADIUS, rad);
524         BMO_Set_Int(&op, BMOP_ESUBDIVIDE_SELACTION, seltype);
525         BMO_HeaderFlag_To_Slot(bm, &op, BMOP_ESUBDIVIDE_EDGES, flag, BM_EDGE);
526         
527         BMO_Exec_Op(bm, &op);
528         BMO_Finish_Op(bm, &op);
529 }